数据结构与算法第5章数组.ppt

* 4.4 矩阵的转置 稀殊矩阵： ①三元组顺序表 的转置运算 “列序”递增转置法 算法实现 void TransposeTSMatrix(TSMatrix A,TSMatrix *B) { int i,j,k; B-m=A.n; B-n=A.m; B-len=A.len; if(B-len0) { j=1; for(k=1; k=B-m; 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++; } } } #define MAXSIZE 1000 typedef struct { int row, col; ElementType e ; }Triple; typedef struct { Triple data[MAXSIZE +1]; int m, n, len; }TSMatrix; * 第 5 章 数组和广义表 - - 0 28 0 0 36 0 0 0 7 0 5 0 0 14 0 - - 0 0 5 28 0 0 0 0 0 0 7 14 36 0 0 1 2 14 2 2 -7 3 1 36 3 4 28 1 5 -5 i j v i j v 2 1 14 2 2 -7 1 3 36 4 3 28 5 1 -5 矩阵的转置 转置后行号 1 2 3 4 5 该行起始位置 4 5 2 1 4 方法二: 3 6 4 5 2 * col 1 2 3 4 5 num[col] 0 0 0 0 0 1 1 2 1 1 col 1 2 3 4 5 num[col] 0 0 0 0 0 1 1 2 1 1 position[col] 1 2 4 4 5 1 2 14 2 2 -7 3 1 36 3 4 28 1 5 -5 i j v * 第 5 章 数组和广义表 稀殊矩阵： ①三元组顺序表 的转置运算 一次定位快速转置 算法步骤： a.扫描矩阵A的三元组表，统计出A的每一列的 非零元素的个数，存放到数组num[col]中 （num[col] 存放M第col列的非零元素个数）。 b.计算转置矩阵B的每一行在三元组表中的开始 位置，并存放到数组position[col]中， （position[col] 存放T第col行开始位置）。 c.再次扫描矩阵A的三元组表，根据非零元素的列号col， 确定它转置后的行号，查position表，按查到的位置直 接将该项存入转置三元组表B中,并修改position[col] ,将 其指向该行下一个元素的存储位置(position[col ] ++ )。 矩阵的转置 * 第 5 章 数组和广义表 稀殊矩阵： ①三元组顺序表 的转置运算 一次定位快速转置 算法实现： a. for(col=1;col=A.n;col++) num[col]=0; for(t=1;t=A.len;t++) num[A.data[t].col]++; 1 2 14 2 2 -7 3 1 36 3 4 28 1 5 -5 i j v col 1 2 3 4 5 num[col] 0 0 0 0 0 1 1 2 1 1 矩阵的转置 * 第 5 章 数组和广义表 稀殊矩阵： ①三元组顺序表 的转置运算 一次定位快速转置 算法实现： position[1] = 1; for(col=2;colA.n;col++) position[col] = position[col-1]+num[col-1]; col 1 2 3 4 5 n