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

教學(xué)目的：掌握數(shù)組和廣義表的定義、運(yùn)算及存儲(chǔ)結(jié)構(gòu)教學(xué)難點(diǎn)：矩陣的壓縮存儲(chǔ)2023/7/221

本章主要介紹數(shù)組的概念及多維數(shù)組在計(jì)算機(jī)中的存放，特殊矩陣的壓縮存儲(chǔ)及相應(yīng)運(yùn)算，廣義表的概念和存儲(chǔ)結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。通過(guò)本章學(xué)習(xí)，要求掌握如下內(nèi)容：1．多維數(shù)組的定義及在計(jì)算機(jī)中的存儲(chǔ)表示；2．對(duì)稱矩陣、三角矩陣、對(duì)角矩陣等特殊矩陣在計(jì)算機(jī)中的壓縮存儲(chǔ)表示及地址計(jì)算公式；3．稀疏矩陣的三元組表示及轉(zhuǎn)置算法實(shí)現(xiàn)；4．稀疏矩陣的十字鏈表表示及相加算法實(shí)現(xiàn)；5．廣義表存儲(chǔ)結(jié)構(gòu)表示及基本運(yùn)算。本章學(xué)習(xí)導(dǎo)讀

2023/7/222

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

數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級(jí)語(yǔ)言程序設(shè)計(jì)中都設(shè)定了數(shù)組類型。

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

5.1數(shù)組2023/7/223

有時(shí)也把一維數(shù)組稱為向量，二維數(shù)組稱為矩陣。在二維或多維數(shù)組中，每個(gè)數(shù)組元素都受到2個(gè)或n個(gè)關(guān)系的約束。當(dāng)數(shù)組為n維時(shí)，其對(duì)應(yīng)線性表中的每個(gè)元素又是一個(gè)線性表。在每個(gè)關(guān)系中，每個(gè)元素都有一個(gè)直接后繼。因此，就其單個(gè)關(guān)系而言，這n個(gè)關(guān)系中的每一個(gè)仍然是一種線性關(guān)系。數(shù)組中每個(gè)元素都是由一個(gè)值和一組下標(biāo)來(lái)確定的。同線性表一樣，數(shù)組中的所有數(shù)據(jù)元素都必須屬于同一數(shù)據(jù)類型。元素下標(biāo)的個(gè)數(shù)被稱為數(shù)組的維數(shù)。顯然，當(dāng)維數(shù)為1時(shí)，數(shù)組就退化為定長(zhǎng)的線性表。

2023/7/2241．一維數(shù)組

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

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

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

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

可以認(rèn)為Am*n=A，A是這樣的一維數(shù)組：

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

2023/7/226顯然，二維數(shù)組同樣滿足數(shù)組的定義。一個(gè)二維數(shù)組可以看作是每個(gè)數(shù)據(jù)元素都是相同類型的一維數(shù)組。以此類推，任何多維數(shù)組都可以看作一個(gè)線性表，這時(shí)線性表中的每個(gè)數(shù)據(jù)元素也是一個(gè)線性表。多維數(shù)組是特殊的線性表，是線性表的推廣。數(shù)組的性質(zhì)：(1)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定。一旦定義了一個(gè)數(shù)組，其數(shù)據(jù)元素?cái)?shù)目不再有增減變化。它屬于靜態(tài)分配存儲(chǔ)空間的數(shù)據(jù)結(jié)構(gòu)。(2)數(shù)組中的數(shù)據(jù)元素必須具有相同的數(shù)據(jù)類型。(3)數(shù)組中的每個(gè)數(shù)據(jù)元素都有一組唯一的下標(biāo)值。(4)數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。

2023/7/2275.1.2數(shù)組的基本操作

數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組的基本操作一般不會(huì)含有元素的插入或刪除等操作,數(shù)組只有訪問(wèn)數(shù)組元素和修改元素值的操作。

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

2023/7/229

5.1.3數(shù)組的存儲(chǔ)結(jié)構(gòu)

由于數(shù)組一般不作刪除或插入運(yùn)算，所以一旦數(shù)組被定義后，數(shù)組中的元素個(gè)數(shù)和元素之間的關(guān)系就不再變動(dòng)。通常采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組。對(duì)于一維數(shù)組，數(shù)組的存儲(chǔ)結(jié)構(gòu)關(guān)系為:

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

對(duì)于二維數(shù)組，由于計(jì)算機(jī)的存儲(chǔ)單元是一維線性結(jié)構(gòu)，如何用線性的存儲(chǔ)結(jié)構(gòu)存放二維數(shù)組元素就有行/列次序問(wèn)題。常用兩種存儲(chǔ)方法：以行序(rowmajororder)為主序的存儲(chǔ)方式和以列序(columnmajororder)為主序的存儲(chǔ)方式。

2023/7/2210

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

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

在FORTRAN語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。2023/7/2211

圖5-1二維數(shù)組的兩種存儲(chǔ)結(jié)構(gòu)

對(duì)一個(gè)以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)，當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素a0,0的存儲(chǔ)地址LOC(a0,0)以及每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元k確定后，該二維數(shù)組中任一數(shù)據(jù)元素ai,j的存儲(chǔ)地址可由下式確定:LOC(ai,j)=LOC(a0,0)+(i×n+j)k其中n為每行中的列數(shù)。

2023/7/2212

圖5-1二維數(shù)組的兩種存儲(chǔ)結(jié)構(gòu)

對(duì)一個(gè)以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)，當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素a0,0的存儲(chǔ)地址LOC(a0,0)以及每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元k確定后，該二維數(shù)組中任一數(shù)據(jù)元素ai,j的存儲(chǔ)地址可由下式確定:LOC(ai,j)=LOC(a0,0)+(i×n+j)k其中n為每行中的列數(shù)。

2023/7/2213

【例5-1】對(duì)于給定的二維數(shù)組floata[3][4]，計(jì)算：(1)數(shù)組a中的數(shù)組元素?cái)?shù)目；(2)若數(shù)組a的起始地址為1000，且每個(gè)數(shù)組元素長(zhǎng)度為32位(即4個(gè)字節(jié))，數(shù)組元素a[2][3]的內(nèi)存地址。【解】(1)由于C語(yǔ)言中數(shù)組的行、列下標(biāo)值的下界均為0，該數(shù)組行上界為3-1=2，列上界為4-1=3，所以該數(shù)組的元素?cái)?shù)目共有3*4=12個(gè)。(2)由于C語(yǔ)言采用行序?yàn)橹餍虻拇鎯?chǔ)方式，有：

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

【例5-2】有m名學(xué)生，每人考n門(mén)功課，試寫(xiě)出求任一學(xué)生總分?jǐn)?shù)和任一課程總分?jǐn)?shù)的數(shù)據(jù)結(jié)構(gòu)和算法?！窘狻堪褜W(xué)生的考試成績(jī)存放在m行n列的二維數(shù)組中，則第i(0≤i<m)行第j(0≤j<n)列中存放了第i個(gè)學(xué)生的第j門(mén)課程考試成績(jī)。即數(shù)據(jù)結(jié)構(gòu)為：#defineM10//假設(shè)<學(xué)生人數(shù)>為10人#defineN3//假設(shè)<課程門(mén)數(shù)>為3intscore[M][N];//學(xué)生成績(jī)二維數(shù)組求第i名學(xué)生總分?jǐn)?shù)的算法為：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門(mén)課程總分?jǐn)?shù)的算法為：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

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

矩陣的壓縮存儲(chǔ)

2023/7/2217

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

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

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

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

個(gè)元素的存儲(chǔ)空間中去。

稱一維數(shù)組sa[0..n(n+1)/2]為n階對(duì)稱矩陣A的壓縮存儲(chǔ)。其存儲(chǔ)對(duì)應(yīng)關(guān)系如上圖:

對(duì)稱矩陣的壓縮存儲(chǔ)

2023/7/2219

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

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

2023/7/2220

3．對(duì)角矩陣的壓縮存儲(chǔ)

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

具有3條非零對(duì)角線的對(duì)角矩陣

2023/7/2221

對(duì)于n階有m(m必為奇數(shù)，因?yàn)楦睂?duì)角線關(guān)于主對(duì)角線對(duì)稱)條非零元素帶的對(duì)角矩陣，只需存放對(duì)角區(qū)域內(nèi)的所有非零元素即可。在n階對(duì)角矩陣A中，主對(duì)角線元素?cái)?shù)最多（n個(gè)），然后向兩邊依次減少，每隔一條元素帶元素?cái)?shù)就減少1個(gè)，最外端的對(duì)角線有n-(m-1)/2個(gè)元素，所以非零元素總數(shù)u為：

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

設(shè)以一維數(shù)組sa[u+l]為對(duì)角矩陣A的存儲(chǔ)結(jié)構(gòu)，若按行存儲(chǔ)非零元，則A中任一元素ai,j和sa[k]之間存在著如下對(duì)應(yīng)關(guān)系：

結(jié)論：對(duì)特殊矩陣的壓縮存儲(chǔ)實(shí)質(zhì)上就是將二維矩陣中的部分元素按照某種方案排列到一維數(shù)組中，不同的排列方案也就對(duì)應(yīng)不同的存儲(chǔ)方案。2023/7/2222

5.2.2稀疏矩陣的壓縮存儲(chǔ)方法

如果一個(gè)矩陣中有很多元素的值為零，即零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)大于非零元素的個(gè)數(shù)時(shí)，稱該矩陣為稀疏矩陣。

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

2023/7/2223

假設(shè)有一個(gè)6×7階稀疏矩陣A，其元素情況以及非零元對(duì)應(yīng)的三元組表（以行序?yàn)橹餍颍┤鐖D所示。

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

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

1．三元組順序表

假設(shè)以行序?yàn)橹餍?，且以一維數(shù)組作為三元組表的存儲(chǔ)結(jié)構(gòu)，可以得到稀疏矩陣的一種壓縮存儲(chǔ)方法，稱為三元組順序表。三元組順序表的數(shù)據(jù)結(jié)構(gòu)定義如下：#defineNUM100//矩陣中非零元素最大個(gè)數(shù)typedefstruct//三元組結(jié)構(gòu){intr,c;//行(列)號(hào)

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

{introws;//矩陣行數(shù)值

intcols;//矩陣列數(shù)值

intnums;//非零元素個(gè)數(shù)

tupletypedata[NUM];//三元組表

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

2023/7/2225

1．稀疏矩陣的轉(zhuǎn)置運(yùn)算轉(zhuǎn)置是矩陣中最簡(jiǎn)單的一種運(yùn)算。對(duì)于一個(gè)m×n的矩陣其轉(zhuǎn)置矩陣是一個(gè)n×m的矩陣，設(shè)為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

三元組表示的稀疏矩陣的轉(zhuǎn)置常用的算法有以下兩種：1）矩陣的列序轉(zhuǎn)置（傳統(tǒng)的轉(zhuǎn)置算法）矩陣A是按行序?yàn)橹餍虼鎯?chǔ)的，若按列序?yàn)橹餍蜻M(jìn)行轉(zhuǎn)置就可以得到A陣的轉(zhuǎn)置矩陣B。假設(shè)矩陣A的三元組存入一維數(shù)組中，只要在數(shù)組中按三元組的列域cols的值開(kāi)始掃描，從第0列至第n-1列，依序?qū)⑷M列域與行域之值對(duì)換，并順次存人數(shù)組mb中。算法如下：inttranspose(tablema,tablemb){inti,j,k=0,n,t;if(ma.nums==0)return(0)；//矩陣中無(wú)非零元素

m=ma.rows;//m為矩陣A的列數(shù)

n=ma.cols;//n為矩陣A的行數(shù)

t=ma.nums;//為矩陣中非零元素個(gè)數(shù)

mb.rows=n;//轉(zhuǎn)置矩陣B的列數(shù)

mb.cols;//轉(zhuǎn)置矩陣B的行數(shù)

mb.nums=t;//轉(zhuǎn)置矩陣中的非零元素個(gè)數(shù)

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

2023/7/2227

for(j=0;j<t;j++)if(ma.data[j].c==i)//判斷第j個(gè)三元組是不是第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);//成功完成矩陣轉(zhuǎn)置}

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

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

2）快速轉(zhuǎn)置算法：三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算是法的難度。因此，此算法僅適用于t<=m*n的情況。其算法思想為：對(duì)A掃描一次，按A第二列提供的列號(hào)一次確定位置裝入B的一個(gè)三元組。具體實(shí)施如下：一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組?？梢?jiàn)，位置關(guān)系是此種算法的關(guān)鍵。為了預(yù)先確定矩陣M中的每一列的第一個(gè)非零元素在數(shù)組T中應(yīng)有的位置，需要先求得矩陣M中的每一列中非零元素的個(gè)數(shù)。因?yàn)榫仃嘙中第一列的第一個(gè)非零元素在數(shù)組T中應(yīng)有的位置等于前一列第一個(gè)非零元素的位置加上前列非零元素的個(gè)數(shù)。2023/7/2229

為此，需要設(shè)置兩個(gè)一維數(shù)組num[0..n]和rpos[0..n]：num[0..n]：統(tǒng)計(jì)M中每列非零元素的個(gè)數(shù)。rpos[0..n]：M中的每列第一個(gè)非零元素在T中的位置。算法通過(guò)rpos數(shù)組建立位置對(duì)應(yīng)關(guān)系：

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

（算法見(jiàn)教科書(shū)）圖5-5矩陣的num和rpos數(shù)組值2023/7/2230

快速轉(zhuǎn)置算法如下：

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．行邏輯鏈接的順序表(帶行表的三元組)有時(shí)為了方便某些矩陣運(yùn)算，在按行優(yōu)先存儲(chǔ)的三元組中，加入一個(gè)行表來(lái)記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。當(dāng)將行表作為三元組表的一個(gè)新增屬性加以描述時(shí)，就得到了稀疏矩陣的另一種順序存儲(chǔ)結(jié)構(gòu)：帶行表的三元組表。稱這種“帶行鏈接信息”的三元組表為行邏輯鏈接的順序表。其類型描述如下：

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

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

其中，M是m1*n1矩陣，N是m2*n2矩陣。當(dāng)n1=m2時(shí)有：

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];}

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

3．

十字鏈表

稀疏矩陣中非零元的位置或個(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)的循環(huán)鏈表。因此，每個(gè)非零元既是第i行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，又是第j列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，相當(dāng)于處在一個(gè)十字交叉路口，故稱鏈表為十字鏈表。2023/7/2234

另外，為了運(yùn)算方便，我們規(guī)定行、列循環(huán)鏈表的表頭結(jié)點(diǎn)和表示非零元的結(jié)點(diǎn)一樣，也定為五個(gè)域，且規(guī)定行、列、域值為0(因此，為了使表頭結(jié)點(diǎn)和表示非零元的表結(jié)點(diǎn)不發(fā)生混淆，三元組中，輸入行和列的下標(biāo)不能從0開(kāi)始!!!而必須從1開(kāi)始)，并且將所有的行、列鏈表和頭結(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指針惟一確定。2023/7/2235

3．

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

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

2023/7/2237

例如，假設(shè)稀疏矩陣B3ⅹ4為(a)結(jié)點(diǎn)結(jié)構(gòu)(b)頭結(jié)點(diǎn)結(jié)構(gòu)圖5-6十字鏈表結(jié)點(diǎn)結(jié)構(gòu)對(duì)應(yīng)矩陣B3ⅹ4的十字鏈表如圖5-7所示。為圖示方便清楚，把每個(gè)行列頭結(jié)點(diǎn)分別畫(huà)成兩個(gè)（一個(gè)行頭結(jié)點(diǎn)和一個(gè)列頭結(jié)點(diǎn)），而實(shí)際上，行頭結(jié)點(diǎn)hi(0≤i≤4)與列頭結(jié)點(diǎn)hi是存在于一個(gè)行列頭結(jié)點(diǎn)中的。

2023/7/2238

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

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

2023/7/2240十字鏈表結(jié)點(diǎn)結(jié)構(gòu)和頭結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可定義如下：#defineM3//矩陣行數(shù)#defineN4//矩陣列數(shù)#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．廣義表的定義廣義表也是線性表的推廣，是一種多層次的線性結(jié)構(gòu)，線性表中的元素僅限于原子項(xiàng)，即不可以再分；而廣義表中的元素既可以是原子項(xiàng)，也可以是子表（另一個(gè)線性表）。主要用于人工智能領(lǐng)域的表處理語(yǔ)言LISP語(yǔ)言。

廣義表是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ě)字母表示原子。

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

2023/7/2242

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

因此：一個(gè)廣義表是由表頭和表尾構(gòu)成的。

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

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

。

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

C是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為子表。

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

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

E中只含有一個(gè)元素，該元素是一個(gè)表，E的長(zhǎng)度為l。

6）F=(a，F(xiàn))=(a，(a，(a，...)))

F是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。

2023/7/22433．廣義表的表示方法（用次序關(guān)系和層次關(guān)系表示）（1）用L=(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（…）))（3）將廣義表用樹(shù)和圖來(lái)描述（層次關(guān)系）上面提到的廣義表A、B、C的描述見(jiàn)圖5-8。

（次序關(guān)系）2023/7/2244廣義表中數(shù)據(jù)元素的最大層次為表的深度。數(shù)據(jù)元素的層次就是包括該元素韻括號(hào)對(duì)

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

（次序關(guān)系）圖5-8廣義表的圖形表示

從圖5-8可以看出：廣義表的圖形表示像倒著畫(huà)的一棵樹(shù)，樹(shù)根結(jié)點(diǎn)代表整個(gè)廣義表，各層樹(shù)枝結(jié)點(diǎn)代表相應(yīng)的子表，樹(shù)葉結(jié)點(diǎn)代表單元素或空表（如A表）。

2023/7/2245

4．廣義表的深度

一個(gè)廣義表的深度是指該廣義表展開(kāi)后所含括號(hào)的層數(shù)。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3;廣義表兼有線性結(jié)構(gòu)和層次結(jié)構(gòu)的特性，歸納如下：(1)廣義表中的數(shù)據(jù)元素有固定的相對(duì)次序；(2)廣義表的長(zhǎng)度定義為最外層括弧中包含的數(shù)據(jù)元素個(gè)數(shù)；(3)廣義表的深度定義為廣義表書(shū)寫(xiě)形式中括弧的最大重?cái)?shù)，因此空表的深度為1，因?yàn)橐粋€(gè)單元素不是廣義表，所以從定義上講沒(méi)有深度可言，但可以認(rèn)為它的深度為0；(4)廣義表可被其它廣義表所共享。例如上述例子中廣義表B同時(shí)也是廣義表

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

F，自遞歸的廣義表的長(zhǎng)度是個(gè)有限值，而深度為無(wú)限值。

2023/7/2246

5．廣義表的分類（1）線性表：元素全部是原子的廣義表。（2）純表：與樹(shù)對(duì)應(yīng)的廣義表，見(jiàn)圖5-8的(c)

、(d)、(e)。（3）再入表：與圖對(duì)應(yīng)的廣義表(允許結(jié)點(diǎn)共享)，（4）遞歸表：允許有遞歸關(guān)系的廣義表，例如E=(a,E)。

這四種表的關(guān)系滿足：遞歸表再入表

純表

線性表

再入表2023/7/2247

5.3.2廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素類型不一定相同，表中的數(shù)據(jù)元素可以是單元素（原子項(xiàng)），也可以是廣義表，因此，難以用順序結(jié)構(gòu)存儲(chǔ)表中元素，通常采用鏈接存儲(chǔ)方法來(lái)存儲(chǔ)廣義表中元素，并稱之為廣義鏈表。需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：(1)表結(jié)點(diǎn)：用以表示廣義表。由三個(gè)域組成：標(biāo)志域tag、指向表頭的指針域sublist和指向下一個(gè)結(jié)點(diǎn)的指針域link。如圖5-9(a)所示。(2)原子結(jié)點(diǎn)：用以表示原子項(xiàng)。由三個(gè)域組成：標(biāo)志域tag、值域data和指向下一個(gè)元素結(jié)點(diǎn)的指針域link。如圖5-9(b)所示。

2023/7/2248每個(gè)數(shù)據(jù)元素都可用表結(jié)點(diǎn)或原子結(jié)點(diǎn)表示。它們的主要區(qū)別在于從不同的角度反映廣義表的構(gòu)成。

例如，廣義表C的鏈表存儲(chǔ)結(jié)構(gòu)如圖5-10所示。

圖5-10廣義表(a,(b,c,d))的鏈表存儲(chǔ)結(jié)構(gòu)圖

二叉樹(shù)2023/7/2249廣義表的鏈?zhǔn)浇Y(jié)構(gòu)描述如下：typedefcharElemType;typedefstructglnode{inttag;union{ElemTypedata;structglnode*sublist;}val;structglnode*link;}GListNode;

可將一個(gè)廣義表看成一棵樹(shù)，為了方便存儲(chǔ)，通常將其轉(zhuǎn)換成一棵二叉樹(shù)。廣義表C轉(zhuǎn)換成二叉樹(shù)過(guò)程如圖5-11所示：

2023/7/2250廣義表C圖5-11廣義表的轉(zhuǎn)換過(guò)程

2023/7/22515.3.3廣義表的基本操作廣義表的基本操作主要有：求廣義表的長(zhǎng)度和深度、向廣義表插入元素和從廣義表中查找或刪除元素、建立廣義表的存儲(chǔ)結(jié)構(gòu)、輸出廣義表和復(fù)制廣義表等。由于廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，所以對(duì)廣義表的運(yùn)算一般采用遞歸的算法。

1．求廣義表的長(zhǎng)度在廣義表中，同一層次的每個(gè)結(jié)點(diǎn)是通過(guò)1ink域鏈接起來(lái)的，可把它看做是由1ink域鏈接起來(lái)的單鏈表。求廣義表的長(zhǎng)度就變成求單鏈表的長(zhǎng)度，則它的深度可以遞歸求出。2023/7/2252求廣義表長(zhǎng)度的遞歸算法如下：

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

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

2023/7/22531h為空表

GListDepth(h)=

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

intGListDepth(GListNode*h){//h為廣義表頭結(jié)點(diǎn)的sublist域值或?yàn)椴粠ь^結(jié)點(diǎn)的廣義表

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

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

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

max=dep;}h=h->link;//使h指向同一層的下一個(gè)結(jié)點(diǎn)}

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

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

2023/7/2255

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

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

if(ch!=’\0’)//串未結(jié)束判斷{h=(GListNode*)malloc(sizeof(GListNode))；//創(chuàng)建一個(gè)新結(jié)點(diǎn)

if(ch==’(’)//當(dāng)前字符為左括號(hào)時(shí){h->tag=l;//新結(jié)點(diǎn)作為表頭結(jié)點(diǎn)

h->val.sublist=GListCreat(s);//遞歸構(gòu)造子表并鏈到表頭結(jié)點(diǎn)}

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

h=NULL;else{h->tag=0;//新結(jié)點(diǎn)作為單元素結(jié)點(diǎn)

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

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

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

h->link=GListCreat(s);//遞歸構(gòu)造后續(xù)子表

else//串結(jié)束

h->link=NULL;//處理表的最后一個(gè)元素returnh;//返回廣義表指針}2023/7/22574．輸出廣義表以h作為帶表頭附加結(jié)點(diǎn)的廣義表的表頭指針，打印輸出該廣義表時(shí)，需要對(duì)子表進(jìn)行遞歸調(diào)用。當(dāng)h結(jié)點(diǎn)為表元素結(jié)點(diǎn)時(shí)，應(yīng)首先輸出作為一個(gè)表的起始符號(hào)的左括號(hào)，然后再輸出以h->sublist為表頭指針的表；當(dāng)h結(jié)點(diǎn)為單元素結(jié)點(diǎn)時(shí)，則應(yīng)輸出該元素的值。當(dāng)以h->sublist為表頭指針的表輸出完畢后，應(yīng)在其最后輸出一個(gè)作為表終止符的右括號(hào)。當(dāng)h結(jié)點(diǎn)輸出結(jié)束后，若存在后繼結(jié)點(diǎn)，則應(yīng)首先輸出一個(gè)逗號(hào)作為分隔符，然后再遞歸輸出由h->link指針?biāo)赶虻暮罄^表。

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

voidDispGList(GlistNodeh)//h為一個(gè)廣義表的頭結(jié)點(diǎn)指針{if(h!=NULL)//表不為空判斷{if(h->tag==1)//為表結(jié)點(diǎn)時(shí){printf(“(“);//輸出左括號(hào)

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

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

else//為原子結(jié)點(diǎn)時(shí)

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

if(h->tag==1)//為表結(jié)點(diǎn)時(shí)

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

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

2023/7/22595．廣義表的復(fù)制復(fù)制一個(gè)廣義表的過(guò)程如下：對(duì)于廣義表的頭結(jié)點(diǎn)*p，若為空，則返回空指針；若為表結(jié)點(diǎn)，則遞歸復(fù)制子表；否則，復(fù)制單元素結(jié)點(diǎn)，然后再遞歸復(fù)制后續(xù)表。返回復(fù)制后的廣義表鏈表的指針。其算法如下：

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