《數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）》課件第05章

2023年11月28日1第5章多維數(shù)組和廣義表本章學(xué)習(xí)內(nèi)容

5.1多維數(shù)組5.2多維數(shù)組的存儲結(jié)構(gòu)5.3特殊矩陣及其壓縮存儲5.4稀疏矩陣5.5廣義表2023年11月28日25.1多維數(shù)組5.1.1多維數(shù)組的概念數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級語言程序設(shè)計中都設(shè)定了數(shù)組類型。在此，我們僅簡單地討論數(shù)組的邏輯結(jié)構(gòu)及其在計算機(jī)內(nèi)的存儲方式。1．一維數(shù)組一維數(shù)組可以看成是一個線性表或一個向量（第2章中已經(jīng)介紹），它在計算機(jī)內(nèi)是存放在一塊連續(xù)的存儲單元中，適合于隨機(jī)查找。這在第2章的線性表的順序存儲結(jié)構(gòu)中已經(jīng)介紹。2．二維數(shù)組二維數(shù)組可以看成是向量的推廣。例如，設(shè)A是一個有m行n列的二維數(shù)組，則A可以表示為：2023年11月28日3在此，可以將二維數(shù)組A看成是由m個行向量[X0，X1，…，Xm-1]T組成，其中，Xi=(ai0,ai1,…,ain-1)，0≤i≤m-1；也可以將二維數(shù)組A看成是由n個列向量[y0,y1,…,yn-1]組成，其中yi=(ai0,a1i,…,am-1i)，0≤i≤n-1。由此可知二維數(shù)組中的每一個元素最多可有兩個直接前驅(qū)和兩個直接后繼（邊界除外），故是一種典型的非線性結(jié)構(gòu)。3．多維數(shù)組同理，三維數(shù)組最多可有三個直接前驅(qū)和三個直接后繼，三維以上的數(shù)組可以作類似分析。因此，可以把三維以上的數(shù)組稱為多維數(shù)組，多維數(shù)組可有多個直接前驅(qū)和多個直接后繼，故多維數(shù)組是一種非線性結(jié)構(gòu)。5.1.2多維數(shù)組在計算機(jī)內(nèi)的存儲怎樣將多維數(shù)組中的元素存入到計算機(jī)內(nèi)存中呢？由于計算機(jī)內(nèi)存結(jié)構(gòu)是一維的（線性的），因此，用一維內(nèi)存存放多維數(shù)組就必須按某種次序?qū)?shù)組元素排成一個線性序列，然后將這個線性序列順序存放在存儲器中，具體實(shí)現(xiàn)方法在下一節(jié)中介紹。2023年11月28日45.2多維數(shù)組的存儲結(jié)構(gòu)由于數(shù)組是先定義后使用，且為靜態(tài)分配存儲單元，也就是說，一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)組元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動，即它們的邏輯結(jié)構(gòu)就固定下來了，不再發(fā)生變化。因此，采用順序存儲結(jié)構(gòu)表示數(shù)組是順理成章的事了。本章中，僅重點(diǎn)討論二維數(shù)組的存儲，三維及三維以上的數(shù)組（多維），可以作類似分析。多維數(shù)組的順序存儲有下面兩種形式：行優(yōu)先順序存儲和列優(yōu)先順序存儲。5.2.1行優(yōu)先順序1．存放規(guī)則行優(yōu)先順序也稱為低下標(biāo)優(yōu)先存儲，或左邊下標(biāo)優(yōu)先于右邊下標(biāo)。具體實(shí)現(xiàn)時，按行號從小到大的順序，先將第一行中元素按列號從小到大全部存放好，再存放第二行元素，第三行元素，依此類推……2023年11月28日5在BASIC語言、PASCAL語言、C/C++語言等高級語言程序設(shè)計中，都是按行優(yōu)先順序存放的。例如，對剛才的Am×n二維數(shù)組，可用如下形式存放到內(nèi)存中：a00，a01，…，a0n-1，a10，a11，...，a1n-1，…，am-10

，am-11，…，am-1n-1。即二維數(shù)組按行優(yōu)先存放到內(nèi)存后，變成了一個線性序列（線性表）。因此，可以得出多維數(shù)組按行優(yōu)先順序存放到內(nèi)存的規(guī)律：最左邊下標(biāo)變化最慢，最右邊下標(biāo)變化最快，右邊下標(biāo)變化一遍，與之相鄰的左邊下標(biāo)才變化一次。因此，在算法中，若用循環(huán)語句的嵌套來實(shí)現(xiàn)按行優(yōu)先順序存放，最左邊下標(biāo)可以看成是最外層循環(huán)，最右邊下標(biāo)可以看成是最內(nèi)層循環(huán)。2023年11月28日62．地址計算由于多維數(shù)組在內(nèi)存中排列成一個線性序列，因此，若知道第一個元素的內(nèi)存地址，如何求得其他元素的內(nèi)存地址呢？我們可以將它們的地址排列看成是一個等差數(shù)列，假設(shè)每個元素占d個字節(jié)，元素aij

的存儲地址應(yīng)為第一個元素的地址加上排在aij

前面的元素所占用的單元地址數(shù)，而aij

的前面有i行(0~i-1)共i×n個元素，而本行前面又有j個元素，故aij的前面一共有i×n+j個元素，設(shè)a00的內(nèi)存地址為LOC(a00)，則aij的內(nèi)存地址按等差數(shù)列計算為LOC(aij)=LOC(a00)+(i×n+j)×d。同理，三維數(shù)組Am×n×p按行優(yōu)先順序存放的地址計算公式為：LOC(aijk)=LOC(a000)+(i×n×p+j×p+k)×d。5.2.2列優(yōu)先順序1．存放規(guī)則列優(yōu)先順序也稱為高下標(biāo)優(yōu)先存儲，或右邊下標(biāo)優(yōu)先于左邊下標(biāo)。具體實(shí)現(xiàn)時，按列號從小到大的順序，先將第一列中的元素按行號從小到大的順序全部存放好，再存放第二列元素，第三列元素，依此類推……2023年11月28日7在FORTRAN語言程序設(shè)計中，數(shù)組是按列優(yōu)先順序存放的。例如，對前面提到的Am×n二維數(shù)組，可以按如下的形式存放到內(nèi)存中：a00，a10…，am-10，a01，a11，…，am-11，…，a0m-1，a1m-1，...，am-1n-1

。因此，二維數(shù)組按列優(yōu)先順序存放到內(nèi)存后，也變成了一個線性序列（線性表）。因此，可以得出多維數(shù)組按列優(yōu)先順序存放到內(nèi)存的規(guī)律：最右邊下標(biāo)變化最慢，最左邊下標(biāo)變化最快，左邊下標(biāo)變化一遍，與之相鄰的右邊下標(biāo)才變化一次。因此，在算法中，若用循環(huán)語句的嵌套來實(shí)現(xiàn)按列優(yōu)先順序存放，最右邊下標(biāo)可以看成是最外層循環(huán)，最左邊下標(biāo)可以看成是最內(nèi)層循環(huán)。2．地址計算同樣與行優(yōu)先順序存放類似，若知道第一個元素的內(nèi)存地址，則同樣可以求得按列優(yōu)先順序存放的某一元素aij的地址。對二維數(shù)組Am×n有：LOC(aij)=LOC(a00)+(j×m+i)×d對三維數(shù)組Am×n×p有：LOC(aijk)=LOC(a000)+(k×m×n+j×m+i)×d2023年11月28日85.3特殊矩陣及其壓縮存儲矩陣是一個二維數(shù)組，它是很多科學(xué)與工程計算問題中研究的數(shù)學(xué)對象。矩陣可以用行優(yōu)先順序或列優(yōu)先順序的方法順序存放到內(nèi)存中，但是，當(dāng)矩陣的階數(shù)很大時，將會占用較多的存儲單元。而當(dāng)里面的元素分布呈現(xiàn)某種規(guī)律時，這時，從節(jié)約存儲單元出發(fā)，可考慮若干元素共用一個存儲單元，即進(jìn)行壓縮存儲。所謂壓縮存儲是指：為多個值相同的元素只分配一個存儲空間，值為零的元素不分配空間?；蛘呃斫鉃椋簩⒍S數(shù)組（矩陣）壓縮到一個占用存儲單元數(shù)目較少的一維數(shù)組中。但是，在進(jìn)行壓縮存儲時，雖然節(jié)約了存儲單元，但怎樣在壓縮存儲后直接找到某元素呢？因此還必須給出壓縮前下標(biāo)（二維數(shù)組的行、列）和壓縮后（一維數(shù)組的下標(biāo)）下標(biāo)之間的變換公式，才能使壓縮存儲變得有意義。下面將分幾種情況的特殊矩陣來討論。2023年11月28日95.3.1特殊矩陣

1．對稱矩陣若一個n階方陣A中元素滿足下列條件：aij=aji

其中0≤i,j≤n-1，則稱A為對稱矩陣。例如，如圖5-1所示是一個3×3的對稱矩陣。圖5-1一個對稱矩陣2．三角矩陣（1）上三角矩陣即矩陣上三角部分元素是隨機(jī)的，而下三角部分元素全部相同（為某常數(shù)C或全為0），具體形式見圖5-2（a）。（2）下三角矩陣即矩陣的下三角部分元素是隨機(jī)的，而上三角部分元素全部相同（為某常數(shù)C或全為0），具體形式見圖5-2（b）。

（a）上三角矩陣（b）下三角矩陣圖5-2三角矩陣2023年11月28日103．對角矩陣若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。常見的對角矩陣有：三對角矩陣、五對角矩陣、七對角矩陣等。例如，如圖5-3所示為7×7的三對角矩陣（即有三條對角線上元素非0）。圖5-3一個7×7的三對角矩陣2023年11月28日115.3.2壓縮存儲在上面介紹的幾種特殊矩陣（對稱矩陣、上三角矩陣、下三角矩陣、三對角矩陣、多對角矩陣等）中，元素的分布有規(guī)律，從節(jié)省存儲單元的角度來考慮，可以進(jìn)行壓縮存儲，現(xiàn)討論如下：1．對稱矩陣若矩陣An

n是對稱的，對稱的兩個元素可以共用一個存儲單元，這樣，原來n階方陣需n2個存儲單元，若采用壓縮存儲，僅需n(n+1)/2個存儲單元，將近節(jié)約一半存儲單元，這就是實(shí)現(xiàn)壓縮的好處。但是，將n階對稱方陣壓縮存放到一個向量空間s[0]到中，我們怎樣找到s[k]與a[i][j]的一一對應(yīng)關(guān)系呢？使我們在s[k]中能直接找到a[i][j]。2023年11月28日12我們僅以行優(yōu)先順序存放且分兩種方式討論：（1）只存放下三角部分由于對稱矩陣關(guān)于主對角線對稱，故我們只需存放主對角線及主對角線以下的元素。這時，a[0][0]存入s[0]，a[1][0]存入s[1]，a[1][1]存入s[2]，…，a[n-1][n-1]存入中，具體過程參見圖5-4。（a）一個下三角矩陣01234567……-3-2-1a00a10a11a20a21a22a30a31……an-1n-3an-1n-2an-1n-1（b）下三角矩陣的壓縮存儲形式圖5-4對稱矩陣及用下三角壓縮存儲2023年11月28日13這時s[k]與a[i][j]的對應(yīng)關(guān)系為：

i(i+1)/2+j 當(dāng)i≥jk=j(j+1)/2+i 當(dāng)i<j上面的對應(yīng)關(guān)系讀者很容易推出：當(dāng)i≥j時，aij在下三角部分中，aij前面有i行，共有1+2+3+…+i個元素，而aij是第i行的第j個元素，即有k=1+2+3+…+i+j=i(i+1)/2+j。當(dāng)i<j時，aij在上三角部分中，但與aji對稱，故只需在下三角部分中找aij即可，故只需將i與j交換即可，即k=j(j+1)/2+i。（2）只存放上三角部分對于對稱矩陣，除了用下三角形式存放外，還可以用上三角形式存放，這時a[0][0]存入s[0]，a[0][1]存入s[1]，a[0][2]存入s[2]，…，a[0][n-1]存入s[n]，a[1][1]存入s[n+1]，…，a[n-1][n-1]存入s中，具體參見圖5-5。2023年11月28日14（a）一個上三角矩陣01234567……-3-2-1a00a01a02a03a04a05a06a07……an-2n-2an-2n-1an-1n-1（b）上三角矩陣的壓縮存儲形式圖5-5對稱矩陣及用上三角壓縮存儲這時s[k]與a[i][j]的對應(yīng)關(guān)系可以按下面的方法推出：當(dāng)i≤j時，aij在上三角部分中，前面的行號從0~i-1，共有i行，第0行有n個元素，第1行有n-1個元素，…，第i-1行有n-(i-1)個元素，因此，前面i行共有n+n-1+…+n-(i-1)=i*n-個元素，而aij是本行第j-i個元素，故k=i*n-+j-i。2023年11月28日15當(dāng)i>j時，由對稱關(guān)系，交換i與j即可。即有k=j*n-+i-j。故s[k]與a[i][j]的對應(yīng)關(guān)系為：

i*n-+j-i i≤jK= j*n-+i-j i>j2．三角矩陣（1）下三角矩陣下三角矩陣的壓縮存放與對稱矩陣用下三角形式存放類似，但必須多一個存儲單元存放上三角部分元素，使用的存儲單元數(shù)目為n(n+1)/2+1。故可以將n

n的下三角矩陣壓縮存放到只有n(n+1)/2+1個存儲單元的向量中。假設(shè)仍按行優(yōu)先存放，這時s[k]與a[i][j]的對應(yīng)關(guān)系為：

i(i+1)/2+j i≥jk= n(n+1)/2 i<j2023年11月28日16（2）上三角矩陣和下三角矩陣的存儲類似，共需n(n+1)/2+1個存儲單元，假設(shè)仍按行優(yōu)先順序存放，這時s[k]與a[i][j]的對應(yīng)關(guān)系為：

i*n-i(i-1)/2+j-i i≤jk=n(n+1)/2 i>j3．對角矩陣我們僅討論三對角矩陣的壓縮存儲。五對角矩陣、七對角矩陣等，讀者可以作類似分析。在一個n

n的三對角矩陣中，只有n+n-1+n-1個非零元，故只需3n-2個存儲單元即可，零元已不占用存儲單元。故可將n

n三對角矩陣An

n壓縮存放到只有3n-2個存儲單元的s[3n-2]向量中，假設(shè)仍按行優(yōu)先順序存放，則s[k]與a[i][j]的對應(yīng)關(guān)系為： 3i-1 i=j+1k= 3i i=j或k=2i+j 3i+1 i=j-12023年11月28日175.4稀疏矩陣在上節(jié)提到的特殊矩陣中，元素的分布呈現(xiàn)某種規(guī)律，故一定能找到一種合適的方法，將它們進(jìn)行壓縮存放。但是，在實(shí)際應(yīng)用中，我們還經(jīng)常會遇到一類矩陣：其矩陣階數(shù)很大，非零元個數(shù)較少，零元很多，但非零元的排列（分布）沒有一定規(guī)律，我們稱這一類矩陣為稀疏矩陣。按照壓縮存儲的概念，要存放稀疏矩陣的元素，由于沒有某種規(guī)律，除存放非零元的值外，還必須存儲適當(dāng)?shù)妮o助信息（行、列號），才能迅速確定一個非零元是矩陣中的哪一個位置上的元素。下面將介紹稀疏矩陣的幾種存儲方法及一些算法的實(shí)現(xiàn)。5.4.1稀疏矩陣的存儲1．三元組表在壓縮存放稀疏矩陣的非零元同時，若還存放此非零元所在的行號和列號，則稱為三元組表法，即稱稀疏矩陣可用三元組表進(jìn)行壓縮存儲，但它是一種順序存儲（按行優(yōu)先順序存放）。一個非零元有行號、列號、值，為一個三元組，整個稀疏矩陣中非零元的三元組合起來稱為三元組表。2023年11月28日18此時，數(shù)據(jù)類型可描述如下：#include<iostream.h>constintmaxsize=100; //定義非零元的最大數(shù)目classnode //定義一個三元組

{public:inti,j; //非零元行、列號

intv; //非零元值};classsparmatrix //定義稀疏矩陣{public:introws,cols; //稀疏矩陣行、列數(shù)

intterms; //稀疏矩陣非零元個數(shù)

nodedata[maxsize]; //三元組表};2023年11月28日19圖5-6和圖5-7給出了兩個稀疏矩陣。

圖5-6稀疏矩陣M圖5-7稀疏矩陣N（M的轉(zhuǎn)置）2023年11月28日20稀疏矩陣M和N的三元組表見圖5-8。圖5-8稀疏矩陣M和N的三元組表2023年11月28日212．帶行指針的鏈表把具有相同行號的非零元用一個單鏈表連接起來，稀疏矩陣中的若干行組成若干個單鏈表，合起來稱為帶行指針的鏈表。例如，圖5-6所示的稀疏矩陣M的帶行指針的鏈表描述形式見圖5-9。圖5-9帶行指針的鏈表2023年11月28日223．十字鏈表當(dāng)稀疏矩陣中非零元的位置或個數(shù)經(jīng)常變動時，三元組就不適合作稀疏矩陣的存儲結(jié)構(gòu)了，此時采用鏈表作為存儲結(jié)構(gòu)更為恰當(dāng)。十字鏈表為稀疏矩陣中的鏈接存儲中的一種較好的存儲方法，在該方法中，每一個非零元用一個結(jié)點(diǎn)表示，結(jié)點(diǎn)中除了表示非零元所在的行、列和值的三元組(i,j,v)外，還需增加兩個鏈域：行指針域（rptr），用來指向本行中下一個非零元素；列指針域（cptr），用來指向本列中下一個非零元素。稀疏矩陣中同一行的非零元通過向右的rptr指針鏈接成一個帶表頭結(jié)點(diǎn)的循環(huán)鏈表。同一列的非零元也通過cptr指針鏈接成一個帶表頭結(jié)點(diǎn)的循環(huán)鏈表。因此，每個非零元既是第i行循環(huán)鏈表中的一個結(jié)點(diǎn)，又是第j列循環(huán)鏈表中的一個結(jié)點(diǎn)，相當(dāng)于處在一個十字交叉路口，故稱鏈表為十字鏈表。另外，為了運(yùn)算方便，我們規(guī)定行、列循環(huán)鏈表的表頭結(jié)點(diǎn)和表示非零元的結(jié)點(diǎn)一樣，也定為五個域，且規(guī)定行、列、域值為0，并且將所有的行、列鏈表和頭結(jié)點(diǎn)一起鏈成一個循環(huán)鏈表。2023年11月28日23在行（列）表頭結(jié)點(diǎn)中，行、列域的值都為0，故兩組表頭結(jié)點(diǎn)可以共用，即第i行鏈表和第i列鏈表共用一個表頭結(jié)點(diǎn)，這些表頭結(jié)點(diǎn)本身又可以通過V域（非零元值域，但在表頭結(jié)點(diǎn)中為next，指向下一個表頭結(jié)點(diǎn)）相鏈接。另外，再增加一個附加結(jié)點(diǎn)（由指針hm指示，行、列域分別為稀疏矩陣的行、列數(shù)目），附加結(jié)點(diǎn)指向第一個表頭結(jié)點(diǎn)，則整個十字鏈表可由hm指針惟一確定。例如，圖5-6的稀疏矩陣M的十字鏈表描述形式見圖5-10。十字鏈表的數(shù)據(jù)類型描述如下：classlinknode{public:inti,j; //行、列號linknode*cptr,*rptr; //列、行指針unionvnext //定義一個共用體{intv; //表結(jié)點(diǎn)使用v域,表示非零元值linknode*next; //表頭結(jié)點(diǎn)使用next域指向下一個表頭}k;…… //成員函數(shù)的說明及定義

}；2023年11月28日24圖5-10稀疏矩陣的十字鏈表2023年11月28日255.4.2稀疏矩陣的運(yùn)算1．稀疏矩陣的轉(zhuǎn)置運(yùn)算下面將討論三元組表上如何實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置運(yùn)算。轉(zhuǎn)置是矩陣中最簡單的一種運(yùn)算。對于一個m

n的矩陣A，它的轉(zhuǎn)置矩陣B是一個n

m的，且B[i][j]=A[j][i]，0≤i<n,0≤j<m。例如，圖5-6給出的M矩陣和圖5-7給出的N矩陣互為轉(zhuǎn)置矩陣。在三元組表表示的稀疏矩陣中，怎樣求得它的轉(zhuǎn)置呢?從轉(zhuǎn)置的性質(zhì)知道，將A轉(zhuǎn)置為B，就是將A的三元組表a.data變?yōu)锽的三元組表b.data，這時可以將a.data中i和j的值互換，則得到的b.data是一個按列優(yōu)先順序排列的三元組表，再將它的順序適當(dāng)調(diào)整，變成行優(yōu)先排列，即得到轉(zhuǎn)置矩陣B。下面將用兩種方法處理：（1）按照A的列序進(jìn)行轉(zhuǎn)置由于A的列即為B的行，在a.data中，按列掃描，則得到的b.data必按行優(yōu)先存放。但為了找到A的每一列中所有的非零的元素，每次都必須從頭到尾掃描A的三元組表（有多少列，則掃描多少遍），這時算法描述如下：2023年11月28日26classnode //定義一個三元組

{public:inti,j; //非零元行、列號intv; //非零元值};a,sparmatrixb); //快速轉(zhuǎn)置};classsparmatrix //定義稀疏矩陣{public:introws,cols; //稀疏矩陣行、列數(shù)intterms; //稀疏矩陣非零元個數(shù)nodedata[maxsize]; //三元組表voidtranspose(sparmatrixa,sparmatrixb); //轉(zhuǎn)置voidfastrans(sparmatrix2023年11月28日27voidsparmatrix::transpose(sparmatrixa,sparmatrixb){b.rows=a.cols;b.cols=a.rows;b.terms=a.terms;if(b.terms>0){intbno=0;for(intcol=0;col<a.cols;col++) //按列號掃描

for(intano=0;ano<a.terms;ano++) //對三元組表掃描

if(a.data[ano].j==col) //進(jìn)行轉(zhuǎn)置

{b.data[bno].j=a.data[ano].i;b.data[bno].i=a.data[ano].j;b.data[bno].v=a.data[ano].v;bno++;}}for(inti=0;i<a.terms;i++) //輸出轉(zhuǎn)置后的三元組結(jié)果

cout<<b.data[i].i<<""<<b.data[i].j<<""<<b.data[i].v<<endl;}2023年11月28日28voidmain(){sparmatrixa,b;cin>>a.rows>>a.cols>>a.terms; //輸入稀疏矩陣的行、列數(shù)及非零元的個數(shù)

for(inti=0;i<a.terms;i++)cin>>a.data[i].i>>a.data[i].j>>a.data[i].v; //輸入轉(zhuǎn)置前的稀疏矩陣的三元組

for(i=0;i<a.terms;i++)cout<<a.data[i].i<<""<<a.data[i].j<<""<<a.data[i].v<<endl; //輸出轉(zhuǎn)置前的三元組結(jié)果

a.transpose(a,b); //調(diào)用轉(zhuǎn)置算法}分析這個算法，主要工作在col和ano二重循環(huán)上，故算法的時間復(fù)雜度為O(a.cols*a.terms)。而通常的m×n階矩陣轉(zhuǎn)置算法可描述為：for(col=0;col<n;col++)for(row=0;row<m;row++)b[col][row]=a[row][col];2023年11月28日29它的時間復(fù)雜度為O(m×n)。而一般的稀疏矩陣中非零元個數(shù)a.terms遠(yuǎn)大于行數(shù)m，故壓縮存儲時，進(jìn)行轉(zhuǎn)置運(yùn)算，雖然節(jié)省了存儲單元，但增大了時間復(fù)雜度，故此算法僅適應(yīng)于a.terns<<a.rows

a.cols的情形。（2）按照A的行序進(jìn)行轉(zhuǎn)置即按a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組放入b中恰當(dāng)?shù)奈恢?。若能在轉(zhuǎn)置前求出矩陣A的每一列col（即B中每一行）的第一個非零元轉(zhuǎn)置后在b.data中的正確位置pot[col]（0≤col<a.cols），那么在對a.data的三元組依次作轉(zhuǎn)置時，只要將三元組按列號col放置到b.data[pot[col]]中，之后將pot[col]內(nèi)容加1，以指示第col列的下一個非零元的正確位置。為了求得位置向量pot，只要先求出A的每一列中非零元個數(shù)num[col]，然后利用下面公式：pot[0]=0pot[col]=pot[col-1]+num[col-1]當(dāng)1≤col<a.cols2023年11月28日30為了節(jié)省存儲單元，記錄每一列非零元個數(shù)的向量num可直接放入pot中，即上面的式子可以改為：pot[col]=pot[col-1]+pot[col]，其中1≤col<a.cols。于是可用上面公式進(jìn)行迭代，依次求出其他列的第一個非零元素轉(zhuǎn)置后在b.data中的位置pot[col]。例如，對前面圖5-6給出的稀疏矩陣M，有：每一列的非零元個數(shù)為pot[1]=2第0列非零元個數(shù)pot[2]=2第1列非零元個數(shù)pot[3]=2第2列非零元個數(shù)pot[4]=1第3列非零元個數(shù)pot[5]=0第4列非零元個數(shù)pot[6]=1第5列非零元個數(shù)pot[7]=0第6列非零元個數(shù)2023年11月28日31每一列的第一個非零元的位置為pot[0]=0 第0列第一個非零元位置pot[1]=pot[0]+pot[1]=2 第1列第一個非零元位置pot[2]=pot[1]+pot[2]=4 第2列第一個非零元位置pot[3]=pot[2]+pot[3]=6 第3列第一個非零元位置pot[4]=pot[3]+pot[4]=7 第4列第一個非零元位置pot[5]=pot[4]+pot[5]=7 第5列第一個非零元位置pot[6]=pot[5]+pot[6]=8 第6列第一個非零元位置則M稀疏矩陣的轉(zhuǎn)置矩陣N的三元組表很容易寫出（見圖5-8），算法描述如下：voidsparmatrix::fastrans(sparmatrixa,sparmatrixb){intpot[100],col,ano,bno;b.rows=a.cols;b.cols=a.rows;b.terms=a.terms;2023年11月28日32if(b.terms>0){for(col=0;col<a.cols;col++)pot[col]=0;for(intt=0;t<a.terms;t++)//求出每一列的非零元個數(shù)

{col=a.data[t].j;pot[col+1]=pot[col+1]+1;}pot[0]=0;for(col=1;col<a.cols;col++) //求出每一列的第一個非零元在轉(zhuǎn)置后的位置

pot[col]=pot[col-1]+pot[col];for(ano=0;ano<a.terms;ano++)//轉(zhuǎn)置

{col=a.data[ano].j;bno=pot[col];b.data[bno].j=a.data[ano].i;b.data[bno].i=a.data[ano].j;b.data[bno].v=a.data[ano].v;pot[col]=pot[col]+1;}}for(inti=0;i<a.terms;i++)cout<<b.data[i].i<<""<<b.data[i].j<<""<<b.data[i].v<<endl;//輸出轉(zhuǎn)置后的三元組

}2023年11月28日33voidmain(){sparmatrixa,b;cin>>a.rows>>a.cols>>a.terms;//輸入稀疏矩陣的行、列數(shù)及非零元的個數(shù)

for(inti=0;i<a.terms;i++)cin>>a.data[i].i>>a.data[i].j>>a.data[i].v; //輸入轉(zhuǎn)置前的三元組

for(i=0;i<a.terms;i++)cout<<a.data[i].i<<""<<a.data[i].j<<""<<a.data[i].v<<endl;//輸出轉(zhuǎn)置前的三元組

a.fastrans(a,b); //調(diào)用快速轉(zhuǎn)置算法}該算法比按列轉(zhuǎn)置多用了輔助向量空間pot，但它的時間為四個單循環(huán)，故總的時間復(fù)雜度為O(a.cols+a.terms)，比按列轉(zhuǎn)置算法效率要高。2023年11月28日342．稀疏矩陣的相加運(yùn)算當(dāng)稀疏矩陣用三元組表進(jìn)行相加時，有可能出現(xiàn)非零元素的位置變動，這時候，不宜采用三元組表作存儲結(jié)構(gòu)，而應(yīng)該采用十字鏈表較方便(為描述方便，假設(shè)稀疏矩陣的行列下標(biāo)從1開始而非0)。（1）十字鏈表的建立下面分兩步討論十字鏈表的建立算法：第一步，建立表頭的循環(huán)鏈表：依次輸入矩陣的行、列數(shù)和非零元素個數(shù)：m,n和t。由于行、列鏈表共享一組表頭結(jié)點(diǎn)，因此，表頭結(jié)點(diǎn)的個數(shù)應(yīng)該是矩陣中行、列數(shù)中較大的一個。假設(shè)用s表示個數(shù)，即s=max（m，n）。依次建立總表頭結(jié)點(diǎn)（由hm指針指向）和s個行、列表頭結(jié)點(diǎn)，并使用next域使s+1個頭結(jié)點(diǎn)組成一個循環(huán)鏈表，總表頭結(jié)點(diǎn)的行、列域分別為稀疏矩陣的行、列數(shù)目，s個表頭結(jié)點(diǎn)的行列域分別為0。并且開始時，每一個行、列鏈表均是一個空的循環(huán)鏈表，即s個行、列表頭結(jié)點(diǎn)中的行、列指針域rptr和cptr均指向頭結(jié)點(diǎn)本身。2023年11月28日35第二步，生成表中結(jié)點(diǎn)：依次輸入t個非零元素的三元組（i,j,v），生成一個結(jié)點(diǎn)，并將它插入到第i行鏈表和第j列鏈表中的正確位置上，使第i個行鏈表和第j個列鏈表變成一個非空的循環(huán)鏈表。算法描述如下：classlinknode{public:inti,j;unionvnext{intv;linknode*next;}k;linknode*rptr,*cptr;linknode*creatlindmat();};2023年11月28日36linknode*linknode::creatlindmat()linknode*creatlindmat(){intm,n,t,s,i,j,k;linknode*p,*q,*cp[100],*hm;//cp[100]中的100表示矩陣的行、列數(shù)不超過100cout<<"請輸入稀疏矩陣的行、列數(shù)及非零元個數(shù)"<<endl;cin>>m>>n>>t;if(m>m)s=m;elses=n;hm=newlinknode;hm->i=m;hm->j=n;cp[0]=hm;for(i=1;i<=s;i++){p=newlinknode;p->i=0;p->j=0;p->rptr=p;p->cptr=p;cp[i]=p;cp[i-1]->k.next=p;}2023年11月28日37cp[s]->k.next=hm;for(intx=1;x<=t;x++){cout<<"請輸入一個三元組(i,j,v)"<<endl; cin>>i>>j>>k; //輸入一個非零元的三元組p=newlinknode;p->i=i;p->j=j;p->k.v=k; //生成一個三元組的結(jié)點(diǎn)//以下是將p插入到第i行鏈表中q=cp[i];while((q->rptr!=cp[i])&&(q->rptr->j<j))q=q->rptr;p->rptr=q->rptr;q->rptr=p;//以下是將P插入到第j列鏈表中q=cp[j];while((q->cptr!=cp[j])&&(q->cptr->i<i))q=q->cptr;p->cptr=q->cptr;q->cptr=p;}returnhm;}2023年11月28日38voidmain(){linknode*p,*q,T;linknode*hm=NULL;hm=T.creatlindmat(); //生成十字鏈表p=hm->k.next;while(p->k.next!=hm) //輸出十字鏈表{q=p->rptr;while(q->rptr!=p) //輸出一行鏈表

{cout<<q->i<<""<<q->j<<""<<q->k.v<<"";q=q->rptr;}if(p!=q)cout<<q->i<<""<<q->j<<""<<q->k.v<<"";cout<<endl;p=p->k.next;}}在十字鏈表的建立算法中，建表頭結(jié)點(diǎn)，時間復(fù)雜度為O(s)，插入t個非零元結(jié)點(diǎn)到相應(yīng)的行、列鏈表的時間復(fù)雜度為O（t*s），故算法的總的時間復(fù)雜度為O(t*s)。2023年11月28日39（2）用十字鏈表實(shí)現(xiàn)稀疏矩陣相加運(yùn)算假設(shè)原來有兩個稀疏矩陣A和B，如何實(shí)現(xiàn)運(yùn)算A=A+B呢？假設(shè)原來A和B都用十字鏈表作存儲結(jié)構(gòu)，現(xiàn)要求將B中結(jié)點(diǎn)合并到A中，合并后的結(jié)果有三種可能：1）結(jié)果為aij+bij；2）aij（bij=0）；3）bij（aij=0）。由此可知當(dāng)將B加到A中去時，對A矩陣的十字鏈表來說，或者是改變結(jié)點(diǎn)的v域值（aij+bij≠0），或者不變（bij=0），或者插入一個新結(jié)點(diǎn)（aij=0），還可能是刪除一個結(jié)點(diǎn)（aij+bij=0）。于是整個運(yùn)算過程可以從矩陣的第一行起逐行進(jìn)行。對每一行都從行表頭出發(fā)分別找到A和B在該行中的第一個非零元結(jié)點(diǎn)后開始比較，然后按上述四種不同情況分別處理之。若pa和pb分別指向A和B的十字鏈表中行值相同的兩個結(jié)點(diǎn)，則4種情況描述為：1）pa->j=pb->j且pa->k.v+pb->k.v≠0，則只要將aij+bij的值送到pa所指結(jié)點(diǎn)的值域中即可，其他所有域的值都不變化。2023年11月28日402）pa->j=pb->j且pa->k.v+pb->k.v=0,則需要在A矩陣的鏈表中刪除pa所指的結(jié)點(diǎn)。這時，需改變同一行中前一結(jié)點(diǎn)的rptr域值，以及同一列中前一結(jié)點(diǎn)的cptr域值。3）pa->j<pb->j且pa->j≠0，則只要將pa指針往右推進(jìn)一步，并重新加以比較即可。4）pa->j>pb->j或pa->j=0，則需在A矩陣的鏈表中插入pb所指結(jié)點(diǎn)。另外，為了插入和刪除結(jié)點(diǎn)時方便，還需設(shè)立一些輔助指針。其一是，在A的行鏈表上設(shè)qa以指示pa所指結(jié)點(diǎn)的直接前驅(qū)；其二是，在A的每一列的列鏈表上設(shè)一個指針hl[j]，它的初值是指向每一列的列鏈表的表頭結(jié)點(diǎn)cp[j]。2023年11月28日41下面將對矩陣B加到矩陣A上面的操作過程大致描述如下:設(shè)ha和hb分別為表示矩陣A和B的十字鏈表的總表頭；ca和cb分別為指向A和B的行鏈表的表頭結(jié)點(diǎn)，其初始狀態(tài)為：ca=ha->k.next;cb=hb->k.next;pa和pb分別為指向A和B的鏈表中結(jié)點(diǎn)的指針。開始時，pa=ca->rptr;pb=cb->rptr;然后按下列步驟執(zhí)行：①當(dāng)ca->i=0時，重復(fù)執(zhí)行②、③、④步，否則，算法結(jié)束；②當(dāng)pb->j≠0時，重復(fù)執(zhí)行③步，否則轉(zhuǎn)第④步；③比較兩個結(jié)點(diǎn)的列序號，分三種情形：2023年11月28日42a．若pa->j<pb->j且pa->j≠0，則令pa指向本行下一結(jié)點(diǎn)，即qa=pa;pa=pa->rptr;轉(zhuǎn)②步;b．若pa->j>pb->j或pa->j=0，則需在A中插入一個結(jié)點(diǎn)。假設(shè)新結(jié)點(diǎn)的地址為P，則A的行表中指針變化為：qa->rptr=p;p->rptr=pa;同樣，A的列表中指針也應(yīng)作相應(yīng)改變，用hl[j]指向本列中上一個結(jié)點(diǎn)，則A的列表中指針變化為：p->cptr=hl[j]->cptr;hl[j]->cptr=p;轉(zhuǎn)第②步；c．若pa->j=pb->j，則將B的值加上去，即pa->k.v=pa->k.v+bp->k.v，此時若pa->k.v≠0，則指針不變，否則，刪除A中該結(jié)點(diǎn)，于是行表中指針變?yōu)椋簈a->rptr=pa->rptr;同時，為了改變列表中的指針，需要先找同列中上一個結(jié)點(diǎn)，用hl[j]表示，然后令hl[j]->cptr=pa->cptr，轉(zhuǎn)第②步。④一行中元素處理完畢后，按著處理下一行，指針變化為：ca=ca->k.next;cb=cb->k.next;轉(zhuǎn)第1)步。2023年11月28日43稀疏矩陣十字鏈表相加算法如下：//假設(shè)ha為A稀疏矩陣十字鏈表的頭指針，hb為B稀疏矩陣十字鏈表的頭指針classlinknode{public:inti,j;unionvnext{intv;linknode*next;}k;linknode*rptr,*cptr;linknode*creatlindmat();linknode*matadd(linknode*ha,linknode*hb)};linknode*linknode::creatlindmat(){……//前面已有}2023年11月28日44linknode*linknode::matadd(linknode*ha,linknode*hb){linknode*pa,*pb,*qa,*ca,*cb,*p,*q;linknode*hl[100];inti,j,n;if((ha->i!=hb->i)||(ha->j!=hb->j))cout<<"矩陣不匹配,不能相加"<<endl;else{p=ha->k.next;n=ha->j;for(i=1;i<=n;i++){hl[i]=p;p=p->k.next;}ca=ha->k.next;cb=hb->k.next;while(ca->i==0){pa=ca->rptr;pb=cb->rptr;qa=ca;2023年11月28日45while(pb->j!=0){if((pa->j<pb->j)&&(pa->j!=0)){qa=pa;pa=pa->rptr;}elseif((pa->j>pb->j)||(pa->j==0)) //插入一個結(jié)點(diǎn){p=newlinknode;p->i=pb->i;p->j=pb->j;p->k.v=pb->k.v;qa->rptr=p;p->rptr=pa;qa=p;pb=pb->rptr;j=p->j;q=hl[j]->cptr;while((q->i<p->i)&&(q->i!=0)){hl[j]=q;q=hl[j]->cptr;}hl[j]->cptr=p;p->cptr=q;hl[j]=p;}else{pa->k.v=pa->k.v+pb->k.v;if(pa->k.v==0) //刪除一個結(jié)點(diǎn){qa->rptr=pa->rptr;j=pa->j;q=hl[j]->cptr;2023年11月28日46while(q->i<pa->i){hl[j]=q;q=hl[j]->cptr;}hl[j]->cptr=q->cptr;pa=pa->rptr;pb=pb->rptr;deleteq;}else{qa=pa;pa=pa->rptr;pb=pb->rptr;}}}ca=ca->k.next;cb=cb->k.next;}}returnha;}2023年11月28日47voidprint(linknode*ha) //輸出十字鏈表{linknode*p,*q,*r;p=ha->k.next;r=p;while(p->k.next!=r){q=p->rptr;while(q->rptr!=p){cout<<q->i<<""<<q->j<<""<<q->k.v<<"";q=q->rptr;}if(p!=q)cout<<q->i<<""<<q->j<<""<<q->k.v<<"";cout<<endl;p=p->k.next;}}2023年11月28日48voidmain(){linknodeT1,T2;linknode*ha=NULL,*hb=NULL,*hc=NULL;ha=T1.creatlindmat(); //生成一個十字鏈表hahb=T2.creatlindmat(); //生成另一個十字鏈表hbprint(ha);cout<<endl; //輸出十字鏈表haprint(hb);cout<<endl; //輸出十字鏈表hbhc=T1.matadd(ha,hb); //十字鏈表相加print(hc);cout<<endl; //輸出相加后的結(jié)果}通過算法分析可知，進(jìn)行比較、修改指針?biāo)璧臅r間是一個常數(shù)，整個運(yùn)算過程在于對A和B的十字鏈表逐行掃描，其循環(huán)次數(shù)主要取決于A和B的矩陣中非零元個數(shù)na和nb，故算法的時間復(fù)雜度為O(na+nb)。2023年11月28日495.5廣義表5.5.1基本概念廣義表是第2章提到的線性表的推廣。線性表中的元素僅限于原子項，即不可以再分，而廣義表中的元素既可以是原子項，也可以是子表（另一個線性表）。1．廣義表的定義廣義表是n≥0個元素a1，a2，…，an的有限序列，其中每一個ai或者是原子，或者是一個子表。廣義表通常記為LS=(a1,a2,…,an)，其中LS為廣義表的名字，n為廣義表的長度，每一個ai為廣義表的元素。但在習(xí)慣中，一般用大寫字母表示廣義表，小寫字母表示原子。下面我們將給出廣義表的一些例子及表示方法。2023年11月28日502．廣義表舉例（1）F=()，F(xiàn)為空表，長度為0。（2）G=(a,（b,c）)，G是長度為2的廣義表，第一項為原子，第二項為子表。（3）H=(x,y,z)，H是長度為3的廣義表，每一項都是原子。（4）D=(B,C)，D是長度為2的廣義表，每一項都是上面提到的子表。（5）E=(a,E)，是長度為2的廣義表，第一項為原子，第二項為它本身。3．廣義表的表示方法（1）用LS=(a1，a2，…，an)形式，其中每一個ai為原子或廣義表例如：A=(b,c)B=(a,A)C=(A,B)都是廣義表。2023年11月28日51（2）將廣義表中所有子表寫到原子形式，并利用圓括號嵌套例如，上面提到的廣義表A、B、C可以描述為：A(b,c)B(a,A(b,c))C(A(b,c),B(a,A(b,c)))（3）將廣義表用樹和圖來描述上面提到的廣義表A、B、C的描述見圖5-11。

（a）A=(b,c)（b）B=(a,A)（c）C=(A,B)

圖5-11廣義表用樹或圖來表示2023年11月28日524．廣義表的深度一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。5．廣義表的分類（1）線性表：元素全部是原子的廣義表。（2）純表：與樹對應(yīng)的廣義表，見圖5-11的(a)和(b)。（3）再入表：與圖對應(yīng)的廣義表(允許結(jié)點(diǎn)共享)，見圖5-11的(c)。（4）遞歸表：允許有遞歸關(guān)系的廣義表，例如E=(a,E)。這四種表的關(guān)系滿足：遞歸表

再入表

純表

線性表2023年11月28日535.5.2存儲結(jié)構(gòu)由于廣義表的元素類型不一定相同，因此，難以用順序結(jié)構(gòu)存儲表中元素，通常采用鏈接存儲方法來存儲廣義表中元素，并稱之為廣義鏈表。常見的表示方法有：1．單鏈表表示法即模仿線性表的單鏈表結(jié)構(gòu)，每個原子結(jié)點(diǎn)只有一個鏈域link，結(jié)點(diǎn)結(jié)構(gòu)是：其中atom是標(biāo)志域，若為0，則表示為子表，若為1，則表示為原子，data/slink域用來存放原子值或子表的指針，link存放下一個元素的地址。2023年11月28日54數(shù)據(jù)類型描述如下：classnode{public:intatom;node*link;union{node*slink;elemtypedata;}ds;}例如，設(shè)L=(a,b)A=(x,L)=(x,(a,b))B=(A,y)=((x,(a,b)),y)C=(A,B)=((x,(a,b)),((x,(a,b)),y))可用如圖5-12的結(jié)構(gòu)描述廣義表C，設(shè)頭指針為hc。2023年11月28日55圖5-12廣義表的單鏈表表示法2023年11月28日56用此方法存儲有兩個缺點(diǎn)：其一，在某一個表(或子表)中開始處插入或刪除一個結(jié)點(diǎn)，修改的指針較多，耗費(fèi)大量時間；其二，刪除一個子表后，它的空間不能很好地回收。2．雙鏈表表示法每個結(jié)點(diǎn)含有兩個指針及一個數(shù)據(jù)域，每個結(jié)點(diǎn)的結(jié)構(gòu)如下：其中，link1指向該結(jié)點(diǎn)