数据结构上机作业1-5章(9)

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 …… 此处隐藏：645字，全部文档内容请下载后查看。喜欢就下载吧 ……