"这是一份关于清华大学严蔚敏教授《数据结构》课程中的数组部分的教学笔记,涵盖了数组的类型定义、顺序表示和实现。笔记详细介绍了数组的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分别是数组的行长度和列长度。这种映射方式简化了对数组元素的访问,因为可以快速定位到任何元素的位置。
理解数组的这些概念对于学习和应用数据结构至关重要,特别是在算法设计、数据库管理、图像处理等领域。通过严蔚敏教授的讲解,学习者可以更好地掌握数组的理论知识和实际操作技巧。