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

1、5.21 假設(shè)稀疏矩陣A和B均以三元組表作為存儲(chǔ)結(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 / 非零元個(gè)數(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ù)和非零元個(gè)數(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è)一個(gè)行起始向量，其每個(gè)分量是二元組表的一個(gè)下標(biāo)值，指示該行中第一個(gè)非零元素在二元組表中的起始位置。試編寫一個(gè)算法，由矩陣元素的下標(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; / 這個(gè)向量存儲(chǔ)每一行在二元組中的起始位置 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 試編寫一個(gè)以三元組形式輸出用十字鏈表表示的稀疏矩陣中非零元素及其下標(biāo)的算法。要求實(shí)現(xiàn)以下函數(shù)：void OutCSM(CrossList M, void(*Out3)(int, int, int);/* 用函數(shù)Out3,依次以三元組格式輸出十字鏈表表示的矩陣 */稀疏矩陣的十字鏈表存儲(chǔ)表示: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ù)和非零元個(gè)數(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 試編寫判別兩個(gè)廣義表是否相等的遞歸算法。要求實(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ì)一個(gè)算法，將數(shù)組A中的元素A0.n-1循環(huán)右移k位，并要求只用一個(gè)元素大小的附加存儲(chǔ)，元素移動(dòng)或交換次數(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