數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組與廣義表課件-展示頁
2024-09-12 09:02本頁面
【正文】 空間中。 數(shù)組的特點(diǎn)： 元素類型必須相同； 可對每一個元素隨機(jī)訪問 , 數(shù)組中的元素個數(shù)是固定的。 ?計算數(shù)組元素存儲地址的公式稱為 尋址公式 。 1. 一維數(shù)組的尋址公式 對于一維數(shù)組，若其第一個元素的首地址為 Loc(a0)，下標(biāo)為 i 的數(shù)組元素 A[i]的地址為 Loc(ai)， 則 Loc(ai) = Loc(a0) + k * i ( 0≤i≤n1) 2. 二維數(shù)組的尋址公式 二維數(shù)組分為 以行為主序存儲 和 以行為主序存儲 . 在 C語言中，采用以 行為主序 存儲 在 FORTRAN語言中，采用以 列為主序 存儲 設(shè)二維數(shù)組 A[m][n]， m、 n分別表示數(shù)組的行數(shù)和列數(shù)，用 Loc (aij)表示數(shù)組元素 A[i][j]的地址 . 設(shè)每個元素占用 k個存儲單元，則尋址公式為 : 若 以行為主序，則 Loc(ai,j) = Loc(a00) + (i*n+j)*k 若 以列為主序 ，則 Loc(ai,j) = Loc(a00) + (j*m+i)*k [注 ]:假設(shè)數(shù)組從 0開始編址 . 例：二維數(shù)組 A[5, 6]，設(shè)每一元素占32位，若以 行序為主 序存儲， 1. 數(shù)組 A共占多少個字節(jié) ? 2. 若 A的起始地址是 1000， A[2,5]的地 址是多少？ 解： 1. 共有 30個元素 30*4=120 個字節(jié) 2. Loc[2,5]=loc[0,0]+(2*6+5)*4 =1068 特殊矩陣的壓縮存儲 1. 對稱矩陣的壓縮存儲 一個 n階矩陣，滿足 A[i,j]=A[j,i] 則稱為對稱矩陣。 當(dāng) i=j 時 , k=i*(i+1)/2+j 當(dāng) ij 時 , k=n*(n+1)/2 例 : 元素 A[3, 2], 對應(yīng)的地址 k=3*4/2 + 2=8 ?若一個 m*n矩陣，有 s個非 0元素， 記 e=s/(m*n) e 稱為 稀疏因子 。 例 : 0 2 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 4 0 M= 0 0 0 0 0 0 0 0 8 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 9 0 ?在稀疏矩陣中，非 0元素的排列無規(guī)律，所以不能采用以前的壓縮方法。 其中 i： 非 0元素的行號 j： 非 0元素的列號 A[i, j]：非 0元素的值 如上例矩陣用三元組表示成： (1,2,2), (1,3,1), (3,1,1), (3,6,4), (5,2,8), (6,1,5), (7,6,9) 稀疏矩陣的三元組定義
試題試卷相關(guān)推薦
鄂ICP備17016276號-1