数据结构第五章数组和广义表.ppt

B = 0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 分析： ◆ 将矩阵的行列数的值交换 ◆ 将每一个三元组的 i 和 j 相互调换 ◆ 重排三元组之间的次序 A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 算法一 i j v 0 1 2 3 4 5 6 7 8 3 1 -3 6 1 15 1 2 12 5 2 18 1 3 9 4 3 24 6 4 -7 3 6 14 6 7 8 i j v 0 1 2 3 4 5 6 7 8 2 1 12 4 6 -7 1 3 -3 3 4 24 1 6 15 3 1 9 6 3 14 2 5 18 7 6 8 按照A的列序来进行转换的基本思想 对 ma[ ] 从头至尾扫描： 第一次扫描时，将 ma[ ]中列号为0的所有元组交换行列值后，依次赋值到 mb[ ]中； 第二次扫描时，将 ma[ ]中列号为1的所有元组交换行列值后，依次赋值到 mb[ ] 中； 依此类推，直至将 ma[ ]的所有三元组赋值到 mb[ ]中。 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v 3 1 -3 2 5 18 1 3 -3 6 1 15 1 6 15 1 2 12 2 1 12 5 2 18 1 3 9 3 1 9 4 3 24 3 4 24 6 4 -7 4 6 -7 3 6 14 6 3 14 A矩阵 B矩阵 对A六次扫描完成转置运算 第一次扫描查找第1列元素 第一次扫描结束 第二次扫描结束 第二次扫描查找第2列元素 第三次扫描查找第3列元素 第四次扫描查找第4列元素 第五次扫描查找第5列元素 第六次扫描查找第6列元素 转置运算算法图示 0 1 2 3 4 5 6 7 8 6 7 8 7 6 8 算法一描述(保持以行序为主序存储) int tpm(tsmatrix m, tsmatrix *t) { t-mu=m.nu; t-nu=m.mu; t-tu=m.tu; if(t-tu) { q=1; for(col=1;col=m.nu;col++) for(p=1;p=m.tu;p++) if(m.data[p].j==col) { t-data[q].i=m.data[p].j; t-data[q].j=m.data[p].i; t-data[q].v=m.data[p].v; q++; } } return ok; } ▲ 时间复杂度为 〇(nu×tu) i j v 0 1 2 3 4 5 6 7 8 7 6 8 mb[ ] 算法二——快速转置算法 方法：以 A 矩阵的三元组为中心, 依次取出 ma[ ] 中的每一个三元组，交换行列后，直接将其写入mb[ ]合适的位置中。 3 4 24 1 6 15 3 1 9 6 3 14 2 5 18 1 3 -3 i j v ma[ ] 0 1 2 3 4 5 6 7 8 3 1 -3 6 1 15 6 7 8 5 2 18 1 3 9 4 3 24 6 4 -7 3 6 14 1 2 12 2 1 12 4 6 -7 ⑤ 十字链表 I 概念