中山大学考研真题：数组与广义表基础操作详解

在严蔚敏的数据结构课程中，"基本操作-严蔚敏数据结构课件05：数组和广义表"这一章节主要探讨了一维和多维数组的概念以及它们与广义表的关系。数组是一种重要的数据结构，它在编程中广泛应用，尤其是在处理线性数据时。 首先，一维数组被定义为线性表的一种简化形式，操作相对简单，主要支持通过给定下标访问和修改元素，例如`Value(A,&e,index1,…,indexn)`和`Assign(&A,e,index1,…,indexn)`函数。由于其结构限制，一维数组通常不支持动态插入和删除，这与线性表的动态特性有所区别。 二维数组则进一步扩展了这种线性关系，每个元素由两个下标标识，既可以在行方向上形成线性关系，也可以在列方向上形成。这使得二维数组可以看作是以一维数组作为数据元素的另一个线性表，具有前后继的概念。在多维数组中，如三维或更高维度，每个元素对应多个下标，这些下标之间存在线性关系，形成更复杂的层次结构。 广义表作为另一种抽象数据类型，虽然名字中包含“表”，但它并不局限于简单的线性结构，而是允许数据元素自身也是线性表，从而实现多层次的数据组织。这意味着广义表的灵活性更高，可以用来模拟复杂的数据结构。 课程中详细讲解了数组的定义，包括数据对象的表示（如`ji=0,…,bi-1,i=1,2,…,n`）和数据关系（通过`Ri`规则定义），以及关键的初始化（`InitArray`）、销毁（`DestroyArray`）和访问值（`Value`）等基本操作。 此外，还讨论了二维数组的顺序表示和实现，以及矩阵的压缩存储方法，这是为了优化存储空间，特别是当数据具有对角线稀疏性时。这些内容对于理解数组在内存管理中的效率至关重要。 总结来说，这一节深入探讨了数组作为数据结构的核心概念，不仅涉及了数组的定义、操作，还涵盖了它们如何作为线性表的扩展，以及在实际应用中的优化技巧。掌握这些知识点对于理解计算机科学中数据结构的基础，特别是数组和广义表的使用，具有重要意义。