对称矩阵

Matrix.h

#pragmaoncetemplate<classT>classSymmetricMatrix{public:SymmetricMatrix(constT*a,size_tN)//对称矩阵只存下三角:_a(newT[N*(N+1)/2]),_n(N){size_tindex=0;for(size_ti=0;i<N;++i){for(size_tj=0;j<N;++j){if(i>=j){_a[index++]=a[i*N+j];}else{break;}}}}~SymmetricMatrix(){}voidDisplay(){for(size_ti=0;i<_n;++i){for(size_tj=0;j<_n;++j){if(i>=j)//访问下三角{cout<<_a[i*(i+1)/2+j]<<"";}else//访问上三角{cout<<_a[j*(j+1)/2+i]<<"";}}cout<<endl;}cout<<endl;}T&Access(size_ti,size_tj)//访问i,j这里的数据{if(i<j)//若为上三角，交换{swap(i,j);}return_a[i(i+1)/2+j];}protected:T*_a;size_t_n;};voidTest1(){inta[5][5]={{0,1,2,3,4},{1,0,1,2,3},{2,1,0,1,2},{3,2,1,0,1},{4,3,2,1,0},};SymmetricMatrix<int>sm((int*)a,5);sm.Display();}Test.cpp#include<iostream>usingnamespacestd;#include"Matrix.h"intmain(){Test1();system("pause");return0;}

稀疏矩阵

Matrix.h

#include<vector>template<classT>structTriple//三元组{size_t_row;size_t_col;T_value;Triple(size_trow=0,size_tcol=0,constT&value=T()):_row(row),_col(col),_value(value){}};template<classT>classSqarseMatrix//稀疏矩阵{public:SqarseMatrix(size_tM,size_tN,constT&invalid):_M(M),_N(N),_invalid(invalid){}SqarseMatrix(constT*a,size_tM,size_tN,constT&invalid):_M(M),_N(N),_invalid(invalid){for(size_ti=0;i<M;++i){for(size_tj=0;j<N;++j){if(a[i*N+j]!=invalid){Triple<T>t(i,j,a[i*N+j]);_a.push_back(t);}}}}voidDisplay(){size_tindex=0;for(size_ti=0;i<_M;++i){for(size_tj=0;j<_N;++j){if(index<_a.size()&&i==_a[index]._row&&j==_a[index]._col)//不能超出有效值的范围{cout<<_a[index]._value<<"";++index;}else//不是有效值则输出非法值{cout<<_invalid<<"";}}cout<<endl;}cout<<endl;}SqarseMatrix<T>Transport()//转置{//o(有效数据的个数*列数)SqarseMatrix<T>sm(_N,_M,_invalid);for(size_ti=0;i<_N;++i){size_tindex=0;while(index<_a.size()){if(_a[index]._col==i){Triple<T>t(_a[index]._col,_a[index]._row,_a[index]._value);sm._a.push_back(t);}++index;}}returnsm;}SqarseMatrix<T>FastTransport()//快速转置{//O(2*有效数据个数+列数)SqarseMatrix<T>sm(_N,_M,_invalid);int*rowCounts=newint[_N];memset(rowCounts,0,sizeof(int)*_N);//初始化size_tindex=0;while(index<_a.size()){rowCounts[_a[index]._col]++;++index;}int*rowStart=newint[_N];rowStart[0]=0;for(size_ti=1;i<_N;++i){rowStart[i]=rowStart[i-1]+rowCounts[i-1];}index=0;sm._a.resize(_a.size());while(index<_a.size()){size_trow=_a[index]._col;//转置前的列就是转置后的行int&start=rowStart[row];//每行的起始位置，第一个起始位置就是0Triple<T>t(_a[index]._col,_a[index]._row,_a[index]._value);sm._a[start]=t;++start;++index;}delete[]rowCounts;delete[]rowStart;returnsm;}protected:vector<Triple<T>>_a;size_t_M;size_t_N;T_invalid;};voidTest2(){inta[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}};SqarseMatrix<int>sm((int*)a,6,5,0);sm.Display();SqarseMatrix<int>sm2=sm.Transport();sm2.Display();SqarseMatrix<int>sm3=sm.FastTransport();sm3.Display();}Test.cpp#include<iostream>usingnamespacestd;#include"Matrix.h"intmain(){//Test1();Test2();system("pause");return0;}