二维阵列.pptVIP

陣列的位址計算 陣列的表示 名稱 起始位址(第一個元素儲存的位址） 維度(Dimension) 索引(Index)上限 索引(Index)下限 元素的資料型態(決定所佔的記憶體大小) 元素個數（索引上限－索引下限＋1） 一維陣列→起始位置+元素長度*索引 起始位置 元素的長度 例如int Array[7]始位置為1000，一個int元素長度是2byte，那麼Array[7]的記憶體為何？ 二維陣列 二維陣列的儲存方式會分為兩種： 以列為主(Row-Major)：每一列走完換一行 以行為主(Column-Major)：每一行走完換一列 以列為主(Row-Major) 定義一個int Array[2][6],假設Array[0][0]的位址是1000,求Array[1][1]? Array[i][j]的記憶位址 = 起始位址 +? (元素距離)?* [ (j * 每一行元素個數) +?i ] 以行為主(Column-Major) 定義一個int Array[2][6],假設Array[0][0]的位址是1000,求Array[1][1]? Array[i][j] 的記憶體 = 起始位址 +? (元素大小)?* [ (i * 每一列元素個數) + j ] 陣列位址公式表示法 一維陣列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 二維陣列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) (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 (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 一維陣列範例(一) － 求第n項的費氏級數 一維陣列範例(二) －求質數 二維陣列範例 －九九乘法表 應用－矩陣與多項式 前言 由於早期電腦的記憶體昂貴，程式設計師必須節省記憶空間 陣列的早期應用多集中於如何有效率地利用記憶體空間 如多項式和稀疏矩陣的表示法。 稀疏矩陣 矩陣的大部分元素都為零即稱稀疏矩陣 表示一個陣列中如果有很多位置沒有被使用，造成記憶體的浪費 我們可以將其轉變成另一個小的陣列,減少記憶體使用。 比方說一個陣列如下： 可以轉成一個新的陣列如下： 原本的陣列是int型態，總共用去5(行)*4(列)*2(int型態是2byte) = 40。 可以轉成一個新的陣列如下： 新的的元素是int型態，總共用去5(行)*3(列)*2(int型態是2byte) = 30。 40byte -30byte = 10byte，減少了10byte空間。 範例 上三角陣列 一個方陣中對角線左下方都是0稱之。 設int first[5[5]： 為了減少記憶體的使用,和稀疏陣列一樣可以轉換成一個新的陣列 新陣列的排法分為以列為主及以行為主： 把原陣列first當成一個梯形梯形公式是(上底+下底)*高/2?(1+5)*5/2 = 15 ＝＞新陣列為int second[15]。 以列為主 兩個陣列轉換的關係： 令first[x][x]是原陣列,因為是方形矩陣,所以長寬相等,都是x 令y = (1+x)?* x / 2,second[y]為壓縮後的陣列 令i,j是表示索引值 ＝＞兩個陣列的關係：fi