[数据结构与算法]稀疏矩阵算法专项提高

二叉树的算法专项提高

本次数据结构专项提高为矩阵类，算法比较易懂，主要为稀疏矩阵的三元表达法、十字链表示法。最后有总结嗷！
你的三连就是我创作的最大动力！

稀疏矩阵三元表示法的结构代码（重点）

typedef struct{
    int val;
    int i,j;
}Trimat;

如果定义一个稀疏矩阵，则只需要写如下代码

Trimat trimat[Maxsize];

当然也可以不用上述结构体来表示，可以直接定义一个二维数组也可以

int trimat[maxterms][3];

则trimat[k][0]表示按行优先顺序的第k个元素，规定第0行的3个元素分别存储非零元素的个数、行数和列数。

稀疏矩阵的十字链表示法结构代码

typedef struct OLNode{
    int row;
    int col;
    struct OLNode *right,*down;
    float val;
}OLNode;

//头结点
typedef struct{
    OLNode *rhead,*chead;
    int m,n,k;
}CrossList;

下图展现了一个矩阵的2个表达方法，当然还缺少邻接表的表示（准备在图论提高中涉及，这里就不再说了）

建立三元表

题目1:给定一个稀疏矩阵A，m*n型，建立对应的三元组存储，并通过三元表打印矩阵A

分析:问题在于求原矩阵的非零元素个数与值以及位置。比较简单，只要学会遍历即可，这里直接采用数组的方法来保存。

void CreatTrimat(int A[][Maxsize],int m,int n,int B[][3]){
    int k=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(A[i][j]){
                //建立的核心算法
                B[K][0]=A[i][j];
                B[k][1]=i;
                B[k][2]=j;
                k++;//统计
            }
        }
    }
    B[0][0]=k-1;
    B[0][1]=m;
    B[0][2]=n;
}

void print(int B[][3]){
    for(int i=0;i<B[0][1];i++){
        for(int j=0;j<B[0][2];j++){
            int flag=0,k;
            for(k=1;k<=B[0][0];k++){
                if(i==B[k][1]&&j==B[k][2]){
                    cout<<B[k][0]<<" ";
                    flag=1;
                    break;
                }
                if(!flag){
                    cout<<"0";
                }
            }
        }
        cout<<endl;
    }
}

建立十字链表结构

题目2：给定一个稀疏矩阵A，m*n型，非零元素个数为k，建立相应的十字链表结构。

int CreatCrossListmat(int A[][Maxsize],int m,int n,int k,CrossList &M){
    if(M.rhead) free(M.rhead);
    if(M.chead) free(M.chead);
    M.m=m;
    M.n=n;
    M.k=k;
    //申请头结点
    if(!(M.rhead=(OLNode *)malloc(sizeof(OLNode)*m))) return 0;
    if(!(M.chead=(OLNode *)malloc(sizeof(OLNode)*n))) return 0;
    //使头结点数组right,down为NULL
    for(int i=0;i<m;i++){
        M.rhead[i].right=NULL;
        M.rhead[i].down=NULL;
    }
    for(int i=0;i<n;i++){
        M.chead[i].right=NULL;
        M.chead[i].down=NULL;
    }
    OLNode *temp_r[Maxsize];//建立列链表的指针数组
    for(int j=0;j<n;j++){
        temp_r[j]=&(M.chead[j]);
    }
    for(int i=0;i<m;i++){
        OLNode *c=&(M.rhead[i]);
        for(int j=0;j<n;j++){
            if(A[i][j]){
                OLNode *p=(OLNode *)malloc(sizeof(OLNode));
                p->row=i;
                p->col=j;
                p->val=A[i][j];
                p->right=NULL;
                p->down=NULL;
                c->right=p;
                c=p;
                temp_r[j]->down=p;
                temp_r[j]=p;
            }
        }
    }
    return 1;
}

总结

一般来说，矩阵和数组考的不多，大多处于计算题中，但是这些算法至关重要，是考量算法功底的看家本领。矩阵就是二维数组，适当运用合理的方法，可以简化问题并且缩减空间。当然，在矩阵里面有很多算法题，这里值得一提的是著名的斐波那契数列的快速幂计算，这里埋个坑有时间出个教程看看！最后，理解教材内容，尽管十字链表比较有难度，但还是需要掌握一下，熟练使用指针和地址也是有益的!