《數(shù)據(jù)結(jié)構(gòu)教程》課件第5章

第5章數(shù)組與廣義表5.1數(shù)組的概念與存儲結(jié)構(gòu)5.2特殊矩陣的壓縮存儲5.3稀疏矩陣5.4廣義表

5.1數(shù)組的概念與存儲結(jié)構(gòu)

5.1.1數(shù)組的基本概念

數(shù)組是我們很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以將它看做線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是：結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。一維數(shù)組[a1,a2,…,an]由固定的n個元素構(gòu)成，其本身就是一種線性表結(jié)構(gòu)。對于二維數(shù)組：數(shù)組中的每一個數(shù)據(jù)元素受到兩個下標(biāo)關(guān)系的約束，但可看作是“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，即每一維關(guān)系仍然具有線性特性，而整個結(jié)構(gòu)則呈非線性。同樣，三維數(shù)組可看作是“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組這種特殊線性表。依此類推，n維數(shù)組則是由n-1維數(shù)組定義的。

因此，n維數(shù)組是一種“同構(gòu)”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組中的每一個元素類型相同結(jié)構(gòu)也一致。n維數(shù)組是線性表在維數(shù)上的拓展，即線性表中的元素又可以是一個線性表。從數(shù)據(jù)結(jié)構(gòu)關(guān)系的角度看，n維數(shù)組中每個數(shù)據(jù)元素都受到n個關(guān)系的約束。但在每個關(guān)系中，數(shù)據(jù)元素都有一個直接前驅(qū)(除去第一個元素)和一個直接后繼(除去最后一個元素)。因此就單個關(guān)系而言，這n個關(guān)系仍然是線性關(guān)系。數(shù)組具有以下性質(zhì)：

(1)數(shù)組中的元素個數(shù)固定。一旦定義了一個數(shù)組，其元素個數(shù)不再有增減變化。

(2)數(shù)組中每個數(shù)據(jù)元素都具有相同的數(shù)據(jù)類型。

(3)數(shù)組中每個元素都有一組唯一的下標(biāo)與之對應(yīng)，并且數(shù)組元素的下標(biāo)具有上、下界約束且下標(biāo)有序。

(4)數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)，可隨機(jī)存取數(shù)組中的任意元素。

也即，數(shù)組是一種元素個數(shù)固定的線性表，當(dāng)維數(shù)大于1時可以看做是線性表的推廣。5.1.2數(shù)組的存儲結(jié)構(gòu)

由于計算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此多維數(shù)組的存儲就必須按某種方式進(jìn)行降維處理，最終將所有的數(shù)組元素排成一個線性序列。由于高維數(shù)組是由低維數(shù)組定義，并最終由一維數(shù)組定義，因此可通過遞推關(guān)系將多維數(shù)組的數(shù)據(jù)元素轉(zhuǎn)化為線性序列來存儲。

對于一維數(shù)組，假定每個數(shù)據(jù)元素占用k個存儲單元，一旦第一個數(shù)據(jù)元素a0的存儲地址LOC(a0)確定，則一維數(shù)組中的任一數(shù)據(jù)元素ai的存儲地址LOC(ai)就可以由下面式(5-1)求出。LOC(ai)=LOC(a0)+i×k

(5-1)該式說明一維數(shù)組中任一數(shù)據(jù)元素的存儲地址都可以直接計算得到。也即，一維數(shù)組中數(shù)據(jù)元素都可以直接存取。因此，一維數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)。由于二維乃至多維數(shù)組都可降至一維數(shù)組定義，因此，二維至多維數(shù)組也都滿足隨機(jī)存取特性。

對于二維數(shù)組，有以行為主序(行先變化)和以列為主序(列先變化)的兩種存儲方法(如圖5-1所示)。設(shè)二維數(shù)組中的每個數(shù)據(jù)元素占用k個存儲單元，m和n為二維數(shù)組的行數(shù)和列數(shù)，則二維數(shù)組以行為主序的數(shù)據(jù)元素ai,j的存儲地址計算公式(行、列下標(biāo)均從0開始)為：LOC(ai,j)?=?LOC(a0,0)?+?(i×n+j)×k(5-2)圖5-1二維數(shù)組的兩種存儲方式圖5-2二維數(shù)組中ai,j位置示意圖二維數(shù)組以列為主序的數(shù)據(jù)元素ai,j存儲地址計算公式為LOC(ai,j)?=?LOC(a0,0)?+?(j×m+i)×k

上述公式和結(jié)論可推廣至三維或多維數(shù)組。對三維數(shù)組Amnp即m×n×p數(shù)組，以行為主序的數(shù)組元素ai,j,l的存儲地址計算公式為LOC(ai,j,l)=LOC(a0,0,0)+[i×n×p+j×p+l]×k

可以將三維數(shù)組看作一個三維空間，如圖5-3所示，對ai,j,l來說，前面已經(jīng)存放了i個面，每個面上有m×p個元素，對第i個面則類同于圖5-2，即前面有j行，每行有p個元素，第j行有l(wèi)個元素。圖5-3三維數(shù)組示意圖以上討論均假定數(shù)組各維的下界為0，更一般的情況下各維的上、下界是任意指定的。以二維數(shù)組為例，假定二維數(shù)組的行下界為c1，行上界為d1，列下界為c2，列上界為d2，則二維數(shù)組元素ai,j以行為主序的存儲地址計算公式為LOC(ai,j)

=

LOC(ac1,c2)+

[(i-c1)×(d2-c2+1)+(j-c2)]×k

(5-4)

二維數(shù)組元素ai,j以列為主序的存儲地址計算公式為

(5-5)

例5.1

已知C語言二維數(shù)組定義如下

floata[8][5];

且每個float型數(shù)組元素均占用4個字節(jié)的內(nèi)存空間。

(1)求二維數(shù)組a的元素個數(shù)。

(2)假定數(shù)組a的起始存儲地址為1000，求以行為主序的數(shù)組元素a[6][3]的存儲地址。

【解】(1)由數(shù)組a定義floata[8][5]可知，8和5即為各維的長度，所以二維數(shù)組a的元素個數(shù)為：8×5=40。

(2)已知m=8、n=5，由式(5-2)可知，a[6][3]的計算如下(C語言數(shù)組的行、列下界均為0)：

LOC(a6,3)=LOC(a0,0)+(i×n+j)×k=1000+(6×5+3)×4=1132

例5.2

設(shè)計一個算法，對有n個元素的一維數(shù)組a，使其數(shù)組元素循環(huán)右移k位，要求算法盡量少使用輔助存儲空間。

【解】由于只允許使用一個變量輔助實(shí)現(xiàn)數(shù)組元素的移動，因此將該題轉(zhuǎn)化為每次將數(shù)組元素循環(huán)右移一位并且進(jìn)行k次來實(shí)現(xiàn)。故需用兩重for循環(huán)：外層的for循環(huán)控制k次移位，內(nèi)層的for循環(huán)控制整個數(shù)組元素循環(huán)右移一位。數(shù)組元素循環(huán)右移一位的示意圖如圖5-4所示。圖5-4數(shù)組元素循環(huán)右移一位示意圖算法如下：

voidMovek(inta[],intk,intn)

{ //對數(shù)組a的n個元素循環(huán)右移k次

inti,j,x;

for(i=1;i<=k;i++) //循環(huán)右移k次

{

x=a[n-1];

for(j=n-2;j>=0;j--)

a[j+1]=a[j];

a[0]=x;

}

} 5.2特殊矩陣的壓縮存儲

5.2.1對稱矩陣在一個n階方陣A中，若元素滿足以下性質(zhì)：ai,

j=aj,i (0≤i,j＜n)假設(shè)以一維數(shù)組B(下標(biāo)由0～)作為n階對稱矩陣A的存儲結(jié)構(gòu)，在B中只存儲對稱矩陣A的下三角元素ai,j(i≥j)，其存儲示意圖如圖5-5所示。圖5-5對稱矩陣壓縮存儲示意圖由于上三角元素ai,j等于下三角元素aj,i，因此可以將上式中的行、列下標(biāo)互換就得到對稱矩陣上三角中任一元素ai,

j存儲于一維數(shù)組B中的位置k。因此，對稱矩陣A中任一元素ai,j在一維數(shù)組B中的存儲位置k與其下標(biāo)i、j之間存在著如下對應(yīng)關(guān)系：

當(dāng)i≥j時當(dāng)i＜j時(5-6)圖5-6給出了5階矩陣及它壓縮存儲于一維數(shù)組的情況。圖5-65階對稱矩陣及它的壓縮存儲5.2.2三角矩陣

以主對角線來劃分，三角矩陣分為上三角矩陣和下三角矩陣兩種。上三角矩陣是指矩陣的下三角(不包括主對角線)中的元素均為常數(shù)c或0的n階矩陣，下三角矩陣則恰好相反。三角矩陣的示意圖如圖5-7所示。圖5-7三角矩陣示意圖當(dāng)三角矩陣采用壓縮存儲時，除了和對稱矩陣一樣，只存儲其下三角或上三角中的元素外，再加上一個存儲常數(shù)c的存儲空間，即三角矩陣中的n2個元素壓縮存儲到個單元中。

1.下三角矩陣

下三角矩陣的壓縮存儲示意圖如圖5-8所示，即存放完矩陣下三角中的元素之后，緊接著存放主對角線上方的常數(shù)c，因為是同一個常數(shù)，故只存放一個即可。由圖5-8可知，下三角矩陣中的ai,j(i≥j)在一維數(shù)組中的存儲位置關(guān)系與對稱矩陣中的下三角元素ai,j完全相同，因此，下三角矩陣中的任意一元素ai,j壓縮存儲在一維數(shù)組中的位置k與其下標(biāo)i、j之間的關(guān)系為

當(dāng)i≥j時當(dāng)i＜j時(5-7)圖5-8下三角矩陣壓縮存儲示意圖圖5-9上三角矩陣壓縮存儲示意圖由此得到上三角矩陣中的任意一個元素ai,j壓縮存儲在一維數(shù)組中的位置k與其下標(biāo)i、j之間的關(guān)系為：當(dāng)i≤j時當(dāng)i≤j時(5-8)5.2.3對角矩陣

對角矩陣又稱帶狀矩陣，對角矩陣的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域內(nèi)，即除了主對角線上和主對角線兩側(cè)的若干對角線上的元素外，其他所有元素的值均為0。最常見的三對角帶狀矩陣如圖5-10所示。圖5-10三對角帶狀矩陣示意圖三對角帶狀矩陣的壓縮存儲方法是：將帶狀區(qū)域的非零元素按行存儲在一維數(shù)組中。在三對角帶狀矩陣中，除了第一行和最后一行只有兩個非零元素外，其余各行均有三個非零元素。因此，所需壓縮存儲的一維數(shù)組空間大小為2+2+3×(n-2)。圖5-10的三對角帶狀矩陣壓縮存儲到一維數(shù)組的示意圖如圖5-11所示。圖5-11三對角帶狀矩陣壓縮存儲示意圖三對角帶狀矩陣中的非零元素ai,j壓縮存儲到一維數(shù)組的位置k與其下標(biāo)i、j之間的關(guān)系分析如下：

(1)主對角線左下角的對角線上元素，其下標(biāo)具有i=j+1關(guān)系，而此時的位置k為

k=3i-1 (當(dāng)i=j+1時)

(2)主對角線上元素下標(biāo)具有i=j關(guān)系，而此時的位置k為

k=3i (當(dāng)i=j時)

(3)主對角線右上角的對角線上元素下標(biāo)具有i=j-1關(guān)系，而此時的位置k為

k=3i+1 (當(dāng)i=j-1時)

綜合(1)、(2)、(3)并參考圖5-10和5-11，我們得到三對角帶狀矩陣中非零元素ai,j壓縮存儲到一維數(shù)組的位置k與與其下標(biāo)i、j之間的關(guān)系為

k=2i+j (0≤i＜n且i-1≤j≤i+1)(5-9) 5.3稀疏矩陣

5.3.1稀疏矩陣的三元組表示

對一個m×n的稀疏矩陣，其非零元素的個數(shù)t<<m×n，如果采用常規(guī)的存儲方法來存儲矩陣的每一個元素的話，將會造成內(nèi)存的很大浪費(fèi)。為了節(jié)省存儲空間，稀疏矩陣的存儲必須采用壓縮存儲方式，即只存儲非零元素。但是稀疏矩陣中的非零元素其分布無規(guī)律可循，所以除了存儲非零元素的值外，還必須同時存儲它所在的行和列位置，這樣才能找到它。也即，每一個非零元素ai,j由一個三元組(i,j,ai,j)唯一確定，其中i和j分別代表非零元素ai,j所在的行和列位置。除了用一個三元組(i,j,ai,j)表示一個非零元素ai,j之外，還需要記下稀疏矩陣的行數(shù)m、列數(shù)n和非零元素個數(shù)t，即也形成一個三元組(m,n,t)。若將所有三元組按行(或按列)的優(yōu)先順序排列，則得到一個數(shù)據(jù)元素為三元組的線性表，并將三元組(m,n,t)放置于該線性表的第一個位置。我們將這種線性表的順序存儲結(jié)構(gòu)稱為三元組表。圖5-12給出了一個稀疏矩陣及其三元組表的示意圖。圖5-12稀疏矩陣M及其三元組表示意圖一般來說，稀疏矩陣的三元組存儲是以行為主序的。在這種方式下，三元組表中的行域i值遞增有序，而對相同的i值列域j值也遞增有序。

三元組表的順序存儲結(jié)構(gòu)定義如下：

typedefstruct

{

inti; //行號

intj; //列號

intv; //非零元素值

}TNode; //三元組類型

typedefstruct

{

intm; //矩陣行數(shù)

intn; //矩陣列數(shù)

intt; //矩陣中非零元素個數(shù)

TNodedata[MAXSIZE]; //三元組表

}TSMatrix; //三元組表類型

1.為存儲于二維數(shù)組的稀疏矩陣建立三元組表存儲

假定m×n的稀疏矩陣已存儲在二維數(shù)組中，現(xiàn)以行為主序來掃描二維數(shù)組，將所有的非零元素存入到三元組表中。算法實(shí)現(xiàn)如下：

voidCreatMat(TSMatrix*p,int*a,intm,intn)

{//p指向三元組表，a指向存儲稀疏矩陣的二維數(shù)組，m、n為矩陣的行數(shù)和列數(shù)

inti,j;

p->m=m;

p->n=n;

p->t=0; //p->t初始指向三元組表data的第一個三元組位置0

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

if(a[i][j]!=0) //將非零元素存儲于三元組表data中

{

p->data[p->t].i=i;

p->data[p->t].j=j;

p->data[p->t].v=a[i][j];

p->t++; //下標(biāo)加1以便三元組表a存放下一個非零元素

}

}

}

2.矩陣轉(zhuǎn)置

轉(zhuǎn)置是一種最簡單的矩陣運(yùn)算。對一個m×n的矩陣A，它的轉(zhuǎn)置矩陣為n×m的矩陣B，且ai,j=bj,i(0≤i＜m,0≤j＜n)，即A的行是B的列、A的列是B的行。圖5-13給出了圖5-12(a)稀疏矩陣M所對應(yīng)的轉(zhuǎn)置矩陣三元組表。

分析圖5-12(c)和圖5-13可知，只要將三元組表中的i域和j域的值交換，然后再按以行為主序的原則重新排列三元組表即可。但是，我們希望在交換行、列值的過程中就同時確定該三元組在行為主序的三元組表中的位置，而不必在交換結(jié)束后再重新去排列三元組表。對此，有下面兩種處理方法。圖5-13圖5-12(a)中矩陣M轉(zhuǎn)置后的三元組表

1)按列序遞增轉(zhuǎn)置法

由于交換后的列變?yōu)榱诵?，即以列為主序在原三元組表a中進(jìn)行查找，才能使交換后生成的三元組表b做到以行為主序。因此，應(yīng)從三元組表a的第一行開始依次按三元組表a中的j域(即列)值由小到大進(jìn)行選擇，將選中的三元組i和j交換后送入三元組表b中，直到a中的三元組全部放入b中為止。按這種順序生成的三元組表b則已經(jīng)是行為主序。算法實(shí)現(xiàn)如下：

voidTranTat(TSMatrix*a,TSMatrix*b)

{/*在三元組表的存儲方式下，實(shí)現(xiàn)矩陣轉(zhuǎn)置，

a和b分別是指向轉(zhuǎn)置前后兩個不同三元組表的指針*/

intk,p,q;//k指向三元組表a的列號；p、q分別為指示三元組a和b的下標(biāo)

b->m=a->m;

b->n=a->n;

b->t=a->t;

if(b->t!=0) //當(dāng)三元組表不為空時

{

q=0; //由三元組b的第一個三元組位置0開始

for(k=0;k<a->n;k++) //對三元組表a按列下標(biāo)由小到大掃描

{

for(p=0;p<a->t;p++) //按表長t掃描整個三元組表a

if(a->data[p].j==k) //找到列下標(biāo)與k相同的三元組

{ //將其復(fù)制到三元組表b中

b->data[q].i=a->data[p].j;

b->data[q].j=a->data[p].i;

b->data[q].v=a->data[p].v;

q++;//三元組b表的存放位置加1，準(zhǔn)備存放下一個三元組

}

}

}

}

該算法的時間耗費(fèi)主要在兩重for循環(huán)上，其時間復(fù)雜度為O(a->n×a->t)。

2)快速轉(zhuǎn)置法

按列序遞增轉(zhuǎn)置算法效率不高的原因在于二重for循環(huán)的重復(fù)掃描，而快速轉(zhuǎn)置法則只掃描一遍。快速轉(zhuǎn)置法的基本思想是：在三元組表a中依次取出每一個三元組，并使其準(zhǔn)確地放置在轉(zhuǎn)置后的三元組表b中最終應(yīng)該放置的位置上，當(dāng)順序取完三元組表a中的所有三元組時，轉(zhuǎn)置后的三元組表b也就形成，而無需再調(diào)整b中三元組的位置。這種方法的實(shí)現(xiàn)需要預(yù)先計算以下數(shù)據(jù)：

(1)三元組表a中每一列非零元素的個數(shù)，它也是轉(zhuǎn)置后三元組表b每一行非零元素的個數(shù)。

(2)三元組表a中每一列的第一個非零元素在三元組表b中正確的存放位置，它也是轉(zhuǎn)置后每一行第一個非零元素在三元組b中正確的存放位置。

為了避免混淆，我們將行、列序號與數(shù)組的下標(biāo)統(tǒng)一起來，即用第0行、第0列來表示原第一行、第一列，依此類推。

設(shè)矩陣A(在三元組表a中行數(shù)為a->n)每一列k(即轉(zhuǎn)置后矩陣B的每一行k)的第一個非零元素在三元組表b中的正確位置為pot[k](0≤k＜a->n)，則對三元組表a進(jìn)行轉(zhuǎn)置時，只需將三元組按列號k放到三元組表b的b->data[pot[k]]中即可，然后pot[k]增1以指示下一個列號為k的三元組在表b中的存放位置。于是有：(5-10)pot[0]=0pot[k]=pot[k-1]+第k-1列非零元素的個數(shù)為了統(tǒng)計第k-1列非零元素的個數(shù)可以再引入一個數(shù)組，但為了節(jié)省存儲空間，我們可以將第k-1列的非零元素個數(shù)暫時記錄于pot[k]中，也即pot[1]～pot[a->n](注意k值此時可取到a->n)實(shí)際存放的分別是第0列到第a->n-1列非零元素的個數(shù)，而pot[0]存放的卻是第0列的第一個非零元素應(yīng)該放置在三元組表b中的位置(下標(biāo))，這樣k值可按由1遞增到a->n-1的次序，依次求出表a中每一列第一個非零元素應(yīng)該在表b中的存放位置，即：pot[k]=pot[k-1]+pot[k]

(5-11)注意，式(5-11)中的pot[k-1]此時已是按順序求出的第k-1列第一個非零元素在表b中的存放位置，而賦值號“=”右側(cè)的pot[k]則是暫存的第k-1列非零元素個數(shù)。因此，pot[k-1]+pot[k]正好是待求的第k列第一個非零元素在表b中的存放位置，并將這個位置值賦給pot[k]。

圖5-14(b)、(c)給出了圖5-14(a)所示矩陣M的pot數(shù)組變化情況。在圖5-14(b)中，pot[0]為第0列第一個非零元素在表b中的存放位置，而pot[1]～pot[4]則為第0列～第3列的非零元素的個數(shù)。在圖5-14(c)中，pot[0]～pot[3]為根據(jù)(5-11)式求得的第0列～第3列非零元素在表b中的起始存放位置，此時pot[4]已經(jīng)無用了。圖5-14pot數(shù)組變化示意圖快速轉(zhuǎn)置算法如下：

voidFastTranTat(TSMatrix*a,TSMatrix*b)

{

inti,k,pot[MAXSIZE];

b->m=a->m;

b->n=a->n;

b->t=a->t;

if(b->t!=0) //當(dāng)三元組表不為空時

{

for(k=1;k<=a->n;k++)

pot[k]=0; //pot數(shù)組初始化

for(i=0;i<a->t;i++)

{

k=a->data[i].j;

pot[k+1]=pot[k+1]+1; //統(tǒng)計第k列非零元素的個數(shù)并送入pot[k+1]

}

pot[0]=0; //第0列第一個非零元素在表b中的存放位置

for(k=1;k<a->n;k++)

pot[k]=pot[k-1]+pot[k]; /*求第1～第n-1列第一個非零元素

在表b中的存放位置*/

for(i=0;i<a->t;i++)

{

k=a->data[i].j;

b->data[pot[k]].i=a->data[i].j;

b->data[pot[k]].j=a->data[i].i;

b->data[pot[k]].v=a->data[i].v;

pot[k]=pot[k]+1; /*第k列的存放位置加1，

準(zhǔn)備存放第k列的下一個三元組*/

}

}

}5.3.2稀疏矩陣的十字鏈表表示

三元組表可以看作是稀疏矩陣的順序存儲，但是在進(jìn)行某些矩陣運(yùn)算時，比如矩陣的加法、減法和乘法，運(yùn)算的結(jié)果將使非零元素的個數(shù)以及非零元素的位置發(fā)生較大的變化，這必將引起數(shù)據(jù)的大量移動。這種情況下如果還用順序存儲的三元組表來存放稀疏矩陣就不太合適了，而采用鏈?zhǔn)酱鎯Y(jié)構(gòu)來表示三元組表則更為恰當(dāng)。下面我們介紹稀疏矩陣的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)——十字鏈表。用十字鏈表來表示稀疏矩陣的基本上思想是：將每個非零元素存儲為一個結(jié)點(diǎn)，而每個結(jié)點(diǎn)由5個域組成，其結(jié)構(gòu)如圖5-15所示；其中row、col和v分別表示該非零元素所在的行、列和非零元素值。指針right(向右)用以鏈接同一行中的下一個非零元素，指針down(向下)用以鏈接同一列中下一個非零元素。圖5-14(a)的矩陣M所對應(yīng)的十字鏈表存儲示意圖如圖5-16所示。圖5-15十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)圖5-16稀疏矩陣的十字鏈表示意圖注意，圖5-16中最上面一行的頭結(jié)點(diǎn)H0、H1和H2與最左面一列的頭結(jié)點(diǎn)H0、H1和H2實(shí)際上是同一個頭結(jié)點(diǎn)，分開表示主要是使十字鏈表示意更加清晰。

由圖5-16可知，稀疏矩陣中每一行的非零元素結(jié)點(diǎn)按其列號由小到大依次由right指針鏈成一個帶表頭結(jié)點(diǎn)的循環(huán)行鏈表，同樣，每一列中的非零元素結(jié)點(diǎn)按其行號由小到大依次由down指針鏈成一個帶頭結(jié)點(diǎn)的循環(huán)列鏈表。因此，每個非零元素ai,j既是第i行循環(huán)鏈表中的一個結(jié)點(diǎn)，又是第j列循環(huán)鏈表中的一個結(jié)點(diǎn)。鏈表頭結(jié)點(diǎn)中的row和col置為-1，指針right指向該行鏈表的第一個非零元素結(jié)點(diǎn)，指針down指向該列鏈表的第一個非零元素結(jié)點(diǎn)。為了方便地找到每一行或每一列，則將所有的頭結(jié)點(diǎn)鏈起來形成一個頭結(jié)點(diǎn)循環(huán)鏈表。非零元素結(jié)點(diǎn)的值域是datatype類型，而表頭結(jié)點(diǎn)則需要一個指針類型以方便頭結(jié)點(diǎn)之間的鏈接，為了使整個十字鏈表結(jié)構(gòu)的結(jié)點(diǎn)一致，我們規(guī)定頭結(jié)點(diǎn)和其他結(jié)點(diǎn)一樣具有相同的結(jié)構(gòu)，因此值域采用一個共用體來表示，改進(jìn)后的結(jié)點(diǎn)結(jié)構(gòu)如圖5-17所示。圖5-17十字鏈表中非零元素和表頭共用的結(jié)點(diǎn)結(jié)構(gòu)這樣，我們得到結(jié)點(diǎn)的結(jié)構(gòu)定義如下：

typedefstructnode

{

introw,col; //row和col為非零元素所在的行和列

structnode*right,*down;

//right和down為非零元素結(jié)點(diǎn)的行、列指針

union

{

datatypev; //v為非零元素的值

structnode*next;//next為頭結(jié)點(diǎn)鏈表指針

}tag;

}MNode; //十字鏈表結(jié)點(diǎn)類型下面我們介紹創(chuàng)建一個稀疏矩陣的十字鏈表算法。首先輸入矩陣的行數(shù)、列數(shù)和非零元個數(shù)m、n和t，然后輸入t個非零元素的三元組值(i,j,ai,j)。

該算法的思想是：首先對頭結(jié)點(diǎn)鏈表初始化，使之成為不含非零元素的循環(huán)鏈表。然后每輸入一個三元組(i,j,ai,j)則將其結(jié)點(diǎn)按其列號的大小插入到第i個行鏈表中去，同時也按其行號的大小將該結(jié)點(diǎn)插入到第j個列鏈表中去。在算法中使用指針數(shù)組*h[i]來指向第i行(第i列)鏈表的頭結(jié)點(diǎn)，這樣可以在建立十字鏈表中隨機(jī)訪問任何一行或列。建立稀疏矩陣的十字鏈表算法如下：

voidCreatMat(MNode**mh,MNode*h[])

{//mh為指向頭結(jié)點(diǎn)循環(huán)鏈表的頭指針，*h[]為存儲頭結(jié)點(diǎn)的指針數(shù)組

MNode*p,*q; //p和q為暫存指針

inti,j,k,m,n,t,v,max; //設(shè)非零元素的值v為整型

printf("Inputm,n,t:");

scanf("%d,%d,%d",&m,&n,&t);

*mh=(MNode*)malloc(sizeof(MNode));//創(chuàng)建頭結(jié)點(diǎn)循環(huán)鏈表的頭結(jié)點(diǎn)

(*mh)->row=m; //存儲矩陣的行數(shù)

(*mh)->col=n; //存儲矩陣的列數(shù)

p=*mh; //指針p指向頭結(jié)點(diǎn)*mh

if(m>n)

max=m; //如果行數(shù)大于列數(shù)則將行數(shù)值賦給max

else

max=n; //如果列數(shù)大于行數(shù)則將列數(shù)值賦給max

for(i=0;i<max;i++) //采用尾插法創(chuàng)建頭結(jié)點(diǎn)h[0]、h[1]、…、h[max-1]的循環(huán)鏈表

{

h[i]=(MNode*)malloc(sizeof(MNode));

h[i]->down=h[i]; //初始時down指向頭結(jié)點(diǎn)自身(即列為空)

h[i]->right=h[i]; //初始時right指向頭結(jié)點(diǎn)自身(即行為空)

h[i]->row=-1;

h[i]->col=-1;

p->tag.next=h[i]; //將頭結(jié)點(diǎn)鏈接起來形成一個鏈表

p=h[i];

}

p->tag.next=*mh; /*將最后插入的頭結(jié)點(diǎn)(即鏈尾)中的next指針再指向鏈頭形成頭結(jié)點(diǎn)循環(huán)鏈表*/

for(k=0;k<t;k++)

{

printf("Inputi,j,v:");

scanf("%d,%d,%d",&i,&j,&v); //輸入一個三元組

p=(MNode*)malloc(sizeof(MNode));

p->row=i;

p->col=j;

p->tag.v=v;

//以下實(shí)現(xiàn)將*P插入到第i行鏈表中去，且按列號有序

q=h[i];

while(q->right!=h[i]&&q->right->col<j) //按列號找到插入位置

q=q->right;

p->right=q->right; //完成插入

q->right=p;

//以下實(shí)現(xiàn)將*p插入到第j列鏈表中去，且按行號有序

q=h[j];

while(q->down!=h[j]&&q->down->row<i) //按行號找到插入位置

q=q->down;

p->down=q->down; //完成插入

q->down=p;

}

}圖5-18未輸入非零元素時的十字鏈表示意圖上述算法中，建立頭結(jié)點(diǎn)循環(huán)鏈表的時間復(fù)雜度為O(max)。由于每個結(jié)點(diǎn)插入時都要在鏈表中尋找插入位置，因此每個結(jié)點(diǎn)插入到相應(yīng)的行鏈表或列鏈表總的時間復(fù)雜度為O(t×max)。該算法對三元組的輸入順序沒有要求。如果我們按行或按列為主序來輸入三元組，則每次都將新結(jié)點(diǎn)插入到鏈表的尾部，這樣對算法改進(jìn)后可使時間復(fù)雜度為O(max+t)(t為非零元素個數(shù))。 5.4廣義表

5.4.1廣義表的基本概念

在第2章中我們把線性表定義為n≥0個元素a1,a2,…,an的有限序列，線性表的每個元素ai

(1≤i≤n)只能是結(jié)構(gòu)上不可再分割的單元素，而不能是其他結(jié)構(gòu)。如果放寬這個限制，允許表中的元素既可以是單元素，又可以是另外一個表，則稱這樣的表為廣義表。

廣義表是n(n≥0)個數(shù)據(jù)元素a1,a2,…,ai,…,an的有序序列，一般記作：LS=(a1,a2,…,ai,…,an)顯然，廣義表的定義是遞歸的，因為在描述廣義表時又用到了廣義表自身的概念。廣義表與線性表的主要區(qū)別在于：線性表的每個元素都是結(jié)構(gòu)上不可再分的單元素，而廣義表的每個元素既可以是單個元素，又可以是一個廣義表。為清楚起見，通常用大寫字母表示廣義表，用小寫字母表示單元素。廣義表用括號“()”括起來，括號內(nèi)的數(shù)據(jù)元素用逗號“,”隔開。下面是一些廣義表的例子：

(1)?A=() A是長度為0的空表。

(2)?B=(e) B是一個長度為1且元素為單元素的廣義表。

(3)?C=(a,(b,c))??C是長度為2的廣義表，它的第一個元素為單元素a，第二個元素為子表(b,c)。

(4)?D=(A,B,C)??D是長度為3的廣義表，其中3個元素均為子表。顯然，若將各子表帶入后可得到D=((),(e),(a,(b,c)))。

(5)??E=(a,E)E是一個長度為2的遞歸廣義表，相當(dāng)于一個無限的廣義表E=(a,(a,(a,…)…))。

(6)?F=(A)F是長度為1的廣義表，其中的一個元素為子表。顯然將子表帶入后得到F=(())。注意，A=()是一個無任何元素的空表，但F=(A)=(())則不是空表，它有一個元素，只不過這個元素是一個空表而已。因此，A的長度為0而F的長度為1。

根據(jù)上述廣義表的定義和例子可知廣義表具有如下特點(diǎn)：

(1)廣義表是一種線性結(jié)構(gòu)，其長度為最外層包含的元素個數(shù)。

(2)廣義表中的元素可以是子表，而子表的元素還可以是子表，因此廣義表是一種多層次結(jié)構(gòu)。

(3)一個廣義表也可以為其他廣義表所共享，例如，在D=(A，B，C)中，A、B、C就是D的子表。

(4)廣義表可以是遞歸的，即廣義表也可以是其自身的一個廣義表，例如E=(a,E)。廣義表的這些特點(diǎn)對于它的使用價值和應(yīng)用效果起到了很大作用。廣義表可以看成是線性表的推廣，因此線性表只是廣義表的一個特例。由于廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下它可以兼容線性表、數(shù)組、樹和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)，如將二維數(shù)組的每行(或每列)作為子表處理時，二維數(shù)組即為廣義表。由于廣義表不僅集中了線性表、數(shù)組、樹和圖等常見數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可以有效地利用存儲空間，因此在計算機(jī)的許多領(lǐng)域都得到了廣泛的應(yīng)用。廣義表的主要操作有求表的長度；查找表中滿足條件的元素；在表中指定位置進(jìn)行插入或刪除等。另外，求廣義表的深度、取廣義表的表頭或表尾等也都是廣義表重要的基本操作。由于廣義表結(jié)構(gòu)比線性表復(fù)雜，因此廣義表各種運(yùn)算的實(shí)現(xiàn)也不如線性表簡單。

所謂廣義表的深度，是指廣義表中所包含括號的重數(shù)，它是廣義表的一種重要量度。前面例子中，B的深度為1，C的深度為2，D的深度為3。另外要注意的是空表的深度也為1。取表頭Head(LS)的操作是：取出的表頭為非空廣義表的第一個元素，該元素可以是單元素也可以是一個子表。取表尾Tail(LS)的操作是：取出的表尾為除去表頭元素之外，由其余元素構(gòu)成的表。注意，表尾一定是一個表而不會是一個單元素。對前面的例子有：

Head(B)=e Tail(B)=()

Head(C)=a Tail(C)=((b,c))

Head(D)=A Tail(D)=(B,C)

Head(E)=a Tail(E)=(E)

Head(F)=A Tail(F)=()5.4.2廣義表的存儲結(jié)構(gòu)

1.頭尾表示法

根據(jù)表頭和表尾的定義，當(dāng)廣義表非空時可分解為表頭和表尾兩個部分。反之，一對確定的表頭和表尾則可唯一地確定一個廣義表。頭尾表示法就是根據(jù)這一性質(zhì)設(shè)計而成的一種存儲方法。

由于廣義表中的元素既可以是表元素也可以是單元素，故在頭尾表示法中結(jié)點(diǎn)的結(jié)構(gòu)形式也有兩種：一種是表結(jié)點(diǎn)，用來表示表元素；另一種是元素結(jié)點(diǎn)，用來表示單元素。并且，在表結(jié)點(diǎn)中應(yīng)該有一個指向表頭的指針和一個指向表尾的指針，而在元素結(jié)點(diǎn)中則應(yīng)表示單元素的元素值。除此之外，在每個結(jié)點(diǎn)中還要設(shè)置一個標(biāo)志域flag，并且有：1表示本結(jié)點(diǎn)為表結(jié)點(diǎn)0表示本結(jié)點(diǎn)為元素結(jié)點(diǎn)flag頭尾表示法的結(jié)點(diǎn)結(jié)構(gòu)如圖5-19所示。圖5-19頭尾表示法的結(jié)點(diǎn)結(jié)構(gòu)頭尾表示法的結(jié)點(diǎn)類型定義如下：

typedefstructnode

{

intflag; //標(biāo)志域

union //元素結(jié)點(diǎn)和表結(jié)點(diǎn)共用內(nèi)存

{

datatypedata; //元素結(jié)點(diǎn)的數(shù)據(jù)域

struct //表結(jié)點(diǎn)

{

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

structnode*tp; //表結(jié)點(diǎn)的表尾指針

}ptr; //ptr.hp和ptr.tp分別指向子表的表頭和表尾

}

}HTNode; //廣義表結(jié)點(diǎn)類型圖5-20廣義表頭尾表示法存儲結(jié)構(gòu)示意圖由圖5-20可以看出，該存儲結(jié)構(gòu)恰好是5.4.1節(jié)中對廣義表A、B、C、D、E、F求出的Head和Tail值的一種表示。同樣，由圖5-19可以看出，頭尾表示法存儲結(jié)構(gòu)有如下幾個特點(diǎn)：

(1)若廣義表為空表則表頭指針為空。否則表頭指針總是指向一個表結(jié)點(diǎn)，且該表結(jié)點(diǎn)中的hp指針指向廣義表的表頭，tp指針指向廣義表的表尾。

(2)容易分清廣義表中單元素和子表所在的層次。如廣義表D中，單元素e和a在同一層上，而單元素b和c在同一層上且比e和a低了一層。

(3)最高層的表結(jié)點(diǎn)個數(shù)為廣義表的長度。例如廣義表D的最高層有三個表結(jié)點(diǎn)，其廣義表的長度為3；廣義表C最高層有2個結(jié)點(diǎn)，其廣義表長度為2。

2.孩子兄弟表示法

廣義表的另一種表示法稱為孩子兄弟表示法。孩子兄弟表示法中也有兩種結(jié)點(diǎn)形式：一種是有孩子結(jié)點(diǎn)，用來表示表元素；另一種是無孩子結(jié)點(diǎn)，用來表示單元素。在有孩子結(jié)點(diǎn)中包含一個指向第一個孩子(長子)的指針和一個指向兄弟的指針；而在無孩子結(jié)點(diǎn)中則含有該結(jié)點(diǎn)的數(shù)據(jù)值和一個指向兄弟的指針。如同頭尾表示法一樣，為了能區(qū)分這兩類結(jié)點(diǎn)，在結(jié)點(diǎn)中還要設(shè)置一個標(biāo)志域flag，并且有：1表示本結(jié)點(diǎn)有孩子結(jié)點(diǎn)0表示本結(jié)點(diǎn)無孩子flag圖5-21孩子兄弟表示法的結(jié)點(diǎn)結(jié)構(gòu)孩子兄弟表示法的結(jié)點(diǎn)類型定義如下：

typedefstructnode

{

intflag; //標(biāo)志域

union //元素結(jié)點(diǎn)和表結(jié)點(diǎn)共用內(nèi)存

{

chardata; //元素結(jié)點(diǎn)的數(shù)據(jù)域

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

}val;

structnode*tp; //指向下一個兄弟結(jié)點(diǎn)

}CBNode; //廣義表結(jié)點(diǎn)類型在這種廣義表的存儲結(jié)構(gòu)中，tp指針相當(dāng)于線性表的next指針，它指向下一個元素結(jié)點(diǎn)。對于5.4.1節(jié)所列舉的廣義表A、B、C、D、E、F，若采用孩子兄弟表示法的存儲方式，其存儲結(jié)構(gòu)如圖5-22所示。圖5-22廣義表的孩子兄弟表示法存儲結(jié)構(gòu)例5.3

求如下廣義表的運(yùn)算結(jié)果。

Head(Tail(Tail(Head(((a,b,(c,d),e),f,(g,h)))))

【解】

例5.4

根據(jù)頭尾表示法和孩子兄弟表示法，畫出廣義表LS=((a,b),c,((d)))在這兩種方法下的存儲結(jié)構(gòu)示意。

【解】廣義表LS=((a,b),c,((d)))在頭尾表示法下的存儲結(jié)構(gòu)示意圖如圖5-23所示。

廣義表LS=((a,b),c,((a)))在孩子兄弟表示法下的存儲結(jié)構(gòu)示意圖如圖5-24所示。圖5-23廣義表頭尾表示法存儲結(jié)構(gòu)示意圖圖5-24廣義表孩子兄弟表示法存儲結(jié)構(gòu)示意圖5.4.3廣義表基本操作實(shí)現(xiàn)算法

1.建立廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

采用孩子兄弟表示法來建立廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，并假定廣義表中的元素類型datatype為char類型，每個單元素的值被限定為英文字母。并且廣義表是一個表達(dá)式，其格式為：各元素之間用一個逗號“,”隔開，表元素的起始和結(jié)束符號分別為左括號“(”和右括號“)”，空表在“()”內(nèi)部不包含任何字符。例如“(a,(b,c,d),e)”就是一個符合規(guī)定的廣義表格式。

建立廣義表的存儲結(jié)構(gòu)的算法是一個非遞歸算法，該算法使用一個具有廣義表格式的字符數(shù)組ex，返回由它生成的廣義表存儲結(jié)構(gòu)的頭指針h。建立廣義表鏈?zhǔn)酱鎯Y(jié)構(gòu)的算法如下：

CBNode*Create(charex[])//用孩子兄弟表示法建立廣義表

{

CBNode*p,*q=NULL,*h,*hp[MAXSIZE]; //h為最終生成的廣義表表頭指針

SeqStack*s;

charx,*y=&x; //出棧元素經(jīng)過指針y傳給x

inti=0,j=0,b=0,t=0,k=0;

Init_SeqStack(&s);

while(ex[i]!='\0') //是否到表達(dá)式串的串尾

{

if(ex[i]=='') //當(dāng)前字符為空格字符時

i++;

if(ex[i]=='(') //當(dāng)前字符為左括號"("時

{

Push_SeqStack(s,ex[i]);//將“(”壓入棧s中

p=(CBNode*)malloc(sizeof(CBNode));//創(chuàng)建一個新結(jié)點(diǎn)

p->flag=1; //新結(jié)點(diǎn)作為表頭結(jié)點(diǎn)

p->tp=NULL;//表元素結(jié)點(diǎn)的tp指針暫置為空

k=0; //表元素結(jié)點(diǎn)標(biāo)志

hp[j++]=p;//將指向表元素結(jié)點(diǎn)的指針p壓入棧hp中

if(q!=NULL)

if(t==1)

{

t=0;

q->tp=p;//結(jié)點(diǎn)*p作為結(jié)點(diǎn)*q兄弟結(jié)點(diǎn)鏈入表中

}

else

q->val.hp=p; //結(jié)點(diǎn)*p作為結(jié)點(diǎn)*q孩子結(jié)點(diǎn)鏈入表中

else

q=p; //指針q下移指向結(jié)點(diǎn)*p

if(b==0) //剛生成的是廣義表的第一個結(jié)點(diǎn)

{

h=p;b=1; //使廣義表表頭指針h指向該結(jié)點(diǎn)

}

}

else

if(ex[i]==')') //遇到")"字符則子表結(jié)束

{

Top_SeqStack(s,y);

if(*y=='(')

{

p->tp=NULL;

if(ex[i-1]=='('||(ex[i-1]==''&&ex[i-2]=='('))//空表時的處理

p->val.hp=NULL; //子表是空表

Pop_SeqStack(s,y);

if(j!=0) //當(dāng)棧hp未到棧底時

{

q=hp[--j];//將保存于棧hp的表元素結(jié)點(diǎn)指針彈出賦給q

if(ex[i+1]==‘,’)

{

if(ex[i+2]==‘(’) //下一兄弟結(jié)點(diǎn)是表元素結(jié)點(diǎn)的處理

{

t=1;k=0;i++;

gotol2;

}

i++;

}

k=1; //下一兄弟結(jié)點(diǎn)是單元素結(jié)點(diǎn)的處理

l2:;

}

}

else

{

h=NULL;//輸入的廣義表字符串有錯,置廣義表為空

printf(“Error!\n”);

gotol1;

}

}

else

if(ex[i]!=‘,’) //生成單元素結(jié)點(diǎn)的處理

{

if(k==0) //在此之前生成的*p為表元素結(jié)點(diǎn)

{

q=p; //使q指向這個表元素結(jié)點(diǎn)

k=0;

}

p=(CBNode*)malloc(sizeof(CBNode));//創(chuàng)建一個新結(jié)點(diǎn)

p->flag=0; //新結(jié)點(diǎn)作為單元素結(jié)點(diǎn)

p->val.data=ex[i];

if(ex[i-1]=='(')

q->val.hp=p;//作為孩子結(jié)點(diǎn)鏈接到當(dāng)前結(jié)點(diǎn)上

else

q->tp=p;//作為兄弟結(jié)點(diǎn)鏈接到當(dāng)前結(jié)點(diǎn)上

}

else //當(dāng)ex[i]等于","時的處理

{

q=p;

t=1;

}

i++;

}

if