多維數(shù)組和廣義表

多維數(shù)組和廣義表第一頁(yè)，共六十頁(yè)，2022年，8月28日第6

章樹(shù)知識(shí)點(diǎn)多維數(shù)組的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)特殊矩陣的壓縮存儲(chǔ)稀疏矩陣的三元組存儲(chǔ)、十字鏈表存儲(chǔ)廣義表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其基本算法難點(diǎn)第二頁(yè)，共六十頁(yè)，2022年，8月28日要求

第三頁(yè)，共六十頁(yè)，2022年，8月28日第6

章目錄6-1多維數(shù)組6-2特殊矩陣的壓縮存儲(chǔ)6-3稀疏矩陣6-4廣義表小結(jié)驗(yàn)證性實(shí)驗(yàn)６：稀疏矩陣和廣義表子系統(tǒng)自主性實(shí)驗(yàn)6：稀疏矩陣十字鏈表的存儲(chǔ)

單元練習(xí)6第四頁(yè)，共六十頁(yè)，2022年，8月28日6-1多維數(shù)組6.1.1邏輯結(jié)構(gòu)數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是結(jié)構(gòu)中的元素可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。比如，一維數(shù)組可以看作一個(gè)線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組。一般把三維以上的數(shù)組稱為多維數(shù)組，n維的多維數(shù)組可以視為n1維數(shù)組元素組成的線性結(jié)構(gòu)。其中每一個(gè)一維數(shù)組又由m個(gè)單元組成。圖6-1是一個(gè)n行m列的數(shù)組。

第五頁(yè)，共六十頁(yè)，2022年，8月28日第六頁(yè)，共六十頁(yè)，2022年，8月28日

在二維數(shù)組中的每一個(gè)元素最多可以有兩個(gè)直接前驅(qū)和兩個(gè)直接后繼（邊界除外），在n維數(shù)組中的每一個(gè)元素最多可以有n個(gè)直接前驅(qū)和n個(gè)直接后繼。所以多維數(shù)組是一種非線性結(jié)構(gòu)。數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個(gè)數(shù)據(jù)元素有唯一的一組下標(biāo)來(lái)標(biāo)識(shí)，通常在很多高級(jí)語(yǔ)言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。因此，在數(shù)組上一般不做插入或刪除數(shù)據(jù)元素的操作。在數(shù)組中經(jīng)常做的兩種操作如下。（1）取值操作：給定一組下標(biāo)，讀取其對(duì)應(yīng)的數(shù)據(jù)元素。（2）賦值操作：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。

第七頁(yè)，共六十頁(yè)，2022年，8月28日6.1.2存儲(chǔ)結(jié)構(gòu)

通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種存儲(chǔ)結(jié)構(gòu)，這是因?yàn)樵谟?jì)算機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)是一維的。數(shù)組的行列固定后，通過(guò)一個(gè)映象函數(shù)，就可以根據(jù)數(shù)組元素的下標(biāo)得到它的存儲(chǔ)地址。對(duì)于一維數(shù)組只要按下標(biāo)順序分配即可；對(duì)多維數(shù)組分配時(shí)，要把它的元素映象存儲(chǔ)在一維存儲(chǔ)器中。1．存儲(chǔ)方式（1）以行為主（row

major

order）以行為主的存儲(chǔ)方式也稱為按行優(yōu)先順序方式，實(shí)現(xiàn)時(shí)按行號(hào)從小到大的順序，先存儲(chǔ)第0行的全部元素，再存放第1行的元素、第2行的元素……

一個(gè)2×3二維數(shù)組的邏輯結(jié)構(gòu)如圖6-2所示，以行為主的內(nèi)存映象如圖6-3（a）所示，其分配順序?yàn)椋篴00，a01，a02，a10，a11，a12。第八頁(yè)，共六十頁(yè)，2022年，8月28日第九頁(yè)，共六十頁(yè)，2022年，8月28日

以行為主序的分配規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個(gè)下標(biāo)再變……，從右向左，最后是左下標(biāo)。（2）以列為主序（column

major

order）以列為主的存儲(chǔ)方式也稱為按列優(yōu)先順序方式，實(shí)現(xiàn)時(shí)按列號(hào)從小到大的順序，先存儲(chǔ)第0列的全部元素，再存儲(chǔ)第1列的元素、第2列的元素……

圖6-2所示的邏輯結(jié)構(gòu)，以列為主的內(nèi)存映象如圖6-3（b）所示，其分配順序?yàn)椋篴00，a10，a01，a11，a02，a12。以列為主分配的規(guī)律恰好與以行為主次序相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個(gè)下標(biāo)再變……，從左向右，最后是右下標(biāo)。第十頁(yè)，共六十頁(yè)，2022年，8月28日2．存儲(chǔ)地址“以行為主”次序分配存儲(chǔ)單元為例看其地址的計(jì)算（1）二維數(shù)組中aij的地址在C語(yǔ)言中數(shù)組中每一維的下界定義為0，數(shù)組的基址為L(zhǎng)OC(a00)，每個(gè)數(shù)組元素占據(jù)d個(gè)字節(jié)，那么aij

的物理地址可用一個(gè)線性尋址函數(shù)計(jì)算：

LOC(aij)=LOC(a00)+(i×n+j)×d

（0下標(biāo)起始的語(yǔ)言）（2）三維數(shù)組中aijk的地址同理對(duì)于三維數(shù)組元素aijk的物理地址為：

LOC(aijk)=LOC(a000)+((i×n×p+j×p+k)×d

（0下標(biāo)起始的語(yǔ)言）

第十一頁(yè)，共六十頁(yè)，2022年，8月28日【例6-1】設(shè)二維數(shù)組A5×6，每個(gè)元素占4個(gè)字節(jié)（Byte），存儲(chǔ)器按字節(jié)編址。已知A的起始地址為2000。計(jì)算（1）數(shù)組的大小

n×m×d=5×6×4=120Byte（2）數(shù)組結(jié)點(diǎn)a45的存儲(chǔ)地址

LOC(aij)=LOC(a00)+(i*n+j)*d//n為總列數(shù)

LOC(a45)=2000+(4×6+5)×4=2116（3）按行為主存儲(chǔ)，計(jì)算a32的存儲(chǔ)地址

LOC(aij)=LOC(a00)+(i*n+j)*d//n為總列數(shù)

LOC(a32)=2000+(3×6+2)×4=2080（4）按列為主存儲(chǔ)，計(jì)算a32的存儲(chǔ)地址

LOC(aij)=LOC(a00)+(j*m+i)*d//m為總行數(shù)

LOC(a32)=2000+(2×5+3)×4=2052第十二頁(yè)，共六十頁(yè)，2022年，8月28日

【例6-2】若矩陣An×m

中存在某個(gè)元素aij，滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫(xiě)一個(gè)算法，找出A中的所有鞍點(diǎn)?；舅枷耄涸诰仃嘇中求出每一行的最小值元素，然后判斷該元素是否是它所在列中的最大值。如果是則打印輸出，接著處理下一行。設(shè)矩陣A用一個(gè)二維數(shù)組表示，其算法如下：voidsaddle(intA[][],intn,intm) {inti,j,min;for(i=0;i<n;i++)

//按行處理

{min=A[i][0]for(j=1;j<m;j++)if(A[i][j]<min)min=A[i][j];//找第i行最小值

第十三頁(yè)，共六十頁(yè)，2022年，8月28日f(shuō)or(j=0;j<m;j++)

//檢測(cè)最小值是否是鞍點(diǎn)

if(A[i][j]==min){k=j;p=0;while(p<n&&A[p][j]<min)p++;if(p>=n)printf(＂%d,%d,%d\n＂,i,k,min);}}}算法的時(shí)間復(fù)雜度為O(n(m+nm))。第十四頁(yè)，共六十頁(yè)，2022年，8月28日6-2

特殊矩陣的壓縮存儲(chǔ)

矩陣是一個(gè)二維數(shù)組，是眾多科學(xué)與工程計(jì)算問(wèn)題中研究的數(shù)學(xué)對(duì)象。在矩陣中非零元素或零元素的分布有一定規(guī)律的矩陣稱為特殊矩陣，如三角矩陣、對(duì)稱矩陣、帶狀矩陣、稀疏矩陣等。當(dāng)矩陣的階數(shù)很大時(shí)，用普通的二維數(shù)組存儲(chǔ)這些特殊矩陣將會(huì)占用很多的存儲(chǔ)單元。從節(jié)約存儲(chǔ)空間的角度考慮，下面來(lái)考慮這些特殊矩陣的存儲(chǔ)方法。第十五頁(yè)，共六十頁(yè)，2022年，8月28日

6.2.1對(duì)稱矩陣對(duì)稱矩陣是一種特殊矩陣，n階方陣的元素滿足性質(zhì)：aij=aji

（0<=i,j<=n1）。如圖6-4所示是一個(gè)５階對(duì)稱矩陣。對(duì)稱矩陣是關(guān)于主對(duì)角線的對(duì)稱，因此只需存儲(chǔ)上三角或下三角部分的數(shù)據(jù)即可。比如，只存儲(chǔ)下三角中的元素aij，其特點(diǎn)是中j<=i且0=<i=<n1，對(duì)于上三角中的元素aij

，它和對(duì)應(yīng)的aji相等，因此當(dāng)訪問(wèn)的元素在上三角時(shí)，直接去訪問(wèn)和它對(duì)應(yīng)的下三角元素即可，這樣，原來(lái)需要nn個(gè)存儲(chǔ)單元，現(xiàn)在只需要n(n+1)/2個(gè)存儲(chǔ)單元了，節(jié)約了n(n1)/2個(gè)存儲(chǔ)單元。第十六頁(yè)，共六十頁(yè)，2022年，8月28日?qǐng)D6-45階對(duì)稱方陣及它的壓縮存儲(chǔ)

第十七頁(yè)，共六十頁(yè)，2022年，8月28日

如何只存儲(chǔ)下三角部分呢？將下三角部分以行序?yàn)橹餍蝽樞虼鎯?chǔ)到一個(gè)向量SA中去。在下三角中共有n(n+1)/2個(gè)元素，存儲(chǔ)到一個(gè)向量空間SA[0]至SA[n(n+1)/2-1]中，存儲(chǔ)順序可用圖6-5示意。圖6-5對(duì)稱矩陣下三角壓縮存儲(chǔ)第十八頁(yè)，共六十頁(yè)，2022年，8月28日

原矩陣下三角中的某一個(gè)元素aij具體對(duì)應(yīng)一個(gè)sak，用“以行優(yōu)先”存放下三角部分的元素時(shí)，a00存入sa0，a10存入sa1，a11存入sa2……。sak與aij的一一對(duì)應(yīng)關(guān)系為：

k=j(j+1)/2+i

（0<=k<n(n+1)/21）當(dāng)i≥j時(shí)，在下三角部分aij前有i行，共有1+2+3+…+i個(gè)元素，而aij是第i行的第j個(gè)元素，即有k=1+2+3+……+i+j=i(i+1)/2+j。當(dāng)i<j時(shí)，aij是上三角中的元素，因?yàn)閍ij=aji

，這樣，訪問(wèn)上三角中的元素aij時(shí)則去訪問(wèn)和它對(duì)應(yīng)的下三角中的aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的元素在SA中的對(duì)應(yīng)關(guān)系：

k=j(j+1)/2+i

（0<=k<n(n+1)/21）第十九頁(yè)，共六十頁(yè)，2022年，8月28日6.2.2三角矩陣

三角矩陣的特殊性是以主對(duì)角線劃分矩陣。主對(duì)角線任意一側(cè)（不包括主對(duì)角線中）的元素均為常數(shù)，如圖6-6所示（矩陣中的c為某個(gè)常數(shù)）。三角矩陣又可以分為下三角矩陣（主對(duì)角線以上均為同一個(gè)常數(shù)和上三角矩陣（主對(duì)角線以下均為同一個(gè)常數(shù)）。下面討論三角矩陣的壓縮存儲(chǔ)方法。

第二十頁(yè)，共六十頁(yè)，2022年，8月28日1．下三角矩陣的存儲(chǔ)下三角矩陣的存儲(chǔ)與對(duì)稱矩陣的下三角形存儲(chǔ)類似，不同之處在于存完下三角中的元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量。因?yàn)槭峭粋€(gè)常數(shù)，所以只要增加一個(gè)存儲(chǔ)單元即可，這樣一共需要n(n+1)/2+1個(gè)存儲(chǔ)單元。將nn的下三角矩陣壓縮存儲(chǔ)設(shè)到向量SA[n(n+1)/2+1]中，這種的存儲(chǔ)方式可節(jié)約n(n1)/21個(gè)存儲(chǔ)單元。sak與aji

的對(duì)應(yīng)關(guān)系為：

下三角矩陣壓縮存儲(chǔ)如圖6-7所示。第二十一頁(yè)，共六十頁(yè)，2022年，8月28日2．上三角矩陣對(duì)于上三角矩陣，其存儲(chǔ)思想與下三角類似，共需要n(n+1)/2+1個(gè)存儲(chǔ)單元。sak與aji

的對(duì)應(yīng)關(guān)系為：

上三角矩陣壓縮存儲(chǔ)如圖6-8所示。

圖6-8上三角矩陣壓縮存儲(chǔ)第二十二頁(yè)，共六十頁(yè)，2022年，8月28日6.3

稀疏矩陣

上述特殊矩陣，由于元素的分布具有某種規(guī)律，所以能找到一種合適的方法進(jìn)行壓縮存儲(chǔ)。但實(shí)際應(yīng)用中有一種矩陣，在mn的矩陣中有t個(gè)非零元素，且t遠(yuǎn)小于mn，我們這樣的矩陣稱為稀疏矩陣。在很多科學(xué)管理及工程計(jì)算中，常會(huì)遇到階數(shù)很高的大型稀疏矩陣。若按常規(guī)方法順序分配在計(jì)算機(jī)內(nèi)，那是相當(dāng)浪費(fèi)內(nèi)存的。為此提出另外一些存儲(chǔ)方法，僅僅存放非零元素。但對(duì)于這類矩陣，通常零元素分布沒(méi)有規(guī)律，為了能找到相應(yīng)的元素，僅存儲(chǔ)非零元素的值是不夠的，還要記下它所在的行和列等信息。下面介紹幾種常用的稀疏矩陣存儲(chǔ)方法以及算法的實(shí)現(xiàn)。第二十三頁(yè)，共六十頁(yè)，2022年，8月28日

6.3.1稀疏矩陣的存儲(chǔ)1．三元組表存儲(chǔ)將非零元素所在的行、列以及它的值構(gòu)成一個(gè)三元組，然后再按某種規(guī)律存儲(chǔ)這些三元組，采用這種方法存儲(chǔ)稀疏矩陣稱為三元組表，可以大大節(jié)約稀疏矩陣的存儲(chǔ)空間。如圖6-9的稀疏矩陣A，采用按行優(yōu)先順序方式存儲(chǔ)該表，其三元組表如圖6-10所示。顯然，要唯一的表示一個(gè)稀疏矩陣，每個(gè)非零元素必須存儲(chǔ)行、列、值（i,j,v）三個(gè)信息。第二十四頁(yè)，共六十頁(yè)，2022年，8月28日第二十五頁(yè)，共六十頁(yè)，2022年，8月28日三元組表的定義：#defineSMAX100//定義一個(gè)足夠大的三元組表structSPNode//定義三元組{ inti,j,v;//三元組非零元素的行、列和值};structsparmatrix //定義稀疏矩陣{introws,cols,terms;//稀疏矩陣行、列和非零元素的個(gè)數(shù)

SPNodedata[SMAX]; //三元組表};

這樣的存儲(chǔ)方法確實(shí)節(jié)約了存儲(chǔ)空間，但矩陣的運(yùn)算可能會(huì)變得復(fù)雜一些。第二十六頁(yè)，共六十頁(yè)，2022年，8月28日2．帶行指針的鏈表存儲(chǔ)若把具有同一行號(hào)的非零元素用一個(gè)鏈表連接起來(lái)，則稀疏矩陣中的若干行組成若干個(gè)單向鏈表，合起來(lái)就成為帶行指針的單向鏈表。圖6-9的稀疏矩陣A，可以用圖6-11帶行指針的單向鏈表表示。第二十七頁(yè)，共六十頁(yè)，2022年，8月28日3．十字鏈表存儲(chǔ)

三元組表可以看作稀疏矩陣順序存儲(chǔ)，但是在做一些操作（如加法、乘法）時(shí)，非零元素的位置和個(gè)數(shù)會(huì)發(fā)生變化，三元組表就不太合適了。此時(shí)采用十字鏈表來(lái)表示稀疏矩陣將是很方便的。用十字鏈表存儲(chǔ)稀疏矩陣的基本思想是：把每個(gè)非零元素作為一個(gè)結(jié)點(diǎn)存儲(chǔ)，結(jié)點(diǎn)中除了表示非零元素所在的行、列、值的三元組（i,j,v）以外還增加兩個(gè)指針域，其結(jié)構(gòu)如圖6-14所示。其中：列指針域down用來(lái)指向本列中下一個(gè)非零元素；行指針域right用來(lái)指向本行中下一個(gè)非零元素。第二十八頁(yè)，共六十頁(yè)，2022年，8月28日?qǐng)D6-13是一個(gè)稀疏矩陣A的十字鏈表。

第二十九頁(yè)，共六十頁(yè)，2022年，8月28日

稀疏矩陣中每一行的非零元素結(jié)點(diǎn)按其列號(hào)從小到大的順序由right域連成一個(gè)帶表頭結(jié)點(diǎn)的循環(huán)行鏈表，同樣每一列中的非零元素按其行號(hào)從小到大的順序由down域也連成一個(gè)帶表頭結(jié)點(diǎn)的循環(huán)列鏈表。即每個(gè)非零元素aij既是第i行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，又是第j列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)。行鏈表、列鏈表的頭結(jié)點(diǎn)的i域和j域置0。每一列鏈表的表頭結(jié)點(diǎn)的down域指向該列鏈表的第一個(gè)元素結(jié)點(diǎn)，每一行鏈表的表頭結(jié)點(diǎn)的right域指向該行表的第一個(gè)元素結(jié)點(diǎn)。由于各行、列鏈表頭結(jié)點(diǎn)的i域、j域和v域均為零，行鏈表頭結(jié)點(diǎn)只用right指針域，列鏈表頭結(jié)點(diǎn)只用right指針域，故這兩組表頭結(jié)點(diǎn)可以合用，也就是說(shuō)對(duì)于第i行的鏈表和第i列的鏈表可以共用同一個(gè)頭結(jié)點(diǎn)。為了方便地找到每一行或每一列，將每行（列）的這些頭結(jié)點(diǎn)們鏈接起來(lái)，因?yàn)轭^結(jié)點(diǎn)的值域空閑，所以用頭結(jié)點(diǎn)的值域作為連接各頭結(jié)點(diǎn)的鏈域，即第i行（列）的頭結(jié)點(diǎn)的值域指向第i+1行（列）的頭結(jié)點(diǎn)……，形成一個(gè)循環(huán)表。這個(gè)循環(huán)表又有一個(gè)頭結(jié)點(diǎn)，這就是最后的總頭結(jié)點(diǎn)，指針HA指向它?？傤^結(jié)點(diǎn)的i和j域存儲(chǔ)原矩陣的行數(shù)和列數(shù)。第三十頁(yè)，共六十頁(yè)，2022年，8月28日

因?yàn)榉橇阍亟Y(jié)點(diǎn)的值域是datatype類型，在表頭結(jié)點(diǎn)中需要一個(gè)指針類型，為了使整個(gè)結(jié)構(gòu)的結(jié)點(diǎn)一致，我們規(guī)定表頭結(jié)點(diǎn)和其他結(jié)點(diǎn)有同樣的結(jié)構(gòu)，因此該域用一個(gè)共用體來(lái)表示；改進(jìn)后的結(jié)點(diǎn)結(jié)構(gòu)如圖6-14所示。

結(jié)點(diǎn)的結(jié)構(gòu)定義如下：typedefstructnode{inti,j;structnode*down,*right;unionv_next //定義一個(gè)共用體

{datatypev; //值域

structnode*next; //表頭結(jié)點(diǎn)使用的next域

}}MNode,*MLink;第三十一頁(yè)，共六十頁(yè)，2022年，8月28日6.3.2稀疏矩陣的算法1．建立稀疏矩陣A的十字鏈表

首先輸入的信息是：m（A的行數(shù)），n（A的列數(shù)），r（非零項(xiàng)的數(shù)目），緊跟著輸入的是r個(gè)形如（i,j,aij）的三元組。算法的設(shè)計(jì)思想是：首先建立每行（每列）只有頭結(jié)點(diǎn)的空鏈表，并建立起這些頭結(jié)點(diǎn)拉成的循環(huán)鏈表；然后每輸入一個(gè)三元組（i,j,aij），則將其結(jié)點(diǎn)按其列號(hào)的大小插入到第i個(gè)行鏈表中去，同時(shí)也按其行號(hào)的大小將該結(jié)點(diǎn)插入到第j個(gè)列鏈表中去。在算法中將利用一個(gè)輔助數(shù)組MNodehd[s+1];其中s=max(m,n),hd[i]指向第i行（第i列）鏈表的頭結(jié)點(diǎn)。這樣做可以在建立鏈表時(shí)隨機(jī)的訪問(wèn)任何一行（列），為建表帶來(lái)方便。第三十二頁(yè)，共六十頁(yè)，2022年，8月28日MLinkCreatMLink() //返回十字鏈表的頭指針｛

MLinkH;Mnode*p,*q,*hd[s+1];inti,j,m,n,t;datatypev;scanf("d%,d%,%d",&m,&n,&t);H=newMNode; //申請(qǐng)總頭結(jié)點(diǎn)

H->row=m;H->col=n;hd[0]=H;for(i=1;i<S;i++){p=newMNode; //申請(qǐng)第i個(gè)頭結(jié)點(diǎn)

p->row=0;p->col=0;p->right=p;p->down=p;hd[i]=p;hd[i-1]->v_next.next=p;}

第三十三頁(yè)，共六十頁(yè)，2022年，8月28日

hd[S]->v_next.next=H; //將頭結(jié)點(diǎn)們形成循環(huán)鏈表

for(k=1;k<=t;k++){scanf(“%d,%d,%d”,&i,&j,&v);//輸入一個(gè)三元組

p=newMNode;p->row=i;p->col=j;p->v_next.v=vq=hd[i];while(q->right!=hd[i]&&(q->right->col)<j)//按列號(hào)找位置

q=q->right;p->right=q->right;//插入

q->right=p;q=hd[i];while(q->down!=hd[j]&&(q->down->row)<i)//按行號(hào)找位置

q=q->down;p->down=q->down; //插入

q->down=p;}returnH;}第三十四頁(yè)，共六十頁(yè)，2022年，8月28日

上述算法中，建立頭結(jié)點(diǎn)循環(huán)鏈表時(shí)間復(fù)雜度為O(S)，插入每個(gè)結(jié)點(diǎn)到相應(yīng)的行表和列表的時(shí)間復(fù)雜度是O(tS)，這是因?yàn)槊總€(gè)結(jié)點(diǎn)插入時(shí)都要在鏈表中尋找插入位置，所以總的時(shí)間復(fù)雜度為O(tS)。該算法對(duì)三元組的輸入順序沒(méi)有要求。如果我們輸入三元組時(shí)是按以行為主序（或列）輸入的，則每次將新結(jié)點(diǎn)插入到鏈表的尾部的，改進(jìn)算法后，時(shí)間復(fù)雜度為O(S+t)。第三十五頁(yè)，共六十頁(yè)，2022年，8月28日2．稀疏矩陣的加法已知兩個(gè)十字鏈表存儲(chǔ)的稀疏矩陣A和B，計(jì)算C=A+B，C也采用十字鏈表方式存儲(chǔ)，并且在A的基礎(chǔ)上形成C。由矩陣的加法規(guī)則知，只有A和B行列對(duì)應(yīng)相等，二者才能相加。C中的非零元素cij只可能有3種情況：或者是aij+bij，或者是aij（bij=0），或者是bij（aij=0），因此當(dāng)B加到A上時(shí)，對(duì)A十字鏈表的當(dāng)前結(jié)點(diǎn)來(lái)說(shuō)，對(duì)應(yīng)下列四種情況：或者改變結(jié)點(diǎn)的值（aij+bij≠0），或者不變（bij0），或者插入一個(gè)新結(jié)點(diǎn)（aij0），還可能是刪除一個(gè)結(jié)點(diǎn)（aij+bij0）。整個(gè)運(yùn)算從矩陣的第一行起逐行進(jìn)行。對(duì)每一行都從行表的頭結(jié)點(diǎn)出發(fā)，分別找到A和B在該行中的第一個(gè)非零元素結(jié)點(diǎn)后開(kāi)始比較，然后按4種不同情況分別處理。設(shè)pa和pb分別指向A和B的十字鏈表中行號(hào)相同的兩個(gè)結(jié)點(diǎn)，4種情況如下：第三十六頁(yè)，共六十頁(yè)，2022年，8月28日（1）若pa->col=pb->col且pa->v+pb->v≠0，則只要用aij+bij的值改寫(xiě)pa所指結(jié)點(diǎn)的值域即可。（2）若pa->col=pb->col且pa->v+pb->v=0，則需要在矩陣A的十字鏈表中刪除pa所指結(jié)點(diǎn)，此時(shí)需改變?cè)撔墟湵碇星摆吔Y(jié)點(diǎn)的right域，以及該列鏈表中前趨結(jié)點(diǎn)的down域。（3）若pa->col<pb->col且pa->col≠0（即不是表頭結(jié)點(diǎn)），則只需要將pa指針向右推進(jìn)一步，并繼續(xù)進(jìn)行比較。（4）

若pa->col>pb->col或pa->col0（即是表頭結(jié)點(diǎn)），則需要在矩陣A的十字鏈表中插入一個(gè)pb所指結(jié)點(diǎn)。由前面建立十字鏈表算法知，總表頭結(jié)點(diǎn)的行列域存放的是矩陣的行和列，而各行（列）鏈表的頭結(jié)點(diǎn)其行列域值為零，當(dāng)然各非零元素結(jié)點(diǎn)的行列域其值不會(huì)為零，下面分析的4種情況利用了這些信息來(lái)判斷是否為表頭結(jié)點(diǎn)。第三十七頁(yè)，共六十頁(yè)，2022年，8月28日

MLinkAddMat(Ha,Hb)MLinkHa,Hb;{Mnode*p,*q,*pa,*pb,*ca,*cb,*qa;if(Ha->row!=Hb->row||Ha->col!=Hb->col)returnNULL;ca=Ha->v_next.next;//ca初始指向A矩陣中第一行表頭結(jié)點(diǎn)

cb=Hb->v_next.next;//cb初始指向B矩陣中第一行表頭結(jié)點(diǎn)

do{pa=ca->right;//pa指向A矩陣當(dāng)前行中第一個(gè)結(jié)點(diǎn)

qa=ca; //qa是pa的前驅(qū)

pb=cb->right;//pb指向B矩陣當(dāng)前行中第一個(gè)結(jié)點(diǎn)

while(pb->col!=0)//當(dāng)前行沒(méi)有處理完

{if(pa->col<pb->col&&pa->col!=0){qa=pa;pa=pa->right;}elseif(pa->col>pb->col||pa->col==0){p=newMNode;p->row=pb->row;p->col=pb->col;p->v=pb->v;p->right=pa;qa->right=p; //新結(jié)點(diǎn)插入*pa的前面

pa=p; //新結(jié)點(diǎn)還要插到列鏈表的合適位置，先找位置，再插入

q=Find_JH(Ha,p->col); //從列鏈表的頭結(jié)點(diǎn)找起

while(q->down->row!=0&&q->down->row<p->row)q=q->down;p->down=q->down;//插在*q的后面

q->down=p;pb=pb->right;}else //第一、二種情況

{x=pa->v_next.v+pb->v_next.v;if(x==0) //第二種情況

{qa->right=pa->right;//從行鏈中刪除，

//要從列鏈中刪除，找*pa的列前驅(qū)結(jié)點(diǎn)

q=Find_JH(Ha,pa->col);//從列鏈表的頭結(jié)點(diǎn)找起

while(q->down->row<pa->row)q=q->down; q->down=pa->down;deletepa;pa=qa;}else //第一種情況

{pa->v_next.v=x;qa=pa;}pa=pa->right;pb=pb->right;}}ca=ca->v_next.next; //ca指向A中下一行的表頭結(jié)點(diǎn)

cb=cb->v_next.next; //cb指向B中下一行的表頭結(jié)點(diǎn)

}while(ca->row==0) //當(dāng)還有未處理完的行則繼續(xù)

returnHa;}

為了保持算法的層次，在上面的算法中用到了一個(gè)函數(shù)Find_JH()，其功能是：返回十字鏈表H中第j列鏈表的頭結(jié)點(diǎn)指針。第三十八頁(yè)，共六十頁(yè)，2022年，8月28日3．矩陣的轉(zhuǎn)置

設(shè)SPMatrixA;表示一m*n的稀疏矩陣，其轉(zhuǎn)置B則是一個(gè)n*m的稀疏矩陣，因此也有SPMatrixB;由稀疏矩陣A求它的轉(zhuǎn)置B只要將A的行、列轉(zhuǎn)化成B的列、行。將A.data中每一三元組的行列交換后轉(zhuǎn)化到B.data后，似乎已完成了轉(zhuǎn)置，其實(shí)不然。A的轉(zhuǎn)置B如圖6.15所示，圖6.16是它對(duì)應(yīng)的三元組存儲(chǔ)。也就是說(shuō)，在A的三元組存儲(chǔ)基礎(chǔ)上得到B的三元組表存儲(chǔ)。第三十九頁(yè)，共六十頁(yè)，2022年，8月28日轉(zhuǎn)置算法的實(shí)質(zhì)是將矩陣A的行和列轉(zhuǎn)化成矩陣B的列和行。sparmatrixTrans(sparmatrixA)//調(diào)用稀疏矩陣A{sparmatrixB;//定義稀疏矩陣BB.rows=A.cols;B.cols=A.rows;B.terms=A.terms;for(intn=0;n<=A.terms-1;n++) {B.data[n].i=A.data[n].j; B.data[n].j=A.data[n].i; B.data[n].v=A.data[n].v; }returnB;//返回轉(zhuǎn)置矩陣B}

本算法的時(shí)間復(fù)雜度為O(n)。第四十頁(yè)，共六十頁(yè)，2022年，8月28日

廣義表是線性表的推廣，也有人稱其為列表（Lists）。線性表中的元素僅限于單個(gè)數(shù)據(jù)元素（也稱為原子項(xiàng)），即不可以再分割；而廣義表中的元素既可以是原子項(xiàng)，也可以是子表。6.4.1廣義表的定義和運(yùn)算1.廣義表的定義廣義表（GeneralizedLists）是n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an的有序序列，一般記作：LS＝（a1，a2，…，ai，…，an）其中：LS是廣義表的名稱，n是廣義表的長(zhǎng)度。每個(gè)ai（1≤i≤n）是LS的成員，它可以是單個(gè)元素（原子），也可以是一個(gè)廣義表（子表）。當(dāng)廣義表LS非空時(shí)，稱第一個(gè)元素a1為L(zhǎng)S的表頭（head），稱其余元素組成的表（a2，…，ai，…，an）為L(zhǎng)S的表尾（tail）。顯然，廣義表的定義是遞歸的。6-4

廣義表第四十一頁(yè)，共六十頁(yè)，2022年，8月28日

廣義表通常用圓括號(hào)括起來(lái)，并用逗號(hào)分隔表中的元素。為了清楚起見(jiàn)，通常用大寫(xiě)字母表示廣義表，用小寫(xiě)字母表示單個(gè)數(shù)據(jù)元素。廣義表的長(zhǎng)度指該廣義表中所包含的元素（包括原子和子表）的個(gè)數(shù)。廣義表的深度指該廣義表中所包含括號(hào)的層數(shù)。廣義表中的結(jié)點(diǎn)具有不同的結(jié)構(gòu)，即原子結(jié)點(diǎn)和子表結(jié)點(diǎn)。為了將兩者統(tǒng)一，一般用一個(gè)標(biāo)志tag，當(dāng)其為1時(shí)表示是原子結(jié)點(diǎn)，其data域存儲(chǔ)結(jié)點(diǎn)的值，link域指向下一個(gè)結(jié)點(diǎn)；當(dāng)tag為0時(shí)表示是子表結(jié)點(diǎn)，其sublist為指向子表的指針。廣義表的存儲(chǔ)結(jié)點(diǎn)可定義如下：structlinknode

{inttag; //區(qū)分原子和子表的標(biāo)志位

linknode*link;//存放下一個(gè)元素的地址

uniondata_sublist{chardata;//元素的值域

linknode*sublist;//存放子表的指針

}node;

};第四十二頁(yè)，共六十頁(yè)，2022年，8月28日

2.廣義表的性質(zhì)從上述廣義表的定義和例子可以得到廣義表的下列重要性質(zhì)：（1）廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其中的元素可以是單元素，也可以是子表。（2）廣義表可以是遞歸的表，即廣義表也可以是其自身的子表。例如表E就是一個(gè)遞歸的表。（3）義表可以為其他表所共享。例如表B、表C是表D的共享子表。廣義表的結(jié)構(gòu)相當(dāng)靈活，它可以兼容線性表、數(shù)組、樹(shù)和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)。當(dāng)二維數(shù)組的每行（或每列）作為子表處理時(shí)，二維數(shù)組即為一個(gè)廣義表。另外，樹(shù)和有向圖也可以用廣義表來(lái)表示。廣義表不僅集中了線性表、數(shù)組、樹(shù)和有向圖等常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可有效地利用存儲(chǔ)空間，因此在計(jì)算機(jī)的應(yīng)用領(lǐng)域有許多成功應(yīng)用的實(shí)例。第四十三頁(yè)，共六十頁(yè)，2022年，8月28日【例6.3】廣義表的例子（1）A＝()，廣義表A是長(zhǎng)度為0的空表。（2）B＝(a，b)，B是長(zhǎng)度為2的廣義表。由于表中的元素全部是原子項(xiàng)，它實(shí)質(zhì)上就是線性表。（3）C＝(c，(d，e))，C是長(zhǎng)度為2的廣義表，其中第一項(xiàng)為原子項(xiàng)，第二項(xiàng)為子表。（4）D＝(B，C)，D是長(zhǎng)度為2的廣義表，其中每一項(xiàng)都是子表。（5）E＝(f，g，E)，E是長(zhǎng)度為3的廣義表，其中第一、第二項(xiàng)為原子項(xiàng)，第三項(xiàng)是本身，這樣的廣義表也稱為遞歸表。第四十四頁(yè)，共六十頁(yè)，2022年，8月28日【例6.4】求例6.3廣義表的頭元素和尾元素。

Head（A）＝（） Tail（A）＝（）

Head（B）＝a Tail（B）＝bHead（C）＝c Tail（C）＝（（d，e））

Head（D）＝B Tail（D）＝CHead（E）＝fTail（E）＝（g，E）3.廣義表基本運(yùn)算（1）

創(chuàng)建廣義表：CreateGL(GL)

操作結(jié)果：創(chuàng)建一個(gè)廣義表GL（2）

求廣義表的長(zhǎng)度：Len(GL)

初始條件：廣義表存在。操作結(jié)果：返回廣義表的長(zhǎng)度。第四十五頁(yè)，共六十頁(yè)，2022年，8月28日（3）

求廣義表的深度：Depth(GL)

初始條件：廣義表存在。操作結(jié)果：返回廣義表的深度。（4）查找操作：Search(GL，x)

初始條件：廣義表GL存在，ｘ是給定的一個(gè)數(shù)據(jù)元素或子表。操作結(jié)果：查找成功返回1；

否則返回0。（5）

求廣義表頭部：Head(LS)

初始條件：廣義表存在。操作結(jié)果：返回廣義表的頭元素。（6）

求廣義表尾部：Tail(LS)

初始條件：廣義表存在。操作結(jié)果：返回廣義表的尾元素。第四十六頁(yè)，共六十頁(yè)，2022年，8月28日6.4.2廣義表的首尾存儲(chǔ)法廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，因此難以用順序的存儲(chǔ)結(jié)構(gòu)來(lái)表示，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分配靈活，易于解決廣義表的共享與遞歸問(wèn)題，所以通常都采用鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)廣義表。廣義表中的元素可以是數(shù)據(jù)元素，也可以是表，因此結(jié)點(diǎn)的結(jié)構(gòu)也需要兩種：一種是表結(jié)點(diǎn)，用以表示表；另一種是原子結(jié)點(diǎn)，用以表示原子。按結(jié)點(diǎn)形式的不同，廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又可以分為不同的兩種存儲(chǔ)方式。由于廣義表中的數(shù)據(jù)元素既可能是表也可能是單元素，相應(yīng)地在頭尾表示法中結(jié)點(diǎn)的結(jié)構(gòu)形式有兩種：一種是表結(jié)點(diǎn)，用以表示表；另一種是元素結(jié)點(diǎn)，用以表示原子。表結(jié)點(diǎn)由三個(gè)域：標(biāo)志域（tag=1）、表頭指針域（hp）、表尾指針域（tp）組成；而原子結(jié)點(diǎn)由兩個(gè)域：標(biāo)志域（tag=0）和值域（data）組成。第四十七頁(yè)，共六十頁(yè)，2022年，8月28日

廣義表的結(jié)點(diǎn)形式如圖6.17所示。

廣義表的這種表示法也稱為頭尾表示法。若廣義表不空，則可分解成表頭和表尾；反之，一對(duì)確定的表頭和表尾可惟一地確定一個(gè)廣義表。頭尾表示法就是根據(jù)這一性質(zhì)設(shè)計(jì)而成的一種存儲(chǔ)方法。對(duì)于例6.3廣義表的例子所列舉的廣義表A、B、C、D、E，若采用頭尾表示法的存儲(chǔ)方式，其存儲(chǔ)結(jié)構(gòu)如圖6.18所示。第四十八頁(yè)，共六十頁(yè)，2022年，8月28日第四十九頁(yè)，共六十頁(yè)，2022年，8月28日6.4.3廣義表的算法1．創(chuàng)建廣義表算法設(shè)廣義表以單鏈表形式存儲(chǔ)，元素的類型為字符型char。廣義表的元素由鍵盤(pán)輸入，假定全部為字母。元素之間用逗號(hào)分割，元素的起止符號(hào)分別用左、右圓括號(hào)表示。linknode*CreateGL(chars[]){linknode*p,*q,*r,*gh;charsubs[100],hstr[100];intlen;len=strlen(s);if(!strcmp(s,"()")) gh=NULL;else第五十頁(yè)，共六十頁(yè)，2022年，8月28日if(len==1){gh=newlinknode;gh->tag=0;gh->node.data=*s;gh->link=NULL;}else{gh=newlinknode;gh->tag=1;p=gh;s++;strncpy(subs,s,len-2);subs[len-2]='\0';}第五十一頁(yè)，共六十頁(yè)，2022年，8月28日

do{Disastr(subs,hstr);r=CreateGL(hstr); p->node.sublist=r; q=p; len=strlen(subs); if(len>0) {p=newlinknode;p->tag=1; q->link=p; }}while(len>0);q->link=NULL;}returngh;

}

創(chuàng)建廣義表算法的時(shí)間復(fù)雜度為O(n)。第五十二頁(yè)，共六十頁(yè)，2022年，8月28日

2．廣義表取頭算法若廣義表GL=（a1，a2，……，an），則head（GL）=a1。取表頭運(yùn)算的結(jié)果可以是原子，也可以是一個(gè)子表。例如，head（（a1，a2），（a3，a4，a5），a6）=（a1，a2）。Head(linknode*GL){ifGL->tag==1p=GL->hp;returnp;}第五十三頁(yè)，共六十頁(yè)，2022年，8月28日

3.廣義表取尾算法

若廣義表GL=（a1，a2，……，an），則tail（GL）=（a2，……，an）

。取表尾運(yùn)算的結(jié)果是取出除表頭以外的所有元素。例如，tail（（a1，a2），（a3，a4，a5），a6）=（（a3，a4，a5），a6）。

Tail(linknode*GL){ifGL->tag==1p=GL->tp;returnp;}第五十四頁(yè)，共六十頁(yè)，2022年，8月28日4.求廣義表深度算法intDepth(linknode*GL){intmax=0;while(GL!=NULL){if(GL->tag==0)//有子表{intdep=Depth(GL->sublit)if(dep>max)max=dep;}GL=GL->link;}returnmax+1;//非空表的深度是各元素的深度的最大值加1}求廣義表深度算法的時(shí)間復(fù)雜度為O(n)。第五十五頁(yè)，共六十頁(yè)，2022年，8月28日（1）

數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個(gè)數(shù)據(jù)元素有唯一的一組下標(biāo)來(lái)標(biāo)識(shí)，在數(shù)組上不太適宜做插入、刪除數(shù)據(jù)元素的操作。（2）二維數(shù)組中aij的地址為：

LOC(aij)=