c描述數(shù)組和廣義表

1、第五章數(shù)組和廣義表數(shù)組和廣義表數(shù)組和廣義表可以看成是一種擴(kuò)展的線性數(shù)據(jù)結(jié)構(gòu)，其特殊性不是操作受限，也不是數(shù)據(jù)元素類(lèi)型受限，而是反映在數(shù)據(jù)元素的構(gòu)成上。數(shù)組和廣義表中的數(shù)據(jù)元素可以推廣到是一種具有特定結(jié)構(gòu)的數(shù)據(jù)，即線性表中的數(shù)據(jù)元素本身也是一個(gè)線性表。5.1 數(shù)組的定義和運(yùn)算5.2 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn)5.3 矩陣的壓縮存儲(chǔ)5.4 廣義表5.5 本章小結(jié)5.6 課后練習(xí)第5章 數(shù)組和廣義表（1） 數(shù)組的結(jié)構(gòu)特征（2） 數(shù)組的操作（3） 數(shù)組的抽象數(shù)據(jù)類(lèi)型定義（4） 小結(jié)5.1 數(shù)組的定義和運(yùn)算數(shù)組的結(jié)構(gòu)特征數(shù)組是一種數(shù)據(jù)類(lèi)型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看成是一般線性表的擴(kuò)充。二維數(shù)組可以看成是線性

2、表的線性表。例如：Amn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amn二維數(shù)組該二維數(shù)組可以看成是一個(gè)線性表AA=(1 2 j n)，其中j （1jn）本身也是一個(gè)線性表，稱(chēng)為列向量，j =(a1j,a2j,amj)矩陣Amn可以看成是由n個(gè)列向量組成的線性表Amn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amnA=（ 1 2 j n)二維數(shù)組該二維數(shù)組還可以看成是另一個(gè)線性表BB=(1 2 m)，其中i（1im）本身也是一個(gè)線性表，稱(chēng)為

3、行向量， i=（ai1,ai2,ain）矩陣Amn可以看成是由m個(gè)行向量組成的線性表Amn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amnB12im數(shù)組可以看出，數(shù)組是線性表的推廣。二維數(shù)組可以看成是每個(gè)元素都是一個(gè)一維數(shù)組的線性表，三維數(shù)組數(shù)組中的每一個(gè)元素由一個(gè)值和一組下標(biāo)來(lái)描述，值代表元素的數(shù)據(jù)信息，下標(biāo)描述該元素在數(shù)組中的相對(duì)位置。數(shù)組的操作 數(shù)組是一組有固定個(gè)數(shù)的元素的集合。由于這個(gè)性質(zhì)，使得對(duì)數(shù)組的操作不象對(duì)線性表的操作那樣，可以在表中任意一個(gè)合法的位置插入或刪除一個(gè)元素。對(duì)于數(shù)組的操作一般只有兩類(lèi)：（1

4、）獲得特定位置的元素值；（2）修改特定位置的元素值。數(shù)組的抽象數(shù)據(jù)類(lèi)型定義ADT Array 數(shù)據(jù)對(duì)象： Daj1,j2, .,ji,jn|ji=1,.,bi,i=1,2, .n 數(shù)據(jù)關(guān)系： RR1, R2, ., Rn Ri|1jkbk,1k n 且k i, 1jibi-1, i=1,.,n 基本操作： ADT Array ji第i維的下標(biāo)bi第i維的長(zhǎng)度基本操作（1）InitArray(A,n,bound1,boundn)：若維數(shù)n和各維的長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回TRUE； （2）DestroyArray（A）：銷(xiāo)毀數(shù)組A； （3）GetValue（A，e, index1, ,

5、indexn）： 若下標(biāo)合法，用e返回?cái)?shù)組A中由index1, ,indexn所指定的元素的值。 基本操作（4）SetValue（A，e，index1, ,indexn）： 若下標(biāo)合法，則將數(shù)組A中由index1, ,indexn所指定的元素的值置為e。 注意：這里定義的數(shù)組下標(biāo)是從1開(kāi)始，C語(yǔ)言數(shù)組的下標(biāo)是從0開(kāi)始，略有不同。小結(jié)數(shù)組特點(diǎn)(1)數(shù)組結(jié)構(gòu)固定，一旦定義其維數(shù)和維界不再改變(2)數(shù)據(jù)元素同構(gòu)數(shù)組運(yùn)算(1)給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素(2)給定一組下標(biāo)，修改數(shù)據(jù)元素的值小結(jié)關(guān)系每個(gè)數(shù)據(jù)元素都受著n個(gè)關(guān)系的約束，如二維數(shù)組中，元素aij既是第i行又是第j列的元素。( )( )(

6、)( )( )( )( )( )( )（1） 采用順序存儲(chǔ)結(jié)構(gòu)的原因（2） 數(shù)組的存儲(chǔ)方式（3） 數(shù)組元素存儲(chǔ)地址的計(jì)算5.2 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn)采用順序存儲(chǔ)結(jié)構(gòu)的原因數(shù)組一般不作插入或刪除操作。一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素之間的關(guān)系不再發(fā)生變動(dòng)。所以，采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示數(shù)組比較合適。數(shù)組的存儲(chǔ)方式數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一維的結(jié)構(gòu)。所以，用一組連續(xù)的存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素有次序的約定。如，二維數(shù)組有兩種存儲(chǔ)方式:以行序?yàn)橹餍?低下標(biāo)優(yōu)先) C PASCAL以列序?yàn)橹餍?高下標(biāo)優(yōu)先) FORTRAN數(shù)組元素存儲(chǔ)地址的計(jì)算假設(shè)有一二維數(shù)組以行序?yàn)橹餍?的方式存儲(chǔ) 稱(chēng)為基地址或

7、基址二維數(shù)組Amxn中任一元素ai,j 的存儲(chǔ)位置 LOC(i,j) = LOC(1,1) + (n（i-1）（j-1）)La12a11a13a21a22a23a12a11a13a21a22a23L數(shù)組元素存儲(chǔ)地址的計(jì)算 假定每個(gè)元素占一個(gè)存儲(chǔ)單元，三維數(shù)組Armn采用以行為主序的方式存存儲(chǔ)，則：首元素a111的地址為L(zhǎng)oc1,1,1ai11的地址為:Loci,1,1=Loc1,1,1+(i-1)*m*n那么求任意元素aijk的地址計(jì)算公式為：Loci,j,k=Loc1,1,1+(i-1)*m*n+(j-1)*n+(k-1)其中1i，1j，1k。數(shù)組元素存儲(chǔ)地址的計(jì)算如果將三維數(shù)組推廣到一般情

8、況：用j1,j2,j3代替數(shù)組下標(biāo)i,j,kj1,j2,j3的下限分別為c1,c2,c3j1,j2,j3的上限分別為d1,d2,d3每個(gè)元素占L個(gè)存儲(chǔ)單元數(shù)組元素存儲(chǔ)地址的計(jì)算則三維數(shù)組中任意元素a(j1,j2,j3)的地址為：Locj1,j2,j3=Locc1,c2,c3 + (d2-c2+1)*(d3-c3+1)*(j1-c1)*L + (d3-c3+1)*(j2-c2) *L + (j3-c3)*L其中L為每個(gè)元素所占存儲(chǔ)單元數(shù)數(shù)組元素存儲(chǔ)地址的計(jì)算令1=L*(d2-c2+1)*(d3-c3+1)2=L*(d3-c3+1)3=L，則:Locj1,j2,j3=Locc1,c2,c3+1*(

9、j1-c1)+2*(j2-c2)+3(j3-c3)=Locc1,c2,c3+ i*(ji-ci)（1i3）由公式可知Locj1,j2,j3與j1,j2,j3呈線性關(guān)系數(shù)組元素存儲(chǔ)地址的計(jì)算對(duì)于維數(shù)組A(c1:d1,c2:d2，,cn:dn)，我們只要把上式推廣，就可以容易地得到維數(shù)組中任意元素aj1j2jn的存儲(chǔ)地址的計(jì)算公式: 思考題已知三維數(shù)組M23,-42,-14,且每個(gè)元素占用2個(gè)存儲(chǔ)單元，起始地址為100，以行序?yàn)橹餍蝽樞虼鎯?chǔ)，求：（1）M含有的數(shù)據(jù)元素?cái)?shù)目；（2）元素M3，-3，3和M3，0，0的存儲(chǔ)地址是多少？思考題數(shù)組A0.5,0.6的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在

10、起始地址為1000的內(nèi)存單元中，則元素A4,5的地址是_。1000+(5-0)*6+(4-0)*5數(shù)組元素存儲(chǔ)地址的計(jì)算在高級(jí)語(yǔ)言的應(yīng)用層上，一般不會(huì)涉及到地址Locj1,j2,jn的計(jì)算，該任務(wù)是由高級(jí)語(yǔ)言的編譯系統(tǒng)完成的。在使用時(shí)，只需給出數(shù)組元素的下標(biāo)。由Locj1,j2,jn的計(jì)算公式可以看出，數(shù)組的維數(shù)越高，數(shù)組元素存儲(chǔ)地址的計(jì)算量越大，計(jì)算花費(fèi)的時(shí)間越多。因此在定義和使用數(shù)組時(shí)，維數(shù)應(yīng)根據(jù)具體情況來(lái)確定，不宜過(guò)大。（1） 壓縮存儲(chǔ)問(wèn)題引入（2） 特殊矩陣的壓縮存儲(chǔ)（3） 稀疏矩陣的壓縮存儲(chǔ)及運(yùn)算5.3 矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ)問(wèn)題引入矩陣是科學(xué)計(jì)算、工程數(shù)學(xué)，尤其是數(shù)值分析經(jīng)常研究的

11、對(duì)象。在高級(jí)編程語(yǔ)言中，常采用二維數(shù)組的形式來(lái)描述。如何存儲(chǔ)矩陣的元素使矩陣的運(yùn)算能有效進(jìn)行？問(wèn)題：有許多值相同的元素或零值元素的高階矩陣，為了節(jié)省存儲(chǔ)空間應(yīng)進(jìn)行壓縮存儲(chǔ)。壓縮存儲(chǔ)問(wèn)題引入壓縮存儲(chǔ)：為多個(gè)值相同的元素分配一個(gè)存儲(chǔ)空間對(duì)零值元素不分配存儲(chǔ)空間特殊矩陣：若值相同的元素或零值元素在矩陣中的分布有一定規(guī)律，稱(chēng)為特殊矩陣。稀疏矩陣：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣稱(chēng)為稀疏矩陣。特殊矩陣的壓縮存儲(chǔ)（1） n階對(duì)稱(chēng)矩陣（2） 三角矩陣（3） 帶狀矩陣n階對(duì)稱(chēng)矩陣 a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . n階對(duì)稱(chēng)矩陣 a11 a1

12、2 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍簩2個(gè)元素壓縮到n(n+1)/2個(gè)空間中三角矩陣 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0三角矩陣 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍?/p>

13、：Loci,j=Loc1,1+ +(j-1)i(i-1)2思考題設(shè)有上三角矩陣Ann，下三角部分全為0，將其上三角元素按行優(yōu)先存儲(chǔ)方式存入數(shù)組Bm中(m足夠大)，使得Bk=aij，且有k=f1(i)+f2(j)+c。試推出函數(shù)f1、f2及常數(shù)c（要求f1和f2中不含常數(shù)項(xiàng)）。思考題分析K=n+(n-1)+(n-2)+(n-(i-1)+1)+(j-i) =(i-1)*(2n-i+2)/2+(j-i) =(2n+1)i-i2)/2+j-n-1f1(i)=(2n+1)i-i2)/2f2(j)=jC=-n-1帶狀矩陣 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2

14、 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34 0 0 帶狀矩陣 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34 0 0 a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 3n-4 3n-3按行序?yàn)橹餍颍篖oci,j= Loc1,1 + 2 + 3*(i-2) + (j-i+1) = Loc1,1 + 2*(i-1) + (j-1)稀疏矩陣的壓縮存儲(chǔ)（1）稀疏矩陣的定義（2）壓縮存儲(chǔ)原

15、則（3）分析稀疏矩陣的組成（4）稀疏矩陣的壓縮存儲(chǔ) （a）三元組順序表存儲(chǔ)結(jié)構(gòu) （b）十字鏈表存儲(chǔ)結(jié)構(gòu)稀疏矩陣的定義定義：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣。假設(shè) m 行 n 列的矩陣含 t 個(gè)非零元素，則稱(chēng)為稀疏因子，通常認(rèn)為0.25的矩陣為稀疏矩陣。稀疏矩陣壓縮存儲(chǔ)的原則 只存儲(chǔ)矩陣的:行列維數(shù)每個(gè)非零元的行列下標(biāo)及其值例如，稀疏矩陣M如下：稀疏矩陣組成分析7個(gè)非零元： (1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15) 矩陣維數(shù)：6x7M由非零元組和矩陣維數(shù)唯一確定一個(gè)三元組(i,j,aij)唯一確

16、定了矩陣的一個(gè)非零元三元組順序表（1）三元組順序表類(lèi)型描述（2）矩陣的轉(zhuǎn)置運(yùn)算（3）快速轉(zhuǎn)置算法（4）三元組順序表存儲(chǔ)結(jié)構(gòu)小結(jié)三元組順序表類(lèi)型描述#define MaxSize 20typedef struct int row,col; ElemType e;Triple;typedef struct Triple dataMaxSize+1; int m,n,len;TSMatrix;data0未用1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 row col e0 1 2 3 4 5 6 7 8行列下標(biāo)非零元值data中的三元組

17、是以行序?yàn)橹餍蝽樞蚺帕械娜M順序表存儲(chǔ)結(jié)構(gòu)矩陣的轉(zhuǎn)置運(yùn)算一般矩陣轉(zhuǎn)置算法 for(i=0;in;i+) for(j=0;jm=M.n; N-n=M.m; N-len=M.len; if(N-len) q=1; for(col=1;col=M.n;+col) for(p=1;pdataq.row=M.datap.col; N-dataq.col=M.datap.row; N-dataq.e=M.datap.e; +q; return OK;簡(jiǎn)單轉(zhuǎn)置算法分析算法的時(shí)間復(fù)雜度：T(n)=O(M.nM.len) 若len與M.mM.n同數(shù)量級(jí) 則T(n)=O(M.mM.n2)所以，該算法僅適用于le

18、nm=M.n; N-n=M.m; N-len=M.len; if(N-len) for(col=1;col=M.n;+col) numcol=0; for(t=1;t=M.len;+t) +numM.datat.col; pos1=1; for(col=2;colm=M.n; N-n=M.m; N-len=M.len; if(N-len) /num,pos for(p=1; pdataq.row=M.datap.col; N-dataq.col=; N-dataq.e=; +positioncol; return OK;定位快速轉(zhuǎn)置算法分析算法的時(shí)間復(fù)雜度：T(n)=O(M.n+M.len)

19、若len與M.mM.n同數(shù)量級(jí) 則T(n)=O(M.mM.n) 和非壓縮矩陣的轉(zhuǎn)置算法時(shí)間復(fù)雜度相同課外閱讀：基于三元組順序表的矩陣相乘算法P106-P107練習(xí)題給定一個(gè)稀疏矩陣如下,用快速轉(zhuǎn)置實(shí)現(xiàn)該稀疏矩陣的轉(zhuǎn)置，寫(xiě)出轉(zhuǎn)置前后的三元組表及開(kāi)始的每一列第一個(gè)非零元的位置poscol的值。三元組順序表存儲(chǔ)結(jié)構(gòu)小結(jié)三元組順序表又稱(chēng)有序的雙下標(biāo)法特點(diǎn)：非零元在表中按行序有序存儲(chǔ)優(yōu)點(diǎn)：便于整體依行序順序處理的矩陣運(yùn)算缺點(diǎn)：若按行號(hào)存取某一行的非零元(單行，單個(gè)處理)，則需從頭開(kāi)始進(jìn)行查找；適用場(chǎng)合：當(dāng)矩陣的非零元的個(gè)數(shù)和位置在操作中變化不大時(shí)，適合采用。十字鏈表當(dāng)矩陣中非零元的個(gè)數(shù)和位置在操作中變化

20、較大，不宜采用順序存儲(chǔ)結(jié)構(gòu)應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示三元組構(gòu)成的線性表鏈表中結(jié)點(diǎn)的類(lèi)型每個(gè)非零元可用一個(gè)含五個(gè)域的結(jié)點(diǎn)表示類(lèi)型描述：typedef struct OLNode int row, col ; ElemType e ； struct OLNode * right; /同行下一個(gè)非零元的位置 struct OLNode * down; /同列下一個(gè)非零元的位置OLNode, * OLink;稀疏矩陣的十字鏈表存儲(chǔ)結(jié)構(gòu)類(lèi)型描述：typedef struct OLNode OLink * rhead; /行鏈表頭指針向量基址 OLink * chead; /列鏈表頭指針向量基址 int m,

21、n,len; CrossList;十字鏈表存儲(chǔ)結(jié)構(gòu)示意圖row col edownright113418225234A.cheadA.rhead練習(xí)題畫(huà)出如下所示的稀疏矩陣A的三元組表A.data和十字鏈表。十字鏈表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)每個(gè)非零元既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)。整個(gè)矩陣構(gòu)成了一個(gè)十字交叉的鏈表，故稱(chēng)此存儲(chǔ)結(jié)構(gòu)為十字鏈表。相關(guān)運(yùn)算的實(shí)現(xiàn)類(lèi)似于單鏈表的處理。（1） 廣義表的概念（2） 抽象數(shù)據(jù)類(lèi)型廣義表的定義（3） 廣義表與線性表的區(qū)別（4） 廣義表的結(jié)構(gòu)特點(diǎn)（5） 廣義表的存儲(chǔ)結(jié)構(gòu)5.4 廣義表廣義表的概念廣義表：是線性表的推廣，又稱(chēng)列表Lists，廣泛地用于人

22、工智能領(lǐng)域的表處理語(yǔ)言LISP。廣義表也是n個(gè)數(shù)據(jù)元素（d1，d2，d3，dn）的有限序列，但不同的是，廣義表中的di既可以是單個(gè)元素，還可以是一個(gè)廣義表。廣義表的概念廣義表通常記作：GL=（d1，d2，dn）。 GL是廣義表的名字，通常用大寫(xiě)字母表示。 n是廣義表的長(zhǎng)度。若di是一個(gè)廣義表，則稱(chēng)di是廣義表GL的子表。 在GL中，d1是GL的表頭，其余部分組成的表（d2，d3，dn）稱(chēng)為GL的表尾。抽象數(shù)據(jù)類(lèi)型廣義表的定義ADT Glist 數(shù)據(jù)對(duì)象：D ei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet為某個(gè)數(shù)據(jù)對(duì)象 數(shù)據(jù)關(guān)系： LR| ei-

23、1 , eiD, 2in 基本操作：ADT Glist廣義表與線性表的區(qū)別線性表：ai 僅限于是單個(gè)元素廣義表：ai 可以是單個(gè)元素(原子，用小寫(xiě)字母表示)，也可以是廣義表(子表，用大寫(xiě)字母表示)。廣義表是遞歸定義的線性結(jié)構(gòu)，在描述廣義表時(shí)又用到了廣義表的概念。廣義表與線性表的區(qū)別例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )廣義表的結(jié)構(gòu)特點(diǎn)(1) 廣義表中的數(shù)據(jù)元素有相對(duì)次序;(2) 廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù);(3) 廣義表的深度定義為所含括號(hào)的重?cái)?shù);

24、注意:“原子”的深度為 0 ; “空表”的深度為 1 。例：A = ( ) 長(zhǎng)度為 0 ，深度為 1 廣義表的結(jié)構(gòu)特點(diǎn)F = (d, (e) 長(zhǎng)度為 2 ，深度為 2 D = (a,(b,c), (d, (e) 長(zhǎng)度為 3 ，深度為 3(4) 廣義表可以共享;(5) 廣義表可以是一個(gè)遞歸的表; 如，B = (a, B) = (a, (a, (a, , ) ) )遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。廣義表的結(jié)構(gòu)特點(diǎn)(6) 廣義表是一個(gè)多層次的線性結(jié)構(gòu)，可以用圖形象地表示，一般用表示子表，用表示原子。例如，D=(E, F)，其中：E=(a, (b, c)F=(d, (e)DEFabcde廣義表的結(jié)

25、構(gòu)特點(diǎn)(7) 任何一個(gè)非空廣義表LS=(1,2,n)均可分解為表頭和表尾兩部分：表頭Head(LS)=1表尾Tail(LS)=(2,n)例如:D=(E,F)=(a,(b, c),F)Head(D)=E Tail(D)=(F)Head(E)=a Tail(E)=(b,c)廣義表的結(jié)構(gòu)特點(diǎn)Head( b,c)=(b,c) Tail(b,c)=( )Head(b,c)=b Tail(b,c)=(c)Head(c)=c Tail(c)=( )練習(xí)題給出以下各廣義表運(yùn)算的結(jié)果：(1) Head(a,b),(c,d)(2) Tail(a,b),(c,d)(3) HeadTail(a,b),(c,d) (4