数据结构-C语言描述(第三版)第4章线性表和数组ADT.ppt

图4－14 稀疏矩阵的转置：方法一 (a) 交换图4－12(b)三元组表A的行、列号；(b) A的转置矩阵的行三元组表B 　　方法二：对数组A扫描n遍，第一遍取出矩阵A的第0列元素，得到转置矩阵B的第0行元素，第i遍扫描取出A的第i－1列元素，得到B的第i－1行元素，依次存入数组B中。此方法的时间复杂度为O(n?×?t)，t为非零元素的个数。 　　以上两种方法都比较费时，下面介绍被称为快速转置算法的方法三。 　　方法三：快速转置算法。 　　快速转置算法通过增加适量的存储空间，来达到节省时间的目的。 　　快速转置算法使用数组k，k[i]为矩阵A中每i列的第一个非零元素在数组B中的存放位置。数组k的长度为矩阵的列数n。如k[3]=5表示矩阵A的第3列第一个非零元素a03=22在数组B的下标为5，见图4－14(b)。 为了得到数组k，我们需要用另一个数组num保存矩阵A的各列的非零元素个数，例如，num[i]存放A的第i列的非零元素的个数，即转置矩阵B的第i行的非零元素个数。 数组num的值由下列语句求得： for (i=0; icols; i++) num[i]=0; /* 初始化数组num*/ for (i=0; inonzeros; i++) num[a.Elements[i].Col]++; 如果数组num的值已计算出，则数组k可以简单地由以下的递推公式计算： (1≤i＜n) 其中，k[0]=0，代表B的第0行的第一个非零元素始终存放在下标为0的位置。很显然，B中第1行第一个非零元素在B中的位置等于k[0]＋num[0]。 (4-6) 一般地，有k[i]=k[i－1]+num[i－1]。见下列语句： k[0]=0; for (i=1; icols; i++) k[i]=k[i－1]+num[i－1]; 对图4－12(b)的三元组表A，计算num和k的结果见表4－2。 有了数组k，只需要对A扫描一次，即可完成转置。完成这项工作的程序段如下： for (i=0; inonzeros; i++){ j=k[a.Elements[i].Col]++; b.Elements[j].Row=a.Elements[i].Col; b.Elements[j].Col=a.Elements[i].Row; b.Elements[j].Value=a.Elements[i].Value; } 上面的程序段中，结构a和b被用来实现矩阵A和B的行三元组表。 (3) 若 p-Element.Expq-Element.Exp，则此时需将q指示的当前项保留在结果多项式中，所以令指针q1和q后移一项，指针p不动。 程序4－10为多项式相加函数PolyAdd的实现，该函数调用函数exp_comp实现两个项的指数间的比较。值得注意的是，算法在多项式A处理完成时结束，即当p-Element.Exp 0 成立时终止外层while循环，如果此时多项式*B中还有未处理的项，则自动保留在结果多项式*B中。 【程序4－10】 函数PolyAdd。 int exp_comp(T x, T y) { if (x.Exp==y.Exp) return 0; else if (x.Expy.Exp) return 1; else return -1; } void PolyAdd (Polynomial A, Polynomial *B) { Node* q, *q1, *q2, *p; T x; p=A.First-Link; q1=B-First; q=q1-Link; while (p-Element.Exp=0) { switch(exp_comp(p-Element, q-Element)){ case -1: q1=q; q=q-Link; break; case 0: q-Element.Coef=q-Element.Coef+p-Element.Coef; if (q-Element.Coef==0){ q2=q; q1-Link=q-Link; q=q-Link; free(q2); p=p-Link; } else { q1