数据结构第五章：数组与广义表的存储解析

"《数据结构》第五章讲义主要涵盖了数组和广义表的概念、存储结构及基本操作。数组是一种特殊的线性结构，其元素通过下标进行区分，具有统一的数据类型。广义表则是一种多层次的线性结构，可以包含其他广义表，形成嵌套结构。" 在数据结构中，数组是一种基础且重要的结构，它由一组具有相同名字但下标不同的变量组成。数组的维数和维界的确定性使得其在内存中的布局通常是连续的，这有利于快速访问和操作。例如，二维数组可以视为行或列的线性表示，元素之间的关系既有行关系也有列关系。数组的处理相对简单，主要操作包括初始化、元素存取和修改。 数组的顺序存储表示和实现是通过将多维数组按照特定顺序排列成一维序列，然后在计算机的一维存储空间中顺序存放。对于二维数组，通常有两种存储方式：行主序和列主序，分别按照行或列的顺序存储元素。例如，一个m×n的二维数组可以看作是m个长度为n的一维数组的集合，或者n个长度为m的一维数组的集合。 接下来，讲义提到了矩阵的压缩存储，尤其是对于特殊矩阵和稀疏矩阵的处理。特殊矩阵如对角矩阵、单位矩阵等可以通过特定的编码方式减少存储空间。稀疏矩阵是指非零元素远少于总元素数的矩阵，常使用三元组表示法，存储每非零元素的行号、列号和值，这样可以大大节省存储空间。 然后，广义表作为本章的重点，是一个可以包含其他广义表的线性结构，允许数据的多层次嵌套。广义表的定义包括原子和子表两种基本元素。在存储结构上，可以采用链式存储，便于处理嵌套的情况。广义表的基本操作包括创建、查询、修改和删除，以及获取表头和表尾等。递归算法在处理广义表时尤其重要，特别是对于嵌套结构的遍历和操作。 学习本章需要掌握的关键点包括：数组的定义和运算、特殊矩阵的压缩存储、稀疏矩阵的三元组表示及其运算、广义表的定义和存储结构，以及如何进行广义表的基本操作。理解三元组表示稀疏矩阵时的运算处理方法和广义表的递归算法是学习的难点。 数据结构第五章讲解了数组和广义表的理论与实践，为理解和实现复杂的数据结构奠定了基础，对计算机科学和软件工程领域的程序员来说是至关重要的知识。