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

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; typedef 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=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); else 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 int 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;jright) 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 depth 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 TRUE; 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 OutAtom(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 Rotate(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