扫码获取更多资源

广义表

●稀疏矩阵的压缩存储

在实际应用中，经常会遇到另一类型的矩阵，其阶数高、非零元素较零元素少，且分布没 有一定规律。假设在mXn矩阵中，如果有t个非零元素，令8 = t/(mXn),则称6为矩阵的 稀疏因子。通常认为6W0.05的矩阵为稀疏矩阵(Sparse Matrix) o这类矩阵的压缩存储要 比特殊矩阵复杂。

●稀疏矩阵的抽象数据类型

按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素值a.之 外还必须同时记下其所在行和列的位置(i, j),这样组成了一个三元组(i, j, aij)0反之，一 个三元组(i, j, a°)唯一确定了矩阵的一个非零元素。将稀疏矩阵非零元素对应的三元组所 构成的集合，按行优先顺序排列成一个线性表，称为三元组表(List of 3-Tuples)o由此，稀 疏矩阵可以由表示非零元素的三元组及其行列数唯一确定。

三元组顺序表的定义

将表示稀疏矩阵非零元素的三元组按行优先顺序排列，并依次存放在一组地址连续的 存储单元里的方式称为稀疏矩阵的顺序存储结构，釆用这种存储结构的稀疏矩阵称为三元 组顺序表(Triple Sequential List) o

十字链表的定义

将稀疏矩阵的非零元素用一个包含五个域的 结点表示：行号域row、列号域col、值域e、列链接 指针域down和行链接指针域right

稀疏矩阵中同一行的非零元素通过right连接 成一个行链表，同一列的非零元素通过down连接 成一个列链表；每个非零元素既是某个行链表中 的一个结点，又是某个列链表中的一个结点，整个 矩阵构成了一个十字交叉的链表；依靠行列指针连接建立相邻的逻辑关系的方式称为稀疏 矩阵的链式存储结构，采用这种存储结构的稀疏矩阵称为十字链表(Cross Linked List)o

联系我们：

微信