数据结构作业系统-第五章答案

5.21④假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。要求实现以下函数：StatusAddTSM(TSMatrixA,TSMatrixB,TSMatrix&C);/*三元组表示的稀疏矩阵加法:C=A+B*/稀疏矩阵的三元组顺序表类型TSMatrix的定义：#defineMAXSIZE20//非零元个数的最大值typedefstruct{inti,j;//行下标,列下标ElemTypee;//非零元素值}Triple;typedefstruct{Tripledata[MAXSIZE+1];//非零元三元组表,data[0]未用intmu,nu,tu;//矩阵的行数、列数和非零元个数}TSMatrix;StatusAddTSM(TSMatrixA,TSMatrixB,TSMatrix&C)/*三元组表示的稀疏矩阵加法:C=A+B*/{intk=1,n=1,p=1;ElemTypece;if(A.mu!=B.mu||A.nu!=B.nu)returnERROR;while(k=A.tu&&n=B.tu){if(A.data[k].i==B.data[n].i&&A.data[k].j==B.data[n].j){ce=A.data[k].e+B.data[n].e;if(ce){C.data[p].i=A.data[k].i;C.data[p].j=A.data[k].j;C.data[p].e=ce;p++;//printf(%d,,%d,ce,C.data[p-1].e);}k++;n++;}elseif(A.data[k].iB.data[n].i||A.data[k].i==B.data[n].i&&A.data[k].jB.data[n].j){C.data[p].e=A.data[k].e;C.data[p].i=A.data[k].i;C.data[p].j=A.data[k].j;k++;p++;}else{C.data[p].e=B.data[n].e;C.data[p].i=B.data[n].i;C.data[p].j=B.data[n].j;n++;p++;}}if(kA.tu)while(n=B.tu){C.data[p].e=B.data[n].e;C.data[p].i=B.data[n].i;C.data[p].j=B.data[n].j;n++;p++;printf(%dB,B.data[n].e);}elsewhile(k=A.tu){C.data[p].e=A.data[k].e;C.data[p].i=A.data[k].i;C.data[p].j=A.data[k].j;k++;p++;printf(%dA,C.data[p].e);}C.mu=A.mu;C.nu=A.nu;C.tu=p-1;returnTRUE;}5.23②三元组表的一种变型是，从三元组表中去掉行下标域得到二元组表，另设一个行起始向量，其每个分量是二元组表的一个下标值，指示该行中第一个非零元素在二元组表中的起始位置。试编写一个算法，由矩阵元素的下标值i，j求矩阵元素。试讨论这种方法和三元组表相比有什么优缺点。要求实现以下函数：StatusGetElem(T2SMatrixM,inti,intj,ElemType&e);/*求二元组矩阵的元素A[i][j]的值e*/稀疏矩阵的二元组顺序表＋行起始向量的类型T2SMatrix的定义：typedefstruct{intj;ElemTypee;}TwoTuples;typedefstruct{TwoTuplesdata[MAXSIZE];intcpot[MAXROW];//这个向量存储每一行在二元组中的起始位置intmu,nu,tu;}T2SMatrix;//二元组矩阵类型StatusGetElem(T2SMatrixM,inti,intj,ElemType&e)/*求二元组矩阵的元素A[i][j]的值e*/{intk;if(iM.mu||jM.nu||i1||j1)returnERROR;for(k=M.cpot[i];kM.cpot[i+1];k++){if(M.data[k].j==j){e=M.data[k].e;returnOK;}}e=0;returnOK;}5.26③试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。要求实现以下函数：voidOutCSM(CrossListM,void(*Out3)(int,int,int));/*用函数Out3,依次以三元组格式输出十字链表表示的矩阵*/稀疏矩阵的十字链表存储表示:typedefstructOLNode{inti,j;//该非零元的行和列下标ElemTypee;//非零元素值OLNode*right,*down;//该非零元所在行表和列表的后继链域}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;//行和列链表头指针向量基址intmu,nu,tu;//稀疏矩阵的行数、列数和非零元个数}CrossList;voidOutCSM(CrossListM,void(*Out3)(int,int,int))/*用函数Out3,依次以三元组格式输出十字链表表示的矩阵*/{intj=0;OLinkp;for(j=0;j=M.mu;j++){if(M.rhead[j])for(p=M.rhead[j];p;p=p-right)Out3(p-i,p-j,p-e);}}5.30③试按表头、表尾的分析方法重写求广义表的深度的递归算法。要求实现以下函数：intGListDepth(GListls);/*Returnthedepthoflist*/广义表类型GList的定义：typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{charatom;struct{GLNode*hp,*tp;}ptr;}un;}*GList;intGListDepth(GListls)/*Returnthedepthoflist*/{intmax=0,dep;GListp;if(ls==NULL)return1;if(ls-tag==ATOM)return0;for(p=ls;p;p=p-un.ptr.tp){dep=GListDepth(p-un.ptr.hp);if(maxdep)max=dep;}returnmax+1;}5.32④试编写判别两个广义表是否相等的递归算法。要求实现以下函数：StatusEqual(GListA,GListB);/*判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE*/广义表类型GList的定义：typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{charatom;struct{GLNode*hp,*tp;}ptr;}un;}*GList;StatusEqual(GListA,GListB)/*判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE*/{if(A==NULL&&B==NULL)returnTRUE;if(A-tag==ATOM&&B-tag==ATOM&&A-un.atom==B-un.atom)returnTRUE;if(A-tag==LIST&&B-tag==LIST)if(Equal(A-un.ptr.hp,B-un.ptr.hp)&&Equal(A-un.ptr.tp,B-un.ptr.tp))returnTRUE;returnFALSE;}5.33④试编写递归算法，输出广义表中所有原子项及其所在层次。要求实现以下函数：voidOutAtom(GListA,intlayer,void(*Out2)(char,int));/*递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次*/广义表类型GList的定义：typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{charatom;struct{GLNode*hp,*tp;}ptr;}un;}*GList;voidOutAtom(GListA,intlayer,void(*Out2)(char,int))/*递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次*/{if(A==NULL)return;if(A-tag==ATOM)Out2(A-un.atom,layer);else{OutAtom(A-un.ptr.hp,layer+1,Out2);OutAtom(A-un.ptr.tp,layer,Out2);}}5.18⑤试设计一个算法，将数组A中的元素A[0..n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。要求实现以下函数：voidRotate(Array1D&a,intn,intk);一维数组类型Array1D的定义：typedefElemTypeArray1D[MAXLEN];voidRotate(Array1D&a,intn,intk)/*a[n]containstheelements,*//*rotatethemrightcirclelybyksits*/{inti,j,l,p,temp;for(i=1;i=k;i++)if(k%i==0&&n%i==0)p=i;for(i=0;ip;i++){j=i;l=(j+k)%n;while(l!=i){if(j==i){temp=a[l];a[l]=a[j];a[j]=temp;}else{temp=a[l];a[l]=a[i];a[i]=temp;}j=l;l=(k+j)%n;}}}