严蔚敏数据结构课件：信息处理与数据结构的关系

"清华大学严蔚敏数据结构课件，涵盖了数据结构的基本概念、术语、抽象数据类型及其表示与实现，以及算法设计与效率分析。课件以PPT格式呈现，适合配合教学视频学习。" 在计算机科学中，数据结构是至关重要的一环，它涉及到如何有效地组织和存储数据，以便于数据的访问和处理。严蔚敏教授的数据结构课程从第一章绪论开始，深入浅出地讲解了这一主题。 1.1 什么是数据结构 数据结构不仅关注数据本身，更关注数据之间的关系。例如，在电话号码查询系统中，数据结构可以是二维数组、表或向量，不同的结构会影响查找算法的效率。数据的逻辑结构描述了数据元素之间的逻辑关系，而物理结构则关注数据在内存中的实际存储方式。 1.2 基本概念和术语 - 数据(Data)：是信息的载体，可以是数字、字符、图像等各种形式。 - 数据元素(Data Element)：数据的基本单位，可以是简单数据类型，也可以是复杂的数据结构。 - 数据项(Data Item)：构成数据元素的不可分割的最小单位。 - 结构(Structure)：数据元素的集合，以及元素间的关系。 - 逻辑结构(Logical Structure)：从用户角度看数据的组织方式，如线性结构、树形结构、图结构等。 - 物理结构(Physical Structure)：数据在计算机存储器中的实际存储形式，如顺序存储、链式存储等。 - 抽象数据类型(ADT, Abstract Data Type)：包括数据的逻辑结构和相关的操作集合，如栈、队列、树、图等。 - 类型(Type)：数据的一种分类，如整型、浮点型等。 - 数据对象(Data Object)：具有相同类型的数据元素的集合。 1.3 抽象数据类型的表示与实现 ADT的表示通常涉及接口（定义了可用的操作）和实现（具体的数据结构和算法）。例如，链表是一种实现方式，它提供了插入、删除等操作的实现。 1.4 算法和算法分析 - 算法(Algorithm)：解决特定问题的明确、有限的计算序列。 - 算法设计的要求：正确性、可读性、健壮性、效率。 - 算法效率的度量：主要通过时间复杂度和空间复杂度来评估，比如O(n)、O(n²)等。 - 算法的存储空间需求：除了考虑运行时的内存占用，还包括存储数据结构所需的内存。 课件还通过实例，如图书馆书目检索系统、教师资料档案管理系统和多叉路口交通灯的管理问题，进一步阐述了数据结构在实际问题中的应用。学习这些概念和实例有助于理解如何选择合适的数据结构以优化算法性能，提高程序效率。