稀疏矩阵压缩存储：十字链表介绍

"稀疏矩阵M的十字链表是数据结构中的一种压缩存储方式，尤其适用于处理大量元素为0的矩阵。本讲义主要讲解了数据结构中的数组、矩阵的压缩存储以及广义表的相关概念。数组作为一种基本的数据结构，其维数固定，元素通过下标访问。二维数组可以映射为一维数组，通过行优先或列优先的方式存储。在顺序存储中，数组元素的存储地址可以通过公式计算得出。对于矩阵，尤其是稀疏矩阵，压缩存储如十字链表可以节省大量的存储空间。矩阵的压缩存储主要针对特殊矩阵，例如对称矩阵，其中多个相同元素或零元素可以共享存储空间。此外，讲义还涉及到了广义表的定义和存储结构，以及m元多项式的表示和递归算法。" 在数据结构中，数组是一种非常基础且重要的数据组织形式。数组定义时的维数是固定的，并且其数据元素由值和下标共同标识。数组可以被视为一系列的线性表，每个元素都可以看作是一个列向量或行向量。在二维数组中，每一行可以看作是一维数组，而整个二维数组则可以视为由这些一维数组组成的数组。在编程中，可以使用typedef来定义不同维度的数组类型。 数组的操作主要是存取和修改元素，这些操作可以通过给定下标来完成。顺序存储是数组常用的一种存储方式，因为数组不涉及插入和删除操作，因此顺序存储结构最为合适。顺序存储包括行优先和列优先两种方式，行优先是将数组元素按照行的顺序依次存储，而列优先则是按照列的顺序存储。 数组元素的存储地址可以通过一定的公式计算得到，例如对于二维数组，元素的地址可以通过行号和列号计算。矩阵的压缩存储针对的是特殊矩阵，如稀疏矩阵，其中大部分元素为0。稀疏矩阵的十字链表存储方式能够有效减少存储空间的占用，只存储非零元素，通过链接结构记录元素的位置信息。 此外，讲义还提到了广义表，它是一种可以包含其他表的表，具有递归结构。广义表的存储结构通常有链式存储和顺序存储两种。同时，m元多项式的表示也有所提及，这涉及到多项式的系数和指数的表示方法。最后，广义表的递归算法是处理复杂数据结构时的重要工具，它利用了广义表自身的递归性质来实现算法。