chapter-5数组与广义表1
第五章 数组和广义表
• 数组的类型定义（5.1 ）
数组是几乎所有程序设计语言都设定为固有类型的一种数据类型。从线性结构看，数组类型可以看作是数据元素本身还是线性结构的一个数据结构。n维数组的特点是每一个数据元素受n个线性关系的约束，在每个关系中都有唯一的直接前驱和后继。
在第五章的开头部分，我们首先进行了数组的类型定义。数组类型定义是一个抽象数据类型定义(ADT)。在该定义中，数据对象(D)是数组的元素集合，每个元素都有一组下标值用来表示其在数组中的位置。数据关系(R)是数组元素之间的线性关系，指明了每个元素的前驱和后继。同时，数组的维数和每个维度的长度也在类型定义中确定。
• 数组的顺序表示和实现（5.2）
在接下来的部分，我们介绍了数组的顺序表示和实现。数组的顺序表示可以使用一维数组或多维数组来实现。一维数组是最简单的数组形式，而多维数组通过嵌套的方式进行表示。我们探讨了数组在内存中的存储方式，以及如何通过下标索引来访问数组元素。
同时，我们还介绍了数组的初始化和赋值操作。数组的初始化包括对每个元素的赋初值，可以使用循环结构来逐个初始化数组元素。数组的赋值操作则是通过索引来指定被赋值的元素位置，然后进行赋值操作。
• 稀疏矩阵的压缩存储 （5.3）
在第五章的第三节，我们介绍了稀疏矩阵的压缩存储。稀疏矩阵是指大部分元素都为0的矩阵。由于矩阵的存储空间占用较大，而且大部分元素都为0，因此采用压缩存储可以有效节省存储空间。
稀疏矩阵的压缩存储可以采用三元组顺序表的方式进行表示。在三元组顺序表中，只记录非零元素的位置和值，而0元素不占用存储空间。这种方式可以减少存储空间的占用，并且通过特定的算法可以实现对稀疏矩阵的快速访问。
• 广义表的类型定义（5.4）
接下来，我们介绍了广义表的类型定义。广义表是一种比数组更加灵活的数据结构，可以存储不同类型的元素，并且可以嵌套存储其他广义表。广义表的类型定义是一个递归的定义，可以通过头和尾两部分来表示。
在广义表的类型定义中，头部表示广义表的第一个元素，尾部则表示剩余的广义表。通过递归的方式，可以实现对广义表的遍历和操作。
• 广义表的表示方法（5.15）
在第五章的后半部分，我们介绍了广义表的表示方法。广义表可以通过分段链表的方式进行表示。每个节点包含一个元素和指向下一个节点的指针，可以通过链表的形式实现广义表的存储和访问。
广义表的表示方法可以从逻辑上分为原子广义表和子表两种情况。原子广义表表示只有一个元素的广义表，而子表表示嵌套在广义表中的另一个广义表。
• 广义表操作的递归函数（5.6）
最后，我们介绍了广义表操作的递归函数。由于广义表的递归结构，可以使用递归函数来实现广义表的遍历和操作。
递归函数可以通过基本情况和递归情况来定义。基本情况表示递归的终止条件，递归情况表示递归函数的执行过程。通过递归函数，可以实现对广义表的遍历、查找、插入、删除等操作。
综上所述，第五章主要介绍了数组和广义表的相关概念和操作。数组是一种固有数据类型，可以通过类型定义和顺序表示来实现。稀疏矩阵的压缩存储可以有效节省存储空间。广义表是一种灵活的数据结构，可以存储不同类型的元素。通过递归函数可以实现对广义表的操作。这些内容对于理解和应用数组和广义表具有重要意义。
