數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第5章 數(shù)組和廣義表

第5章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)5.1數(shù)組的定義數(shù)組：按一定格式排列起來(lái)的具有相同類型的數(shù)據(jù)元素的集合。一維數(shù)組：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡(jiǎn)單元素，則稱為一維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。定長(zhǎng)的線性表。聲明格式：數(shù)據(jù)類型變量名稱[長(zhǎng)度]；

例：intnum[5]={0，1，2，3，4};二維數(shù)組：若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則稱為二維數(shù)組。非線性結(jié)構(gòu)

num[5]={0，1，2，3，4};A=(0,1,…,p)(p=m-1orn-1)j=(a0j,a1j,…,am-1,j)0≤j≤n-1i=(ai0,ai1,…,ai,n-1)0≤i≤m-1二維數(shù)組的邏輯結(jié)構(gòu)線性結(jié)構(gòu)定長(zhǎng)的線性表每一個(gè)數(shù)據(jù)元素既在一個(gè)行表中，又在一個(gè)列表中。

該線性表的每個(gè)數(shù)據(jù)元素也是一個(gè)定長(zhǎng)的線性表。

在C語(yǔ)言中，一個(gè)二維數(shù)組類型也可以定義為一維數(shù)組類型（其分量類型為一維數(shù)組類型），即：

typedefelemtypearray2[m][n];等價(jià)于：

typedefelemtypearray1[n];typedefarray1array2[m];聲明格式：數(shù)據(jù)類型變量名稱[行數(shù)][列數(shù)]

；

例：intnum[5][8];三維數(shù)組：若二維數(shù)組中的元素又是一個(gè)一維數(shù)組結(jié)構(gòu)，則稱作三維數(shù)組?！?/p>

n

維數(shù)組：若n-1維數(shù)組中的元素又是一個(gè)一維數(shù)組結(jié)構(gòu)，則稱作n

維數(shù)組。線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個(gè)特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴(kuò)展。結(jié)論數(shù)組特點(diǎn)：結(jié)構(gòu)固定——定義后，維數(shù)和維界不再改變。

數(shù)組基本操作：除了結(jié)構(gòu)的初始化和銷毀之外，只有取元素和修改元素值的操作。

數(shù)組的抽象數(shù)據(jù)類型的定義ADTArray{

數(shù)據(jù)對(duì)象：D＝{aj1j2…jn|ji

=0,...,bi-1,i=1,2,..,n,

n(>0)稱為數(shù)組的維數(shù)，

bi

是數(shù)組第i

維的長(zhǎng)度，

ji

是數(shù)組元素的第i

維下標(biāo)，

aj1j2…jn∈ElemSet}數(shù)據(jù)關(guān)系：R＝{R1,R2,...,Rn}Ri＝{<aj1...ji...jn,aj1...ji+1...jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,

aj1…ji…jn

,aj1…ji+1…jn∈D,i=2,...,n}數(shù)據(jù)對(duì)象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}數(shù)據(jù)關(guān)系:

R={ROW,COL}ROW={<ai,j

,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}COL={<ai,j

,ai,

j+1>|0≤i≤b1-1,0≤j≤b2-2}二維數(shù)組的抽象數(shù)據(jù)類型的數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義基本操作：InitArray(&A,n,bound1,...,boundn)操作結(jié)果：若維數(shù)n

和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。DestroyArray(&A)操作結(jié)果：銷毀數(shù)組A。Value(A,&e,index1,...,indexn)初始條件：A是n

維數(shù)組，e

為元素變量，隨后是n

個(gè)下標(biāo)值。操作結(jié)果：若各下標(biāo)不超界，則e

賦值為所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始條件：A是n

維數(shù)組，e

為元素變量，隨后是n

個(gè)下標(biāo)值。操作結(jié)果：若下標(biāo)不超界，則將e

的值賦給所指定的A的元素，并返回OK。}ADTArray數(shù)組特點(diǎn)：結(jié)構(gòu)固定——維數(shù)和維界不變。

數(shù)組基本操作：初始化、銷毀、取元素、修改元素值。

5.2數(shù)組的順序表示和實(shí)現(xiàn)一般不做插入和刪除操作。因?yàn)樗裕阂话愣际遣捎庙樞虼鎯?chǔ)結(jié)構(gòu)來(lái)表示數(shù)組。注意：數(shù)組可以是多維的，但存儲(chǔ)數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲(chǔ)數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問(wèn)題。兩種順序存儲(chǔ)方式以行序?yàn)橹餍?低下標(biāo)優(yōu)先)BASIC、COBOL和PASCAL以列序?yàn)橹餍?高下標(biāo)優(yōu)先)FORTRAN以行序?yàn)橹餍虼娣牛?/p>

am-1,n-1

……..

am-1,1

am-1,0

……….

a1,n-1

……..

a11

a10

a0,n-1

…….

a01

a0001n-1m*n-1n二維數(shù)組中任一元素

aij

的存儲(chǔ)位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×L某個(gè)元素的地址就是它前面所有行所占的單元加上它所在行前面所有列元素所占的單元數(shù)之和?；刂坊蚧范S數(shù)組的映象函數(shù)

a00a01……..a0,n-1

a10a11……..a1,n-1

am-1,0

am-1,1……..am-1,n-1

….按列序?yàn)橹餍虼娣?1m-1m*n-1m

am-1,n-1

……..

a1,n-1

a0,n-1

……….

am-1,1

……..

a11

a01

am-1,0

…….

a10

a00

a00

a01

……..

a0,n-1

a10

a11

……..

a1,n-1

am-1,0

am-1,1

……..

am-1,n-1

….二維數(shù)組中任一元素

aij

的存儲(chǔ)位置

LOC(i,j)=LOC(0,0)+(b1×j＋i)×L某個(gè)元素的地址就是它前面所有列所占的單元加上它所在列前面所有行元素所占的單元數(shù)之和。例

1：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6

個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是

個(gè)字節(jié)。答：

Volume=m×n×L=(6–1+1)×(7–0+1)×6=48×6=288288例2：〖某校計(jì)算機(jī)系考研題〗

設(shè)數(shù)組A[0…59,0…69]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素A[31,57]的存儲(chǔ)地址為

。解：LOC(i,j)=LOC(31,57)=LOC(0,0)+(b1×j＋i)×L=2048+(60×57＋31

)×2=89508950

a00a01…a0,69

a10a11…a1,69

a59,0a59,1…a59,69

………a31,57……

……………

……………▲5.3矩陣的壓縮存儲(chǔ)

矩陣定義：一個(gè)由m×n

個(gè)元素排成的m

行（橫向）

n

列（縱向）的表。

矩陣的常規(guī)存儲(chǔ)：

將矩陣描述為一個(gè)二維數(shù)組。

矩陣的常規(guī)存儲(chǔ)的特點(diǎn)：

可以對(duì)其元素進(jìn)行隨機(jī)存?。痪仃囘\(yùn)算非常簡(jiǎn)單；存儲(chǔ)的密度為1。

不適宜常規(guī)存儲(chǔ)的矩陣：值相同的元素很多且呈某種規(guī)律分布；零元素多。

矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。5.3.1特殊矩陣

特殊矩陣：元素值的排列具有一定規(guī)律的矩陣。對(duì)稱矩陣、下（上）三角矩陣、對(duì)角線矩陣等。

1、對(duì)稱矩陣

在一個(gè)n

階方陣A中，若元素滿足下述性質(zhì)：

aij=aji

1≤i,j≤n

則稱A為對(duì)稱矩陣。對(duì)稱矩陣上下三角中的元素?cái)?shù)均為：n(n+1)/2

可以行序?yàn)橹餍驅(qū)⒃卮娣旁谝粋€(gè)一維數(shù)組

sa[n(n+1)/2]中。對(duì)稱矩陣的存儲(chǔ)結(jié)構(gòu)k=01234n(n-1)/2n(n+1)/2-1以行序?yàn)橹餍虼鎯?chǔ)下三角：a11a21a22a31a32

…an1…ann則aij

和sa[k]存在著一一對(duì)應(yīng)關(guān)系：aij

前的i-1行有1+2+…+(i-1)=i(i-1)/2個(gè)元素，在第i

行上有

j個(gè)元素。因?yàn)閍ij

=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i

和j

即可。k=01234n(n-1)/2以行序?yàn)橹餍虼鎯?chǔ)下三角：a11a21a22a31a32

…an1…ann

2、三角矩陣以主對(duì)角線劃分，三角矩陣有上（下）三角兩種。上（下）三角矩陣的下（上）三角（不含主對(duì)角線）中的元素均為常數(shù)。在大多數(shù)情況下，三角矩陣常數(shù)為零。上三角矩陣下三角矩陣

三角矩陣的存儲(chǔ)：除了存儲(chǔ)主對(duì)角線及上（下）三角中的元素外，再加一個(gè)存儲(chǔ)常數(shù)c

的空間。

3、對(duì)角矩陣在對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一維數(shù)組中，且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。5.3.2稀疏矩陣稀疏矩陣：設(shè)在m×n

的矩陣中有t

個(gè)非零元素。令

=t/(m×n)

通常認(rèn)為當(dāng)

≤0.05

時(shí)稱為稀疏矩陣。壓縮存儲(chǔ)原則：存各非零元的值、行列位置和矩陣的行列數(shù)。M由

{(1,2,12),

(1,3,9),

(3,1,-3),

(3,6,14),(4,3,24),(5,2,18),

(6,1,15),(6,4,-7)}和矩陣維數(shù)(6,

7)唯一確定。三元組(i,j,aij)惟一確定矩陣的一個(gè)非零元。三元組的不同表示方法可決定稀疏矩陣不同的壓縮存儲(chǔ)方法。#defineMAXSIZE12500//假設(shè)非零元個(gè)數(shù)的最大值typedefstruct{inti,j;//該非零元的行列下標(biāo)

Elemtypee;}Triple;

typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;//矩陣的行、列數(shù)和非零元個(gè)數(shù)}TSMatrix;ijtu012345678稀疏矩陣的壓縮存儲(chǔ)方法——順序存儲(chǔ)結(jié)構(gòu)

1、三元組順序表

6

7

8

1

2

12

1

3

9

3

1

-3

3

6

14

4

3

24

5

2

18

6

1

15

6

4

-7

轉(zhuǎn)置矩陣：一個(gè)m×n的矩陣M，它的轉(zhuǎn)置T是一個(gè)n×m的矩陣，且T(i,j)=M(j,i)，1≤i≤n，1≤j≤m，即M的行是T的列，M的列是T的行。求轉(zhuǎn)置矩陣

問(wèn)題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表。ijtu012345678

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7

解決思路：將矩陣行、列

維數(shù)互換將每個(gè)三元組

中的i

和

j

相

互調(diào)換

重排三元組次序，使b.data

中元素以

T

的

行

(M的列)

為

主序。

M.dataijtu012345678

7

6

8

1

3

-3

1

615

2

112

2

518

3

1

9

3

424

4

6

-7

6

314T.datab.dataijtu0123456787

6

8

211231913-3631434242518161546-7▲方法一：按M

的列序轉(zhuǎn)置

為找到

M

中每一列所有非零元素，需對(duì)其三元組表

M.data

從第一行起掃描一遍。由于M的列是T的行，且T.data

中以

M的

列序?yàn)橹餍?，所以由此得到?/p>

T.data必定是按行優(yōu)先存放的。

7

6

8

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7T.dataM.data13-3161521122518319342446-76314typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;//行、列、非零元數(shù)}TSMatrix;StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu){q=1;

for(col=1;col<=M.nu;++col)

for(p=1;p<=M.tu;++p)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++q;}}returnOK;}//TransposeSMatrix時(shí)間復(fù)雜度：O(nutu)若tu與munu同數(shù)量級(jí)，

則為：O(munu2)

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-713-3161521122518319342446-763147

6

8

qppqpqpfor(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];一般矩陣轉(zhuǎn)置算法：一般矩陣轉(zhuǎn)置算法時(shí)間復(fù)雜度：O(munu)用三元組順序表存儲(chǔ)的矩陣轉(zhuǎn)置算法時(shí)間復(fù)雜度：O(nutu)若tu與munu同數(shù)量級(jí)，則為：O(munu2)算法僅適用于tu<<munu的情況。結(jié)論用三元組順序表存儲(chǔ)稀疏矩陣節(jié)約存儲(chǔ)空間（優(yōu)點(diǎn)）；

tu與munu同數(shù)量級(jí)時(shí)，算法時(shí)間復(fù)雜度高（缺點(diǎn)）；方法二：按M

的行序轉(zhuǎn)置

——

快速轉(zhuǎn)置

7

6

8

1

3

-3

1

615

2

112

2

518

3

1

9

3

424

4

6

-7

6

314

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7T.dataM.data實(shí)施步驟：1、確定M

的第1列的第1個(gè)非零元在T.data

中的位置。13、確定M

的第col列的第一個(gè)非零元在

T.data

中的位置。2、確定M

的第col-1列的非零元個(gè)數(shù)。存入數(shù)組num[M.nu]存入數(shù)組cpot[M.nu]cpot[1]=1;cpot[col]=cpot[col–1]+num[col–1]2≤col≤a.nu

col

1

2

3

4

5

6

7

num(col)

2

2

2

1

0

1

0

cpot(col)

1

3

5

7

8

8

9StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){

//采用三元組順序表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu){

for(col=1;col<=M.nu;++col)num[col]=0;

for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中各列非零元的個(gè)數(shù)

cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];

//求M中各列的第一個(gè)非零元在

T.data

中的序號(hào)

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7

col

1

2

3

4

5

6

7

num(col)

cpot(col)

76

8

0000000111122211357889

for(p=1;p<=M.tu;++p){//轉(zhuǎn)置矩陣元素

col=M.data[p].j;q=cpot[col];

T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++cpot[col];

}//for

}//if

returnOK;

}//FastTransposeSMatrix

6

7

8

1

212

1

3

9

3

1

-3

3

614

4

324

5

218

6

115

6

4

-7

col

1

2

3

4

5

6

7

num(col)

2

2

2

1

0

1

0

cpot(col)

1

3

5

7

8

8

976

8

2112431

9613-326314934247251851615346-78012345678012345678pqpqpqpqpqpqpqpqStatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){

//采用三元組順序表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu){

for(col=1;col<=M.nu;++col)num[col]=0;

for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中各列非零元的個(gè)數(shù)

cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];

//求M中各列的第一個(gè)非零元在

T.data

中的序號(hào)

for(p=1;p<=M.tu;++p){//轉(zhuǎn)置矩陣元素

col=M.data[p].j;q=cpot[col];

T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++cpot[col];

}//for

}//if

returnOK;

}//FastTransposeSMatrix時(shí)間復(fù)雜度為:O(nu+tu)

若tu與munu同數(shù)量級(jí)，則為：O(munu)

與經(jīng)典算法相同。三元組順序表又稱有序的雙下標(biāo)法。三元組順序表的優(yōu)點(diǎn)：非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。三元組順序表的缺點(diǎn)：不能隨機(jī)存取。若按行號(hào)存取某一行中的非零元，則需從頭開(kāi)始進(jìn)行查找。

2、行邏輯鏈接的順序表（帶行表的三元組）在稀疏矩陣中，若要隨機(jī)存取任意一行的非零元，需要知道每一行的第一個(gè)非零元在三元組表中的位置，而這必須從第一個(gè)元素起進(jìn)行搜索查詢。

7

6

8

1

3

-3

1

615

2

112

2

518

3

1

9

3

424

4

6

-7

6

314

col

1

2

3

4

5

6

7

num(col)

2

2

2

1

0

1

0

cpot(col)

1

3

5

7

8

8

9若在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中增加一個(gè)行表rpos——快速轉(zhuǎn)置算法中的

cpot，指示稀疏矩陣中每行的非零元素在三元組表中的起始位置，則不必從第一個(gè)元素起進(jìn)行搜索查詢。稱這種“帶行鏈接信息”的三元組表為：行邏輯鏈接的順序表。#defineMAXSIZE12500//假設(shè)非零元個(gè)數(shù)的最大值typedefstruct{inti,j;//該非零元的行列下標(biāo)

Elemtypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];

intmu,nu,tu;//矩陣的行、列數(shù)和非零元個(gè)數(shù)}TSMatrix;intrpos[MAXRC+1];//

指示各行第一個(gè)非零元的位置兩個(gè)稀疏矩陣相乘時(shí)，可以看出這種表示方法的優(yōu)越性。RLSMatrix;▲矩陣乘法設(shè)矩陣M是m1×n1

矩陣，N

是m2×n2

矩陣；只有n1=m2時(shí)，才能相乘得到結(jié)果矩陣Q=M×N（一個(gè)m1×n2

的矩陣）。矩陣相乘的經(jīng)典算法：for(i=1;i<=m1;i++)for(j=1;j<=n2;j++){Q[i][j]=0;for(k=1;k<=n1;k++)

Q[i][j]=Q[i][j]+M[i][k]*N[k][j];}i

i

j

j

k

k

不論是否為零，都要進(jìn)行一次乘法運(yùn)算。沒(méi)必要！

i

j

e

1

1

3

1

4

5

2

2

-1

3

1

2

i

j

e

1

2

2

2

1

1

3

1

-2

3

2

4

i

j

e

M[i][k]*N[k][j];

row

1

2

3

4rpos[row]

1

2

3

5

1

26

2

1

-1

3

2

4

0

06-1004注意：兩個(gè)稀疏矩陣相乘的結(jié)果

不一定是稀疏矩陣。3、稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：十字鏈表優(yōu)點(diǎn)：它能夠靈活地插入因運(yùn)算而產(chǎn)生的新的非零元素，刪除因運(yùn)算而產(chǎn)生的新的零元素，實(shí)現(xiàn)矩陣的各種運(yùn)算。在十字鏈表中，矩陣的每一個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示，該結(jié)點(diǎn)除了（row，col，value）以外，還要有兩個(gè)域：

right：用于鏈接同一行中的下一個(gè)非零元素；

down：用以鏈接同一列中的下一個(gè)非零元素。rowcolvaluedownright十字鏈表中結(jié)點(diǎn)的結(jié)構(gòu)示意圖：113145^^312^^22-1^^

^M.rheadM.chead211^122^31-2^324^^

M.rheadM.chead

^十字鏈表的結(jié)構(gòu)類型說(shuō)明如下：typedefstructOLNode{inti,j;//非零元素的行和列下標(biāo)

ElementTypee;structOLNode*right,*down;//非零元素所在行表列表的后繼鏈域}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;//行、列鏈表的頭指針向量基址

intmu,nu,tu;//稀疏矩陣的行數(shù)、列數(shù)、非零元個(gè)數(shù)}CrossList;建立稀疏矩陣的十字鏈表算法：CreateCrossList(CrossList*M){//采用十字鏈表存儲(chǔ)結(jié)構(gòu)，創(chuàng)建稀疏矩陣Mif(M!=NULL)free(M);scanf(&m,&n,&t);//輸入M的行數(shù),列數(shù)和非零元素的個(gè)數(shù)

M->m=m;M->n=n;M->len=t;If(!(M->row_head=(Olink*)malloc((m+1)sizeof(OLink))))exit(OVERFLOW);If(!(M->col_head=(OLink*)malloc((n+1)sizeof(OLink))))exit(OVERFLOW);M->rhead[]=M->chead[]=NULL;//初始化行、列頭指針向量，各行、列鏈表為空的鏈表for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e))//按任意次序輸入非0元{if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;//生成結(jié)點(diǎn)

if(M->rhead[i]==NULL||M->rhead[i]->j>j) {p->right=M->rhead[i];M->rhead[i]=p;}else{/*尋找行表中的插入位置*/ for(q=M->rhead[i];q->right&&q->right->j<j;q=q->right);p->right=q->right;q->right=p;/*完成插入*/}if(M->chead[j]==NULL||M->rhead[j]->i>i)

{p->down=M->chead[j];M->chead[j]=p;}else{/*尋找列表中的插入位置*/for(q=M->chead[j];q->down&&q->down->i<i;q=q->down);p->down=q->down;q->down=p;/*完成插入*/}}}

廣義表（又稱列表Lists）是n≥0個(gè)元素a0,a1,…,an-1

的有限序列，其中每一個(gè)ai

或者是原子，或者是一個(gè)子表。5.4廣義表的定義例：中國(guó)舉辦的國(guó)際足球邀請(qǐng)賽，參賽隊(duì)名單可表示如下：

（阿根廷，巴西，德國(guó)，法國(guó)，（），西班牙，意大利，英國(guó)，（國(guó)家隊(duì)，魯能，恒大））

在這個(gè)表中，韓國(guó)隊(duì)?wèi)?yīng)排在法國(guó)隊(duì)后面，但由于其水平低未敢參加，成為空表。國(guó)家隊(duì)、魯能隊(duì)、恒大隊(duì)均作為東道主的參賽隊(duì)參加，構(gòu)成一個(gè)小的線性表，成為原線性表的一個(gè)數(shù)據(jù)元素。這種拓寬了的線性表就是廣義表。單個(gè)元素廣義表通常記作：LS=(a1，a2，…，an)其中：LS為表名，n為表的長(zhǎng)度，每一個(gè)ai

為表的元素。習(xí)慣上，一般用大寫(xiě)字母表示廣義表，小寫(xiě)字母表示原子。

表頭：若LS

非空(n≥1)，則其第一個(gè)元素a1

就是表頭。記作head(LS)=a1。注：表頭可以是原子，也可以是子表。

表尾：除表頭之外的其它元素組成的表。記作

tail(LS)=(a2,...,an)。

注：表尾不是最后一個(gè)元素，而是一個(gè)子表。(1)A=()例：空表，長(zhǎng)度為0。(2)B=(())(3)C=(a,(b,c))長(zhǎng)度為1，表頭、表尾均為()。長(zhǎng)度為2，由原子a和子表(b,c)構(gòu)成。(4)D=(x,y,z)表頭為a；表尾為((b,c))。長(zhǎng)度為3，每一項(xiàng)都是原子。(5)E=(C,D)表頭為x；表尾為(y,z)。(6)F=(a,F)長(zhǎng)度為2，每一項(xiàng)都是子表。表頭為C；表尾為(D)。長(zhǎng)度為2，第一項(xiàng)為原子，第二項(xiàng)為它本身。F=(a,(a,(a,…)))表頭為a；表尾為(F)。廣義表的性質(zhì)(1)廣義表中的數(shù)據(jù)元素有相對(duì)次序；廣義表的長(zhǎng)度定義為最外層所包含元素的個(gè)數(shù)；

如：

C=(a,(b,c))是長(zhǎng)度為2的廣義表。(3)廣義表的深度定義為該廣義表展開(kāi)后所含括號(hào)的重?cái)?shù)；

A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。

注意：“原子”的深度為0;

“空表”的深度為1。

(4)廣義表可以為其他廣義表共享；如：廣義表B

就共享表A。在B

中不必列出A

的值，而是通過(guò)名稱來(lái)引用。(5)廣義表可以是一個(gè)遞歸的表。如：F=(a,F)=(a,(a,(a,…)))

注意：遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。廣義表是多層次結(jié)構(gòu)，廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，…。可以用圖形象地表示。

例：D=(E,F)其中：

E=(a,(b,c))F=(d,(e))DadbceEF廣義表可以看成是線性表的推廣，線性表是廣義表的特例。廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下，它可以兼容線性表、數(shù)組、樹(shù)和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)。當(dāng)二維數(shù)組的每行（或每列）作為子表處理時(shí)，二維數(shù)組即為一個(gè)廣義表。另外，樹(shù)和有向圖也可以用廣義表來(lái)表示。由于廣義表不僅集中了線性表、數(shù)組、樹(shù)和有向圖等常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可有效地利用存儲(chǔ)空間，因此在計(jì)算機(jī)的許多應(yīng)用領(lǐng)域都有成功使用廣義表的實(shí)例。取表頭運(yùn)算GetHead和取表尾運(yùn)算GetTail若廣義表LS=(a1,a2,…,an)，則GetHead(LS)=a1。

GetTail(LS)=(a2,…,an)。注意：取表頭運(yùn)算得到的結(jié)果可以是原子，也可以是一個(gè)子表。取表尾運(yùn)算得到的結(jié)果一定是一個(gè)子表。例:

D=(E,F)=((a,(b,c))，F(xiàn))GetHead(D)=EGetTail(D)=(F)GetHead(E)=aGetTail(E)=((b,c))GetHead(((b,c)))=(b,c)GetTail(((b,c)))=