严蔚敏老师的课件（chap5.ppt）

这可是及其珍贵的资料，是严老师（就是我的老师的老师）<br><br>亲自编写的！以我老师的说法是：这个课件严老师不喜欢外<br><br>传的！不过，我想和大家分享，就偷偷的发了！尽情享受吧<br><br>！ 在IT领域，数据结构与算法是计算机科学的基础，它们直接影响着程序的效率和设计。严蔚敏老师的课件，特别是“chap5.ppt”，详细介绍了数组、稀疏矩阵和广义表等重要的数据结构概念。 我们关注数组的类型定义。数组是一种数据结构，其中的数据元素具有相同的类型，并且可以通过一个或多个整数索引来访问。在ADT（抽象数据类型）Array的定义中，数据对象D由一系列aj表示，每个元素可以是0到bi-1的值，其中i是数组的维度。数据关系R则定义了如何通过索引移动到相邻元素。基本操作包括初始化数组、销毁数组、获取元素值以及分配新值。初始化操作创建指定维数和大小的数组，销毁操作释放数组占用的内存，获取元素值操作用于读取特定位置的元素，而分配操作则是用来修改元素值。 二维数组作为特殊的数组形式，其数据对象是所有aij，下标范围限制在0到对应维度的边界内。数据关系ROW和COL分别代表按行和列移动的操作。数组的顺序表示和实现是指如何在实际的一维存储空间中映射多维数组。两种主要的顺序映射方式是“行序为主序”和“列序为主序”。行序为主序意味着先按照较低的下标遍历，而列序为主序则先按照较高的下标遍历。这两种方式决定了数组元素在内存中的存储顺序。 对于二维数组，元素ai,j的存储位置可以用基地址LOC(0,0)加上计算得到的偏移量。例如，对于“行序为主序”，偏移量等于(b2 * i + j) * L，其中L是元素的大小；而在“列序为主序”中，偏移量是(b1 * j + i) * L。这种线性映射关系对于理解和优化数组操作至关重要，尤其是在考虑内存访问效率时。 此外，课件还提到了稀疏矩阵的压缩存储和广义表的概念，这些都是高级数据结构的主题。稀疏矩阵在大多数元素为零的情况下，可以节省大量存储空间，通过仅存储非零元素及其对应的行和列索引来实现。广义表则是一种更灵活的数据结构，它可以表示具有任意复杂结构的列表，包括链式结构和递归结构。广义表的类型定义和表示方法，以及它的操作，如递归函数，是理解动态数据结构和算法设计的关键。 严蔚敏老师的课件涵盖了数组的基本概念，包括类型定义、顺序表示和实现，这些内容是深入学习数据结构与算法的基础。理解这些知识对于任何从事编程和系统设计的人都至关重要，因为它们是构建高效算法和软件系统的核心。