十字链表矩阵

数据结构的十字链表矩阵要一开始的行列的表头要相互连接来表示邻接关系

这里用数组表示邻接也不浪费空间

写了Serach( i , j );函数可以寻找矩阵位置为i j数值

然后加，减，乘，也就方便了……

至于算法复杂度嘛……因为懒所以直接用Search()了（所以矩阵运算比想象中复杂度高……）……23333333

代码……

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstdlib>

using namespace std;

struct Node{
    int row;
    int col;
    int val;
    Node * right;
    Node * down;
    Node(int r = 0,int c = 0,int v = 0):row(r),col(c),val(v){
        right = down = NULL;
    }
};

class SparseMatrix{
    Node * first;
    friend ostream & operator << (ostream &,SparseMatrix &);
public:
    SparseMatrix(){
        first = NULL;
    }
    void Create(int r,int c){
        int m = max(r,c);
        first = new Node[m+1];
        first[0].row = r;
        first[0].col = c;
        first[0].val = 0;
    }
    void Create(){
        cout << "请输入矩阵的行列和数目" << endl;
        int r,c,num;
        cin >> r >> c >> num;
        int m = max(r,c);
        first = new Node[m+1];
        first[0].row = r;
        first[0].col = c;
        first[0].val = 0;

        while(num--){
            cout << "请输入元素" << endl;
            cin >> r >> c >> m;
            if(m == 0)
                continue;
            Insert(r,c,m);
        }
    }
    void Insert(int r,int c,int v){
        Node * p = new Node(r,c,v);
        Node * rr = &first[r];
        Node * cc = &first[c];
        first[0].val++;
        while(rr->right != NULL && rr->right->col <= c){
            rr = rr->right;
        }
        p->right = rr->right;
        rr->right = p;
        while(cc->down != NULL && cc->down->row <= r){
            cc = cc->down;
        }
        p->down = cc->down;
        cc->down = p;
    }
    int Search(int r,int c){
        Node * rr = & first[r];
        while(rr->right != NULL && rr->right->col <= c){
            if(rr->right->col == c)
                return rr->right->val;
            rr = rr->right;
        }
        return 0;
    }
    Node * getFirst(){
        return first;
    }
    SparseMatrix & operator + (SparseMatrix & x){
        Node * p = first;
        Node * q = x.getFirst();
        int r = p[0].row;
        int c = p[0].col;
        if(r != q[0].row || c != q[0].col){
            cout << "矩阵行列不相同，退出" << endl;
            exit(1);
        }
        SparseMatrix s;
        s.Create(r,c);
        for(int i = 1;i <= r;i++){
            for(int j = 1;j <= c;j++){
                int tmp = Search(i,j)+x.Search(i,j);
                if(tmp != 0){
                    s.Insert(i,j,tmp);
                }
            }
        }
        return s;
    }
    SparseMatrix & operator * (SparseMatrix & x){
        Node * p = first;
        Node * q = x.getFirst();
        int r = p[0].row;
        int c = q[0].col;
        int m = p[0].col;
        if(m != q[0].row){
            cout << "矩阵不能相乘"<< endl;
        }
        SparseMatrix s;
        s.Create(r,c);
        for(int i = 1;i <= r;i++){
            for(int j = 1;j <= c;j++){
                int ans = 0;
                for(int k = 1;k <= m;k++){
                    ans += (Search(i,k)*x.Search(k,j));
                }
                if(ans != 0){
                    s.Insert(i,j,ans);
                }
            }
        }
        return s;
    }
    SparseMatrix & Reserve(){
        Node * p = first;
        int r = p[0].row;
        int c = p[0].col;
        SparseMatrix s;
        s.Create(r,c);
        for(int i = r;i > 0;i--){
            for(int j = c;j > 0;j--){
                int tmp = Search(i,j);
                if(tmp != 0){
                    s.Insert(j,i,tmp);
                }
            }
        }
        return s;
    }
};
ostream & operator << (ostream &out,SparseMatrix &x){
    Node * p = x.getFirst();
    int r = p->row;
    int c = p->col;
    cout << "矩阵为：" << endl;
    for(int i = 0;i <= r;i++){
        if(i)
            cout << setw(4) << i;
        for(int j = 1;j <= c;j++){
            if(!i){
                if(j == 1)
                    out << setw(8)<< j;
                else
                    out << setw(4)<< j;
                continue;
            }
            cout << setw(4) << x.Search(i,j);
        }
        cout << endl;
    }
    return out;
}
int main(){
    //freopen("input.txt","r",stdin);
    SparseMatrix matrix1;
    SparseMatrix matrix2;
    matrix1.Create();
    matrix2.Create();
    SparseMatrix matrix3 = matrix1 + matrix2;
    SparseMatrix matrix4 = matrix1 * matrix2;
    SparseMatrix matrix5 = matrix1.Reserve();
    cout << "矩阵1 为" << matrix1 << endl;
    cout << "矩阵2 为" << matrix2 << endl;
    cout << "矩阵1，2相加 为" << matrix3 << endl;
    cout << "矩阵1，2相乘 为" << matrix4 << endl;
    cout << "矩阵1 转置 为" << matrix5 << endl;
    return 0;
}