算法与数据结构，关于矩阵的压缩存储

问题描述：

#include<iostream>

using namespace std;

#define N1 3

#define N2 4

struct element

{

int row, col; //行号，列号

int item; //非零元素值

};

const int MaxTerm=100;

struct Matrix

{

element data[MaxTerm]; //存储非零元素

int rows, cols, tu; //行数、列数、非零元个数

};

void CreatMa(Matrix &T,int A[N1][N2])//创建三元组顺序表

{ 自己完成;

}

void Display(Matrix M)//将按三元组存储的稀疏矩阵输出

{ 自己完成;

}

void TransposeMatrix(Matrix M, Matrix &T)//求稀疏矩阵的转置矩阵

{ 自己完成;

}

void Fast(Matrix M, Matrix &T)//快速转置

{ 自己完成;

} //FastTranposeSMatrix;

void main()

{ 自己完成;

}

答

#include<stdio.h>
//判断该矩阵是否为稀疏矩阵
#define m    10
#define n    10
int a[m][n]={
    {1,0,0,0,0,0,0,0,0,0},   //自定义数组
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {1,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,7,0},
    {0,0,0,0,0,0,8,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
            };

struct three
{
    int i,j;            //定义矩阵下标
    int value;          //下标对应值
};
struct three stu[100];

struct three1
{
    int i,j;           //定义转置矩阵元素的下标
    int value;         //转置矩阵下标对应值
};
struct three1 stu1[100];

//检测
int examine()
{
    int x=0;           //赋初值为0
    for(x=0;x<=99;x++)
    {
        stu[x].value=0;
    }
    float t=0;         //非零元素个数
    float v;           //非零元素占有率
    for(int i=0;i<m;i++)  //遍历矩阵元素
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]!=0)  //如果该矩阵元素不为零
            t++;            //非零元素个数加一
        }
    }
    if((v=t/(m*n))<=0.05)   //计算矩阵非零元素占有率
    {
        printf("该矩阵为稀疏矩阵%f\n",v);
        return 1;
    }
    else
    {
        printf("该矩阵不是稀疏矩阵\n");
        return 0;
    }
}

//压缩存储
void compress()
{
    int t=0;
    for(int r=0;r<m;r++)
    {
        for(int c=0;c<n;c++)
        {
            if(a[r][c]!=0)   //只存储不为零的元素
            {
                stu[t].i=r;  //行下标
                stu[t].j=c;  //列下标
                stu[t].value=a[r][c];//压缩后矩阵的值用二维数组的下标表示
                t++;
            }
        }
    }
}

void display()  //打印三元组
{
    int x=0;
    printf("压缩矩阵的三元组为:\n");
    for(x=0;x<=99;x++)
    {
        if(stu[x].value==0)    break;//如果值为0，跳出循环
        printf("{%d,%d,%d} ",stu[x].i,stu[x].j,stu[x].value);//如果不为零，输出三元组(横纵坐标，值)
    }
    printf("\n");
}

//转置矩阵
void zhuanzhi()
{
    int x=0;     //赋初值为0
    int t=0;
    int num[10]={0,0,0,0,0,0,0,0,0,0};   //每一列非0的数目
    int j;
    for(x=0;x<=99;x++)
    {
         stu1[x].value=0;
    }
    for(int j=0;j<n;j++)      //遍历矩阵元素
    {
        for(int i=0;i<m;i++)
        {
            if(a[i][j]!=0)     //非零元素出现
            {
                num[j]++;      //数组num第j个元素变为1
                t++;           //非零元素数目加一
            }
        }
    }
    int cpot[10]={0,0,0,0,0,0,0,0,0,0};
    cpot[0]=0;
    for(j=1;j<n;j++)
    {
        cpot[j]=cpot[j-1]+num[j-1];//找到表中j列最小值1所在的三元组
    }
    int col=0;
    int q=0;
    for(int k=0;k<t;k++)
    {
        col=stu[k].j;
        q=cpot[col];
        stu1[q].i=stu[k].j;    //i，j位置互换
        stu1[q].j=stu[k].i;
        stu1[q].value=stu[k].value;//值互换
        ++cpot[col];
    }
}

//输出转置后的三元组
void display1()
{
    int x=0;
    printf("转置以后的三元组为:\n");
    for(x=0;x<=99;x++)
    {
        if(stu1[x].value==0)    break; //矩阵元素值为零，跳出循环
        printf("{%d,%d,%d} ",stu1[x].i,stu1[x].j,stu1[x].value);//不为零，输出三元组(坐标+值)
    }
    printf("\n");
}

//输出矩阵中所有元素的三元组
void display2()
{
    int d,b;
    for(d=0;d<m;d++)
    {
        for(b=0;b<m;b++)
        {
            printf("%d  ",a[d][b]);
        }
        printf("\n");
    }
}


int main()
{
    display2();
    if(examine()==1)   //检测通过
    {
        compress();    //压缩
        display();     //列出
        zhuanzhi();    //转置
        display1();
    }
}

算法与数据结构，关于矩阵的压缩存储

相关推荐