《数据结构作业系统_第五章答案.doc》由会员分享，可在线阅读，更多相关《数据结构作业系统_第五章答案.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构作业系统_第五章答案.精品文档.5.21 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。要求实现以下函数：Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);/* 三元组表示的稀疏矩阵加法: C=A+B */稀疏矩阵的三元组顺序表类型TSMatrix的定义：#define MAXSIZE 20 / 非零元个数的最大值typedef struct int i,j; / 行下标,列下标 ElemType e; / 非零元素值Triple;type
2、def struct Triple dataMAXSIZE+1; / 非零元三元组表,data0未用 int mu,nu,tu; / 矩阵的行数、列数和非零元个数TSMatrix;Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)/* 三元组表示的稀疏矩阵加法: C=A+B */ int k=1,n=1,p=1; ElemType ce; if(A.mu!=B.mu|A.nu!=B.nu)return ERROR; while(k=A.tu&n=B.tu) if(A.datak.i=B.datan.i&A.datak.j=B.datan.j) ce
3、=A.datak.e+B.datan.e; if(ce) C.datap.i=A.datak.i; C.datap.j=A.datak.j; C.datap.e=ce; p+; /printf(%d,%d ,ce,C.datap-1.e); k+;n+; else if(A.datak.iB.datan.i|A.datak.i=B.datan.i&A.datak.jA.tu) while(n=B.tu) C.datap.e=B.datan.e; C.datap.i=B.datan.i; C.datap.j=B.datan.j; n+;p+; printf(%d B ,B.datan.e); e
4、lse while(kM.mu|jM.nu|i1|j1)return ERROR; for(k=M.cpoti;kM.cpoti+1;k+) if(M.datak.j=j) e=M.datak.e; return OK; e=0; return OK;5.26 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。要求实现以下函数：void OutCSM(CrossList M, void(*Out3)(int, int, int);/* 用函数Out3,依次以三元组格式输出十字链表表示的矩阵 */稀疏矩阵的十字链表存储表示:typedef struct OLNode i
5、nt i,j; / 该非零元的行和列下标 ElemType e; / 非零元素值 OLNode *right,*down; / 该非零元所在行表和列表的后继链域OLNode, *OLink;typedef struct OLink *rhead,*chead; / 行和列链表头指针向量基址 int mu,nu,tu; / 稀疏矩阵的行数、列数和非零元个数CrossList;void OutCSM(CrossList M, void(*Out3)(int, int, int)/* 用函数Out3,依次以三元组格式输出十字链表表示的矩阵 */ int j=0; OLink p; for(j=0;j
6、right) Out3(p-i,p-j,p-e); 5.30 试按表头、表尾的分析方法重写求广义表的深度的递归算法。要求实现以下函数：int GListDepth(GList ls);/* Return the depth of list */广义表类型GList的定义：typedef enum ATOM,LIST ElemTag;typedef struct GLNode ElemTag tag; union char atom; struct GLNode *hp, *tp; ptr; un; *GList;int GListDepth(GList ls)/* Return the dep
7、th of list */ int max=0,dep; GList p; if(ls=NULL)return 1; if(ls-tag=ATOM)return 0; for(p=ls;p;p=p-un.ptr.tp) dep=GListDepth(p-un.ptr.hp); if(maxtag=ATOM&B-tag=ATOM&A-un.atom=B-un.atom) return TRUE; 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) return TRU
8、E; return FALSE;5.33 试编写递归算法，输出广义表中所有原子项及其所在层次。要求实现以下函数：void OutAtom(GList A, int layer, void(*Out2)(char, int);/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */广义表类型GList的定义：typedef enum ATOM,LIST ElemTag;typedef struct GLNode ElemTag tag; union char atom; struct GLNode *hp, *tp; ptr; un; *GList;void OutA
9、tom(GList A, int layer, 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中的元素A0.n-1循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。要求实现以下函数：void Rota
10、te(Array1D &a, int n, int k);一维数组类型Array1D的定义：typedef ElemType Array1DMAXLEN;void Rotate(Array1D &a, int n, int k)/* an contains the elements, */* rotate them right circlely by k sits */ int i,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=al;al=aj;aj=temp; else temp=al; al=ai; ai=temp; j=l; l=(k+j)%n;