魏斐翡+沈华

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

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

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

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

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

随机稀疏矩阵是一种非零元比零元少得多（即稀疏性）且非零元在矩阵中的分布不具有一定规律性（即随机性）的矩阵[7-8]。其压缩存储目标是，压缩掉对零元的存储，只存储非零元。因为非零元的分布是随机的，所以它需要用一个三元组（元素所在的行，元素所在的列，元素的值）来唯一确定。因此，一个稀疏矩阵对应一个三元组集合。三元组集合给出了所有非零元的分布和值，但是只给出了部分零元的分布，从而不能确定一个稀疏矩阵[7]。……