严蔚敏《数据结构（C语言版）》讲义

《数据结构（C语言版）》是计算机科学领域内一门非常重要的课程，尤其对于初学者而言，它提供了理解和掌握数据组织方式的基础。本课程由严蔚敏教授编著，主要聚焦于C语言环境下数据结构的教学，是学习数据结构理论与实践的优秀教材。 ### 重要知识点 #### 1.1 什么是数据结构 数据结构指的是数据元素的集合以及它们之间的关系，这些关系决定了数据的逻辑结构和物理结构。数据结构不仅关注数据的存储，还涉及数据的组织和处理方式，直接影响算法的效率和程序的质量。例如，在电话号码查询系统中，如何存储和组织名字与电话号码的数据，直接影响查找算法的效率和系统的性能。 #### 1.2 基本概念和术语 - **数据**：用于表示信息的符号集合，是计算机处理的对象。 - **数据元素**：数据的基本单位，如单个数值或字符，在程序中通常作为一个整体处理。 - **数据项**：数据的最小单位，不可再分。 - **数据对象**：具有相同性质的数据元素的集合。 - **数据结构**：一组数据元素以及它们之间的关系，分为逻辑结构和物理结构。逻辑结构描述数据之间的关联，物理结构则是数据在计算机内存中的实际存储方式。 数据结构的基本类型包括： - **集合结构**：数据元素之间无特定关系，仅共享同一属性。 - **线性结构**：数据元素之间存在一对一的关系，如链表、数组。 - **树型结构**：数据元素之间存在一对多的关系，如树结构。 - **图状结构**：数据元素之间存在多对多的关系，如图结构。 #### 1.3 抽象数据类型的表示与实现 抽象数据类型（ADT）是数据结构的高级抽象，它定义了数据的逻辑结构以及在该结构上可以执行的操作。ADT由数据对象的集合、关系的集合以及操作的集合构成，不涉及具体实现细节，为用户提供了一种清晰、独立于实现的接口。例如，栈和队列都是常见的ADT。 #### 1.4 算法和算法分析 - **算法**：解决特定问题的明确步骤和过程，是计算思维的核心。 - **算法设计的要求**：包括正确性、效率、健壮性和可读性等。 - **算法效率的度量**：通常采用时间复杂度和空间复杂度来衡量算法的效率，前者关注算法执行所需时间的增长率，后者关注算法执行所需的额外空间。 - **算法的存储空间需求**：算法的空间效率也是评价算法好坏的重要标准之一，特别是在资源受限的环境中更为关键。 ### 存储结构 数据结构的存储实现有两种主要方式： - **顺序存储结构**：利用连续的存储单元存储数据元素，数据元素之间的逻辑关系由它们在存储器中的相对位置决定。 - **链式存储结构**：通过附加的指针字段表示数据元素之间的逻辑关系，每个元素可能包含指向其他元素的链接，如链表。 ### 结论 严蔚敏的《数据结构（C语言版）》讲义深入浅出地介绍了数据结构的基础概念、分类以及实现方式，强调了数据结构对于算法设计和程序优化的重要性。通过学习本课程，学生不仅可以掌握数据组织和处理的基本技能，还能培养出解决复杂问题的能力，为后续深入学习计算机科学的其他领域打下坚实的基础。