数据结构第6章矩阵和广义表.ppt

第六章 数组和广义表 前面讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。 本章讨论的两种数据结构——数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。 void transpose(sparmatrix a,sparmatrix b) {b.rows=a.cols; b.cols=a.rows; b.terms=a.terms; if (b.terms0){int bno=0; for (int col=0; cola.cols; col++)//按列号扫描 for(int ano=0;anoa.terms;ano++)//对三元组表扫描 if (a.data[ano].j==col) //进行转置 { b.data[bno].j=a.data[ano].i; b.data[bno].i=a.data[ano].j; b.data[bno].v=a.data[ano].v; bno++;}}} 分析这个算法，主要工作在col和ano二重循环上，故算法的时间复杂度为 O(a.cols*a.terms)。而通常的m?n阶矩阵转置算法可描述为： for(col=0; coln; col++) for (row=0;rowm;row++) b[col][row]=a[row][col]; 它的时间复杂度为o(m?n)。而一般的稀疏矩阵中非零元个数a.terms远大于行数 m，故压缩存贮时，进行转置运算，虽然节省了存贮单元，但增大了时间复杂度，故此算法仅适应于a.ternsa.rows? a.cols的情形。 （2）按照A的行序进行转置 即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。若能在转置前求出矩阵A的每一列col(即B中每一行)的第一个非零元转置后在b.data中的正确位置pot[col](0≤cola.cols)，那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.data[pot[col]]中，之后将pot[col]内容加1，以指示第col列的下一个非零元的正确位置。为了求得位置向量pot，只要先求出A的每一列中非零元个数num[col]，然后利用下面公式： pot[0]=0 ? pot[col]=pot[col-1]+num[col-1] 当1≤cola.cols 算法描述如下： void fastrans(sparmatrix a,sparmatrix b) { int pot[100],col,ano,bno; b.rows=a.cols; b.cols=a.rows;b.terms=a.terms; if (b.terms0) { for(col=0;cola.cols;col++) pot[col]=0; for(int t=0;ta.terms;t++) //求出每一列的非零元个数 { col=a.data[t].j; pot[col+1]=pot[col+1]++; } pot[0]=0; for(col=1;cola.cols;col++) //求出每一列的第一个非零元在转置后的位置 pot[col]=pot[col-1]+pot[col]; for( ano=0;anoa.terms;ano++) //转置 { col=a.data[ano].j; bno=pot[col]; b.data[bno].j=a.data[ano].i; b.data[bno].i=a.data[ano].j; b.data[bno].v=a.data[ano].v; pot[col]=pot[col]+1;}} } 该算法比按列转置多用了辅助向量空间pot，但它的时间为四个单循环，故总的时间复杂度为O(a.cols+a.terms)，比按列转置算法效率要高。 2．稀疏矩阵的相加运算 当稀疏矩阵用三元组表进行相加时，有可能出现非零元素的位置变动，这时候，不宜采用三元组表作存储结构，而应该采用十字链表较方便。 5.5 广义表 5.5.1基本概念 广义表是第二章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表(另一个线性表)。 1．广义表的定义 广义表是n≥0个元素a1，a2，…，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=(a1,a2,…,an)，其中LS为广义表的名字，n为广义表的长度， 每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。