《数据结构题集》参考答案5 数组和广义表.doc

第五章 数组和广义表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,b=n-1,m=n; int t,c=k/n,r,g,d,e; r=k-c*n; e=r; while(r!=0) g=r; d=m/r; r=m-d*r; m=g; for(;bn-1-m;-b) ElemType q=ab; i=b; t=b+e-n; if(t0)t=b+e; while(i!=t) if(ie) ai=ai+n-e; i=i+n-e; else ai=ai-e; i-=e; /while at=q; /for5.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 */ if( A.mu != B.mu | A.nu != B.nu ) return ERROR; C.mu=A.mu;C.nu=A.nu;C.tu=0; int pa=1; int pb=1; int pc=1; ElemType ce; int x; for(x=1;x=A.mu;x+) /对矩阵的每一行进行加法 while(A.datapa.ix) pa+; while(B.datapb.iB.datapb.j) C.datapc.i=x; C.datapc.j=B.datapb.j; C.datapc.e=B.datapb.e; pb+;pc+; else C.datapc.i=x; C.datapc.j=A.datapa.j; C.datapc.e=A.datapa.e; pa+;pc+; /while while(A.datapa.i=x) /插入A中剩余的元素(第x行) C.datapc.i=x; C.datapc.j=A.datapa.j; C.datapc.e=A.datapa.e; pa+;pc+; while(B.datapb.i=x) /插入B中剩余的元素(第x行) C.datapc.i=x; C.datapc.j=B.datapb.j; C.datapc.e=B.datapb.e; pb+;pc+; /for C.tu=pc; return OK;/TSMatrix_Add5.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 i; OLink p; for(i=0;iright) Out3(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 m,n; if(ls=NULL) return 1; else if(ls-tag=0) return 0; m=GListDepth(ls-un.ptr.hp)+1; n=GListDepth(ls-un.ptr.tp); if(mn) return m; else return n;5.32 试编写判别两个广义表是否相等的递归算法。要求实现以下函数：Status Equal(GList A, GList B);/* 判断广义表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-tag!=B-tag) return FALSE; else if(A-tag=ATOM) if(A-un.atom!=B-un.atom) return FALSE; else return TRUE; else if(Equal(A-un.ptr.hp,B-un.ptr.hp)&Equal(A-un.ptr.tp,B-un.ptr.tp) return TRUE; else return FALSE; 5.33 试编写递归算法，输出广义表中所有原子项及其所在层次。广义表类型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, in