数据结构（13）矩阵及其压缩存储

旧城等待， 2023-07-03 10:38 11阅读 0赞

### 数据结构（13）矩阵及其压缩存储 ###

*   *   *  前言
         *  特殊矩阵与稀疏矩阵
         *  特殊矩阵的压缩存储
         *  稀疏矩阵的压缩存储
         *   *  用三元组来保存非零元素
             *  三元组顺序表矩阵的创建
             *  三元组顺序表矩阵的转置
             *  三元组顺序表矩阵的快速转置
         *  全部代码
         *   *  Matrix.txt
             *  SpareMatrix.h
             *  SpareMatrix.c
             *  Main.c

### 前言 ###

矩阵我们平时接触得比较少，但是在计算机中如何存储表示它也值得思考。通常在高级语言里，用二维数组来存储矩阵元素。但是在矩阵中有许多值相同的元素或者零元素，使用二维数组来保存可能会浪费空间，因此牵扯到矩阵的压缩存储问题。

所谓的压缩存储是指，为多个值相同的元只分配一个存储空间，对零元不分配存储空间。

### 特殊矩阵与稀疏矩阵 ###

矩阵有特殊矩阵和稀疏矩阵的区别。

特殊矩阵是指：值相同的元素或者零元素在矩阵的分布中有一定规律

而稀疏矩阵是指：零元素的数量远多于非零元素的数量，并且非零元素的分布没有规律可言

### 特殊矩阵的压缩存储 ###

特殊矩阵中，非零元素的分布都有一定的规律，我们可以根据规律将其压缩到一维数组中，并且找到每个非零元素在一维数组中的对应关系。以对称矩阵为例，由于对称矩阵沿对角线两侧的数据相等，因此我们可以只存储矩阵中对角线一侧（包含对角线）的数据即可。

![img\_1][img_1]

按行元素存储到一维数组中，可以得到如下的一维数组

![img\_2][img_2]  
矩阵中的元素和一维数组中的元素是存在着一一对应的关系的，设某元素所在的位置为（ i , j ），它的值与数组中对应值skr\[k\]的关系如下：

![img\_3][img_3]

注：矩阵元素中的行和列从1开始

例如，现在要求位于（3,1）处的元素值，代入公式：

![img\_4][img_4]  
得k值为3，代入一维数组skr\[3\] = 3，与矩阵相符。

以上参考：[矩阵（稀疏矩阵）压缩存储（3种方式）][3]

除了对称矩阵外，还有诸如三角矩阵、对角矩阵等都可以找到规律来压缩存储，这里不详谈了，下面主要讲稀疏矩阵的压缩存储。

### 稀疏矩阵的压缩存储 ###

#### 用三元组来保存非零元素 ####

按照压缩存储的概念，我们只存储其非零元素的值，而稀疏矩阵的问题在于其非零元素的分布没有规律。因此除了值本身之外，我们还需要存储它所在的行和列的位置。这实际上需要一个结构体来表示，一般称为三元组。

//三元组
    typedef struct Triple{ 
        //行
        int i;
        //列
        int j;
        //元素值
        ElemType e;
    }Triple;

例如，如图所示的稀疏矩阵

![img\_5][img_5]

可以由如下的三元组表来记录

![img\_6][img_6]

当然，一般还需要记录下稀疏矩阵的行数、列数。

通过三元组表可以来表示稀疏矩阵，而如何来存储表示三元组表，则可以引申出稀疏矩阵不同的压缩存储方法。

*  三元组顺序表：即用顺序存储结构来存储三元组表，也是本文代码中使用的方式
 *  行逻辑连接的顺序表：行逻辑连接的顺序表也是用顺序存储结构来存储，但是在提取效率上比三元组顺序表更高。不详谈，可参考：[行逻辑链接的顺序表（压缩存储稀疏矩阵）详解][Link 1]
 *  十字链表：用链式存储结构来存储的三元组表。不详谈，可参考：[十字链表法，十字链表压缩存储稀疏矩阵详解][Link 2]

以上三种方法除了都存储行、列和元素值外，在结点或者整个表结构的设计上会有所区别，例如十字链表法的结点中还会额外设置两个指针域。而三元组顺序表，一般会记录整个稀疏矩阵的行数、列数和非零元的个数。

//稀疏矩阵
    typedef struct SMatrix{ 
        //一个数组用于保存三元组
        Triple data[MAXSIZE];
        //行数
        int mu;
        //列数
        int nu;
        //非零元素的个数
        int tu;
    }SMatrix;

#### 三元组顺序表矩阵的创建 ####

这里所说的创建矩阵，实际上就是将一个稀疏矩阵转化为三元组顺序表的过程。我们默认从文件中读取一个矩阵，第一行为矩阵的行数和列数，文件内容如下（矩阵为上图展示的矩阵M）：

![img\_7][img_7]

首先读取出矩阵的行和列

//读取出矩阵的行和列
    fscanf(fp, "%d %d",&m->mu,&m->nu);

根据行列遍历矩阵，读取到每一个值后，判断是否为零，若不是则记录下行数、列数和该值即可。

//读取数据
        int value;
    		//行
        for (int i = 0; i < m->mu; i++) { 
            //列
            for (int j = 0; j < m->nu; j ++) { 
                fscanf(fp, "%d",&value);
                if (value != 0) { 
                    //保存到三元组中
                    m->data[m->tu].e = value;
                    m->data[m->tu].i = i;
                    m->data[m->tu].j = j;
                    //非零元个数
                    m->tu ++;
                }
            }
        }

#### 三元组顺序表矩阵的转置 ####

转置是矩阵的运算之一，设矩阵M为m行n列，则其转置的矩阵T为n行m列，且 T( i , j ) = M( j , i ) 。如图所示。

![img\_8][img_8]

如图，a.data表示的是矩阵M，b.data表示的是矩阵T，如何将a转成b呢？

![img\_9][img_9]  
可以看到对于矩阵M来说，a.data是按行来依次输出，而b.data是按列来依次输出，并且由于转置运算，需要将 i 和 j 对调。

![img\_10][img_10]  
那么我们的转置算法可以这样设计：

*  用一个 col 循环来查找每一列，即依次从1 2 3 4…开始找
 *  遍历整个三元组表，比较与当前循环次数相等的 j 下标
 *  如果相等说明是该列的元素，需要行列对调，然后保存到新表中

![img\_11][img_11]

可以发现，这个方法需要的循环次数过多，假如列数和非零元个数很多，就没有效率，下面介绍矩阵的快速转置方法。

#### 三元组顺序表矩阵的快速转置 ####

矩阵的快速转置方法，它的基本思想是：先计算出每一列元素在b.data里所占的位置，这样在每转置一个元素时，可以直接得其在b.data的位置，存入即可

![img\_12][img_12]

为了实现这个算法，我们需要额外设置两个数组，一个用于保存每一列中非零元素的个数，进而得到另一个用于保存每一列的第一个非零元素在b.data中位置的数组。

![img\_13][img_13]

得到如上数组后，我们只需要遍历一次a.data，依次把元素放入b.data的相应位置就好了。需要注意的是，在存完一个元素后，对应列的第一个非零元素在b.data的位置应该加一，例如在存完（2，1，12）后，下一个（2，5，18）应该保存到4的位置。这个”每一列第一个非零元素“，应该是”剩下还没转置“的第一个。

![img\_14][img_14]

### 全部代码 ###

需要说明一下：矩阵的行和列从1开始，为了方便说明包括数组也是从1开始的，但是在代码中为了方便，行列值都是从0开始

#### Matrix.txt ####

6 7

0 12 9 0 0 0 0

0 0 0 0 0 0 0

\-3 0 0 0 0 14 0

0 0 24 0 0 0 0

0 18 0 0 0 0 0

15 0 0 -7 0 0 0

#### SpareMatrix.h ####

#ifndef SparseMatrix_h
    #define SparseMatrix_h
    
    #include <stdio.h>
    #include <memory.h>
    #include <stdlib.h>
    #include <assert.h>
    
    #define ElemType int
    #define MAXSIZE 20
    
    //三元组
    typedef struct Triple{ 
        //行
        int i;
        //列
        int j;
        //元素值
        ElemType e;
    }Triple;
    
    //稀疏矩阵
    typedef struct SMatrix{ 
        //一个数组用于保存三元组
        Triple data[MAXSIZE];
        //行数
        int mu;
        //列数
        int nu;
        //非零元素的个数
        int tu;
    }SMatrix;
    
    //创建矩阵
    void CreateMatrix(SMatrix *m);
    //打印矩阵
    void PrintMatrix(SMatrix *m);
    //拷贝矩阵->将m拷贝到t中
    void CopyMatrix(SMatrix *m,SMatrix *t);
    //矩阵转置
    void TransposeMatrix(SMatrix *m,SMatrix *t);
    //矩阵快速转置
    void FastTransposeMatrix(SMatrix *m,SMatrix *t);
    
    #endif /* SparseMatrix_h */

#### SpareMatrix.c ####

#include "SparseMatrix.h"
    //创建矩阵
    void CreateMatrix(SMatrix *m){ 
        //从文件中读取数据
        FILE *fp = fopen("/Matrix.txt", "r");
        if (fp == NULL) { 
            exit(1);
        }
        //读取出矩阵的行和列
        fscanf(fp, "%d %d",&m->mu,&m->nu);
        //读取数据
        int value;
        //行
        for (int i = 0; i < m->mu; i++) { 
            //列
            for (int j = 0; j < m->nu; j ++) { 
                fscanf(fp, "%d",&value);
                if (value != 0) { 
                    //保存到三元组中
                    m->data[m->tu].e = value;
                    m->data[m->tu].i = i;
                    m->data[m->tu].j = j;
                    //非零元个数
                    m->tu ++;
                }
            }
        }
        fclose(fp);
    }
    
    //打印矩阵（只打印三元组表
    void PrintMatrix(SMatrix *m){ 
        printf("row:%d col:%d\n",m->mu,m->nu);
        for (int i = 0; i < m->tu; i ++) { 
            printf("(%d,%d,%d)\n",m->data[i].i,m->data[i].j,m->data[i].e);
        }
    }
    
    //拷贝矩阵->将m拷贝到t中
    void CopyMatrix(SMatrix *m,SMatrix *t){ 
        t->mu = m->nu;
        t->nu = m->nu;
        t->tu = m->tu;
        
        for (int i = 0; i < m->tu; i ++) { 
            t->data[i].i = m->data[i].i;
            t->data[i].j = m->data[i].j;
            t->data[i].e = m->data[i].e;
        }
    }
    
    //矩阵转置
    void TransposeMatrix(SMatrix *m,SMatrix *t){ 
        //先转置行数和列数
        t->mu = m->nu;
        t->nu = m->mu;
        t->tu = m->tu;
        
        //转置数值
        int k = 0;
        if (m->tu != 0) { 
            //从每一列开始找
            for (int col = 0; col < m->nu ; col++) { 
                //遍历整个三元组表，寻找j坐标和当前列标一致的元素
                for (int i = 0; i < m->tu; i++) { 
                    if (m->data[i].j == col) { 
                        //交换i、j值，保存数据
                        t->data[k].i = m->data[i].j;
                        t->data[k].j = m->data[i].i;
                        t->data[k].e = m->data[i].e;
                        k ++;
                    }
                }
            }
        }
    }
    
    //矩阵快速转置
    void FastTransposeMatrix(SMatrix *m,SMatrix *t){ 
        //先转置行数和列数
        t->mu = m->nu;
        t->nu = m->mu;
        t->tu = m->tu;
        
        //记录每一列（即转置后每一行）的非零元素个数
        int *num = (int *)malloc(sizeof(int) * m->tu);
        assert(num != NULL);
        
        //记录每一列（即转置后每一行）的第一个非零元素在转置后的位置
        int *cpot = (int *)malloc(sizeof(int)*m->nu);
        assert(cpot != NULL);
        
        if (t->tu != 0) { 
            //先将计数矩阵初始化为零
            for (int col = 0; col < m->nu; col++) { 
                num[col] = 0;
            }
            //统计每一列非零元素的个数
            for (int t = 0; t < m->tu; t++) { 
                num[m->data[t].j]++;
            }
            
            //计算每一列第一个元素转置后的起始位置
            //第0列直接为0
            cpot[0] = 0;
            for (int col = 1; col < m->nu; col++) { 
                //此后的每一列起始位置 = 上一列的起始位置+上一列非零元素的个数
                cpot[col] = cpot[col -1] + num[col -1];
            }
            
            
            int q = 0;
            for (int p = 0; p < m->tu; p ++) { 
                //得到列数
                int col = m->data[p].j;
                //得到本列非零元素的起始位置
                q = cpot[col];
                //保存
                t->data[q].i = m->data[p].j;
                t->data[q].j = m->data[p].i;
                t->data[q].e = m->data[p].e;
                
                //起始位置自增
                cpot[col] ++;
            }
        }
        free(num);
        free(cpot);
    }

#### Main.c ####

#include "SparseMatrix.h"
    
    int main(int argc, const char * argv[]) { 
        SMatrix sm,sm1;
        //全部初始化为0
        memset(&sm, 0, sizeof(sm));
        
        CreateMatrix(&sm);
        PrintMatrix(&sm);
        
        //拷贝
       // CopyMatrix(&sm, &sm1);
       // PrintMatrix(&sm1);
        
        //转置
        //TransposeMatrix(&sm, &sm1);
        FastTransposeMatrix(&sm, &sm1);
        PrintMatrix(&sm1);
        return 0;
    }

[img_1]: https://img-blog.csdnimg.cn/20200205152900976.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_2]: https://img-blog.csdnimg.cn/20200205152929510.png
[img_3]: https://img-blog.csdnimg.cn/20200205152948805.png
[img_4]: https://img-blog.csdnimg.cn/2020020515301145.png
[3]: http://data.biancheng.net/view/183.html
[img_5]: https://img-blog.csdnimg.cn/20200205153035826.png
[img_6]: https://img-blog.csdnimg.cn/20200205153056868.png
[Link 1]: http://data.biancheng.net/view/185.html
[Link 2]: http://data.biancheng.net/view/186.html
[img_7]: https://img-blog.csdnimg.cn/20200205153130402.png
[img_8]: https://img-blog.csdnimg.cn/20200205153152253.png
[img_9]: https://img-blog.csdnimg.cn/20200205153219286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_10]: https://img-blog.csdnimg.cn/20200205153237226.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_11]: https://img-blog.csdnimg.cn/20200205153256355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_12]: https://img-blog.csdnimg.cn/20200205153328900.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_13]: https://img-blog.csdnimg.cn/20200205153404530.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_14]: https://img-blog.csdnimg.cn/20200205153426720.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70