C++實現稀疏矩陣的壓縮存儲

知識 07-08

什麼是稀疏矩陣呢，就是在M*N的矩陣中，有效值的個數遠小於無效值的個數，並且這些數據的分布沒有規律。在壓縮存儲稀疏矩陣的時候我們只存儲極少數的有效數據。我們在這裡使用三元組存儲每一個有效數據，三元組按原矩陣中的位置，以行優先順序先後次序依次存放。下面我們來看一下代碼實現。

#include

#include

#include

usingnamespace std;

template

class SparseMatrix

{

//三元組

template

struct Trituple

{

Trituple()//給一個默認構造函數

{}

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:

//稀疏矩陣的壓縮存儲

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)//將有效值存儲在一個一維數組中

_sm.push_back(Trituple(i,j,arr[i*col+j]));//將三元組的無名對象push進去

}

}

}

//訪問稀疏矩陣中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)//當前行列與我們要訪問那個元素行列相同時返回這個有效值

return _sm[idx]._data;

}

return _invalid;*///否則返回無效值

//2、

vector>::iterator it = _sm.begin();//定義一個迭代器,指向起始位置

while(it != _sm.end())//未到最後一個元素時

{

if(it->_row == row && it->_col == col)//行列相等輸出值

return it->_data;

++it;//迭代器向後移動

}

return _invalid;

}

//還原稀疏矩陣

template

friend ostream& operator<<(ostream& _cout, SparseMatrix& 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()/*防止數組越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j)

{

_cout<

++idex;

}

else

_cout<

}

_cout<

}

return _cout;

}

//實現稀疏矩陣的逆置時間複雜度O(M*N)(M為元素個數N為矩陣列數)

SparseMatrix Transport()

{

SparseMatrix sm;

sm._row = _col;

sm._col = _row;

sm._invalid = _invalid;

for(size_t i = 0; i < _col; i++)

{

vector>::iterator it = _sm.begin();

while(it != _sm.end())

{

if(it->_col == i)//從原矩陣第0列開始，將每列中的有效值依次放入新的稀疏矩陣

sm._sm.push_back(Trituple (i, it->_row, it->_data));

++it;

}

}

return sm;

}

//實現稀疏矩陣的快速轉置時間複雜度O(N)+O(M)

SparseMatrix FastTransport()

{

SparseMatrix sm;

sm._col = _row;

sm._row = _col;

sm._invalid = _invalid;

sm._sm.resize(_sm.size());//開闢空間

//1、統計原矩陣中每一列有多少個有效元素

int* pCount = newint[_col];//開闢原矩陣中列個數的空間

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開始，第一個位置起始為0已經放入*/; i < _sm.size(); i++)

{

pAddr[i] = pAddr[i - 1] + pCount[i - 1];//前一個起始位值+前一列有效元素個數

}

//3、放置元素到新空間

for(int i = 0; i < _sm.size(); i++)

{

int& addr = pAddr[_sm[i]._col];

sm._sm[addr] = Trituple(_sm[i]._col,_sm[i]._row,_sm[i]._data);

addr++;

}

return sm;

}

//實現稀疏矩陣的加法操作1

/*SparseMatrix operator+(const SparseMatrix& sp)

{

int i = 0, j = 0, k = 0;

T v;

SparseMatrix 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(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(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(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(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));

i++;

k++;

}

else

{

s._sm.push_back(Trituple(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));

j++;

k++;

}

}

return s;

}*/

//實現稀疏矩陣的加法操作2

SparseMatrix operator+(const SparseMatrix& sp)

{

assert(_row == sp._row && _col == sp._col);//檢測兩個相加的矩陣行列是否相等

SparseMatrix ret;

ret._row = _row;

ret._col = _col;

ret._invalid = _invalid;

int iLidx = 0, iRidx = 0;//定義兩個索引

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(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));

iLidx++;

}

elseif(AddrLeft > AddrRight)

{

ret._sm.push_back(Trituple(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));

iRidx++;

}

else//當左邊等於右邊判斷相加後和是否為0，不為0放入

{

Trituple 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(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));

iLidx++;

}

while(iRidx < sp._sm.size())

{

ret._sm.push_back(Trituple(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));

iRidx++;

}

return ret;

}

private:

size_t _row;

size_t _col;

vector> _sm;

T _invalid;//無效值

};

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 s((int*)arr,6,5,0);

SparseMatrix s1((int*)arr1,6,5,0);

cout<<"訪問三行四列元素"<

cout<

cout<

cout<<"快速轉置"<

cout<

cout<

cout<<"矩陣s："<

cout<

cout<<"矩陣s1："<

cout<

cout<<"s+s1求和："<

cout<

system("pause");

return 0;

}