数据结构-稀疏矩阵（十字链表）

稀疏矩阵

/*coder:cyl   time: 2020.12.1*/
#include<bits/stdc++.h>
using namespace std;
#define ElemType int
#define Status   int
#define OK     1
#define ERROR -1
#define MAXSIZE 12500
int dp[MAXSIZE][MAXSIZE];
int x[MAXSIZE][MAXSIZE],y[MAXSIZE][MAXSIZE];

typedef struct OLNode{
    int i,j;
    ElemType e;
    struct OLNode *right,*down;
}OLNode,*OLink;
typedef struct {
    OLink *rhead,*chead;
    int mu,nu,tu;
}CrossList;

Status InitSMatrix(CrossList &M) {
    M.rhead = M.chead = NULL;
    M.mu = M.nu = M.tu = 0;
    return OK;
}


Status CreateSMatrix_OL(CrossList &M)
{

    OLNode *p, *q;
    int i, j, e;
    int m = rand()%6+3, n = rand()%6+3, t = rand()%(m*(n-2));
    M.mu = m;
    M.nu = n;
    M.tu = t;
    if (!(M.rhead = (OLink *)malloc((m + 1)*sizeof(OLink))))
        return ERROR;
    if (!(M.chead = (OLink *)malloc((n + 1)*sizeof(OLink))))
        return ERROR;
    for (int a = 1; a <= m; a++)  // 初始化行列头指针向量；各行列链表为空链表
        M.rhead[a] = NULL;
    for (int b = 1; b <= n; b++)
        M.chead[b] = NULL;
    for (int c = 1; c <= t; c++)
    {
        i=rand()%M.mu;
        j=rand()%M.nu;
        e=rand()%100;
        if (!(p = (OLNode *)malloc(sizeof(OLNode))))
            return ERROR;
        p->i = i;
        p->j = j;
        p->e = e;
        p->down = NULL;
        p->right = NULL;
        if (M.rhead[i] == NULL || M.rhead[i]->j > j)
        {
            p->right = M.rhead[i];
            M.rhead[i] = p;
        }
        else
        {
            for (q = M.rhead[i]; (q->right) && (q->right->j<j); q = q->right);
            p->right = q->right;
            q->right = p;
        }
        if (M.chead[j] == NULL || M.chead[j]->i > i)
        {
            p->down = M.chead[j];
            M.chead[j] = p;
        }
        else
        {
            for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
            p->down = q->down;
            q->down = p;
        }
    }
    return OK;
}


Status INsretSMatrix_OL(CrossList &M)
{

    OLNode *p, *q;
    int i, j, e;
    int m ,n,t;
    cout<<"请输入行数、列数、非零元素个数"<<endl;
    cin>>m>>n>>t;
    M.mu = m;
    M.nu = n;
    M.tu = t;
    if (!(M.rhead = (OLink *)malloc((m + 1)*sizeof(OLink))))
        return ERROR;
    if (!(M.chead = (OLink *)malloc((n + 1)*sizeof(OLink))))
        return ERROR;
    for (int a = 1; a <= m; a++)  // 初始化行列头指针向量；各行列链表为空链表
        M.rhead[a] = NULL;
    for (int b = 1; b <= n; b++)
        M.chead[b] = NULL;
    cout<<"请输入"<<t<<"个元素"<<endl;
    for (int c = 1; c <= t; c++)
    {
        scanf("%d%d%d",&i,&j,&e);
        if (!(p = (OLNode *)malloc(sizeof(OLNode))))
            return ERROR;
        p->i = i;
        p->j = j;
        p->e = e;
        p->down = NULL;
        p->right = NULL;
        if (M.rhead[i] == NULL || M.rhead[i]->j > j)
        {
            p->right = M.rhead[i];
            M.rhead[i] = p;
        }
        else
        {
            for (q = M.rhead[i]; (q->right) && (q->right->j<j); q = q->right);
            p->right = q->right;
            q->right = p;
        }
        if (M.chead[j] == NULL || M.chead[j]->i > i)
        {
            p->down = M.chead[j];
            M.chead[j] = p;
        }
        else
        {
            for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
            p->down = q->down;
            q->down = p;
        }
    }
    return OK;
}

Status SameCreateSMatrix_OL(CrossList &M)
{

    OLNode *p, *q;
    int i, j, e;
    int m = 3, n = 6, t = 5;
    M.mu = m;
    M.nu = n;
    M.tu = t;
    if (!(M.rhead = (OLink *)malloc((m + 1)*sizeof(OLink))))
        return ERROR;
    if (!(M.chead = (OLink *)malloc((n + 1)*sizeof(OLink))))
        return ERROR;
    for (int a = 1; a <= m; a++)  // 初始化行列头指针向量；各行列链表为空链表
        M.rhead[a] = NULL;
    for (int b = 1; b <= n; b++)
        M.chead[b] = NULL;
    for (int c = 1; c <= t; c++)
    {
        i=rand()%M.mu;
        j=rand()%M.nu;
        e=rand()%100;
        if (!(p = (OLNode *)malloc(sizeof(OLNode))))
            return ERROR;
        p->i = i;
        p->j = j;
        p->e = e;
        p->down = NULL;
        p->right = NULL;
        if (M.rhead[i] == NULL || M.rhead[i]->j > j)
        {
            p->right = M.rhead[i];
            M.rhead[i] = p;
        }
        else
        {
            for (q = M.rhead[i]; (q->right) && (q->right->j<j); q = q->right);
            p->right = q->right;
            q->right = p;
        }
        if (M.chead[j] == NULL || M.chead[j]->i > i)
        {
            p->down = M.chead[j];
            M.chead[j] = p;
        }
        else
        {
            for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
            p->down = q->down;
            q->down = p;
        }
    }
    return OK;
}

Status Output(CrossList M){
    OLink P;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=M.mu;i++){
        P=M.rhead[i];
        while(P){
            dp[P->i][P->j]=P->e;
            P=P->right;
        }
    }
    for(int m=0;m<M.nu;m++){
        cout<<"\t"<<"["<<m<<"]";
    }
    cout<<endl;
    for(int m=1;m<=M.mu;m++){
        cout<<"["<<m-1<<"]"<<"\t";
        for(int n=1;n<=M.nu;n++){
            cout << dp[m][n] << " " << "\t";
        }
        cout<<endl;
    }
    return OK;
}

Status AddMatrix(CrossList X,CrossList Y,CrossList &Z){
    OLink P;
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=1;i<=X.mu;i++){
        P=X.rhead[i];
        while(P){
            x[P->i][P->j]=P->e;
            P=P->right;
        }
    }
    for(int i=1;i<=Y.mu;i++){
        P=Y.rhead[i];
        while(P){
            y[P->i][P->j]=P->e;
            P=P->right;
        }
    }
    for(int m=1;m<=X.mu;m++){
        for(int n=1;n<=X.nu;n++){
            x[m][n]=x[m][n]+y[m][n];
        }
    }
    cout<<"X+Y=Z："<<endl;
    for(int m=0;m<X.nu;m++){
        cout<<"\t"<<"["<<m<<"]";
    }
    cout<<endl;
    for(int m=1;m<=X.mu;m++){
        cout<<"["<<m-1<<"]"<<"\t";
        for(int n=1;n<=X.nu;n++){
            cout << x[m][n] << " " << "\t";
        }
        cout<<endl;
    }
    return OK;
}

Status Menus(){
    cout<<"1.求稀疏矩阵的加法"<<endl;
    cout<<"2.随机生成稀疏矩阵"<<endl;
    cout<<"3.输入"<<endl;
    cout<<"0.退出程序"<<endl;
    int n;
    cin>>n;
    return n;
}

int main(){
    srand(time(0));
    CrossList M;
    InitSMatrix(M);
    CreateSMatrix_OL(M);
    Output(M);
    int problem=Menus();
    while(problem){
        if(problem==1){
            cout<<"随机生成两个行数、列数都相等的稀疏矩阵"<<endl;
            CrossList X,Y,Z;
            InitSMatrix(X);
            InitSMatrix(Y);
            SameCreateSMatrix_OL(X);
            SameCreateSMatrix_OL(Y);
            cout<<"X稀疏矩阵："<<endl;
            Output(X);
            cout<<"Y稀疏矩阵："<<endl;
            Output(Y);
            AddMatrix(X,Y,Z);
        }
        else if(problem==2){
            InitSMatrix(M);
            CreateSMatrix_OL(M);
            Output(M);
        }
        else if(problem==3){
            InitSMatrix(M);
            INsretSMatrix_OL(M);
            Output(M);
        }
        problem=Menus();
    }
    return 0;
}