[文学]5第5章 数组和广义表.ppt

#define MAXSIZE 1000 /*非零元素的个数最多为1000*/ #define MAXROW 1000 /*矩阵最大行数为1000*/ typedef struct {int row, col; /*该非零元素的行下标和列下标*/ ElementType e； /*该非零元素的值*/ }Triple; typedef struct { Triple data[MAXSIZE+1]; /* 非零元素的三元组表，data[0]未用*/ int first[MAXROW+1]; /*三元组表中各行第一个非零元素所在的位置。*/ int m, n, len; /*矩阵的行数、列数和非零元素的个数*/ }TriSparMatrix； 为方便实现，将三元组表的类型说明修改如下： 具体算法如下： int MulSMatrix(TriSparMatrix M, TriSparMatrix N, TriSparMatrix *Q) {/*采用改进的三元组表表示法，求矩阵乘积Q＝M×N*/ int arow , brow , p; int ctemp[MAXSIZE]; if(M.n!=N.m) return FALSE; /*返回FALSE表示求矩阵乘积失败*/ Q-m=M.m; Q-n=N.n; Q-len=0; if(M.len*N.len!=0) {for(arow=1; arow=M.m; arow++) /*逐行处理M*/ {for(p=1;p=M.n;p++) ctemp[p]=0 ; /* 当前行各元素的累加器清零*/ Q-first[arow]=Q-len+1; for(p=M.first[arow];pM.first[arow+1];p++) /*p指向M当前行中每一个非零元素*/ {brow=M.data[p].col; /* M中的列号应与N中的行号相等*/ if(browN.n) t=N.first[brow+1]; else t=N.len+1; for(q=N.first[brow];qt;q++) {ccol=N.data[q].col; /*乘积元素在Q中列号*/ ctemp[ccol]+=M.data[p].e*N.data[q].e; } /* for q */ } /*求得Q中第crow行的非零元*/ for(ccol=1;ccolQ-n；col++) /*压缩存储该非零元*/ if(ctemp[ccol]) {if(++Q-lenMAXSIZE) return 0; Q-data[Q-len]={arow, ccol, ctemp[ccol]}; }/* if */ }/* for arow */ }/*if*/ return(TRUE); /*返回TRUE表示求矩阵乘积成功*/ } 2. 稀疏矩阵的链式存储结构：十字链表 优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。 在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有两个域： right： 用于链接同一行中的下一个非零元素； down：用以链接同一列中的下一个非零元素。 right down value col row 十字链表中结点的结构示意图： 十字链表的结构类型说明如下： typedef struct OLNode { int row, col; /*非零元素的行和列下标*/ ElementType value; struct OLNode * right,*down; /*非零元素所在行表列表的后继链域*/ }OLNode; *OLink; typedef struct { OLink * row_head, *col_head; /*行、列链表的头指针向量*/ int m, n, len; /*稀疏矩阵的行数、列数、非零元素的个数*/ }CrossList; 建立稀疏矩阵的十字链表算法： CreateCrossList (CrossList