數(shù)組和廣義表

1、關(guān)于數(shù)組與廣義表第一張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月第5章 數(shù)組與廣義表 本章主要內(nèi)容一、數(shù)組的存儲(chǔ)結(jié)構(gòu)及其地址變換二、特殊矩陣的壓縮存儲(chǔ)及其地址變換三、稀疏矩陣的存儲(chǔ)結(jié)構(gòu)與算法四、廣義表的存儲(chǔ)結(jié)構(gòu)與算法第二張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月5.1 數(shù)組 數(shù)組是線性表的直接推廣 。如果線性表的元素又是具有相同數(shù)據(jù)類型的線性表，這種線性表就是二維數(shù)組，若在二維數(shù)組中，元素還是線性表，即得到三維數(shù)組，依次類推可以得到n維數(shù)組。 本節(jié)主要討論數(shù)組的有關(guān)概念、存儲(chǔ)結(jié)構(gòu)及地址變換。 第三張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月511 數(shù)組類型與存儲(chǔ)結(jié)構(gòu)一、二維數(shù)組 一個(gè)m行n列的二維

2、數(shù)組如下表所示： 第四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月數(shù)組類型與存儲(chǔ)結(jié)構(gòu) 令i =（ai1，ai2，ai,n）(i=1,2,m) ，每行作為一個(gè)元素，則A=(1 ,2 ,m) 是一個(gè)元素為線性表的線性表。若令j = (a1j，a2j，am j)T (j=1,2,n),每列作為一個(gè)元素，則A=(1,2,n)也是一個(gè)元素為線性表的線性表?；谶@一原因，而把數(shù)組看成是線性表的推廣。 第五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月數(shù)組類型與存儲(chǔ)結(jié)構(gòu) 數(shù)組是一個(gè)具有固定格式、固定個(gè)數(shù)的數(shù)據(jù)元素構(gòu)成的有序集合，每一個(gè)數(shù)據(jù)元素有唯一的一對(duì)下標(biāo)標(biāo)識(shí)（i，j），因此，在數(shù)組中不能做插入、刪除操作。在高

3、級(jí)語(yǔ)言中，數(shù)組一旦被定義，每一維的下標(biāo)上下界都不能改變。對(duì)數(shù)組可以施加的操作主要有以下兩種：（1）取值操作：給定下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。（2）賦值操作：給定下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。 第六張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月數(shù)組類型與存儲(chǔ)結(jié)構(gòu) 由含n個(gè)下標(biāo)（0jibi1，i=1,2,n）且具有相同類型的 個(gè)數(shù)據(jù)元素構(gòu)成的集合稱為一個(gè)n維數(shù)組，bi稱為第i維的長(zhǎng)度。數(shù)組中的每個(gè)元素對(duì)應(yīng)于一組下標(biāo)（ ），受到n個(gè)關(guān)系的約束。固定n-1個(gè)下標(biāo)，讓另一個(gè)下標(biāo)變換就是一個(gè)一維數(shù)組。在n個(gè)關(guān)系中，對(duì)于任意元素（0jibi2）都有一個(gè)直接后繼。n維數(shù)組的ADT定義。 只包含4種操作： I

4、nitArray(&A，n，b1，b2，,bn)：初始化數(shù)組。 DestroyArray(&A)：撤銷數(shù)組。 Value(A，&e，j1，j2，jn)。取某個(gè)數(shù)據(jù)元素的值 Assign(&A，e，j1，j2，jn)：為數(shù)據(jù)元素賦值。 第七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象一、二維數(shù)組的存儲(chǔ)結(jié)構(gòu)及地址變換1、以行為主序順序存儲(chǔ)。用一塊連續(xù)存儲(chǔ)空間逐行順序存儲(chǔ)數(shù)組元素。例如：一個(gè)mn數(shù)組按行存儲(chǔ)表示如下圖： 第八張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象2、以列為主序順序存儲(chǔ)。用連續(xù)存儲(chǔ)空間逐列順序存儲(chǔ)數(shù)組元素。例如：mn數(shù)組按列順序存儲(chǔ)，如下圖所示：第九張，P

5、PT共八十五頁(yè)，創(chuàng)作于2022年6月512 數(shù)組的內(nèi)存映象3、地址變換設(shè)二維數(shù)組Amn順序存儲(chǔ)在連續(xù)區(qū)域中，基地址為L(zhǎng)OC(a11)，每個(gè)數(shù)組元素占據(jù)L個(gè)地址單元，現(xiàn)在考察由元素aij的下標(biāo)求其存儲(chǔ)地址的計(jì)算公式為：對(duì)于“以行為主序”的存儲(chǔ)方式，因?yàn)閿?shù)組元素aij的前面有i-1行，每一行有n個(gè)元素?cái)?shù)，在第i行中，它的前面還有j-1個(gè)元素，所以有： LOC(aij) = LOC(a11) + ( (i-1)n + j-1 )L 。在C語(yǔ)言中，對(duì)數(shù)組的每一維下標(biāo)，規(guī)定下界從0開(kāi)始，所以可改為：LOC(aij) = LOC(a00) + ( in + j )L。第十張，PPT共八十五頁(yè)，創(chuàng)作于202

6、2年6月數(shù)組的內(nèi)存映象對(duì)于“以列為主序”的存儲(chǔ)方式，數(shù)組元素aij的前面有j-1列，每一列有m個(gè)元素?cái)?shù)，在第j列中，它的前面還有i-1個(gè)元素，所以有： LOC(aij) = LOC(a11) + ( (j-1)m + i-1 )L。當(dāng)下界從0開(kāi)始是，應(yīng)改為：LOC(aij) = LOC(a00) + ( jm + i )L。對(duì)一般的二維數(shù)組，設(shè)數(shù)組Ac1.d1 c2.d2，下標(biāo)的上、下界可以是任何整數(shù)，則aij的物理地址計(jì)算公式為：行主序：LOC(aij)=LOC(a c1 c2)+( (i- c1)( d2 - c2 + 1)+ (j- c2) )L。列主序：LOC(aij)=LOC(a c

7、1 c2)+( (j- c2)( d1 c1 + 1)+ (i- c1) )L。 第十一張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象二、n維數(shù)組 LOC( )=LOC( )+(d2-c2+1)(d3-c3+1)(dn-cn+1)(j1-c1 )+(d3-c3+1)(d4-c4+1)(dn-cn+1)(j2-c2) +(dn-cn+1)jn-1-cn-1) + (jn-cn )L= LOC( ) + ( )L例如：三維數(shù)組Amnp，元素aijk其物理地址為：LOC(aijk)=LOC(a111)+( ( i-1)np+ (j-1)p +k-1)L 第十二張，PPT共八十五頁(yè)，創(chuàng)作于2

8、022年6月數(shù)組的內(nèi)存映象舉例。若矩陣Amn 中存在某個(gè)元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫一個(gè)算法，找出A中的所有鞍點(diǎn)。解決此問(wèn)題的基本思想是：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，否則不輸出，接著處理下一行。設(shè)矩陣A用一個(gè)二維數(shù)組表示。 第十三張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象算法如下：void saddle (int A ,int m, int n) / m,n是矩陣A的行數(shù)和列數(shù) int i,j,min; for (i=0;im;i+) / 按行處理 mi

9、n=Ai0; for (j=1; jn; j+) if (Aijmin ) min=Aij; k=j; / 找第i行最小值 for (p=0;papk; p+) / 檢測(cè)該行中的每一個(gè)最小值是否是鞍點(diǎn) if ( p=m) printf (%d,%d,%dn, i ,k,min); / if /for/ 第十四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月5.2 特殊矩陣的壓縮存儲(chǔ)521 對(duì)稱矩陣一、對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣：n階方陣中，若aij=aji，其中1i,jn，則稱該矩陣為對(duì)稱矩陣。如下圖所示的矩陣是一個(gè)階對(duì)稱矩陣。第十五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月特殊矩陣的壓縮存儲(chǔ)對(duì)稱矩

10、陣的元素關(guān)于主對(duì)角線對(duì)稱，因此只需存儲(chǔ)上三角或下三角部分即可。例如：上圖（a）給出的5階對(duì)稱矩陣存儲(chǔ)到一個(gè)一維數(shù)組如下圖（b）所示。第十六張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月對(duì)稱矩陣的壓縮存儲(chǔ)將一個(gè)對(duì)稱矩陣只存儲(chǔ)下三角（或上三角）部分的元素aij，此時(shí)有ji且1in，對(duì)于上三角部分的元素aij和它對(duì)應(yīng)的aji相等，因此當(dāng)訪問(wèn)的元素在上三角時(shí)，直接去訪問(wèn)與其對(duì)應(yīng)的下三角元素即可。這樣，原來(lái)需要n2個(gè)存儲(chǔ)單元，現(xiàn)在只需要 個(gè)，可節(jié)約 個(gè)存儲(chǔ)單元。第十七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月對(duì)稱矩陣的壓縮存儲(chǔ)采用以行為主序的方法順序存儲(chǔ)到一個(gè)一維數(shù)組中。因?yàn)橄氯侵泄灿袀€(gè) 元素，設(shè)存儲(chǔ)結(jié)構(gòu)

11、為一維數(shù)組。A ，如下圖所示。 第十八張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月對(duì)稱矩陣的壓縮存儲(chǔ)二、地址變換設(shè)矩陣的下三角部分的元素aij，下標(biāo)滿足條件：ij且1in，存儲(chǔ)到一維數(shù)組A的第k個(gè)元素Ak中， 則有： 第十九張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月522 三角矩陣一、下三角矩陣的壓縮存儲(chǔ)形如下圖所示的矩陣稱為下三角矩陣。主對(duì)角線上方所有元素等于同一個(gè)常數(shù)C。第二十張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月一、下三角矩陣的壓縮存儲(chǔ)下三角矩陣的壓縮存儲(chǔ)與對(duì)稱矩陣的壓縮存儲(chǔ)類似。例如：下圖所給給出一個(gè)下三角矩陣存儲(chǔ)結(jié)構(gòu)。第二十一張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月下三角矩陣的壓

12、縮存儲(chǔ)下三角矩陣壓縮存儲(chǔ)的地址變換用一維數(shù)組A 。存儲(chǔ)下三角矩陣。如下圖所示： 設(shè)aji 存放在Ak中，則k與i、j的對(duì)應(yīng)關(guān)系有如下公式：當(dāng)ij時(shí)， k= 當(dāng)ij 時(shí)第二十四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月523 帶狀矩陣n階矩陣A稱為帶狀矩陣，如果存在最小正數(shù)m，滿足當(dāng)i-jm時(shí)，aij =0，這時(shí)稱w=2n-1為矩陣A的帶寬。例如下圖是一個(gè)w=3(m=2)的帶狀矩陣。 第二十五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶狀矩陣帶狀矩陣A采用壓縮存儲(chǔ)有兩種方法。第一種方法：將A壓縮到一個(gè)n行w列的二維數(shù)組B中，如下圖所示。當(dāng)某行非零元素的個(gè)數(shù)小于帶寬w時(shí)，先存放非零元素然后補(bǔ)零。第

13、二十六張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶狀矩陣另一種壓縮方法是將帶狀矩陣壓縮到一維數(shù)組中去，按以行為主序存儲(chǔ)，順序存放非零元素，如下圖所示，按此規(guī)律，可得到相應(yīng)的映象函數(shù)。如當(dāng)w=3時(shí)，映象函數(shù)為：k=2（i-1)+j-1 第二十七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月5.3 稀疏矩陣當(dāng)m*n矩陣中有t個(gè)非零元素且tm*n時(shí)，這樣的矩陣稱為稀疏矩陣。 稀疏矩陣壓縮存儲(chǔ)方法是僅存放非零元素。由于非零元素分布沒(méi)有規(guī)律，為了能找到相應(yīng)的元素，所以僅存儲(chǔ)非零元素的值是不夠的，還必須記下它們所在的行號(hào)和列號(hào)。為此采取如下方法：將非零元素所在的行、列以及它的值構(gòu)成一個(gè)三元組（i,j,v），然

14、后將這些三元組按某種規(guī)律順序存儲(chǔ)，這種方法可以節(jié)約大量的存儲(chǔ)空間。 第二十八張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣稀疏矩陣的ADT定義對(duì)稀疏矩陣的操作只定義一下8種：創(chuàng)建稀疏矩陣。 CreareSMatrix（&M）撤銷稀疏矩陣。 DetroySMatrix（&M）輸出稀疏矩陣。 PrintSMatrix（M）復(fù)制稀疏矩陣。 CopySMatrix（M , &T）稀疏矩陣加法。 AddSMatrix（M , N , &T）稀疏矩陣減法。 SubtractSMatrix（M , N , &T）稀疏矩陣乘法。MultSMatrix（M , N , &T）稀疏矩陣轉(zhuǎn)置。 Transpos

15、eSMatrix（M , &T）第二十九張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月531 稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法一、稀疏矩陣的三元組存儲(chǔ)表示 將稀疏矩陣每個(gè)非0元素的值以及行下標(biāo)、列下標(biāo)構(gòu)成的三元組按行優(yōu)先順序存儲(chǔ)，同一行中列號(hào)按從小到大排列成一個(gè)線性表，稱這種存儲(chǔ)方法為三元組表示。例如，設(shè)稀疏矩陣如下圖 (a)所示，對(duì)應(yīng)的三元組存儲(chǔ)結(jié)構(gòu)如圖 (b)所示。 第三十張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法存儲(chǔ)結(jié)構(gòu)的定義：define MAXSIZE 1024 / 非0元素的個(gè)數(shù)數(shù)typedef struct / 定義三元組元素結(jié)構(gòu) int i , j;

16、 / 非零元素的行號(hào)和列號(hào) ElemType e ; / 非零元素的值 Triple ; / 三元組類型typedef struct SPNode dataMAXSIZE+1; / 三元組順序表int mu , nu , tu ; / 矩陣的行、列及非零元素的個(gè)數(shù) TSMatrix ; / 三元組表的存儲(chǔ)類型 第三十一張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法二、稀疏矩陣的算法實(shí)現(xiàn)1矩陣的轉(zhuǎn)置設(shè)TSMatrix A表示一個(gè)mn的稀疏矩陣，其轉(zhuǎn)置TSMatrix B是一個(gè)nm的稀疏矩陣。轉(zhuǎn)置算法基本思想：A的行、列轉(zhuǎn)化成B的列、行；在A.data中依次找第一列的、

17、第二列的、直到最后一列，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B.data中。 第三十二張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法算法描述如下：void TransposeSMatrix ( TSMatrix A , TSMatrix &B) B.mu=A.nu; B.nu=A.mu; B.tu=A.tu ; / 復(fù)制行、列數(shù)及元素個(gè)數(shù) if ( B.tu ) / 有非零元素則轉(zhuǎn)換 q=1; for ( col = 1; col = A.nu ; col+ ) / 按A的列序轉(zhuǎn)換 for ( p=1; ptu0) return OK; / Transpos

18、eSMatrix 第三十三張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法算法性能分析。設(shè)m、n是原矩陣的行數(shù)和列數(shù)，t是稀疏矩陣的非零元素個(gè)數(shù)。該算法的時(shí)間主要耗費(fèi)在二重循環(huán)上，所以時(shí)間復(fù)雜性為O(n*t)。顯然當(dāng)非零元素的個(gè)數(shù)t和m*n同數(shù)量級(jí)時(shí)，算法的時(shí)間復(fù)雜度為O(m*n2)。與通常存儲(chǔ)方式下矩陣轉(zhuǎn)置算法相比，可能節(jié)約了一定量的存儲(chǔ)空間，但算法的時(shí)間性能更差一些。 第三十四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法2帶列邏輯連接的三元組順序存儲(chǔ)與改進(jìn)的轉(zhuǎn)置算法引入兩個(gè)向量：numn+1和cpotn+1，其中numcol表示矩陣A

19、中第col列的非零元素的個(gè)數(shù)（為了方便下標(biāo)均從1開(kāi)始），cpotcol的初始值表示矩陣A中的第col列的第一個(gè)非零元素在B.data中的位置。于是cpot的初始值為：cpot1=1；cpotcol=cpotcol-1+numcol-1； 2coln 第三十五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法例如。下圖（a）所給矩陣A的num和cpot的數(shù)組值如右圖所示。改進(jìn)的稀疏矩陣轉(zhuǎn)置算法稱為快速轉(zhuǎn)置。算法思想：依次掃描A.data，當(dāng)掃描到一個(gè)col列元素時(shí)，直接將其存放在B.data的cpotcol位置上，且cpotcol加，cpotcol中始終是下一個(gè)col列元

20、素在B.data中的位置。第三十六張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法快速轉(zhuǎn)置算法如下：Status FastTransposeSMatrix ( TSMatri x A , TSMatrix &B ) B.mu=A.nu ; B.nu=A.mu ; B.tu=A.tu ; / 稀疏矩陣的行、列及元素個(gè)數(shù) if ( B.tu0 ) / 有非零元素則轉(zhuǎn)換 for ( i = 1 ; i = A.nu ; i+ ) numi=0; for (i= 1 ; i = A.tu ; i+ ) / 求矩陣A中每一列非零元素的個(gè)數(shù) j = A.datai.j ; num

21、j+; cpot1 = 1 ; / 求矩陣A中每一列第一個(gè)非零元素在B.data中的位置for ( i = 2 ; i = A.nu ; i+ ) cpoti= cpoti-1+numi-1; for ( i =1; i = A.tu ; i+) / 掃描三元組表 j =A.datai.j ; / 當(dāng)前三元組的列號(hào) k = cpotj ; / 當(dāng)前三元組在B.data中的位置 B.datak.i = A.datai.j ; B.datak.j = A.datai.i ; B.datak.v = A.datai.v ;cpotj+; / for i / if (B.tu) return B; /

22、 返回的是轉(zhuǎn)置矩陣的指針 / FastTransposeSMatrix 第三十七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法算法的時(shí)間復(fù)雜度分析：上述算法中有四個(gè)循環(huán)，分別執(zhí)行n，t，n-1，t次，在每個(gè)循環(huán)中，每次迭代的時(shí)間是一個(gè)常量，因此總的計(jì)算量是O（n+t）。所需要的存儲(chǔ)空間比前一個(gè)算法多了兩個(gè)向量，空間復(fù)雜度為O（t）。 第三十八張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月2帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法已知稀疏矩陣A(m1 n1)和B(m2 n2)，求乘積C(m1 n2)。例如：稀疏矩陣A、B、C及它們對(duì)應(yīng)的三元組順序表A.data、B.data

23、、C.data如下圖 (a)和(b)所示。 第三十九張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法由矩陣乘法規(guī)則知：Ci，j=Ai,1B1,j+Ai,2B2,j+Ai,nBn,j =當(dāng)A的元素Ai,k的列號(hào)與B的元素Bk,p的行號(hào)相等時(shí)才能相乘，且當(dāng)兩項(xiàng)都不為零時(shí)，乘積中的這一項(xiàng)才不為零。為運(yùn)算方便設(shè)一個(gè)累加器：datatype tempn+1；用來(lái)存放當(dāng)前行中cij的值，當(dāng)前行中所有元素全部計(jì)算出之后，再存放到C.data中去。 第四十張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法為了便于在B.data中尋找B中的第k行的第

24、一個(gè)非零元素，與前面類似，引入numn和rpotn兩個(gè)向量。numk表示矩陣B中第k行的非零元素的個(gè)數(shù)；rpotk表示第k行的第一個(gè)非零元素在B.data中的位置。于是有：rpot1=1rpotk=rpotk-1+numk-1 2kn第四十一張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法例如，下圖（a）的矩陣B的其numn 和rpotn 的值如右邊的表所示。k1234num k 2020cpot k 1335第四十二張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法稀疏矩陣存儲(chǔ)結(jié)構(gòu)定義：# define MAXSIZE 1024

25、/ 稀疏矩陣非0元素最大個(gè)數(shù)# define MAXRC 100 / 稀疏矩陣的最大行數(shù)typedef struct / 定義帶行邏輯連接的三元組順序表類型 Triple data MAXSIZE+1 ; int rpotMAXRC+1 int mu , nu , tu ; RLSMatrix 稀疏矩陣乘法的算算步驟：初始化。清理一些單元，準(zhǔn)備按行順序存放乘積矩陣;求B的numn和rpotn數(shù)組值;做矩陣乘法。將A.data中三元組的列值與B.data中三元組的行值相等的非零元素相乘，并將具有相同下標(biāo)的乘積元素相加。第四十三張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲(chǔ)

26、與乘積算法稀疏矩陣乘法的算法描述：Status MatrixMultiply (RLSMatrix *A, RLSMatrix *B, RLSMatrix &C) / 求稀疏矩陣C=AB int p , q , i , j , k , r ; ElemType ctempn+1; int numB.nu+1; if (A.nu != B.mu) return ERROR ; / A的列與B的行不相等 C.mu = A.mu ; C.nu = B.nu ; C.tu = 0 ; if (A.tu*B.tu != 0 ) for ( i =1 ; i = B.mu ; i+ ) numi=0; /

27、 求矩陣B中每一行非零元素的個(gè)數(shù)for ( k =1 ; k = B.tu ; k+) i = B.datak.i ;numi+; rpot1=1; / 求矩陣B中每一行第一個(gè)非零元素在B.data中的位置for (i=2 ; i= B.mu ; i+ ) rpoti = rpoti-1 + numi-1 ;第四十四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法r = 0 ; / 當(dāng)前C中非零元素的個(gè)數(shù) p=1; / 指示A.data中當(dāng)前非零元素的位置 for ( i= 1; i= A.mu; i+) for ( j =1 ; j = B.nu ; j+)

28、tempj=0; / cij的累加器初始化 while (A.datap.i = = i ) / 求第i行的 k = A.datap.j; / A中當(dāng)前非零元的列號(hào) if (kB.mu) t = rpotk+1 ; else t = B.tu+1; / 確定B中第k行的非零元素在B.data中的下限位置 for (q = rpotk ; qt ; q+ ) / B中第k行的每一個(gè)非零元素 j = B.dataq.j ; tempj + = A.datap.e * B.dataq.e p+; / while for (j=1;jnu;j+) if (tempj ) r+; C.datar= i

29、, j , tempj ; /for iC.tu = r ; returnOK ; / MulSMatrix 第四十五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法算法的時(shí)間性能分析。求num的時(shí)間復(fù)雜度為O(B.nu+B.tu)；求rpot 時(shí)間復(fù)雜度為O(B.mu)；求temp時(shí)間復(fù)雜度為O(A.mu*B.nu)；求C的所有非零元素的時(shí)間復(fù)雜度為O(A.tu*B.tu / B.mu)；壓縮存儲(chǔ)時(shí)間復(fù)雜度為O(A.mu*B.nu)；所以總的時(shí)間復(fù)雜度為O(A.mu*B.nu+(A.tu*B.tu) / B.nu )。 第四十六張，PPT共八十五頁(yè)，創(chuàng)作于20

30、22年6月532 稀疏矩陣的十字鏈表存儲(chǔ)與求和一、十字鏈表存儲(chǔ)結(jié)構(gòu) 基本思想：每個(gè)非零元素用一個(gè)結(jié)點(diǎn)存儲(chǔ)，結(jié)點(diǎn)由5個(gè)域組成，如下圖所示。其中： i域存儲(chǔ)非零元素的行號(hào)， j域存儲(chǔ)非零元素的列號(hào)， e域存儲(chǔ)元素的值，right是橫向鏈表指針域，down是縱向鏈表指針域。 第四十七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和存儲(chǔ)方法：將稀疏矩陣的每一行的非0元素結(jié)點(diǎn)按列號(hào)從小到大的順序，由right指針拉成一個(gè)帶表頭結(jié)點(diǎn)的行單鏈表。每一列的非0元素按行號(hào)從小到大的順序，由down指針拉成一個(gè)帶表頭結(jié)點(diǎn)的列單鏈表。每個(gè)非零元素aij，既是第i個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是第j個(gè)

31、列鏈表中的一個(gè)結(jié)點(diǎn)。所有行鏈表的頭指針用一個(gè)指針數(shù)組rheadm存放，所有列鏈表的頭指針用指針數(shù)組cheadn存放。 第四十八張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和存儲(chǔ)結(jié)構(gòu)定義：typedef struct OLNnode / 十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)int row , col ; / 元素的行號(hào)與列號(hào)域ElemtType e ; / 數(shù)據(jù)元素域 struct OLNode *down , *right ; / 行、列鏈表指針域 OLNode , *OLink ; typedef struct / 定義行、列鏈表頭結(jié)點(diǎn)指針數(shù)組OLink *rhead , *chead

32、 ; / 行、列鏈表頭結(jié)點(diǎn)指針數(shù)組 int mu , nu , tu ; / 行數(shù)、列數(shù)、非0元素個(gè)數(shù)域 CrossList ; 第四十九張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和例如。稀疏矩陣A的十字鏈表存儲(chǔ)結(jié)構(gòu)如下圖所示。 第五十張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和二、基于十字鏈表存儲(chǔ)結(jié)構(gòu)的稀疏矩陣求和算法。1建立稀疏矩陣的十字鏈表算法步驟：（1）輸入矩陣M的行數(shù)m、列數(shù)n和非0元素個(gè)數(shù)r。（2）申請(qǐng)行、列頭指針數(shù)組空間，并初始化為空指針。（3）逐個(gè)輸入非0元素的形如（i,j,aij）的三元組，建立三元組結(jié)點(diǎn)，分別插入到行鏈表和

33、列鏈表中，直到所有非0元素的的三元組輸入完為止。第五十一張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和算法描述如下：status CreateSMatrixOL (CrossList &M ) / 創(chuàng)建十字鏈表針if ( M ) free ( M ) ;scanf (“%d ,%d, %d”, &m , &n , &t ) ; M.rhead = (OLink *)malloc(m+1)*(sizeof (OLink); / 申請(qǐng)行頭指針數(shù)組空間 if ( !M.rhead ) exit ( OVERFLOW ) ;M.chead = (OLink *)malloc(n

34、+1)*(sizeof (OLink); / 申請(qǐng)列頭指針數(shù)組空間 if ( !M.chead ) exit ( OVERFLOW ) ; M.rhead = M.chead = NULL ; / 行、列頭指針數(shù)置空 for( k =1; k i = i ; p-j = j ; p-e = e ; / 生成結(jié)點(diǎn)if ( M.rheadi = = NULL | M.rheadi-j j ) / 在第i個(gè)鏈表插入結(jié)點(diǎn) 第五十二張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和 p-right = M.rheadi；M.rheadi = p ; else / 在第i個(gè)行鏈表找插入

35、位置 for (q = M.chead; (q-right) & q.right-j right ；p-right = q-right ; q-right = p ; / 插入結(jié)點(diǎn)if ( M.cheadj = = NULL | M.rheadj-i i ) / 在第j個(gè)列鏈表插入結(jié)點(diǎn) p-down = M.cheadj；M.cheadj = p ; else / 在第j個(gè)列鏈表找插入位置 for (q = M.cheadj; (q-down) & q.down-i doen ；p-down = q-right ; q-down = p ; / 插入結(jié)點(diǎn) return OK ; 上述算法的時(shí)間

36、復(fù)雜度為O(ts)，其中s=max(m,n)。 第五十三張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和基于十字鏈表的稀疏矩陣求和已知兩個(gè)稀疏矩陣A和B，分別采用十字鏈表存儲(chǔ)，計(jì)算C=A+B，C也采用十字鏈表方式存儲(chǔ)，并且在A的基礎(chǔ)上形成C。對(duì)于求C=A-B，可表示成C=A+（-B）矩陣加法規(guī)則：只有當(dāng)A與B的行數(shù)和列數(shù)相等時(shí)二者才能相加，且cij = aij + bij。 第五十四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和以下假定將B加到A上。設(shè)pa和pb分別指向A和B的十字鏈表中行號(hào)相同的兩個(gè)結(jié)點(diǎn)，對(duì)應(yīng)元素相加時(shí)分為下列4種情況：(1) 若

37、pa-j = pb-j且pa-e + pb-e 0，則只要用aij+bij的值改寫pa所指結(jié)點(diǎn)的數(shù)據(jù)域即可。(2) 若pa-j=pb-j且pa-e + pb-e =0，則需要在矩陣A的十字鏈表中刪除pa所指結(jié)點(diǎn)，此時(shí)需改變?cè)撔墟湵碇星摆吔Y(jié)點(diǎn)的right域，以及該列鏈表中前趨結(jié)點(diǎn)的down域。(3) 若pa-j j且pa-j0（即不是表頭結(jié)點(diǎn)），則只需要將pa指針向右推進(jìn)一步，繼續(xù)進(jìn)行比較。(4) 若pa-jpb-j或pa-j0（即是表頭結(jié)點(diǎn)），則需要在矩陣A的十字鏈表中插入一個(gè)pb所指結(jié)點(diǎn)。 第五十五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和算法描述如下：statu

38、s AddMatrix (CrossList &A , CrossList B) / 求稀疏矩陣的乘積AB OLNode *p, *q,*pa,*pb,*ca,*cb,*qa; if (A.mu != B.mu | A.nu != B.nu ) return ERROR ; ca = A.rhead1 ; / 初始化ca指向A的第一個(gè)結(jié)點(diǎn) cb = B.rhead1 ; / 初始化cb指向B的第一個(gè)結(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

39、(pb-j != 0 ) / 當(dāng)前行沒(méi)有處理完 if (pa-j j & pa-j !=0 ) / 第三種情況 qa=pa; pa=pa-right; else if (pa-j pb-j | pa-j = =0 ) / 第四種情況 p= malloc(sizeof(MNode); p-i = pb- i ; p-j = pb-j; p-e = pb-e ; p-right = pa ; qa-right = p ; / 新結(jié)點(diǎn)插入*pa的前面 pa=p; / 新結(jié)點(diǎn)還要插到列鏈表的合適位置，先找位置，再插入 q = Find_JH (Ha,p-col); / 從列鏈表的頭結(jié)點(diǎn)找起第五十六張，

40、PPT共八十五頁(yè)，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲(chǔ)與求和 while (q-down-i != 0 & q-down-i i ) q=q-down; p-down=q-down; / 插在*q的后面 q-down=p ; pb=pb-right; / end if else / 第一、二種情況 x= pa-v_next.v+ pb-v_next.v; if (x= =0) / 第二種情況 qa-right = pa-right; / 從行鏈中刪除q= Find_JH (Ha,pa-col); / 找*pa的列前驅(qū)結(jié)點(diǎn)并刪除 while ( q-down-i i ) q = q-dow

41、n; q-down = pa-down ; free (pa) ; pa = qa; / if (x= =0) else / 第一種情況 pa-e = x ; qa = pa ; pa = pa-right; pb = pb-right; / while ca = ca-next; / ca指向A中下一行的表頭結(jié)點(diǎn) cb = cb-next; / cb指向B中下一行的表頭結(jié)點(diǎn) while (ca-i = =0 ) / 當(dāng)還有未處理完的行則繼續(xù) 第五十七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月54 廣義表 5.4.1廣義表的概念與ADT定義一、廣義表的概念與性質(zhì)1廣義表的定義。廣義表是n（n0

42、）個(gè)數(shù)據(jù)元素a1，a2，ai，an的有限序列，一般記作：Ls（a1，a2，ai，an）其中：Ls是廣義表的名稱，n稱為廣義表的長(zhǎng)度，記為L(zhǎng)ength(Ls)。每個(gè)元素ai（1in）稱為L(zhǎng)s的成員，它們既可以是單個(gè)元素，也可以是一個(gè)廣義表，分別稱為廣義表Ls的原子和子表。當(dāng)廣義表Ls非空時(shí)，稱第一個(gè)元素a1為L(zhǎng)s的表頭記為head（Ls），稱其余元素組成的子表（a2，ai，an）為L(zhǎng)s的表尾,記為tail(Ls) 。一個(gè)廣義表中的括號(hào)嵌套層數(shù)稱為該廣義表的深度,記為Depth(Ls)。廣義表是遞歸定義的。 第五十八張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表例如：下面是一些廣義表的例子。A

43、（），空廣義表，Length(A) =0，Depth(A)=1。B （e），單個(gè)原子構(gòu)成的廣義表，Length(B) =1，Depth(B)=1。C （a，（b，c，d），一個(gè)原子和一個(gè)子表構(gòu)成的廣義表。Length(C) =2，Depth(C)=2。D （A，B，C）= (（），（e），（a，（b，c，d）)，以三個(gè)廣義表為元素的廣義表，Length(D) =3，Depth(D)=3。E （a，E）= (a , (a , (a , (a, E ) ) ，這是一個(gè)遞歸的廣義表，其長(zhǎng)度和深度可以任意大。F （），這是一個(gè)由一個(gè)空廣義表構(gòu)成的廣義表，Length(F) =1，Depth(F)=2。

44、 第五十九張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表2廣義表的性質(zhì) 廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表?？梢杂脴?shù)結(jié)構(gòu)表示廣義表，其中原子用小矩形表示，子表用圓圈表示。例如，上述例子中的廣義表D，畫成樹(shù)的形式如下圖所示。 第六十張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表廣義表可以是遞歸的表。廣義表的定義并沒(méi)有限制元素的遞歸，即廣義表的元素也可以是其自身的子表。例如表E就是一個(gè)遞歸的表。廣義表可以為其他表所共享。例如，廣義表A、B、C是廣義表D的共享子表。在D中可以不必列出子表的值，而用子表的名稱來(lái)引用。 第六十一張，PPT共

45、八十五頁(yè)，創(chuàng)作于2022年6月廣義表二、廣義表ADT定義 1初始化廣義表InitGList ( &L )。2創(chuàng)建廣義表CreateGLists(&L , S) 。3撤消廣義表DestroyGList ( &L )。4復(fù)制廣義表CopyGList(&T ，L ) 。5判斷廣義表是否空EmptyGList(&L)。6求廣義表的長(zhǎng)度GListLength( L )。7求廣義表的深度GListDepth( L )。8在廣義表L中查找數(shù)據(jù)元素GListLocate (L ，x)。9插入一個(gè)元素InsertFirst (&L ，e )。10刪除一個(gè)元素DeleteFirstge (&L ，&e )。11取

46、表頭GetHead ( L )。 12取表尾GetTail ( L )。 13遍歷廣義表TraverseGList ( L , visit( ) )。 第六十二張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表廣義表操作舉例。對(duì)前面所給出的廣義表A、B、C、D、E、F有。GetHead（B） e , GetTail（B）（）;GetHead（C） a , GetTail（C）（b，c，d）;GetHead（D） A , GetTail（D）（B，C）;GetHead（E） a , GetTail（E）（E）;GetHead（F）（） GetTail（F）（）。 第六十三張，PPT共八十五頁(yè)，創(chuàng)作

47、于2022年6月542 廣義表的存儲(chǔ)一、頭尾表示法 廣義表中的數(shù)據(jù)元素既可能是廣義表，也可能是原子，相應(yīng)地在頭尾表示法中，結(jié)點(diǎn)的結(jié)構(gòu)形式有兩種：一種是子表結(jié)點(diǎn)，用以表示子表；另一種是原子結(jié)點(diǎn)，用以表示原子。在表結(jié)點(diǎn)中應(yīng)該包括一個(gè)指向表頭的指針和指向表尾的指針；而在原子結(jié)點(diǎn)中應(yīng)該包括所表示原子的元素值。為了區(qū)分這兩類結(jié)點(diǎn)，在結(jié)點(diǎn)中還要設(shè)置一個(gè)標(biāo)志域，如果標(biāo)志為1，則表示該結(jié)點(diǎn)為子表結(jié)點(diǎn)；如果標(biāo)志為0，則表示該結(jié)點(diǎn)為原子結(jié)點(diǎn)。結(jié)點(diǎn)結(jié)構(gòu)如圖所示： 第六十四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的存儲(chǔ)存儲(chǔ)結(jié)構(gòu)定義：typedef enum ATOM, LIST Elemtag; / ATOM

48、=0表示單元素；LIST=1表示子表typedef struct GLNode Elemtag tag ; / 標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn) union / 元素結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分 AtomType atom ; / atom是元素結(jié)點(diǎn)的值域 struct struct GLNode *hp, *tp ; ptr; / ptr是表結(jié)點(diǎn)的指針域，ptr.hp和ptr.tp分別指向表頭和表尾 *GList; / 廣義表類型 第六十五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的存儲(chǔ)舉例對(duì)前面所給的廣義表A、B、C、D、E、F，存儲(chǔ)結(jié)構(gòu)如下圖所示。 D （A，B，C）= (（），（e），

49、（a，（b，c，d）)第六十六張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的存儲(chǔ)二、孩子兄弟表示法兩種結(jié)點(diǎn)形式：一種是有孩子結(jié)點(diǎn)，用以表示列表；另一種是無(wú)孩子結(jié)點(diǎn)，用以表示單元素。在有孩子結(jié)點(diǎn)中包括一個(gè)指向第一個(gè)孩子（長(zhǎng)子）的指針和一個(gè)指向兄弟的指針；而在無(wú)孩子結(jié)點(diǎn)中包括一個(gè)指向兄弟的指針和該元素的元素值。為了能區(qū)分這兩類結(jié)點(diǎn)，在結(jié)點(diǎn)中還要設(shè)置一個(gè)標(biāo)志域。如果標(biāo)志為1，則表示該結(jié)點(diǎn)為有孩子結(jié)點(diǎn)；如果標(biāo)志為0，則表示該結(jié)點(diǎn)為無(wú)孩子結(jié)點(diǎn)。結(jié)點(diǎn)結(jié)構(gòu)如圖所示。 第六十七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的存儲(chǔ)存儲(chǔ)結(jié)構(gòu)定義：typedef enum ATOM, LIST Elemtag

50、; / ATOM=0：?jiǎn)卧?；LIST=1：子表typedef struct GLNode Elemtag tag ; / 標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn) union / 元素結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分 AtomType atom; / 元素結(jié)點(diǎn)的值域 struct GLNode *hp; / 表結(jié)點(diǎn)的表頭指針 ; struct GLNode *tp; / 指向下一個(gè)結(jié)點(diǎn) *GList; / 廣義表類型 第六十八張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的存儲(chǔ)舉例對(duì)于前面所給的廣義表A、B、C、D、E、F，孩子兄弟表示法如下圖所示。 D （A，B，C）= (（），（e），（a，（b，c，d

51、）)第六十九張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月543 廣義表的基本操作算法算法思想：假設(shè)廣義表以串S的形式給出，當(dāng)廣義表為空時(shí)，即S=( )，此時(shí)直接返回L=NULL。當(dāng)廣義表為不空時(shí)，S=(a1 , a2 , , an )，其中ai(i=1,2,n)為S的子串表示的子表。建立廣義表S就是建立n個(gè)子表結(jié)點(diǎn)拉成的鏈表。第i個(gè)（1in）表結(jié)點(diǎn)的tp指針指向第i+1個(gè)表結(jié)點(diǎn)，第n個(gè)表結(jié)點(diǎn)的tp指針為NULL。第i個(gè)表結(jié)點(diǎn)的hp指針指向由ai建立的子表。由此可見(jiàn)，建立廣義表S轉(zhuǎn)化為建立子表ai（1in）的問(wèn)題。而建立子表ai（1in）的過(guò)程與建立廣義表S的過(guò)程完全相同，這顯然是一個(gè)遞歸問(wèn)題。對(duì)

52、每個(gè)ai又分三種情況：（1）ai是帶括號(hào)的空串；（2）ai是長(zhǎng)度為1的單字符串；（3）ai是長(zhǎng)度大于1的字符串。前兩種情況就是遞歸的終結(jié)狀態(tài)，第三種情況是遞歸調(diào)用。 第七十張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的基本操作算法遞歸過(guò)程如下：基本項(xiàng)：置空廣義表， 當(dāng)S為空表串時(shí)； 建立原子結(jié)點(diǎn)子表， 當(dāng)S為單字符串時(shí)；歸納項(xiàng)：假定S =(a1 , a2 , , an )，sub=s1,s2,sn是S脫去的最外層括號(hào)之后的字符串，其中si(i=1,2,n)是非空的字符串，對(duì)每個(gè)si建立一個(gè)表結(jié)點(diǎn)，結(jié)點(diǎn)的hp指針域指向由si建立的子表，tp指針指向由si+1（itag = ATOM ; L-

53、atom = S; / 創(chuàng)建原子結(jié)點(diǎn) else L-tag = LIST; p = L ; / 重復(fù)建立n個(gè)子表 SubString (sub , S , 2 , StrLength (S )-2 ) ; / 脫去外層括號(hào) do sever ( sub , hsub ) ; / 從sub中分離出表頭串 CreateGList (p-ptr.hp , hsub) ; q = p ; if (!StrEmpty (sub) / 表尾不空 if (!(p = (GList)malloc(sizeof(GLNode) exit (OVERFLOW); p-tag = LIST ; q-ptr.tp =

54、 p; while (!StrEmpty (sub) ); q-ptr.tp = NULL; return OK ; 第七十二張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的基本操作算法status sever(SString &str , SString &hstr) n = StrLength(str); i= 1; k = 0 ; for (i = 1, k = 0; i = n | k != 0; +i) ch = SubStr (ch , str , i ,1 ); if (ch = = ( ) +k; else if (ch = = ) -k; if (i tag = = 1)

55、p = L-hp; return p; GList GetTail(GList L) if ( L-tag = = 1) p = L-tp; return p; 第七十四張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的基本操作算法三、求廣義表的深度設(shè)廣義表LS=(a1 , a2 , , an )，求廣義表深度的遞歸形式如下：基本項(xiàng)： Depth (LS) = 1， 當(dāng)LS為空廣義表； Depth (LS) = 0 ， 當(dāng)LS為原子時(shí)；歸納項(xiàng)： Depth (LS) = 1 + max Depth (si) | 1=i=1 。算法描述：int GListDepth ( GList L ) if

56、 (! L) return 1; / 空表深度為1 if ( L-tag = = ATOM ) return 0; / 單元素深度為0 for ( max = 0 , p =L ; p ; p = p-ptr.tp) dep = GListDepth ( p-ptr.hp ) ; / 求以p-ptr.hp尾頭指針的子表深度 if (dep max) max = dep; return max +1; / 非空表的深度是各元素的深度的最大值加1 第七十五張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的基本操作算法四、求廣義表的長(zhǎng)度算法思想：只需統(tǒng)計(jì)最頂層的表結(jié)點(diǎn)個(gè)數(shù)即可。算法描述：int GL

57、istLength ( GList L ) if ( L ) return 1+ GListLength ( L -tp ) ; else return 0 ; 第七十六張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的基本操作算法五、復(fù)制廣義表算法思想：將廣義表分成表頭和表尾兩部分，先復(fù)制表頭部分，再?gòu)?fù)制表尾部分。若表頭部分是原子，就建立一個(gè)原子結(jié)點(diǎn)，若表頭是子表，則又將分成表頭和表尾兩部分處理。表尾一定是子表，又分成表頭和表尾兩部分處理。復(fù)制整個(gè)廣義表和復(fù)制子表的過(guò)程完全相同。設(shè)復(fù)制后的廣義表為NewLS，遞歸過(guò)程如下： 基本項(xiàng)：InitGList (NewLS), 當(dāng)LS為空廣義表，置空表； 歸納項(xiàng)：COPY(GetHead(LS) , GetHead (NewLS) ) / 復(fù)制表頭 COPY(GetTail(LS) , GetTail (NewLS) ) / 復(fù)制表尾 第七十七張，PPT共八十五頁(yè)，創(chuàng)作于2022年6月廣義表的基本操作算法 算法過(guò)程描述：status Copy