清华大学严蔚敏数据结构.ppt

数据结构是计算机科学中至关重要的基础课程，主要探讨如何有效地组织和操作数据。严蔚敏教授的《数据结构》是该领域内的经典教材，广泛应用于中国高校的教学。本课件聚焦于数据结构的基本概念、术语及其重要性。 1.1 什么是数据结构 数据结构指的是数据元素之间的相互关系，它不仅包含数据的逻辑结构，还涉及数据的物理存储方式。例如，电话号码查询系统中，名字和电话号码可以表现为二维数组、表结构或向量。不同的数据结构会影响查询算法的设计和执行效率。数据结构的设计应提供一系列操作，确保经过这些操作后数据结构的完整性。 1.2 基本概念和术语 - 数据(Data)：是信息的符号表示，是计算机程序处理的对象。 - 数据元素(Data Element)：数据的基本单位，可作为一个整体处理。 - 数据项(Data Item)：数据元素的不可分割最小单位。 - 数据对象(Data Object)：性质相同的数据元素集合，是数据的一个子集。 - 数据结构(Data Structure)：数据元素间存在特定关系的集合，包括逻辑结构和物理结构。 - 逻辑结构：数据元素间的抽象关系，如集合、线性结构、树型结构和图状结构。 - 物理结构：数据在计算机内存中的实际存储形式。 数据结构的形式定义为一个二元组(D, S)，其中D是数据元素的有限集，S是D上的关系集合。例如，复数数据结构可以表示为(C, R)，C是复数集合，R是定义在C上的关系集合。 1.3 抽象数据类型(ADT)的表示与实现 抽象数据类型是逻辑结构的一种形式化描述，不涉及具体实现细节。它定义了一组操作以及这些操作作用于的数据集合。实现ADT时，需要考虑如何在计算机内存中存储数据以支持ADT的操作。 1.4 算法和算法分析 - 算法：解决问题的明确规范，有有限步骤且每个步骤都是清晰的。 - 算法设计要求：正确性、可行性、效率、健壮性等。 - 算法效率的度量：通常使用时间复杂度和空间复杂度来评估算法运行速度和内存需求。 - 算法的存储空间需求：除了算法执行时的空间，还包括数据结构占用的空间。 在计算机科学中，理解数据结构和算法是至关重要的，因为它们直接影响程序的性能和可维护性。通过学习严蔚敏教授的《数据结构》，学生可以掌握如何选择和设计合适的数据结构来解决各种计算问题，同时提高编程技巧和问题解决能力。