《第5章 数组和广义表》习题解答.doc 43页

'第5章数组和广义表第5章数组和广义表本章学习要点◆掌握多维数组在行优先顺序存储结构中地址的计算方法◆了解特殊矩阵压缩存储时的下标转换方法◆掌握稀疏矩阵常用的两种压缩存储表示方法（三元组表和十字链表表示法）的特点和存储结构◆掌握稀疏矩阵在三元组表表示下的基本运算（矩阵加法、减法、转置和乘法等）方法◆了解广义表的有关概念、广义表的各种表示方法和存储结构◆掌握广义表的基本操作（求广义表的表头、表尾、表的深度以及广义表的复制等）数组是最常用的数据结构之一，几乎所有的高级程序设计语言都把数组类型设定为内部类型。在前面讨论的线性结构中，其数据元素都是非结构的原子类型，元素的值是不可再分解的。本章所讨论的数组可以看成是线性表的一种扩展，即线性表中的每个数据元素本身也是一个线性表。稀疏矩阵是一种特殊的二维数组，因其在压缩存储方面的特点而被广泛使用。广义表是一种较为复杂的数据结构，它是线性结构和树型结构的拓广。广义表被广泛应用于人工智能等领域。5.1数组的概念5.1.1数组的定义如果一个向量的所有元素又都是向量（或称子向量），且这些子向量具有相同的上限和下限标号，那么这种特殊形式的向量称为数组。一维数组是一个向量，它的每一个元素都是该结构中不可分割的最小单位。n(n>1)维数组是一个向量，它的每个元素都是n-1维数组，且具有相同的上限和下限。从逻辑结构上看，n维数组Array中各元素的位置由该元素的下标唯一确定，一旦给定一组下标(j0,,j1,j2,…,jn-1)，都存在唯一的一个与其相对应的元素值a称为数组元素，记为a(j0,,j1,j2,…,jn-1)。其中，0<=ji=0;i--)//计算数组元素的映像常数向量A.constent[i]=A.constent[i+1]*A.bounds[i+1];return1;}3．根据下标(script)提取数组元素的操作操作intValue(ArrayA,int*script,EType&e)的功能是，根据下标向量script提取数组A中相应元素的值到e中。如果下标合理返回1表示提取成功，否则返回0表示操作失败。intValue(ArrayA,int*script,EType&e){inti,off=0;for(i=0;i=A.bounds[i]||script[i]<0)return0;off+=script[i]*A.constent[i];//计算对应元素的偏移量off}e=A.base[off];return1;}简化的提取数组元素操作函数ETypeValue(ArrayA,int*script)，该操作对下标越界不做检查。ETypeValue(ArrayA,int*script){inti,off=0;for(i=0;i=A.bounds[i]||script[i]<0)return0;off+=script[i]*A.constent[i];//计算对应元素的偏移量off}A.base[off]=e;return1;}5．数组的按行序输入操作-.133.- 第5章数组和广义表操作voidArrayInput(Array&A)的功能是，以左下标为主序依次输入多维数组A中各元素的值。voidArrayInput(Array&A){intlength=1,i;for(i=0;i>A.base[i];}6．数组的按行序输出操作操作voidArrayoutput(ArrayA)的功能是，按左下标为主序，输出一维、二维、三维和多维数组A中的元素。voidArrayoutput(ArrayA){ints[3],i,len=1;switch(A.dim){case1://按一维数组格式输出for(s[0]=0;s[0]b时，a[i][j]=0，带状区域的元素个数为：(2b+1)n-(b+1)b。例如，图5.4所示的5阶矩阵D5×5就是一个半带宽为b=2，带宽为m=5的带状阵。-.133.- 第5章数组和广义表可将带宽为m的n阶方阵An×n中的非零元素压缩存储到一维数组B[(n-1)m+1]中。压缩存储过程是，对所有带状区域中的元素按行优先的顺序存储，并且除了第一行和最后一行外，每行都按照m（即2b+1）个非零元素计算，如果该行中的区域元素不够m个时要采用左、右零补齐的方法。这样，A中元素a[i][j]与B中元素B[k]的对应关系是：图5.5是带状矩阵D的压缩存储示意图。5.3.2稀疏矩阵1．稀疏矩阵的概念当用矩阵表示某个数学模型时，经常出现这样一些特殊矩阵，它的阶数很高且非零元素的个数远远小于矩阵中零元素的个数，我们称这样的矩阵为稀疏矩阵(sparsematrix)。假设矩阵Am×n中有t个非零元素，令δ=t/(m×n)，则称δ为矩阵A的稀疏因子。通常认为，当δ≤0.05时称矩阵Am×n为稀疏矩阵。图5.6给出两个稀疏矩阵A5×5和B5×5的通常表示形式，显然矩阵B为矩阵A的装置。对于稀疏矩阵，若按通常办法将零元素与非零元素一起存储起来，显然浪费了大量的存储空间，本节讨论有关稀疏矩阵的三元组压缩存储问题以及三元组存储矩阵的基本运算方法。2．稀疏矩阵的三元组表示在稀疏矩阵的压缩存储过程中，可以只考虑非零元素的存储以达到压缩矩阵存储空间的目的。但是，稀疏矩阵中非零元素的出现是没有规律的，如果只是简单地将它们一个挨一个存放起来，将来就很难按行、列号找到它们。所以在存储一个非零元素A[i][j]的值aij时，必须同时将它的行下标i和列下标j一起存储起来，即组成一个三元组(i,j,aij)。将一个稀疏矩阵的所有非零元素都用三元组来表示，若用顺序存储结构，就构成一个向量，该向量的每个分量是一个三元组。对于图5.6中的稀疏矩阵A，可按行优先的顺序用三元组顺序表示成向量：-.133.- 第5章数组和广义表((0,2,-9),(0,4,5),(1,0,-7),(1,2,7),(3,1,8),(4,2,9))同理，稀疏矩阵B可用三元组顺序表示为向量：((0,1,-7),(1,3,8),(2,0,-9),(2,1,7),(2,4,9),(4,0,5))3．稀疏矩阵的基本操作由于稀疏矩阵是一种特殊的矩阵，所以有关稀疏矩阵的基本运算即为矩阵的基本运算。其主要操作有：（1）创建CreatSMatrix(&M)该操作创建稀疏矩阵M；（2）复制CopySMatrix(M,&T)该操作由稀疏矩阵M复制到T；（3）加法AddSMatrix(A,B,&C)其功能是求稀疏矩阵A、B的和C；（4）减法SubMatrix(A,B,&C)其功能是求稀疏矩阵A减B的差C；（5）转置TransSMatrix(M,&T)其功能是求稀疏矩阵M的转置T；（6）乘法MulMatrix(A,B,&C)其功能是求稀疏矩阵A、B的积C。5.3.3稀疏矩阵的顺序存储表示与实现1．稀疏矩阵的顺序存储结构在C++语言程序设计环境中，可定义稀疏矩阵的顺序存储结构为#include"iostream.h"#defineMAXSIZE2000//定义非零元素的最大总数即三元组的最大容量typedefintEtype;//此处定义数组元素的类型为整型以便于上机操作structTriple//定义三元组结构类型{inti,j;Etypee;};structTSMatrix{Tripledata[MAXSIZE+1];intmu,nu,tu;//mu---行数,nu---列数,tu---非零元素总数};说明：在用三元组的顺序存储来表示一个稀疏矩阵时，还必须同时确定该矩阵的行数(mu)和列数(nu)，只有这样才能保证矩阵的三元组表示与原矩阵的一一对应。按行优先的顺序可将图5.6中的稀疏矩阵A、B顺序表示为图5.7中的三元组A.data和B.data。其中，A.mu、A.nu、B.mu、B.nu的值均为5，A.tu、B.tu的值为6。2．稀疏矩阵的输入操作操作voidCreate_TSM(TSMatrix-.133.- 第5章数组和广义表&T)的功能是，根据行优先的顺序创建一个三元组顺序表示的稀疏矩阵T。voidCreate_TSM(TSMatrix&T){intk;cout<<"请输入行数和列数:";cin>>T.mu>>T.nu;T.tu=0;cout<<"输入ije:n";do{k=++T.tu;cin>>T.data[k].i>>T.data[k].j>>T.data[k].e;}while(T.data[k].iN.data[q].j)A.data[r++]=N.data[q++];else{if(e=M.data[p].e+N.data[q].e)//如果和不为零则保存结果{A.data[r]=M.data[p];A.data[r++].e=e;}p++;q++;}}elseif(M.data[p].ij)break;}return0;}（3）函数voidMult_TSM(TSMatrixA,TSMatrixB,TSMatrix&C)的功能是，实现三元组矩阵的乘法运算C=A×B。voidMult_TSM(TSMatrixA,TSMatrixB,TSMatrix&C){inti,j,k;Etypes,e1,e2;int*Anum=newint[A.mu];int*Bnum=newint[B.mu];Frpot(Anum,A);Frpot(Bnum,B);C.mu=A.mu;C.nu=B.nu;C.tu=0;for(i=0;i=M.mu||j<0||j>=M.nu)return(0);M.tu++;p=newOLNode;p->e=e,p->i=i,p->j=j;if(!M.rhead[i]||M.rhead[i]->j>j){p->right=M.rhead[i];M.rhead[i]=p;}else{for(q=M.rhead[i];q->right&&q->right->jright);p->right=q->right;q->right=p;}if(!M.chead[j]||M.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}else{for(q=M.chead[j];q->down&&q->down->idown);p->down=q->down;q->down=p;}return(1);}4．十字链的建立操作函数voidCreate_OL(CrossList&M)的功能是，在十字链表M中随机插入若干个非零元素的三元组。voidCreate_OL(CrossList&M){intm,n,i,j;Etypee;cout<<"CreateCrossMatrix:n输入行数和列数mn:n";cin>>m>>n;Init_OL(M,m,n);cout<<"inputije(e=0退出):n";while(1){cin>>i>>j>>e;if(!Insert_OL(M,i,j,e))break;}-.133.- 第5章数组和广义表}5．十字链的遍历操作函数voidPrint_OL(CrossListM)的作用是，以三元组形式输出用十字链表表示的稀疏矩阵M的所有非零元素及其所在的行、列下标。voidPrint_OL(CrossListM){inti;Olinkp;for(i=0;iright)cout<<"("<i<<""<j<<""<e<<")n";}6．十字链表存储的稀疏矩阵矩阵的输入输出演示程序voidmain(){CrossListMM;inty=1;while(y==1){Create_OL(MM);cout<<"yourinputis:n";Print_OL(MM);cout<<"继续吗(y=1/no=2)?";cin>>y;}}运行结果为：-.133.-第5章数组和广义表CreateCrossMatrix:输入行数和列数mn:46↙inputije(e=0退出):029↙115↙151↙204↙252↙338↙000↙yourinputis:(029)(115)(151)(204)(252)(338)继续吗(y=1/no=2)?1CreateCrossMatrix:输入行数和列数mn:46↙inputije(e=0退出):338↙204↙115↙029↙151↙252↙000↙yourinputis:(029)(115)(151)(204)(252)(338)继续吗(y=1/no=2)?-.133.-第5章数组和广义表5.4广义表5.4.1广义表的概念广义表是n(n≥0)个数据元素a1,a2,a3,…,an的有限序列，记为：LS=。其中，LS称为广义表的表名，n称为广义表LS的长度，当n为0时称LS为空表，-.133.- 第5章数组和广义表ai(i=1,2,3,…,n)称为广义表的元素。广义表中的元素既可以是单个元素称为原子（通常用小写字母表示），也可以是广义表称为子表（通常用大写字母表示），当LS非空时称第一个元素a1为广义表LS的表头(Head)，而(a2,a3,…,an)称为广义表LS的表尾(Tail)。广义表中括号的最大重数称为该广义表的深度。显然，广义表是一种递归定义的数据结构，虽然它也是线性结构但是它与线性表有着明显的差别。广义表的这一特点在处理具有层次特点的线性结构问题时有着独特的功能。【例5.4】求广义表的长度、深度、表头和表尾（如果存在）。（1）A=()A是一个空表，长度为0，深度为1，不存在表头和表尾。（2）B=(e)B是一个广义表，只有一个原子e，长度为1，深度为1，表头为原子e，表尾为空表()。（3）C=(a,(b,c,d))C是一个广义表，有两个元素，第一个a为原子，第二个(b,c,d)为子表，所以长度为2，深度为2，它的表头为a,表尾为((b,c,d))。（4）D=(A，B，C)D=((),(e),(a,(b,c,d)))是广义表，长度为3，深度为3，表头为A=()，表尾为(B,C)=((e),(a,(b,c,d)))。（5）E=(a,E)E=(a,(a,(a,…)))是一个广义表，长度为2，深度为无限大，表头为a，表尾为(E)。5.4.2广义表的特点和基本操作1．广义表的几个重要特点（1）广义表中的元素还可以是广义表，可见它是一个多层次结构。用□表示原子，用○表示广义表，可以用图形形象地将[例5.4]中的广义表D表示为图5.10(a)。（2）一个广义表可以为其它广义表共享。如[例5.4]中的广义表D。（3）广义表可以是一个递归定义的广义表，如[例5.4]中的广义表E。此时深度为无限大，其图形结构如图5.10(b)所示。-.133.- 第5章数组和广义表（4）非空广义表的表尾还是一个广义表，且表尾的深度≤原表的深度，表尾的长度比原表少一；而表头可以是原子，也可以是子表。注意：广义表（）和（（））是两个不同的广义表。前者为空表而后者非空，其长度为1深度为2。2．广义表的基本操作广义表的基本操作主要有：（1）初始化InitGList(&L)其功能是创建一个空表L；（2）创建CreateGList(&L,S)其操作结果为，由广义表串S创建广义表L；（3）复制CopyGList(&T,L)该操作的结果是由广义表L复制得到广义表T；（4）求长度GetLength(L)该操作的功能是返回广义表L的长度；（5）求深度GetDepth(L)该操作的功能是返回广义表L的深度；（6）求表头Head(L)该操作的功能是返回广义表L的表头；（7）求表尾Tail(L)该操作的功能是返回广义表L的表尾；（8）插入操作InsertFirst_GL(&L,e)该操作插入元素e作为广义表L的第一个元素；（9）删除操作DeleteFirst_GL(&L,&e)该操作的结果是，删除广义表L的第一个元素，并用e返回其值；（10）遍历操作Traverse_GL(L)该操作的功能是依次输出L中的每个数据元素。【例5.5】求下列对广义表进行基本操作的结果：（1）Head【((a,b),(c,d))】；（2）Head【Tail【((a,b),(c,d))】】；（3）Tail【Head【((a,b),(c,d))】】；（4）Tail【Head【Tail【((a,b),(c,d))】】】；（5）Head【Tail【Head【((a,b),(c,d))】】】。（说明：用【】作为基本操作的函数符号以示区别。）解：（1）Head【((a,b),(c,d))】=(a,b)（2）Head【Tail【((a,b),(c,d))】】=Head【((c,d))】=(c,d)（3）Tail【Head【((a,b),(c,d))】】=Tail【(a,b)】=(b)（4）Tail【Head【Tail【((a,b),(c,d))】】】=Tail【Head【((c,d))】】=Tail【(c,d)】=(d)（5）Head【Tail【Head【((a,b),(c,d))】】】=Head【Tail【(a,b)】】=Head【(b)】=b5.4.3用链式存储结构表示广义表广义表通常采用链式存储结构，每个数据元素可用一个结点来表示，为了区分该结点是原子或子表，在结点中设置一个标志域tag，当tag=0时表示结点为原子结点，tag=1时表示结点为子表结点。对于子表结点，设置指向头表的指针域hp和指向表尾的指针域tp；而对于原子结则设置数据域atom。其结构如图5.11所示。-.133.- 第5章数组和广义表例如，对于[例5.4]中的广义表：（1）A=()。（2）B=(e)。（3）C=(a,(b,c,d))。（4）D=((),(e),(a,(b,c,d)))。（5）E=(a,E)。可用链式存储方式表示为图5.12的形式。由于广义表本身是递归定义的，所以广义表的存储结构也用递归的方式来定义是必然的。在C++语言中用以下结构类型来表示广义表。typedefcharAtomType;//定义广义表的数据域data的类型为charenumElemTag{ATOM,LIST};//定义结点标志域tag的类型为枚举(enum)类型ElemTag其中，ElemTag为枚举类型(enum)，该类型变量的值只能是ATOM（其值为0表示原子）或LIST（其值为1表示广义表）。typedefstructGLNode//定义结点的结构类型GLNode{ElemTagtag;union//定义结点信息域Data的类型为共同体类型(union){AtomTypedata;//定义结点的数据域data的类型为AtomTypestruct{GLNode*hp,*tp;}ptr;//定义广义表的表头(hp)、表尾(tp)指针域ptr的类型为无名结构体}Data;}*GList;//定义广义表类型GList5.4.4广义链表中基本操作的实现由于广义表的存储结构类型是递归定义的，在广义表基本操作的算法中采用递归的方法较为简单。本节中有关广义表的所有基本操作均采用递归的方法进行处理。1．求广义表GL的深度的递归算法intGListDepth(GListGL)该操作的算法的思想是，先用递归算法算出广义表GL中所有子表的深度的最大值max，-.133.- 第5章数组和广义表再返回该广义表GL的深度max+1。算法的程序实现如下：intGListDepth(GListGL){intmax,dep;GListpp;if(!GL)return(1);//空表的深度为1if(GL->tag==ATOM)return(0);//原子的深度为0for(max=0,pp=GL;pp;pp=pp->Data.ptr.tp)//计算所有子表的最大深度max{dep=GListDepth(pp->Data.ptr.hp);if(dep>max)max=dep;}return(max+1);//返回广义表GL的深度max+1}2．求广义表GL的长度的递归算法intGListLength(GListGL)该算法的递归过程是，广义表GL的长度值=GL的尾表的长度值+1。其程序实现代码如下：intGListLength(GListGL){inth;if(!GL)h=0;elseh=GListLength(GL->Data.ptr.tp)+1;return(h);}3．将广义表L复制到广义表T的递归算法voidCopyGList(GList&T,GListL)该算法的递归过程是，先复制广义表的标志域(tag)再根据其值的不同情况复制广义表的数据域(data)或指针域(ptr)中的表头和表尾。其程序实现代码如下：voidCopyGList(GList&T,GListL)//用递归方法完成由广义表L复制得到广义表T的操作{if(!L)T=NULL;else{T=newGLNode;T->tag=L->tag;if(L->tag==ATOM)T->Data.data=L->Data.data;else{CopyGList(T->Data.ptr.hp,L->Data.ptr.hp);//复制广义表L的表头到TCopyGList(T->Data.ptr.tp,L->Data.ptr.tp);//复制广义表L的表尾到T-.133.- 第5章数组和广义表}}}4．由广义表字符序列str创建广义链表L的递归算法：voidCreateGList(GList&L,AtomType*str)(1)函数voidSever(AtomType*&str,AtomType*&hstr)的功能是，从str中取出所有括号”()”之外的第一个逗号","之前的子字符串赋给hstr，并且使str成为删去子串hstr和","之后的剩余串。若str中没有逗号","，则将str复制到hstr中并使str=NULL。比如：操作前str=”((a),b),(((c))),(d,e),((f))”，操作后的结果为str=”(((c))),(d,e),((f))”，hstr=”((a),b)”。voidSever(AtomType*&str,AtomType*&hstr){inti,j=0,k;AtomTypech;for(i=0,k=0;(ch=str[i])&&(ch!=","||k!=0);i++)//k表示”(”的重数{//程序从str中逐个复制字符到htsr中，直到遇见”()”之外的第一个逗号","或str结束为止hstr[i]=ch;if(ch=="(")k++;elseif(ch==")")k--;}hstr[i]="";if(ch==",")while(str[j++]=str[++i]);//从str中删除hstrelsestr[0]="";}(2)用递归算法由str创建广义链表L的过程是：1）如果str=”()”，L=NULL返回，否则先建立一个结点(GLNode)使L指向该结点，执行2）。2）如果str中只有原子(ATOM)数据，则L->tag=ATOM;L->Data.data=str[0];返回，否则执行3）。3）L->tag=LIST;p=L;取str中所有子表组成的串sub，执行4）。4）逐个创建p的每一个子广义链表。其程序实现代码如下：voidCreateGList(GList&L,AtomType*&str){intn=0,i,j;GListp;while(str[n])n++;AtomType*hstr=newAtomType[n+1];AtomType*sub=newAtomType[n+1];if(str[0]=="("&&str[1]==")"&&!str[2])L=NULL;else-.133.- 第5章数组和广义表{L=p=newGLNode;if(str[0]&&!str[1]){L->tag=ATOM;L->Data.data=str[0];}else{p->tag=LIST;for(i=1,j=0;sub[j]=str[i];i++)j++;//将str[]中()内的字符序列赋值到数组sub[]中sub[j-1]="";do{Sever(sub,hstr);//取表头元素序列CreateGList(p->Data.ptr.hp,hstr);//创建p的头表if(sub[0])//创建表尾结点p{p->Data.ptr.tp=newGLNode;p=p->Data.ptr.tp;p->tag=LIST;}}while(sub[0]);p->Data.ptr.tp=NULL;//结束循环后的为表为空表}}delete[]sub;delete[]hstr;}5．遍历广义链表GL的递归算法voidTraverse_GL(GListGL)递归遍历广义链表GL的执行过程：如果GL为空表则输出”()”，如果GL为原子则输出dada值。否则，从前往后逐个递归遍历每个子表。算法的实现代码如下：voidTraverse_GL(GListGL){GListp;if(!GL)cout<<"()";else{if(GL->tag==ATOM)cout<Data.data;else{cout<<"(";p=GL;while(p){Traverse_GL(p->Data.ptr.hp);p=p->Data.ptr.tp;if(p)cout<<",";}-.133.- 第5章数组和广义表cout<<")";}}}6．对广义链表GL的表头遍历的递归算法voidHead(GListGL)该操作的实现过程类似于算法voidTraverse_GL(GListGL)，算法的实现代码如下：voidHead(GListGL){GListh;cout<<"广义表:";Traverse_GL(GL);cout<tag==ATOM)cout<<"为原子或空表不能取表头n";else{cout<<"表头为:";h=GL->Data.ptr.hp;if(h->tag==ATOM)cout<Data.data;elseTraverse_GL(h);cout<tag==ATOM)cout<<"为原子或空表不能取表尾n";else{cout<<"表尾为:";h=GL->Data.ptr.tp;Traverse_GL(h);cout<>str;CreateGList(GL,str);cout<<"(1)遍历结果为:";Traverse_GL(GL);cout<’表示‘，’；（3）遇到中间的‘^’表示‘（）’；（4）遇到右面的‘^’表示‘)’。三、编程设计1．编写一个函数，将整型数组A[0,…,n-1]中的所有奇数移到偶数之前，并且要求只用一个元素大小的附加存储空间，且时间复杂度为O(n)。-.133.-第5章数组和广义表voidfunc51(intA[],intn){intt=*A,i=0,j=n-1;while(i>T.mu>>T.nu;T.tu=0;cout<<"输入ije:n";while(1){cin>>te.i>>te.j>>te.e;-.133.- 第5章数组和广义表if(te.i>=T.mu||te.j>=T.nu||!te.e)break;k=T.tu++;while(k>=1&&(T.data[k].i>te.i||(T.data[k].i==te.i&&T.data[k].j>te.j))){T.data[k+1]=T.data[k];k--;}T.data[k+1]=te;}}3．在用三元组顺序表示稀疏矩阵的情况下，编写实现稀疏矩阵A和稀疏矩阵B的减法运算：C=A-B。并且要求C也是用三元组顺序表示的稀疏矩阵。voidSub_TSM(TSMatrixA,TSMatrixB,TSMatrix&C){intp;for(p=1;p<=B.tu;p++)B.data[p].e*=-1;Add_TSM(A,B,C);}4．在用三元组顺序表示稀疏矩阵的情况下，编写实现稀疏矩阵A和稀疏矩阵B的乘法运算：C=A×B。其中矩阵C可以是用通常存储方式存储的矩阵。（1）函数voidFrpot(intrpot[],TSMatrixM)完成的操作是，求稀疏矩阵M中每行起始位置的向量rpot。voidFrpot(intrpot[],TSMatrixM){intraw,t,*num=newint[M.mu];for(raw=0;rawj)break;}return0;}voidMult_TSM(TSMatrixA,TSMatrixB,TSMatrix&C){inti,j,k;-.133.- 第5章数组和广义表Etypes,e1,e2;int*Anum=newint[A.mu],*Bnum=newint[B.mu];Frpot(Anum,A);Frpot(Bnum,B);C.mu=A.mu;C.nu=B.nu;C.tu=0;for(i=0;ijj){Insert_OL(C,p->i,p->j,p->e);p=p->right;}elseif(p->j>q->j){Insert_OL(C,q->i,q->j,q->e);q=q->right;}else{if(e=p->e+q->e)Insert_OL(C,p->i,p->j,e);p=p->right;q=q->right;}}r=(p)?p:q;while(r){Insert_OL(C,r->i,r->j,r->e);r=r->right;}}}-.133.- 第5章数组和广义表6．编写一个算法，将一个广义表中的元素x替换成y。例如，原广义表为((a,b),a,(d,a))，将’a’替换成’x’后为((x,b),x,(d,x))。voidfunc56(GList&GL,AtomTypex,AtomTypey){GListp;if(!GL)return;else{if(GL->tag==ATOM){if(GL->Data.data==x)GL->Data.data=y;}else//通过递归调用的方法，先替换表头中的x再替换表尾中的x{p=GL;while(p){func56(p->Data.ptr.hp,x,y);p=p->Data.ptr.tp;}}}}7．编写一个算法，判断两个广义表是否相等。intfunc57(GListGL1,GListGL2){GListp1=GL1,p2=GL2;intk,k1,k2;if(!p1||!p2){if(!p1&&!p2)k=1;elsek=0;}//其中有一个是空表的情况elseif(p1->tag==ATOM||p2->tag==ATOM)//其中有一个是原子的情况{if(p1->tag==ATOM&&p2->tag==ATOM&&p1->Data.data==p2->Data.data)k=1;elsek=0;}else//GL1、GL2均为非空广义表的情况{k1=func57(p1->Data.ptr.tp,p2->Data.ptr.tp);k2=func57(p1->Data.ptr.hp,p2->Data.ptr.hp);k=k1*k2;}return(k);}8．编写一个函数，将两个广义表合并成为一个广义表，合并是指两个广义表中的元素的合并。例如广义表((a,b),(c))与(a,(e,f))合并后的结果是((a,b),(c),a,(e,f))。voidfunc58(GList&G1,GList&G2)//函数将广义表G2合并的广义表G1的表尾中{GListp=G1;if(!p)p=G2;else{while(p->Data.ptr.tp)p=p->Data.ptr.tp;p->Data.ptr.tp=G2;}G2=NULL;-.133.- 第5章数组和广义表}5.6上机实验本单元是作为从线性结构到非线性结构的过度来安排的。数组和广义表可以看成其元素本身也是其自身结构（递归结构）的线性表。广义表本质上是一种层次结构，自顶向下识别并建立一个广义表的操作，可视为对某种树的遍历操作，其遍历的访问动作是建立一个结点。稀疏矩阵的十字链表存储结构也是图的一种存储结构。由此可见，本单元的实验具有承上启下的作用。通过上机实验使学生能深入研究数组的存储表示和实现技术，进一步熟悉广义表的存储结构的特性。实验题目1稀疏矩阵运算器【问题描述】稀疏矩阵是那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。设计一个能进行稀疏矩阵基本运算的运算器。【基本要求】以三元组顺序表表示稀疏矩阵，实现两个矩阵的相加、相减、相乘运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式显示输出。【测试数据】【实现提示】（1）首先输入矩阵的行数和列数，并判断基本操作中两个矩阵的行数和列数对于所要求的运算是否相匹配。可预先设定矩阵的最大行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制。比如，按行优先的顺序输入数组中的非零元素。（3）在用三元组顺序存储表示稀疏矩阵时，相加、相减的结果矩阵应另行生成，乘积运算的结果矩阵可用二维数组存储。参见5.3.3稀疏矩阵的顺序存储表示与实现-.133.- 第5章数组和广义表实验题目2识别广义表的“表头”或“表尾”的演示【问题描述】编写一个程序，建立广义表的存储结构，演示在此存储结构上实现的求广义表表头和表尾操作序列的结果。【基本要求】（1）设一个广义表允许分多行输入，其中可以任意地输入空格符，原子是不限长的仅由字母和数字组成的串。（2）广义表采用链式存储结构存储，试按广义表的表头和表尾分解的方法编写建立广义表存储结构的算法。（3）对已建立存储结构的广义表实施操作，并以符号形式显示结果。【测试数据】求广义表((),(e1),(abc,(e2,c,dd)))的表头和表尾。【实现提示】（1）广义表串可以利用串的定长存储或堆分配存储结构来储存。（2）输入广义表时依靠括号匹配判断结束，滤掉空格符之后存于一个串变量中。实验程序代码如下：#include"iostream.h"#defineNULL0（1）广义表结构的定义enumElemTag{ATOM,LIST};//定义结点标志域tag的类型为枚举(enum)类型ElemTagstructHString{intlength;char*ch;};typedefcharAtomType;typedefHStringAType;//定义广义表的数据域data的类型为HStringtypedefstructGLNode//定义结点的结构类型GLNode{ElemTagtag;union//定义结点信息域Data的类型为共同体类型(union){ATypedata;//定义结点的数据域data的类型为ATypestruct{GLNode*hp,*tp;}ptr;//定义表头(hp)、表尾(tp)指针域ptr的类型为无名结构体}Data;}*GList;//定义广义表类型GList（2）计算广义表深度的操作intGListDepth(GListGL)//求广义表的深度{intmax,dep;GListpp;if(!GL)return(1);//空表的深度为1if(GL->tag==ATOM)return(0);//原子的深度为0for(max=0,pp=GL;pp;pp=pp->Data.ptr.tp)//计算所有子表的最大深度max{dep=GListDepth(pp->Data.ptr.hp);//利用递归算法计算表头的深度if(dep>max)max=dep;}-.133.- 第5章数组和广义表return(max+1);//返回广义表GL的深度(max+1)}（3）求广义表长度的操作intGListLength(GListGL){inth;if(!GL)h=0;elseh=GListLength(GL->Data.ptr.tp)+1;return(h);}（4）广义表的复制操作voidCopyGList(GList&T,GListL)//用递归方法完成由广义表L复制得到广义表T的操作{intlen,i;if(!L)T=NULL;else{T=newGLNode;T->tag=L->tag;if(L->tag==ATOM){len=L->Data.data.length;T->Data.data.length=len;T->Data.data.ch=newAtomType[len+1];for(i=0;T->Data.data.ch[i]=L->Data.data.ch[i];i++);}else{CopyGList(T->Data.ptr.hp,L->Data.ptr.hp);//复制广义表L的表头到TCopyGList(T->Data.ptr.tp,L->Data.ptr.tp);//复制广义表L的表尾到T}}}（4）广义表的创建操作voidSever(AtomType*&str,AtomType*&hstr){//程序从str中逐个复制字符到htsr中，直到遇见"()"之外的第一个逗号","或str结束为止inti,j=0,k;AtomTypech;for(i=0,k=0;(ch=str[i])&&(ch!=","||k!=0);i++)//k表示"("的重数{hstr[i]=ch;if(ch=="(")k++;elseif(ch==")")k--;}-.133.- 第5章数组和广义表hstr[i]="";if(ch==",")while(str[j++]=str[++i]);//从str中删除hstrelsestr[0]="";}voidCreateGList(GList&L,AtomType*&str){intn=0,i,j;GListp;while(str[n])n++;AtomType*hstr=newAtomType[n+1];AtomType*sub=newAtomType[n+1];if(str[0]=="("&&str[1]==")"&&!str[2])L=NULL;else{L=p=newGLNode;if(str[0]!="("){L->tag=ATOM;L->Data.data.length=n;L->Data.data.ch=newAtomType[n+1];for(i=0;L->Data.data.ch[i]=str[i];i++);}else{p->tag=LIST;for(i=1,j=0;sub[j]=str[i];i++)j++;//将str[]中()内的字符序列赋值到数组sub[]中sub[j-1]="";do{Sever(sub,hstr);//取表头元素序列CreateGList(p->Data.ptr.hp,hstr);//创建p的头表if(sub[0])//创建表尾结点p{p->Data.ptr.tp=newGLNode;p=p->Data.ptr.tp;p->tag=LIST;}}while(sub[0]);p->Data.ptr.tp=NULL;//结束循环后的为表为空表}}delete[]sub;delete[]hstr;}-.133.- 第5章数组和广义表（5）广义表的遍历操作voidTraverse_GL(GListGL){GListp;if(!GL)cout<<"()";else{if(GL->tag==ATOM)cout<Data.data.ch;else{cout<<"(";p=GL;while(p){Traverse_GL(p->Data.ptr.hp);p=p->Data.ptr.tp;if(p)cout<<",";}cout<<")";}}}（6）提取广义表的表头voidHead(GListGL){GListh;cout<<"广义表:";Traverse_GL(GL);cout<tag==ATOM)cout<<"为原子或空表不能取表头n";else{cout<<"表头为:";h=GL->Data.ptr.hp;if(!h)cout<<"()";elseif(h->tag==ATOM)cout<Data.data.ch;elseTraverse_GL(h);cout<tag==ATOM)cout<<"为原子或空表不能取表尾n";else{cout<<"表尾为:";h=GL->Data.ptr.tp;Traverse_GL(h);cout<