数据结构05数组和广义表11.pptVIP

* * 为此，需要设置两个一维数组num[0..n]和rpos[0..n]： num[0..n]：统计M中每列非零元素的个数。 rpos[0..n]：M中的每列第一个非零元素在T中的位置。 算法通过rpos数组建立位置对应关系： rpos[0]=0 ； rpos[col]=rpos[col-1]+num[col-1] 0＜col＜M.rows； 例如图5-4(a) 所示的稀疏矩阵的三元组表对应的num[0..n-1]和rpos[0..n-1]如图5-5所示。 （算法5.2见教科书P100） 图5-5 矩阵的num和rpos 数组值 * * 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){ int p,q,col,k; int num[0..a.n],copt[0..a.n]; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”\n); for(col=1;col=a.u;++col) num[col]=0; for(k=1;k=a.t;++k) ++num[a.data[k].j]; cpot[0]=1; for(col=2;col=a.t;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p=a.t;++p){ col=a.data[p].j; q=cpot[col]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; ++cpot[col]; } } } * * 2．行逻辑链接的顺序表(带行表的三元组) 有时为了方便某些矩阵运算，在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。 其类型描述如下： #define maxrow 100 typedef struct{ triple data[maxsize]; int rpos[maxrow]; int n,m,t; }rtripletable * * 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性： 若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。 当n1=m2时有： for(i=1;i=m1;++i) for(j=1;j=n2;++j){ q[i][j]=0 for(k=1;k=n1;++k) q[i][j]+=m[i][k]*n[k][j]; } 此算法的复杂度为O(m1*n1*n2)。 * * 5.3.2 稀疏矩阵的十字链表存储 三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法、乘法）时，非零元个数及位置在操作过程中变化较大时，这种表示就十分不便。 在这节中，我们介绍稀疏矩阵的一种链式存储结构——十字链表，它具备链式存储的特点，因此，在某些情况下，采用十字链表表示三元组的线性表更为恰当。 * * 下图是一个稀疏矩阵的十字链表。 * * 用十字链表表示稀疏矩阵的基本思想是：对每个非零元素存储为一个结点，结点由5个域组成，其结构如图表示，其中：i域存储非零元素的行号，j域存储非零元素的列号，value域存储本元素的值，right向右域，用以链接同一行中下一个非零元素；down向下域，用以链接同一列中下一个非零元素。 next域,用以各行(列)表头结点与其下一结点之间的链接。 算法思想：同一行的非零元素通过right域链接成一个链表，同一列的非零元素通过down域链接成一个链表，每一个非零元既是某个行链表中的结点，同时又是某个列链表中的结点。整个矩阵构成了一个十字交叉的链表。故称为十字链表。 (a) 结点结构 (b) 头结点结构