十字链表算法实现与数组存储结构解析

"这篇资料主要介绍了如何通过键盘输入信息来构建十字链表的算法，以及数据结构中的数组、顺序存储结构和压缩存储等概念。" 十字链表是一种特殊的数据结构，通常用于表示二维表格，其节点包含两部分信息：行索引和列索引。在该算法中，通过非零元个数`t`和最大维度`s`(行或列的较大值)来评估时间复杂度`O(t*s)`。具体实现中，用变量`q`和`p`分别表示当前行链表的尾部和当前位置，通过比较新元素的列索引`c`与`p->col`，确定新元素的插入位置： 1. 如果`p`不为空且`c > p->col`，则`p`和`q`向右移动。 2. 插入新元素`s`： a. 如果`p`和`q`都为空，表示本行为空，将`rh[r-1]`指向`s`。 b. 如果`p`为空但`q`不为空，表示走到行末，将`q->right`设为`s`。 c. 如果`c`等于`p->col`，则更新`p->val`。 d. 如果`c < p->col`且`q`为空，那么`s`是行链表的第一个节点，令`rh[r-1] = s`且`s->right = p`。 e. 如果`c < p->col`且`q`不为空，那么在`p`之前插入`s`，即`q->right = s`且`s->right = p`。 数组是数据结构的基础，它是由相同类型的数据元素构成的有序集合。数组的特点包括结构固定，即一旦创建，大小不可变，且所有元素具有相同的类型。数组的运算主要包括根据下标存取和修改元素。顺序存储结构是数组最常见的实现方式，可以按行序或列序存储，元素的存储位置可以通过公式计算得出，例如在行序为主序的情况下，元素`a[i][j]`的位置为`Loc(a11) + [(i-1)*n + (j-1)]*l`，其中`l`是每个元素占用的存储空间。 在特定情况下，如对称矩阵、三角矩阵或对角矩阵，可以采用压缩存储技术减少存储空间。对称矩阵只需存储下三角或上三角元素，三角矩阵只存储主对角线以下或以上的元素，对角矩阵则只存储对角线元素。这些压缩存储方法显著减少了存储需求，尤其对于大型稀疏矩阵，可以极大地提高效率。