數(shù)組與廣義表

數(shù)組與廣義表第1頁(yè)，共82頁(yè)，2023年，2月20日，星期五第5章數(shù)組與廣義表

本章主要內(nèi)容一、數(shù)組的存儲(chǔ)結(jié)構(gòu)及其地址變換二、特殊矩陣的壓縮存儲(chǔ)及其地址變換三、稀疏矩陣的存儲(chǔ)結(jié)構(gòu)與算法四、廣義表的存儲(chǔ)結(jié)構(gòu)與算法第2頁(yè)，共82頁(yè)，2023年，2月20日，星期五5.1數(shù)組

數(shù)組是線性表的直接推廣。如果線性表的元素又是具有相同數(shù)據(jù)類型的線性表，這種線性表就是二維數(shù)組，若在二維數(shù)組中，元素還是線性表，即得到三維數(shù)組，依次類推可以得到n維數(shù)組。本節(jié)主要討論數(shù)組的有關(guān)概念、存儲(chǔ)結(jié)構(gòu)及地址變換。第3頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．1．1數(shù)組類型與存儲(chǔ)結(jié)構(gòu)一、二維數(shù)組

一個(gè)m行n列的二維數(shù)組如下表所示：

第4頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(shù)組類型與存儲(chǔ)結(jié)構(gòu)

令αi=（ai1，ai2，…，ai,n）(i=1,2,…,m)，每行作為一個(gè)元素，則A=(α1,α2,…,αm)是一個(gè)元素為線性表的線性表。 若令βj=(a1j，a2j，…，amj)T(j=1,2,…,n),每列作為一個(gè)元素，則A=(β1,β2,…,βn)也是一個(gè)元素為線性表的線性表。 基于這一原因，而把數(shù)組看成是線性表的推廣。第5頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(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ù)組中不能做插入、刪除操作。在高級(jí)語(yǔ)言中，數(shù)組一旦被定義，每一維的下標(biāo)上下界都不能改變。對(duì)數(shù)組可以施加的操作主要有以下兩種：（1）取值操作：給定下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。（2）賦值操作：給定下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。第6頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(shù)組類型與存儲(chǔ)結(jié)構(gòu)

由含n個(gè)下標(biāo)（0≦ji≦bi－1，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ì)于任意元素（0≦ji≦bi－2）都有一個(gè)直接后繼。n維數(shù)組的ADT定義。

只包含4種操作：

InitArray(&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ù)元素賦值。

第7頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(shù)組的內(nèi)存映象一、二維數(shù)組的存儲(chǔ)結(jié)構(gòu)及地址變換1、以行為主序順序存儲(chǔ)。用一塊連續(xù)存儲(chǔ)空間逐行順序存儲(chǔ)數(shù)組元素。例如：一個(gè)m×n數(shù)組按行存儲(chǔ)表示如下圖：第8頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(shù)組的內(nèi)存映象2、以列為主序順序存儲(chǔ)。用連續(xù)存儲(chǔ)空間逐列順序存儲(chǔ)數(shù)組元素。例如：m×n數(shù)組按列順序存儲(chǔ)，如下圖所示：第9頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．1．2數(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)+(i×n+j)×L。第10頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(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)+(j×m+i)×L。對(duì)一般的二維數(shù)組，設(shè)數(shù)組A[c1..d1][c2..d2]，下標(biāo)的上、下界可以是任何整數(shù)，則aij的物理地址計(jì)算公式為：行主序：LOC(aij)=LOC(ac1c2)+((i-c1)×(d2-c2+1)+(j-c2))×L。列主序：LOC(aij)=LOC(ac1c2)+((j-c2)×(d1

–c1+1)+(i-c1))×L。第11頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(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ù)組A[m][n][p]，元素aijk其物理地址為：LOC(aijk)=LOC(a111)+((i-1)×n×p+(j-1)×p+k-1)×L

第12頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(shù)組的內(nèi)存映象舉例。若矩陣Am×n

中存在某個(gè)元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫(xiě)一個(gè)算法，找出A中的所有鞍點(diǎn)。解決此問(wèn)題的基本思想是：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，否則不輸出，接著處理下一行。設(shè)矩陣A用一個(gè)二維數(shù)組表示。第13頁(yè)，共82頁(yè)，2023年，2月20日，星期五數(shù)組的內(nèi)存映象算法如下：voidsaddle(intA[][],intm,intn)//m,n是矩陣A的行數(shù)和列數(shù){inti,j,min;for(i=0;i<m;i++)//按行處理

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

for(p=0;p<m&&a[i][k]>a[p][k];p++)//檢測(cè)該行中的每一個(gè)最小值是否是鞍點(diǎn)

if(p>=m)printf(＂%d,%d,%d\n＂,i,k,min);}//if}//for/}第14頁(yè)，共82頁(yè)，2023年，2月20日，星期五5.2特殊矩陣的壓縮存儲(chǔ)5．2．1對(duì)稱矩陣一、對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣：n階方陣中，若aij=aji，其中1≤i,j≤n，則稱該矩陣為對(duì)稱矩陣。如下圖所示的矩陣是一個(gè)５階對(duì)稱矩陣。第15頁(yè)，共82頁(yè)，2023年，2月20日，星期五特殊矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的元素關(guān)于主對(duì)角線對(duì)稱，因此只需存儲(chǔ)上三角或下三角部分即可。例如：上圖（a）給出的5階對(duì)稱矩陣存儲(chǔ)到一個(gè)一維數(shù)組如下圖（b）所示。第16頁(yè)，共82頁(yè)，2023年，2月20日，星期五對(duì)稱矩陣的壓縮存儲(chǔ)將一個(gè)對(duì)稱矩陣只存儲(chǔ)下三角（或上三角）部分的元素aij，此時(shí)有j≤i且1≤i≤n，對(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ǔ)單元。第17頁(yè)，共82頁(yè)，2023年，2月20日，星期五對(duì)稱矩陣的壓縮存儲(chǔ)采用以行為主序的方法順序存儲(chǔ)到一個(gè)一維數(shù)組中。因?yàn)橄氯侵泄灿袀€(gè)元素，設(shè)存儲(chǔ)結(jié)構(gòu)為一維數(shù)組。A[]，如下圖所示。第18頁(yè)，共82頁(yè)，2023年，2月20日，星期五對(duì)稱矩陣的壓縮存儲(chǔ)二、地址變換設(shè)矩陣的下三角部分的元素aij，下標(biāo)滿足條件：i≥j且1≤i≤n，存儲(chǔ)到一維數(shù)組A的第k個(gè)元素A[k]中，則有：第19頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．2．2三角矩陣一、下三角矩陣的壓縮存儲(chǔ)形如下圖所示的矩陣稱為下三角矩陣。主對(duì)角線上方所有元素等于同一個(gè)常數(shù)C。第20頁(yè)，共82頁(yè)，2023年，2月20日，星期五一、下三角矩陣的壓縮存儲(chǔ)下三角矩陣的壓縮存儲(chǔ)與對(duì)稱矩陣的壓縮存儲(chǔ)類似。例如：下圖所給給出一個(gè)下三角矩陣存儲(chǔ)結(jié)構(gòu)。第21頁(yè)，共82頁(yè)，2023年，2月20日，星期五下三角矩陣的壓縮存儲(chǔ)下三角矩陣壓縮存儲(chǔ)的地址變換用一維數(shù)組A[]。存儲(chǔ)下三角矩陣。如下圖所示：設(shè)aji存放在A[k]中，則k與i、j的對(duì)應(yīng)關(guān)系有如下公式：當(dāng)i≥j時(shí)，k=當(dāng)i<j時(shí)k=。第22頁(yè)，共82頁(yè)，2023年，2月20日，星期五二、上三角矩陣

三角矩陣，存儲(chǔ)思想與下三角類似，以行為主序順序存儲(chǔ)上三角部分，最后存儲(chǔ)對(duì)角線下方的常量，如下圖所示。第23頁(yè)，共82頁(yè)，2023年，2月20日，星期五上三角矩陣地址變換公式：若元素aji

存儲(chǔ)在一維數(shù)組A的A[k]中，則k與i和j的對(duì)應(yīng)關(guān)系為：k=當(dāng)i≤j時(shí)k=當(dāng)i>j時(shí)第24頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．2．3帶狀矩陣n階矩陣A稱為帶狀矩陣，如果存在最小正數(shù)m，滿足當(dāng)∣i-j∣≥m時(shí)，aij=0，這時(shí)稱w=2n-1為矩陣A的帶寬。例如下圖是一個(gè)w=3(m=2)的帶狀矩陣。第25頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶狀矩陣帶狀矩陣A采用壓縮存儲(chǔ)有兩種方法。第一種方法：將A壓縮到一個(gè)n行w列的二維數(shù)組B中，如下圖所示。當(dāng)某行非零元素的個(gè)數(shù)小于帶寬w時(shí)，先存放非零元素然后補(bǔ)零。第26頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶狀矩陣另一種壓縮方法是將帶狀矩陣壓縮到一維數(shù)組中去，按以行為主序存儲(chǔ)，順序存放非零元素，如下圖所示，按此規(guī)律，可得到相應(yīng)的映象函數(shù)。如當(dāng)w=3時(shí)，映象函數(shù)為：k=2（i-1)+j-1第27頁(yè)，共82頁(yè)，2023年，2月20日，星期五5.3稀疏矩陣當(dāng)m*n矩陣中有t個(gè)非零元素且t<<m*n時(shí)，這樣的矩陣稱為稀疏矩陣。稀疏矩陣壓縮存儲(chǔ)方法是僅存放非零元素。由于非零元素分布沒(méi)有規(guī)律，為了能找到相應(yīng)的元素，所以僅存儲(chǔ)非零元素的值是不夠的，還必須記下它們所在的行號(hào)和列號(hào)。為此采取如下方法：將非零元素所在的行、列以及它的值構(gòu)成一個(gè)三元組（i,j,v），然后將這些三元組按某種規(guī)律順序存儲(chǔ)，這種方法可以節(jié)約大量的存儲(chǔ)空間。第28頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣稀疏矩陣的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)置。TransposeSMatrix（M,&T）第29頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．3．1稀疏矩陣的三元組存儲(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)所示。第30頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法存儲(chǔ)結(jié)構(gòu)的定義：defineMAXSIZE1024//非0元素的個(gè)數(shù)數(shù)typedefstruct//定義三元組元素結(jié)構(gòu)

{inti,j;//非零元素的行號(hào)和列號(hào)

ElemTypee;//非零元素的值

}Triple;//三元組類型typedefstruct{SPNodedata[MAXSIZE+1];//三元組順序表intmu,nu,tu;//矩陣的行、列及非零元素的個(gè)數(shù)

}TSMatrix;//三元組表的存儲(chǔ)類型第31頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法二、稀疏矩陣的算法實(shí)現(xiàn)1．矩陣的轉(zhuǎn)置設(shè)TSMatrixA表示一個(gè)m×n的稀疏矩陣，其轉(zhuǎn)置TSMatrixB是一個(gè)n×m的稀疏矩陣。轉(zhuǎn)置算法基本思想：①A的行、列轉(zhuǎn)化成B的列、行；②在A.data中依次找第一列的、第二列的、…、直到最后一列，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B.data中。

第32頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法算法描述如下：voidTransposeSMatrix(TSMatrixA,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;p<=A.tu;p++)//掃描整個(gè)三元組表

if(A.data[p].j==col){B.data[q].i=A.data[p].j;B.data[q].j=A.data[p].i;B.data[q].e=A.data[p].e;q++;}//if}//if(B->tu>0)returnOK;

}//TransposeSMatrix第33頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(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í)間性能更差一些。第34頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法2．帶列邏輯連接的三元組順序存儲(chǔ)與改進(jìn)的轉(zhuǎn)置算法引入兩個(gè)向量：num[n+1]和cpot[n+1]，其中num[col]表示矩陣A中第col列的非零元素的個(gè)數(shù)（為了方便下標(biāo)均從1開(kāi)始），cpot［col］的初始值表示矩陣A中的第col列的第一個(gè)非零元素在B.data中的位置。于是cpot的初始值為：cpot[1]=1；cpot[col]=cpot[col-1]+num[col-1]；2≤col≤n

第35頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法例如。下圖（a）所給矩陣A的num和cpot的數(shù)組值如右圖所示。改進(jìn)的稀疏矩陣轉(zhuǎn)置算法稱為快速轉(zhuǎn)置。算法思想：依次掃描A.data，當(dāng)掃描到一個(gè)col列元素時(shí)，直接將其存放在B.data的cpot[col]位置上，且cpot[col]加１，cpot[col]中始終是下一個(gè)col列元素在B.data中的位置。第36頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(chǔ)與轉(zhuǎn)置、乘法快速轉(zhuǎn)置算法如下：StatusFastTransposeSMatrix(TSMatrixA,TSMatrix&B){

B.mu=A.nu;B.nu=A.mu;

B.tu=A.tu;//稀疏矩陣的行、列及元素個(gè)數(shù)

if(B.tu>0)//有非零元素則轉(zhuǎn)換

{for(i=1;i<=A.nu;i++)num[i]=0;for(i=1;i<=A.tu;i++)//求矩陣A中每一列非零元素的個(gè)數(shù)

{j=A.data[i].j;num[j]++;}cpot[1]=1;//求矩陣A中每一列第一個(gè)非零元素在B.data中的位置for(i=2;i<=A.nu;i++)cpot[i]=cpot[i-1]+num[i-1];for(i=1;i<=A.tu;i++)//掃描三元組表

{j=A.data[i].j;//當(dāng)前三元組的列號(hào)

k=cpot[j];//當(dāng)前三元組在B.data中的位置

B.data[k].i=A.data[i].j;B.data[k].j=A.data[i].i;B.data[k].v=A.data[i].v;cpot[j]++;}//fori

}//if(B.tu)

returnB;//返回的是轉(zhuǎn)置矩陣的指針

}//FastTransposeSMatrix第37頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的三元組存儲(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）。第38頁(yè)，共82頁(yè)，2023年，2月20日，星期五2．帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法已知稀疏矩陣A(m1×n1)和B(m2×n2)，求乘積C(m1×n2)。例如：稀疏矩陣A、B、C及它們對(duì)應(yīng)的三元組順序表A.data、B.data、C.data如下圖(a)和(b)所示。

第39頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法由矩陣乘法規(guī)則知：C[i，j]=A[i,1]×B[1,j]+A[i,2]×B[2,j]+…+A[i,n]×B[n,j]=當(dāng)A的元素A[i,k]的列號(hào)與B的元素B[k,p]的行號(hào)相等時(shí)才能相乘，且當(dāng)兩項(xiàng)都不為零時(shí)，乘積中的這一項(xiàng)才不為零。為運(yùn)算方便設(shè)一個(gè)累加器：datatypetemp[n+1]；用來(lái)存放當(dāng)前行中cij的值，當(dāng)前行中所有元素全部計(jì)算出之后，再存放到C.data中去。第40頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法為了便于在B.data中尋找B中的第k行的第一個(gè)非零元素，與前面類似，引入num[n]和rpot[n]兩個(gè)向量。num[k]表示矩陣B中第k行的非零元素的個(gè)數(shù)；rpot[k]表示第k行的第一個(gè)非零元素在B.data中的位置。于是有：rpot[1]=1rpot[k]=rpot[k-1]+num[k-1]2≤k≤n第41頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法例如，下圖（a）的矩陣B的其num[n]和rpot[n]的值如右邊的表所示。k1234num[k]2020cpot[k]1335第42頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法稀疏矩陣存儲(chǔ)結(jié)構(gòu)定義：#defineMAXSIZE1024//稀疏矩陣非0元素最大個(gè)數(shù)#defineMAXRC100//稀疏矩陣的最大行數(shù)typedefstruct{//定義帶行邏輯連接的三元組順序表類型

Tripledata[MAXSIZE+1];intrpot[MAXRC+1]intmu,nu,tu;}RLSMatrix

稀疏矩陣乘法的算算步驟：⑴初始化。清理一些單元，準(zhǔn)備按行順序存放乘積矩陣;⑵求B的num[n]和rpot[n]數(shù)組值;⑶做矩陣乘法。將A.data中三元組的列值與B.data中三元組的行值相等的非零元素相乘，并將具有相同下標(biāo)的乘積元素相加。第43頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶行邏輯連接的三元組順序存儲(chǔ)與乘積算法稀疏矩陣乘法的算法描述：StatusMatrixMultiply(RLSMatrix*A,RLSMatrix*B,RLSMatrix&C)//求稀疏矩陣C=A×B{intp,q,i,j,k,r;ElemTypectemp[n+1];intnum[B.nu+1];if(A.nu!=B.mu)returnERROR;//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++)num[i]=0;//求矩陣B中每一行非零元素的個(gè)數(shù)for(k=1;k<=B.tu;k++){i=B.data[k].i;num[i]++;}

rpot[1]=1;//求矩陣B中每一行第一個(gè)非零元素在B.data中的位置for(i=2;i<=B.mu;i++)rpot[i]=rpot[i-1]+num[i-1];第44頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶行邏輯連接的三元組順序存儲(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++)temp[j]=0;//cij的累加器初始化

while(A.data[p].i==i)//求第i行的

{k=A.data[p].j;//A中當(dāng)前非零元的列號(hào)

if(k<B.mu)t=rpot[k+1];elset=B.tu+1;//確定B中第k行的非零元素在B.data中的下限位置

for(q=rpot[k];q<t;q++)//B中第k行的每一個(gè)非零元素

{j=B.data[q].j;

temp[j]+=A.data[p].e*B.data[q].e}p++;

}//whilefor(j=1;j<=B->nu;j++)if(temp[j]){r++;C.data[r]={i,j,temp[j]};}

}//foriC.tu=r;returnOK;}//MulSMatrix第45頁(yè)，共82頁(yè)，2023年，2月20日，星期五帶行邏輯連接的三元組順序存儲(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)。第46頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．3．2稀疏矩陣的十字鏈表存儲(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是縱向鏈表指針域。

第47頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(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è)列鏈表中的一個(gè)結(jié)點(diǎn)。所有行鏈表的頭指針用一個(gè)指針數(shù)組rhead[m]存放，所有列鏈表的頭指針用指針數(shù)組chead[n]存放。

第48頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(chǔ)與求和存儲(chǔ)結(jié)構(gòu)定義：typedefstructOLNnode{//十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)introw,col;//元素的行號(hào)與列號(hào)域ElemtTypee;//

數(shù)據(jù)元素域

structOLNode*down,*right;//行、列鏈表指針域

}OLNode,*OLink;

typedefstruct{//定義行、列鏈表頭結(jié)點(diǎn)指針數(shù)組OLink*rhead,*chead;//行、列鏈表頭結(jié)點(diǎn)指針數(shù)組

intmu,nu,tu;//

行數(shù)、列數(shù)、非0元素個(gè)數(shù)域}CrossList;

第49頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(chǔ)與求和例如。稀疏矩陣A的十字鏈表存儲(chǔ)結(jié)構(gòu)如下圖所示。

第50頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(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)，分別插入到行鏈表和列鏈表中，直到所有非0元素的的三元組輸入完為止。第51頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(chǔ)與求和算法描述如下：statusCreateSMatrixOL(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+1)*(sizeof(OLink));//申請(qǐng)列頭指針數(shù)組空間

if(!M.chead)exit(OVERFLOW);M.rhead[]=M.chead[]=NULL;//行、列頭指針數(shù)置空

for(k=1;k<M.tu;k++){p=(OLink*)malloc(sizeof(OLink);//申請(qǐng)第k個(gè)結(jié)點(diǎn)if(!p)exit(OVERFLOW);scanf(“%d,%d,%d”,&i,&j,&e);//輸入結(jié)點(diǎn)數(shù)據(jù)p->i=i;p->j=j;p->e=e;//生成結(jié)點(diǎn)if(M.rhead[i]==NULL||M.rhead[i]->j>j)//在第i個(gè)鏈表插入結(jié)點(diǎn)第52頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(chǔ)與求和

{p->right=M.rhead[i]；M.rhead[i]=p;}else{//在第i個(gè)行鏈表找插入位置

for(q=M.chead;(q->right)&&q.right->j<j)q=q->right；p->right=q->right;q->right=p;//插入結(jié)點(diǎn)}if(M.chead[j]==NULL||M.rhead[j]->i>i)//在第j個(gè)列鏈表插入結(jié)點(diǎn)

{p->down=M.chead[j]；M.chead[j]=p;}else{//在第j個(gè)列鏈表找插入位置

for(q=M.chead[j];(q->down)&&q.down->i<i)q=q->doen；p->down=q->right;q->down=p;//插入結(jié)點(diǎn)}}returnOK;}上述算法的時(shí)間復(fù)雜度為O(t×s)，其中s=max(m,n)。

第53頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(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。第54頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(chǔ)與求和以下假定將B加到A上。設(shè)pa和pb分別指向A和B的十字鏈表中行號(hào)相同的兩個(gè)結(jié)點(diǎn)，對(duì)應(yīng)元素相加時(shí)分為下列4種情況：(1)若pa->j=pb->j且pa->e+pb->e≠0，則只要用aij+bij的值改寫(xiě)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<pb->j且pa->j≠0（即不是表頭結(jié)點(diǎn)），則只需要將pa指針向右推進(jìn)一步，繼續(xù)進(jìn)行比較。(4)若pa->j>pb->j或pa->j＝0（即是表頭結(jié)點(diǎn)），則需要在矩陣A的十字鏈表中插入一個(gè)pb所指結(jié)點(diǎn)。第55頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(chǔ)與求和算法描述如下：statusAddMatrix(CrossList&A,CrossListB)//求稀疏矩陣的乘積A×B{OLNode*p,*q,*pa,*pb,*ca,*cb,*qa;if(A.mu!=B.mu||A.nu!=B.nu)returnERROR;ca=A.rhead[1];//初始化ca指向A的第一個(gè)結(jié)點(diǎn)

cb=B.rhead[1];//初始化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(pb->j!=0)//當(dāng)前行沒(méi)有處理完

{if(pa->j<pb->j&&pa->j!=0)//第三種情況

{qa=pa;pa=pa->right;}elseif(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)找起第56頁(yè)，共82頁(yè)，2023年，2月20日，星期五稀疏矩陣的十字鏈表存儲(chǔ)與求和

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

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

{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<pa->i)q=q->down;q->down=pa->down;free(pa);pa=qa;}//if(x==0)else//第一種情況{pa->e=x;qa=pa;}pa=pa->right;pb=pb->right;}}//whileca=ca->next;//ca指向A中下一行的表頭結(jié)點(diǎn)

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

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

}第57頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．4廣義表

5.4.1廣義表的概念與ADT定義一、廣義表的概念與性質(zhì)1．廣義表的定義。廣義表是n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an的有限序列，一般記作：Ls＝（a1，a2，…，ai，…，an）其中：Ls是廣義表的名稱，n稱為廣義表的長(zhǎng)度，記為L(zhǎng)ength(Ls)。每個(gè)元素ai（1≤i≤n）稱為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)。廣義表是遞歸定義的。第58頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表例如：下面是一些廣義表的例子。A＝（），空廣義表，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。第59頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表2．廣義表的性質(zhì)

⑴廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表。可以用樹(shù)結(jié)構(gòu)表示廣義表，其中原子用小矩形表示，子表用圓圈表示。例如，上述例子中的廣義表D，畫(huà)成樹(shù)的形式如下圖所示。第60頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表⑵廣義表可以是遞歸的表。廣義表的定義并沒(méi)有限制元素的遞歸，即廣義表的元素也可以是其自身的子表。例如表E就是一個(gè)遞歸的表。⑶廣義表可以為其他表所共享。例如，廣義表A、B、C是廣義表D的共享子表。在D中可以不必列出子表的值，而用子表的名稱來(lái)引用。第61頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表二、廣義表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．取表頭GetHead(L)。12．取表尾GetTail(L)。13．遍歷廣義表TraverseGList(L,visit())。第62頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表廣義表操作舉例。對(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）＝（）。第63頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．4．2廣義表的存儲(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)如圖所示：第64頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的存儲(chǔ)存儲(chǔ)結(jié)構(gòu)定義：typedefenum{ATOM,LIST}Elemtag;//ATOM=0表示單元素；LIST=1表示子表typedefstructGLNode{Elemtagtag;//標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn)

union{//元素結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分

AtomTypeatom;//atom是元素結(jié)點(diǎn)的值域

struct{structGLNode*hp,*tp;}ptr;//ptr是表結(jié)點(diǎn)的指針域，ptr.hp和ptr.tp分別指向表頭和表尾

}}*GList;//廣義表類型第65頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的存儲(chǔ)舉例．對(duì)前面所給的廣義表A、B、C、D、E、F，存儲(chǔ)結(jié)構(gòu)如下圖所示。

D＝（A，B，C）=(（），（e），（a，（b，c，d））)第66頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的存儲(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)如圖所示。第67頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的存儲(chǔ)存儲(chǔ)結(jié)構(gòu)定義：typedefenum{ATOM,LIST}Elemtag;//ATOM=0：?jiǎn)卧?；LIST=1：子表typedefstructGLNode{Elemtagtag;//標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn)

union{//元素結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分

AtomTypeatom;//元素結(jié)點(diǎn)的值域

structGLNode*hp;//表結(jié)點(diǎn)的表頭指針

};structGLNode*tp;//指向下一個(gè)結(jié)點(diǎn)

}*GList;//廣義表類型第68頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的存儲(chǔ)舉例．對(duì)于前面所給的廣義表A、B、C、D、E、F，孩子兄弟表示法如下圖所示。

D＝（A，B，C）=(（），（e），（a，（b，c，d））)第69頁(yè)，共82頁(yè)，2023年，2月20日，星期五5．4．3廣義表的基本操作算法算法思想：假設(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è)（1≤i≤n）表結(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（1≤i≤n）的問(wèn)題。而建立子表ai（1≤i≤n）的過(guò)程與建立廣義表S的過(guò)程完全相同，這顯然是一個(gè)遞歸問(wèn)題。對(duì)每個(gè)ai又分三種情況：（1）ai是帶括號(hào)的空串；（2）ai是長(zhǎng)度為1的單字符串；（3）ai是長(zhǎng)度大于1的字符串。前兩種情況就是遞歸的終結(jié)狀態(tài)，第三種情況是遞歸調(diào)用。

第70頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的基本操作算法遞歸過(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（i<n）建立的表結(jié)點(diǎn)，最后一個(gè)表結(jié)點(diǎn)的tp指針為NULL。

第71頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的基本操作算法算法描述：statusCreateGLint(GList&L,SStringS){if(StrEmpty(S))L=NULL;//創(chuàng)建空表

else{if(!(L=(GList)malloc(sizeof(GLNode))))exit(OVERFLOW);//建表結(jié)點(diǎn)

if(StrLength(S)==1){L->tag=ATOM;L->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=p;}}while(!StrEmpty(sub));q->ptr.tp=NULL;}}returnOK;}第72頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的基本操作算法statussever(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;elseif(ch==')')--k;}if(i<=n){hstr=SubStr(hstr,str,1,i-2);str=SubStr(str,str,i,n-i+1);}else{StrCopy(hstr,str);ClearStr(str);}}第73頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的基本操作算法二、取廣義表的頭、尾部分算法思想很簡(jiǎn)單，只要返回表頭或表尾結(jié)點(diǎn)的指針即可。GListGetHead(GListL){if(L->tag==1)p=L->hp;returnp;}GListGetTail(GListL){if(L->tag==1)p=L->tp;returnp;}

第74頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的基本操作算法三、求廣義表的深度設(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<=n}，n>=1。算法描述：intGListDepth(GListL){if(!L)return1;//空表深度為1

if(L->tag==ATOM)return0;//單元素深度為0

for(max=0,p=L;p;p=p->ptr.tp){dep=GListDepth(p->ptr.hp);//求以p->ptr.hp尾頭指針的子表深度

if(dep>max)max=dep;}

returnmax+1;//非空表的深度是各元素的深度的最大值加1

}第75頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的基本操作算法四、求廣義表的長(zhǎng)度算法思想：只需統(tǒng)計(jì)最頂層的表結(jié)點(diǎn)個(gè)數(shù)即可。算法描述：intGListLength(GListL){if(L)return1+GListLength(L->tp);elsereturn0;}

第76頁(yè)，共82頁(yè)，2023年，2月20日，星期五廣義表的基本操作算法五、復(fù)制廣義表算法思想：將廣義表分成表頭和表尾兩部分，先復(fù)制表頭部分，再?gòu)?fù)制表尾部分。若表頭部分是原子，就建立一個(gè)原子結(jié)點(diǎn)，若表頭是子表，則又將分成表頭和表尾兩部分處理。表尾一定是子表，又分成表頭和表尾兩部分處理。復(fù)制整個(gè)廣義表和復(fù)制子表的過(guò)程完全相同。設(shè)復(fù)制后的廣義表為NewLS，遞歸過(guò)程如下：基本項(xiàng)：InitGList(