數(shù)組和廣義表新

數(shù)組和廣義表新第一頁，共一百二十頁，編輯于2023年，星期三5.1數(shù)組的定義5.3矩陣的壓縮存儲5.2數(shù)組的順序表示和實(shí)現(xiàn)5.4廣義表的定義5.5

廣義表的存儲結(jié)構(gòu)5.7廣義表操作的遞歸函數(shù)5.6m元多項(xiàng)式的表示本章主要內(nèi)容：第二頁，共一百二十頁，編輯于2023年，星期三5.1數(shù)組的定義ADTArray{

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

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}n(>0)稱為數(shù)組的維數(shù)，bi是數(shù)組第i維的長度，

ji是數(shù)組元素的第i維下標(biāo)，

數(shù)據(jù)關(guān)系：

R＝{R1,R2,...,Rn}Ri＝{<aj1,...ji,...jn,aj1,...ji+1,...jn>|0jkbk-1,1kn且ki,0ji

bi-2,i=2,...,n}

基本操作:}ADTArray第三頁，共一百二十頁，編輯于2023年，星期三二維數(shù)組的定義:數(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}基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)第四頁，共一百二十頁，編輯于2023年，星期三

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為元素變量，隨后是n個下標(biāo)值。

操作結(jié)果：若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OK。第五頁，共一百二十頁，編輯于2023年，星期三

Assign(&A,e,index1,...,indexn)

初始條件：A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。

操作結(jié)果：若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。第六頁，共一百二十頁，編輯于2023年，星期三5.2數(shù)組的順序表示和實(shí)現(xiàn)

類型特點(diǎn):1）只有引用型操作，沒有加工型操作；2）數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。

有兩種順序映象的方式:

1）以行序?yàn)橹餍颍ǖ拖聵?biāo)優(yōu)先）；

2）以列序?yàn)橹餍颍ǜ呦聵?biāo)優(yōu)先）。第七頁，共一百二十頁，編輯于2023年，星期三例如：

稱為基地址或基址以“行序?yàn)橹餍颉钡拇鎯τ诚蠖S數(shù)組A中任一元素ai,j

的存儲位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×La0,1a0,0a0,2a1,0a1,1a1,2二維數(shù)組存儲結(jié)構(gòu)a0,1a0,0a0,2a1,0a1,1a1,2L第八頁，共一百二十頁，編輯于2023年，星期三推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲位置的映象關(guān)系稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)。其中cn=L，ci-1=bi×ci,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n第九頁，共一百二十頁，編輯于2023年，星期三//－－－－數(shù)組的順序存儲表示－－－－#include<stdarg.h>//標(biāo)準(zhǔn)頭文件，提供宏va_start、va_arg和va_end,用于存取變長參數(shù)表#defineMAX_ARRAY_DIM8//假設(shè)數(shù)組維數(shù)的最大值為8typedefstruct{ElemType*base;//數(shù)組元素地址，由InitArray分配

intdim;//數(shù)組維數(shù)

int*bounds;//數(shù)組維界基址，由InitArray分配

int*constants;//數(shù)組映像函數(shù)常量基址，由InitArray分配}Array;第十頁，共一百二十頁，編輯于2023年，星期三//－－－－基本操作的函數(shù)原型說明－－－－StatusInitArray(Array&A,intdim…);//若維數(shù)dim和隨后的各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。

intDestroyArray(Array&A);//銷毀數(shù)組AintStrCompare(Array&A,ElemType&e,…)//A是n維數(shù)組，e為元素變量，隨后是n各下標(biāo)值。//若各下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。第十一頁，共一百二十頁，編輯于2023年，星期三//－－－－基本操作的算法描述－－－－StatusInitArray(Array&A,intdim,…);

//若維數(shù)dim和隨后的各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。

if(dim<1||dim>MAX.ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)

exit(OVERFLOW);

//若各維長度合法，則存入A.bounds，并求出A的元素總數(shù)elemtotalelemtotal=1;va_start(ap,dim);//ap為va_list類型，是存放變長參數(shù)表信息的數(shù)組

for(i=0;i<dim;++i){A.bounds[i]=va.arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;elemtotal*=A.bounds[i];}第十二頁，共一百二十頁，編輯于2023年，星期三va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);//求映像函數(shù)的常數(shù)ci,并存入A.constants[i-1],i=1,…,dimA.constants=(int*)malloc(dim*sizeof(int));if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;//L=1,指針的增減以元素的大小為單位for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]A.constants[i+1];returnOK;}第十三頁，共一百二十頁，編輯于2023年，星期三StatusDestroyArray(Array&A){//銷毀數(shù)組A

if(!A.base)returnERROR;

free(A.base);A.base=NULL;

if(!A.bounds)returnERROR;

free(A.bounds);A.bounds=NULL;

if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;

returnOK;}

第十四頁，共一百二十頁，編輯于2023年，星期三

StatusLocate(ArrayA,va_listap,int&off){

//若ap指示的各下標(biāo)值合法，則求出該元素在A中相對地址offoff=0;

for(i=0;i<A.dim;++i){ind=va_arg(ap,int);if(ind<0||ind>=A.bounds[i])returnOVREFLOW;

off+=A.constants[i]*ind;}

return

OK;}第十五頁，共一百二十頁，編輯于2023年，星期三

StatusValue(ArrayA,ElemType&e,…){

//A是n維數(shù)組，e為元素變量，隨后是n各下標(biāo)值。

//若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OKva_start(ap,e);if((result=Loate(A,ap,off))<=0)returnresult;e=*(A.base+off);returnOK;}第十六頁，共一百二十頁，編輯于2023年，星期三

StatusAssign(Array&A,ElemTypee,…){

//A是n維數(shù)組，e為元素變量，隨后是n各下標(biāo)值。

//若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OKva_start(ap,e);if((result=Loate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}第十七頁，共一百二十頁，編輯于2023年，星期三5.3矩陣的壓縮存儲在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)在矩陣中有許多值相同的元素或零元素。有時(shí)為節(jié)省空間，可以對這類矩陣進(jìn)行壓縮存儲。假設(shè)值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則稱此類矩陣為特殊矩陣；反之，稱為稀疏矩陣。第十八頁，共一百二十頁，編輯于2023年，星期三以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問題:1)零值元素占了很大空間;2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。1)盡可能少存或不存零值元素；解決問題的原則:2)盡可能減少沒有實(shí)際意義的運(yùn)算；3)操作方便。即：能盡可能快地找到與下標(biāo)值(i，j)對應(yīng)的元素，能盡可能快地找到同一行或同一列的非零值元。第十九頁，共一百二十頁，編輯于2023年，星期三若n階矩陣A中的元素滿足下述性質(zhì)

aij=aji1<=i,j<=n則稱為n階對稱矩陣。5.3.1特殊矩陣對于對稱矩陣，可以為每一對對稱元分配一個存儲空間，則可將n2個元素壓縮存儲到n(n+1)/2個元的空間中。不失一般性，可以行序?yàn)橹餍虼鎯ζ湎氯牵ò▽蔷€）中的元素。非零元在矩陣中的分布有一定規(guī)則。例如:上（下）三角矩陣、對角矩陣、對稱矩陣等。第二十頁，共一百二十頁，編輯于2023年，星期三假設(shè)以一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A存儲結(jié)構(gòu)，則sa[k]

和矩陣元素aij之間存在著一一對應(yīng)的關(guān)系。k=i(i-1)2+j-1

當(dāng)i>=j對角線下方j(luò)(j-1)2+i-1

當(dāng)i<j對角線上方對于任意給定一組下標(biāo)(i，j)，均可在sa中找到矩陣元素aij，反之，對所有的k=0,1,2,…,(n(n+1))/2-1,都能確定sa[k]中的元在矩陣中的位置(i，j)。由此稱sa[n(n+1)/2]為n階對稱矩陣A的壓縮存儲第二十一頁，共一百二十頁，編輯于2023年，星期三這種壓縮存儲的方法同樣也適應(yīng)于三角矩陣和對角矩陣。5.3.2稀疏矩陣假設(shè)m行n列的矩陣含t個非零元素，則稱為稀疏因子。通常認(rèn)為

0.05的矩陣為稀疏矩陣。何謂稀疏矩陣？nmt×=第二十二頁，共一百二十頁，編輯于2023年，星期三//－－稀疏矩陣的三元組順序表存儲表示－－

#defineMAXSIZE12500//最大非零元個數(shù)

typedefstruct{

inti,j;//該非零元的行下標(biāo)和列下標(biāo)

ElemTypee;//該非零元的值

}Triple;//三元組類型一、三元組順序表typedefunion{

Tripledata[MAXSIZE+1];//非零元三元組表

intmu,nu,tu;//矩陣的行數(shù)、列數(shù)和非零元個數(shù)}TSMatrix;//稀疏矩陣類型第二十三頁，共一百二十頁，編輯于2023年，星期三如何求稀疏矩陣的轉(zhuǎn)置矩陣？úúú?ùêêê?é--028003600070500140úúúúúú?ùêêêêêê?é--005280000007143600轉(zhuǎn)置例如，稀疏矩陣第二十四頁，共一百二十頁，編輯于2023年，星期三用常規(guī)的二維數(shù)組表示時(shí)的算法其中，M為原稀疏矩陣，T為轉(zhuǎn)置后的稀疏矩陣，其時(shí)間復(fù)雜度為:O(mu×nu)

for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];第二十五頁，共一百二十頁，編輯于2023年，星期三用“三元組”表示時(shí)如何實(shí)現(xiàn)？121415-522-731363428211451-522-713364328a.datab.data第二十六頁，共一百二十頁，編輯于2023年，星期三

假設(shè)a和b是TSMatrix型的變量，分別表示矩陣M和T?？梢杂袃煞N處理方法：（1）

按照b.data中三元組的次序依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。換句話說，按照矩陣M的列序來進(jìn)行轉(zhuǎn)置。為了找到M的每一列中所有的非零元素，需要對其三元組表a.data從第一行起整個掃描一遍，由于a.data是以M的行序?yàn)橹餍騺泶娣琶總€非零元的，由此得到的恰是b.data應(yīng)有順序。

具體算法如5.1所示第二十七頁，共一百二十頁，編輯于2023年，星期三StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲表示，求稀疏矩陣M的轉(zhuǎn)置矩陣TT.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;}//if

}

returnOK;}//TransposeSMatrix算法5.1第二十八頁，共一百二十頁，編輯于2023年，星期三該算法主要工作是在p和col的兩重循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(nu*tu)。當(dāng)非零元的個數(shù)tu和mu*nu同數(shù)量級時(shí)，算法5.1的時(shí)間復(fù)雜度就為O(nu*nu2)了。（2）按照a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b中恰當(dāng)?shù)奈恢谩Ｈ绻茴A(yù)先確定矩陣M中每一列（即T中每一行）的第一個非零元在b.data中的準(zhǔn)確位置，則對a.data中的三元組依次轉(zhuǎn)置時(shí)，便可直接放到b.data中恰當(dāng)?shù)奈恢蒙?。第二十九頁，共一百二十頁，編輯?023年，星期三需附設(shè)num和cpot兩個向量。num[col]表示矩陣M中第col列中非零元的個數(shù)，cpot[col]指示M中第col列的第一個非零元在b.data中的恰當(dāng)位置。cpot[1]=1；cpot[col]=cpot[col-1]+num[col-1]第三十頁，共一百二十頁，編輯于2023年，星期三例如：下面稀疏矩陣的三元組表示對應(yīng)各向量值如下：

cpot[1]=1;

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

col12345Num[col]12011Cpot[col]12445該轉(zhuǎn)置方法稱為快速轉(zhuǎn)置，如算法5.2所示。第三十一頁，共一百二十頁，編輯于2023年，星期三StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&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中每一

cpot[1]=1;//列非零元個數(shù)

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

}//if

returnOK;}//FastTransposeSMatrix

…轉(zhuǎn)置矩陣元素算法5.2第三十二頁，共一百二十頁，編輯于2023年，星期三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]

轉(zhuǎn)置矩陣元素：第三十三頁，共一百二十頁，編輯于2023年，星期三分析算法FastTransposeSMatrix的時(shí)間復(fù)雜度：時(shí)間復(fù)雜度為:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……第三十四頁，共一百二十頁，編輯于2023年，星期三三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需隨機(jī)存取某一行中的非零元，則需從頭開始進(jìn)行查找。為便于隨機(jī)存取某一行中的非零元，則需知道每一行的第一個非零元在三元組表中的位置。為此，可將上節(jié)快速轉(zhuǎn)置矩陣算法中建立的，指示‘行’信息的輔助數(shù)組cpot固定在稀疏矩陣的存儲結(jié)構(gòu)中。稱這種‘帶行鏈接信息’的三元組表為行邏輯鏈接的順序表。二、行邏輯聯(lián)接的順序表第三十五頁，共一百二十頁，編輯于2023年，星期三

#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];//非零元三元組表

intrpos[MAXRC+1];//各行第一個非零元的位置表

intmu,nu,tu;//矩陣的行數(shù)、列數(shù)和非零元個數(shù)

}RLSMatrix;//行邏輯鏈接順序表類型行邏輯鏈接的順序表的類型描述如下：第三十六頁，共一百二十頁，編輯于2023年，星期三例如：給定一組下標(biāo)，求矩陣的元素值ElemTypevalue(RLSMatrixM,intr,intc){

p=M.rpos[r];

while(M.data[p].i==r&&M.data[p].j<c)p++;

if(M.data[p].i==r&&M.data[p].j==c)

returnM.data[p].e;

elsereturn0;}//value第三十七頁，共一百二十頁，編輯于2023年，星期三矩陣乘法的精典算法:for(i=1;i<=m1;++i)for(j=1;j<=m2;++j){Q[i][j]=0;for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]*N[k][j];}其時(shí)間復(fù)雜度為:O(m1×m2×n1)

兩個矩陣相乘的經(jīng)典算法。若設(shè)Q=M*N其中，M是m1*n1矩陣，N是n1*m2矩陣，則第三十八頁，共一百二十頁，編輯于2023年，星期三（1）乘積矩陣Q中元素

Q(i,j)=∑M(i,k)*N(k,j)在經(jīng)典算法中，不論M(i,k)和N(k,j)的值是否為零，都要進(jìn)行一次乘法運(yùn)算，這兩者有一個為零，其乘積也為零。在對稀疏矩陣進(jìn)行運(yùn)算時(shí)，應(yīng)免去這種無效操作。即為求Q的值，只需在M.data和N.data中找到相應(yīng)的各對元素（即M.data中的j值和N.data中的i值相等的各對元素）相乘即可。兩個稀疏矩陣相乘（QMN）的過程可大致描述如下：若兩個矩陣是稀疏矩陣并用三元組表作存儲結(jié)構(gòu)時(shí)，就不能套用上述算法。第三十九頁，共一百二十頁，編輯于2023年，星期三

在稀疏矩陣的行邏輯連接的順序表中，N.rpos提供了有關(guān)信息。rpos[row]指示矩陣N的第row行中第一個非零元在N.data中的序號，則rpos[row+1]-1指示矩陣N的第row行中最后一個非零元在N.data中的序號。而最后一行中最后一個非零元在N.data中的序號就是N.tu了。第四十頁，共一百二十頁，編輯于2023年，星期三

（2）稀疏矩陣相乘的基本操作是：對于M.data[P](P=1,2…M.tu)找到N中所有滿足條件M.data[P].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.data[q].v的乘積，這個乘積只是Q[i][j]中的一部分。為便于操作，應(yīng)對每個元素設(shè)一累計(jì)和變量，其初值為零，然后掃描數(shù)組M，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)那罄塾?jì)和的變量上。第四十一頁，共一百二十頁，編輯于2023年，星期三

（3）兩個稀疏矩陣的乘積不一定是稀疏矩陣。反之，即使每個分量值M(i,k)*N(k,j)

不為零，其累加值Q[i][j]也可能為零。因此乘積矩陣Q中的元素是否為非零元，只有在求得累加和后才能確定。由于Q中元素的行號和M中元素的行號一致，又M中元素排列是以M的行序?yàn)橹餍虻?，由此可對Q進(jìn)行逐行處理，先求得累計(jì)求和的中間結(jié)果（Q的一行），然后再壓縮存儲到Q.data中去。第四十二頁，共一百二十頁，編輯于2023年，星期三

Q初始化；If(Q是非零矩陣）{//逐行求積

for(arow=1;arow<=M.tu;++arow{

//處理M每一行

ctemp[]=0;//累加器清零

計(jì)算Q中第arow行的積并存入ctemp[]中；將ctemp[]中非零元壓縮存儲到Q.data;

}//forarow

}//if兩個稀疏矩陣相乘（QMN）的過程可大致描述如下：第四十三頁，共一百二十頁，編輯于2023年，星期三

StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q)

{

if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;

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

for(arow=1;arow<=M.mu;++arow){

//處理M的每一行

}//forarow}//ifreturnOK;}//MultSMatrix算法5.3第四十四頁，共一百二十頁，編輯于2023年，星期三

ctemp[]=0;//當(dāng)前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){//對當(dāng)前行中每一個非零元

brow=M.data[p].j;if(brow<N.nu)t=N.rpos[brow+1];

else{t=N.tu+1}

for(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處理的每一行M第四十五頁，共一百二十頁，編輯于2023年，星期三分析上述算法的時(shí)間復(fù)雜度累加器ctemp初始化的時(shí)間復(fù)雜度為O(M.muN.nu)，求Q的所有非零元的時(shí)間復(fù)雜度為O(M.tuN.tu/N.mu)，進(jìn)行壓縮存儲的時(shí)間復(fù)雜度為O(M.muN.nu)，總的時(shí)間復(fù)雜度就是O(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個數(shù)M.tu=Mmn，

N中非零元的個數(shù)

N.tu=Nnp，相乘算法的時(shí)間復(fù)雜度就是O(mp(1+nMN))

，當(dāng)M<0.05和N<0.05及n<1000時(shí)，相乘算法的時(shí)間復(fù)雜度就相當(dāng)于O(mp)。第四十六頁，共一百二十頁，編輯于2023年，星期三三、十字鏈表對稀疏矩陣的每個非零元，建立一個結(jié)點(diǎn)。結(jié)點(diǎn)形式如下：ijedownright其中：i、j和e分別表示該非零元所在的行、列和非零元的值。向右域right指向同一行中下一個非零元，向下域down指向同一列中下一個非零元。每個非零元既是某個行鏈表中的一個結(jié)點(diǎn)，又是某個列鏈表中的一個結(jié)點(diǎn)，整個矩陣構(gòu)成一個十字交叉的鏈表。第四十七頁，共一百二十頁，編輯于2023年，星期三例如：30050-100200011314522-1312^^^^^^^第四十八頁，共一百二十頁，編輯于2023年，星期三typedefstructOLNode{inti,j;//該非零元的行和列下標(biāo)

ElemTypee;structOLNode*right,*down;

//該非零元所在行表和列表的后繼鏈域

}OLNode;*OLink;typedefstruct{

OLink*rhead,*chead;//行和列鏈表頭指針向量基址由CreateSMatrix分配

intmu,nu,tu;//稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)

}CrossList;第四十九頁，共一百二十頁，編輯于2023年，星期三

Status

CreateSMatrix_OL(CrossList&M){//創(chuàng)建稀疏矩陣M。采用十字鏈表存儲表示。

if(M)free(M);scanf(&m,&n,&t);//輸入M的行數(shù)、列數(shù)和非零元個數(shù)

M.mu:=m;M.nu=n;M.tu:=t;

if(!(M.rhead)=(OLink*)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW);if(!(M.chead)=(OLink*)malloc((n+1)*sizeof(OLink))))exit(OVERFLOW);

M.rhead[]=M.chead[]=NULL;

//初始化行列頭指針向量，各行列鏈表為空鏈表

for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)

){//按任意次序輸入非零元算法5.4第五十頁，共一百二十頁，編輯于2023年，星期三

if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->i=i;p->j=j;p->e=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.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}else{//尋查在行表中的插入位置

for(q=M.chead[i];(q->down)&&q->down->j<j;q=q->down);p->down=q->down;q->down=p;}//完成列插入

}returnOK;}//CreateSMatrix_OL第五十一頁，共一百二十頁，編輯于2023年，星期三5.4廣義表的定義ADTGlist{

數(shù)據(jù)對象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet為某個數(shù)據(jù)對象}

數(shù)據(jù)關(guān)系：

LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist基本操作:顧名思義，廣義表是線性表的推廣，也稱其為列表。第五十二頁，共一百二十頁，編輯于2023年，星期三廣義表是遞歸定義的線性結(jié)構(gòu)，廣義表一般記作：

LS=(1,2,,n)

其中：n是它的長度，i

或?yàn)樵踊驗(yàn)閺V義表。習(xí)慣上，用大寫字母表示廣義表的名稱，用小寫字母表示原子。稱1為LS的表頭，其余元素組成的表(2,,n)是LS的表尾。例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,,)))第五十三頁，共一百二十頁，編輯于2023年，星期三廣義表是一個多層次的線性結(jié)構(gòu)例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce第五十四頁，共一百二十頁，編輯于2023年，星期三廣義表

LS=(1,2,…,n)的結(jié)構(gòu)特點(diǎn):1)廣義表中的數(shù)據(jù)元素有相對次序；2)廣義表的長度定義為最外層包含元素個數(shù)；3)廣義表的深度定義為所含括弧的重?cái)?shù)；注意：“原子”的深度為0

“空表”的深度為14)廣義表可以共享；5)廣義表可以是一個遞歸的表。遞歸表的深度是無窮值，長度是有限值。第五十五頁，共一百二十頁，編輯于2023年，星期三6)任何一個非空廣義表

LS=(1,2,…,n)

均可分解為

表頭

Head(LS)=1

和

表尾

Tail(LS)=(2,…,n)兩部分。例如:

D=(E,F)=((a,(b,c))，F(xiàn))Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()第五十六頁，共一百二十頁，編輯于2023年，星期三

結(jié)構(gòu)的創(chuàng)建和銷毀

InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);狀態(tài)函數(shù)

GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);插入和刪除操作

InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);遍歷

Traverse_GL(L,Visit());基本操作：第五十七頁，共一百二十頁，編輯于2023年，星期三5.5廣義表的存儲結(jié)構(gòu)通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn):原子結(jié)點(diǎn)：tag=1hptptag=0data第五十八頁，共一百二十頁，編輯于2023年，星期三1)表頭、表尾分析法：構(gòu)造存儲結(jié)構(gòu)的兩種分析方法:若表頭為原子，則為空表

ls=NIL非空表lstag=1指向表頭的指針指向表尾的指針tag=0data否則，依次類推。第五十九頁，共一百二十頁，編輯于2023年，星期三第六十頁，共一百二十頁，編輯于2023年，星期三L=(a,(x,y),((x)))a(x,y)(

)

1LL=()0a

1

1

1

1

10x()x((x,y),((x)))(((x)))(x,y)((x))(x)第六十一頁，共一百二十頁，編輯于2023年，星期三//－－－－廣義表的頭尾鏈表存儲表示－－－－typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子，LIST==1:子表typedefstructGLNode{ElemTagtag;//公共部分，用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)

union{//原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分

AtomTypeatom;//atom是原子結(jié)點(diǎn)的值域，AtomType由用戶定義

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

};}*GList;//廣義表類型第六十二頁，共一百二十頁，編輯于2023年，星期三A=NILBCDE∧1e0∧11a01b0∧1d01c01a01∧1∧1∧1圖5.9廣義表的存儲結(jié)構(gòu)示例第六十三頁，共一百二十頁，編輯于2023年，星期三2)子表分析法：若子表為原子，則為空表

ls=NIL非空表

1指向子表1

的指針tag=0datatp否則，依次類推。

1指向子表2

的指針

1指向子表n

的指針ls…第六十四頁，共一百二十頁，編輯于2023年，星期三例如:

a(x,y)((x))LS=(a,(x,y),((x)))ls第六十五頁，共一百二十頁，編輯于2023年，星期三//－－－廣義表的擴(kuò)展線性鏈表存儲表示－－－typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子，LIST==1:子表typedefstructGLNode{ElemTagtag;//公共部分，用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)

union{//原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分

AtomTypeatom;//是原子結(jié)點(diǎn)的值域

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

};structGLNode*tp;//相當(dāng)于線性鏈表的next，指向下一個元素結(jié)點(diǎn)}*GList;//廣義表類型GList是一種擴(kuò)展的線性鏈表第六十六頁，共一百二十頁，編輯于2023年，星期三ABCDE1c0∧1∧1圖5.11列表的另一種鏈表表示∧∧1∧1∧e0∧1∧1∧1a0∧1b0∧1a0∧d0第六十七頁，共一百二十頁，編輯于2023年，星期三

一個m元多項(xiàng)式的表示就是廣義表應(yīng)用的典型實(shí)例。例如三元多項(xiàng)式

p(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15,可以改寫為：

p(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15

即p(x,y,z)=Az2+Bz+15其中

A=((x10+2x6)y3+3x5y2)B=((x4+6x3)y4+2y)A、B又是關(guān)于x、y的多項(xiàng)式，依次類推，上述多項(xiàng)式可以表示為：5.6m元多項(xiàng)式的表示第六十八頁，共一百二十頁，編輯于2023年，星期三

p=z((A,2),(B,1),(15,0))其中：A=y((C,3),(D,2))C=x((1,10),(2,6))D=x((3,5))B=y((E,4),(F,1))E=x((1,4),(6,3))F=x((2,0))第六十九頁，共一百二十頁，編輯于2023年，星期三

可類似于廣義表的第二種存儲結(jié)構(gòu)來定義表示m元多項(xiàng)式的廣義表的存儲結(jié)構(gòu)。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：

其中exp為指數(shù)域,coef為系數(shù)域,hp指向其系數(shù)子表,tp指向同一層的下一結(jié)點(diǎn)。其形式定義說明如下：tag=1exphptp表結(jié)點(diǎn)tag=0expcoeftp原子結(jié)點(diǎn)第七十頁，共一百二十頁，編輯于2023年，星期三typedefstructMPNode{ElemTagtag;//區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)

intexp;//指數(shù)域

union{floatcoef;//系數(shù)域

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

};structMPNode*tp;//相當(dāng)于線性鏈表的next，指向下一個元素結(jié)點(diǎn)}*MPList;//m元多項(xiàng)式廣義表類型第七十一頁，共一百二十頁，編輯于2023年，星期三P圖5.12三元多項(xiàng)式的存儲結(jié)構(gòu)示意圖3∧1211111111113∧10∧0153121410∧0

25∧0

3100

16∧0

240

13∧0

6xyz第七十二頁，共一百二十頁，編輯于2023年，星期三5.7廣義表操作的遞歸函數(shù)遞歸函數(shù)一個含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個條件：

1)在每一次調(diào)用自己時(shí)，必須是(在某種意義上)更接近于解;

2)必須有一個終止處理或計(jì)算的準(zhǔn)則。第七十三頁，共一百二十頁，編輯于2023年，星期三例如:

梵塔的遞歸函數(shù)voidhanoi(int

n,

charx,chary,charz){if

(n==1)move(x,1,z);//遞歸終止

else{

hanoi(n-1,x,z,y);//遞歸調(diào)用

move(x,n,z);

hanoi(n-1,

y,x,z);//遞歸調(diào)用

}}第七十四頁，共一百二十頁，編輯于2023年，星期三二叉樹的前序遍歷

void

PreOrderTraverse(BiTreeT,void(Visit)(BiTreeP))

{

if(T)

{Visit(T->data);(PreOrderTraverse(T->lchild,Visit);(PreOrderTraverse(T->rchild,Visit);

}}//PreOrderTraverse第七十五頁，共一百二十頁，編輯于2023年，星期三一、分治法(DivideandConquer)(又稱分割求解法)如何設(shè)計(jì)遞歸函數(shù)？二、后置遞歸法(Postponingthework)三、回溯法(Backtracking)第七十六頁，共一百二十頁，編輯于2023年，星期三對于一個輸入規(guī)模為n的函數(shù)或問題，用某種方法把輸入分割成k(1<k≤n)個子集，從而產(chǎn)生l

個子問題，分別求解這l個問題，得出

l

個問題的子解，再用某種方法把它們組合成原來問題的解。若子問題還相當(dāng)大，則可以反復(fù)使用分治法，直至最后所分得的子問題足夠小，以至可以直接求解為止。分治法的設(shè)計(jì)思想為:

在利用分治法求解時(shí)，所得子問題的類型常常和原問題相同，因而很自然地導(dǎo)致遞歸求解。第七十七頁，共一百二十頁，編輯于2023年，星期三例如:梵塔問題:

Hanoi(n,x,y,z)可遞歸求解Hanoi(n-1,x,z,y)

將n個盤分成兩個子集(1至n-1和n)，從而產(chǎn)生下列三個子問題：1)將1至n-1號盤從x軸移動至y軸；3)將1至n-1號盤從y軸移動至z軸；2)將n號盤從x軸移動至z軸；可遞歸求解Hanoi(n-1,y,x,z)第七十八頁，共一百二十頁，編輯于2023年，星期三又如:遍歷二叉樹:

Traverse(BT)

可遞歸求解Traverse(LBT)

將n個結(jié)點(diǎn)分成三個子集(根結(jié)點(diǎn)、左子樹和右子樹)，從而產(chǎn)生下列三個子問題：1)訪問根結(jié)點(diǎn)；3)遍歷右子樹;2)遍歷左子樹；可遞歸求解Traverse(RBT)第七十九頁，共一百二十頁，編輯于2023年，星期三廣義表從結(jié)構(gòu)上可以分解成廣義表=表頭+表尾或者廣義表=子表1+子表2+···+子表n因此常利用分治法求解之。算法設(shè)計(jì)中的關(guān)鍵問題是，如何將l

個子問題的解組合成原問題的解。第八十頁，共一百二十頁，編輯于2023年，星期三廣義表的頭尾鏈表存儲表示：typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//標(biāo)志域

union{AtomTypeatom;//原子結(jié)點(diǎn)的數(shù)據(jù)域

struct{structGLNode*hp,*tp;}ptr;

};}*GListtag=1

hp

tpptr表結(jié)點(diǎn)第八十一頁，共一百二十頁，編輯于2023年，星期三廣義表的深度=Max{子表的深度}+15.7.1求廣義表的深度可以直接求解的兩種簡單情況為：

空表的深度=1

原子的深度=0廣義表的深度定義為廣義表中括弧的層數(shù)。

將廣義表分解成n個子表，分別(遞歸)求得每個子表的深度，第八十二頁，共一百二十頁，編輯于2023年，星期三

int

GlistDepth(GlistL){

//返回指針L所指的廣義表的深度

for(max=0,

pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);if(dep>max)max=dep;

}

returnmax+1;}//GlistDepthif(!L)return1;if(L->tag==ATOM)return0;算法5.5第八十三頁，共一百二十頁，編輯于2023年，星期三

1

1

1L…for(max=0,

pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);if(dep>max)max=dep;

}例如:pppp->ptr.hppppppp->ptr.hppp->ptr.hp具體例子，講義P114圖5.13第八十四頁，共一百二十頁，編輯于2023年，星期三5.7.2復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成?？梢灾苯忧蠼獾膬煞N簡單情況為：

空表復(fù)制求得的新表自然也是空表;

原子結(jié)點(diǎn)可以直接復(fù)制求得。前面提到，任何一個非空廣義表均可分解成表頭和表尾；反之，一對確定的表頭和表尾可惟一確定一個廣義表。

將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(fù)制求得新的表頭和表尾，第八十五頁，共一百二十頁，編輯于2023年，星期三若ls=NIL則newls=NIL否則構(gòu)造結(jié)點(diǎn)newls,

由表頭ls->ptr.hp復(fù)制得newhp

由表尾ls->ptr.tp復(fù)制得newtp

并使newls->ptr.hp=newhp,newls->ptr.tp=newtp復(fù)制求廣義表的算法描述如下:第八十六頁，共一百二十頁，編輯于2023年，星期三Status

CopyGList(Glist&T,GlistL){if(!L)T=NULL;//復(fù)制空表

else{if(!(T=(Glist)malloc(sizeof(GLNode))))

exit(OVERFLOW);//建表結(jié)點(diǎn)

T->tag=L->tag;if(L->tag==ATOM)

T->atom=L->atom;//復(fù)制單原子結(jié)點(diǎn)

else{}

}//elsereturnOK;}//CopyGList分別復(fù)制表頭和表尾算法5.6第八十七頁，共一百二十頁，編輯于2023年，星期三CopyGList(T->ptr.hp,

L->ptr.hp);

//復(fù)制求得表頭L->ptr.hp的一個副本T->ptr.hpCopyGList(T->ptr.tp,

L->ptr.tp);//復(fù)制求得表尾L->ptr.tp的一個副本T->ptr.tp語句

CopyGList(T->ptr.hp,

L->ptr.hp);等價(jià)于

CopyGList(newhp,

L->ptr.tp);

T->ptr.hp=newhp;復(fù)制表頭和表尾為：第八十八頁，共一百二十頁，編輯于2023年，星期三5.7.3建立廣義表的存儲結(jié)構(gòu)

對應(yīng)廣義表的不同定義方法相應(yīng)地有不同的創(chuàng)建存儲結(jié)構(gòu)的算法。從上述兩種廣義表操作的遞歸算法中可以發(fā)現(xiàn)：在對廣義表進(jìn)行操作的遞歸定義時(shí)，可有兩種分析方法：一種是把廣義表分解成表頭和表尾；另一種是把廣義表看成是含有n個并列子表（假設(shè)原子也作為子表）的表。第八十九頁，共一百二十頁，編輯于2023年，星期三假設(shè)以字符串S=(1,2,,n)

的形式定義廣義表L，建立相應(yīng)的存儲結(jié)構(gòu)。由于S中的每個子串i定義L的一個子表，從而產(chǎn)生n個子問題，即分別由這n個子串(遞歸)建立n個子表，再組合成一個廣義表?？梢灾苯忧蠼獾膬煞N簡單情況為：由串(

)建立的廣義表是空表；由單字符建立的子表只是一個原子結(jié)點(diǎn)。第九十頁，共一百二十頁，編輯于2023年，星期三如何由子表組合成一個廣義表？首先分析廣義表和子表在存儲結(jié)構(gòu)中的關(guān)系。先看第一個子表和廣義表的關(guān)系:

1L指向廣義表的頭指針指向第一個子表的頭指針第九十一頁，共一百二十頁，編輯于2023年，星期三再看相鄰兩個子表之間的關(guān)系:

1

1指向第i+1個子表的頭指針指向第i個子表的頭指針可見，兩者之間通過表結(jié)點(diǎn)相鏈接。第九十二頁，共一百二十頁，編輯于2023年，星期三若S=()

則L=NIL；否則，構(gòu)造第一個表結(jié)點(diǎn)*L，

并從串S中分解出第一個子串1，對應(yīng)創(chuàng)建第一個子廣義表L->ptr.hp；若剩余串非空，則構(gòu)造第二個表結(jié)點(diǎn)

L->ptr.tp，并從串S中分解出第二個子串2，對應(yīng)創(chuàng)建第二個子廣義表

……；

依次類推，直至剩余串為空串止。第九十三頁，共一百二十頁，編輯于2023年，星期三void

CreateGList(Glist&L,SStringS){if(strcompare(S,emp))L=NULL;//創(chuàng)建空表else{if(!(L=(Glist)malloc(sizeof(GLNode))))exit(overflow);//建表結(jié)點(diǎn)if(Strlength(s)==1){L->tag=ATOM;L->atom=s;}else{//創(chuàng)建單原子廣義表L->tag=List;

p=L;sub=SubString(S,2,StrLength(S)-2);//脫去串S的外層括弧

}//elsereturnOK}

由sub中所含n個子串建立n個子表;算法5.7第九十四頁，共一百二十頁，編輯于2023年，星期三do{//重復(fù)建n個子表sever(sub,

hsub);//從sub中分離出表頭串hsub

CreateGlist(p->ptr.hp,hsub);q=p;if(!StrEmpty(sub){//表尾不空if(!(p=(GLNode*)malloc(sizeof(GLNode))))exit(overflow);p->tag=LIST;q->ptr.tp=p;

}//if}while(!StrEmpty(sub));q->ptr.tp=NULL;//表尾為空表}//else第九十五頁，共一百二十頁，編輯于2023年，星期三Statusserver(Sstring

&str,

SString&hstr)

{//將非空串str分割成兩部分：hsub為第一個‘，’之前的子串，str為之后的子串

n=Strlength(str);i=0;k=0;//k記尚未配對的左括號個數(shù)

Do{//搜索最外層的第一個逗號

++i；

SubString（ch，str，i