【精品数据结构】数组讲解.pptVIP

第四章 数组 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 4.1 数组的定义和特点 定义 4.2 数组的顺序存储结构 次序约定 以行序为主序 以列序为主序 4.3 矩阵的压缩存储 对称矩阵 三角矩阵 稀疏矩阵的压缩存储方法 顺序存储结构 三元组表 带辅助行向量的二元组表 求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法： 十字链表 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义 for(col=1;col=a.n;col++) for(p=0;p=a.t;p++) if(a.data[p].j==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; q++; } } 分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;++col) for(row=0;row=m;++row) t[col][row]=m[row][col]; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t=m*n的情况。 下面给出一种快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。 为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num[0..n]和cpot[0..n] num[0..n]：统计M中每列非零元素的个数，num[col]的值可以由A的第二列求得。 cpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot[1]=1 cpot[i]=cpot[i-1]+num[i-1] 2=i=a.n 例如：图中的矩阵M和相应的三元组A可以求得num[i]和 cpot[i]的值如下： i 1 2 3 4 5 6 7 num[i] 2 2 2 1 0 1 0 cpot[i] 1 3 5 7 8 8 9 v 2 1 … q A i j v 第一列元素个数 第二列元素个数 第三列元素个数 num cpot q=cpot[i] v 1 2 p q 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){ int p,q,l,k; int num[a.n],copt[a.n]; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”\n); for(l=1;l=a.n;++l) num[l]=0; for(k=1;k=a.t;++k) ++num[a.data[k].j]; cpot[0]=1; for(l=2; l=a.t;++l) cpot[l]=cpot[l-1]+num[l-1]; for(p=1;p=a.t;++p){ col=a.data[p].j; q=cpot[l]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.da