陣列的位址計算.

Presentation on theme: "陣列的位址計算."— Presentation transcript:

1 陣列的位址計算

2 陣列的表示 名稱 起始位址(第一個元素儲存的位址） 維度(Dimension) 索引(Index)上限 索引(Index)下限
元素的資料型態(決定所佔的記憶體大小) 元素個數（索引上限－索引下限＋1）

3 一維陣列→起始位置+元素長度*索引 起始位置 元素的長度
例如 int Array[7]始位置為1000，一個int元素長度是2byte，那麼Array[7]的記憶體為何？ 索引 Array[0] Array[1] Array[2] Array[3] Array[4] Array[5] Array[6] Array[7] 記憶體 1000 1002 1004 1006 1008 1010 1012 1014

4 二維陣列 二維陣列的儲存方式會分為兩種： 以列為主(Row-Major)：每一列走完換一行
以行為主(Column-Major)：每一行走完換一列

5 以列為主(Row-Major) 定義一個int Array[2][6],假設Array[0][0]的位址是1000,求Array[1][1]? Array[i][j]的記憶位址 = 起始位址 +  (元素距離) * [ (j * 每一行元素個數) + i ] 索引 Array[0][0] Array[0][1] Array[0][2] Array[0][3] Array[0][4] Array[0][5] 記憶體 1000 1002 1004 1006 1008 1010 Array[1][0] Array[1][1] Array[1][2] Array[1][3] Array[1][4] Array[1][5] 1012 1014 1016 1018 1020 1022

6 以行為主(Column-Major) 定義一個int Array[2][6],假設Array[0][0]的位址是1000,求Array[1][1]? Array[i][j] 的記憶體 = 起始位址 +  (元素大小) * [ (i * 每一列元素個數) + j ] 索引 Array[0][0] Array[0][1] Array[0][2] Array[0][3] Array[0][4] Array[0][5] 記憶體 1000 1004 1008 1012 1016 1020 Array[1][0] Array[1][1] Array[1][2] Array[1][3] Array[1][4] Array[1][5] 1002 1006 1010 1014 1018 1022

7 陣列位址公式表示法

8 一維陣列A[1 to n] a1a2.....an名稱：A 起始位址： 維度：1 索引上限：n 索引下限：1
元素的大小或長度(資料型態)：d 元素個數：n 儲存方式：元素a j的儲存位址為 Location(a j)＝＋( j－1) × d 說明如下： a 1的儲存位址為 a 2的儲存位址為＋d＝＋(2-1)×d a 3的儲存位址為＋d＝＋(3-1)×d ． a j的儲存位址為＋d＝＋( j-1)×d

9 二維陣列A[1 to am , 1 to an] a1,1a1,2.....a1,na2,1a2,2.....a2,n am,1am,2.....am,n 名稱：A 起始位址： 維度：1 索引1上限：m 索引2上限：n 索引1,2下限：1 元素的大小或長度(資料型態)：d 元素個數：m×n 儲存方式：轉換成一維(1)以列為主(Row-Major)或是(2)以行為主(Column-Major)

10 (1)以列為主(Row-Major) 若二維陣列為A[1 to am , 1 to an]，則
Location(a i , j)＝＋( i－1) × n × d＋( j－1) × d 若二維陣列為A[l1 to am , l2 to an]，則 Location(a i , j)＝＋( i－l1) × (n－l2＋1) × d＋( j－l2) × d

11 (2)以行為主(Column-Major)
若二維陣列為A[1 to am , 1 to an]，則 Location(a i , j)＝＋( j－1)×m ×d＋( i－1) × d 若二維陣列為A[l1 to am , l2 to an]，則 Location(a i , j)＝＋( j－l2) × (m－l1+1) × d＋( i－l1) × d

12 一維陣列範例(一) － 求第n項的費氏級數

13 一維陣列範例(二) －求質數

14 二維陣列範例 －九九乘法表

15 應用－矩陣與多項式

16 前言 由於早期電腦的記憶體昂貴，程式設計師必須節省記憶空間 陣列的早期應用多集中於如何有效率地利用記憶體空間 如多項式和稀疏矩陣的表示法。

17 稀疏矩陣 矩陣的大部分元素都為零即稱稀疏矩陣 表示一個陣列中如果有很多位置沒有被使用，造成記憶體的浪費
我們可以將其轉變成另一個小的陣列,減少記憶體使用。

18 比方說一個陣列如下： 可以轉成一個新的陣列如下：
原本的陣列是int型態，總共用去5(行)*4(列)*2(int型態是2byte) = 40。 索引 1 2 3 7 4 5

19 可以轉成一個新的陣列如下： 範例 新的的元素是int型態，總共用去5(行)*3(列)*2(int型態是2byte) = 30。
40byte -30byte = 10byte，減少了10byte空間。 範例 索引 1 2 備註 5 4 原陣列有5行4列4個值 3 7 第0行第3列是7 第1行第1列是4 第2行第3列是1 第3行第0列是5

20 上三角陣列 一個方陣中對角線左下方都是0稱之。 設int first[5[5]： 索引 1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

21 為了減少記憶體的使用,和稀疏陣列一樣可以轉換成一個新的陣列
新陣列的排法分為以列為主及以行為主： 把原陣列first當成一個梯形 梯形公式是(上底+下底)*高/2  (1+5)*5/2 = 15 ＝＞新陣列為int second[15]。

22 索引 1 2 3 4 5 6 7 8 9 10 11 12 13 14 值 15 以列為主 兩個陣列轉換的關係： 令first[x][x]是原陣列,因為是方形矩陣,所以長寬相等,都是x 令y = (1+x) * x / 2,second[y]為壓縮後的陣列 令i,j是表示索引值 ＝＞兩個陣列的關係： first[i][j] = second[ [ ( x + 1 ) + ( x - i ) ] *  i / 2 + ( j - i ) ]

23 索引 1 2 3 4 5 6 7 8 9 10 11 12 13 14 值 15 以行為主 兩個陣列轉換的關係： 令first[x][x]是原陣列,因為是方形矩陣,所以長寬相等,都是x 令y = (1+x) * x / 2,second[y]為壓縮後的陣列 令i,j是表示索引值 ＝＞兩個陣列的關係： first[i][j] = second[j * ( j + 1 ) / 2 + i ]

24 下三角陣列 一個方陣中對角線右上方都是0稱之，假設int first[5][5]： 索引 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

25 為了減少記憶體的使用，和稀疏陣列一樣可以轉換成一個新的陣列
新陣列的排法分為以列為主及以行為主： 把原陣列first當成一個梯形 梯形公式是(上底+下底)*高/2  (1+5)*5/2 = 15 ＝＞新陣列為int second[15]。

26 以列為主 兩個陣列轉換的關係： 令first[x][x]是原陣列,因為是方形矩陣,所以長寬相等,都是x 令y = (1+x) * x / 2,second[y]為壓縮後的陣列 令i , j是表示索引值 ＝＞兩個陣列的關係： first[i][j] = second[ i * ( i + 1 ) / 2 + j ]。

27 以行為主 兩個陣列轉換的關係： 令first[x][x]是原陣列,因為是方形矩陣,所以長寬相等,都是x 令y = (1+x) * x / 2,second[y]為壓縮後的陣列 令i , j是表示索引值 ＝＞兩個陣列的關係： first[i][j] = second[ (x + 1) + ( x - j ) ] * j / 2 + ( i - j) ]

28 多項式 P(x)＝anxn＋an-1xn-1＋…＋a1x＋a0

29 int A[1 to n＋2]＝{n, an, an-1,an-2,．．．,a0 } ;
儲存方式有兩種表示方式： 使用一個n＋2長度的一維陣列A來儲存，陣列的第一個位置儲存最高項的指數n，其餘依指數遞減，依序儲存對應的係數 int A[1 to n＋2]＝{n, an, an-1,an-2,．．．,a0 } ; 只儲存非零項，若有m項則使用一個2m＋1長度的一維陣列A來儲存，陣列的第一個位置儲存非零項個數m，其餘依指數遞減，依序儲存每一個非零項的指數與係數 int A[1 to 2m＋1]＝{m, e m-1, a m-1,e n-2, a n-2,．．．, e 0, a 0 } ;

30 結語 近年來電腦科技與元件製造技術精進，記憶體的價格不再高不可攀，節省空間不再是主要的考量，資料輸出入及處理的時間效率已是程式設計師的主要考量了，例如影像處理時會開啟一個很大的陣列，並將圖片或影像資料直接存放在這個陣列中，直接由此陣列存取資料，而不再以磁碟中的檔案資料做處理，如此一來，即可有效地節省輸出入的時間。