第5章數組和廣義表本章主題：多維數組、特殊矩陣和廣義表

教學目的：掌握數組和廣義表的定義、運算及存儲結構教學難點：矩陣的壓縮存儲2023/7/221

本章主要介紹數組的概念及多維數組在計算機中的存放，特殊矩陣的壓縮存儲及相應運算，廣義表的概念和存儲結構及其相關運算的實現。通過本章學習，要求掌握如下內容：1．多維數組的定義及在計算機中的存儲表示；2．對稱矩陣、三角矩陣、對角矩陣等特殊矩陣在計算機中的壓縮存儲表示及地址計算公式；3．稀疏矩陣的三元組表示及轉置算法實現；4．稀疏矩陣的十字鏈表表示及相加算法實現；5．廣義表存儲結構表示及基本運算。本章學習導讀

2023/7/222

數組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數所元素本身也是一種線性表。5.1.1數組的定義

數組是大家都已經很熟悉的一種數據類型，幾乎所有高級語言程序設計中都設定了數組類型。

數組（Array）是由n(n>1)個相同類型數據元素a0，al，…ai…，an-1構成的有限序列。n是數組的長度。其中數組中的數據元素ai是一個數據結構，即ai可以是線性表中的一個元素，本身也可以是一個線性表，而線性子表中的每一個數據元素還可以再分解……。根據數組元素ai的組織形式不同，數組可以分為一維數組、二維數組以及多維（n維）數組。

5.1數組2023/7/223

有時也把一維數組稱為向量，二維數組稱為矩陣。在二維或多維數組中，每個數組元素都受到2個或n個關系的約束。當數組為n維時，其對應線性表中的每個元素又是一個線性表。在每個關系中，每個元素都有一個直接后繼。因此，就其單個關系而言，這n個關系中的每一個仍然是一種線性關系。數組中每個元素都是由一個值和一組下標來確定的。同線性表一樣，數組中的所有數據元素都必須屬于同一數據類型。元素下標的個數被稱為數組的維數。顯然，當維數為1時，數組就退化為定長的線性表。

2023/7/2241．一維數組

一維數組可以看成是一個線性表或一個向量，它在計算機內是存放在一塊連續的存儲單元中，適合于隨機查找。一維數組記為A[n]或A=(a0，al，…ai，…，an-1)

一維數組中，一旦a0的存儲地址、一個數據元素所占存儲單元數k確定，則ai的存儲地址LOC(ai)就可求出：

LOC(ai)=LOC(a0)+i*k(0≤i<n)

2．二維數組二維數組，又稱矩陣(matrix)。二維數組中的每一個元素又是一個定長的線性表（一維數組），都要受到兩個關系即行關系和列關系的約束，也就是每個元素都同屬于兩個線性表。例如，設A是一個有m行n列的二維數組，則A可以表示為：2023/7/225可以看成由m個行向量組成的向量，也可以看由n個列向量組成的向量。數組中的每個元素由元素值aij及一組下標（i，j）來確定。aij既屬于第i行的行向量，又屬于第j列的列向量。其中，ai=(ai,0ai,1…ai,n-1)(0≤i＜n)

可以認為Am*n=A，A是這樣的一維數組：

A=(a0，al，…，ai，…，am-1)

2023/7/226顯然，二維數組同樣滿足數組的定義。一個二維數組可以看作是每個數據元素都是相同類型的一維數組。以此類推，任何多維數組都可以看作一個線性表，這時線性表中的每個數據元素也是一個線性表。多維數組是特殊的線性表，是線性表的推廣。數組的性質：(1)數組中的數據元素數目固定。一旦定義了一個數組，其數據元素數目不再有增減變化。它屬于靜態分配存儲空間的數據結構。(2)數組中的數據元素必須具有相同的數據類型。(3)數組中的每個數據元素都有一組唯一的下標值。(4)數組是一種隨機存儲結構。可隨機存取數組中的任意數據元素。

2023/7/2275.1.2數組的基本操作

數組一旦被定義，它的維數和維界就不再改變。因此，除了結構的初始化和銷毀之外，數組的基本操作一般不會含有元素的插入或刪除等操作,數組只有訪問數組元素和修改元素值的操作。

(1)value(A，indexl，index2，…，indexd)：A是已存在的d維數組，indexl，index2，…，indexd是指定的d個下標值，且這些下標均不超過對應維的上界。其運算結果是返回由下標指定的A中的對應元素的值。(2)assign(A，e，indexl，index2，…，indexd)：A是已存在的d維數組，e為元素變量，indexl，index2，…，indexd是指定的d個下標值，且這些下標均未越界。其運算結果是將e的值賦給由下標指定的A中的對應元素。2023/7/228(3)disp(A)：輸出數組A的所有元素。在大多數程序設計語言中，取數組元素值操作value(A，indexl，index2，…，indexd)通常直接寫作A[indexl][index2]…[indexd]，而對數組元素的賦值操作assign(A，e，indexl，index2，…，indexd)寫作e=A[indexl][index2]…[indexd]，或者類似的形式。

2023/7/229

5.1.3數組的存儲結構

由于數組一般不作刪除或插入運算，所以一旦數組被定義后，數組中的元素個數和元素之間的關系就不再變動。通常采用順序存儲結構表示數組。對于一維數組，數組的存儲結構關系為:

LOC(ai)=LOC(a0)+i*k(0≤i<n)

對于二維數組，由于計算機的存儲單元是一維線性結構，如何用線性的存儲結構存放二維數組元素就有行/列次序問題。常用兩種存儲方法：以行序(rowmajororder)為主序的存儲方式和以列序(columnmajororder)為主序的存儲方式。

2023/7/2210

⑴行優先順序——將數組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數組為例，按行優先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

在PASCAL、C語言中，數組就是按行優先順序存儲的。⑵列優先順序——將數組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，A的m*n個元素按列優先順序存儲的線性序列為：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm

在FORTRAN語言中，數組就是按列優先順序存儲的。2023/7/2211

圖5-1二維數組的兩種存儲結構

對一個以行序為主序的計算機系統，當二維數組第一個數據元素a0,0的存儲地址LOC(a0,0)以及每個數據元素所占用的存儲單元k確定后，該二維數組中任一數據元素ai,j的存儲地址可由下式確定:LOC(ai,j)=LOC(a0,0)+(i×n+j)k其中n為每行中的列數。

2023/7/2212

圖5-1二維數組的兩種存儲結構

對一個以行序為主序的計算機系統，當二維數組第一個數據元素a0,0的存儲地址LOC(a0,0)以及每個數據元素所占用的存儲單元k確定后，該二維數組中任一數據元素ai,j的存儲地址可由下式確定:LOC(ai,j)=LOC(a0,0)+(i×n+j)k其中n為每行中的列數。

2023/7/2213

【例5-1】對于給定的二維數組floata[3][4]，計算：(1)數組a中的數組元素數目；(2)若數組a的起始地址為1000，且每個數組元素長度為32位(即4個字節)，數組元素a[2][3]的內存地址。【解】(1)由于C語言中數組的行、列下標值的下界均為0，該數組行上界為3-1=2，列上界為4-1=3，所以該數組的元素數目共有3*4=12個。(2)由于C語言采用行序為主序的存儲方式，有：

LOC(a2,3)=LOC(a0,0)+(i*n+j)*k=1000+(2*4+3)*4=10442023/7/2214

【例5-2】有m名學生，每人考n門功課，試寫出求任一學生總分數和任一課程總分數的數據結構和算法。【解】把學生的考試成績存放在m行n列的二維數組中，則第i(0≤i<m)行第j(0≤j<n)列中存放了第i個學生的第j門課程考試成績。即數據結構為：#defineM10//假設<學生人數>為10人#defineN3//假設<課程門數>為3intscore[M][N];//學生成績二維數組求第i名學生總分數的算法為：intstudent_sum(intscore[M][N],inti){intj,sum=0;for(j=0;j<N;j++)sum=sum+score[i][j];return(sum);}

2023/7/2215

求第j門課程總分數的算法為：intcourse_sum(intscore[M][N],intj){inti,sum=0;for(i=0;i<M;i++)sum=sum+score[i][j];return(sum);}

2023/7/2216

矩陣是數值計算程序設計中經常用到的數學模型，它是由m行和n列的數值構成（當m=n時稱為方陣）。在高級程序設計語言中，通常用二維數組表示矩陣。然而在數值分析過程中經常遇到一些比較特殊的矩陣，它們的階數很高，矩陣中元素數量很大，而且有很多元素的值相同或零值元素，如對稱矩陣、三角矩陣、帶狀矩陣和稀疏矩陣等。為了節省存儲空間并且加快處理速度，需要對這類矩陣進行壓縮存儲，壓縮存儲的原則是：不重復存儲相同元素；不存儲零值元素。5.2

矩陣的壓縮存儲

2023/7/2217

5.2.1特殊矩陣的壓縮存儲方法特殊矩陣是指非零元素或零元素的分布有一定規律的矩陣。主要形式有對稱矩陣、三角矩陣、對角矩陣等。1．對稱矩陣的壓縮存儲

對稱矩陣是一個n階方陣。若一個n階矩陣A中的元素滿足:ai,j=aj,I(0≤i，j≤n-1)，則稱A為n階對稱矩陣。15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1對稱矩陣2023/7/2218

在這個下三角矩陣中，第i行恰有i+1個元素，元素總數為：(i+1)=n(n+1)/2

由于對稱矩陣中的元素關于主對角線對稱，因此可以為每一對對稱的矩陣元素分配1個存儲空間，n階矩陣中的n×n個元素就可以被壓縮到n(n+1)/2

個元素的存儲空間中去。

稱一維數組sa[0..n(n+1)/2]為n階對稱矩陣A的壓縮存儲。其存儲對應關系如上圖:

對稱矩陣的壓縮存儲

2023/7/2219

2．三角矩陣的壓縮存儲三角矩陣也是一個n階方陣，有上三角和下三角矩陣。下(上)三角矩陣是主對角線以上（下）元素均為零的n階矩陣。設以一維數組sb[0..n(n+1)/2]作為n階三角矩陣B的存儲結構，仍采用按行存儲方案，則B中任一元素bi,j和sb[k]之間存在著如下對應關系：

其中，sb[n(n+1)/2]中存放常數c或0。

2023/7/2220

3．對角矩陣的壓縮存儲

對角方陣(或稱帶狀矩陣)是指所有的非零元素(簡稱非零元)都集中在以主對角線為中心的帶狀區域中，即除了主對角線上和緊靠著主對角線上下方若干條對角線上的元素外，所有其它元素皆為零的矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。下圖是一個具有3(1≤m＜n)條非零元素帶的n階對角矩陣。

具有3條非零對角線的對角矩陣

2023/7/2221

對于n階有m(m必為奇數，因為副對角線關于主對角線對稱)條非零元素帶的對角矩陣，只需存放對角區域內的所有非零元素即可。在n階對角矩陣A中，主對角線元素數最多（n個），然后向兩邊依次減少，每隔一條元素帶元素數就減少1個，最外端的對角線有n-(m-1)/2個元素，所以非零元素總數u為：

u=m×n-2×[(m-1)/2+((m-1)/2-1)+…+l]=m×n-(m2-1)/4

設以一維數組sa[u+l]為對角矩陣A的存儲結構，若按行存儲非零元，則A中任一元素ai,j和sa[k]之間存在著如下對應關系：

結論：對特殊矩陣的壓縮存儲實質上就是將二維矩陣中的部分元素按照某種方案排列到一維數組中，不同的排列方案也就對應不同的存儲方案。2023/7/2222

5.2.2稀疏矩陣的壓縮存儲方法

如果一個矩陣中有很多元素的值為零，即零元素的個數遠遠大于非零元素的個數時，稱該矩陣為稀疏矩陣。

根據存儲時所附加信息的不同，稀疏矩陣的順序存儲方法包括：三元組表示法、帶輔助行向量的二元組表示法和偽地址表示法，其中以三元組表示法最常用。三元組表示法就是在存儲非零元的同時，存儲該元素所對應的行下標和列下標。稀疏矩陣中的每一個非零元素由一個三元組(i，j，aij)唯一確定。矩陣中所有非零元素存放在由三元組組成的數組中。由線性表的兩種不同存儲結構可以得到稀疏矩陣壓縮的不同的存儲方法。

2023/7/2223

假設有一個6×7階稀疏矩陣A，其元素情況以及非零元對應的三元組表（以行序為主序）如圖所示。

(a)稀疏矩陣(b)三元組表示

三元組表中的第一行分別表示稀疏矩陣A的行數、列數和非零元的個數。顯然，非零元素的三元組是按行號遞增的順序、相同行號的三元組按列號遞增的順序排列的。2023/7/2224

1．三元組順序表

假設以行序為主序，且以一維數組作為三元組表的存儲結構，可以得到稀疏矩陣的一種壓縮存儲方法，稱為三元組順序表。三元組順序表的數據結構定義如下：#defineNUM100//矩陣中非零元素最大個數typedefstruct//三元組結構{intr,c;//行(列)號

ElemTyped;//元素值}tupletype;//三元組定義typedefstruct

{introws;//矩陣行數值

intcols;//矩陣列數值

intnums;//非零元素個數

tupletypedata[NUM];//三元組表

}table;//三元組順序表定義

2023/7/2225

1．稀疏矩陣的轉置運算轉置是矩陣中最簡單的一種運算。對于一個m×n的矩陣其轉置矩陣是一個n×m的矩陣，設為Bn×m且滿足ai,j=bj,i

即：a[i][j]=b[j][i]，其中：0≤i≤m-1，0≤j≤n-1即A的行是B的列，A的列是B的行。稀疏矩陣的三元組表2023/7/2226

三元組表示的稀疏矩陣的轉置常用的算法有以下兩種：1）矩陣的列序轉置（傳統的轉置算法）矩陣A是按行序為主序存儲的，若按列序為主序進行轉置就可以得到A陣的轉置矩陣B。假設矩陣A的三元組存入一維數組中，只要在數組中按三元組的列域cols的值開始掃描，從第0列至第n-1列，依序將三元組列域與行域之值對換，并順次存人數組mb中。算法如下：inttranspose(tablema,tablemb){inti,j,k=0,n,t;if(ma.nums==0)return(0)；//矩陣中無非零元素

m=ma.rows;//m為矩陣A的列數

n=ma.cols;//n為矩陣A的行數

t=ma.nums;//為矩陣中非零元素個數

mb.rows=n;//轉置矩陣B的列數

mb.cols;//轉置矩陣B的行數

mb.nums=t;//轉置矩陣中的非零元素個數

for(i=0;i<n;i++)//按矩陣A的列序掃描

2023/7/2227

for(j=0;j<t;j++)if(ma.data[j].c==i)//判斷第j個三元組是不是第i列的{mb.data[k].r=ma.data[j].c;mb.data[k].c=ma.data[j].r;mb.data[k++].d=ma.data[j].d;}return(1);//成功完成矩陣轉置}

以上算法的時間復雜度分析：若n為轉置矩陣的列數，t為矩陣中非零元素個數，則算法的時間花費主要在兩個循環上，所以若時間復雜度為O(n×t)。也就是說，時間的花費和矩陣A的列數和非零元素個數的乘積成正比。若用m×n的二維數組表示矩陣，則相應的矩陣轉置算法的循環為：for(i=0；i＜n；i++)for(j=0；j＜m；j++＝b[i][j]=a[j][i]；

此時，時間復雜度為O(m×n)。2023/7/2228

2）快速轉置算法：三元組順序表雖然節省了存儲空間，但時間復雜度比一般矩陣轉置的算法還要復雜，同時還有可能增加算是法的難度。因此，此算法僅適用于t<=m*n的情況。其算法思想為：對A掃描一次，按A第二列提供的列號一次確定位置裝入B的一個三元組。具體實施如下：一遍掃描先確定三元組的位置關系，二次掃描由位置關系裝入三元組。可見，位置關系是此種算法的關鍵。為了預先確定矩陣M中的每一列的第一個非零元素在數組T中應有的位置，需要先求得矩陣M中的每一列中非零元素的個數。因為矩陣M中第一列的第一個非零元素在數組T中應有的位置等于前一列第一個非零元素的位置加上前列非零元素的個數。2023/7/2229

為此，需要設置兩個一維數組num[0..n]和rpos[0..n]：num[0..n]：統計M中每列非零元素的個數。rpos[0..n]：M中的每列第一個非零元素在T中的位置。算法通過rpos數組建立位置對應關系：

rpos[0]=0；rpos[col]=rpos[col-1]+num[col-1]0＜col＜M.rows；例如圖5-4(a)所示的稀疏矩陣的三元組表對應的num[0..n-1]和rpos[0..n-1]如圖5-5所示。

（算法見教科書）圖5-5矩陣的num和rpos數組值2023/7/2230

快速轉置算法如下：

voidfasttranstri(tritupletableb,tritupletablea){intp,q,col,k;intnum[0..a.n],copt[0..a.n];b.m=a.n;b.n=a.m;b.t=a.t;if(b.t<=0)printf(“a=0”\n);for(col=1;col<=a.u;++col)num[col]=0;for(k=1;k<=a.t;++k)++num[a.data[k].j];cpot[0]=1;for(col=2;col<=a.t;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=a.t;++p){col=a.data[p].j;q=cpot[col];b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;++cpot[col];}}}2023/7/2231

2．行邏輯鏈接的順序表(帶行表的三元組)有時為了方便某些矩陣運算，在按行優先存儲的三元組中，加入一個行表來記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。當將行表作為三元組表的一個新增屬性加以描述時，就得到了稀疏矩陣的另一種順序存儲結構：帶行表的三元組表。稱這種“帶行鏈接信息”的三元組表為行邏輯鏈接的順序表。其類型描述如下：

#definemaxrow100typedefstruct{tripledata[maxsize];intrpos[maxrow];intn,m,t;}rtripletable2023/7/2232

下面討論兩個稀疏矩陣相乘的例子，容易看出這種表示方法的優越性：若設Q=M*N

其中，M是m1*n1矩陣，N是m2*n2矩陣。當n1=m2時有：

for(i=1;i<=m1;++i)for(j=1;j<=n2;++j){q[i][j]=0for(k=1;k<=n1;++k)q[i][j]+=m[i][k]*n[k][j];}

此算法的復雜度為O(m1*n1*n2)。2023/7/2233

3．

十字鏈表

稀疏矩陣中非零元的位置或個數經常變動時，三元組就不適合于作稀疏矩陣的存儲結構，此時，采用鏈表作為存儲結構更為恰當。十字鏈表為稀疏矩陣中的鏈接存儲中的一種較好的存儲方法，在該方法中，每一個非零元用一個結點表示，結點中除了表示非零元所在的行、列和值的三元組（i,j,v）外，還需增加兩個鏈域：行指針域（rptr），用來指向本行中下一個非零元素；列指針域（cptr），用來指向本列中下一個非零元素。稀疏矩陣中同一行的非零元通過向右的rptr指針鏈接成一個帶表頭結點的循環鏈表。同一列的非零元也通過cptr指針鏈接成一個帶表頭結點的循環鏈表。因此，每個非零元既是第i行循環鏈表中的一個結點，又是第j列循環鏈表中的一個結點，相當于處在一個十字交叉路口，故稱鏈表為十字鏈表。2023/7/2234

另外，為了運算方便，我們規定行、列循環鏈表的表頭結點和表示非零元的結點一樣，也定為五個域，且規定行、列、域值為0(因此，為了使表頭結點和表示非零元的表結點不發生混淆，三元組中，輸入行和列的下標不能從0開始!!!而必須從1開始)，并且將所有的行、列鏈表和頭結點一起鏈成一個循環鏈表。在行（列）表頭結點中，行、列域的值都為0，故兩組表頭結點可以共用，即第i行鏈表和第i列鏈表共用一個表頭結點，這些表頭結點本身又可以通過V域（非零元值域，但在表頭結點中為next，指向下一個表頭結點）相鏈接。另外，再增加一個附加結點（由指針hm指示，行、列域分別為稀疏矩陣的行、列數目），附加結點指向第一個表頭結點，則整個十字鏈表可由hm指針惟一確定。2023/7/2235

3．

十字鏈表用三元數組的結構來表示稀疏矩陣，在某些情況下可以節省存儲空間并加快運算速度。但在運算過程中，若稀疏矩陣的非零元素位置發生變化，必將會引起數組中元素的頻繁移動。這時，采用鏈式存儲結構(十字鏈表)表示三元組的線性表更為恰當。十字鏈表(orthogonallist)是稀疏矩陣的另一種存儲結構。它是用多重鏈表來存儲稀疏矩陣。十字鏈表適用于操作過程中非零元素的個數及元素位置變動頻繁的稀疏矩陣。十字鏈表為矩陣中的每一行設置一個單獨鏈表，同時也為每一列設置一個單獨鏈表。這樣，矩陣中的每個非零元就同時包含在兩個鏈表中（即所在行和所在列的鏈表）。這就大大降低了鏈表的長度，方便了算法中行方向和列方向的搜索，大大降低了算法的時間復雜度。2023/7/2236

對于一個m×n的稀疏矩陣，每個非零元用一個含有五個域的結點來表示。如圖5-6所示。其中各分量含義如下：(1)矩陣中非零元素的行號i；(2)矩陣中非零元素的列號j；(3)矩陣中非零元素的值value；(4)向右域right，用以鏈接同一行中下一個非零元素；(5)向下域down，用以鏈接同一列中下一個非零元素。長度，方便了算法中行方向和列方向的搜索，大大降低了算法的時間復雜度。即同一行的非零元素通過right域鏈接成一個鏈表，同一列的非零元素通過down域鏈接成一個鏈表，每一個非零元既是某個行鏈表中的結點，同時又是某個列鏈表中的結點。整個矩陣構成了一個十字交叉的鏈表。故稱為十字鏈表。

2023/7/2237

例如，假設稀疏矩陣B3ⅹ4為(a)結點結構(b)頭結點結構圖5-6十字鏈表結點結構對應矩陣B3ⅹ4的十字鏈表如圖5-7所示。為圖示方便清楚，把每個行列頭結點分別畫成兩個（一個行頭結點和一個列頭結點），而實際上，行頭結點hi(0≤i≤4)與列頭結點hi是存在于一個行列頭結點中的。

2023/7/2238

圖5-7稀疏矩陣的十字鏈表

2023/7/2239綜上所述，稀疏矩陣的十字鏈表表示共有三種線性鏈表：(1)由各行(列)表頭結點組成的線性鏈表，其結點之間用各結點的next域相鏈接。(2)由同一行中的非零元素結點組成的線性鏈表，其結點之間用各結點的right域相鏈接。(3)由同一列中的非零元素結點組成的線性鏈表，其結點之間用各結點的down域相鏈接。

2023/7/2240十字鏈表結點結構和頭結點的數據結構可定義如下：#defineM3//矩陣行數#defineN4//矩陣列數#defineMax((M)>(N)?(M)：(N))//矩陣行列較大者typedefstructmtxn{introw；intcol；structmtxn*right，*down；union{intvalue；structmtxn*next；}tag；}MatNode；

2023/7/22415.3

廣義表的定義

5.3.1廣義表的定義1．廣義表的定義廣義表也是線性表的推廣，是一種多層次的線性結構，線性表中的元素僅限于原子項，即不可以再分；而廣義表中的元素既可以是原子項，也可以是子表（另一個線性表）。主要用于人工智能領域的表處理語言LISP語言。

廣義表是n≥0個元素a1，a2，…，an的有限序列，其中每一個ai或者是原子，或者是一個子表。廣義表通常記為LS=(a1,a2,…,an)，其中LS為廣義表的名字，n為廣義表的長度，每一個ai為廣義表的元素。但在習慣中，一般用大寫字母表示廣義表，小寫字母表示原子。

若n=0時為空表。記作：L=()。

2023/7/2242

當廣義表L非空(n＞0)時，第一個數據元素a0被稱為廣義表的表頭(head)，其余數據元素組成的表(a1，…an-1)被稱為廣義表L的表尾(tail)，分別記為head(A)=a0，tail=(a1，…an-1)。

因此：一個廣義表是由表頭和表尾構成的。

2．廣義表舉例1）A=()A為空表，長度為0。

2）B=(e)B是一個只含有原子e的表，其長度為l；

。

3）C=(a，(b，c，d))

C是長度為2的廣義表，第一項為原子，第二項為子表。

4）D=(A，B，C)=(()，(e)，(a，(b，c，d)))

5）E=((a，(a，b)，((a，b)，c)))

E中只含有一個元素，該元素是一個表，E的長度為l。

6）F=(a，F)=(a，(a，(a，...)))

F是長度為2的廣義表，第一項為原子，第二項為它本身。

2023/7/22433．廣義表的表示方法（用次序關系和層次關系表示）（1）用L=(a1，a2，…，an)形式，其中每一個ai為原子或廣義表例如：A=(b,c)B=(a,A)E=(a,E)都是廣義表。（2）將廣義表中所有子表寫成原子形式，并利用圓括號嵌套例如，廣義表A、B、C可以描述為：A(b,c)B(a,A(b,c))E(a,E(a,E（…）))（3）將廣義表用樹和圖來描述（層次關系）上面提到的廣義表A、B、C的描述見圖5-8。

（次序關系）2023/7/2244廣義表中數據元素的最大層次為表的深度。數據元素的層次就是包括該元素韻括號對

的數目。例如廣義表G=(a，b，(c，(d)))中，數據元素a，b在第一層，數據元素c在第二層，數據元素d在第三層，廣義表G的深度為3。

（次序關系）圖5-8廣義表的圖形表示

從圖5-8可以看出：廣義表的圖形表示像倒著畫的一棵樹，樹根結點代表整個廣義表，各層樹枝結點代表相應的子表，樹葉結點代表單元素或空表（如A表）。

2023/7/2245

4．廣義表的深度

一個廣義表的深度是指該廣義表展開后所含括號的層數。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3;廣義表兼有線性結構和層次結構的特性，歸納如下：(1)廣義表中的數據元素有固定的相對次序；(2)廣義表的長度定義為最外層括弧中包含的數據元素個數；(3)廣義表的深度定義為廣義表書寫形式中括弧的最大重數，因此空表的深度為1，因為一個單元素不是廣義表，所以從定義上講沒有深度可言，但可以認為它的深度為0；(4)廣義表可被其它廣義表所共享。例如上述例子中廣義表B同時也是廣義表

D中的一個子表；(5)廣義表可以是一個自遞歸的表。例如上述例子中的廣義表

F，自遞歸的廣義表的長度是個有限值，而深度為無限值。

2023/7/2246

5．廣義表的分類（1）線性表：元素全部是原子的廣義表。（2）純表：與樹對應的廣義表，見圖5-8的(c)

、(d)、(e)。（3）再入表：與圖對應的廣義表(允許結點共享)，（4）遞歸表：允許有遞歸關系的廣義表，例如E=(a,E)。

這四種表的關系滿足：遞歸表再入表

純表

線性表

再入表2023/7/2247

5.3.2廣義表的存儲結構由于廣義表的元素類型不一定相同，表中的數據元素可以是單元素（原子項），也可以是廣義表，因此，難以用順序結構存儲表中元素，通常采用鏈接存儲方法來存儲廣義表中元素，并稱之為廣義鏈表。需要兩種結構的結點：(1)表結點：用以表示廣義表。由三個域組成：標志域tag、指向表頭的指針域sublist和指向下一個結點的指針域link。如圖5-9(a)所示。(2)原子結點：用以表示原子項。由三個域組成：標志域tag、值域data和指向下一個元素結點的指針域link。如圖5-9(b)所示。

2023/7/2248每個數據元素都可用表結點或原子結點表示。它們的主要區別在于從不同的角度反映廣義表的構成。

例如，廣義表C的鏈表存儲結構如圖5-10所示。

圖5-10廣義表(a,(b,c,d))的鏈表存儲結構圖

二叉樹2023/7/2249廣義表的鏈式結構描述如下：typedefcharElemType;typedefstructglnode{inttag;union{ElemTypedata;structglnode*sublist;}val;structglnode*link;}GListNode;

可將一個廣義表看成一棵樹，為了方便存儲，通常將其轉換成一棵二叉樹。廣義表C轉換成二叉樹過程如圖5-11所示：

2023/7/2250廣義表C圖5-11廣義表的轉換過程

2023/7/22515.3.3廣義表的基本操作廣義表的基本操作主要有：求廣義表的長度和深度、向廣義表插入元素和從廣義表中查找或刪除元素、建立廣義表的存儲結構、輸出廣義表和復制廣義表等。由于廣義表是一種遞歸的數據結構，所以對廣義表的運算一般采用遞歸的算法。

1．求廣義表的長度在廣義表中，同一層次的每個結點是通過1ink域鏈接起來的，可把它看做是由1ink域鏈接起來的單鏈表。求廣義表的長度就變成求單鏈表的長度，則它的深度可以遞歸求出。2023/7/2252求廣義表長度的遞歸算法如下：

intGListLength(GListNode*h)//h為一個廣義表頭結點的指針{intn=0;h=h->val.sublist;//h指向廣義表的第一個元素

while(h!=NULL){n++;h=h->link;}returnn;}2．求廣義表的深度廣義表深度的遞歸定義是：它等于所有子表中表的最大深度加1。若一個表為空或僅由單元素所組成，則深度為l。求廣義表深度的遞歸函數GListDepth()如下：

2023/7/22531h為空表

GListDepth(h)=

max{GListDepth(sh)|sh為h的子表}+1其它情況

intGListDepth(GListNode*h){//h為廣義表頭結點的sublist域值或為不帶頭結點的廣義表

intmax=0,dep;//max中存放子表的最大深度

while(h!=NULL)//遍歷表中的每一個結點{if(h->tag==1)//只需要求出子表深度即可，單元素深度為0{dep=GListDepth(h->val.sublist);//遞歸調用求出子表的深度

if(dep>max)//讓max始終為同一層所求過的子表中深度的最大值

max=dep;}h=h->link;//使h指向同一層的下一個結點}

returnmax+l;//返回表的深度}

2023/7/22543．建立廣義表的存儲結構假設廣義表以單鏈表的形式存儲，廣義表的元素類型elemtype為字符型char，廣義表由鍵盤輸入，假定全部為字母，輸入格式為：元素之間用逗號分隔，表元素的起止符號分別為左、右圓括號，空表在其圓括號內使用一個“#”字符表示，最后使用一個分號作為整個廣義表的結束。例如“(a，(b，c，d))”，就是一個符合上述規定的廣義表格式（注意：不包括引號）。建立廣義表存儲結構的算法同樣是一個遞歸算法。

2023/7/2255

建立廣義表的算法如下：GListNode*GListCreat(char*s){GListNode*h;charch;ch=*s;//取一個掃描字符

s++;//串指針后移一位

if(ch!=’\0’)//串未結束判斷{h=(GListNode*)malloc(sizeof(GListNode))；//創建一個新結點

if(ch==’(’)//當前字符為左括號時{h->tag=l;//新結點作為表頭結點

h->val.sublist=GListCreat(s);//遞歸構造子表并鏈到表頭結點}

elseif(ch==’)’)//遇到’)’字符，子表為空

h=NULL;else{h->tag=0;//新結點作為單元素結點

h->val.data=ch;}}2023/7/2256

elseh=NULL;//串結束，子表為空ch=*s;//取下一個掃描字符s++;//串指針后移一位if(h!=NULL)//串未結束判斷

if(ch=’,’)//當前字符為

h->link=GListCreat(s);//遞歸構造后續子表

else//串結束

h->link=NULL;//處理表的最后一個元素returnh;//返回廣義表指針}2023/7/22574．輸出廣義表以h作為帶表頭附加結點的廣義表的表頭指針，打印輸出該廣義表時，需要對子表進行遞歸調用。當h結點為表元素結點時，應首先輸出作為一個表的起始符號的左括號，然后再輸出以h->sublist為表頭指針的表；當h結點為單元素結點時，則應輸出該元素的值。當以h->sublist為表頭指針的表輸出完畢后，應在其最后輸出一個作為表終止符的右括號。當h結點輸出結束后，若存在后繼結點，則應首先輸出一個逗號作為分隔符，然后再遞歸輸出由h->link指針所指向的后繼表。

2023/7/2258算法描述如下：

voidDispGList(GlistNodeh)//h為一個廣義表的頭結點指針{if(h!=NULL)//表不為空判斷{if(h->tag==1)//為表結點時{printf(“(“);//輸出左括號

if(h->val.sublist==NULL)printf(“”);//輸出空子表

elseDispGList(h->val.sublist);//遞歸輸出子表}

else//為原子結點時

printf(“%c”,h->val.data);//輸出元素值

if(h->tag==1)//為表結點時

printf(“)”);//輸出右括號

if(h->link!=NULL){printf(“,”);DispGList(h->link);//遞歸輸出后續表的內容}}}

2023/7/22595．廣義表的復制復制一個廣義表的過程如下：對于廣義表的頭結點*p，若為空，則返回空指針；若為表結點，則遞歸復制子表；否則，復制單元素結點，然后再遞歸復制后續表。返回復制后的廣義表鏈表的指針。其算法如下：

GListNode*GListCopy(GListNode*p)/*p為被被復制的廣義表的頭結點指針*/{GListNode*q;if(p==NULL)returnNULL；q=(GListNode*)malloc(sizeof(GListNode));q->tag=p->tag;if(p->tag==1)q->val.sublist=GL