什么是稀疏矩陣呢，就是在M*N的矩陣中，有效值的個數遠小于無效值的個數，并且這些數據的分布沒有規律。在壓縮存儲稀疏矩陣的時候我們只存儲極少數的有效數據。我們在這里使用三元組存儲每一個有效數據，三元組按原矩陣中的位置，以行優先級先后次序依次存放。下面我們來看一下代碼實現。
#include<iostream> #include<vector> #include<assert.h> using namespace std; template<class T> class SparseMatrix { //三元組 template<class T> 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<T>(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<Trituple<T>>::iterator it = _sm.begin();//定義一個迭代器,指向起始位置 while(it != _sm.end())//未到最后一個元素時 { if(it->_row == row && it->_col == col)//行列相等輸出值 return it->_data; ++it;//迭代器向后移動 } 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()/*防止數組越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j) { _cout<<s._sm[idex]._data<<" "; ++idex; } else _cout<<s._invalid<<" "; } _cout<<endl; } return _cout; } //實現稀疏矩陣的逆置 時間復雜度O(M*N)(M為元素個數N為矩陣列數) 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; } //實現稀疏矩陣的快速轉置 時間復雜度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、統計原矩陣中每一列有多少個有效元素 int* pCount = new int[_col];//開辟原矩陣中列個數的空間 memset(pCount, 0, _col*sizeof(pCount[0])); for(int i = 0; i < _sm.size(); i++) pCount[_sm[i]._col]++; //2、原矩陣每一列在新矩陣中的起始位值 int* pAddr = new int[_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<T>(_sm[i]._col,_sm[i]._row,_sm[i]._data); addr++; } return sm; } //實現稀疏矩陣的加法操作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; }*/ //實現稀疏矩陣的加法操作2 SparseMatrix<T> operator+(const SparseMatrix<T>& sp) { assert(_row == sp._row && _col == sp._col);//檢測兩個相加的矩陣行列是否相等 SparseMatrix<T> 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<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data)); iLidx++; } else if(AddrLeft > AddrRight) { ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data)); iRidx++; } else//當左邊等于右邊判斷相加后和是否為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;//無效值 }; 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<<"訪問三行四列元素"<<endl; cout<<s.Acess(3,4)<<endl; cout<<s<<endl; cout<<"快速轉置"<<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; } 運行結果截圖：
在上面的代碼中用到C++模板、標準庫中vector容器，以及迭代器實現了一些基本的操作，如訪問稀疏矩陣中某個元素，輸出稀疏矩陣、稀疏矩陣的轉置以及快速轉置還有兩個稀疏矩陣的加法。
快速轉置操作的基本思路是：
（1）統計原矩陣中每一列有多少個有效元素；
（2）原矩陣中每一列在新矩陣中的起始地址；
（3）放置元素到新空間中。
還需注意的是，在我們打印這個稀疏矩陣時雖然也可以直接調用訪問元素的Acess接口，但是每次進去之后都得遍歷一遍，時間復雜度較高，所以我們不采取這種辦法，而是比較當前行列的值，若相等輸出有效元素，不等則輸出無效元素0。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
圖片精選
