数据结构课件：数组与广义表解析

"该资源是严蔚敏数据结构课程的一部分，主要讲解了数组和广义表的概念，同时提及了中山大学2000年的考研真题中关于串的练习。内容涉及一维数组、二维数组、多维数组以及广义表的定义、表示和操作。" 在计算机科学中，数组是一种基础且重要的数据结构，它允许我们存储相同类型的多个数据项，并通过一个或多个下标来访问这些元素。数组通常分为一维、二维和多维数组。 一维数组，也称为线性表，其特点是数据元素按照线性顺序排列，每个元素都有唯一的索引。由于数组的内存分配通常是连续的，因此访问速度非常快。然而，由于内存布局的限制，一维数组在插入和删除操作时通常不如链表灵活，因为这可能需要移动大量元素。数组的主要操作包括初始化、销毁、读取和修改指定下标的元素。 二维数组可以看作是由多个一维数组按行或列排列形成的，每个元素由一对下标标识。它们在数学和计算机图形学等领域中有广泛应用，例如处理表格数据或坐标系统。在二维数组中，每个元素除了自身的位置外，还有两个前驱和两个后继，即在行方向和列方向上的相邻元素。 多维数组则扩展到了三个或更多维度，每个元素有多个下标。这种数据结构可以用来表示更复杂的关系，例如高维空间的数据或复杂的网格结构。在多维数组中，任何一维都可以看作是一维数组，而其他维度的数据元素则是这一维数组的实例。 广义表是数组和链表的组合，它可以包含原子（ATOM）或子列表（LIST），这使得广义表能够表示层次结构的数据。在给定的类型定义中，`elemtag`枚举用于区分元素是原子还是列表，`glnode`结构体用于存储元素的tag以及原子值或子列表的指针。这种结构使得广义表能够处理更复杂的数据结构，比如树或图的节点表示。 数组的抽象数据类型（ADT）通常包括以下基本操作： 1. `InitArray(&A,n,bound1,…,boundn)`：初始化一个n维数组A，每个维度的大小分别为bound1到boundn。 2. `DestroyArray(&A)`：释放数组A所占用的内存，清理相关资源。 3. `Value(A,&e,index1,…,indexn)`：获取或设置数组A中下标为index1到indexn的元素值。 数组和广义表的顺序表示和实现涉及如何在内存中有效地存储和访问这些数据结构，而矩阵的压缩存储则是一种优化技术，特别是在处理稀疏矩阵时，它只存储非零元素，从而节省内存。 对于中山大学2000年的考研真题，涉及的是串的练习，具体题目未给出，但串也是线性结构的一种，其操作包括连接、查找、替换等。串处理在文本处理、模式匹配等领域有广泛应用。在实际编程中，字符串通常用数组或动态分配的字符数组来实现。