严蔚敏《数据结构》数组详解与实现

"这是一份关于清华大学严蔚敏教授《数据结构》课程中的数组部分的教学笔记，涵盖了数组的类型定义、顺序表示和实现。笔记详细介绍了数组的ADT（抽象数据类型）定义，包括数据对象、数据关系以及基本操作如初始化、销毁、读取和赋值。此外，还讨论了二维数组在内存中的两种顺序映射方式——行序为主序和列序为主序，并给出了元素存储位置的计算公式。" 在计算机科学中，数据结构是组织和管理数据的重要工具，而数组是最基础的数据结构之一。严蔚敏教授的《数据结构》课程深入讲解了数组这一概念。数组是一种特殊的线性结构，它允许通过一个或多个下标来访问和操作数据元素。在本节中，数组被定义为一个多维的结构，其中每个元素都有一个唯一的下标集合来标识。 数组的抽象数据类型（ADT）定义了其数据对象和数据关系。数据对象D是由一系列元素aj,j组成，每个元素都有n维下标，且每个维度的下标范围由相应的长度bi决定。数据关系R则定义了元素之间的顺序关系，如在二维数组中，元素之间可以通过相邻下标的增减来表示。 在ADT中，定义了四个基本操作： 1. InitArray用于初始化数组，传入数组的维数n和各维长度，如果合法则创建数组并返回成功标志。 2. DestroyArray用于销毁数组，释放其所占用的内存空间。 3. Value操作用于读取数组中的元素值，传入数组引用、元素变量以及下标，如果下标合法则将元素值赋给变量并返回成功标志。 4. Assign操作用于赋值，将给定的值e赋给数组中指定下标的元素，同样需要检查下标合法性。 数组的顺序表示和实现主要涉及如何在内存中存储和访问数组元素。通常，尽管数组逻辑上是多维的，但在物理存储上是一维的。有两种常见的顺序映射方法： 1. 行序为主序，即先按行填充，然后按列填充，这种顺序有利于按行处理数据。 2. 列序为主序，即先按列填充，然后按行填充，适合按列处理数据。 例如，在行序为主序的二维数组中，元素A[i][j]的存储位置可以通过以下公式计算： LOC[i,j] = LOC[0,0] + (b2 * (i - 0) + (j - 0) * b1) 这里的LOC[0,0]是数组第一元素的存储位置，b1和b2分别是数组的行长度和列长度。这种映射方式简化了对数组元素的访问，因为可以快速定位到任何元素的位置。 理解数组的这些概念对于学习和应用数据结构至关重要，特别是在算法设计、数据库管理、图像处理等领域。通过严蔚敏教授的讲解，学习者可以更好地掌握数组的理论知识和实际操作技巧。