数据结构：广义表的性质与数组的定义

"这篇资料主要介绍了数据结构中的数组和广义表，特别是来自清华大学版教材的相关内容。资料中提到了数组的一维、二维以及多维形式，并深入探讨了广义表的特性，包括其多层次结构、共享性以及递归性质。此外，还强调了矩阵的压缩存储方法，如特殊矩阵和稀疏矩阵的处理。" 在数据结构领域，数组是一种基本的数据组织形式，它由相同类型的数据元素构成，并存储在同一块连续的内存空间中。一维数组可以被视为线性表，其元素通过线性关系直接计算存储地址，因此具有随机访问的能力。二维数组则进一步扩展了这个概念，形成了一个由行和列组成的结构，每个元素都有行和列的下标，可以视作由多个一维行向量或列向量组成。多维数组则将这种思想拓展到三维及以上，形成更复杂的结构。 广义表是数组概念的一种扩展，它的元素不仅可以是原子，也可以是其他子表，这使得广义表可以呈现出多层次的结构。这种结构可以用图形表示，圆圈代表列表，方块代表原子。广义表的特性包括： 1. **多层次结构**：列表的元素可以是子表，子表的元素又可以是子表，如此递归下去，形成了多级嵌套的结构。 2. **共享性**：一个列表的元素可以被其他列表共享，这意味着不同的列表可能含有相同的子表，有效地节省了存储空间。 3. **递归性**：广义表可以是自身的一个子表，即一个列表可以包含自身，形成自引用的结构，这种性质在数据结构的递归操作中十分常见。 广义表的长度定义为最外层元素的个数，不考虑嵌套的子表元素。例如，给定的广义表`e a d c b D A B C`中，最外层有7个元素。 在实际应用中，对于某些特定类型的矩阵，如稀疏矩阵（大部分元素为零），可以使用压缩存储来节约空间。例如，对于特殊矩阵，只需存储非零元素；而对于稀疏矩阵，通常使用三元组表示法（行号、列号、值）存储非零元素，大大减少了存储需求。 数组和广义表是数据结构的重要组成部分，它们为数据的组织和处理提供了灵活的手段，尤其是在处理复杂关系和大量数据时，这些结构能够有效地支持算法的实现和优化。在编程和计算机科学中，理解并熟练掌握这些基本数据结构对于解决问题至关重要。