十四、矩阵的快速转置算法

文章目录

• 十四、矩阵的快速转置算法
• • 题目描述
  • 解题思路
  • 上机代码

题目描述

数据压缩是提高传输、存储效率一种技术。教材第5章介绍了两种简单的压缩存储方法。本实验要求实现三元组顺序表表示下的矩阵快速转置算法。

输入：

​ 稀疏矩阵的行数、列数、非零元个数(三个数都大于0)

​ 以行为主序输入稀疏矩阵三元组表

输出：

​ 辅助数组num[ ]

​ 辅助数组cpot[ ]

​ 以行为主序输出对应的转置矩阵三元组表

测试输入期待的输出时间限制内存限制额外进程

测试用例 1	6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7	num:2,2,2,1,0,1,0, cpot:1,3,5,7,8,8,9, 1,3,-3 1,6,15 2,1,12 2,5,18 3,1,9 3,4,24 4,6,-7 6,3,14	1秒	256KB	0
测试用例 2	5 4 6 2 1 1 2 2 2 4 2 2 4 3 3 5 3 3 5 4 4	num:1,2,2,1, cpot:1,2,4,6, 1,2,1 2,2,2 2,4,2 3,4,3 3,5,3 4,5,4	1秒	64M	0

解题思路

稀疏矩阵的快速转置算法在教材（紫皮书）上已经有了很详细的介绍，我们只需要按照方法一步一步复现出来就好了。

• 教材第 98 页，定义了三元组顺序表和稀疏矩阵
• 第 99 页，详细介绍了快速转置算法的原理：按照 a.data 中三元组的次序进行转置，并将转置后的三元组置于 b 中恰当的位置
• 第 100 页，给出了快速转置算法的具体实现

上机代码

#include<cstdio> #include<stack> #include<cstring> #include<cstdlib> #include<iostream> using namespace std; #define MAXSIZE 12500//定义三元组 typedef struct {int i, j;int e; }Triple; //定义稀疏矩阵 typedef struct {Triple data[MAXSIZE + 1];int mu, nu, tu; }TSMatrix;//两个辅助数组 int num[1010] = { 0 }, cpot[1010] = { 0 };int main() {TSMatrix M, T;int row = 0, col = 0;int t = 0, p = 0, q = 0;//输入三元组表cin >> M.mu >> M.nu >> M.tu;for (int i = 1; i <= M.tu; i++){cin >> M.data[i].i >> M.data[i].j >> M.data[i].e;}/* 快速转置算法 */T.nu = M.mu;T.mu = M.nu;T.tu = M.tu;if (T.tu){for (col = 1; col <= M.nu; ++col)num[col] = 0;for (t = 1; t <= M.tu; ++t)++num[M.data[t].j];cpot[1] = 1;cpot[0] = 1;for (col = 2; col <= M.nu; ++col)cpot[col] = cpot[col - 1] + num[col - 1];for (p = 1; p <= M.tu; p++){col = M.data[p].j;q = cpot[col];T.data[q].i = M.data[p].j;T.data[q].j = M.data[p].i;T.data[q].e = M.data[p].e;++cpot[col];}}//输出辅助数组cout << "num:";for (int i = 1; i <= M.nu; i++)cout << num[i] << ",";cout << endl;cout << "cpot:";for (int i = 0; i < M.nu; i++)cout << cpot[i] << ",";cout << endl;//输出转置矩阵三元组表for (int i = 1; i <= M.tu; i++)cout << T.data[i].i << "," << T.data[i].j << "," << T.data[i].e << endl;return 0; }

总结

以上是生活随笔为你收集整理的十四、矩阵的快速转置算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。