對(duì)稱矩陣及稀疏矩陣的壓縮存儲(chǔ)
創(chuàng)新互聯(lián)公司是一家專業(yè)提供五龍口企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、H5開發(fā)、小程序制作等業(yè)務(wù)。10年已為五龍口眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)絡(luò)公司優(yōu)惠進(jìn)行中。
1.稀疏矩陣
對(duì)于那些零元素?cái)?shù)目遠(yuǎn)遠(yuǎn)多于非零元素?cái)?shù)目，并且非零元素的分布沒有規(guī)律的矩陣稱為稀疏矩陣（sparse）。
人們無(wú)法給出稀疏矩陣的確切定義，一般都只是憑個(gè)人的直覺來(lái)理解這個(gè)概念，即矩陣中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，并且非零元素沒有分布規(guī)律。
實(shí)現(xiàn)代碼：
//稀疏矩陣及其壓縮存儲(chǔ)
#pragma once
#include
#include
using namespace std;
template
struct Triple
{
size_t _r;
size_t _c;
T _value;
Triple(size_t row = 0, size_t col = 0, const T& value = T())
:_r(row)
,_c(col)
,_value(value)
{}
};
template
class SparseMatrix
{
public:
SparseMatrix()
:_row(0)
,_col(0)
,_illegal(T())
{}
SparseMatrix(T* arr, size_t row, size_t col, const T& illegal)
:_row(row)
,_col(col)
,_illegal(illegal)
{
for(size_t i = 0; i t(i,j,arr[i*col+j]);
_matrix.push_back(t);
}
}
}
}
void Display()
{
vector >::iterator iter;
iter = _matrix.begin();
for(size_t i = 0; i<_row; ++i)
{
for(size_t j = 0; j<_col; ++j)
{
if(iter!=_matrix.end()
&&iter->_r == i
&&iter->_c == j)
{
cout << iter->_value <<" ";
++iter;
}
else
{
cout << _illegal <<" ";
}
}
cout << endl;
}
cout << endl;
}
//普通轉(zhuǎn)置(行優(yōu)先存儲(chǔ))
//列變行，從0列開始，將列數(shù)據(jù)一個(gè)一個(gè)放進(jìn)轉(zhuǎn)置矩陣
SparseMatrix Transpose()
{
SparseMatrix tm;
tm._row = _col;
tm._col = _row;
tm._illegal = _illegal;
tm._matrix.reserve(_matrix.size());
for(size_t i = 0; i<_col; ++i)
{
size_t index = 0;
while(index < _matrix.size())
{
if(_matrix[index]._c == i)
{
Triple t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value);
tm._matrix.push_back(t);
}
++index;
}
}
return tm;
}
SparseMatrix FastTranspose()
{
SparseMatrix tm;
tm._row = _col;
tm._col = _row;
tm._illegal = _illegal;
tm._matrix.resize(_matrix.size());
int* count = new int[_col];//記錄每行的元素個(gè)數(shù)
memset(count, 0, sizeof(int)*_col);
int* start = new int[_col];//轉(zhuǎn)置矩陣中元素的位置
start[0] = 0;
size_t index = 0;
while(index < _matrix.size())
{
count[_matrix[index]._c]++;
++index;
}
for(size_t i=1; i<_col; ++i)
{
start[i] = start[i-1] + count[i-1];
}
index = 0;
while(index < _matrix.size())
{
Triple t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value);
tm._matrix[start[_matrix[index]._c]++] = t; //核心代碼
++index;
}
delete[] count;
delete[] start;
return tm;
}
protected:
vector > _matrix;
size_t _row;
size_t _col;
T _illegal;
};
2.對(duì)稱矩陣
實(shí)現(xiàn)代碼：
//對(duì)稱矩陣及其壓縮存儲(chǔ)
#pragma once
#include
using namespace std;
template
class SymmetricMatrix
{
public:
SymmetricMatrix(T* arr, size_t n)
:_n(n)
,_matrix(new T[n*(n+1)/2])
{
size_t index = 0;
for(size_t i = 0; i= j)
{
_matrix[index] = arr[i*n+j];
++index;
}
else
{
continue;
}
}
}
}
void Display()
{
for(size_t i =0; i < _n; ++i)
{
for(size_t j = 0; j < _n; ++j)
{
/* if(i
以上就是C++ 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)稀疏矩陣與對(duì)稱矩陣，如有疑問請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
網(wǎng)頁(yè)標(biāo)題：C++數(shù)據(jù)結(jié)構(gòu)之對(duì)稱矩陣及稀疏矩陣的壓縮存儲(chǔ)
地址分享：
http://weahome.cn/article/gpjjcd.html
重慶分公司
重慶分公司
