1、1 第第5章章 數組和廣義表數組和廣義表5.1 數組的定義5.2 數組的順序表示和實現5.3 矩陣的壓縮存儲5.4 廣義表的定義5.5 廣義表的存儲結構25.1 5.1 數組的定義數組的定義二維數組： a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1 Amn= 可以看成是由若干個行向量行向量組成的向量，也可以看成是由若干個列向量列向量組成的向量。 數組一旦被定義，它的維數和維界就不再改變。因此，除了結構的初始化和銷毀之外，數組只有存取元素和修改元素值的操作。 抽象數據類型定義：P903 5.2 5.2 數組的順序表示和實現數組的順序表示和

2、實現 由于計算機的內存結構是一維的，因此用一維內存來表示多維數組，就必須按某種次序將數組元素排成一列序列，然后將這個線性序列存放在存儲器中。 4通常有兩種順序存儲方式：行優先順序行優先順序將數組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數組為例，按行優先順序存儲的線性序列為： a00,a01,a0,n-1,a10,a1,n-1,am-1,1,am-1,n-1 在PASCAL、C語言中，數組就是按行優先順序存儲的。列優先順序列優先順序將數組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，A的m*n個元素按列優先順序存儲的線性序列為：a00,a10,am-1,0,a01

3、,a11,am-1,1,an-1,1,an-1,m-1在FORTRAN語言中，數組就是按列優先順序存儲的。5 多維數組的情況多維數組的情況：行優先順序可規定為先排最右的下標，從右到左，最后排最左下標；列優先順序與此相反，先排最左下標，從左向右，最后排最右下標。 按上述兩種方式順序存儲的數組，只要知道開始開始元素的存放地址元素的存放地址（即基地址基地址），維數和每維的上、每維的上、下界下界，以及每個數組元素所占用的單元數元素所占用的單元數，就可以將數組元素的存放地址表示為其下標的線性函數。因此，數組中的任一元素可以在相同的時間內存取，即順序存儲的數組是一個隨機存取結構隨機存取結構。6例如，二維數

4、組Amn按“行優先順序”存儲在內存中，假設每個元素占用d個存儲單元。 元素aij的存儲地址應是數組的基地址加上排在aij前面的元素所占用的單元數。因為aij位于i行、j列，前面i行一共有in個元素，i行上aij前面又有j個元素，故它前面一共有in+j個元素，因此，aij的地址計算函數為： LOC(aLOC(aijij)=LOC(a)=LOC(a0000)+(i)+(i* *n+j)n+j)* *d d若下標的下界是1，二維數組的行優先地址計算公式為： LOC(aijij)=LOC(a1111)+(i-1)*n+j-1)*d7 5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲 在科學與工程計算問題中

5、，矩陣矩陣是一種常用的數學對象，在高級語言編制程序時，將一個矩陣描述為一個二維數組二維數組。矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為1。但是在矩陣中非零元素呈某種規律分布或者矩陣中出現大量零元素呈某種規律分布或者矩陣中出現大量的零元素的零元素的情況下，許多單元去存儲重復的非零元素或零元素，這對高階矩陣會造成極大的浪費，為了節省存儲空間， 我們可以對這類矩陣進行壓縮存儲壓縮存儲：即為多個相同的非零元素只分配一個為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。存儲空間；對零元素不分配空間。85.3.15.3.1特殊矩陣特殊矩陣特殊矩陣特

6、殊矩陣: :指非零元素或零元素的分布有一定規律的矩陣。1、對稱矩陣對稱矩陣 在一個n階方陣A中，若元素滿足下述性質： aij=aji 1i,j n則稱A為對稱矩陣。如圖5.1便是一個5階對稱矩陣。 對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節約近一半的存儲空間。9按“行優先行優先順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示： 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an 1 a n 2 a

7、 n 3 a n n 圖 5.1 對稱矩陣 在這個下三角矩陣中，元素總數為： 1+2+.+n=n(n+1)/2 因此，我們可以將這些元素存放在一個向量sa0.n(n+1)/2-1中。10為了便于訪問對稱矩陣A中的元素，我們必須在aijij和sak之間找一個對應關系。 若ij，則aij在下三角形中。 aij之前的i-1行（從第1行到第i-1行）一共有1+2+i-1=i(i-1)/2個元素，在第i行上， aij之前恰有j-1個元素（即ai1,ai2,ai3,aij-1），因此有： k=ik=i* *(i-1)/2+j-1 0(i-1)/2+j-1 0kn(n+1)/2kn(n+1)/2 若ij，則

8、aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應關系式中的i和j即可得到： k=jk=j* *(j-1)/2+i-1 0(j-1)/2+i-1 0kn(n+1)/2kn(n+1)/2 11稱san(n+1)/2為n階對稱矩陣A的壓縮存儲，見下圖：k=0 1 2 3 n(n-1)/2 n(n+1)/2-1例如a32和a23均存儲在 sa4中 a11a21a22a31an 1 an n122、三角矩陣、三角矩陣 以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數。下三角矩陣正好相反，它的主對角線上方均為常數，如圖所示。在大

9、多數情況下，三角矩陣常數為零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩陣 (b)下三角矩陣 圖5.2 三角矩陣13 三角矩陣中的重復元素重復元素c c可共享一個存儲空間可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa0.n(n+1)/2中，其中c存放在向量的最后一個分量中，其存儲方法同對稱矩陣。 143 3、對角矩陣、對角矩陣 對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區域中，即除了主對角

10、線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣， a00 a01 a10 a11 a12 a21 a22 a23 . . . an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1圖5.3 對角矩陣對角矩陣可按行優先順序或對角線的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應關系。 155.3.2 5.3.2 稀疏矩陣稀疏矩陣u什么是稀疏矩陣？簡單說，設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數（即smn），則稱A為稀疏矩陣稀疏矩陣。u精確點，設在矩陣A中，有s個非零元素。令 e=s/

11、(m*n)，稱e為矩陣的稀疏因子。通常認為e0.05時稱之為稀疏矩陣。16在存儲稀疏矩陣時，為了節省存儲單元，很自然地想到使用壓縮存儲方法。但由于非零元素的分布分布一般是沒有規律沒有規律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。反之，一個三元組三元組(i,j,a(i,j,aijij) )唯一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數唯一確定。17例如，下列三元組表(1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7) 加上(6,7)這一對行、列

12、值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 圖5.4 稀疏矩陣M和TM=T=1 2 3 4 5 6 71234561 2 3 4 5 6123456718一、三元組順序表 假設以順序存

13、儲結構來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法三元組順序表。 #define MAXSIZE 10000 typedef struct int i,j; ElemType v; Triple; typedef struct Triple dataMAXSIZE; int m,n,t; TSMatrix;19設A為TSMatrix型的結構變量，圖5.4中所示的稀疏矩陣的三元組的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 20 下面以矩陣矩陣的轉置轉置為例，說明在這種壓縮存儲結構上如何實現矩陣的運算

14、。 一個mn的矩陣A，它的轉置B是一個nm的矩陣，且aij=bji，1im，1jn，即A的行是B的列，A的列是B的行。 由于A的列是B的行，因此，按a.data的列序轉置，所得到的轉置矩陣B的三元組表b.data必定是按行優先存放的。 兩種處理方法。21方法：基本思想：對A中的每一列col(1coln)，通過從頭至尾掃描三元組表a.data，找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放入b.data中，即可得到B的按行優先的壓縮存儲表示。 22Status transmatrix(TSMatrixTSMatrix a, TSMatrixTSMatrix &b) i

15、nt p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) return ERROR; q=1; 23 for(col=1;col=a.n;col+) for(p=1;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; return OK; 分析算法:主要的工作是在p和col的兩個循環中完成的，故算法的時間復雜度為O(n*t).此算法僅適用于t=m*n的情況。24方法：快速轉置快速轉置算法u算法思想為：按照a.data中

16、三元組的次序進行轉置，并將轉置后的三元組置入b中恰當的位置。如果能事先確定矩陣A中每一列（即B中每一行）的第一個非零元在b.data中應有的位置，那么在對a.data中的三元組依次作轉置時，便可直接放到b.data中恰當的位置上去。u關鍵：如何確定M中每一列的第一個非零元在b.data中應有的位置？25方法： 設置兩個一維數組num和cpot numcol-M中第col列非零元素的個數，cpotcol-M中第col列的第一個非零元在 b.data中的恰當位置。顯然有： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=col=a.n26 例如：圖5.4中的矩陣M和相應的

17、三元組A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 927快速轉置算法如下： Status fasttranstri(TSMatrixTSMatrix &b, TSMatrixTSMatrix a) int p,q,col,k; int numa.n,copta.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) return ERROR; for(col=1;col=a.n;+col) numcol=0; for(k=1;k=a.t;

18、+k)/得到M中每一列的非零元素個數 +numa.datak.j;28 cpot1=1; for(col=2;col=a.n;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=a.t;+p) col=a.datap.j; /col為該元素的列 q=cpotcol;/q為該元素在b.data中的位置 b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; 29二、帶行表的三元組 有時為了方便某些矩陣運算，我們在按行優先存儲的三元組中，加入加入一個行表行表來記錄記錄稀疏矩

19、陣中每行的非零元素在三元組表中的起始位置每行的非零元素在三元組表中的起始位置。其類型描述如下： typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; int n,m,t; RLSMatrix; 30 兩個矩陣相乘的經典算法:若設 Q=M*N 其中，M是m1*n1矩陣，N是m2*n2矩陣。 當n1=m2時有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0 for(k=1;k=0)個元素a1,a2,a3,an的有限序列，其中ai或者是原子項原子項，或者是一個廣義表廣義表。通常記作LS=（a1,a2,a3,an)

20、。LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS的子表。習慣上用大寫字母表示廣義表的名稱，用小寫字母表示原子。36當廣義表非空時，稱第一個元素a1為LS的表頭表頭（表頭可能是原子，也可能是列表），其余元素組成的表表（a2,a3,an）是LS的表尾表尾（表尾一定是列表）。 舉例：A=()-A是一個空表，其長度為0；B=(e)-B只有一個原子，其長度為1，表頭為e,表尾為空表（）；C=(a,(b,c,d)-長度為2D=(A,B,C)-其長度為3E=(a,E)-遞歸表，長度為2。思考思考：廣義表的表頭和表尾分別是什么？深度深度：廣義表中括號嵌套的最大層數。373 3個重要結論：個重要結論：u列表的元素可以是子表，而子表的元素還可以是子表，由此列表是一個多層次結構，可用圖形象的表示。用圖示表示列表D.A=() B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)u列表可為其它列表所共享。如D。u列表可以是一個遞歸的表。如E。注意（）和（）的區別。DABCeabcdC38 5.5. 廣義表的存儲結構廣義表的存儲結構廣義表中的元素可能是原子也可能是列表，因此難以用順序存儲結構，通常采用鏈式存儲