广州大学松田学院6数据结构复习题-广义表-参考答案

1、以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000, 每个元素占4个字节，下标变量A[4][3]的地址是____。

A.1069B.1092C.1023D.1046正确答案：B2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

A.1040B.1026C.1046D.1038正确答案：A3、设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

A.1048B.1024C.1096D.1060正确答案：A4、设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。

如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

A.1036B.1144C.1014D.10565、设有一个10行10列的矩阵A，采用行序优先存储方式。

如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

A.4B.1C.2D.3正确答案：D6、不能够对数据元素进行随机访问的物理结构是_________。

A.三元组顺序表B.对称矩阵的压缩存储C.三对角矩阵的压缩存储D.数组的顺序存储正确答案：A7、对特殊矩阵采用压缩存储的目的主要是_________。

A.表达变得简单B.去掉矩阵中的多余元素C.对矩阵元素的存储变得简单D.减少不必要的存储空间正确答案：D8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

A.nB.n(n+1)/2C.n2D.n(n+1)9、设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3] 保存在SA[k]中，这里k等于_________。

第4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴ 数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。

【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。

除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。

【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。

⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

【解答】三元组顺序表，十字链表A 数组是一种线性结构B 数组是一种定长的线性结构C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操【解答】C【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。

⑷ 对特殊矩阵采用压缩存储的目的主要是为了（）A 表达变得简单B 对矩阵元素的存取变得简单C 去掉矩阵中的多余元素D 减少不必要的存储空间【解答】D【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。

⑸ 下面（）不属于特殊矩阵。

A 对角矩阵B 三角矩阵C 稀疏矩阵D 对称矩阵【解答】C⑹ 若广义表A满足Head(A)=Tail(A)，则A为（）A ( )B (( ))C (( ),( )) D(( ),( ),( ))【解答】BA 广义表是一种多层次的结构B 广义表是一种非线性结构C 广义表是一种共享结构D 广义表是一种递归【解答】B【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。

1、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。

A) Head(Head(Tail(Tail(L))))B) Tail(Head(Head(Tail(L))))C) Head(Tail(Head(Tail(L))))D)Head(Tail(Head(Tail(Tail(L)))))2、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D3、与无向图相关的术语有（ C ）。

A）强连通图 B）入度C）路径 D）弧4、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。

A）p->next=p->next->next B）p=p->nextC）p=p->nexe->next D）p->next=p5、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;6、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

A）一个数量级别B）一个平均值C）一个最大值 D）一个均方值7、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树8、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的9、下列各种数据结构中属于线性结构的有（ A ）。

A）栈 B) 二叉树C) 广义表 D) 图10、数据结构研究的内容是（ D ）。

2数据结构复习题（线性表）一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（×）（1）线性表的链式存储结构优于顺序存储。

（×）（2）链表的每个结点都恰好包含一个指针域。

（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

（√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。

（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

二．填空题（1）顺序表中逻辑上相邻的元素在物理位置上必须相连。

（2）线性表中结点的集合是有限的，结点间的关系是一对一关系。

（3）顺序表相对于链表的优点是：节省存储和随机存取。

（4）链表相对于顺序表的优点是：插入、删除方便。

（5）采用顺序存储结构的线性表叫顺序表。

（6）（7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度（8）在双链表中要删除已知结点*P（9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。

（10）单链表中需知道头指针才能遍历整个链表。

（11）性表中第一个结点没有直接前趋，称为开始结点。

（12）在一个长度为n的顺序表中删除第i个元素，要移动n-i 个元素。

（13）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n- i +1 个元素。

（14）在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。

第五章数组和广义表答案部分答案解释如下。

1. 错误。

对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。

4. 错误。

数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。

因此，可以说数祖是元素值和下标构成的偶对的有穷集合。

5. 错误。

数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。

6. 错误。

稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。

8. 错误。

广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。

9. 错误。

广义表的表头就是广义表的第一个元素。

只有非空广义表才能取表头。

10. 错误。

广义表中元素可以是原子，也可以是表（包括空表和非空表）。

11. 错误。

广义表的表尾，指去掉表头元素后，剩余元素所组成的表。

三、填空题1. 顺序存储结构2.（1）9572（2）12283.（1）9174（2）87884. 11005. 1164 公式：LOC(a ijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l为每个元素所占单元数)6. 2327. 13408. 11969. 第1行第3列10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1<=i,j<=n)12. (1)n(n+1)/2 (2)i(i+1)/2 (或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1<=i,j<=n)13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1<=i,j<=n)14. 33 (k=i(i-1)/2+j) (1<=i,j<=n)15. 非零元很少(t<<m*n)且分布没有规律 16. 节省存储空间。

17. 上三角矩阵中，主对角线上第r(1≤r≤n) 行有n-r+1个元素，a ij所在行的元素数是j-i+1。

1．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ ）A ．数组的元素处在行和列两个关系中B ．数组的元素必须从左到右顺序排列C ．数组的元素之间存在次序关系D ．数组是多维结构，内存是一维结构 2．从广义表LS ＝（(p, q), r, s ）中分解出原子q 的运算是（ ） A ．tail (head (LS))B ．head (tail (head (LS)))C ．head (tail (LS))D ．tail (tail (head (LS)))3．二维数组A ［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A ［9］［7］的地址为( )A. 429B. 432C. 435D. 4384．二维数组A ［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A ［0］［0］的存储地址为300，则A ［10］［10］的地址为（ ）A.700B.1120C.1180D.11405．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（ ）A ．R[3][3][3]B ．R[3][3][4]C ．R[4][3][5]D ．R[4][3][4]6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ ）A ．1207B ．1209C ．1211D ．12137．对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )A. (e,f)B. ((e,f))C. (f)D. ( )8．设有二维数组A ［n ］［n ］表示如下：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡ 653421， 则A ［i ］［i ］（0≤i ≤n-1）的值为（ ）A ．i*(i-1)/2B.i*(i+1)/2C.(i+2)*(i+1)/2D.i 2/2 9．对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（ ）A ．dB ．eC ．(e)D ．(e,f )10．假设按行优先顺序将一个20阶的三对角矩阵A 压缩存储在一维数组Q 中，其中Q[0]存放矩阵的第1个元素a 1,1，那么矩阵元素a 3,4在Q 中的存储位置k=_______。

第4章（数组和广义表）作业参考答案一、单项选择题1.将一个A[1..100，1..100]的三对角矩阵，按行优先压缩存储到一维数组B[1‥298]中，A 中元素A[66][65]在B数组中的位置K为（C ）。

A. 198B. 197C. 195D. 1962.广义表（a,(b,c),d,e）的表头为（ A ）。

A. aB. a,(b,c)C. (a,(b,c))D. (a)3.在三对角矩阵中，非零元素的行标i和列标j的关系是（ A ）。

A. |i-j|≤1B. i>jC. i==jD. i<j4.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ D ）。

A. cB. b，cC.（b，c）D.（（b，c））5.设二维数组A[1..m,1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ D ）。

A. j*m+i-1B. (i-1)*n+j-1C. i*(j-1)D. (i-1)*n+j6.广义表(( ),( ),( ))的深度为（ C ）。

A. 0B. 1C. 2D. 37.假设以行序为主序存储二维数组A[0..99,0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC（A[4][4]）=（ C ）。

A. 1020B. 1010C. 818D. 8088.已知广义表A=((a,b),(c,d))，则head(A)等于（ A ）。

A. (a,b)B. ((a,b))C. a,bD. a9.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)则其转置矩阵的三元组表中第3个三元组为（ C ）。

A. (2，3，-1)B. (3，1，5)C. (2，1，3)D. (3，2，-1)10.广义表（(b,c),d,e）的表尾为（ C ）。

习题五数组和广义表一、单项选择题1．常对数组进行的两种基本操作是（）A.建立与删除B. 索引与修改C. 查找与修改D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*kD.Loc[i,j]=[(n+1)*i+j]*k3．稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素B. 三元祖（i,j, aij）C. aijD. i,j4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175B. 1180C. 1205D. 12105. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].nextB. j=j+1C. j=j->nextD. j=r[j]-> next7. 对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算 B．便于输入和输出C．节省存储空间 D．降低运算的时间复杂度8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))9. 广义表（（a,b,c,d））的表头是（），表尾是（）。

第五章数组和广义表5.18void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间{for(i=1;i<=k;i++)if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数pfor(i=0;i{j=i;l=(i+n-k)%n;temp=A[i];while(l!=i){A[j]=A[l];j=l;l=(j+n-k)%n;}// 循环右移一步A[j]=temp;}//for}//RSh分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:n=15,k=6,则p=3.第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的.5.19void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点{for(i=0;i{for(min=A[i][0],j=0;jif(A[i][j]for(j=0;jif(A[i][j]==min) //判断这个(些)最小值是否鞍点{for(flag=1,k=0;kif(minif(flag)printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]);}}//for}//Get_Saddle5.20int exps[MAXSIZE]; //exps数组用于存储某一项的各变元的指数int maxm,n; //maxm指示变元总数,n指示一个变元的最高指数void Print_Poly_Descend(int *a,int m)//按降幂顺序输出m元多项式的项，各项的系数已经按照题目要求存储于m维数组中，数组的头指针为a{maxm=m;for(i=m*n;i>=0;i--) //按降幂次序,可能出现的最高项次数为mnGet_All(a,m,i,0); //确定并输出所有次数为i的项}//Print_Poly_Descendvoid Get_All(int *a,int m,int i,int seq)//递归求出所有和为i的m个自然数{if(seq==maxm) Print_Nomial(a,exps); //已经求完时,输出该项else{min=i-(m-1)*n; //当前数不能小于minif(min<0) min=0;max=nfor(j=min;j<=max;j++){exps[seq]=j; //依次取符合条件的数Get_All(a,m-1,i-j,seq+1); //取下一个数}}//elseexps[seq]=0; //返回}//Get_Allvoid Print_Nomial(int *a,int exps[ ])//输出一个项,项的各变元的指数已经存储在数组exps中{pos=0;for(i=0;i{pos*=n;pos+=exps[i];}coef=*(a+pos); //取得该系数coefif(!coef) return; //该项为0时无需输出else if(coef>0) printf("+"); //系数为正时打印加号else if(coef<0) printf("-"); //系数为负时打印减号if(abs(coef)!=1) printf("%d",abs(coef)); //当系数的绝对值不为1时打印系数for(i=0;iif(exps[i]) //打印各变元及其系数{printf("x");printf("%d",i);printf("E");if(exps[i]>1) printf("%d",exp[i]); //系数为1时无需打印}}//Print_Nomial分析:本算法的关键在于如何按照降幂顺序输出各项.这里采用了一个递归函数来找到所有满足和为i的m个自然数作为各变元的指数.只要先取第一个数为j,然后再找到所有满足和为i-j的m-1个自然数就行了.要注意j的取值范围必须使剩余m-1个自然数能够找到,所以不能小于i-(m-1)*maxn,也不能大于i.只要找到了一组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置,并且在系数不为0时输出对应的项.5.21void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法{C.mu=A.mu;C.nu=A.nu;C.tu=0;pa=1;pb=1;pc=1;for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法{while(A.data[pa].iwhile(B.data[pb].iwhile(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素{if(A.data[pa].j==B.data[pb].j){ce=A.data[pa].e+B.data[pb].e;if(ce) //和不为0{C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=ce;pa++;pb++;pc++;}}//ifelse if(A.data[pa].j>B.data[pb].j){C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;}else{C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].epa++;pc++;}}//whilewhile(A.data[pa]==x) //插入A中剩余的元素(第x行){C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].epa++;pc++;}while(B.data[pb]==x) //插入B中剩余的元素(第x行){C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;}}//forC.tu=pc;}//TSMatrix_Add5.22void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上{for(i=1;i<=A.tu;i++)A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置pa=MAXSIZE-A.tu+1;pb=1;pc=1;for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法{while(A.data[pa].iwhile(B.data[pb].iwhile(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素{if(A.data[pa].j==B.data[pb].j){ne=A.data[pa].e+B.data[pb].e;if(ne) //和不为0{A.data[pc].i=x;A.data[pc].j=A.data[pa].j;A.data[pc].e=ne;pa++;pb++;pc++;}}//ifelse if(A.data[pa].j>B.data[pb].j){A.data[pc].i=x;A.data[pc].j=B.data[pb].j;A.data[pc].e=B.data[pb].e;pb++;pc++;}else{A.data[pc].i=x;A.data[pc].j=A.data[pa].j;A.data[pc].e=A.data[pa].epa++;pc++;}}//whilewhile(A.data[pa]==x) //插入A中剩余的元素(第x行){A.data[pc].i=x;A.data[pc].j=A.data[pa].j;A.data[pc].e=A.data[pa].epa++;pc++;}while(B.data[pb]==x) //插入B中剩余的元素(第x行){A.data[pc].i=x;A.data[pc].j=B.data[pb].j;A.data[pc].e=B.data[pb].e;pb++;pc++;}}//forA.tu=pc;for(i=A.tu;i}//TSMatrix_Addto5.23typedef struct{int j;int e;} DSElem;typedef struct{DSElem data[MAXSIZE];int cpot[MAXROW];//这个向量存储每一行在二元组中的起始位置int mu,nu,tu;} DSMatrix; //二元组矩阵类型Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)//求二元组矩阵的元素A[i][j]的值e {for(s=A.cpot[i];sif(s{e=A.data[s];return OK;}return ERROR;}//DSMatrix_Locate5.24typedef struct{int seq; //该元素在以行为主序排列时的序号int e;} SElem;typedef struct{SElem data[MAXSIZE];int mu,nu,tu;} SMatrix; //单下标二元组矩阵类型Status SMatrix_Locate(SMatrix A,int i,int j,int &e)//求单下标二元组矩阵的元素A[i][j]的值e {s=i*A.nu+j+1;p=1;while(A.data[p].seqif(A.data[p].seq==s) //找到了元素A[i][j]{e=A.data[p].e;return OK;}return ERROR;}//SMatrix_Locate5.25typedef enum{0,1} bool;typedef struct{int mu,nu;int elem[MAXSIZE];bool map[mu][nu];} BMMatrix; //用位图表示的矩阵类型void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)//位图矩阵的加法{C.mu=A.mu;C.nu=A.nu;pa=1;pb=1;pc=1;for(i=0;ifor(j=0;j{if(A.map[i][j]&&B.map[i][j]&&(A.elem[pa]+B.elem[pb]))//结果不为0{C.elem[pc]=A.elem[pa]+B.elem[pb];C.map[i][j]=1;pa++;pb++;pc++;}else if(A.map[i][j]&&!B.map[i][j]){C.elem[pc]=A.elem[pa];C.map[i][j]=1;pa++;pc++;}else if(!A.map[i][j]&&B.map[i][j]){C.elem[pc]=B.elem[pb];C.map[i][j]=1;pb++;pc++;}}}//BMMatrix_Add5.26void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵{for(i=0;i{if(A.rhead[i])for(p=A.rhead[i];p;p=p->right) //逐次遍历每一个行链表printf("%d %d %d\n",i,p->j,p->e;}}//Print_OLMatrix5.27void OLMatrix_Add(OLMatrix &A,OLMatrix B)//把十字链表表示的矩阵B加到A上{for(j=1;j<=A.nu;j++) cp[j]=A.chead[j]; //向量cp存储每一列当前最后一个元素的指针for(i=1;i<=A.mu;i++){pa=A.rhead[i];pb=B.rhead[i];pre=NULL;while(pb){if(pa==NULL||pa->j>pb->j) //新插入一个结点{p=(OLNode*)malloc(sizeof(OLNode));if(!pre) A.rhead[i]=p;else pre->right=p;p->right=pa;pre=p;p->i=i;p->j=pb->j;p->e=pb->e; //插入行链表中if(!A.chead[p->j]){A.chead[p->j]=p;p->down=NULL;}else{while(cp[p->j]->down) cp[p->j]=cp[p->j]->down;p->down=cp[p->j]->down;cp[p->j]->down=p;}cp[p->j]=p; //插入列链表中}//ifelse if(pa->jj){pre=pa;pa=pa->right;} //pa右移一步else if(pa->e+pb->e){pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;} //直接相加else{if(!pre) A.rhead[i]=pa->right;else pre->right=pa->right;p=pa;pa=pa->right; //从行链表中删除if(A.chead[p->j]==p)A.chead[p->j]=cp[p->j]=p->down;else cp[p->j]->down=p->down; //从列链表中删除free (p);}//else}//while}//for}//OLMatrix_Add分析:本题的具体思想在课本中有详细的解释说明.5.28void MPList_PianDao(MPList &L)//对广义表存储结构的多元多项式求第一变元的偏导{for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp){if(p->tag) Mul(p->hp,p->exp);else p->coef*=p->exp; //把指数乘在本结点或其下属结点上p->exp--;}pre->tp=NULL;if(p) free (p); //删除可能存在的常数项}//MPList_PianDaovoid Mul(MPList &L,int x)//递归算法,对多元多项式L乘以x{for(p=L;p;p=p->tp){if(!p->tag) p->coef*=x;else Mul(p->hp,x);}}//Mul5.29void MPList_Add(MPList A,MPList B,MPList &C)//广义表存储结构的多项式相加的递归算法{C=(MPLNode*)malloc(sizeof(MPLNode)); if(!A->tag&&!B->tag) //原子项,可直接相加{C->coef=A->coef+B->coef;if(!C->coef){free(C);C=NULL;}}//ifelse if(A->tag&&B->tag) //两个多项式相加{p=A;q=B;pre=NULL;while(p&&q){if(p->exp==q->exp){C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp;MPList_Add(A->hp,B->hp,C->hp);pre->tp=C;pre=C;p=p->tp;q=q->tp;}else if(p->exp>q->exp){C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp;C->hp=A->hp;pre->tp=C;pre=C;p=p->tp;}else{C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=q->exp;C->hp=B->hp;pre->tp=C;pre=C;q=q->tp;}}//whilewhile(p){C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp;C->hp=p->hp;pre->tp=C;pre=C;p=p->tp;}while(q){C=(MPLNode*)malloc(sizeof(MPLNode));C->exp=q->exp;C->hp=q->hp;pre->tp=C;pre=C;q=q->tp;} //将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题}//else ifelse if(A->tag&&!B->tag) //多项式和常数项相加{x=B->coef;for(p=A;p->tp->tp;p=p->tp);if(p->tp->exp==0) p->tp->coef+=x; //当多项式中含有常数项时,加上常数项if(!p->tp->coef){free(p->tp);p->tp=NULL;}else{q=(MPLNode*)malloc(sizeof(MPLNode));q->coef=x;q->exp=0;q->tag=0;q->tp=NULL;p->tp=q;} //否则新建常数项,下同}//else ifelse{x=A->coef;for(p=B;p->tp->tp;p=p->tp);if(p->tp->exp==0) p->tp->coef+=x;if(!p->tp->coef){free(p->tp);p->tp=NULL;}else{q=(MPLNode*)malloc(sizeof(MPLNode));q->coef=x;q->exp=0;q->tag=0;q->tp=NULL;p->tp=q;}}//else}//MPList_Add5.30int GList_Getdeph(GList L)//求广义表深度的递归算法{if(!L->tag) return 0; //原子深度为0else if(!L) return 1; //空表深度为1m=GList_Getdeph(L->ptr.hp)+1;n=GList_Getdeph(L->ptr.tp);return m>n?m:n;}//GList_Getdeph5.31void GList_Copy(GList A,GList &B)//复制广义表的递归算法{if(!A->tag) //当结点为原子时,直接复制{B->tag=0;B->atom=A->atom;}else //当结点为子表时{B->tag=1;if(A->ptr.hp){B->ptr.hp=malloc(sizeof(GLNode));GList_Copy(A->ptr.hp,B->ptr.hp);} //复制表头if(A->ptr.tp){B->ptr.tp=malloc(sizeof(GLNode));GList_Copy(A->ptr.tp,B->ptr.tp);} //复制表尾}//else}//GList_Copy5.32int GList_Equal(GList A,GList B)//判断广义表A和B是否相等,是则返回1,否则返回0 { //广义表相等可分三种情况:if(!A&&!B) return 1; //空表是相等的if(!A->tag&&!B->tag&&A->atom==B->atom) return 1;//原子的值相等if(A->tag&&B->tag)if(GList_Equal(A->ptr.hp,B->ptr.hp)&&GList_Equal(A->ptr.tp,B->ptr.tp))return 1; //表头表尾都相等return 0;}//GList_Equal5.33void GList_PrintElem(GList A,int layer)//递归输出广义表的原子及其所在层次,layer表示当前层次{if(!A) return;if(!A->tag) printf("%d %d\n",A->atom,layer);else{GList_PrintElem(A->ptr.hp,layer+1);GList_PrintElem(A->ptr.tp,layer); //注意尾表与原表是同一层次}}//GList_PrintElem5.34void GList_Reverse(GList A)//递归逆转广义表A{GLNode *ptr[MAX_SIZE];if(A->tag&&A->ptr.tp) //当A不为原子且表尾非空时才需逆转{for(i=0,p=A;p;p=p->ptr.tp,i++){if(p->ptr.hp) GList_Reverse(p->ptr.hp); //逆转各子表ptr[i]=p->ptr.hp;}for(p=A;p;p=p->ptr.tp) //重新按逆序排列各子表的顺序p->ptr.hp=ptr[--i];}}//GList_Reverse5.35Status Create_GList(GList &L)//根据输入创建广义表L,并返回指针{scanf("%c",&ch);if(ch==' '){L=NULL;scanf("%c",&ch);if(ch!=')') return ERROR;return OK;}L=(GList)malloc(sizeof(GLNode));L->tag=1;if(isalphabet(ch)) //输入是字母{p=(GList)malloc(sizeof(GLNode)); //建原子型表头p->tag=0;p->atom=ch;L->ptr.hp=p;}else if(ch=='(') Create_GList(L->ptr.hp); //建子表型表头else return ERROR;scanf ("%c",&ch);if(ch==')') L->ptr.tp=NULL;else if(ch==',') Create_GList(L->ptr.tp); //建表尾else return ERROR;return OK;}//Create_GList分析:本题思路见书后解答.5.36void GList_PrintList(GList A)//按标准形式输出广义表{if(!A) printf("()"); //空表else if(!A->tag) printf("%d",A->atom);//原子else{printf("(");for(p=A;p;p=p->ptr.tp){GList_PrintList(p->ptr.hp);if(p->ptr.tp) printf(","); //只有当表尾非空时才需要打印逗号}printf(")");}//else}//GList_PrintList5.37void GList_DelElem(GList &A,int x)//从广义表A中删除所有值为x的原子{if(A&&A->ptr.hp){if(A->ptr.hp->tag) GList_DelElem(A->ptr.hp,x);else if(!A->ptr.hp->tag&&A->ptr.hp->atom==x){q=A;A=A->ptr.tp; //删去元素值为x的表头free(q);GList_DelElem(A,x);}}if(A&&A->ptr.tp) GList_DelElem(A->ptr.tp,x);}//GList_DelElem5.39void GList_PrintElem_LOrder(GList A)//按层序输出广义表A中的所有元素{InitQueue(Q);for(p=L;p;p=p->ptr.tp) EnQueue(Q,p);while(!QueueEmpty(Q)){DeQueue(Q,r);if(!r->tag) printf("%d",r->atom);elsefor(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r);}//while}//GList_PrintElem_LOrder分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.。