多維數(shù)組和廣義表第1頁(yè)，共28頁(yè)，2023年，2月20日，星期一二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在兩個(gè)前驅(qū)和兩個(gè)后繼。也可看作是以線性表為數(shù)據(jù)元素的線性表。n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n個(gè)下標(biāo)，受n個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系?？煽醋魇菙?shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組是對(duì)線性表的擴(kuò)展：線性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。5.1多維數(shù)組第2頁(yè)，共28頁(yè)，2023年，2月20日，星期一多維數(shù)組用一維的存儲(chǔ)單元存放，需約定次序。C語(yǔ)言是行優(yōu)先順序。二維數(shù)組中任一元素aij的存儲(chǔ)地址:n維數(shù)組Loc(aij)=Loc(a00)+(n*i+j)*d第3頁(yè)，共28頁(yè)，2023年，2月20日，星期一5.2矩陣的壓縮存儲(chǔ)

壓縮存儲(chǔ)使用一維數(shù)組存儲(chǔ)矩陣，并且在一維數(shù)組中為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元不分配空間。第4頁(yè)，共28頁(yè)，2023年，2月20日，星期一5.2.1特殊矩陣對(duì)稱矩陣：aij=aji0≤i,j≤n-1壓縮存儲(chǔ)方法：為每一對(duì)對(duì)稱元分配一個(gè)存儲(chǔ)空間將下三角的元素，按行存儲(chǔ)到一維數(shù)組sa中,共有n(n+1)/2個(gè)存儲(chǔ)單元，aij在一維數(shù)組中的位置k為：

i(i＋1)/2+j當(dāng)i>=j；

j(j＋1)/2+i否則第5頁(yè)，共28頁(yè)，2023年，2月20日，星期一特殊矩陣三角矩陣：上（下）三角中的元素均為常數(shù)c或0壓縮存儲(chǔ)方法：只存儲(chǔ)上（下）三角元素。下三角：k=i*(i＋1)/2+j(i>=j);k=n*(n+1)/2(i<j)上三角：k=(i/2)*(2n-i+1)+j-i(i<=j);k=n*(n+1)/2(i>j)注意：k,i,j從零開始第6頁(yè)，共28頁(yè)，2023年，2月20日，星期一特殊矩陣對(duì)角矩陣：所有非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中壓縮方法：壓縮存儲(chǔ)到一維數(shù)組sa[]中，三對(duì)角矩陣有3n-2個(gè)元素。

第7頁(yè)，共28頁(yè)，2023年，2月20日，星期一5.2.2稀疏矩陣

已知矩陣Am×n，t為非零元個(gè)數(shù)，若t<<(m×n)，則稱Am×n為稀疏矩陣。 用三元組(i,j,v)存儲(chǔ)行和列的位置及非零元值。第8頁(yè)，共28頁(yè)，2023年，2月20日，星期一1.三元組表順序存儲(chǔ)方式存儲(chǔ)稀疏矩陣的三元組.第9頁(yè)，共28頁(yè)，2023年，2月20日，星期一

三元組表結(jié)構(gòu)定義#definesmax16//非零元個(gè)數(shù)最大值Typedefintdatatypetypedefstruct{inti，j;//行下標(biāo)和列下標(biāo)

datatypev;}node;typedefstruct{nodedata[smax];//非零元三元組表

intm,n,t;//行數(shù)、列數(shù)、非零元個(gè)數(shù)

}SpMatrix;SPMatrix*a,*b;第10頁(yè)，共28頁(yè)，2023年，2月20日，星期一三元組表稀疏矩陣的轉(zhuǎn)置運(yùn)算第11頁(yè)，共28頁(yè)，2023年，2月20日，星期一稀疏矩陣的轉(zhuǎn)置

Spmatrix*transmat(a)Spmatrix*a;{intano,bno,col;Spmatrix*b;b=malloc(sizeof(Spmatrix));b->m=a->n;b->n=a->m;b->t=a->t;if(b->t>0){bno=0;for(col=0;col<a->n;col++)for(ano=0;ano<a->t;ano++)if(a->data[ano].j==col){b->data[bno].i=a->data[ano].j;b->data[bno].j=a->data[ano].i;b->data[bno].v=a->data[ano].v;bno++;}}returnb;}第12頁(yè)，共28頁(yè)，2023年，2月20日，星期一2.十字鏈表當(dāng)矩陣中非零元素的個(gè)數(shù)和位置經(jīng)過運(yùn)算后變化較大時(shí)，就不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示三元組。行鏈表與列鏈表都是帶表頭結(jié)點(diǎn)的循環(huán)鏈表。第13頁(yè)，共28頁(yè)，2023年，2月20日，星期一元素結(jié)點(diǎn)rptr——指向同一行中下一個(gè)非零元素的指針（向右域）cptr——指向同一列中下一個(gè)非零元素的指針（向下域）ijVcptrrptr00nextrptr00nextcptr表頭結(jié)點(diǎn)行表頭結(jié)點(diǎn)列表頭結(jié)點(diǎn)next用于表示頭結(jié)點(diǎn)的鏈接第14頁(yè)，共28頁(yè)，2023年，2月20日，星期一1396457稀疏矩陣的十字鏈表表示的示例第15頁(yè)，共28頁(yè)，2023年，2月20日，星期一十字鏈表結(jié)構(gòu)定義：typedefstructlnode{inti,j;//非零元的行下標(biāo)和列下標(biāo)

structlnode*cptr,*rptr;union{structlnode*next;datatypev;}uval;} Link;Link*l；ijVcptrrptr第16頁(yè)，共28頁(yè)，2023年，2月20日，星期一需要輔助結(jié)點(diǎn)作鏈表的表頭，同時(shí)每個(gè)結(jié)點(diǎn)要增加兩個(gè)指針域，所以只有在矩陣較大和較稀疏時(shí)才能起到節(jié)省空間的效果。分別用兩個(gè)一維數(shù)組存儲(chǔ)行鏈表的頭指針和列鏈表的頭指針，可加快訪問速度。第17頁(yè)，共28頁(yè)，2023年，2月20日，星期一

5.3廣義表

5.3.1廣義表的概念

5.3.2廣義表的存儲(chǔ)結(jié)構(gòu)第18頁(yè)，共28頁(yè)，2023年，2月20日，星期一

什么是廣義表廣義表也稱為列表，是線性表的一種擴(kuò)展，也是數(shù)據(jù)元素的有限序列。記作：LS=(α1,α2,…，αn)。其中αi可以是單個(gè)元素，也可以是廣義表。5.3.1廣義表的概念

說明

1）在廣義表中，元素可以是單個(gè)元素，稱為原子；也可以是廣義表，稱為廣義表的子表；

3）廣義表的定義是一個(gè)遞歸定義，因?yàn)樵诿枋鰪V義表時(shí)又用到了廣義表；2）n是廣義表長(zhǎng)度；第19頁(yè)，共28頁(yè)，2023年，2月20日，星期一A=()6）對(duì)非空廣義表L,稱第一個(gè)元素為L(zhǎng)的表頭，其余元素組成的廣義表稱為L(zhǎng)的表尾；

B=(e)

C=(a,(b,c,d))

D=(A,B,C)

E=(a,E)例：B=(e)

C=(a,(b,c,d))D=(A,B,C)表頭：e；表尾()表頭：a；表尾((b,c,d))表頭：A；表尾(B,C)空表，表長(zhǎng)為0；4）下面是一些廣義表的例子；B中只有一個(gè)元素e，表長(zhǎng)為1；兩個(gè)元素分別為a和子表（b,c,d)；表長(zhǎng)為2。它的三個(gè)元素A，B，C廣義表；表長(zhǎng)為3。E的表長(zhǎng)為25）廣義表的深度：表展開后所含括號(hào)的層數(shù)。設(shè)一個(gè)原子的深度是0。深度＝max｛各元素的深度｝＋1第20頁(yè)，共28頁(yè)，2023年，2月20日，星期一廣義表的圖形表示LabL=（a，b）AxLA=（x，L）abAxLabyBB=（A，y）AxLayBCbC=（A，B）aDD=（a，D）第21頁(yè)，共28頁(yè)，2023年，2月20日，星期一廣義表的基本運(yùn)算

1）取廣義表L的表頭；head（）

2）取廣義表L的表尾；tail（）

例如：head(L)=a,tail(L)=(b),head(tail(L))=b,tail(tail(L))=()head(B)=A,tail(B)=(y)第22頁(yè)，共28頁(yè)，2023年，2月20日，星期一5.3.2廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表中的數(shù)據(jù)元素可以具有不同的類型，（或是原子，或是廣義表）因此難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，書上介紹了兩種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，一種是單鏈表示法，另一種是雙鏈表示法。

第23頁(yè)，共28頁(yè)，2023年，2月20日，星期一單鏈表示法

atomData/slinklinkatom=本結(jié)點(diǎn)為子表本結(jié)點(diǎn)為原子第24頁(yè)，共28頁(yè)，2023年，2月20日，星期一示例A=NuLL

A=()B1∧e

B=(e)C=(a,(b,c,d))C1a∧111bcd∧0第25頁(yè)，共28頁(yè)，2023年，2月20日，星期一1E0∧aE＝（a,E）D=(B,C)0D0∧B1∧eC1a∧111bcd∧0第26頁(yè)，共28頁(yè)，2023年，2月20日，星期一雙鏈表示法

Link1Datalink2C∧a∧∧∧∧bcd∧C=(a,(b,c,d))指向該結(jié)點(diǎn)的子表指向該結(jié)點(diǎn)的后繼第27頁(yè)，共28頁(yè)，2