數(shù)據(jù)結(jié)構(gòu)描述電子教案

數(shù)據(jù)結(jié)構(gòu)描述電子教案第1頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.5廣義表5.1多維數(shù)組5.2多維數(shù)組的存儲(chǔ)結(jié)構(gòu)5.3特殊矩陣及其壓縮存儲(chǔ)5.4稀疏矩陣退出目錄第2頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.1多維數(shù)組5.1.1多維數(shù)組的概念

1．一維數(shù)組一維數(shù)組可以看成是一個(gè)線性表或一個(gè)向量（第二章已經(jīng)介紹），它在計(jì)算機(jī)內(nèi)是存放在一塊連續(xù)的存儲(chǔ)單元中，適合于隨機(jī)查找。這在第二章的線性表的順序存儲(chǔ)結(jié)構(gòu)中已經(jīng)介紹。2．二維數(shù)組二維數(shù)組可以看成是向量的推廣。第3頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月例如，設(shè)A是一個(gè)有m行n列的二維數(shù)組，則A可以表示為：在此，可以將二維數(shù)組A看成是由m個(gè)行向量[X0，X1，…，Xm-1]T組成，其中，Xi=(ai0,ai1,….,ain-1)，0≤i≤m-1；也可以將二維數(shù)組A看成是由n個(gè)列向量[y0,y1,……,yn-1]組成，其中yi=(a0i,a1i,…..,am-1i)，0≤i≤n-1。第4頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月由此可知二維數(shù)組中的每一個(gè)元素最多可有二個(gè)直接前驅(qū)和兩個(gè)直接后繼（邊界除外），故是一種典型的非線性結(jié)構(gòu)。3．多維數(shù)組同理，三維數(shù)組最多可有三個(gè)直接前驅(qū)和三個(gè)直接后繼，三維以上數(shù)組可以作類(lèi)似分析。因此，可以把三維以上的數(shù)組稱(chēng)為多維數(shù)組，多維數(shù)組可有多個(gè)直接前驅(qū)和多個(gè)直接后繼，故多維數(shù)組是一種非線性結(jié)構(gòu)。第5頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.1.2多維數(shù)組在計(jì)算機(jī)內(nèi)的存放怎樣將多維數(shù)組中元素存入到計(jì)算機(jī)內(nèi)存中呢？由于計(jì)算機(jī)內(nèi)存結(jié)構(gòu)是一維的（線性的），因此，用一維內(nèi)存存放多維數(shù)組就必須按某種次序?qū)?shù)組元素排成一個(gè)線性序列，然后將這個(gè)線性序列順序存放在存儲(chǔ)器中5.2多維數(shù)組的存儲(chǔ)結(jié)構(gòu)由于數(shù)組一般不作插入或刪除操作，也就是說(shuō)，一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)組元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)，即它們的邏輯結(jié)構(gòu)就固定下來(lái)了，不再發(fā)生變化。因此，采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組是順理成章的事了。本章中，僅重點(diǎn)討論二維數(shù)組的存儲(chǔ)，三維及三維以上的數(shù)組可以作類(lèi)似分析。第6頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月多維數(shù)組的順序存儲(chǔ)有兩種形式：5.2.1行優(yōu)先順序1．存放規(guī)則行優(yōu)先順序也稱(chēng)為低下標(biāo)優(yōu)先或左邊下標(biāo)優(yōu)先于右邊下標(biāo)。具體實(shí)現(xiàn)時(shí)，按行號(hào)從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，依次類(lèi)推……在BASIC語(yǔ)言、PASCAL語(yǔ)言、C/C++語(yǔ)言等高級(jí)語(yǔ)言程序設(shè)計(jì)中，都是按行優(yōu)先順序存放的。例如，對(duì)剛才的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)存后，變成了一個(gè)線性序列（線性表）。第7頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月因此，可以得出多維數(shù)組按行優(yōu)先存放到內(nèi)存的規(guī)律：最左邊下標(biāo)變化最慢，最右邊下標(biāo)變化最快，右邊下標(biāo)變化一遍，與之相鄰的左邊下標(biāo)才變化一次。因此，在算法中，最左邊下標(biāo)可以看成是外循環(huán)，最右邊下標(biāo)可以看成是最內(nèi)循環(huán)。2．地址計(jì)算由于多維數(shù)組在內(nèi)存中排列成一個(gè)線性序列，因此，若知道第一個(gè)元素的內(nèi)存地址，如何求得其它元素的內(nèi)存地址？我們可以將它們的地址排列看成是一個(gè)等差數(shù)列，假設(shè)每個(gè)元素占l個(gè)字節(jié)，元素aij的存儲(chǔ)地址應(yīng)為第一個(gè)元素的地址加上排在aij前面的元素所占用的單元數(shù)，而aij的前面有i行(0~i-1)共i×n個(gè)元素，而本行前面又有j個(gè)元素，故aij的前面一共有i×n+j個(gè)元素，設(shè)a00的內(nèi)存地址為L(zhǎng)OC(a00)，則aij的內(nèi)存地址按等差數(shù)列計(jì)算為L(zhǎng)OC(aij)=LOC(a00)+（i×n+j）×l。同理，三維數(shù)組Am×n×p按行優(yōu)先存放的地址計(jì)算公式為：LOC(aijk)=LOC(a000)+(i×n×p+j×p+k)×l。第8頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.2.2列優(yōu)先順序1．存放規(guī)則列優(yōu)先順序也稱(chēng)為高下標(biāo)優(yōu)先或右邊下標(biāo)優(yōu)先于左邊下標(biāo)。具體實(shí)現(xiàn)時(shí)，按列號(hào)從小到大的順序，先將第一列中元素全部存放好，再存放第二列元素，第三列元素，依次類(lèi)推……在FORTRAN語(yǔ)言程序設(shè)計(jì)中，數(shù)組是按列優(yōu)先順序存放的。例如，對(duì)前面提到的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)存后，也變成了一個(gè)線性序列（線性表）。第9頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月因此，可以得出多維數(shù)組按列優(yōu)先存放到內(nèi)存的規(guī)律：最右邊下標(biāo)變化最慢，最左邊下標(biāo)變化最快，左邊下標(biāo)變化一遍，與之相鄰的右邊下標(biāo)才變化一次。因此，在算法中，最右邊下標(biāo)可以看成是外循環(huán)，最左邊下標(biāo)可以看成是最內(nèi)循環(huán)。2．地址計(jì)算同樣與行優(yōu)先存放類(lèi)似，若知道第一個(gè)元素的內(nèi)存地址，則同樣可以求得按列優(yōu)存放的某一元素aij的地址。對(duì)二維數(shù)組有：LOC(aij)=LOC(a00)+(j×m+i)×l對(duì)三維數(shù)組有：LOC(aijk)=LOC(a000)+(k×m×n+j×m+i)×l第10頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.3特殊矩陣及其壓縮存儲(chǔ)5.3.1特殊矩陣

若一個(gè)n階方陣A中元素滿足下列條件：aij=aji其中0≤i,j≤n-1，則稱(chēng)A為對(duì)稱(chēng)矩陣。例如，圖5-1是一個(gè)3*3的對(duì)稱(chēng)矩陣。1．對(duì)稱(chēng)矩陣第11頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月2．三角矩陣（1）上三角矩陣即矩陣上三角部分元素是隨機(jī)的，而下三角部分元素全部相同（為某常數(shù)C）或全為0，具體形式見(jiàn)圖5-2(a)。（2）下三角矩陣即矩陣的下三角部分元素是隨機(jī)的，而上三角部分元素全部相同（為某常數(shù)C）或全為0，具體形式見(jiàn)圖5-2(b)。第12頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月3．對(duì)角矩陣若矩陣中所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱(chēng)為對(duì)角矩陣。常見(jiàn)的有三對(duì)角矩陣、五對(duì)角矩陣、七對(duì)角矩陣等。例如，圖5-3為77的三對(duì)角矩陣（即有三條對(duì)角線上元素非0）。第13頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.3.2壓縮存儲(chǔ)1．對(duì)稱(chēng)矩陣若矩陣Ann是對(duì)稱(chēng)的，對(duì)稱(chēng)的兩個(gè)元素可以共用一個(gè)存儲(chǔ)單元，這樣，原來(lái)n階方陣需n2個(gè)存儲(chǔ)單元，若采用壓縮存儲(chǔ)，僅需n(n+1)/2個(gè)存貯單元，將近節(jié)約一半存貯單元，這就是實(shí)現(xiàn)壓縮的好處。但是，將n階對(duì)稱(chēng)方陣存放到一個(gè)向量空間s[0]到s[-1]中，我們?cè)鯓诱业絪[k]與a[i][j]的一一對(duì)稱(chēng)應(yīng)關(guān)系呢？使我們?cè)趕[k]中直接找到a[i][j]。我們僅以行優(yōu)先存放分兩種方式討論：第14頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月（1）只存放下三角部分由于對(duì)稱(chēng)矩陣關(guān)于主對(duì)角線對(duì)稱(chēng)，故我們只需存放主對(duì)角線及主對(duì)角線以下的元素。這時(shí)，a[0][0]存入s[0]，a[1][0]存入s[1]，a[1][1]存入s[2]，…，具體參見(jiàn)圖5-4。這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i(i+1)/2+j當(dāng)i≥jk=j(j+1)/2+i當(dāng)i<j上面的對(duì)應(yīng)關(guān)系讀者很容易推出：當(dāng)i≥j時(shí)，aij在下三角部分中，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在上三角部分中，但與aji對(duì)稱(chēng)，故只需在下三角部分中找aij即可，故只需將i與j交換即可，即k=j(j+1)/2+i。第15頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月第16頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月(2)只存放上三角部分對(duì)于對(duì)稱(chēng)陣，除了用下三角形式存放外，還可以用上三角形式存放，這時(shí)a[0][0]存入s[0],a[0][1]存入s[1]，a[0][2]存入s[2]，…，具體參見(jiàn)圖5-5。這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系可以按下面方法推出：當(dāng)i≤j時(shí)，aij在上三角部分中，前面共有i行，共有n+n-1+…+n-(i-1)=i*n-個(gè)元素，而aij是本行第j-i個(gè)元素，故k=i*n-+j-i，當(dāng)i>j時(shí)，交換i與j即可。故s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i*n-+j-i當(dāng)i≤jk=j*n-+i-j當(dāng)i>j第17頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月第18頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月2．三角矩陣（1）下三角矩陣下三角矩陣的壓縮存放與對(duì)稱(chēng)矩陣用下三角形式存放類(lèi)似，但必須多一個(gè)存儲(chǔ)單元存放上三角部分元素，使用的存儲(chǔ)單元數(shù)目為n(n+1)/2+1。故可以將nn的下三角矩陣壓縮存放到只有n(n+1)/2+1個(gè)存儲(chǔ)單元的向量中，假設(shè)仍按行優(yōu)先存放，這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i(i+1)/2+ji≥jk=n(n+1)/2i<j第19頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月(2)上三角矩陣和下三角矩陣的存儲(chǔ)類(lèi)似，共需n(n+1)/2+1個(gè)存貯單元，假設(shè)仍按行優(yōu)先順序存放，這時(shí)s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：i*n-i(i-1)/2+j-i當(dāng)i≤jk=n(n+1)/2i>j第20頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月3．對(duì)角矩陣我們僅討論三對(duì)角矩陣的壓縮存貯，五對(duì)角矩陣，七對(duì)角矩陣等讀者可以作類(lèi)似分析。在一個(gè)nn的三對(duì)角矩陣中，只有n+n-1+n-1個(gè)非零元素，故只需3n-2個(gè)存儲(chǔ)單元即可，零元已不占用存儲(chǔ)單元。故可將nn三對(duì)角矩陣A壓縮存放到只有3n-2個(gè)存儲(chǔ)單元的s向量中，假設(shè)仍按行優(yōu)先順序存放，則：s[k]與a[i][j]的對(duì)應(yīng)關(guān)系為：3i-1當(dāng)i=j+1k=3i當(dāng)i=j3i+1當(dāng)i=j-1第21頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.4稀疏矩陣在上節(jié)提到的特殊矩陣中，元素的分布呈現(xiàn)某種規(guī)律，故一定能找到一種合適的方法，將它們進(jìn)行壓縮存放。但是，在實(shí)際應(yīng)用中，我們還經(jīng)常會(huì)遇到一類(lèi)矩陣：其矩陣階數(shù)很大，非零元個(gè)數(shù)較少，零元很多，但非零元的排列沒(méi)有一定規(guī)律，我們稱(chēng)這一類(lèi)矩陣為稀疏矩陣。按照壓縮存儲(chǔ)的概念，要存放稀疏矩陣的元素，由于沒(méi)有某種規(guī)律，除存放非零元的值外，還必須存貯適當(dāng)?shù)妮o助信息，才能迅速確定一個(gè)非零元是矩陣中的哪一個(gè)位置上的元素。下面將介紹稀疏矩陣的幾種存儲(chǔ)方法及一些算法的實(shí)現(xiàn)。第22頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.4.1稀疏矩陣的存儲(chǔ)1．三元組表在壓縮存放稀疏矩陣的非零元同時(shí)，若還存放此非零元所在的行號(hào)和列號(hào)，則稱(chēng)為三元組表法，即稱(chēng)稀疏矩陣可用三元組表進(jìn)行壓縮存儲(chǔ)，但它是一種順序存貯（按行優(yōu)先順序存放）。一個(gè)非零元有行號(hào)、列號(hào)、值，為一個(gè)三元組，整個(gè)稀疏矩陣中非零元的三元組合起來(lái)稱(chēng)為三元組表。第23頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月此時(shí)，數(shù)據(jù)類(lèi)型可描述如下：constintmaxsize=100;//定義非零元的最大數(shù)目structnode//定義一個(gè)三元組{inti,j;//非零元行、列號(hào)intv;//非零元值};structsparmatrix//定義稀疏矩陣{introws,cols;//稀疏矩陣行、列數(shù)intterms;//稀疏矩陣非零元個(gè)數(shù)nodedata[maxsize];//三元組表};第24頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月稀疏矩陣M和N的三元組表見(jiàn)圖5-8。第25頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月2．帶行指針的鏈表把具有相同行號(hào)的非零元用一個(gè)單鏈表連接起來(lái)，稀疏矩陣中的若干行組成若干個(gè)單鏈表，合起來(lái)稱(chēng)為帶行指針的鏈表。例如，圖5-6的稀疏矩陣M的帶行指針的鏈表描述形式見(jiàn)圖5-9。第26頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月3．十字鏈表當(dāng)稀疏矩陣中非零元的位置或個(gè)數(shù)經(jīng)常變動(dòng)時(shí)，三元組就不適合于作稀疏矩陣的存儲(chǔ)結(jié)構(gòu)，此時(shí)，采用鏈表作為存儲(chǔ)結(jié)構(gòu)更為恰當(dāng)。十字鏈表為稀疏矩陣中的鏈接存儲(chǔ)中的一種較好的存儲(chǔ)方法，在該方法中，每一個(gè)非零元用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)中除了表示非零元所在的行、列和值的三元組(i,j,v)外，還需增加兩個(gè)鏈域：行指針域(rptr)，用來(lái)指向本行中下一個(gè)非零元素；列指針域(cptr)，用來(lái)指向本列中下一個(gè)非零元素。稀疏矩陣中同一行的非零元通過(guò)向右的rptr指針鏈接成一個(gè)帶表頭結(jié)點(diǎn)的循環(huán)鏈表。同一列的非零元也通過(guò)cptr指針鏈接成一個(gè)帶表頭結(jié)點(diǎn)的循鏈鏈表。因此，每個(gè)非零元既是第i行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，又是第j列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，相當(dāng)于處在一個(gè)十字交叉路口，故稱(chēng)鏈表為十字鏈表。第27頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月另外，為了運(yùn)算方便，我們規(guī)定行、列循環(huán)鏈表的表頭結(jié)點(diǎn)和表示非零元的結(jié)點(diǎn)一樣，也定為五個(gè)域，且規(guī)定行、列、域值為0，并且將所有的行、列鏈表和頭結(jié)點(diǎn)一起鏈成一個(gè)循環(huán)鏈表。在行(列)表頭結(jié)點(diǎn)中，行、列域的值都為0，故兩組表頭結(jié)點(diǎn)可以共用，即第i行鏈表和第i列鏈表共用一個(gè)表頭結(jié)點(diǎn)，這些表頭結(jié)點(diǎn)本身又可以通過(guò)V域(非零元值域，但在表頭結(jié)點(diǎn)中為next，指向下一個(gè)表頭結(jié)點(diǎn))相鏈接。另外，再增加一個(gè)附加結(jié)點(diǎn)(由指針hm指示，行、列域分別為稀疏矩陣的行、列數(shù)目)，附加結(jié)點(diǎn)指向第一個(gè)表頭結(jié)點(diǎn)，則整個(gè)十字鏈表可由hm指針唯一確定。第28頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月十字鏈表的數(shù)據(jù)類(lèi)型描述如下：structlinknode{inti,j;linknode*cptr,*rptr;unionvnext//定義一個(gè)共用體{intv;//表結(jié)點(diǎn)使用V域,表示非零元值linknode*next;//表頭結(jié)點(diǎn)使用next域}k;}例如，圖5-6的稀疏矩陣M的十字鏈表描述形式見(jiàn)圖5-10。第29頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月第30頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.4.2稀疏矩陣的運(yùn)算1．稀疏矩陣的轉(zhuǎn)置運(yùn)算轉(zhuǎn)置是矩陣中最簡(jiǎn)單的一種運(yùn)算。對(duì)于一個(gè)mn的矩陣A，它的轉(zhuǎn)置B是一個(gè)nm的，且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，這時(shí)可以將a.data中i和j的值互換，則得到的b.data是一個(gè)按列優(yōu)先順序排列的三元組表，再將它的順序適當(dāng)調(diào)整，變成行優(yōu)先排列，即得到轉(zhuǎn)置矩陣B。下面將用兩種方法處理：第31頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月（1）按照A的列序進(jìn)行轉(zhuǎn)置由于A的列即為B的行，在a.data中，按列掃描，則得到的b.data必按行優(yōu)先存放。但為了找到A的每一列中所有的非零的元素，每次都必須從頭到尾掃描A的三元組表(有多少列，則掃描多少遍)，這時(shí)算法描述如下：第32頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月voidtranspose(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++)//按列號(hào)掃描for(intano=0;ano<a.terms;ano++)//對(duì)三元組表掃描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++;}}}第33頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月分析這個(gè)算法，主要工作在col和ano二重循環(huán)上，故算法的時(shí)間復(fù)雜度為O(a.cols*a.terms)。而通常的mn階矩陣轉(zhuǎn)置算法可描述為：for(col=0;col<n;col++)for(row=0;row<m;row++)b[col][row]=a[row][col];它的時(shí)間復(fù)雜度為o(mn)。而一般的稀疏矩陣中非零元個(gè)數(shù)a.terms遠(yuǎn)大于行數(shù)m，故壓縮存貯時(shí)，進(jìn)行轉(zhuǎn)置運(yùn)算，雖然節(jié)省了存貯單元，但增大了時(shí)間復(fù)雜度，故此算法僅適應(yīng)于a.terns<<a.rowsa.cols的情形。第34頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月（2）按照A的行序進(jìn)行轉(zhuǎn)置即按a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組放入b中恰當(dāng)?shù)奈恢?。若能在轉(zhuǎn)置前求出矩陣A的每一列col(即B中每一行)的第一個(gè)非零元轉(zhuǎn)置后在b.data中的正確位置pot[col](0≤col<a.cols)，那么在對(duì)a.data的三元組依次作轉(zhuǎn)置時(shí)，只要將三元組按列號(hào)col放置到b.data[pot[col]]中，之后將pot[col]內(nèi)容加1，以指示第col列的下一個(gè)非零元的正確位置。為了求得位置向量pot，只要先求出A的每一列中非零元個(gè)數(shù)num[col]，然后利用下面公式：pot[0]=0

pot[col]=pot[col-1]+num[col-1]當(dāng)1≤col<a.cols第35頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月算法描述如下：voidfastrans(sparmatrixa,sparmatrixb){intpot[100],col,ano,bno;b.rows=a.cols;b.cols=a.rows;b.terms=a.terms;if(b.terms>0){for(col=0;col<a.cols;col++)pot[col]=0;for(intt=0;t<a.terms;t++)//求出每一列的非零元個(gè)數(shù) {col=a.data[t].j; pot[col+1]=pot[col+1]++;} pot[0]=0; for(col=1;col<a.cols;col++)//求出每一列的第一個(gè)非零元在轉(zhuǎn)置后的位置 pot[col]=pot[col-1]+pot[col];第36頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月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;}}}該算法比按列轉(zhuǎn)置多用了輔助向量空間pot，但它的時(shí)間為四個(gè)單循環(huán)，故總的時(shí)間復(fù)雜度為O(a.cols+a.terms)，比按列轉(zhuǎn)置算法效率要高。第37頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月2．稀疏矩陣的相加運(yùn)算當(dāng)稀疏矩陣用三元組表進(jìn)行相加時(shí)，有可能出現(xiàn)非零元素的位置變動(dòng)，這時(shí)候，不宜采用三元組表作存儲(chǔ)結(jié)構(gòu)，而應(yīng)該采用十字鏈表較方便。第38頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.5廣義表5.5.1基本概念廣義表是第二章提到的線性表的推廣。線性表中的元素僅限于原子項(xiàng)，即不可以再分，而廣義表中的元素既可以是原子項(xiàng)，也可以是子表(另一個(gè)線性表)。1．廣義表的定義廣義表是n≥0個(gè)元素a1，a2，…，an的有限序列，其中每一個(gè)ai或者是原子，或者是一個(gè)子表。廣義表通常記為L(zhǎng)S=(a1,a2,…,an)，其中LS為廣義表的名字，n為廣義表的長(zhǎng)度，每一個(gè)ai為廣義表的元素。但在習(xí)慣中，一般用大寫(xiě)字母表示廣義表，小寫(xiě)字母表示原子。第39頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月2．廣義表舉例(1)A=(),A為空表，長(zhǎng)度為0。(2)B=(a,（b,c）),B是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為子表。(3)C=(x,y,z)C是長(zhǎng)度為3的廣義表，每一項(xiàng)都是原子。D=(B,C)，D是長(zhǎng)度為2的廣義表，每一項(xiàng)都是上面提到的子表。E=(a,E)是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。

第40頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月3．廣義表的表示方法(1)用LS=(a1，a2，…，an)形式，其中每一個(gè)ai為原子或廣義表例如：A=(b,c)B=(a,A)E=(a,E)都是廣義表。（2）將廣義表中所有子表寫(xiě)到原子形式，并利用圓括號(hào)嵌套例如，上面提到的廣義表A、B、C可以描述為：A(b,c)B(a,A(b,c))E(a,E(a,E（…）))第41頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月(3)將廣義表用樹(shù)和圖來(lái)描述上面提到的廣義表A、B、C的描述見(jiàn)圖5-11。第42頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月4．廣義表的深度一個(gè)廣義表的深度是指該廣義表展開(kāi)后所含括號(hào)的層數(shù)。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。5．廣義表的分類(lèi)（1）線性表：元素全部是原子的廣義表。（2）純表：與樹(shù)對(duì)應(yīng)的廣義表，見(jiàn)圖5-11的(a)和(b)。（3）再入表:與圖對(duì)應(yīng)的廣義表(允許結(jié)點(diǎn)共享)，見(jiàn)圖5-11的(c)。（4）遞歸表：允許有遞歸關(guān)系的廣義表，例如E=(a,E)。第43頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月這四種表的關(guān)系滿足：遞歸表再入表純表線性表5.5.2存儲(chǔ)結(jié)構(gòu)由于廣義表的元素類(lèi)型不一定相同，因此，難以用順序結(jié)構(gòu)存儲(chǔ)表中元素，通常采用鏈接存儲(chǔ)方法來(lái)存儲(chǔ)廣義表中元素，并稱(chēng)之為廣義鏈表。常見(jiàn)的表示方法有：1．單鏈表表示法即模仿線性表的單鏈表結(jié)構(gòu)，每個(gè)原子結(jié)點(diǎn)只有一個(gè)鏈域link，結(jié)點(diǎn)結(jié)構(gòu)是：第44頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月可用如圖5-12的結(jié)構(gòu)描述廣義表C=(A,B)=((x,(a,b)),((x,(a,b)),y))，設(shè)頭指針為hc。第45頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月2．雙鏈表表示法每個(gè)結(jié)點(diǎn)含有兩個(gè)指針及一個(gè)數(shù)據(jù)域，每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)如下：例如，對(duì)圖5-12用單鏈表表示的廣義表C，可用圖5-13的雙鏈表方法表示。第46頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月5.5.3基本運(yùn)算廣義表有許多運(yùn)算，現(xiàn)僅介紹如下幾種：1.求廣義表的深度depth(LS)假設(shè)廣義表以剛才的單鏈表表示法作存儲(chǔ)結(jié)構(gòu)，則它的深度可以遞歸求出。即廣義表的深度等于它的所有子表的最大深度加1，設(shè)dep表示任一子表的深度，max表示所有子表中表的最大深度，則廣義表的深度為：depth=max+1，算法描述如下：第47頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月intdepth(node*LS){intmax=0;while(LS!=NULL){if(LS->atom==0)//有子表{intdep=depth(LS->slink);if(dep>max)max=dep;}LS=LS->link;}returnmax+1;}該算法的時(shí)間復(fù)雜度為O(n)。第48頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月2.廣義表的建立creat(LS)假設(shè)廣義表以單鏈表的形式存儲(chǔ)，廣義表的元素類(lèi)型elemtype為字符型char，廣義表由鍵盤(pán)輸入，假定全部為字母，輸入格式為：元