随机稀疏矩阵链式存储结构的探讨

魏斐翡+沈华

摘要：随机稀疏矩阵的压缩存储是数据结构课程的主要内容之一。随机稀疏矩阵的压缩存储有两类实现：顺序存储方式和链式存储方式。在数据结构课程中讨论随机稀疏矩阵顺序存储结构相对较多，缺少对其链式存储结构的详细介绍和深入讨论。为了弥补这个不足，深入讨论了随机稀疏矩阵的三种链式存储结构、分析了它们之间的关系和特点。

关键词：数据结构；随机稀疏矩阵；压缩存储；链式存储结构

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2017）36-0191-02

数据结构是计算机科学的基础核心课程，它对于外围课程的知识与经验具有迁移性、衍生性，对学生自学知识和获取实践经验具有基础性、发展性[1-6]。随着计算机应用的发展，出现了许多用计算机处理高阶矩阵的问题，这类问题对内存要求较高，因此研究矩阵的压缩存储是非常必要的[7]。本文重点讨论随机稀疏矩阵压缩存储的三种链式存储。

一、随机稀疏矩阵及其压缩存储

随机稀疏矩阵是一种非零元比零元少得多（即稀疏性）且非零元在矩阵中的分布不具有一定规律性（即随机性）的矩阵[7-8]。其压缩存储目标是，压缩掉对零元的存储，只存储非零元。因为非零元的分布是随机的，所以它需要用一个三元组（元素所在的行，元素所在的列，元素的值）来唯一确定。因此，一个稀疏矩阵对应一个三元组集合。三元组集合给出了所有非零元的分布和值，但是只给出了部分零元的分布，从而不能确定一个稀疏矩阵[7]。如果同时有稀疏矩阵的规模信息（即行数和列数），那么我们就可以知道零元的所有分布，从而可以唯一确定一个稀疏矩阵[7]。综上所述，一个稀疏矩阵可以用其对应的三元组集合和它的行数、列数唯一确定。如果三元组集合中的元素以行序为主序，那么我们得到了一个三元组线性表。三元组线性表的顺序存储是随机稀疏矩阵的一种压缩存储表示法——三元组顺序表。三元组线性表的链式存储是随机稀疏矩阵的另一种压缩存储表示法，因为在这种链式存储结构中每个非零元位于一个行链表和一个列链表的交汇处，就像一个“十字”，因此该链式存储结构被形象地称为“十字链表”。

二、随机稀疏矩阵链式存储结构的实现

十字链表除了要存放非零元的信息（row，col，val），还需要存放它与同行、同列非零元之间的关系，因此需要存放两个指针：一个是行指针rnext，用来指向同行的下一个非零元；另一个是列指针cnext，用来指向同列的下一个非零元。非零元的三个属性信息和行、列指针信息就构成了十字链表的存储映像。

（一）不纯粹的链式存储结构

对于一个规模为m×n的稀疏矩阵而言，它有m个行链表和n个列链表，如何组织这m+n个（不带头结点的）链表的头指针呢？一种简单的处理方法是，用两个大小分别为m和n的指针数组分别存放m个行链表的头指针和n个列链表的头指针。图1给出了一个随机稀疏矩阵实例，图2给出了该实例的如上所述链式存储结构示意图。此链式存储结构之所以不纯粹是因为它引入两个指针数组。能否不引入指针数组解决存储m+n个链表的头指针问题呢？回答是肯定的，我们可以仅仅利用十字链表的存储结点来解决这个问题。

（二）纯粹的链式存储结构

随机稀疏矩阵更纯粹的链式存储结构是：稀疏矩阵每一行的非零元信息用一个带头结点的单链环存储、每一列的非零元信息也用一个带头结点的单链存储。头结点的结构和表结点的结构相同。可以用m+n个头结点分别来担当m+n个单链环的头结点的角色。接下来需要思考的是这m+n个头结点该如何来组织的问题。本文选择用单链环来解决这个问题：m个行頭结点、n个列头结点分别构成一个单链环。同时，我们再引入一个总头结点，它既作为m个行头结点单链环的头结点又作为n个列头结点单链环的头结点。此外，可以用总头结点的非指针域存储稀疏矩阵的规模信息。指向总头结点的指针成为整个十字链表的唯一入口。随机稀疏矩阵C对应的存储结构示意图如图3所示。

（三）存储效率更高的纯粹链式存储结构

上述十字链表存储结构需要m+n个头结点，能否将头结点减少为max（m，n）个？本文选择用单链环的形式来组织这max（m，n）个头结点。同样，我们需要再引入一个总头结点，它是max（m，n）个头结点构成的单链环的头结点。用总头结点的rnext指针域指向第一头结点，用总头结点的非指针域存储稀疏矩阵的规模信息。指向总头结点的指针是整个十字链表的唯一入口。为了得到稀疏矩阵这种效率更高的纯粹链式存储结构，我们需要将头结点原来的一个非指针域改造为指针域。随机稀疏矩阵C对应的存储结构示意图如图4所示。

三、结束语

矩阵是一种在科学与工程计算问题中常用的数学对象，高阶矩阵对内存容量要求较高，矩阵的压缩存储是一个值得研究的课题。本文主要讨论随机稀疏矩阵的压缩存储问题，重点讨论了它的三种链式存储结构。深化了数据结构课程中数组相关内容的教学和学习，加强了对学生计算思维（如何将逻辑关系映射到存储器）的训练。

参考文献：

[1]余艳.数据结构实践教学内容设置的分析与思考[J].实验技术与管理，2014，31（4）：170-173.

[2]董丽薇.“数据结构”课程教学方法的改进[J].沈阳师范大学学报（自然科学版），2012，30（2）：307-309.

[3]杨程，刘涛，范勇等.基于虚拟现实的数据结构三维动态教学系统[J].实验技术与管理，2012，1（1）：74-78.

[4]沈华.数据结构课内实践教学方案[J].实验室研究与探索，2013，32（10）：396-400.

[5]沈华.数据结构、算法和程序之间关系的探讨[J].计算机教育，2013，（04）：58-61.

[6]沈华.数据结构入门教学中的实例法[J].计算机教育，2013，（24）：64-66.

[7]沈华，杨晓艳，马驰，等.数据结构及应用：C语言描述[M].北京：机械工业出版社，2011.

[8]Korsh J F，Garrett L J.Data structures，algorithms and program style using c [M].Boston，PWS-Kent Publishing Co，US，1986.endprint