第五章数组和广义表作业参考答案.pptVIP

作业 三元组顺序表的一种变型是，从三元组顺序表中去掉行下标域得到二元组顺序表，另设一个行起始向量，其每个分量是二元组顺序表的一个下标值，指示该行中第一个非零元素在二元组顺序表中的起始位置。试编写一个算法，由矩阵元素的下标值i，j求矩阵元素。 #define MAXSIZE 12500 #define MAXMN 500 typedef struct { int j; //该非零元的列下标 ElemType e; // 该非零元的值 } two-tuples; // 二元组类型 typedef struct { two-tuples data[MAXSIZE + 1]; //非零元三元组表 int rpos[MAXMN + 1]; //各行第一个非零元的位置表 int mu, nu, tu; } RLSMatrix; ElemType value (RLSMatrix M, int r, int c) { p = M.rpos[r]; if(rM.mu) q=M.rpos[r+1]; else q=M.tu+1; while ( pq M.data[p].j c) p++; if ( pq M.data[p].j= =c) return M.data[p].e; else return 0; } // value P105 矩阵相加（十字链表） typedef struct OLNode { int i, j; elemtype e; struct OLNode *down, *right; }OLNode; *OLink; Typedef struct{ OLink *rhead, *chead; int mu, nu, tu; } CrossList; Status Add( Crosslist A, Crosslist B ){ for(j=1; jA.nu; j++) hl[j]=A.chead[j]; for( i=1; i=A.mu; i++) { pa=A.rhead[i]; pb=B.rhead[i]; pre=NULL; while(pb) { if( pa==NULL || pa-j pb-j) //插入一个新结点 { p=(OLNode *)malloc(sizeof(OLNode)); p-i=pb-i; p-j=pb-j; p-e=pb-e; if(pre==NULL) A.rhead[p-i]=p; else pre-right=p; p-right=pa; pre=p; if(!A.chead[p-j] || A.chead[p-j]-i p-i) { p-down=A.chead[p-j]; A.chead[p-j]=p;} else { while(hl[p-j]-down-i p-i) hl[p-j]=hl[p-j]-down; p-down=hl[p-j]-down; hl[p-j]-down=p; } hl[p-j]=p; pb=pb-right; }//if1 else if (pa!=NULL pa-j pb-j ) { pre=pa; pa=pa-right;} else // pa-j==pb-j { pa-e+=pb-e; if(!pa-e) //删除结点pa { if(pre==NULL) A.rhead[pa-i]=pa-right; else pre-right=pa-right; p=pa; pa=pa-right; if(A.chead[p-j]==p) A.chead[p-j]=hl[p-j]=p-down; else { while(hl[p-j] -down-i p-i) hl[p-j]=