清华大学严蔚敏数据结构讲义解析

"tsinghua严版教材讲义.ppt - 清华大学严蔚敏数据结构课程的PPT讲义，涵盖了数据结构的基本概念、术语、抽象数据类型的表示与实现，以及算法和效率分析等内容。" 在计算机科学中，数据结构是至关重要的一个领域，它研究的是数据的组织方式，即数据的逻辑结构和物理存储形式，以及在此基础上定义的运算。清华大学严蔚敏教授的数据结构课程深入浅出地讲解了这一主题。首先，课程引出了数据结构的概念，通过电话号码查询系统、图书馆书目检索系统、教师资料档案管理和多叉路口交通灯管理等实际问题，阐述了数据结构在解决问题中的作用。 1.1 什么是数据结构 数据结构不仅仅是数据的简单集合，而是数据之间的关联和组织方式。例如，在电话号码查询系统中，数据可以组织成二维数组、表结构或向量。不同的数据结构会影响算法的设计和效率。数据结构包括逻辑结构（数据元素之间的逻辑关系）和物理结构（数据在内存中的实际存储方式）。 1.2 基本概念和术语 - 数据(Data)：是计算机处理的对象，可以是数字、字符、图像等各种形式。 - 结构(Structure)：数据元素之间的相互关系，如线性结构、树形结构、图结构等。 - 数据类型(DataType)：一组值的集合以及定义在这些值上的操作。 - 抽象数据类型(ADT，Abstract Data Type)：从用户的角度定义数据类型，不涉及具体实现细节，只关注能进行的操作和操作的效果。 - 数据元素(Data Element)：数据的基本单位，可以是一个数据项或由多个数据项组成的数据结构。 - 算法(Algorithm)：一系列清晰定义的步骤，用于解决特定问题或执行特定任务。 1.3 抽象数据类型的表示与实现 抽象数据类型通过接口（数据类型的操作集）和实现（如何在内存中存储数据并执行操作）来定义。实现可以是直接的，如数组、链表，也可以是间接的，如堆、栈和队列等。 1.4 算法和算法分析 1.4.1 算法：解决问题或执行任务的一系列明确指令，具有输入、输出、有限性、确定性和可行性等特性。 1.4.2 算法设计的要求：简洁性、正确性、可读性、健壮性等。 1.4.3 算法效率的度量：主要通过时间复杂度和空间复杂度来评估，衡量算法运行时间和所需存储空间。 1.4.4 算法的存储空间需求：除了算法运行时的计算资源外，还需要考虑数据结构的存储需求。 通过对这些概念的深入理解和应用，开发者能够更有效地设计和实现程序，提高程序的性能和可维护性。严蔚敏教授的数据结构课程为学生提供了扎实的基础，有助于他们在后续的学习和工作中更好地解决实际问题。