數(shù)據(jù)結(jié)構(gòu)作業(yè)系統(tǒng)_第五章答案

1、5.21 假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組表C存放結(jié)果矩陣。要求實(shí)現(xiàn)以下函數(shù)：Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);/* 三元組表示的稀疏矩陣加法: C=A+B */稀疏矩陣的三元組順序表類型TSMatrix的定義：#define MAXSIZE 20 / 非零元個數(shù)的最大值typedef struct int i,j; / 行下標(biāo),列下標(biāo) ElemType e; / 非零元素值Triple; typedef struct Triple dataMAXSIZE+1; / 非零元三元組

2、表,data0未用 int mu,nu,tu; / 矩陣的行數(shù)、列數(shù)和非零元個數(shù)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 三元組表的一種變型是，從三元組表中去掉行下標(biāo)域得到二元組表，另設(shè)一個行起始向量，其每個分量是二元組表的一個下標(biāo)值，指示該行中第一個非零元素在二元組表中的起始位置。試編寫一個算法，由矩陣元素的下標(biāo)值i，j求矩陣元素。試討論這種方法和三元組表相比有什么優(yōu)缺點(diǎn)。要求實(shí)現(xiàn)以下函數(shù)：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 試編寫一個以三元組形式輸出用十字鏈表表示的稀疏矩陣中非零元素及其下標(biāo)的算法。要求實(shí)現(xiàn)以下函數(shù)：void OutCSM(CrossList M, void(*Out3)(int, int, int);/* 用函數(shù)Out3,依次以三元組格式輸出十字鏈表表示的矩陣 */稀疏矩陣的十字鏈表存儲表示:typedef struct OLNode int i,j; / 該非零元的行和列下標(biāo)

8、 ElemType e; / 非零元素值 OLNode *right,*down; / 該非零元所在行表和列表的后繼鏈域OLNode, *OLink;typedef struct OLink *rhead,*chead; / 行和列鏈表頭指針向量基址 int mu,nu,tu; / 稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)CrossList;void OutCSM(CrossList M, void(*Out3)(int, int, int)/* 用函數(shù)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 試按表頭、表尾的分析方法重寫求廣義表的深度的遞歸算法。要求實(shí)現(xiàn)以下函數(shù)：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 試編寫判別兩個廣義表是否相等的遞歸算法。要求實(shí)現(xiàn)以下函數(shù)：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 試編寫遞歸算法，輸出廣義表中所有原子項(xiàng)及其所在層次。要求實(shí)現(xiàn)以下函數(shù)：void OutAtom(GList A, int laye

13、r, void(*Out2)(char, int);/* 遞歸地用函數(shù)Out2輸出廣義表的原子及其所在層次,layer表示當(dāng)前層次 */廣義表類型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)/* 遞歸地用函數(shù)Out2輸出廣義表的原子及其所在層次,layer表示當(dāng)前層次

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 試設(shè)計(jì)一個算法，將數(shù)組A中的元素A0.n-1循環(huán)右移k位，并要求只用一個元素大小的附加存儲，元素移動或交換次數(shù)為O(n)。要求實(shí)現(xiàn)以下函數(shù)：void Rotate(Array1D &a, int n, int k);一維數(shù)組類型Array1D的定義：typedef ElemType Array1DMAXLEN;void Rotate(Array1D &a, int n, int k)/* an contains the elements, */* rotat