稀疏矩阵模板

Posted by Harid2011 - Mar - 29 留个言

稀疏矩阵就是一个包含大量零元素的矩阵,具体零元素在矩阵中占多大的比例并没有明确的界定,所以稀疏矩阵也只是一个意识形态上的概念。但是,稀疏矩阵的实际应用意义很大。例如,建立计算机网络时,用999条线路把1000个站点连接起来,用以表示这个网络的连接矩阵有1000×1000个矩阵元素,其中只有1998个非零元素,却有998002个零元素。显然,把所有的零元素都存在计算机中是不经济的,所以必须考虑对稀疏矩阵的压缩存储表示。

一种比较常用的表示稀疏矩阵的方法是用三元组表。每一个三元组为<row, cloumn, value>,它能唯一确定一个矩阵元素。

下面是一个比较蛋疼的C++稀疏矩阵模板类:

#ifndef SPARSEMATRIX_H_
#define SPARSEMATRIX_H_
#include 
template  class SparseMatrix;
template  std::ostream & operator<< (std::ostream & out, const SparseMatrix & instance);
template 
class SparseMatrix{
private:
    int mRows;    // 矩阵的行
    int mCols;   //  矩阵的列
    int mItems;   // 矩阵中非零数的个数
    struct Trituple{
        int row;   // 记录某个矩阵元素所在的行
        int col;   //  记录某个矩阵元素所在的列
        Type value; // 记录某个矩阵元素的值
        Trituple* next;
        Trituple() : row(0), col(0), value(0), next(0){};
    } * smArray; // 存储所有三元组的链表
protected:
    void getMatrix(); // 获得三元组的输入
    Type find(int row, int col)const; // 在三元组表中查找某一个矩阵元素(此函数未优化)
public:
    SparseMatrix();
    ~SparseMatrix();
    SparseMatrix(int rows, int cols);
    SparseMatrix(SparseMatrix &); //Copy constructor.
    SparseMatrix transpose(); // Matrix thranspose.
    SparseMatrix add(SparseMatrix & b); //(*this) + b.
    SparseMatrix multiply(SparseMatrix & b); //(*this) * b.
    int getRows()const{
        return this->mRows; }
    int getCols()const{
        return this->mCols; }
    int getItems()const{
        return this->mItems; }
    Trituple * getArray()const{
        return this->smArray; }
    friend std::ostream & operator<< (std::ostream & out, const SparseMatrix & instance);
};
// End of class statement.
template
SparseMatrix::SparseMatrix(){
    this->mRows = 0;
    this->mCols = 0;
    this->mItems = 0;
    this->smArray = 0;
}
template 
SparseMatrix::SparseMatrix(int rows, int cols){
    this->mRows = rows;
    this->mCols = cols;
    this->getMatrix();
}
template 
SparseMatrix::SparseMatrix(SparseMatrix & source){
    this->mRows = source.getRows();
    this->mCols = source.getCols();
    this->mItems = source.getItems();
    Trituple* create = 0;
    Trituple* last =  0;
    for(int j=0; jgetItems(); j++){
        create = new Trituple;
        if(j == 0)
            this->smArray = create;
        else
            last->next = create;
        last = create;
    }
    Trituple* tempD = this->getArray();
    Trituple* tempS = source.getArray();
    for(int i=0; igetItems(); i++){
        tempD->row = tempS->row;
        tempD->col = tempS->col;
        tempD->value = tempS->value;
        tempD = tempD->next;
        tempS = tempS->next;
    }
}
template 
SparseMatrix  SparseMatrix:: transpose(){
    SparseMatrix b;
    b.mRows = this->getCols();
    b.mCols = this->getRows();
    b.mItems = this->getItems();
    Trituple* create = 0;
    Trituple* last =  0;
    for(int j=0; jnext = create;
            last = create;
        }
    }
    Trituple* temp1 = this->getArray();
    Trituple* temp2 = b.getArray();
    if(this->mItems > 0){
        for(int k=0; kgetCols(); k++){
            for(int i=0;igetItems();i++){
                if(temp1->col == k){
                    temp2->row = k;
                    temp2->col = temp1->row;
                    temp2->value = temp1->value;
                    temp2 = temp2->next;
                }
                temp1 = temp1->next;
            }
            temp1 = this->getArray();
        }
    }
    return b;
}
template 
SparseMatrix SparseMatrix::add(SparseMatrix & b){
    if(this->getRows() != b.getRows()){
        std::cerr<<" Illegal addition! Quit now."< result;
    result.mCols = b.getCols();
    result.mRows = b.getRows();
    Trituple* tempA = this->getArray();
    Trituple* tempB = b.getArray();
    Trituple* tempR = 0;
    Trituple* last = 0;
    int countA = this->getItems();
    int countB = b.getItems();
    int countR = 0;
    while(1){
        if(countA != 0 || countB != 0){
            if(countA != 0 && countB != 0){
                if(tempA->row < tempB->row){
                    tempR = new Trituple;
                    countR++;
                    if(result.getArray() == 0)
                        result.smArray = tempR;
                    else
                        last->next = tempR;
                    last = tempR;
                    tempR->col = tempA->col;
                    tempR->row = tempA->row;
                    tempR->value = tempA->value;
                    tempA = tempA->next;
                    countA--;
                }
                else if(tempA->row == tempB->row){
                    if(tempA->col < tempB->col){
                        tempR = new Trituple;
                        countR++;
                        if(result.getArray() == 0)
                            result.smArray = tempR;
                        else
                            last->next = tempR;
                        last = tempR;
                        tempR->col = tempA->col;
                        tempR->row = tempA->row;
                        tempR->value = tempA->value;
                        tempA = tempA->next;
                        countA--;
                    }
                    else if(tempA->col == tempB->col){
                        if((tempA->value + tempB->value) != 0){
                        tempR = new Trituple;
                        countR++;
                        if(result.getArray() == 0)
                            result.smArray = tempR;
                        else
                            last->next = tempR;
                        last = tempR;
                        tempR->col = tempA->col;
                        tempR->row = tempA->row;
                        tempR->value = tempA->value + tempB->value;
                        tempA = tempA->next;
                        tempB = tempB->next;
                        countA--;
                        countB--;
                        }
                        else if((tempA->value + tempB->value) == 0){
                            tempA = tempA->next;
                            tempB = tempB->next;
                            countA--;
                            countB--;
                        }
                    }
                    else if(tempA->col > tempB->col){
                        tempR = new Trituple;
                        countR++;
                        if(result.getArray() == 0)
                            result.smArray = tempR;
                        else
                            last->next = tempR;
                        last = tempR;
                        tempR->col = tempB->col;
                        tempR->row = tempB->row;
                        tempR->value = tempB->value;
                        tempB = tempB->next;
                        countB--;
                    }
                }
                else if(tempA->row > tempB->row){
                    tempR = new Trituple;
                    countR++;
                    if(result.getArray() == 0)
                        result.smArray = tempR;
                    else
                        last->next = tempR;
                    last = tempR;
                    tempR->col = tempB->col;
                    tempR->row = tempB->row;
                    tempR->value = tempB->value;
                    tempB = tempB->next;
                    countB--;
                }
            }
            else if(countA == 0){
                tempR = new Trituple;
                countR++;
                if(result.getArray() == 0)
                    result.smArray = tempR;
                else
                    last->next = tempR;
                last = tempR;
                tempR->col = tempB->col;
                tempR->row = tempB->row;
                tempR->value = tempB->value;
                tempB = tempB->next;
                countB--;
            }
            else if(countB == 0){
                tempR = new Trituple;
                countR++;
                if(result.getArray() == 0)
                    result.smArray = tempR;
                else
                    last->next = tempR;
                last = tempR;
                tempR->col = tempA->col;
                tempR->row = tempA->row;
                tempR->value = tempA->value;
                tempA = tempA->next;
                countA--;
            }
        }
        else{
            break;
        }
    }
    result.mItems = countR;
    return result;
}
template 
SparseMatrix SparseMatrix::multiply(SparseMatrix & b){
    if(this->getCols() != b.getRows()){
        std::cerr<<" Illegal addition! Quit now."< result;
    result.mRows = this->mRows;
    result.mCols = b.mCols;
    Type temp = 0;
    Type tempA, tempB;
    Trituple* tempResult = 0;
    Trituple* last = 0;
    int count = 0;
    for(int i=0; igetRows(); i++){
        for(int j=0; jgetCols(); k++){
                tempA = this->find(i, k);
                if(tempA != 0){
                    tempB = b.find(k, j);
                    temp += tempA * tempB;
                }
            }
            if(temp != 0){
                tempResult = new Trituple;
                count++;
                if(result.getArray() == 0)
                    result.smArray = tempResult;
                else
                    last->next = tempResult;
                last = tempResult;
                tempResult->row = i;
                tempResult->col = j;
                tempResult->value = temp;
                temp = 0;
            }
        }
    }
    result.mItems = count;
    return result;
}
template 
void SparseMatrix::getMatrix(){
    using namespace std;
    Trituple* temp = 0;
    Trituple* last = 0;
    cout <<"\n一共有多少个非零值?\n";
    cin>>this->mItems;
    cout <<"\n按如下方式每次输入一个非空三元组: \n\tRow\tColumn\tValue\n\t0  \t0  \t10\n\n";
    for(int i=0; igetItems(); i++){
        temp = new Trituple;
        if(i == 0)
            this->smArray = temp;
        else
            last->next = temp;
        last = temp;
        cout <<"第"<< i+1<<"组: ";
        cin>>temp->row >>temp->col >> temp->value;
    }
}
template 
Type SparseMatrix::find(int row, int col)const{
    Trituple* pt = this->getArray();
    for(int i=0; igetItems(); i++){
        if(pt->row == row && pt->col == col){
            return pt->value;
        }
        else
            pt = pt->next;
    }
    return 0;
}
template 
std::ostream & operator<< (std::ostream & out, const SparseMatrix & instance){
    using namespace std;
    out <<"The matrix is as follows:\n";
    Type temp = 0;
    for(int i=0; i
SparseMatrix::~SparseMatrix(){
    delete [] smArray;
}
#endif

如果您有更好的代码,敬请分享!

   声明:本文采用 BY-NC-SA 协议进行授权 | 星期九
   原创文章转载请注明:转自《稀疏矩阵模板

Comments(16) Leave comments
  1. Gravatar
    Roowe Mozilla Firefox Mozilla Firefox 4.0 Linux Linux
    四月 6th, 2011 at 01:29  | #1

    😈 没有高亮的代码很蛋疼呀

    • Gravatar Harid  @  四月 6th, 2011 at 09:16 replied.

      @Roowe, 不仅代码让人蛋疼,还把页面也弄坏了。这两天在调整博客。

    • Gravatar Harid  @  四月 6th, 2011 at 13:04 replied.

      @Roowe, 现在再看看这代码效果,怎么样? 🙂

  2. Gravatar
    云侃 Mozilla Firefox Mozilla Firefox 4.0 Windows Windows 7
    四月 2nd, 2011 at 19:41  | #2

    这文,,我,,还是回火星好了 😀

  3. Gravatar
    SayMe Google Chrome Google Chrome 10.0.648.151 Linux Linux
    四月 1st, 2011 at 20:40  | #3

    这个对俺来说太难啦 哈哈.还是不看了 😀

  4. Gravatar
    yesureadmin Google Chrome Google Chrome 7.0.517.44 Windows Windows XP
    三月 31st, 2011 at 08:55  | #4

    表示不理解

  5. Gravatar
    宝典网 Mozilla Firefox Mozilla Firefox 4.0 Windows Windows 7
    三月 30th, 2011 at 21:31  | #5

    看来是高手啊···我表示完全不懂

  6. Gravatar
    Suitear Google Chrome Google Chrome 10.0.648.204 Windows Windows XP
    三月 30th, 2011 at 21:03  | #6

    老这么专业~ ❓ 没兴趣~ 😉

    • Gravatar Harid  @  四月 3rd, 2011 at 10:20 replied.

      @Suitear, 嘿嘿,另外也没啥写的哦。

  7. Gravatar
    韩国 Google Chrome Google Chrome 6.0.472.63 Windows Windows XP
    三月 30th, 2011 at 13:28  | #7

    虽然不是专业,博主很值得 学习。

  8. Gravatar
    太子虹 Internet Explorer Internet Explorer 6.0 Windows Windows XP
    三月 30th, 2011 at 11:53  | #8

    边走边看边支持博主

  9. Gravatar
    混乱博客 Google Chrome Google Chrome 10.0.648.133 Windows Windows 7
    三月 30th, 2011 at 11:51  | #9

    C++哈哈还真不会..呵呵!

    • Gravatar Harid  @  四月 3rd, 2011 at 10:15 replied.

      @混乱博客, C++还是比较难的,我也有点头大。不过比C++难得多的是用它实现的算法与数据结构…… 😳

  10. Gravatar
    煎豆 Google Chrome Google Chrome 12.0.712.0 Windows Windows 7
    三月 29th, 2011 at 18:13  | #10

    沉默数月的煎豆来访了~~

    • Gravatar Harid  @  四月 3rd, 2011 at 10:14 replied.

      @煎豆, 的确是好久了,煎豆赚大钱去了?

47 + 28 =  (required)
comment_ad

 NOTICE1: You should type some Chinese word (like “你好”) in your comment to pass the spam-check, thanks for your patience!

 NOTICE2: 请申请gravatar头像(http://en.gravatar.com),木有头像的会显示为“小怪物”头像,将难以通过审核!

分享按钮