第5章

數(shù)組和廣義表5．1數(shù)組的定義

二維數(shù)組：我們可以把二維數(shù)組看成是這樣一個(gè)定長(zhǎng)線性表：它的每個(gè)數(shù)據(jù)元素也是一個(gè)定長(zhǎng)線性表。例如。圖5．1

數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，數(shù)組只有存取元素和修改元素值的操作。第5章數(shù)組和廣義表二維數(shù)組：數(shù)組一旦被定義，它的維數(shù)和15．2數(shù)組的順序表示和實(shí)現(xiàn)一．采用順序存儲(chǔ)結(jié)構(gòu)：一般不作插入或刪除操作,因此，采用順序存儲(chǔ)結(jié)構(gòu)二．存儲(chǔ)順序：存儲(chǔ)單元是一維的結(jié)構(gòu)，數(shù)組是個(gè)多維的結(jié)構(gòu)，用一組連續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有次序約定問(wèn)題。

對(duì)二維數(shù)組可有兩種存儲(chǔ)方式：1．以列序?yàn)橹餍?co1umnmajororder)的存儲(chǔ)方式，如圖5．2(a)所示2．以行序?yàn)橹餍?rowmajororder)的存儲(chǔ)方式，如圖5．2(b)所示。5．2數(shù)組的順序表示和實(shí)現(xiàn)一．采用順序存儲(chǔ)結(jié)構(gòu)：2數(shù)組和廣義表1數(shù)組的定義課件3三．元素存儲(chǔ)位置計(jì)算：

以行序?yàn)橹餍虻亩S數(shù)組存儲(chǔ)結(jié)構(gòu)為例:二維數(shù)組A中任一元素aij的存儲(chǔ)位置可由下式確定

LOC(i,j)＝LOC(0,0)十(b2×i十j)L(5-1)式中：b2是數(shù)組的第二維長(zhǎng)度，即列數(shù)；L是每個(gè)數(shù)據(jù)元素占的存儲(chǔ)單元個(gè)數(shù)；LOC(i,j)是aij的存儲(chǔ)位置；LOC(0,0)是a00的存儲(chǔ)位置，即二維數(shù)組A的基地址或基址。由于計(jì)算各個(gè)元素存儲(chǔ)位置的時(shí)間相等，所以存取數(shù)組中任一元素的時(shí)間也相等。我們稱(chēng)具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。

三．元素存儲(chǔ)位置計(jì)算：45．3矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ)是指：為多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間；對(duì)零元不分配空間。

5．3．1特殊矩陣：一．對(duì)稱(chēng)矩陣：1．特點(diǎn)：aij=aji1≤i,j≤n2．存儲(chǔ)：可壓縮存儲(chǔ)，不失一般性，以行主序存儲(chǔ)下三角中的元（包括對(duì)角線上的元）。

5．3矩陣的壓縮存儲(chǔ)53．映像關(guān)系：以數(shù)組sa[n(n+1)/2]存儲(chǔ)n階對(duì)稱(chēng)矩陣A，稱(chēng)sa[n(n+1)/2]為n階對(duì)稱(chēng)矩陣A的壓縮存儲(chǔ)。（圖5.3）則sa[k]和矩陣元aij間關(guān)系：3．映像關(guān)系：稱(chēng)sa[n(n+1)/2]為n階對(duì)稱(chēng)矩陣A的壓6二．三角矩陣：1．特點(diǎn)：下(上)三角矩陣指矩陣的上(下)三角(不包括對(duì)角線)中的元均為常數(shù)c或零的n階矩陣。2．存儲(chǔ)：存儲(chǔ)其下(上)三角中的元和常數(shù)c。3．映像關(guān)系：以數(shù)組sa[n(n+1)/2]存儲(chǔ)，sa[0]可用來(lái)存儲(chǔ)常數(shù)c二．三角矩陣：7三．對(duì)角矩陣：1．特點(diǎn)：所有的非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中。如圖5．4所示。2．存儲(chǔ)：亦可按某個(gè)原則(或以行為主，或以對(duì)角線的順序)將其壓縮存儲(chǔ)到一維數(shù)組上。三．對(duì)角矩陣：85．3．2稀疏矩陣：一．什么是稀疏矩陣：二．抽象數(shù)據(jù)類(lèi)型稀疏矩陣的定義：（P96）三．稀疏矩陣壓縮存儲(chǔ)：只存非零元。以圖5.5矩陣為例5．3．2稀疏矩陣：91．三元組順序表：#defineMAXSIZE12500 //稀疏矩陣中非0元素的最大數(shù)目typedefstruct{ inti,j;//非0元素的行號(hào)、列號(hào) ElemTypee;//非0元素的值}Triple;//三元組數(shù)據(jù)類(lèi)型名typedefstruct{ intmu，nu，tu;//稀疏矩陣的行數(shù)、列數(shù)、非0元素的數(shù)目 Tripledata[MAXSIZE+1];//三元組數(shù)組，data[0]未用}TSMatrix;//三元組順序表數(shù)據(jù)類(lèi)型名1．三元組順序表：10矩陣轉(zhuǎn)置運(yùn)算：(1)將矩陣的行列值相互交換；(2)將每個(gè)三元組中的i和j相互調(diào)換；(3)重排三元組之間的次序。實(shí)現(xiàn)第三條有兩種處理方法：按照b.data中三元組的次序依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。

矩陣轉(zhuǎn)置運(yùn)算：11121213931-3361443245218611564-713-3161521122518319342446-763141212112算法5.1:StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//M為原三元組順序表，行優(yōu)先順序 T.mu=M.nu; T.nu=M.mu;T.tu=M.tu;if(!M.tu)returnFALSE;//三元組空q=1;for(col=1;col<=M.nu;col++)for(p=1;k<=M.tu;++p){if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e;q++;}} returnOK; }算法5.1:13這個(gè)算法主要的工作是在p和col的兩重循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(nu×tu)，即和M的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。一般矩陣的轉(zhuǎn)置算法為for(col＝1;col＜=nu;++colfor(row＝1;row＜=mu;++rowT[col][row]＝M[row][col];其時(shí)間復(fù)雜度為O(mu×nu)。當(dāng)非零元的個(gè)數(shù)tu和mu×nu同數(shù)量級(jí)時(shí)，算法5．1的時(shí)間復(fù)雜度就為O(mu×nu2)了(例如，假設(shè)在100×500的矩陣中有tu＝10000個(gè)非零元)，雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度提高了，因此算法5．1僅適于tu<<mu×nu的情況。這個(gè)算法主要的工作是在p和col的兩重循環(huán)中完成的，故算法的14(2)快速轉(zhuǎn)置：需兩個(gè)向量:num和cpotnum[col]表示矩陣M中第col列中非零元的個(gè)數(shù)，cpot[col]指示M中第col列的第一個(gè)非零元在b.data中的恰當(dāng)位置。則有cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1]2≤col≤a.nu例如，對(duì)圖5.5的矩陣M，num和cpot的值如表5.1所示（下頁(yè)圖）(2)快速轉(zhuǎn)置：151234567813-3161521122518319342446-763140000000111122211357889462975381234567813-316算法5.2：StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu; T.nu=M.mu;T.tu=M.tu; if(!M.tu)returnFALSE;//三元組空f(shuō)or(col=1;col<=M.nu;col++)num[col]=0;for(t=1;t<=M.tu;t++)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;col++)cpot[col]=cpot[col-1]+num[col-1]; for(p=1;k<=M.tu;++p){ col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e;++cpot[col]; }//得到的T也是三元組順序表，行優(yōu)先順序 returnOK; }該算法比算法5.1多用了兩個(gè)輔助向量。時(shí)間復(fù)雜度為O(nu+tu)。當(dāng)非零元的個(gè)數(shù)tu和mu×nu同數(shù)量級(jí)時(shí)，算法5.2的時(shí)間復(fù)雜度為O(mu×nu)。三元組順序表又稱(chēng)有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需按行號(hào)存取某一行的非零元，則需從頭開(kāi)始進(jìn)行查找。算法5.2：該算法比算法5.1多用了兩個(gè)輔助向量。時(shí)間復(fù)雜度172．行邏輯鏈接的順序表：為了便于隨機(jī)存取任意一行的非零元，則需知道每一行的第一個(gè)非零元在三元組表中的位置。為此可將上節(jié)快速轉(zhuǎn)置矩陣的算法中創(chuàng)建的指示“行”信息的輔助數(shù)組cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中。稱(chēng)這種“帶行鏈接信息”的三元組表為行邏輯鏈接的順序表，其類(lèi)型描述如下；typedefstruct{intmu，nu，tu;//稀疏矩陣的行數(shù)、列數(shù)、非0元素的數(shù)目Tripledata[MAXSIZE+1];//三元組數(shù)組，data[0]未用intrpos[MAXRC+1];//各行第一個(gè)非零元的位置表}TSMatrix;//三元組順序表數(shù)據(jù)類(lèi)型名2．行邏輯鏈接的順序表：183．十字鏈表：當(dāng)矩陣的非零元個(gè)數(shù)和位置在操作過(guò)程中變化較大時(shí)，就不宜采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組的線性表。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示三元組的線性表更為恰當(dāng)。例如，將矩陣B加到矩陣A上1)表示和實(shí)現(xiàn)：typedefstructOLNode{inti,j;ElemTypee;structOLNode*right,*down;}OLNode;*OLink;typedefstruct{OLink*rhead,*cheak;intmu,nu,tu;}CrossList;3．十字鏈表：19ijerightdown十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)

3005M=0-1002000ije十字鏈表的結(jié)點(diǎn)20算法5.4：創(chuàng)建稀疏矩陣，用十字鏈表存儲(chǔ)表示StatusCreateSMatrix_OL(CrossList&M){if(M)free(M);scanf(&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW);if(!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink))))exit(OVERFLOW);M.rhead[]=M.chead[]=NULL;算法5.4：創(chuàng)建稀疏矩陣，用十字鏈表存儲(chǔ)表示21for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p-->i=i;p-->j=j;p-->e=e;if((M.rhead[i]==NULL||M.rhead[i]-->j>j){p-->right=M.rhead[i];M.rhead[i]=p;}else{for(q=M.rhead[i];(q-->right)&&q-->right-->j<j;q=q-->right);p-->right=q-->right;q-->right=p;}for(scanf(&i,&j,&e);i!=0;scan22if(M.chead[j]==NULL||M.chead[j]-->i>i){p-->down=M.chead[j];M.chead[j]=p;}else{for(q=M.chead[j];(q-->down)&&q-->down-->i<i;q=q-->down);p-->down=q-->down;q-->down=p;}}returnOK;}//CreateSMatrix_OLif(M.chead[j]==NULL||M.chead[j232)將矩陣B加到矩陣A上:十字鏈表表示稀疏矩陣假設(shè)兩個(gè)矩陣相加后的結(jié)果為A'，則和矩陣A'中的非零元“aij'’可能有以下情況：1．a(chǎn)ij'=aij+bij改變結(jié)點(diǎn)的e域值2．a(chǎn)ij'=aij(bij=0)結(jié)點(diǎn)不變3．a(chǎn)ij'=bij(aij=0)增加結(jié)點(diǎn)4．a(chǎn)ij'=0(aij=-bij)刪除結(jié)點(diǎn)2)將矩陣B加到矩陣A上:245.4廣義表的定義廣義表是線性表的推廣。一．抽象數(shù)據(jù)類(lèi)型廣義表定義：(P107)二．術(shù)語(yǔ)：廣義表記作LS=(a1,a2,…,an)LS是廣義表的名稱(chēng)，n是其長(zhǎng)度。ai可以是單個(gè)元素（原子），也可以是廣義表（子表）。習(xí)慣上用大寫(xiě)字母表示廣義表的名稱(chēng)，用小寫(xiě)字母表示原子。廣義表非空時(shí)，稱(chēng)第一個(gè)元素a1為其表頭，稱(chēng)其余元素組成的表（a2,…,an）為其表尾。5.4廣義表的定義25例：(1)A＝()—A是一個(gè)空表，它的長(zhǎng)度為零。(2)B＝(e)—列表B只有一個(gè)原子e，B的長(zhǎng)度為1。(3)C＝(a，(b，c，d))—列表C的長(zhǎng)度為2，兩個(gè)元素分別為原子a和子表(b，c，d)。(4)D＝(A，B，C)—列表D的長(zhǎng)度為3，三個(gè)元素都是列表。顯然，將子表的值代入后，則有D＝(()，(e)，(a，(b，c，d)))。(5)E＝(a，E)—這是一個(gè)遞歸的表，它的長(zhǎng)度為2。E相當(dāng)于一個(gè)無(wú)限的列表E＝(a，(a，(a，…)))。例：26三．三個(gè)重要結(jié)論：(1)列表的元素可以是子表，而子表的元素還可以是子表，…。(2)列表可為其它列表所共享。(3)列表可以是一個(gè)遞歸的表，即列表也可以是其本身的一個(gè)子表。

根據(jù)前述對(duì)表頭、表尾的定義可知：任何一個(gè)非空列表其表頭可能是原子，也可能是列表，而其表尾必定為列表。

三．三個(gè)重要結(jié)論：27A＝()B＝(e)C＝(a，(b，c，d))D＝(A，B，C)E＝(a，E)例如：GetHead(B)=eGetTail(B)＝()GetHead(D)＝AGetTail(D)＝(B，C)由于(B，C)為非空列表，則可繼續(xù)分解得到：GetHead((B,C))＝BGetTail((B,C))＝(C)列表()和(())不同。前者為空表、長(zhǎng)度n＝0；后者長(zhǎng)度n＝1，可分解得到其表頭、表尾均為空表()。A＝()285.5廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，(或是原子，或是列表)，因此難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素可用一個(gè)結(jié)點(diǎn)表示。一.廣義表的頭尾鏈表存儲(chǔ)

1．設(shè)定結(jié)點(diǎn)的結(jié)構(gòu)：由于列表中的數(shù)據(jù)元素可能為原子或列表，由此需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：一種是表結(jié)點(diǎn)，用以表示列表；一種是原子結(jié)點(diǎn)，用以表示原子。5.5廣義表的存儲(chǔ)結(jié)構(gòu)29若列表不空，則可分解成表頭和表尾；反之，一對(duì)確定的表頭和表尾可唯一確定列表。由此，一個(gè)表結(jié)點(diǎn)可由三個(gè)域組成；標(biāo)志域、指示表頭的指針域指示表尾的指針域；而原子結(jié)點(diǎn)只需兩個(gè)域；標(biāo)志域值域(如圖5．8所示)。若列表不空，則可分解成表頭和表尾；302.舉例：A＝()B＝(e)C＝(a，(b，c，d))D＝(A，B，C)E＝(a，E)2.舉例：313．廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：在上述廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu)中有幾種情況：(1)除空表的表頭指針為空外，對(duì)任何非空列表，其表頭指針均指向一個(gè)表結(jié)點(diǎn)，且該結(jié)點(diǎn)中的hp域指示列表表頭(或?yàn)樵咏Y(jié)點(diǎn)，或?yàn)楸斫Y(jié)點(diǎn))，tp域指向列表表尾(除非表尾為空，則指針為空，否則必為表結(jié)點(diǎn))；(2)容易分清列表中原子和子表所在層次。(3)最高層的表結(jié)點(diǎn)個(gè)數(shù)即為列表的長(zhǎng)度。這三個(gè)特點(diǎn)在某種程度上給列表的操作帶來(lái)方便。也可采用另一種結(jié)點(diǎn)結(jié)構(gòu)的鏈表表示列表

3．廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：32二．廣義表的擴(kuò)展線性鏈表存儲(chǔ)：1．形式定義說(shuō)明：typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{ElemTagatom;structGLNode*hp;};structGLNode*tp;}*GList;二．廣義表的擴(kuò)展線性鏈表存儲(chǔ)：332.舉例：A＝()B＝(e)C＝(a，(b，c，d))D＝(A，B，C)E＝(a，E)2.舉例：A＝()B＝(e)34第5章

數(shù)組和廣義表5．1數(shù)組的定義

二維數(shù)組：我們可以把二維數(shù)組看成是這樣一個(gè)定長(zhǎng)線性表：它的每個(gè)數(shù)據(jù)元素也是一個(gè)定長(zhǎng)線性表。例如。圖5．1

數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，數(shù)組只有存取元素和修改元素值的操作。第5章數(shù)組和廣義表二維數(shù)組：數(shù)組一旦被定義，它的維數(shù)和355．2數(shù)組的順序表示和實(shí)現(xiàn)一．采用順序存儲(chǔ)結(jié)構(gòu)：一般不作插入或刪除操作,因此，采用順序存儲(chǔ)結(jié)構(gòu)二．存儲(chǔ)順序：存儲(chǔ)單元是一維的結(jié)構(gòu)，數(shù)組是個(gè)多維的結(jié)構(gòu)，用一組連續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有次序約定問(wèn)題。

對(duì)二維數(shù)組可有兩種存儲(chǔ)方式：1．以列序?yàn)橹餍?co1umnmajororder)的存儲(chǔ)方式，如圖5．2(a)所示2．以行序?yàn)橹餍?rowmajororder)的存儲(chǔ)方式，如圖5．2(b)所示。5．2數(shù)組的順序表示和實(shí)現(xiàn)一．采用順序存儲(chǔ)結(jié)構(gòu)：36數(shù)組和廣義表1數(shù)組的定義課件37三．元素存儲(chǔ)位置計(jì)算：

以行序?yàn)橹餍虻亩S數(shù)組存儲(chǔ)結(jié)構(gòu)為例:二維數(shù)組A中任一元素aij的存儲(chǔ)位置可由下式確定

LOC(i,j)＝LOC(0,0)十(b2×i十j)L(5-1)式中：b2是數(shù)組的第二維長(zhǎng)度，即列數(shù)；L是每個(gè)數(shù)據(jù)元素占的存儲(chǔ)單元個(gè)數(shù)；LOC(i,j)是aij的存儲(chǔ)位置；LOC(0,0)是a00的存儲(chǔ)位置，即二維數(shù)組A的基地址或基址。由于計(jì)算各個(gè)元素存儲(chǔ)位置的時(shí)間相等，所以存取數(shù)組中任一元素的時(shí)間也相等。我們稱(chēng)具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。

三．元素存儲(chǔ)位置計(jì)算：385．3矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ)是指：為多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間；對(duì)零元不分配空間。

5．3．1特殊矩陣：一．對(duì)稱(chēng)矩陣：1．特點(diǎn)：aij=aji1≤i,j≤n2．存儲(chǔ)：可壓縮存儲(chǔ)，不失一般性，以行主序存儲(chǔ)下三角中的元（包括對(duì)角線上的元）。

5．3矩陣的壓縮存儲(chǔ)393．映像關(guān)系：以數(shù)組sa[n(n+1)/2]存儲(chǔ)n階對(duì)稱(chēng)矩陣A，稱(chēng)sa[n(n+1)/2]為n階對(duì)稱(chēng)矩陣A的壓縮存儲(chǔ)。（圖5.3）則sa[k]和矩陣元aij間關(guān)系：3．映像關(guān)系：稱(chēng)sa[n(n+1)/2]為n階對(duì)稱(chēng)矩陣A的壓40二．三角矩陣：1．特點(diǎn)：下(上)三角矩陣指矩陣的上(下)三角(不包括對(duì)角線)中的元均為常數(shù)c或零的n階矩陣。2．存儲(chǔ)：存儲(chǔ)其下(上)三角中的元和常數(shù)c。3．映像關(guān)系：以數(shù)組sa[n(n+1)/2]存儲(chǔ)，sa[0]可用來(lái)存儲(chǔ)常數(shù)c二．三角矩陣：41三．對(duì)角矩陣：1．特點(diǎn)：所有的非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中。如圖5．4所示。2．存儲(chǔ)：亦可按某個(gè)原則(或以行為主，或以對(duì)角線的順序)將其壓縮存儲(chǔ)到一維數(shù)組上。三．對(duì)角矩陣：425．3．2稀疏矩陣：一．什么是稀疏矩陣：二．抽象數(shù)據(jù)類(lèi)型稀疏矩陣的定義：（P96）三．稀疏矩陣壓縮存儲(chǔ)：只存非零元。以圖5.5矩陣為例5．3．2稀疏矩陣：431．三元組順序表：#defineMAXSIZE12500 //稀疏矩陣中非0元素的最大數(shù)目typedefstruct{ inti,j;//非0元素的行號(hào)、列號(hào) ElemTypee;//非0元素的值}Triple;//三元組數(shù)據(jù)類(lèi)型名typedefstruct{ intmu，nu，tu;//稀疏矩陣的行數(shù)、列數(shù)、非0元素的數(shù)目 Tripledata[MAXSIZE+1];//三元組數(shù)組，data[0]未用}TSMatrix;//三元組順序表數(shù)據(jù)類(lèi)型名1．三元組順序表：44矩陣轉(zhuǎn)置運(yùn)算：(1)將矩陣的行列值相互交換；(2)將每個(gè)三元組中的i和j相互調(diào)換；(3)重排三元組之間的次序。實(shí)現(xiàn)第三條有兩種處理方法：按照b.data中三元組的次序依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。

矩陣轉(zhuǎn)置運(yùn)算：45121213931-3361443245218611564-713-3161521122518319342446-763141212146算法5.1:StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//M為原三元組順序表，行優(yōu)先順序 T.mu=M.nu; T.nu=M.mu;T.tu=M.tu;if(!M.tu)returnFALSE;//三元組空q=1;for(col=1;col<=M.nu;col++)for(p=1;k<=M.tu;++p){if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e;q++;}} returnOK; }算法5.1:47這個(gè)算法主要的工作是在p和col的兩重循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(nu×tu)，即和M的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。一般矩陣的轉(zhuǎn)置算法為for(col＝1;col＜=nu;++colfor(row＝1;row＜=mu;++rowT[col][row]＝M[row][col];其時(shí)間復(fù)雜度為O(mu×nu)。當(dāng)非零元的個(gè)數(shù)tu和mu×nu同數(shù)量級(jí)時(shí)，算法5．1的時(shí)間復(fù)雜度就為O(mu×nu2)了(例如，假設(shè)在100×500的矩陣中有tu＝10000個(gè)非零元)，雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度提高了，因此算法5．1僅適于tu<<mu×nu的情況。這個(gè)算法主要的工作是在p和col的兩重循環(huán)中完成的，故算法的48(2)快速轉(zhuǎn)置：需兩個(gè)向量:num和cpotnum[col]表示矩陣M中第col列中非零元的個(gè)數(shù)，cpot[col]指示M中第col列的第一個(gè)非零元在b.data中的恰當(dāng)位置。則有cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1]2≤col≤a.nu例如，對(duì)圖5.5的矩陣M，num和cpot的值如表5.1所示（下頁(yè)圖）(2)快速轉(zhuǎn)置：491234567813-3161521122518319342446-763140000000111122211357889462975381234567813-350算法5.2：StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu; T.nu=M.mu;T.tu=M.tu; if(!M.tu)returnFALSE;//三元組空f(shuō)or(col=1;col<=M.nu;col++)num[col]=0;for(t=1;t<=M.tu;t++)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;col++)cpot[col]=cpot[col-1]+num[col-1]; for(p=1;k<=M.tu;++p){ col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e;++cpot[col]; }//得到的T也是三元組順序表，行優(yōu)先順序 returnOK; }該算法比算法5.1多用了兩個(gè)輔助向量。時(shí)間復(fù)雜度為O(nu+tu)。當(dāng)非零元的個(gè)數(shù)tu和mu×nu同數(shù)量級(jí)時(shí)，算法5.2的時(shí)間復(fù)雜度為O(mu×nu)。三元組順序表又稱(chēng)有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需按行號(hào)存取某一行的非零元，則需從頭開(kāi)始進(jìn)行查找。算法5.2：該算法比算法5.1多用了兩個(gè)輔助向量。時(shí)間復(fù)雜度512．行邏輯鏈接的順序表：為了便于隨機(jī)存取任意一行的非零元，則需知道每一行的第一個(gè)非零元在三元組表中的位置。為此可將上節(jié)快速轉(zhuǎn)置矩陣的算法中創(chuàng)建的指示“行”信息的輔助數(shù)組cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中。稱(chēng)這種“帶行鏈接信息”的三元組表為行邏輯鏈接的順序表，其類(lèi)型描述如下；typedefstruct{intmu，nu，tu;//稀疏矩陣的行數(shù)、列數(shù)、非0元素的數(shù)目Tripledata[MAXSIZE+1];//三元組數(shù)組，data[0]未用intrpos[MAXRC+1];//各行第一個(gè)非零元的位置表}TSMatrix;//三元組順序表數(shù)據(jù)類(lèi)型名2．行邏輯鏈接的順序表：523．十字鏈表：當(dāng)矩陣的非零元個(gè)數(shù)和位置在操作過(guò)程中變化較大時(shí)，就不宜采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組的線性表。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示三元組的線性表更為恰當(dāng)。例如，將矩陣B加到矩陣A上1)表示和實(shí)現(xiàn)：typedefstructOLNode{inti,j;ElemTypee;structOLNode*right,*down;}OLNode;*OLink;typedefstruct{OLink*rhead,*cheak;intmu,nu,tu;}CrossList;3．十字鏈表：53ijerightdown十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)

3005M=0-1002000ije十字鏈表的結(jié)點(diǎn)54算法5.4：創(chuàng)建稀疏矩陣，用十字鏈表存儲(chǔ)表示StatusCreateSMatrix_OL(CrossList&M){if(M)free(M);scanf(&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW);if(!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink))))exit(OVERFLOW);M.rhead[]=M.chead[]=NULL;算法5.4：創(chuàng)建稀疏矩陣，用十字鏈表存儲(chǔ)表示55for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p-->i=i;p-->j=j;p-->e=e;if((M.rhead[i]==NULL||M.rhead[i]-->j>j){p-->right=M.rhead[i];M.rhead[i]=p;}else{for(q=M.rhead[i];(q-->right)&&q-->right-->j<j;q=q-->right);p-->right=q-->right;q-->right=p;}for(scanf(&i,&j,&e);i!=0;scan56if(M.chead[j]==NULL||M.chead[j]-->i>i){p-->down=M.chead[j];M.chead[j]=p;}else{for(q=M.chead[j];(q-->down)&&q-->down-->i<i;q=q-->down);p-->down=q-->down;q-->down=p;}}returnOK;}//CreateSMatrix_OLif(M.chead[j]==NULL||M.chead[j572)將矩陣B加到矩陣A上:十字鏈表表示稀疏矩陣假設(shè)兩個(gè)矩陣相加后的結(jié)果為A'，則和矩陣A'中的非零元“aij'’可能有以下情況：1．a(chǎn)ij'=aij+bij改變結(jié)點(diǎn)的e域值2．a(chǎn)ij'=aij(bij=0)結(jié)點(diǎn)不變3．a(chǎn)ij'=bij(aij=0)增加結(jié)點(diǎn)4．a(chǎn)ij'=0(aij=-bij)刪除結(jié)點(diǎn)2)將矩陣B加到矩陣A上:585.4廣義表的定義廣義表是線性表的推廣。一．抽象數(shù)據(jù)類(lèi)型廣義表定義：(P107)二．術(shù)語(yǔ)：廣義表記作LS=(a1,a2,…,an)LS是廣義表的名稱(chēng)，n是其長(zhǎng)度。ai可以是單個(gè)元素（原子），也可以是廣義表（子表）。習(xí)慣上用大寫(xiě)字母表示廣義表的名稱(chēng)，用小寫(xiě)字母表示原子。廣義表非空時(shí)，稱(chēng)第一個(gè)元素a1為其表頭，稱(chēng)其余元素組成的表（a2,…,an）為其表尾。5.4廣義表的定義59例：(1)A＝()—A是一個(gè)空表，它的長(zhǎng)度為零。(2)B＝(e)—列表B只有一個(gè)原子e，B的長(zhǎng)度為1。(3)C＝(a，(b，c，d))—列表C的長(zhǎng)度為2，兩個(gè)元素分別為原子a和子表(b，c，d