数组和广义表新

数组和广义表新第一页，共一百二十页，编辑于2023年，星期三5.1数组的定义5.3矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的定义5.5

广义表的存储结构5.7广义表操作的递归函数5.6m元多项式的表示本章主要内容：第二页，共一百二十页，编辑于2023年，星期三5.1数组的定义ADTArray{

数据对象：

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}n(>0)称为数组的维数，bi是数组第i维的长度，

ji是数组元素的第i维下标，

数据关系：

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

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

基本操作:}ADTArray第三页，共一百二十页，编辑于2023年，星期三二维数组的定义:数据对象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:

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

操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。

DestroyArray(&A)

操作结果：销毁数组A。

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

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。第五页，共一百二十页，编辑于2023年，星期三

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

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。第六页，共一百二十页，编辑于2023年，星期三5.2数组的顺序表示和实现

类型特点:1）只有引用型操作，没有加工型操作；2）数组是多维的结构，而存储空间是一个一维的结构。

有两种顺序映象的方式:

1）以行序为主序（低下标优先）；

2）以列序为主序（高下标优先）。第七页，共一百二十页，编辑于2023年，星期三例如：

称为基地址或基址以“行序为主序”的存储映象二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×La0,1a0,0a0,2a1,0a1,1a1,2二维数组存储结构a0,1a0,0a0,2a1,0a1,1a1,2L第八页，共一百二十页，编辑于2023年，星期三推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n第九页，共一百二十页，编辑于2023年，星期三//－－－－数组的顺序存储表示－－－－#include<stdarg.h>//标准头文件，提供宏va_start、va_arg和va_end,用于存取变长参数表#defineMAX_ARRAY_DIM8//假设数组维数的最大值为8typedefstruct{ElemType*base;//数组元素地址，由InitArray分配

intdim;//数组维数

int*bounds;//数组维界基址，由InitArray分配

int*constants;//数组映像函数常量基址，由InitArray分配}Array;第十页，共一百二十页，编辑于2023年，星期三//－－－－基本操作的函数原型说明－－－－StatusInitArray(Array&A,intdim…);//若维数dim和随后的各维长度合法，则构造相应的数组A，并返回OK。

intDestroyArray(Array&A);//销毁数组AintStrCompare(Array&A,ElemType&e,…)//A是n维数组，e为元素变量，随后是n各下标值。//若各下标不超界，则将e的值赋给所指定的A的元素，并返回OK。第十一页，共一百二十页，编辑于2023年，星期三//－－－－基本操作的算法描述－－－－StatusInitArray(Array&A,intdim,…);

//若维数dim和随后的各维长度合法，则构造相应的数组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的元素总数elemtotalelemtotal=1;va_start(ap,dim);//ap为va_list类型，是存放变长参数表信息的数组

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);//求映像函数的常数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){//销毁数组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指示的各下标值合法，则求出该元素在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维数组，e为元素变量，随后是n各下标值。

//若各下标不超界，则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维数组，e为元素变量，随后是n各下标值。

//若各下标不超界，则e赋值为所指定的A的元素值，并返回OKva_start(ap,e);if((result=Loate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}第十七页，共一百二十页，编辑于2023年，星期三5.3矩阵的压缩存储在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或零元素。有时为节省空间，可以对这类矩阵进行压缩存储。假设值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之，称为稀疏矩阵。第十八页，共一百二十页，编辑于2023年，星期三以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。第十九页，共一百二十页，编辑于2023年，星期三若n阶矩阵A中的元素满足下述性质

aij=aji1<=i,j<=n则称为n阶对称矩阵。5.3.1特殊矩阵对于对称矩阵，可以为每一对对称元分配一个存储空间，则可将n2个元素压缩存储到n(n+1)/2个元的空间中。不失一般性，可以行序为主序存储其下三角（包括对角线）中的元素。非零元在矩阵中的分布有一定规则。例如:上（下）三角矩阵、对角矩阵、对称矩阵等。第二十页，共一百二十页，编辑于2023年，星期三假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A存储结构，则sa[k]

和矩阵元素aij之间存在着一一对应的关系。k=i(i-1)2+j-1

当i>=j对角线下方j(j-1)2+i-1

当i<j对角线上方对于任意给定一组下标(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年，星期三这种压缩存储的方法同样也适应于三角矩阵和对角矩阵。5.3.2稀疏矩阵假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵。何谓稀疏矩阵？nmt×=第二十二页，共一百二十页，编辑于2023年，星期三//－－稀疏矩阵的三元组顺序表存储表示－－

#defineMAXSIZE12500//最大非零元个数

typedefstruct{

inti,j;//该非零元的行下标和列下标

ElemTypee;//该非零元的值

}Triple;//三元组类型一、三元组顺序表typedefunion{

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

intmu,nu,tu;//矩阵的行数、列数和非零元个数}TSMatrix;//稀疏矩阵类型第二十三页，共一百二十页，编辑于2023年，星期三如何求稀疏矩阵的转置矩阵？úúúûùêêêëé--028003600070500140úúúúúúûùêêêêêêëé--005280000007143600转置例如，稀疏矩阵第二十四页，共一百二十页，编辑于2023年，星期三用常规的二维数组表示时的算法其中，M为原稀疏矩阵，T为转置后的稀疏矩阵，其时间复杂度为:O(mu×nu)

for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];第二十五页，共一百二十页，编辑于2023年，星期三用“三元组”表示时如何实现？121415-522-731363428211451-522-713364328a.datab.data第二十六页，共一百二十页，编辑于2023年，星期三

假设a和b是TSMatrix型的变量，分别表示矩阵M和T。可以有两种处理方法：（1）

按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。换句话说，按照矩阵M的列序来进行转置。为了找到M的每一列中所有的非零元素，需要对其三元组表a.data从第一行起整个扫描一遍，由于a.data是以M的行序为主序来存放每个非零元的，由此得到的恰是b.data应有顺序。

具体算法如5.1所示第二十七页，共一百二十页，编辑于2023年，星期三StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组表存储表示，求稀疏矩阵M的转置矩阵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的两重循环中完成的，故算法的时间复杂度为O(nu*tu)。当非零元的个数tu和mu*nu同数量级时，算法5.1的时间复杂度就为O(nu*nu2)了。（2）按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中的准确位置，则对a.data中的三元组依次转置时，便可直接放到b.data中恰当的位置上。第二十九页，共一百二十页，编辑于2023年，星期三需附设num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。cpot[1]=1；cpot[col]=cpot[col-1]+num[col-1]第三十页，共一百二十页，编辑于2023年，星期三例如：下面稀疏矩阵的三元组表示对应各向量值如下：

cpot[1]=1;

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

col12345Num[col]12011Cpot[col]12445该转置方法称为快速转置，如算法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;//列非零元个数

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

…转置矩阵元素算法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]

转置矩阵元素：第三十三页，共一百二十页，编辑于2023年，星期三分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为: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年，星期三三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。为便于随机存取某一行中的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置矩阵算法中建立的，指示‘行’信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种‘带行链接信息’的三元组表为行逻辑链接的顺序表。二、行逻辑联接的顺序表第三十五页，共一百二十页，编辑于2023年，星期三

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

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

intmu,nu,tu;//矩阵的行数、列数和非零元个数

}RLSMatrix;//行逻辑链接顺序表类型行逻辑链接的顺序表的类型描述如下：第三十六页，共一百二十页，编辑于2023年，星期三例如：给定一组下标，求矩阵的元素值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];}其时间复杂度为:O(m1×m2×n1)

两个矩阵相乘的经典算法。若设Q=M*N其中，M是m1*n1矩阵，N是n1*m2矩阵，则第三十八页，共一百二十页，编辑于2023年，星期三（1）乘积矩阵Q中元素

Q(i,j)=∑M(i,k)*N(k,j)在经典算法中，不论M(i,k)和N(k,j)的值是否为零，都要进行一次乘法运算，这两者有一个为零，其乘积也为零。在对稀疏矩阵进行运算时，应免去这种无效操作。即为求Q的值，只需在M.data和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。两个稀疏矩阵相乘（QMN）的过程可大致描述如下：若两个矩阵是稀疏矩阵并用三元组表作存储结构时，就不能套用上述算法。第三十九页，共一百二十页，编辑于2023年，星期三

在稀疏矩阵的行逻辑连接的顺序表中，N.rpos提供了有关信息。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]中的一部分。为便于操作，应对每个元素设一累计和变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。第四十一页，共一百二十页，编辑于2023年，星期三

（3）两个稀疏矩阵的乘积不一定是稀疏矩阵。反之，即使每个分量值M(i,k)*N(k,j)

不为零，其累加值Q[i][j]也可能为零。因此乘积矩阵Q中的元素是否为非零元，只有在求得累加和后才能确定。由于Q中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存储到Q.data中去。第四十二页，共一百二十页，编辑于2023年，星期三

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

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

//处理M每一行

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

计算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;//当前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){//对当前行中每一个非零元

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年，星期三分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为O(M.muN.nu)，求Q的所有非零元的时间复杂度为O(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为O(M.muN.nu)，总的时间复杂度就是O(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数M.tu=Mmn，

N中非零元的个数

N.tu=Nnp，相乘算法的时间复杂度就是O(mp(1+nMN))

，当M<0.05和N<0.05及n<1000时，相乘算法的时间复杂度就相当于O(mp)。第四十六页，共一百二十页，编辑于2023年，星期三三、十字链表对稀疏矩阵的每个非零元，建立一个结点。结点形式如下：ijedownright其中：i、j和e分别表示该非零元所在的行、列和非零元的值。向右域right指向同一行中下一个非零元，向下域down指向同一列中下一个非零元。每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成一个十字交叉的链表。第四十七页，共一百二十页，编辑于2023年，星期三例如：30050-100200011314522-1312^^^^^^^第四十八页，共一百二十页，编辑于2023年，星期三typedefstructOLNode{inti,j;//该非零元的行和列下标

ElemTypee;structOLNode*right,*down;

//该非零元所在行表和列表的后继链域

}OLNode;*OLink;typedefstruct{

OLink*rhead,*chead;//行和列链表头指针向量基址由CreateSMatrix分配

intmu,nu,tu;//稀疏矩阵的行数、列数和非零元个数

}CrossList;第四十九页，共一百二十页，编辑于2023年，星期三

Status

CreateSMatrix_OL(CrossList&M){//创建稀疏矩阵M。采用十字链表存储表示。

if(M)free(M);scanf(&m,&n,&t);//输入M的行数、列数和非零元个数

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;//生成结点

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{

数据对象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet为某个数据对象}

数据关系：

LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist基本操作:顾名思义，广义表是线性表的推广，也称其为列表。第五十二页，共一百二十页，编辑于2023年，星期三广义表是递归定义的线性结构，广义表一般记作：

LS=(1,2,,n)

其中：n是它的长度，i

或为原子或为广义表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。称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年，星期三广义表是一个多层次的线性结构例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce第五十四页，共一百二十页，编辑于2023年，星期三广义表

LS=(1,2,…,n)的结构特点:1)广义表中的数据元素有相对次序；2)广义表的长度定义为最外层包含元素个数；3)广义表的深度定义为所含括弧的重数；注意：“原子”的深度为0

“空表”的深度为14)广义表可以共享；5)广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。第五十五页，共一百二十页，编辑于2023年，星期三6)任何一个非空广义表

LS=(1,2,…,n)

均可分解为

表头

Head(LS)=1

和

表尾

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

D=(E,F)=((a,(b,c))，F)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年，星期三

结构的创建和销毁

InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);状态函数

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广义表的存储结构通常采用头、尾指针的链表结构表结点:原子结点：tag=1hptptag=0data第五十八页，共一百二十页，编辑于2023年，星期三1)表头、表尾分析法：构造存储结构的两种分析方法:若表头为原子，则为空表

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;//公共部分，用于区分原子结点和表结点

union{//原子结点和表结点的联合部分

AtomTypeatom;//atom是原子结点的值域，AtomType由用户定义

struct{structGLNode*hp,*tp;}ptr;//ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾

};}*GList;//广义表类型第六十二页，共一百二十页，编辑于2023年，星期三A=NILBCDE∧1e0∧11a01b0∧1d01c01a01∧1∧1∧1图5.9广义表的存储结构示例第六十三页，共一百二十页，编辑于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年，星期三//－－－广义表的扩展线性链表存储表示－－－typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子，LIST==1:子表typedefstructGLNode{ElemTagtag;//公共部分，用于区分原子结点和表结点

union{//原子结点和表结点的联合部分

AtomTypeatom;//是原子结点的值域

structGLNode*hp;//表结点的表头指针

};structGLNode*tp;//相当于线性链表的next，指向下一个元素结点}*GList;//广义表类型GList是一种扩展的线性链表第六十六页，共一百二十页，编辑于2023年，星期三ABCDE1c0∧1∧1图5.11列表的另一种链表表示∧∧1∧1∧e0∧1∧1∧1a0∧1b0∧1a0∧d0第六十七页，共一百二十页，编辑于2023年，星期三

一个m元多项式的表示就是广义表应用的典型实例。例如三元多项式

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又是关于x、y的多项式，依次类推，上述多项式可以表示为：5.6m元多项式的表示第六十八页，共一百二十页，编辑于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年，星期三

可类似于广义表的第二种存储结构来定义表示m元多项式的广义表的存储结构。链表的结点结构为：

其中exp为指数域,coef为系数域,hp指向其系数子表,tp指向同一层的下一结点。其形式定义说明如下：tag=1exphptp表结点tag=0expcoeftp原子结点第七十页，共一百二十页，编辑于2023年，星期三typedefstructMPNode{ElemTagtag;//区分原子结点和表结点

intexp;//指数域

union{floatcoef;//系数域

structMPNode*hp;//表结点的表头指针

};structMPNode*tp;//相当于线性链表的next，指向下一个元素结点}*MPList;//m元多项式广义表类型第七十一页，共一百二十页，编辑于2023年，星期三P图5.12三元多项式的存储结构示意图3∧1211111111113∧10∧0153121410∧0

25∧0

3100

16∧0

240

13∧0

6xyz第七十二页，共一百二十页，编辑于2023年，星期三5.7广义表操作的递归函数递归函数一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：

1)在每一次调用自己时，必须是(在某种意义上)更接近于解;

2)必须有一个终止处理或计算的准则。第七十三页，共一百二十页，编辑于2023年，星期三例如:

梵塔的递归函数voidhanoi(int

n,

charx,chary,charz){if

(n==1)move(x,1,z);//递归终止

else{

hanoi(n-1,x,z,y);//递归调用

move(x,n,z);

hanoi(n-1,

y,x,z);//递归调用

}}第七十四页，共一百二十页，编辑于2023年，星期三二叉树的前序遍历

void

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

{

if(T)

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

}}//PreOrderTraverse第七十五页，共一百二十页，编辑于2023年，星期三一、分治法(DivideandConquer)(又称分割求解法)如何设计递归函数？二、后置递归法(Postponingthework)三、回溯法(Backtracking)第七十六页，共一百二十页，编辑于2023年，星期三对于一个输入规模为n的函数或问题，用某种方法把输入分割成k(1<k≤n)个子集，从而产生l

个子问题，分别求解这l个问题，得出

l

个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。分治法的设计思想为:

在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。第七十七页，共一百二十页，编辑于2023年，星期三例如:梵塔问题:

Hanoi(n,x,y,z)可递归求解Hanoi(n-1,x,z,y)

将n个盘分成两个子集(1至n-1和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个结点分成三个子集(根结点、左子树和右子树)，从而产生下列三个子问题：1)访问根结点；3)遍历右子树;2)遍历左子树；可递归求解Traverse(RBT)第七十九页，共一百二十页，编辑于2023年，星期三广义表从结构上可以分解成广义表=表头+表尾或者广义表=子表1+子表2+···+子表n因此常利用分治法求解之。算法设计中的关键问题是，如何将l

个子问题的解组合成原问题的解。第八十页，共一百二十页，编辑于2023年，星期三广义表的头尾链表存储表示：typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//标志域

union{AtomTypeatom;//原子结点的数据域

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

};}*GListtag=1

hp

tpptr表结点第八十一页，共一百二十页，编辑于2023年，星期三广义表的深度=Max{子表的深度}+15.7.1求广义表的深度可以直接求解的两种简单情况为：

空表的深度=1

原子的深度=0广义表的深度定义为广义表中括弧的层数。

将广义表分解成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复制广义表新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为：

空表复制求得的新表自然也是空表;

原子结点可以直接复制求得。前面提到，任何一个非空广义表均可分解成表头和表尾；反之，一对确定的表头和表尾可惟一确定一个广义表。

将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，第八十五页，共一百二十页，编辑于2023年，星期三若ls=NIL则newls=NIL否则构造结点newls,

由表头ls->ptr.hp复制得newhp

由表尾ls->ptr.tp复制得newtp

并使newls->ptr.hp=newhp,newls->ptr.tp=newtp复制求广义表的算法描述如下:第八十六页，共一百二十页，编辑于2023年，星期三Status

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

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

exit(OVERFLOW);//建表结点

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

T->atom=L->atom;//复制单原子结点

else{}

}//elsereturnOK;}//CopyGList分别复制表头和表尾算法5.6第八十七页，共一百二十页，编辑于2023年，星期三CopyGList(T->ptr.hp,

L->ptr.hp);

//复制求得表头L->ptr.hp的一个副本T->ptr.hpCopyGList(T->ptr.tp,

L->ptr.tp);//复制求得表尾L->ptr.tp的一个副本T->ptr.tp语句

CopyGList(T->ptr.hp,

L->ptr.hp);等价于

CopyGList(newhp,

L->ptr.tp);

T->ptr.hp=newhp;复制表头和表尾为：第八十八页，共一百二十页，编辑于2023年，星期三5.7.3建立广义表的存储结构

对应广义表的不同定义方法相应地有不同的创建存储结构的算法。从上述两种广义表操作的递归算法中可以发现：在对广义表进行操作的递归定义时，可有两种分析方法：一种是把广义表分解成表头和表尾；另一种是把广义表看成是含有n个并列子表（假设原子也作为子表）的表。第八十九页，共一百二十页，编辑于2023年，星期三假设以字符串S=(1,2,,n)

的形式定义广义表L，建立相应的存储结构。由于S中的每个子串i定义L的一个子表，从而产生n个子问题，即分别由这n个子串(递归)建立n个子表，再组合成一个广义表。可以直接求解的两种简单情况为：由串(

)建立的广义表是空表；由单字符建立的子表只是一个原子结点。第九十页，共一百二十页，编辑于2023年，星期三如何由子表组合成一个广义表？首先分析广义表和子表在存储结构中的关系。先看第一个子表和广义表的关系:

1L指向广义表的头指针指向第一个子表的头指针第九十一页，共一百二十页，编辑于2023年，星期三再看相邻两个子表之间的关系:

1

1指向第i+1个子表的头指针指向第i个子表的头指针可见，两者之间通过表结点相链接。第九十二页，共一百二十页，编辑于2023年，星期三若S=()

则L=NIL；否则，构造第一个表结点*L，

并从串S中分解出第一个子串1，对应创建第一个子广义表L->ptr.hp；若剩余串非空，则构造第二个表结点

L->ptr.tp，并从串S中分解出第二个子串2，对应创建第二个子广义表

……；

依次类推，直至剩余串为空串止。第九十三页，共一百二十页，编辑于2023年，星期三void

CreateGList(Glist&L,SStringS){if(strcompare(S,emp))L=NULL;//创建空表else{if(!(L=(Glist)malloc(sizeof(GLNode))))exit(overflow);//建表结点if(Strlength(s)==1){L->tag=ATOM;L->atom=s;}else{//创建单原子广义表L->tag=List;

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

}//elsereturnOK}

由sub中所含n个子串建立n个子表;算法5.7第九十四页，共一百二十页，编辑于2023年，星期三do{//重复建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记尚未配对的左括号个数

Do{//搜索最外层的第一个逗号

++i；

SubString（ch，str，i