稀疏矩陣的列序遞增法和一次定位快速轉(zhuǎn)置法

稀疏矩陣：矩陣中大多數(shù)元素為0的矩陣，從直觀上講，當(dāng)非零元素個(gè)數(shù)低于總元素的30%時(shí)，這樣的矩陣為稀疏矩陣。

如：

int array [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}};

稀疏矩陣的壓縮存儲(chǔ)：使用{row,col,value}三元組存儲(chǔ)每一個(gè)有效數(shù)據(jù)，三元組按原矩陣中的位置，以行優(yōu)先級(jí)先后順序依次存放。

矩陣的轉(zhuǎn)置：將原矩陣的行、列對(duì)換，也就是將[i][j]和[j][i]位置上的數(shù)據(jù)對(duì)換。

稀疏矩陣的列序遞增法：

    按照被轉(zhuǎn)置矩陣三元組表A的序列（即轉(zhuǎn)置后三元組表B的行序）遞增的順序進(jìn)行轉(zhuǎn)置，則轉(zhuǎn)置后矩陣的三元組表B恰好是以“行序?yàn)橹餍虻摹?

一次定位快速轉(zhuǎn)置法：

    在列轉(zhuǎn)置中算法的時(shí)間浪費(fèi)主要在雙重循環(huán)中，要改善算法的性能，必須去掉雙重循環(huán)，使得整個(gè)轉(zhuǎn)置過程通過一次循環(huán)來完成。

為了使得被轉(zhuǎn)置的三元組表A中元素一次定位到三元組表B中，需要計(jì)算一下以下數(shù)據(jù)：

1）RowCounts,三元組表A中每一列有效值的個(gè)數(shù)，即轉(zhuǎn)置后矩陣三元組表B中每一行有效值的個(gè)數(shù)。

2）RowStart,三元組表B中每一行有效值的起始位置。

RowStart[i] = RowStart[i - 1] + RowCounts[i - 1];

代碼實(shí)現(xiàn)：

#include <iostream>

using namespace std;

#include <vector>//動(dòng)態(tài)數(shù)組

//三元組

template<class T>

struct Triple

{

size_t _row;

size_t _col;

T _value;

Triple(size_t row = 0, size_t col = 0, const T& value = T())

:_row(row)

, _col(col)

, _value(value)

{}

};

template<class T>

class SparseMatrix

{

public://invalid   非零值

SparseMatrix(T* a = NULL, size_t M = 0, size_t N = 0, const T& invalid = T())

:_rowSize(M)

, _colSize(N)

, _invalid(invalid)

{

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

{

for (size_t j = 0; j < N; ++j)

{

if (a[i*N + j] != _invalid)//每行元素個(gè)數(shù)就是列的個(gè)數(shù)

{

Triple<T> t;

t._row = i;

t._col = j;

t._value = a[i*N + j];

_a.push_back(t);//在Vector類，插入一個(gè)元素

}

}

}

}

void Display()

{

size_t index = 0;

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

{

for (size_t j = 0; j < _colSize; ++j)

{

if (index < _a.size()&& (_a[index]._row == i)&& (_a[index]._col == j))

{

cout << _a[index++]._value << " ";

}

else

{

cout << _invalid << " ";

}

}

cout << endl;

}

}

//矩陣列序遞增轉(zhuǎn)置算法，時(shí)間復(fù)雜度為O(有效數(shù)據(jù)的個(gè)數(shù)*原矩陣的列數(shù))

SparseMatrix<T> Transport()

{

SparseMatrix<T> sm;

sm._colSize = _rowSize;

sm._rowSize = _colSize;

sm._invalid = _invalid;

for (size_t i = 0; i < _colSize; ++i)//列序遞增

{

size_t index = 0;

while (index < _a.size())

{

if (_a[index]._col == i)

{

Triple<T> t;

t._row = _a[index]._col;

t._col = _a[index]._row;

t._value = _a[index]._value;

sm._a.push_back(t);

}

++index;

}

}

return sm;

}

//一次定位計(jì)數(shù)快速轉(zhuǎn)置 時(shí)間復(fù)雜度為O(有效數(shù)據(jù)的個(gè)數(shù)+原矩陣的列數(shù))

SparseMatrix<T> FastTransport()

{

SparseMatrix<T> sm;

sm._rowSize = _colSize;

sm._colSize = _rowSize;

sm._invalid = _invalid;

int* RowCounts = new int[_colSize];//計(jì)數(shù)

int* RowStart = new int[_colSize];//位置

memset(RowCounts, 0, sizeof(int)*_colSize);

memset(RowStart, 0, sizeof(int)*_colSize);

size_t index = 0;//index  非零元素

while (index < _a.size())

{

++RowCounts[_a[index]._col];

++index;

}

for (size_t i = 1; i < _colSize; ++i)

{

RowStart[i] = RowStart[i - 1] + RowCounts[i - 1];

}

index = 0;

sm._a.resize(_a.size());

while (index < sm._a.size())

{

Triple<T> t;

t._row = _a[index]._col;

t._col = _a[index]._row;

t._value = _a[index]._value;

sm._a[RowStart[_a[index]._col]] = t;

++RowStart[_a[index]._col];

++index;

}

delete[] RowCounts;

delete[] RowStart;

return sm;

}

protected:

vector<Triple<T>> _a;

size_t _rowSize;

size_t _colSize;

T _invalid;

};

void Test()

{

int array[5][4] =

{

{ 1, 0, 3, 0 },

{ 0, 0, 0, 0 },

{ 0, 0, 0, 0 },

{ 2, 0, 4, 5 },

{ 0, 0, 0, 0 },

};

SparseMatrix<int> sm1((int*)array, 5, 4, 0);

cout << "打印原矩陣："<<endl;

sm1.Display();

cout << endl;

cout << "打印轉(zhuǎn)置后的矩陣：" << endl;

SparseMatrix<int> sm2 = sm1.Transport();

/*SparseMatrix<int> sm2 = sm1.FastTransport();*/

sm2.Display();

}

int main()

{

Test();

system("pause");

return 0;

}

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

打印原矩陣：

1 0 3 0

0 0 0 0

0 0 0 0

2 0 4 5

0 0 0 0

打印轉(zhuǎn)置后的矩陣：

1 0 0 2 0

0 0 0 0 0

3 0 0 4 0

0 0 0 5 0

請(qǐng)按任意鍵繼續(xù). . .

兩種算法比較：

    假設(shè)有效數(shù)據(jù)的個(gè)數(shù)為100，原矩陣的列數(shù)為100，矩陣列序遞增轉(zhuǎn)置算法，時(shí)間耗費(fèi)為O(有效數(shù)據(jù)的個(gè)數(shù)*原矩陣的列數(shù))，即100*100=10000次；一次定位計(jì)數(shù)快速轉(zhuǎn)置算法，時(shí)間復(fù)雜度為O(有效數(shù)據(jù)的個(gè)數(shù)+原矩陣的列數(shù))，即100+100=200次左右。顯然一次定位計(jì)數(shù)快速轉(zhuǎn)置算法的時(shí)間效率要高的多，在時(shí)間性能上優(yōu)于列序遞增轉(zhuǎn)置法，但是在空間耗費(fèi)上增加了兩個(gè)輔助向量空間,即RowCounts和RowStart,由此可見，算法在時(shí)間上的節(jié)省是以更多的存儲(chǔ)空間為代價(jià)的。