数据结构带状矩阵的所需存储空间（数据结构学习笔记）

数据结构带状矩阵的所需存储空间（数据结构学习笔记）（2）稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n*m的稀疏矩阵A中有t个非零元素，则稀疏因子δδ的计算公式如下：δ=tn∗mδ=tn∗m(当这个值小于等于0.05时，可以认为是稀疏矩阵)（1）稀疏矩阵其非零元素的个数远远小于零元素的个数，而且这些非零元素的分布也没有规律。如何存储一个稀疏矩阵？拿上图举例，稀疏矩阵需存储以下信息：除此之外，还要存储矩阵的行数 3 和列数 3；稀疏矩阵特性：

一、稀疏矩阵定义 二、稀疏矩阵压缩存储方式 1、三元组顺序表压缩存储方式 2、行逻辑链接的顺序表存储方式 3、十字链表法存储方式

在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数与矩阵所有元素的总数的比率为矩阵的稠密度。

一、稀疏矩阵定义

如下图，如果矩阵中分布有大量的元素 0，即非 0 元素非常少，这类矩阵称为稀疏矩阵。

图10.1 稀疏矩阵

如何存储一个稀疏矩阵？拿上图举例，稀疏矩阵需存储以下信息：

• 第一行：(1 1 1)：数据元素为 1，在矩阵中的位置为 (1 1)；
• 第二行：(5 2 3)：数据元素为 5，在矩阵中的位置为 (2 3)；
• 第三行：(3 3 1)：数据元素为 3，在矩阵中的位置为 (3 1)；

除此之外，还要存储矩阵的行数 3 和列数 3；

稀疏矩阵特性：

（1）稀疏矩阵其非零元素的个数远远小于零元素的个数，而且这些非零元素的分布也没有规律。

（2）稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n*m的稀疏矩阵A中有t个非零元素，则稀疏因子δδ的计算公式如下：δ=tn∗mδ=tn∗m(当这个值小于等于0.05时，可以认为是稀疏矩阵)

二、稀疏矩阵压缩存储方式

存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等。

对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。

1、三元组顺序表压缩存储方式

根据稀疏矩阵的压缩存储定义，至少需要存储以下信息：

• 矩阵中各非 0 元素的值，以及所在矩阵中的行标和列标；
• 矩阵的总行数和总列数；

图10.2 稀疏矩阵

上图稀疏矩阵，若对其进行压缩存储，矩阵中各非 0 元素的存储状态如下：

（1，1，2）

（2，2，1）

（3，3，5）

上图数组中，存储的是三元组（即由 3 部分数据组成的集合），组中数据分别表示（行标，列标，元素值）。（注意，这里矩阵的行标和列标都是从 1 开始。）

C 语言中，三元组需要用结构体实现，如下所示：

/* 三元组类型定义，主要用来存储非零元 */ typedef struct { int i j; // 该三元组非零元的行下标和列下标 ElemType e; } Triple;

由于稀疏矩阵中非 0 元素有多个，因此需要建立 triple 数组存储各个元素的三元组。除此之外，考虑到还要存储矩阵的总行数和总列数，因此可以采用以下结构表示整个稀疏矩阵：

/* 三元组稀疏矩阵类型定义 */ typedef struct { Triple data[MAXSIZE ]; // 非零元三元组表，data[0]未用 int mu nu tu; // 矩阵的行数、列数和非零元个数 } TSMatrix;

可以看到，TSMatrix 是一个结构体，其包含一个三元组数组，以及用于存储矩阵总行数、总列数和非 0 元素个数的变量。如果采用 TSMatrix 结构体存储图10.2 中的稀疏矩阵，则 C 语言实现代码为：

#include<stdio.h> #define MAXSIZE 12500 // 非零元数量的最大值 //存储三元组的结构体 typedef struct { int i j; int data; }triple; //存储稀疏矩阵的结构体 typedef struct { triple data[MAXSIZE]; int mu nu tu; }TSMatrix; //输出存储的稀疏矩阵 void display(TSMatrix M) { int i j k; for (i = 1; i <= M.mu; i ) { for (j = 1; j <= M.nu; j ) { int value = 0; for (k = 0; k < M.tu; k ) { if (i == M.data[k].i && j == M.data[k].j) { printf("%d " M.data[k].data); value = 1; break; } } if (value == 0) printf("0 "); } printf("\n"); } } int main() { TSMatrix M; M.mu = 3; M.nu = 3; M.tu = 3; M.data[0].i = 1; M.data[0].j = 1; M.data[0].data = 2; M.data[1].i = 2; M.data[1].j = 2; M.data[1].data = 1; M.data[2].i = 3; M.data[2].j = 3; M.data[2].data = 5; display(M); return 0; }

输出结果为：

2 0 0 0 1 0 0 0 5

2、行逻辑链接的顺序表存储方式

三元组顺序表存储稀疏矩阵，其实现过程就是将矩阵中各个非 0 元素的行标、列标和元素值以三元组的形式存储到一维数组中。通过研究实现代码你会发现，三元组顺序表每次提取指定元素都需要遍历整个数组，运行效率很低。

因而行逻辑链接的顺序表。它可以看作是三元组顺序表的优化，在三元组顺序表的基础上提高了查找某一行非 0 数据的效率。

行逻辑链接的顺序表和三元组顺序表的实现过程类似，它们存储矩阵的过程完全相同，都是将矩阵中非 0 元素的三元组（行标、列标和元素值）存储在一维数组中。但为了提高提取查找指定行非 0 元素的效率，前者在存储矩阵时比后者多使用了一个数组，专门记录矩阵中每行第一个非 0 元素在一维数组中的位置。

图10.3 稀疏矩阵示意图

以上稀疏矩阵，当使用行逻辑链接的顺序表对其进行压缩存储时，需要做以下两个工作：

（1）将矩阵中的非 0 元素采用三元组的形式存储到一维数组 data 中，如图 10.4 所示（和三元组顺序表一样）：

图 10.4三元组存储稀疏矩阵

（2）使用数组 rpos 记录矩阵中每行第一个非 0 元素在一维数组中的存储位置。如图10.5 所示:

图10.5 存储各行首个非 0 元素在数组中的位置

通过以上两步操作，即实现了使用行逻辑链接的顺序表存储稀疏矩阵。此时，如果想从行逻辑链接的顺序表中提取元素，则可以借助 rpos 数组提高遍历数组的效率。例如，提取图10.4 稀疏矩阵中的元素 2 的过程如下：

• 由 rpos 数组可知，第一行首个非 0 元素位于data[1]，因此在遍历此行时，可以直接从第 data[1] 的位置开始，一直遍历到下一行首个非 0 元素所在的位置（data[3]）之前；
• 同样遍历第二行时，由 rpos 数组可知，此行首个非 0 元素位于 data[3]，因此可以直接从第 data[3] 开始，一直遍历到下一行首个非 0 元素所在的位置（data[4]）之前；
• 遍历第三行时，由 rpos 数组可知，此行首个非 0 元素位于 data[4]，由于这是矩阵的最后一行，因此一直遍历到 rpos 数组结束即可（也就是 data[tu]，tu 指的是矩阵非 0 元素的总个数）。

行逻辑链接的顺序表，可以用下面的结构来表示：

//三元组 typedef struct { int i j;//行，列 ElemType e;//元素值 }Triple; //行逻辑链接的顺序表 typedef struct { Triple data[MAXSIZE 1]; int rpos[MAXRC 1];//每行第一个非零元素在data数组中的位置 int mu nu tu;//行数，列数，元素个数 }RLSMatrix;

假如使用行逻辑链接的顺序表实现图10.3的稀疏矩阵，C 语言实现代码如下：

#include <stdio.h> #define MAXSIZE 12500 #define MAXRC 100 #define ElemType int typedef struct { int i j;//行，列 ElemType e;//元素值 }Triple; typedef struct { Triple data[MAXSIZE 1]; int rpos[MAXRC 1];//每行第一个非零元素在data数组中的位置 int mu nu tu;//行数，列数，元素个数 }RLSMatrix; //矩阵的输出函数 void display(RLSMatrix M) { int i j k; for (i = 1; i <= M.mu; i ) { for (j = 1; j <= M.nu; j ) { int value = 0; //输出前 mu - 1 行矩阵 if (i 1 <= M.mu) { for (k = M.rpos[i]; k < M.rpos[i 1]; k ) { if (i == M.data[k].i && j == M.data[k].j) { printf("%d " M.data[k].e); value = 1; break; } } if (value == 0) { printf("0 "); } } //输出矩阵最后一行的数据 else { for (k = M.rpos[i]; k <= M.tu; k ) { if (i == M.data[k].i && j == M.data[k].j) { printf("%d " M.data[k].e); value = 1; break; } } if (value == 0) { printf("0 "); } } } printf("\n"); } } int main() { RLSMatrix M; M.tu = 4; M.mu = 3; M.nu = 4; M.rpos[1] = 1; M.rpos[2] = 3; M.rpos[3] = 4; M.data[1].e = 3; M.data[1].i = 1; M.data[1].j = 2; M.data[2].e = 5; M.data[2].i = 1; M.data[2].j = 4; M.data[3].e = 1; M.data[3].i = 2; M.data[3].j = 3; M.data[4].e = 2; M.data[4].i = 3; M.data[4].j = 1; //输出矩阵 display(M); return 0; }

运行结果：

0 3 0 5 0 0 1 0 2 0 0 0

3、十字链表法存储方式

对于压缩存储稀疏矩阵，无论是使用三元组顺序表，还是使用行逻辑链接的顺序表，归根结底是使用数组存储稀疏矩阵。由于数组 "不利于插入和删除数据" 的特点，以上两种压缩存储方式都不适合解决类似 "向矩阵中添加或删除非 0 元素" 的问题。

例如，A 和 B 分别为两个矩阵，在实现 "将矩阵 B 加到矩阵 A 上" 的操作时，矩阵 A 中的元素会发生很大的变化，之前的非 0 元素可能变为 0，而 0 元素也可能变为非 0 元素。对于此操作的实现，之前所学的压缩存储方法就显得力不从心。

我们把矩阵的每一行每一列分别看成一个链表，然后将每一行和每一列的链表的第一个元素存放在一个数组中。这个数组就叫行链表的头指针数组，列链表的头指针数组。当我们访问矩阵的时候，就可以从行/列头指针数组中取出对应的指针，就可以访问这一行或者这一列的元素了。

图10.6 三元矩阵转为十字链矩阵

使用十字链表压缩存储稀疏矩阵时，矩阵中各行各列的元素都用一条链表存储，与此同时，将所有行链表的表头存储到一个数组（rhead），将所有列链表的表头存储到另一个数组（chead）中。
各个链表中节点的结构应如图10.6 所示：

行标	列标		结点值
指针域A		指针域B

3.1 建立十字链表元素类型及定义

两个指针域分别指向所在行的下一个元素和所在列的下一个元素。可以用如下的结构体来表示链表中的节点：

/* 十字链表元素类型 */ typedef int ElemType; /* 非零元类型定义 */ typedef struct OLNode { int i j; // 该非零元的行下标和列下标 ElemType e; struct OLNode* right; // 该非零元所在的行表的后继链域 struct OLNode* down; // 该非零元所在的列表的后继链域 } OLNode * OLink;

在此基础上，表示十字链表的结构体为：

/* 十字链表类型定义 */ typedef struct { OLink* rhead; // 行链表头指针 OLink* chead; // 列链表头指针 int mu nu tu; // 矩阵的行数、列数和非零元个数 } CrossList;

3.2 创建十字链表稀疏矩阵

void CreateMatrix(CrossList* M);

下面我们将要根据用户输入的行数，列数，非零元素的值，来创建矩阵。

int m n t; int num = 0; int i j e; OLNode* p = NULL * q = NULL; printf("输入矩阵的行数、列数和非0元素个数："); scanf("%d%d%d" &m &n &t); (*M).mu = m; (*M).nu = n; (*M).tu = t;

创建并初始化存放行列链表头的数组。

if (!((*M).rhead = (OLink*)malloc((m 1) * sizeof(OLink))) || !((*M).chead = (OLink*)malloc((n 1) * sizeof(OLink)))) { printf("初始化矩阵失败"); exit(0); } // 初始化行头指针向量;各行链表为空链表 for (i = 0; i <= m; i ) { (*M).rhead[i] = NULL; } // 初始化列头指针向量;各列链表为空链表 for (j = 0; j <= n; j ) { (*M).chead[j] = NULL; }

存放行列链表头的数组准备好了，接下来就要创建数据节点了。根据用户输入的行号，列号，数值创建节点。

while (num < t) { //输入矩阵数组： scanf("%d%d%d" &i &j &e); num ; if (!(p = (OLNode*)malloc(sizeof(OLNode)))) { printf("初始化三元组失败"); exit(0); } p->i = i; p->j = j; p->e = e; }

当创建好一个节点之后，我们就要放到行或者列的正确的位置。根据输入的行号列号确定插入的位置。那么应该怎样去插入？分两种情况：

  1、当这一行中没有结点的时候，那么我们直接插入：因为之前已经对头结点数组进行了初始化NULL，所以直接根据NULL==M->rhead[i]就可以判断一行中有没有节点。

if (NULL == (*M).rhead[i] || (*M).rhead[i]->j > j) { p->right = (*M).rhead[i]; (*M).rhead[i] = p; }

  2、当这一行中有结点的时候我们插入到正确的位置：当行中有节点的时候，无非是插入到某个节点之前或者某个节点之后。什么时候插入到节点前？什么时候插入到节点后呢？

  1.插入节点前：当我们要插入的节点的列号小于已经存在的节点的列号，这个时候就要插入到这个节点之前了。

  2.插入节点后：当我们要插入的节点的列号大于已经存在的节点的列号，这个时候就要插入到这个节点之后了。

for (q = (*M).rhead[i]; (q->right) && q->right->j < j; q = q->right); //将新非 0 元素插入 q 之后 p->right = q->right; q->right = p; }

以上是行的操作，对于列的插入同样如此，代码如下：

if (NULL == (*M).chead[j] || (*M).chead[j]->i > i) { p->down = (*M).chead[j]; (*M).chead[j] = p; } else { //找到当前元素要插入的位置 for (q = (*M).chead[j]; (q->down) && q->down->i < i; q = q->down); //将当前元素插入到 q 指针下方 p->down = q->down; q->down = p; }

3.3 输出十字链表稀疏矩阵

void printMatrix(CrossList M) { int i j; //一行一行的输出 for (i = 1; i <= M.mu; i ) { //如果当前行没有非 0 元素，直接输出 0 if (NULL == M.rhead[i]) { for (j = 1; j <= M.nu; j ) { printf("0 "); } putchar('\n'); } else { int n = 1; OLink p = M.rhead[i]; //依次输出每一列的元素 while (n <= M.nu) { if (!p || (n < p->j) ) { printf("0 "); } else { printf("%d " p->e); p = p->right; } n ; } putchar('\n'); } } }

最后进行测试：

int main() { CrossList M; M.rhead = NULL; M.chead = NULL; CreateMatrix(&M); printf("输出矩阵M:\n"); printMatrix(M); return 0; }

运行结果：

输入矩阵的行数、列数和非0元素个数：3 4 4 1 1 3 1 4 5 2 2 -1 3 1 2 输出矩阵M: 3 0 0 5 0 -1 0 0 2 0 0 0