稀疏矩阵的初始化及其转置（源代码+截图）

时间：2021-02-23 15:24:45
  1. 稀疏矩阵：如果在矩阵中，多数的元素为0，通常认为非零元素比上矩阵所有元素的值小于等于0.05时，则称此矩阵为稀疏矩阵（sparse matrix）。
  2. 你可能会想到用二维数组来存放此矩阵中的元素，就像这样：int text[][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}};
  3. 这样好像也没有什么不好。我们再来看看这个矩阵，五行五列，可以包含二十五个元素，但是此矩阵只有七个元素。
  4. 但是我们在存放数据的时候分配了二十五块int单元。这样是不是有点太浪费了。如果我们只存储这七个元素我想会节省一部分内存空间。
  5. 但是如果我们只存储矩阵中的元素还是不行的，因为只有元素我们就无法还原矩阵，我们还需要此元素的行列值。
  • 这样就好办了。我们声明一个结构体来表示一个元素。

 typedef struct matrix
 {
     int row;        //行
     int col;        //列
     int value;        //元素值
 };

  • 定义两个数组，一个用来存储稀疏矩阵，一个用来存储转置过后的矩阵：

struct matrix a[MAX_TERM];        //存放矩阵中元素数值不为零的元素
struct matrix b[MAX_TERM];        //转置后的矩阵

  • 存储稀疏矩阵，并赋值：

int initialize(struct matrix a[MAX_TERM])            //初始化稀疏矩阵
 {
     int i,j;
     int count_a = 1;
     for(i = 0;i < N;i++)
     {
         for(j = 0;j < N;j++)
         {
             if(text[i][j] != 0)
             {
                 a[count_a].row = i;
                 a[count_a].col = j;
                 a[count_a].value = text[i][j];
                 count_a++;
             }
         }
     }
     a[0].col = 5;            //矩阵的总列数
     a[0].row = 5;            //矩阵的总行数
     a[0].value = --count_a;    //矩阵中的元素个数

     return count_a;
 }


  • 打印原矩阵：

void showmatrix_1(struct matrix a[MAX_TERM],int count_a)        //打印未经压缩的矩阵
 {
     int i,j;
     int text = 1;
     for(i = 0;i < N;i++)
     {
         for(j = 0;j < N;j++)
         {
             if(a[text].row == i && a[text].col == j)
             {
                 printf(" %d ",a[text].value);
                 text++;
             }
             else
                 printf(" 0 ");
         }
         printf("\n");
     }

 }


  • 打印压缩过后的矩阵：

 void showmatrix_2(struct matrix a[MAX_TERM],int count_a)            //显示稀疏矩阵方
 {
     int i;
     printf(" i row col val\n");
     for(i = 0;i < count_a + 1;i++)
     {
         printf(" %d|  %d   %d   %d\n",i,a[i].row,a[i].col,a[i].value);
     }
 }


  • 转置矩阵并打印：

 void reversal(struct matrix a[MAX_TERM],struct matrix b[MAX_TERM])            //转置矩阵并打印
 {
     int i,j;
     int count_b = 1;        //b的当前元素下标
     b[0].row = a[0].col;
     b[0].col = a[0].row;
     b[0].value = a[0].value;
     for(i = 0;i < a[0].col;i++)
     {
         for(j = 1;j <= a[0].value;j++)
         {
             if(a[j].col == i)
             {
                 b[count_b].row = a[j].col;
                 b[count_b].col = a[j].row;
                 b[count_b].value = a[j].value;
                 count_b++;
             }
         }
     }

      for(i = 0;i < a[0].value + 1;i++)
         printf(" %d|  %d   %d   %d\n",i,b[i].row,b[i].col,b[i].value);
 }
  • 完整的源程序如下：

#include<stdio.h>
#define N 5
#define MAX_TERM 15

typedef struct matrix
{
     int row;        //行
     int col;        //列
     int value;        //元素值
};

int text[5][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}};//用二维数组存储矩阵的初始值 
struct matrix a[MAX_TERM];        //存放矩阵中元素数值不为零的元素
struct matrix b[MAX_TERM];        //转置后的矩阵

int initialize(struct matrix a[MAX_TERM])            //初始化稀疏矩阵
{
    int i,j;
    int count_a = 1;
    for(i = 0;i < N;i++)
    {
        for(j = 0;j < N;j++)
        {
            if(text[i][j] != 0)
            {
                a[count_a].row = i;
                a[count_a].col = j;
                a[count_a].value = text[i][j];
                count_a++;
            }
        }
    }
    a[0].col = 5;            //矩阵的总列数
    a[0].row = 5;            //矩阵的总行数
    a[0].value = --count_a;    //矩阵中的元素个数

    return count_a;
}

void showmatrix_1(struct matrix a[MAX_TERM],int count_a)        //打印稀疏矩阵
{
    int i,j;
    int text = 1;
    for(i = 0;i < N;i++)
    {
        for(j = 0;j < N;j++)
        {
            if(a[text].row == i && a[text].col == j)
            {
                printf(" %d ",a[text].value);
                text++;
            }
            else
                printf(" 0 ");
        }
        printf("\n");
    }

}

void showmatrix_2(struct matrix a[MAX_TERM],int count_a)            //显示稀疏矩阵方
{
    int i;
    printf(" i row col val\n");
    for(i = 0;i < count_a + 1;i++)
    {
        printf(" %d|  %d   %d   %d\n",i,a[i].row,a[i].col,a[i].value);
    }
}


void reversal(struct matrix a[MAX_TERM],struct matrix b[MAX_TERM])            //转置矩阵方法一
{
    int i,j;
    int count_b = 1;        //b的当前元素下标
    b[0].row = a[0].col;
    b[0].col = a[0].row;
    b[0].value = a[0].value;
    for(i = 0;i < a[0].col;i++)
    {
        for(j = 1;j <= a[0].value;j++)
        {
            if(a[j].col == i)
            {
                b[count_b].row = a[j].col;
                b[count_b].col = a[j].row;
                b[count_b].value = a[j].value;
                count_b++;
            }
        }
    }

     for(i = 0;i < a[0].value + 1;i++)
        printf(" %d|  %d   %d   %d\n",i,b[i].row,b[i].col,b[i].value);
}

int main(void)
{
    int count_a;//记录非0元素的个数 
    count_a = initialize(a);//初始化矩阵 ,并统计非0的元素个数 

    printf("打印原矩阵\n");
    showmatrix_1(a,count_a);//显示原矩阵 


    printf("\n显示压缩矩阵\n");
    showmatrix_2(a,count_a);//显示压缩矩阵 

    putchar('\n');

    printf("转置过后的矩阵\n") ;
    reversal(a,b);


    printf("\n");

    return 0;
}

  • devc++中的运行截图：

稀疏矩阵的初始化及其转置（源代码+截图）



标签：

相关文章