數據結構之數組與廣義表課件(存儲版)
【正文】 6 1 3 對稱矩陣有 n*n個元素，但只存儲 n*(n+1)/2個元素即可 . 若以 行序 為主序，把下三角中的元素，存儲在一個一維數組 SA[n*(n+1)/2] 中，則 A[i,j] 和 SA[k] 的對應關系如下： 若 i=j , 則 A[i, j]在下三角中， A[i, j]之前共有1+2+……+i+j = i*(i+1)/2+j 個元素，因此有 k= i*(i+1)/2 + j [注 ]:假定矩陣的行和列從 0開始 , 一維數組的編址從 0開始 . 若 ij , 則 A[i, j]在上三角中，因為A[i,j]=A[j,i], 所以交換上述公式中的 i和 j即可 ,因此有 k= j*(j+1)/2 + i 上頁的矩陣對應的一維數組如下： 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 A[3,0]對應的地址： k=3*4/2+0=6 A[2,4]對應的地址： k=4*5/2+2=12 1 5 0 1 8 9 3 0 2 5 7 0 6 1 3 2. 三角矩陣的壓縮存儲 三角矩陣 : 矩陣的上 (下 )三角 (不包含主 角線 )元素為同一個常數的方陣 . 我們可用對稱矩陣存儲的思想存儲之 . 如數組 A，有 n*(n+1)/2+1個非零元素 , 可以只存儲 n*(n+1)/2+2個元素即可 . 1 0 0 0 A= 2 3 0 0 4 5 6 0 7 8 9 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1 0 數組的第 n*(n+1)/2 (最后一個元素）表示矩陣中的上三角元素 0。 數組的特點： 元素類型必須相同； 可對每一個元素隨機訪問 , 數組中的元素個數是固定的。 例 : 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ī)律，所以不能采用以前的壓縮方法。 /*矩陣的列數 */ int tn。 /*列數變行數 */ =。 [j].element=[k].element。 struct node *right。 例 : 2 0 0 4 M= 0 2 0 0 1 0 0 0 其三元組為 : (1,1,2), (1,4,4), (2,2,2), (3,1,1,) 其十字鏈表為 : ...... 廣義表 ?廣義表的定義 線性表中的數據元素的類型必須是相同的，而且必須是原子項
試題試卷相關推薦
鄂ICP備17016276號-1