数据结构带状矩阵的所需存储空间（数据结构学习笔记）
数据结构带状矩阵的所需存储空间（数据结构学习笔记）（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
