稀疏矩阵的压缩存储

特殊矩阵在采用二维数组存储时，尽管矩阵操作的算法都很简单，但是其空间的利用率很低。系数矩阵就是一种应用很广泛的特殊的矩阵。现要求稀疏矩阵采用“压缩”存储，实现矩阵的常用操作，如输出、转置、求和等。

Question

矩阵采用“压缩”存储，实现矩阵的常用操作，如输出、转置、求和等。

矩阵的输入：有多行，第1行包括三个整数，分别是矩阵的大小m,n及非零元素的个数r。后面r行分别输入各个非零元素的行、列、值

矩阵的输出：按人们习惯的矩阵格式输出，即输出一个m*n的矩阵，是零元素的输出0，非零元素输出元素值。

例如：输入如下：

100 90 5 //矩阵的行数为100，列数为90，共5个非零元素。
1 10 100 //a(1,10)=100
50 60 200//a(50,60)=200
50 80 100//a(50,80)=100
60 60 200//a(60,60)=200
99 89 10//a(99,89)=10
100 90 4 //矩阵b的行数为100，列数为90，共4个非零元素。
1 1 10 //b(1,1)=10
50 60 -200//b(50,60)=-200
50 80 100 //b(50,80)=100
70 70 10 //b(70,70)=10

Example

Input

Output

The transformed matrix  is:
10 1 100
60 50 200
60 60 200
80 50 100
89 99 10
The added matrix is:
1 1 10
1 10 100
50 80 200
60 60 200
70 70 10
99 89 10

分析

首先题目描述有错。

按人们习惯的矩阵格式输出应该是仍然按照题目中格式输出。

所谓矩阵的压缩存储，实际上是在矩阵中元素较少时，只存非零元素的方法。在矩阵比较特殊（如三角阵）或矩阵元素比较稀疏的情况下能大大节省存储空间。但同时，压缩存储也会导致访问效率下降。

所以这里我们定义了结构体来存储矩阵中的某个元素：

typedef struct{
    int row;
    int column;
    int data;
}point;

此题中第一部分，矩阵转置，通过观察即可知道，行变列列变行，只需交换元素row和column即可。

但交换后有个问题，即按照题目给出的标准输出，显然先输出行号小的元素，行号相等先输出列号小的元素。这就涉及了结构体数组的二级排序，也不难：

int cmp(const void *p1,const void *p2){
    if(((point*)p1)->row==((point*)p2)->row){
        return ((point*)p1)->column-((point*)p2)->column;
    }
    return ((point*)p1)->row-((point*)p2)->row;
}
qsort(res,pA,sizeof(point),cmp);

至于第二问，两矩阵相加，类似归并的思想，每次找到小的拿过来，两者相等就相加。不过这里注意，两者相加有可能结果为0，要消去这组数据。

Anwser

#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct{
    int row;
    int column;
    int data;
}point;
int cmp(const void *p1,const void *p2){
    if(((point*)p1)->row==((point*)p2)->row){
        return ((point*)p1)->column-((point*)p2)->column;
    }
    return ((point*)p1)->row-((point*)p2)->row;
}
void printMatrix(point*p,int n){
    for(int i=0;i<n;i++){
        cout<<p[i].row<<' '<<p[i].column<<' '<<p[i].data<<endl;
    }
}
int cmpPos(point*p1,point*p2){//其实这个函数多余，直接用前面那个cmp函数也能达到比较的目的，不过我不习惯
    if(p1->row!=p2->row){
        return p1->row-p2->row;
    }
    if(p1->column!=p2->column){
        return p1->column-p2->column;
    }
    return 0;
}
int main()
{
    int mA,nA,pA;//第一个矩阵的行数、列数、非空元素数目
    int mB,nB,pB;
    point*dataA;
    point*dataB;
    point*res;//存储结果
    cin>>mA>>nA>>pA;
    dataA=new point[pA];
    res=new point[pA];
    for(int i=0;i<pA;i++){
        cin>>dataA[i].row>>dataA[i].column>>dataA[i].data;
        res[i].row=dataA[i].column;//转置
        res[i].column=dataA[i].row;
        res[i].data=dataA[i].data;
    }
    cin>>mB>>nB>>pB;
    dataB=new point[pB];
    for(int i=0;i<pB;i++){
        cin>>dataB[i].row>>dataB[i].column>>dataB[i].data;
    }
    qsort(res,pA,sizeof(point),cmp);
    cout<<"The transformed matrix  is:"<<endl;
    printMatrix(res,pA);
    delete[] res;
    res=new point[pA+pB];//结果元素数目总小于等于二者之和
    point*p1=dataA;
    point*p2=dataB;
    point*p3=res;
    while(p1<dataA+pA&&p2<dataB+pB){
        if(cmpPos(p1,p2)<0){
            *p3=*p1;
            p1++;
        }else if(cmpPos(p1,p2)==0){
            *p3=*p1;
            p3->data=p1->data+p2->data;
            p1++;
            p2++;
            if(p3->data==0){
                p3--;
            }
        }else{
            *p3=*p2;
            p2++;
        }
        p3++;
    }
    while(p1<dataA+pA){
        *p3=*p1;
        p3++;
        p1++;
    }
    while(p2<dataB+pB){
        *p3=*p2;
        p3++;
        p2++;
    }
    cout<<"The added matrix is:"<<endl;
    printMatrix(res,p3-res);
    delete[] res;
    delete[] dataA;
    delete[] dataB;
    return 0;
}

最后修改于 2019-06-01