c语言用指针求Amn,[工学]第5章数据结构C语言描述耿国华.ppt

[工学]第5章数据结构C语言描述耿国华

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; col