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

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; typedef struct Triple dataMAXSIZE+1; / 非零元三元组

2、表,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+

3、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.i<B.datan.i|A.datak.i=B.datan.i&&A.datak.j<B.datan.j) C.datap.e=A.datak.e; C.datap.i=A.datak.i; C.datap.j=A.datak.j; k+;p+; else C.datap.e=B.

4、datan.e; C.datap.i=B.datan.i; C.datap.j=B.datan.j; n+; p+; if(k>A.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(k<=A.tu) C.datap.e=A.datak.e; C.datap.i=A.datak.i; C.datap.j=A.datak.j; k+;p+; printf(&q

5、uot;%d A ",C.datap.e); C.mu=A.mu; C.nu=A.nu; C.tu=p-1; return TRUE; 5.23 三元组表的一种变型是，从三元组表中去掉行下标域得到二元组表，另设一个行起始向量，其每个分量是二元组表的一个下标值，指示该行中第一个非零元素在二元组表中的起始位置。试编写一个算法，由矩阵元素的下标值i，j求矩阵元素。试讨论这种方法和三元组表相比有什么优缺点。要求实现以下函数：Status GetElem(T2SMatrix M, int i, int j, ElemType &e);/* 求二元组矩阵的元素Aij的值e */稀疏矩阵的

6、二元组顺序表行起始向量的类型T2SMatrix的定义：typedef struct int j; ElemType e;TwoTuples;typedef struct TwoTuples dataMAXSIZE; int cpotMAXROW; / 这个向量存储每一行在二元组中的起始位置 int mu,nu,tu; T2SMatrix; / 二元组矩阵类型Status GetElem(T2SMatrix M, int i, int j, ElemType &e)/* 求二元组矩阵的元素Aij的值e */ int k; if(i>M.mu|j>M.nu|i<1|j&l

7、t;1)return ERROR; for(k=M.cpoti;k<M.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; / 该非零元的行和列下标

8、 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<=M.mu;j+) if(M.r

9、headj) for(p=M.rheadj;p;p=p->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; *GLi

10、st;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(max<dep) max=dep; return max+1;5.32 试编写判别两个广义表是否相等的递归算法。要求实现以下函数：Status Equal(GList A, GList B);/*

11、判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */广义表类型GList的定义：typedef enum ATOM,LIST ElemTag;typedef struct GLNode ElemTag tag; union char atom; struct GLNode *hp, *tp; ptr; un; *GList;Status Equal(GList A, GList B)/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */ if(A=NULL&&B=NULL)return TRUE; if(A->tag=ATOM&

12、&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 laye

13、r, 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表示当前层次

14、*/ 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, */* rotat