压缩存储随机稀疏矩阵：从三元组到十字链表

"随机稀疏矩阵的压缩存储方法:-数组和稀疏矩阵（武汉大学教学PPt)" 在计算机科学中，数组是一种基础的数据结构，用于存储同类型的元素集合。数组的类型定义是描述其特性的关键步骤。在描述的文档中，数组被定义为一个抽象数据类型（ADTArray），其数据对象D由一系列元素组成，每个元素可以由多个下标标识（ji）。数据关系R定义了元素之间的关系，如相邻元素的关系。数组的基本操作包括初始化（InitArray）、销毁（DestroyArray）、获取元素值（Value）和赋值（Assign）。 数组的顺序表示和实现主要关注如何在内存中有效地存储和访问数组元素。通常，由于实际存储空间是一维的，多维数组需要通过某种映射方式转换为一维存储。这里提到了两种顺序映射方式，一种是以行序为主序，即优先考虑较低下标的维度。例如，二维数组中元素ai,j的存储位置可以通过基地址（LOC(0,0)）加上行偏移（b2 * i）和列偏移（j）的乘积来计算。这种映射方法使得同一行的元素连续存储，有利于按行进行操作。 当处理稀疏矩阵时，由于大部分元素可能是零，直接使用常规的数组表示法会浪费大量空间。因此，引入了压缩存储的方法。文档中提到了两种压缩存储方法： 1. 三元组顺序表：这种方法将非零元素存储为三元组（行号，列号，值），按照行顺序排列。这种方式节省空间，但访问效率相对较低，因为需要遍历整个三元组列表来找到特定位置的元素。 2. 十字链表：十字链表是一种更复杂的稀疏矩阵压缩存储方法，它使用链表结构来存储非零元素。每个非零元素占据一个节点，节点包含行索引、列索引和值，以及指向同一行和同一列下一个非零元素的指针。这样可以快速定位同一行或列的其他非零元素，提高了访问效率。 稀疏矩阵的压缩存储对于处理大规模的稀疏数据尤其重要，因为它们能显著减少存储需求，同时保持必要的运算性能。在计算密集型应用，如线性代数和图形处理中，这种优化是至关重要的。