稀疏矩陣的通路、普通逆置和快速逆置、還原輸出以及加法

　　首先稀疏矩陣的概念：

　　在一個矩陣中（并不要求為方陣）無效元素的個數遠遠大于有效元素的個數，我們稱之為——稀疏矩陣。一般沒有一個明确的界限分開稀疏矩陣和普通矩陣，不過一些人認為：有效元素的個數/無效元素的個數<0.05即可稱之為稀疏矩陣。

　　跟對稱矩陣壓縮存儲的邏輯相似：我們隻需存儲稀疏矩陣的有限元素就行，但有效元素的位置并沒有什麼規律，是以在存儲時還要存儲相應元素的行、列的下标。

　　可以用結構體實作：

template<class T>
    struct Trituple
    {
        Trituple(size_t row, size_t col, const T& data)
        : _row(row)
        , _col(col)
        , _data(data)
        {}

        Trituple()
        {}

        size_t _row;
        size_t _col;
        T _data;
    };

　　則類中稀疏矩陣的成員應為：

private:
    vector<Trituple<T>> _pData;
    size_t _row;
    size_t _col;
    T _invalid;//無效元素的值

　　構造函數的實作很簡單，我們隻需要周遊一下這個矩陣，将不為無效值的元素的值、行和列存儲就行。這裡采用的方法也是講二位數組轉為一維數組進行通路。

SparseMatrix(int* array, size_t row, size_t col, const T& invalid)
        : _row(row)
        , _col(col)
        , _invalid(invalid)
    {
        for (size_t i = ; i < _row; i++)
        {
            for (size_t j = ; j < _col; j++)
            {
                if (array[i*_col + j] != _invalid)
                    _pData.push_back(Trituple<T>(i, j, array[i*_col + j]));
            }
        }
    }

　　稀疏矩陣的通路：

　　隻需判斷需要通路的行、列在壓縮儲存的一維數組中有沒有對應的元素，如果有，則輸出該值；如果沒有，則輸出無效值。

T& Access(int row, int col)
    {
        for (size_t i = ; i < _pData.size();++i)
        {
            if (_pData[i]._row == row&&_pData[i]._col == col)
                return _pData[i]._data;
        }
        return _invalid;
    }

　　稀疏矩陣的還原輸出：

　　同樣，我們隻需判斷要通路的位置是否存在有效元素，有則輸出，無則輸出無效元素。此時我們最好不要直接通路Acess()函數，這樣的話開銷太大，時間複雜度過高，不是一個優秀的代碼。是以我們使用vector中的疊代器通路被壓縮存儲的每一個元素。或者每次進入之後判斷行、列的關系。

template<class T>
    friend ostream& operator<<(ostream& os, SparseMatrix<T>& s)
    {
        size_t index = ; 
        for (size_t i = ; i < s._row; ++i)
        {
            for (size_t j = ; j < s._col; ++j)
            {
                if ((index < s._pData.size()) && (s._pData[index]._row == i) && (s._pData[index]._col == j))
                //注意：index<s._pData.size()是為了index通路不越界。
                    os << setw() << s._pData[index++]._data << " ";
                else
                    os << setw() << s._invalid << " ";
            }
            os << endl;
        }
        return os;
    }

　　稀疏矩陣的普通逆置：

　　按列通路，每一次進入之後判斷壓縮存儲的一維數組中是否有對應列的元素，有的話，輸出到新空間，并且向後移動。

SparseMatrix<T> Transprot()
    {
        SparseMatrix<T> temp;
        temp._row = _col;
        temp._col = _row;
        for (size_t i = ; i < _col;i++)
        {
            vector<Trituple<T>>::iterator it = _pData.begin();
            while (it != _pData.end())
            {
                if (it->_col == i)//判斷列
                {
                    temp._pData.push_back(Trituple<T>(i, it->_row, it->_data));//輸入時交換行、列
                }
                it++;
            }
        }
        return temp;
    }

　　稀疏矩陣的快速逆置：

　　快速逆置的實作是直接将壓縮存儲中的一維數組的元素的排列方式變成逆置後的樣子，這樣說起來可能有點生硬，看圖：

稀疏矩陣的通路、普通逆置和快速逆置、還原輸出以及加法

　　首先，按列通路，統計該列是否有有限元素存在，如果有，給對應的列的數組下邊的值加一

int* _pCount=new int[_col];//最多有_col列
_pCount[it->_col]++;//此時it表示有限元素的疊代器，it->_col表示它的列。

具體代碼：

int* _pCount = new int[_col];
        memset(_pCount, , _col*sizeof(_pCount[]));
        for (size_t i = ; i < _col; i++)/*按列通路，每列中有多少個有效元素，
                                              本數組中，有5列，從下标為0的第一列開始計*/
        {                                                     
            vector<Trituple<T>>::iterator it = _pData.begin();/*每次進來it從_pData的開始走，判斷pData
                                                              中的元素有沒有列和判斷的列相同的，如果有，則證明：
                                                              _pData在檢測的目前列中存在有效元素，給有效元素的下标位置的_pCount
                                                              加1，因為數組有多行，每一列的元素不止一個，每一列可能有多個有效元素
                                                              ，是以要使用it周遊_pData。*/
            while (it != _pData.end())
            {
                if (it->_col == i)/*it代表_pData的目前元素的指針，當其列==檢測列時*/
                    _pCount[it->_col]++;/*給_pCount中it代表的數的下标位置加一，剛好_pCount的下标與有效元素的列相對應*/
                it++;
            }

        }

　　我們還應該儲存每個有效元素的起始位置，因為原矩陣的列轉置後就變成了新矩陣的行，是以我們隻需儲存原矩陣中每個有效元素的起始列就行。且第一列的起始位址始終未0，下一列的起始位址等于上一列的起始位址+上一列的有效元素的個數。

int* _pAddar = new int[_col];
        memset(_pAddar, , _col*sizeof(_pAddar[]));/*置0時，因為第一行的起始位址為0，第一列的起始位址就已經置為0*/
        for (size_t i = ; i < _col; i++)//是以從1開始
        {
            _pAddar[i] = _pAddar[i - ] + _pCount[i - ];
        }

　　放置有效元素到新空間–>“逆置”_pData

　　如果不懂的話仔細看代碼中的注釋。

for (size_t i = ; i < _pData.size(); i++)
        {

            temp._pData[_pAddar[_pData[i]._col]] = Trituple<T>(_pData[i]._col, _pData[i]._row, _pData[i]._data);
            /*_pAddar[_pData[i]._col]：
            _pAddar儲存的是新數組中有效元素的起始位置，也是原壓縮數組有效元素的列的起始位置
            是以原數組第i個元素的列的位置就是新數組有效元素的行的起始位置
            也就是第i個元素在新數組中的行的起始位置
            是以将原數組的有效元素放置到新數組其對應的行的起始位置
            且存儲的時候将該元素的行列交換*/
            _pAddar[_pData[i]._col]++;
            /*放置完後，再給新數組的行的起始位置加一，因為目前行已經有一個元素存入，
            它的起始位置應該向後移動一位
            按行優先級通路，該行下一個元素在該元素的下個位置*/

        }

　　兩個同行同列的矩陣的相加其實就如：兩個有序單連結清單合并後依然有序的算法一樣。

　　将同行同列的元素相加，并push入對象中，但注意：如果加起來為無效值的話則略過不計；如果行、列值不等，則push小的那個。結束循環的條件為：任何一個已經周遊完畢（雖然同行同列，但是有效元素的數目不一定相同）。然後将未周遊完的矩陣的有限元素直接push入就可。

SparseMatrix<T> operator+(const SparseMatrix<T>& sp)
    {
        SparseMatrix<T> temp;
        temp._row = _row;
        temp._col = _col;
        size_t i = , j = ;
        size_t Size1 = _pData.size();
        size_t Size2 = sp._pData.size();
        while (i < Size1 && j < Size2)
        {
            if ((_pData[i]._row == sp._pData[j]._row) && (_pData[i]._col == sp._pData[j]._col))
            {
                if (_pData[i]._data + sp._pData[i]._data!=_invalid)
                    temp._pData.push_back((Trituple<T>(_pData[i]._row, _pData[i]._col, _pData[i]._data + sp._pData[j]._data)));
                i++; j++;
            }
            else if ((_pData[i]._row > sp._pData[j]._row) || (_pData[i]._col > sp._pData[j]._col))
            {
                temp._pData.push_back(sp._pData[j]);
                j++;
            }
            else if ((_pData[i]._row < sp._pData[j]._row) || (_pData[i]._col < sp._pData[j]._col))
            {
                temp._pData.push_back(_pData[i]);
                i++;
            }
        }
        if (i >= Size1)
        {
            for (; j < Size2; j++)
                temp._pData.push_back(sp._pData[j]);
        }
        if (j >= Size2)
        {
            for (; i < Size1; i++)
                temp._pData.push_back(_pData[i]);
        }
        return temp;
    }

　　關于稀疏矩陣的所有代碼以及測試用例如下：

#include <vector>
#include <iomanip>
#include <iostream>
using namespace std;

template<class T>
class SparseMatrix
{
    template<class T>
    struct Trituple
    {
        Trituple(size_t row, size_t col, const T& data)
        : _row(row)
        , _col(col)
        , _data(data)
        {}

        Trituple()
        {}

        size_t _row;
        size_t _col;
        T _data;
    };

public:

    // 稀疏矩陣的壓縮存儲
    SparseMatrix(int* array, size_t row, size_t col, const T& invalid)
        : _row(row)
        , _col(col)
        , _invalid(invalid)
    {
        for (size_t i = ; i < _row; i++)
        {
            for (size_t j = ; j < _col; j++)
            {
                if (array[i*_col + j] != _invalid)
                    _pData.push_back(Trituple<T>(i, j, array[i*_col + j]));
            }
        }
    }

    SparseMatrix()
    {}

    // 通路稀疏矩陣中row行col中的元素
    T& Access(int row, int col)
    {
        for (size_t i = ; i < _pData.size();++i)
        {
            if (_pData[i]._row == row&&_pData[i]._col == col)
                return _pData[i]._data;
        }
        return _invalid;
    }

    // 稀疏矩陣的逆置
    SparseMatrix<T> Transprot()
    {
        SparseMatrix<T> temp;
        temp._row = _col;
        temp._col = _row;
        for (size_t i = ; i < _col;i++)
        {
            vector<Trituple<T>>::iterator it = _pData.begin();
            while (it != _pData.end())
            {
                if (it->_col == i)
                {
                    temp._pData.push_back(Trituple<T>(i, it->_row, it->_data));
                }
                it++;
            }
        }
        return temp;
    }

    // 稀疏矩陣的快速逆置
    SparseMatrix<T> FastTransprot()
    {
        SparseMatrix<T> temp;
        temp._row = _col;
        temp._col = _row;
        for (size_t i = ; i < _pData.size(); i++)
            temp._pData.push_back(Trituple<T>());

        //統計每列中有效元素的個數
        int* _pCount = new int[_col];
        memset(_pCount, , _col*sizeof(_pCount[]));
        for (size_t i = ; i < _col; i++)/*按列通路，每列中有多少個有效元素*/
        {                                                     
            vector<Trituple<T>>::iterator it = _pData.begin();/*每次進來it從_pData的開始走，判斷pData
                                                              中的元素有沒有列和判斷的列相同的，如果有，則證明：
                                                              _pData在檢測的目前列中存在有效元素，給有效元素的下标位置的_pCount
                                                              加1，因為數組有多行，每一列的元素不止一個，每一列可能有多個有效元素
                                                              ，是以要使用it周遊_pData。*/
            while (it != _pData.end())
            {
                if (it->_col == i)/*it代表_pData的目前元素的指針，當其列==檢測列時*/
                    _pCount[it->_col]++;/*給_pCount中it代表的數的下标位置加一，剛好_pCount的下标與有效元素的列相對應*/
                it++;
            }

        }

        //用數組儲存每列元素在新矩陣中的起始位址
        int* _pAddar = new int[_col];
        memset(_pAddar, , _col*sizeof(_pAddar[]));/*置0時，因為第一行的起始位址為0，第一列的起始位址就已經置為0*/
        for (size_t i = ; i < _col; i++)//是以從1開始
        {
            _pAddar[i] = _pAddar[i - ] + _pCount[i - ];
        }

        //放置有效元素到新空間-->“逆置”_pData
        for (size_t i = ; i < _pData.size(); i++)
        {


            temp._pData[_pAddar[_pData[i]._col]] = Trituple<T>(_pData[i]._col, _pData[i]._row, _pData[i]._data);
            /*_pAddar[_pData[i]._col]：
            _pAddar儲存的是新數組中有效元素的起始位置，也是原壓縮數組有效元素的列的起始位置
            是以原數組第i個元素的列的位置就是新數組有效元素的行的起始位置
            也就是第i個元素在新數組中的行的起始位置
            是以将原數組的有效元素放置到新數組其對應的行的起始位置
            且存儲的時候将該元素的行列交換*/
            _pAddar[_pData[i]._col]++;
            /*放置完後，再給新數組的行的起始位置加一，因為目前行已經有一個元素存入，
            它的起始位置應該向後移動一位
            按行優先級通路，該行下一個元素在該元素的下個位置*/

        }

        return temp;
    }

    // 實作稀疏矩陣的加法操作
    SparseMatrix<T> operator+(const SparseMatrix<T>& sp)
    {
        SparseMatrix<T> temp;
        temp._row = _row;
        temp._col = _col;
        size_t i = , j = ;
        size_t Size1 = _pData.size();
        size_t Size2 = sp._pData.size();
        while (i < Size1 && j < Size2)
        {
            if ((_pData[i]._row == sp._pData[j]._row) && (_pData[i]._col == sp._pData[j]._col))
            {
                if (_pData[i]._data + sp._pData[i]._data!=_invalid)
                    temp._pData.push_back((Trituple<T>(_pData[i]._row, _pData[i]._col, _pData[i]._data + sp._pData[j]._data)));
                i++; j++;
            }
            else if ((_pData[i]._row > sp._pData[j]._row) || (_pData[i]._col > sp._pData[j]._col))
            {
                temp._pData.push_back(sp._pData[j]);
                j++;
            }
            else if ((_pData[i]._row < sp._pData[j]._row) || (_pData[i]._col < sp._pData[j]._col))
            {
                temp._pData.push_back(_pData[i]);
                i++;
            }
        }
        if (i >= Size1)
        {
            for (; j < Size2; j++)
                temp._pData.push_back(sp._pData[j]);
        }
        if (j >= Size2)
        {
            for (; i < Size1; i++)
                temp._pData.push_back(_pData[i]);
        }
        return temp;
    }

    // 還原稀疏矩陣
    template<class T>
    friend ostream& operator<<(ostream& os, SparseMatrix<T>& s)
    {
        size_t index = ; 
        for (size_t i = ; i < s._row; ++i)
        {
            for (size_t j = ; j < s._col; ++j)
            {
                if ((index < s._pData.size()) && (s._pData[index]._row == i) && (s._pData[index]._col == j))
                    os << setw() << s._pData[index++]._data << " ";
                else
                    os << setw() << s._invalid << " ";
            }
            os << endl;
        }
        return os;
    }

private:
    vector<Trituple<T>> _pData;
    size_t _row;
    size_t _col;
    T _invalid;
};

int main()
{
    int array[][] = {
        { , , , ,  },
        { , , , ,  },
        { , , , ,  },
        { , , , ,  },
        { , , , ,  },
        { , , , ,  } };
    int array1[][] = {
        { , , , ,  },
        { , , , ,  },
        { , , , ,  },
        { , , , ,  },
        { , , , ,  },
        { , , , ,  } };
    SparseMatrix<int> sp((int*)array, , , );
    cout << sp << endl;

    cout << sp.Transprot() << endl;

    cout << sp.FastTransprot() << endl;

    SparseMatrix<int> sp1((int*)array1, , , );
    SparseMatrix<int> sp2 = sp + sp1;
    cout << sp2 << endl;
    system("pause");
    return ;
}

　　如有問題，敬請指出。

稀疏矩陣的通路、普通逆置和快速逆置、還原輸出以及加法

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器