【数据结构】稀疏矩阵,对称矩阵

前端之家收集整理的这篇文章主要介绍了【数据结构】稀疏矩阵,对称矩阵前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

稀疏矩阵

在矩阵中,若数值为0的元素数目远远多于非0元素的数目时,则称该矩阵为稀疏矩阵

#include <iostream>
#include<cstdlib>
#include <vector>
using namespace std;
template<typename T>
struct Triple
{
	T _value;
	size_t _row;
	size_t _col;
	Triple(T& value,size_t row,size_t col)
		:_value(value),_row(row),_col(col)
	{}
};
template<typename T>
class SparseMatrix
{
public:
	SparseMatrix(T* a=0,size_t m=0,size_t n=0,const T& invalid=0)
	    :_m(m),_n(n),_invalid(invalid)
	{
		for(size_t i=0;i<m;++i)
		{
			for (size_t j=0;j<n;++j)
			{
				if (a[i*m+n]!=_invalid)
				{
					_matrixs.push_back(Triple<T>(a[i*n+j],i,j));
				}
			}
		}
	}
	~SparseMatrix()
	{

	}

	void Display()
	{
		size_t index=0;
		for (int i=0;i<_m;++i)
		{
			for (int j=0;j<_n;++j)
			{
				if(index<_matrixs.size()
					&&_matrixs[index]._row==i
					&&_matrixs[index]._col==j)
				{
					cout<<_matrixs[index]._value<<" ";
					++index;
				}
				else
				{
					cout<<_invalid<<" ";
				}
				//cout<<endl;

			}
			cout<<endl;
		}
		cout<<endl;
	}
	SparseMatrix<T> Transport()
	{
		SparseMatrix<T> Ts;
		Ts._m=_n;
		Ts._n=_m;
		Ts._invalid=_invalid;
		for (int i=0;i<_n;++i)
		{
			size_t index=0;
			while (index<_matrixs.size())
			{
				if(_matrixs[index]._col==i)
				{
					Ts._matrixs.push_back(Triple<T>(_matrixs[index]._value,_matrixs[index]._row));
				}
				++index;
			} 
		}
		return Ts;
	}

private:
	vector<Triple<T>> _matrixs;  
	 T _invalid;//非法值
	int _m;//行
	int _n;//列
};
void test()
{
	int arr[4][4]=
	{{1,0},{2,3,{4,5,6,{7,8,9,10}
	};
	int arr2[4][4]=
	{{1,{0,10}
	};
	
	SparseMatrix<int> sm((int*)arr,4,0);
	cout<<"原始矩阵"<<endl;
	sm.Display();
	SparseMatrix<int> sm1=sm.Transport();
	cout<<"转置矩阵"<<endl;
	sm1.Display();
	SparseMatrix<int> s((int*)arr2,0);
	cout<<"原始矩阵"<<endl;
	s.Display();
	SparseMatrix<int> sm2=s.Transport();
	cout<<"转置矩阵"<<endl;
	sm2.Display();

}
对称矩阵

元素以主对角线为对称轴对应相等的矩阵

#include <iostream>
#include<cstdlib>
using namespace std;
template<typename T>
class SymmetricMatrix
{
public:
	SymmetricMatrix(T* matrix,size_t n)
		:_matrix(new T[n*(n+1)/2]),_size(n*(n+1)/2),_n(n)
	{
		for(size_t i=0;i<n;++i)
		{
			for (size_t j=0;j<n;++j)
			{
				if(i>=j)
				{
					_matrix[i*(i+1)/2+j]=matrix[i*n+j];
				}
			}
		}

	}
	T& Access(size_t i,size_t j)
	{
		if(i<=j)
		swap(i,j);
		return _matrix[i*(i+1)/2+j];
	}
	void Print()
	{
		for (size_t i=0;i<_n;i++)
		{
			for (size_t j=0;j<_n;j++)
			{
				cout<<Access(i,j)<<" ";
			}
			cout<<endl;
		}
		cout<<endl;

	}
private:
	T* _matrix;
	size_t _size;
	size_t _n;
};
void test2()
{
	int arr[6][6]=
	{{0,1,2,7,11},{1,12},13},10,14},15},{11,12,13,14,15,0}
	};
	SymmetricMatrix<int> smx((int*)arr,6);
	smx.Print();
}
测试函数

#include "SparseMatrix.h"
#include "SymmetricMatrix.h"
int main()
{
	test();
	test2();
	system("pause");
	return 0;
}
原文链接:https://www.f2er.com/datastructure/382444.html

猜你在找的数据结构相关文章