稀疏矩阵存储：十字链表实现与压缩存储

"稀疏矩阵的十字链表存储表示是数据结构中处理大规模非零元素矩阵的一种高效方法。本文档主要介绍了数据结构第五章讲义的内容，包括数组、广义表以及矩阵的压缩存储，特别是稀疏矩阵的十字链表表示。" 稀疏矩阵是一种在实际应用中常见的数据结构，当一个矩阵中大部分元素为零时，采用常规的二维数组存储会浪费大量空间。为了提高存储效率，可以采用稀疏矩阵的十字链表存储表示。十字链表结构由两部分组成：行链表头指针向量`rhead`和列链表头指针向量`chead`，以及记录矩阵行数`mu`、列数`nu`和非零元素个数`tu`。 在十字链表中，每个节点`OLNode`包含四个字段：行索引`row`、列索引`col`、元素值`e`和两个指针，分别指向同一行的下一个元素`right`和同一列的下一个元素`down`。这种结构允许快速访问和修改矩阵中的非零元素，同时避免了存储大量零元素的需求。 数组是基本的数据结构，其维数固定且不可变。数组的元素可以看作是值和下标的组合，每个元素都可以表示为一个线性表。二维数组可以视为一维数组的数组，通过typedef可以简化类型定义。数组的操作主要是存取和修改元素值，顺序存储是数组常用的方式，有行优先和列优先两种策略。对于二维数组，可以通过下标计算出元素在连续存储空间中的位置。 在处理矩阵时，特别是大型稀疏矩阵，压缩存储是必要的。矩阵的压缩存储方法针对零元素较多的情况，如特殊矩阵，例如对称矩阵，其对角线以下或以上的元素与对角线上的元素相等，可以减少存储需求。十字链表存储适用于稀疏矩阵，因为它是动态的，仅存储非零元素，节省空间的同时，还能方便地执行矩阵运算。 广义表是线性表的推广，可以表示多种复杂的数据结构，如链表、树等。广义表的存储结构包括链式存储和顺序存储，其中链式存储更适合于包含不同类型的元素或子表的情况。广义表的递归算法是解决广义表问题的重要工具，如表的拼接、查找等操作。 本讲义详细阐述了数据结构中的关键概念，包括数组的定义、顺序存储、矩阵的压缩存储，特别是稀疏矩阵的十字链表表示，以及广义表的相关内容，这些都是理解并处理复杂数据结构的基础。