while(j<=s[0]) {
if(s[i]==s[j]) {
length1=1;
for(k=1;s[i+k]==s[j+k];k++) length1++;
if(length1>=length) {
index=i;
length=length1; }
j=j+length1; }
else j++; }
i++; }
loc=index;
sub[0]=length; }
第五章
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 data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 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.data[pa].i while(A.data[pa].i==x&&B.data[pb].i==x) //行列值都相等的元素 { if(A.data[pa].j==B.data[pb].j) { ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if else if(A.data[pa].j>B.data[pb].j) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e; pa++;pc++; } }//while while(A.data[pa].i==x) //插入A中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e; pa++;pc++; } while(B.data[pb].i==x) //插入B中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc; return OK; }//TSMatrix_Add /* { int s=1,t=1,k=1; while(s if(A.data[s].i else if(A.data[s].i>B.data[t].i) {C.data[k].i=B.data[t].i; C.data[k].j=B.data[t].j; C.data[k].e=B.data[t].e; k++; t++; } else { C.data[k].i=B.data[t].i; C.data[k].j=B.data[t].j; C.data[k].e=A.data[s].e+B.data[t].e; if(C.data[k].e!=0) k++; s++; t++; } } else if(A.data[s].i {C.data[k].i=B.data[t].i; C.data[k].j=B.data[t].j; C.data[k].e=B.data[t].e; k++; t++; } C.mu=A.mu; C.nu=A.nu; C.tu=k; return 1; } 5.23② 三元组表的一种变型是，从三元组表中去掉行下标域得到二元组表，另设一个行起始向量，其每个分量是二元组表的一个下标值，指示该行中第一个非零元素在二元组表中的起始位置。试编写一个算法，由矩阵元素的下标值i，j求矩阵元素。试讨论这种方法和三元组表相比有什么优缺点。 要求实现以下函数： Status GetElem(T2SMatrix M, int i, int j, ElemType &e); /* 求二元组矩阵的元素A[i][j]的值e */ 稀疏矩阵的二元组顺序表＋行起始向量的类型T2SMatrix的定义： typedef struct{ int j; ElemType e; }TwoTuples; typedef struct{ TwoTuples data[MAXSIZE]; int cpot[MAXROW]; // 这个向量存储每一行在二元组中的起始位置 int mu,nu,tu; } T2SMatrix; // 二元组矩阵类型 Status GetElem(T2SMatrix M, int i, int j, ElemType &e) /* 求二元组矩阵的元素A[i][j]的值e */ { int t; if( i > M.mu || i < 0 || j > M.nu || j < 0 ) //i,j超出范围，0 for( t = M.cpot[i]; M.data[t].j != j&&t < M.cpot[i+1]; t++ ); if( t == M.cpot[i+1] ) e = 0; else e = M.data[t].e; return OK; } /* Status GetElem(T2SMatrix M, int i, int j, ElemType &e) { for(s=A.cpot[i];s e=A.data[s]; return OK; } return ERROR; } */ 5.26③ 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。 要求实现以下函数： void OutCSM(CrossList M); /* 以三元组格式输出十字链表表示的矩阵 */ 稀疏矩阵的十字链表存储表示: 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;i<=M.mu;i++) { if(M.rhead[i]) for(p=M.rhead[i];p;p=p->right) 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(m>n) return m; else return n; } /* { int m,n; if(ls==NULL) return 1; else if(ls->tag==0) return 0; m=GListDepth(ls->ptr.hp)+1; n=GListDepth(ls->ptr.tp); return m>n?m:n; } */ 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, int)) /* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */ { if(!A) return ; if(!A->tag) Out2(A->un.atom,layer); else { OutAtom(A->un.ptr.hp,layer+1,Out2); OutAtom(A->un.ptr.tp,layer,Out2); } }