什么是稀疏矩陣呢，就是在M*N的矩陣中，有效值的個(gè)數(shù)遠(yuǎn)小于無(wú)效值的個(gè)數(shù)，并且這些數(shù)據(jù)的分布沒(méi)有規(guī)律。在壓縮存儲(chǔ)稀疏矩陣的時(shí)候我們只存儲(chǔ)極少數(shù)的有效數(shù)據(jù)。我們?cè)谶@里使用三元組存儲(chǔ)每一個(gè)有效數(shù)據(jù)，三元組按原矩陣中的位置，以行優(yōu)先級(jí)先后次序依次存放。下面我們來(lái)看一下代碼實(shí)現(xiàn)。

[[241564]]

#include<iostream> 
#include<vector> 
#include<assert.h> 
usingnamespace std; 
template<class T> 
class SparseMatrix 
{ 
//三元組 
template<class T> 
struct Trituple 
{ 
Trituple()//給一個(gè)默認(rèn)構(gòu)造函數(shù) 
{} 
Trituple(size_t row, size_t col, const T& data) 
:_row(row) 
,_col(col) 
,_data(data) 
{} 
size_t _row; 
size_t _col; 
T _data; 
}; 
public: 
//稀疏矩陣的壓縮存儲(chǔ) 
SparseMatrix() 
{} 
SparseMatrix(int* arr, size_t row, size_t col, const T& invalid) 
:_row(row) 
,_col(col) 
,_invalid(invalid) 
{ 
for(int i = 0; i < row; i++) 
{ 
for(int j = 0; j < col; ++j) 
{ 
if(arr[i*col+j] != invalid)//將有效值存儲(chǔ)在一個(gè)一維數(shù)組中 
_sm.push_back(Trituple<T>(i,j,arr[i*col+j]));//將三元組的無(wú)名對(duì)象push進(jìn)去 
} 
} 
} 
//訪問(wèn)稀疏矩陣中row行col中的元素 
T& Acess(int row, int col) 
{ 
//1、 
/*for(int idx = 0; idx < _sm.size(); idx++)//遍歷一遍 
{ 
if(_sm[idx]._row == row && _sm[idx]._col == col)//當(dāng)前行列與我們要訪問(wèn)那個(gè)元素行列相同時(shí)返回這個(gè)有效值 
return _sm[idx]._data; 
} 
return _invalid;*///否則返回?zé)o效值 
//2、 
vector<Trituple<T>>::iterator it = _sm.begin();//定義一個(gè)迭代器,指向起始位置 
while(it != _sm.end())//未到***一個(gè)元素時(shí) 
{ 
if(it->_row == row && it->_col == col)//行列相等輸出值 
return it->_data; 
++it;//迭代器向后移動(dòng) 
} 
return _invalid; 
} 
//還原稀疏矩陣 
template<typename T> 
friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& s)//重載<< 
{ 
size_t idex = 0; 
for(size_t i = 0; i < s._row; i++) 
{ 
for(size_t j = 0; j < s._col; j++) 
{ 
if(idex < s._sm.size()/*防止數(shù)組越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j) 
{ 
_cout<<s._sm[idex]._data<<" "; 
++idex; 
} 
else 
_cout<<s._invalid<<" "; 
} 
_cout<<endl; 
} 
return _cout; 
} 
//實(shí)現(xiàn)稀疏矩陣的逆置 時(shí)間復(fù)雜度O(M*N)(M為元素個(gè)數(shù)N為矩陣列數(shù)) 
SparseMatrix<T> Transport() 
{ 
SparseMatrix<T> sm; 
sm._row = _col; 
sm._col = _row; 
sm._invalid = _invalid; 
for(size_t i = 0; i < _col; i++) 
{ 
vector<Trituple<T>>::iterator it = _sm.begin(); 
while(it != _sm.end()) 
{ 
if(it->_col == i)//從原矩陣第0列開始，將每列中的有效值依次放入新的稀疏矩陣 
sm._sm.push_back(Trituple<T> (i, it->_row, it->_data)); 
++it; 
} 
} 
return sm; 
} 
//實(shí)現(xiàn)稀疏矩陣的快速轉(zhuǎn)置 時(shí)間復(fù)雜度O(N)+O(M) 
SparseMatrix<T> FastTransport() 
{ 
SparseMatrix<T> sm; 
sm._col = _row; 
sm._row = _col; 
sm._invalid = _invalid; 
sm._sm.resize(_sm.size());//開辟空間 
//1、統(tǒng)計(jì)原矩陣中每一列有多少個(gè)有效元素 
int* pCount = newint[_col];//開辟原矩陣中列個(gè)數(shù)的空間 
memset(pCount, 0, _col*sizeof(pCount[0])); 
for(int i = 0; i < _sm.size(); i++) 
pCount[_sm[i]._col]++; 
//2、原矩陣每一列在新矩陣中的起始位值 
int* pAddr = newint[_col]; 
memset(pAddr, 0, _col*sizeof(pAddr[0])); 
for(int i = 1/*從1開始，***個(gè)位置起始為0已經(jīng)放入*/; i < _sm.size(); i++) 
{ 
pAddr[i] = pAddr[i - 1] + pCount[i - 1];//前一個(gè)起始位值+前一列有效元素個(gè)數(shù) 
} 
//3、放置元素到新空間 
for(int i = 0; i < _sm.size(); i++) 
{ 
int& addr = pAddr[_sm[i]._col]; 
sm._sm[addr] = Trituple<T>(_sm[i]._col,_sm[i]._row,_sm[i]._data); 
addr++; 
} 
return sm; 
} 
//實(shí)現(xiàn)稀疏矩陣的加法操作1 
/*SparseMatrix<T> operator+(const SparseMatrix<T>& sp) 
{ 
int i = 0, j = 0, k = 0; 
T v; 
SparseMatrix<T> s; 
if(this->_col != sp._col || this->_row != sp._row) 
exit(1); 
s._row = sp._row; 
s._col = sp._col; 
s._invalid = sp._invalid; 
while(i < this->_sm.size() && j < sp._sm.size()) 
{ 
if(this->_sm[i]._row == sp._sm[j]._row) 
{ 
if(this->_sm[i]._col < sp._sm[j]._col) 
{ 
s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data)); 
i++; 
k++; 
} 
else if(this->_sm[i]._col > sp._sm[j]._col) 
{ 
s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data)); 
j++; 
k++; 
} 
else 
{ 
v = this->_sm[i]._data + sp._sm[j]._data; 
if(v) 
{ 
s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, v)); 
k++; 
} 
i++; 
j++; 
} 
} 
else if(this->_sm[i]._row < sp._sm[j]._row) 
{ 
s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data)); 
i++; 
k++; 
} 
else 
{ 
s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data)); 
j++; 
k++; 
} 
} 
return s; 
}*/ 
//實(shí)現(xiàn)稀疏矩陣的加法操作2 
SparseMatrix<T> operator+(const SparseMatrix<T>& sp) 
{ 
assert(_row == sp._row && _col == sp._col);//檢測(cè)兩個(gè)相加的矩陣行列是否相等 
SparseMatrix<T> ret; 
ret._row = _row; 
ret._col = _col; 
ret._invalid = _invalid; 
int iLidx = 0, iRidx = 0;//定義兩個(gè)索引 
while(iLidx < _sm.size() && iRidx < sp._sm.size()) 
{ 
size_t AddrLeft = _sm[iLidx]._row*_col+_sm[iLidx]._col;//左邊矩陣的起始位值 
size_t AddrRight = sp._sm[iRidx]._row*sp._col+sp._sm[iRidx]._col;//右邊矩陣起始位值 
if(AddrLeft < AddrRight)//左<右，將左邊有效值放入和矩陣中，左邊的索引加加 
{ 
ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data)); 
iLidx++; 
} 
elseif(AddrLeft > AddrRight) 
{ 
ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data)); 
iRidx++; 
} 
else//當(dāng)左邊等于右邊判斷相加后和是否為0，不為0放入 
{ 
Trituple<T> temp(_sm[iLidx]); 
temp._data += sp._sm[iRidx]._data; 
if(temp._data) 
{ 
ret._sm.push_back(temp); 
iLidx++; 
iRidx++; 
} 
} 
} 
while(iLidx < _sm.size())//左邊還有剩余則放入剩余元素 
{ 
ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data)); 
iLidx++; 
} 
while(iRidx < sp._sm.size()) 
{ 
ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data)); 
iRidx++; 
} 
return ret; 
} 
private: 
size_t _row; 
size_t _col; 
vector<Trituple<T>> _sm; 
T _invalid;//無(wú)效值 
}; 
int main() 
{ 
int arr[6][5] = { 
{1,0,3,0,5}, 
{0,0,0,0,0}, 
{0,0,0,0,0}, 
{1,0,3,0,5}, 
{0,0,0,0,0}, 
{0,0,0,0,0}}; 
int arr1[6][5] = { 
{1,0,3,0,5}, 
{0,0,0,0,0}, 
{0,0,2,4,0}, 
{1,0,3,0,5}, 
{0,0,0,1,0}, 
{0,0,0,0,1}}; 
SparseMatrix<int> s((int*)arr,6,5,0); 
SparseMatrix<int> s1((int*)arr1,6,5,0); 
cout<<"訪問(wèn)三行四列元素"<<endl; 
cout<<s.Acess(3,4)<<endl; 
cout<<s<<endl; 
cout<<"快速轉(zhuǎn)置"<<endl; 
cout<<s.FastTransport(); 
cout<<endl; 
cout<<"矩陣s："<<endl; 
cout<<s<<endl; 
cout<<"矩陣s1："<<endl; 
cout<<s1<<endl; 
cout<<"s+s1求和："<<endl; 
cout<<s1+s<<endl; 
system("pause"); 
return 0; 
} 

運(yùn)行結(jié)果截圖：

在上面的代碼中用到C++模板、標(biāo)準(zhǔn)庫(kù)中vector容器，以及迭代器實(shí)現(xiàn)了一些基本的操作，如訪問(wèn)稀疏矩陣中某個(gè)元素，輸出稀疏矩陣、稀疏矩陣的轉(zhuǎn)置以及快速轉(zhuǎn)置還有兩個(gè)稀疏矩陣的加法。

快速轉(zhuǎn)置操作的基本思路是：

（1）統(tǒng)計(jì)原矩陣中每一列有多少個(gè)有效元素；

（2）原矩陣中每一列在新矩陣中的起始地址；

（3）放置元素到新空間中。

還需注意的是，在我們打印這個(gè)稀疏矩陣時(shí)雖然也可以直接調(diào)用訪問(wèn)元素的Acess接口，但是每次進(jìn)去之后都得遍歷一遍，時(shí)間復(fù)雜度較高，所以我們不采取這種辦法，而是比較當(dāng)前行列的值，若相等輸出有效元素，不等則輸出無(wú)效元素0。