C++实现稀疏矩阵的压缩存储、转置、快速转置代码分享

发布时间:2020-05-08 14:56:00 作者:Leah
来源:亿速云 阅读:517

本文在介绍关于C++实现稀疏矩阵的压缩存储、转置、快速转置的基础上,重点探讨了其具体步骤分享了代码,本文内容紧凑,希望大家可以有所收获。

/*稀疏矩阵的压缩存储、转置、快速转置*/
#include <iostream>
using namespace std;
#include <vector>

//三元组
template<class T>
struct Triple
{
	size_t _row;
	size_t _col;
	T _value;

	Triple(size_t row = 0, size_t col = 0, const T& value = T())
		:_row(row)
		,_col(col)
		,_value(value)
	{}
};

template<class T>
class SparseMatrix
{
public:
	SparseMatrix(T* a = NULL, size_t M = 0, size_t N = 0, const T& invalid = T())
		:_rowSize(M)
		,_colSize(N)
		,_invalid(invalid)
	{
		for (size_t i = 0; i < M; ++i)
		{
			for (size_t j = 0; j < N; ++j)
			{
				if (a[i*N+j] != _invalid)
				{
					Triple<T> t;
					t._row = i;
					t._col = j;
					t._value = a[i*N+j];

					_a.push_back(t);
				}
			}
		}
	}

	void Display()
	{
		size_t index = 0;

		for (size_t i = 0; i < _rowSize; ++i)
		{
			for (size_t j = 0; j < _colSize; ++j)
			{
				if (index < _a.size()
					&& (_a[index]._row == i)
					&& (_a[index]._col == j))
				{
					cout<<_a[index++]._value<<" ";
				}
				else
				{
					cout<<_invalid<<" ";
				}
			}
			
			cout<<endl;
		}
	}

	//矩阵转置 时间复杂度为 O(有效数据的个数*原矩阵的列数)
	SparseMatrix<T> Transport()
	{
		SparseMatrix<T> sm;
		sm._colSize = _rowSize;
		sm._rowSize = _colSize;
		sm._invalid = _invalid;

		for (size_t i = 0; i < _colSize; ++i)
		{
			size_t index = 0;

			while (index < _a.size())
			{
				if (_a[index]._col == i)
				{
					Triple<T> t;
					t._row = _a[index]._col;
					t._col = _a[index]._row;
					t._value = _a[index]._value;

					sm._a.push_back(t);
				}

				++index;
			}
		}

		return sm;
	}

	//快速转置 时间复杂度为O(有效数据的个数+原矩阵的列数)
	SparseMatrix<T> FastTransport()
	{
		SparseMatrix<T> sm;
		sm._rowSize = _colSize;
		sm._colSize = _rowSize;
		sm._invalid = _invalid;

		int* RowCounts = new int[_colSize];
		int* RowStart = new int [_colSize];
		memset(RowCounts, 0, sizeof(int)*_colSize);
		memset(RowStart, 0, sizeof(int)*_colSize);
		
		size_t index = 0;
		while (index < _a.size())
		{
			++RowCounts[_a[index]._col];
			++index;
		}

		for (size_t i = 1; i < _colSize; ++i)
		{
			RowStart[i] = RowStart[i-1] + RowCounts[i-1];
		}

		index = 0;
		sm._a.resize(_a.size());
		while (index < sm._a.size())
		{
			Triple<T> t;
			t._row = _a[index]._col;
			t._col = _a[index]._row;
			t._value = _a[index]._value;

			sm._a[RowStart[_a[index]._col]] = t;

			++RowStart[_a[index]._col];
			++index;
		}

		delete[] RowCounts;
		delete[] RowStart;

		return sm;
	}
protected:
	vector<Triple<T>> _a;
	size_t _rowSize;
	size_t _colSize;
	T _invalid;
};

void Test()
{
	int array [6][5] = 
	{
		{1, 0, 3, 0, 5},
		{0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0},
		{2, 0, 4, 0, 6},
		{0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0}
	};

	SparseMatrix<int> sm1((int*)array, 6, 5, 0);
	sm1.Display();
	cout<<endl;
	//SprseMatrix<int> sm2 = sm1.Transport();
	SparseMatrix<int> sm2 = sm1.FastTransport();
	sm2.Display();
}

int main()
{
	Test();

	return 0;
}

C++实现稀疏矩阵的压缩存储、转置、快速转置代码分享

看完上诉内容,你们掌握C++实现稀疏矩阵的压缩存储、转置、快速转置的方法了吗?如果想了解更多相关内容,欢迎关注亿速云行业资讯频道!

推荐阅读:
  1. 稀疏矩阵的转置与快速转置
  2. c++矩阵的转置和快速转置

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++ c+

上一篇:深入理解MySQL数据行溢出

下一篇:wpf中textbox无法实时变化解决方法

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》