第5章數(shù)組和廣義表課件

數(shù)組

和

廣義表數(shù)組1、數(shù)組的定義和順序存儲方式；

2、特殊矩陣的壓縮存儲；

3、稀疏矩陣；

4、廣義表的概念、表示及基本操作；廣義表存儲結(jié)構(gòu)的實現(xiàn)。教學內(nèi)容1、數(shù)組的定義和順序存儲方式；

2、特殊矩陣的壓縮存儲；5.1數(shù)組數(shù)組：按一定格式排列起來的具有相同類型的數(shù)據(jù)元素的集合。一維數(shù)組：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡單元素，則稱為一維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。定長的線性表。聲明格式：數(shù)據(jù)類型變量名稱[長度]；

例：intnum[5]={0，1，2，3，4};1數(shù)組的定義5.1數(shù)組數(shù)組：按一定格式排列起來的二維數(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)定長的線性表每一個數(shù)據(jù)元素既在一個行表中，又在一個列表中。

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

二維數(shù)組：若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組在C語言中，一個二維數(shù)組類型也可以定義為一維數(shù)組類型（其分量類型為一維數(shù)組類型），即：typedefelemtypearray2[m][n];等價于：typedefelemtypearray1[n];typedefarray1array2[m];聲明格式：數(shù)據(jù)類型變量名稱[行數(shù)][列數(shù)]

；

例：intnum[5][8];在C語言中，一個二維數(shù)組類型也可以定義為三維數(shù)組：若二維數(shù)組中的元素又是一個一維數(shù)組結(jié)構(gòu)，則稱作三維數(shù)組?！?/p>

n維數(shù)組：若n-1維數(shù)組中的元素又是一個一維數(shù)組結(jié)構(gòu)，則稱作n維數(shù)組。線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴展。結(jié)論數(shù)組特點：結(jié)構(gòu)固定：定義后維數(shù)和維界不再改變。

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

三維數(shù)組：若二維數(shù)組中的元素又是一個一維數(shù)組數(shù)組的抽象數(shù)據(jù)類型的定義ADTArray{

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

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

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

bi

是數(shù)組第i維的長度，

ji

是數(shù)組元素的第i維下標，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ù)組的抽象數(shù)據(jù)類型的定義ADTArray{

數(shù)據(jù)對數(shù)據(jù)對象:

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ù)對象和數(shù)據(jù)關(guān)系的定義數(shù)據(jù)對象:二維數(shù)組的抽象數(shù)據(jù)類型的數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義基本操作：InitArray(&A,n,bound1,...,boundn)操作結(jié)果：若維數(shù)n和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。DestroyArray(&A)操作結(jié)果：銷毀數(shù)組A。Value(A,&e,index1,...,indexn)初始條件：A是n維數(shù)組，e為元素變量。操作結(jié)果：若各下標不超界，則e賦值為所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始條件：A是n維數(shù)組，e為元素變量。操作結(jié)果：若下標不超界，則將e的值賦給所指定的A的元素，并返回OK。}ADTArray基本操作：數(shù)組特點：結(jié)構(gòu)固定——維數(shù)和維界不變。

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

2數(shù)組的順序表示和實現(xiàn)一般不做插入和刪除操作。因為所以：一般都是采用順序存儲結(jié)構(gòu)來表示數(shù)組。注意：數(shù)組可以是多維的，但存儲數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問題。兩種順序存儲方式以行序為主序(低下標優(yōu)先)BASIC、COBOL和PASCAL以列序為主序(高下標優(yōu)先)FORTRAN數(shù)組特點：結(jié)構(gòu)固定——維數(shù)和維界不變。數(shù)組基本操作：初始以行序為主序存放：

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的存儲位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×L某個元素的地址就是它前面所有行所占的單元加上它所在行前面所有列元素所占的單元數(shù)之和?；刂坊蚧范S數(shù)組的映象函數(shù)

a00a01……..a0,n-1

a10a11……..a1,n-1

am-1,0

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

….以行序為主序存放：am-1,n-1…按列序為主序存放01m-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的存儲位置LOC(i,j)=LOC(0,0)+(b1×j＋i)×L某個元素的地址就是它前面所有列所占的單元加上它所在列前面所有行元素所占的單元數(shù)之和。按列序為主序存放01m-1m*n-1mam例1：一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6

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

個字節(jié)。答：Volume=m×n×L=(6–1+1)×(7–0+1)×6=48×6=288288例1：一個二維數(shù)組A，行下標的范圍是1到6，列答例2：〖某校計算機系考研題〗

設(shè)數(shù)組A[0…59,0…69]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素A[31,57]的存儲地址為

。解：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………………………………▲作業(yè)：5.1

例2：〖某校計算機系考研題〗解：LOC(i,j)=L5.2特殊矩陣的壓縮存儲

矩陣定義：一個由m×n個元素排成的m行（橫向）

n列（縱向）的表。

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

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

矩陣的常規(guī)存儲的特點：

可以對其元素進行隨機存??；矩陣運算非常簡單；存儲的密度為1。

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

矩陣的壓縮存儲：為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。5.2特殊矩陣的壓縮存儲矩陣定義：一個由

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

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

aij=aji

1≤i,j≤n

則稱A為對稱矩陣。特殊矩陣：元素值的排列具有一定規(guī)律的矩陣。對稱矩陣上下三角中的元素數(shù)均為：n(n+1)/2可以行序為主序?qū)⒃卮娣旁谝粋€一維數(shù)組sa[n(n+1)/2]中。對稱矩陣的存儲結(jié)構(gòu)k=01234n(n-1)/2n(n+1)/2-1以行序為主序存儲下三角：a11a21a22a31a32…an1…ann對稱矩陣上下三角中的元素數(shù)均對稱矩陣的存儲結(jié)構(gòu)k=則aij和sa[k]存在著一一對應(yīng)關(guān)系：aij

前的i-1行有1+2+…+(i-1)=i(i-1)/2個元素，在第i行上有j個元素。因為aij

=aji，所以只要交換關(guān)系式中的i和j即可。k=0123n(n-1)/2以行序為主序存儲下三角：a11a21a22a31…an1…ann則aij和sa[k]存在著一一對應(yīng)關(guān)系：aij2、三角矩陣以主對角線劃分，三角矩陣有上（下）三角兩種。上（下）三角矩陣的下（上）三角（不含主對角線）中的元素均為常數(shù)。在大多數(shù)情況下，三角矩陣常數(shù)為零。上三角矩陣下三角矩陣

三角矩陣的存儲：除了存儲主對角線及上（下）三角中的元素外，再加一個存儲常數(shù)c的空間。2、三角矩陣上三角矩陣下三角矩陣三角矩陣3、帶狀矩陣對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一維數(shù)組中，且也能找到每個非零元素和向量下標的對應(yīng)關(guān)系。3、帶狀矩陣對角矩陣可按行優(yōu)先順序或?qū)?.3稀疏矩陣稀疏矩陣：設(shè)在m×n的矩陣中有t個非零元素。令=t/(m×n)

當

≤0.05時稱為稀疏矩陣。壓縮存儲原則：存各非零元的值、行列位置和矩陣的行列數(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)惟一確定矩陣的一個非零元。三元組的不同表示方法可決定稀疏矩陣不同的壓縮存儲方法。5.3稀疏矩陣稀疏矩陣：設(shè)在m×n的矩陣中有t#defineMAXSIZE12500//假設(shè)非零元個數(shù)的最大值typedefstruct{inti,j;//該非零元的行列下標Elemtypee;}Triple;

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

6

7

8121213931-3361443245218611564-7#defineMAXSIZE12500i

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

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

67

8121213931-3361443245218611564-7

解決思路：將矩陣行、列

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

中的i

和j

相

互調(diào)換重排三元組次序，使T.data

中元素以T

的行(M的列)為主序。M.dataijtu012345678

76

813-3161521122518319342446-76314T.dataT.dataijtu0123456787

6

8

211231913-3631434242518161546-7▲問題描述：已知一個稀疏矩陣的三元組表，求該矩方法一：按M

的列序轉(zhuǎn)置

76

8

67

8121213931-3361443245218611564-7T.dataM.data13-3161521122518319342446-76314for(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;}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;}方法一：按M的列序轉(zhuǎn)置7686781typedefstruct{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時間復(fù)雜度：O(nutu)若tu與munu同數(shù)量級，則為：O(munu2)

67

8121213931-3361443245218611564-713-3161521122518319342446-763147

6

8

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

的行序轉(zhuǎn)置——

快速轉(zhuǎn)置

76

813-3161521122518319342446-76314

67

8121213931-3361443245218611564-7T.dataM.data實施步驟：1、確定M的第1列的第1個非零元在T.data中的位置。13、確定M的第col列的第一個非零元在

T.data中的位置。2、確定M的第col-1列的非零元個數(shù)。存入數(shù)組num[M.nu]存入數(shù)組cpot[M.nu]cpot[1]=1;cpot[col]=cpot[col–1]+num[col–1]2≤col≤a.nucol1234567num(col)2221010cpot(col)1357889col1234567num(col)2221010cpot(col)

方法2：按M的行序轉(zhuǎn)置——快速轉(zhuǎn)置768StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){

//采用三元組順序表存儲表示，求稀疏矩陣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中各列非零元的個數(shù)

cpot[1]=1;

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

//求M中各列的第一個非零元在T.data中的序號

67

8121213931-3361443245218611564-7col1234567num(col)cpot(col)

76

8

0000000111122211357889StatusFastTransposeSMatrix(Tfor(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

67

8121213931-3361443245218611564-7

col1234567num(col)2221010cpot(col)135788976

8

21124319613-326314934247251851615346-78012345678012345678pqpqpqpqpqpqpqpqfor(p=1;p<=M.tu;StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){

//采用三元組順序表存儲表示，求稀疏矩陣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中各列非零元的個數(shù)

cpot[1]=1;

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

//求M中各列的第一個非零元在T.data中的序號

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時間復(fù)雜度為:O(nu+tu)

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

與經(jīng)典算法相同。StatusFastTransposeSMatrix(T三元組順序表又稱有序的雙下標法。三元組順序表的優(yōu)點：非零元在表中按行序有序存儲，因此便于進行依行順序處理的矩陣運算。三元組順序表的缺點：不能隨機存取。若按行號存取某一行中的非零元，則需從頭開始進行查找。三元組順序表又稱有序的雙下標法。2、行邏輯聯(lián)接的順序表（帶行表的三元組）在稀疏矩陣中若隨機存取任意一行的非零元

76

813-3161521122518319342446-76314col1234567num(col)2221010cpot(col)1357889在存儲三元組表的同時存儲一個行表rpos（快速轉(zhuǎn)置算法中“帶行鏈接信息”的

cpot）需知道每行首個非零元在三元組表中的位置行邏輯聯(lián)接的順序表兩個稀疏矩陣相乘時，可以看出這種表示方法的優(yōu)越性?！?、行邏輯聯(lián)接的順序表（帶行表的三元組）在稀疏矩陣中若隨#defineMAXSIZE12500//假設(shè)非零元個數(shù)的最大值typedefstruct{inti,j;//該非零元的行列下標Elemtypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];

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

指示各行第一個非零元的位置兩個稀疏矩陣相乘時，可以看出這種表示方法的優(yōu)越性。RLSMatrix;▲#defineMAXSIZE12500intrp矩陣乘法設(shè)矩陣M是m1×n1矩陣，N是m2×n2矩陣；只有n1=m2時，才能相乘得到結(jié)果矩陣Q=M×N(一個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

不論是否為零，都要進行乘法運算。沒必要！矩陣乘法設(shè)矩陣M是m1×n1矩陣，N是m

i

j

e

11314522-1312

i

j

e

12221131-2324

i

j

e

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

1234rpos[row]123512621-1324006-1004注意：兩個稀疏矩陣相乘的結(jié)果

不一定是稀疏矩陣。ije11314522intMulSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q){if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//Q初始化

if(M.tu*N.tu!=0)//Q是非零矩陣

for(arow=1;arow<=M.mu;++arow)//逐行處理M

{ctemp[]=0;//當前行各元素的累加器清零

Q.rpos[arow]=Q.tu+1;if(arow<M.mu)tp=M.rpos[arow+1];elsetp=M.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){//對當前行中每一個非零元找到對應(yīng)元在N中的行號

brow=M.data[p].j;if(brow<N.nu)t=N.rpos[brow+1];elset=N.tu+1;intMulSMatrix(RLSMatrixM,Rfor(q=N.rpos[brow];q<t;++q){

ccol=N.data[q].j;//乘積元素在Q中列號

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}//forq

}//求得Q中第crow(=arow)行的非零元

for(ccol=1;ccol<=Q.nu;++ccol)//壓縮存儲該行非零元

if(ctemp[ccol]){

if(++Q.tu>MAXSIZE)returnERROR;

Q.data[Q.tu]={arow,ccol,ctemp[ccol]};

}//if

}//forarow

}//if

returnOK;

}//MultSMatrixfor(q=N.rpos[brow上述算法的時間復(fù)雜度分析：

◆累加器ctemp初始化的時間復(fù)雜度為O(M.mu×N.mu)

◆求Q的所有非零元的時間復(fù)雜度為O(M.tu×N.tu/N.mu)

◆進行壓縮存儲的時間復(fù)雜度為O(M.mu×N.nu)

總的時間復(fù)雜度就是O(M.mu×N.nu+M.tu×N.tu/N.mu)。

若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個數(shù)M.tu=dM×m×n，N中非零元的個數(shù)N.tu=dN×n×p，相乘算法的時間復(fù)雜度就是O(m×p×(1+ndMdN))，當dM<0.05和dN<0.05及n<1000時，相乘算法的時間復(fù)雜度就相當于O(m×p)。

顯然，這是一個相當理想的結(jié)果。如果事先能估算出所求乘積矩陣Q不再是稀疏矩陣，則以二維數(shù)組表示Q，相乘的算法也就更簡單了。上述算法的時間復(fù)雜度分析：

◆累加器ctemp初始化的時3、稀疏矩陣的鏈式存儲結(jié)構(gòu)：十字鏈表優(yōu)點：它能夠靈活地插入因運算而產(chǎn)生的新的非零元素，

刪除因運算而產(chǎn)生的新的零元素，實現(xiàn)矩陣的運算。在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了（row，col，value）外，還有兩個域：right：用于鏈接同一行中的下一個非零元素；down：用以鏈接同一列中的下一個非零元素。rowcolvaluedownright十字鏈表中結(jié)點的結(jié)構(gòu)示意圖：3、稀疏矩陣的鏈式存儲結(jié)構(gòu)：十字鏈表優(yōu)點：它能夠靈活地插入因113145^^312^^22-1^^^M.rheadM.chead113145^^312^^22-1^^^M211^122^31-2^324^^

M.rheadM.chead^211^122^31-2^324^^M.r十字鏈表的結(jié)構(gòu)類型說明如下：typedefstructOLNode{inti,j;//非零元素的行和列下標ElementTypee;structOLNode*right,*down;//非零元素所在行表列表的后繼鏈域}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;//行、列鏈表的頭指針向量基址intmu,nu,tu;//稀疏矩陣的行數(shù)、列數(shù)、非零元個數(shù)}CrossList;十字鏈表的結(jié)構(gòu)類型說明如下：typedefstruct建立稀疏矩陣的十字鏈表算法：CreateCrossList(CrossList*M){//采用十字鏈表存儲結(jié)構(gòu)，創(chuàng)建稀疏矩陣Mif(M!=NULL)free(M);scanf(&m,&n,&t);//輸入M的行數(shù),列數(shù)和非零元素的個數(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->row_head[]=M->col_head[]=NULL;//初始化行、列頭指針向量，各行、列鏈表為空的鏈表for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;//生成結(jié)點建立稀疏矩陣的十字鏈表算法：CreateCrossListif(M->row_head[i]==NULL)M->row_head[i]=p;else{/*尋找行表中的插入位置*/ for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right)p->right=q->right;q->right=p;/*完成插入*/}if(M->col_head[j]==NULL)M->col_head[j]=p;else{/*尋找列表中的插入位置*/for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down)p->down=q->down;q->down=p;/*完成插入*/}}}if(M->row_head[i]==NULL)M->兩個矩陣相加的算法描述：

(1)初始令pa和pb分別指向A和B的第一行的第一個非零元素的結(jié)點，即

pa＝A.rhead[1];pb＝B.rhead[1];pre=NULL;

且令hl初始化for(j=1;j<=A.nu;++j)hl[j]＝A.chead[j];

(2)重復(fù)本步驟，依次處理本行結(jié)點，直到B的本行中無非零元素的結(jié)點，即pb==NULL為止：

①若pa==NULL或pa->j〉pb->j（即A的這一行中非零元素已處理完），則需在A中插入一個pb所指結(jié)點的復(fù)制結(jié)點。假設(shè)新結(jié)點的地址為p，則A的行表中的指針作如下變化：

ifpre==NULLrhead[p->i]=p;

else{pre->right＝p;}

p->right＝pa;pre=p;兩個矩陣相加的算法描述：(1)初始令pa和pb分別指向AA的列鏈表中的指針也要作相應(yīng)的改變。首先需從hl[p->j]開始找到新結(jié)點在同一列中的前驅(qū)結(jié)點，并讓hl[p->j]指向它，然后在列鏈表中插入新結(jié)點：

ifchead[p->j]==NULL

{chead[p->j]=p;p->down=NULL;}

else{

p->down＝hl[p->j]->down;hl[p->j]->down＝p;}

hl[p->j]=p;

②若pa->j〈pb->j且pa->j!=0，則令pa指向本行下一個非零元結(jié)點，即pre＝pa;pa＝pa->right;

③若pa->j==pb->j，則將B中當前結(jié)點的值加到A中當前結(jié)點上，即

pa->e＋＝pb->e;A的列鏈表中的指針也要作相應(yīng)的改變。首先需從hl[p->j]此時若pa->e!=0，則指針不變，否則刪除A中該結(jié)點，即行表中指針變?yōu)椋?/p>

ifpre==NULLrhead[pa->i]=pa->right;

else{pre->right＝pa->right;}

p=pa;pa=pa->right;

同時，為了改變列表中的指針，需要先找到同一列中的前驅(qū)結(jié)點，且讓hl[pa->j]指向該結(jié)點，然后如下修改相應(yīng)指針：

ifchead[p->j]==p

chead[p->j]=hl[p->j]=p->down;

else{hl[p->j]->down＝p->down;}

free(p);

(3)若本行不是最后一行，則令pa和pb指向下一行的第一個非零元結(jié)點，轉(zhuǎn)(2)；否則結(jié)束。

此算法時間復(fù)雜度：O(ta+tb)▲此時若pa->e!=0，則指針不變，否則刪除A中該結(jié)點，即行

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

的有限序列，其中每一個ai或者是原子，或者是一個子表。5.4廣義表的定義例：中國舉辦的國際足球邀請賽，參賽隊名單可表示如下：

（阿根廷，巴西，德國，法國，（），西班牙，意大利，英國，（國家隊，魯能，實德））

在這個表中，韓國隊應(yīng)排在法國隊后面，但由于其水平低未敢參加，成為空表。國家隊、魯能隊、實德隊均作為東道主的參賽隊參加，構(gòu)成一個小的線性表，成為原線性表的一個數(shù)據(jù)元素。這種拓寬了的線性表就是廣義表。單個元素廣義表（又稱列表Lists）是n≥0個元素廣義表通常記作：LS=(a1，a2，…，an)其中：LS為表名，n為表的長度，每一個ai為表的元素。習慣上，一般用大寫字母表示廣義表，小寫字母表示原子。

表頭：若LS非空(n≥1)，則其第一個元素a1

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

表尾：除表頭之外的其它元素組成的表。記作tail(LS)=(a2,...,an)。

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

如：C=(a,(b,c))是長度為2的廣義表。(3)廣義表的深度定義為該廣義表展開后所含括號的重數(shù)；

A=(b,c)的深度為1，B=(A,d)的深度為2，

C=(f,B,h)的深度為3。

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

“空表”的深度為1。

廣義表可以為其他廣義表共享；如：廣義表B就共享表A。在B中不必列出A的值，而是通過名稱來引用。(5)廣義表可以是遞歸的表。如：F=(a,F)=(a,(a,(a,…)))注意：遞歸表的深度是無窮值，長度是有限值。廣義表的性質(zhì)(1)廣義表中的數(shù)據(jù)元素有相對次序；廣義廣義表是多層次結(jié)構(gòu)，廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，…?？梢杂脠D形象地表示。

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

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)))=()GetHead((b,c))=bGetTail((b,c))=(c)GetHead((c))=cGetTail((c))=()廣義表基本運算取表頭運算GetHead和取表尾運算GetTail5.5廣義表的存儲結(jié)構(gòu)由于廣義表是遞歸定義的其元素可具有不同的結(jié)構(gòu)（原子或列表）1、首尾鏈表廣義表（不空）用順序存儲結(jié)構(gòu)表示采用鏈式存儲結(jié)構(gòu)（廣義鏈表）首尾表示法就是根據(jù)這一性質(zhì)設(shè)計的一種存儲方法。表頭+表尾分解確定×5.5廣義表的存儲結(jié)構(gòu)由于廣義表是遞歸定義的1、結(jié)點的結(jié)構(gòu)形式標志域tag=1指示表頭的指針域hp

指示表尾的指針域tp

表結(jié)點由三個域組成tag=1hptp原子結(jié)點由兩個域組成標志域tag=0值域atomtag=0atom結(jié)點的結(jié)構(gòu)形式標志域tag=1表結(jié)點由三個域組成typedefenum{ATOM,LIST}ElemTag;//ATOM=0：單元素；LIST=1：子表typedefstructGLNode{Elemtagtag;//標志域，用于區(qū)分元素結(jié)點和表結(jié)點

Atomtypeatom;//atom是原子結(jié)點的值域

}*GList;//廣義表類型

typedefstructGLNode{Elemtagtag;//標志域，用于區(qū)分元素結(jié)點和表結(jié)點

Atomtypeatom;//atom是原子結(jié)點的值域

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

}*GList;//廣義表類型typedefenum{ATOM,LIST}ElemTag;//ATOM=0：單元素；LIST=1：子表typedefstructGLNode{Elemtagtag;//標志域，用于區(qū)分元素結(jié)點和表結(jié)點

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

Atomtypeatom;//atom是原子結(jié)點的值域

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

};}*GList;//廣義表類型typedefenum{ATOM,LIST}Ele結(jié)點的鏈接A=()A=NULLB=(e)B

1^0eC=(a,(b,c,d))C

10a1^((b,c,d))10b1(c,d)(b,c,d)0c1^(d)0dD

1^1D=(A,B,C)(B,C)1^(C)E=(a,E)E

11^0a(E)采用首尾表示法容易分清列表中原子或子表所在的層次最高層的表結(jié)點的個數(shù)即為廣義表的長度結(jié)點的鏈接A=()A=NULLB=(e)B2、擴展線性鏈表（孩子兄弟鏈表）兩種結(jié)點形式：有孩子結(jié)點，用以表示列表；

無孩子結(jié)點，用以表示單元素。

結(jié)點的結(jié)構(gòu)形式tag=1hptptag=0atomtp表結(jié)點原子結(jié)點指向第一個孩子指向兄弟元素值指向兄弟C

1^1^0a0b0c0d^C=(a,(b,c,d))2、擴展線性鏈表（孩子兄弟鏈表）兩種結(jié)點形typedefenum{ATOM,LIST}Elemtag;//ATOM=0：單元素；LIST=1：子表typedefstructGLNode{Elemtagtag;//標志域，用于區(qū)分元素結(jié)點和表結(jié)點union{//元素結(jié)點和表結(jié)點的聯(lián)合部分Atomtypeatom;//atom是原子結(jié)點的值域structGLNode*hp;//表結(jié)點的表頭指針};structGLNode*tp;//指向下一個結(jié)點}*GList;//廣義表類型typedefenum{ATOM,LIST}EleA=()A

1^^B=(e)B

1^0e^結(jié)點的鏈接C

1^1^0a0b0c0d^C=(a,(b,c,d))D

1^1D=(A,B,C)1^1^E=(a,E)E

1^1^0a表達式中的左括號“（”對應(yīng)存儲表示中的tag=1的結(jié)點最高層結(jié)點tp域必為NULLA=()A1^^B=(e)B1^0e^結(jié)點的1、了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法；

2、掌握特殊矩陣壓縮存儲的下標變換公式；

3、了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，理解以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法；

4、掌握廣義表的結(jié)構(gòu)特點及其存儲表示方法，會對非空廣義表進行分解。教學要求1、了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在教學要求作業(yè)：5.1、5.10、5.11-(1、2、3)、5.12-(2)、5.13-(1)作業(yè)：5.1、5.10、5.11-(1、2、3)、5.12數(shù)組

和

廣義表數(shù)組1、數(shù)組的定義和順序存儲方式；

2、特殊矩陣的壓縮存儲；

3、稀疏矩陣；

4、廣義表的概念、表示及基本操作；廣義表存儲結(jié)構(gòu)的實現(xiàn)。教學內(nèi)容1、數(shù)組的定義和順序存儲方式；

2、特殊矩陣的壓縮存儲；5.1數(shù)組數(shù)組：按一定格式排列起來的具有相同類型的數(shù)據(jù)元素的集合。一維數(shù)組：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡單元素，則稱為一維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。定長的線性表。聲明格式：數(shù)據(jù)類型變量名稱[長度]；

例：intnum[5]={0，1，2，3，4};1數(shù)組的定義5.1數(shù)組