[理学]数据结构第5章.ppt

j=1;  for(k=1; k=A.n; k++)  for(i=1; i=A.len; i++) if(A.data［i］.col==k) { B-data［j］.row=A.data［i］.col B-data［j］.col=A.data［i］.row;  B-data［j］.e=A.data［i］.e;  j++;  } } } 【算法5.1 基于稀疏矩阵的三元组表示矩阵的转置算法】 算法的时间耗费主要是在双重循环中，其时间复杂度为O（A.n×A.len）, 最坏情况下，当A.len=A.m×A.n时，时间复杂度为O（A.m×A.n2）。采用正常方式实现矩阵转置的算法时间复杂度为O（A.m×A.n）。  方法二： 依次按三元组表A的次序进行转置，转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。 为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算以下数据：  (1) 待转置矩阵source每一列中非零元素的个数（即转置后矩阵dest每一行中非零元素的个数）。  (2) 待转置矩阵source每一列中第一个非零元素在三元组表B中的正确位置（即转置后矩阵dest每一行中第一个非零元素在三元组B中的正确位置)。 为此， 需要设两个数组num［ ］和position［ ］，其中num［col］用来存放三元组表A中第col列中非零元素个数（三元组表B中第col行非零元素的个数），position［col］用来存放转置前三元组表A中第col列（转置后三元组表B中第col行）中第一个非零元素在三元组表B中的正确位置。 num［col］的计算方法：  将三元组表A扫描一遍，对于其中列号为k的元素，给相应的num［k］加1。  position［col］的计算方法：  position［1］=1，  position［col］=position［col-1］+num［col-1］， 其中2≤col≤A.n。 图5.16 图5.10中矩阵M的num［col］和position［col］的值 将三元组表A中所有的非零元素直接放到三元组表B中正确位置上的方法：  position［col］的初值为三元组表A中第col列（三元组表B的第col行）中第一个非零元素的正确位置，当三元组表A中第col列有一个元素加入到三元组表B时，则position［col］=position［col］+1，即： 使position［col］始终指向三元组表A中第col列中下一个非零元素的正确位置。  具体算法如下： FastTransposeTSMatrix (TSMatrix A, TSMatrix * B) { /*基于矩阵的三元组表示， 采用快速转置法， 将矩阵A转置为B所指的矩阵*/ int col, t, p， q;  int num［MAXSIZE］, position［MAXSIZE］;  B-len=A.len; B-n=A.m; B-m=A.n;  if(B-len) { for(col=1; col=A.n; col++) num［col］=0;  for(t=1; t=A.len; t++) num［A.data［t］.col］++; /*计算每一列的非零元素的个数*/ position［1］=1;  for(col=2; colA.n; col++) /*求col列中第一个非零元素在B.data［ ］中的正 确位置 */ position［col］=position［col-1］+num［col-1］;  for(p=1; pA.len.p++) { col=A.data［p］.col; q=position［col］; 