稀疏矩阵的实现和转置算法

TriSparseMatrix.h

  1 #pragma once
  2
  3 #include
  4 #include<string.h>
  5 #include
  6 #define DEFAULT_SIZE 5
  7 #define MAX_SIZE 20
  8 typedef int Status;
  9 #define FALSE -1
 10 #define SUCCESS 1
 11 //定义默认尺寸
 12
 13 using namespace std;
 14
 15 template<class ElemType>
 16 struct Triple {
 17     //数据成员
 18     int row, col;        //非零元素的行下标和列下标
 19     ElemType value;        //非零元素的值
 20
 21     //构造函数
 22     Triple() {
 23         row = 0;
 24         col = 0;
 25         value = NULL;
 26     };        //无参构造函数
 27     Triple(int r, int c, ElemType v);        //有参构造函数
 28 };
 29
 30 template <class ElemType>
 31 Triple::Triple(int r, int c, ElemType v) {
 32     row = r;        //初始化行标
 33     col = c;        //初始化列标
 34     value = v;        //初始化非零元素
 35 }
 36
 37 template<class ElemType>
 38 class TriSparseMatrix {
 39 protected:
 40     //稀疏矩阵三元组顺序表的数据成员
 41     Triple* triElems;    //存储稀疏矩阵的三元组表
 42     int maxSize;                //非零元素的最大值
 43     int rows, cols, num;        //稀疏矩阵的行数,列数,非零元素个数
 44 public:
 45     //稀疏矩阵三元组顺序表的函数成员
 46     TriSparseMatrix(int rs = DEFAULT_SIZE, int cs = DEFAULT_SIZE, int size = DEFAULT_SIZE);
 47     ~TriSparseMatrix();            //析构函数
 48     int GetRows() const {        //返回稀疏矩阵行数
 49         return rows;
 50     }
 51
 52     int GetCols() const {
 53         return cols;
 54     }
 55
 56     int GetNum() const {
 57         return num;
 58     }
 59
 60     Status SetElem(int r, int c, const ElemType& v);        //修改指定元素的值
 61     Status GetElem(int r, int c, ElemType& v);                //取指定位置的值
 62     TriSparseMatrix(const TriSparseMatrix& copy);    //复制构造函数
 63     TriSparseMatrix& operator = (const TriSparseMatrix& copy);//赋值运算符重载
 64     void CreateElem(int i);        //创建第i个非零元素
 65     void TriPrint();        //打印矩阵
 66
 67     void SimpleTranspose(TriSparseMatrix& b);
 68     //将稀疏矩阵source转置成b的简单算法;
 69     void FastTranspose(TriSparseMatrix& b);
 70     //将稀疏矩阵source转置成b的快速算法;
 71 };
 72
 73
 74 template <class ElemType>
 75 TriSparseMatrix::TriSparseMatrix(int rs, int cs, int size) {
 76     rows = rs;
 77     cols = cs;
 78     num = size;
 79     maxSize = MAX_SIZE;
 80     triElems = new Triple[maxSize];
 81 }
 82
 83 template <class ElemType>
 84 TriSparseMatrix::~TriSparseMatrix() {
 85     delete[] triElems;
 86 }
 87
 88 template <class ElemType>
 89 Status TriSparseMatrix::SetElem(int r, int c, const ElemType& v) {
 90     if (r < 0 || c < 0 || r >= rows || c >= cols) {
 91         cout << "位置不合法" << endl;
 92         return FALSE;
 93     }
 94     else {
 95         for (int i = 0; i < num; i++) {
 96             if (triElems[i].row == r && triElems[i].col == c) {
 97                 triElems[i].value = v;
 98                 return SUCCESS;
 99             }
100         }
101         return 0;
102     }
103 }
104
105 template <class ElemType>
106 Status TriSparseMatrix ::GetElem(int r, int c, ElemType& v) {
107     if (r < 0 || c < 0 || r >= rows || c >= cols) {
108         cout << "位置不合法" << endl;
109         return FALSE;
110     }
111     else {
112         for (int i = 0; i < num; i++) {
113             if (triElems[i].row == r && triElems[i].col == c) {
114                 v = triElems[i].value;
115                 return SUCCESS;
116             }
117         }
118         return 0;
119     }
120 }
121
122 template <class ElemType>
123 TriSparseMatrix::TriSparseMatrix(const TriSparseMatrix& copy) {
124     int i = copy.GetNum();
125     num = i;
126     rows = copy.GetRows();
127     cols = copy.GetCols();
128     triElems = new Triple[i];
129 }
130
131 template<class ElemType>
132 void TriSparseMatrix< ElemType>::TriPrint() {
133     int i = 0;
134     for (int row = 0; row < rows; row++) {
135         for (int col = 0; col < cols; col++) {
136             if (triElems[i].row == row && triElems[i].col == col) {
137                 cout << triElems[i].value << " ";
138                 i++;
139             }
140             else {
141                 cout << 0 << " ";
142             }
143         }
144         cout << endl;
145     }
146 }
147
148 template <class ElemType>
149 TriSparseMatrix& TriSparseMatrix::operator=(const TriSparseMatrix& copy) {
150     if (© != this) {
151         delete[]triElems;
152         cols = copy.GetCols();
153         rows = copy.GetRows();
154         triElems = new Triple[copy.GetNum()];
155     }
156     return *this;
157 }
158
159 template <class ElemType>
160 void TriSparseMatrix::CreateElem(int i) {
161     int col, row;
162     ElemType val;
163     cout << "请输入非零元素的行数:";
164     cin >> row;
165     cout << "请输入非零元素的列数:";
166     cin >> col;
167     cout << "请输入非零元素的值:";
168     cin >> val;
169     triElems[i].row = row;
170     triElems[i].col = col;
171     triElems[i].value = val;
172 }
173
174 template<class ElemType>
175 void TriSparseMatrix::SimpleTranspose(TriSparseMatrix& b) {
176     //长宽进行转置,再删除已有空间
177     b.rows = cols;
178     b.cols = rows;
179     b.num = num;
180     b.maxSize = maxSize;
181     delete[]b.triElems;
182
183     b.triElems = new Triple[b.maxSize];
184     if (b.num > 0) {
185         int i = 0;        //稀疏矩阵b下一个三元组的存放位置
186         for (int col = 0; col < cols; col++) {//列为0的遍历一遍顺序存储,然后列为1、2、3……
187             for (int j = 0; j < num; j++) {
188                 if (triElems[j].col == col) {
189                     b.triElems[i].row = triElems[j].col;
190                     b.triElems[i].col = triElems[j].row;
191                     b.triElems[i].value = triElems[j].value;
192                     i++;
193                 }//if
194             }//for
195         }//for
196     }//if
197 }//SimpleTranspose时间复杂度O(cols*num)
198
199 template<class ElemType>
200 void TriSparseMatrix::FastTranspose(TriSparseMatrix& b) {
201     //在b中的存储位置只是指在b转换的一维数组中的存储位置,而不是在真实的m*n矩阵中的位置
202     b.rows = cols;
203     b.cols = rows;
204     b.num = num;
205     b.maxSize = maxSize;
206     delete[]b.triElems;
207     b.triElems = new Triple[b.maxSize];
208
209     int* cNum = new int[cols + 1];    //存放矩阵中每一列的非零元素的个数
210     int* cPos = new int[cols + 1];    //存放原矩阵中每一列的第一个非零元素在b中的位置
211
212     int col, i;
213     if (b.num > 0) {
214         for (col = 0; col < cols; col++) {    //初始化cNum数组
215             cNum[col] = 0;
216         }
217         for (i = 0; i < b.num; i++) {        //统计原矩阵中每一列的非零元素个数
218             cNum[triElems[i].col]++;
219         }
220         cPos[0] = 0;    //第0列的第一个非零元素就在0位置
221         for (col = 1; col < cols; col++) {
222             //循环求每一列的第一个非零元素在b存储的位置
223             cPos[col] = cPos[col - 1] + cNum[col - 1];
224         }
225         for (i = 0; i < num; i++) {
226             //循环遍历原矩阵中的三元组。
227             int j = cPos[triElems[i].col];
228             b.triElems[j].row = triElems[i].col;
229             b.triElems[j].col = triElems[i].row;
230             b.triElems[j].value = triElems[i].value;
231             ++cPos[triElems[i].col];    //为同一列的下一个元素标明位置。
232         }
233     }
234     delete[]cNum;
235     delete[]cPos;
236 }//由四个并列循环组成,时间复杂度O(num)

Client.cpp

 1 #include"TriSparseMatrix.h"
 2
 3 void Test() {
 4     TriSparseMatrix<int> tri1(5, 5, 10);    //创建一个5行5列非零元素最多10个的稀疏矩阵
 5     for (int i = 0; i < 10; i++) {
 6         tri1.CreateElem(i);
 7     }
 8     tri1.TriPrint();
 9     TriSparseMatrix<int> tri2 = NULL;
10     tri1.SimpleTranspose(tri2);
11     cout << "简单算法转置后:" << endl;
12     tri2.TriPrint();
13
14     tri1.FastTranspose(tri2);
15     cout << "快速算法转置后:" << endl;
16     tri2.TriPrint();
17 }
18
19 int main() {
20     Test();
21     return 0;
22 }

Original: https://www.cnblogs.com/JIAcheerful/p/16177036.html
Author: 云霄雨霁
Title: 稀疏矩阵的实现和转置算法

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/622637/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • 14. 构造二叉树

    📃 题目一描述 题目链接:从中序与后序遍历构造二叉树 🔔 解题思路 必须明确条件: 给出一个数组的值中,是没有重复的数字的,即没用节点的数值是相同的! 画图分析:(图来自dong哥…

    数据结构和算法 2023年6月12日
    0111
  • 循环链表(约瑟夫环)思路及实现

    单链表的尾节点指向首节点,即可构成循环链表 约瑟夫问题:有 N 个人围成一圈,每个人都有一个编号,编号由入圈的顺序决定,第一个入圈的人编号为 1,最后一个为 N,从第 K (1 O…

    数据结构和算法 2023年6月12日
    098
  • 归并排序及优化

    归并排序 首先把数组分成一半,想办法把左右两边数组排序,之后呢再将它们归并起来,这就是归并排序的基本思想。 这样的话如果有N个元素,就会分成log(n)层,如果整个归并过程我们可以…

    数据结构和算法 2023年6月8日
    0107
  • st表树状数组入门题单

    树状数组用来维护一个具有区间可减(加)性质的工具,所以可以用来维护区间前缀和。区间最值不具有区间可减性,所以不能使用树状数组进行维护,而使用st表。 初始化 &#x9884…

    数据结构和算法 2023年6月7日
    096
  • 多重背包问题的单调队列优化

    多重背包问题的单调队列优化 温馨提示:先吃甜点,再进入正餐食用更佳噢~ 0-1背包问题(餐前甜点) https://www.acwing.com/problem/content/2…

    数据结构和算法 2023年6月7日
    084
  • 密码学之 | RSA 算法之 private public key

    (from geek for geek)The idea of RSA is based on the fact that it is difficult to factorize…

    数据结构和算法 2023年6月8日
    093
  • 音乐项目-环境搭建

    1.后端环境搭建 1.新建工程 2.依赖导入 4.0.0 org.springframework.boot spring-boot-starter-parent 2.3.3.REL…

    数据结构和算法 2023年6月12日
    0130
  • 星空

    大概是因为近视或者污染严重的缘故,我已经很少能看到星空了。更多时候抬起头,望见的只是无法穿透的黑夜。但星空就在那里,它不会因为我看不见它而消失。准确地说,星空一直在我们每个人的心里…

    数据结构和算法 2023年6月12日
    0115
  • 【模板】单源最短路径(Dijkstra)/洛谷P4779

    给定一个 (n) 个点 (m) 条边有向图,每个点有一个非负权值,求从 (s) 点出发,到每个点的最短距离。 数据保证能从 (s) 出发到任意点。 朴素的 (\mathrm{Dij…

    数据结构和算法 2023年6月7日
    074
  • 使用ANSI改变终端输出样式

    默认情况下程序输出到终端的字符样式为白字黑背景,样式、字体比较单一。如想改变程序输出到终端字符的样式等可使用ANSI转移码使其输出具有不同样式; ANSI转义序 ANSI转义序列包…

    数据结构和算法 2023年6月7日
    093
  • C++11实现的数据库连接池

    它什么是? 数据库连接池负责分配、管理和释放数据库连接,它允许应用程序重复使用一个现有的数据库连接,而不是再重新建立一个;类似的还有线程池。 为什么要用? 一个数据库连接对象均对应…

    数据结构和算法 2023年6月8日
    098
  • swap(a, b)异或骚操作方法

    众所周知,平日里我们如果要交换两个变量的时候,通常都是 void swap(int a, int b) { int temp = a; a = b; b = temp; } 通过创…

    数据结构和算法 2023年6月7日
    0116
  • 手撕快速排序(含图解和两种实现代码含改进)

    摘要 快速排序其实也是分而治之的思想 快速排序是递归的 首先找一个基准点,把比基准点小的数字都放到它的左边,比它大的数字都放在它的右边,一趟下来基准点的位置找到了,且它左边的数字小…

    数据结构和算法 2023年6月12日
    0107
  • 使用Vite搭建Vue3+ElementUI-Plus项目过程

    本文主要记录使用Vite搭建一个Vue3+ElementUI-Plus,以及集成Vue Router的过程。本次搭建过程的Nodejs版本为 V16.14.2 创建项目 初始化项目…

    数据结构和算法 2023年6月8日
    0118
  • json序列化NHibernate的实体

    在使用nhibernate时,想将实体对象序列化成json字符串,然后打印在日志中。 序列化时会出现问题,应该是因为这个实体被hibernate管理的原因。具体原因没有分析。 解决…

    数据结构和算法 2023年6月7日
    097
  • AcWing 1100. 抓住那头牛(搜索)

    题目链接 题目描述 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点 N,牛位于点 K。农夫有两种移动方式: 从 X 移动到 X−1 或 X+1,每次移动花费…

    数据结构和算法 2023年6月16日
    0178
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球