数据结构C语言版讲义-严蔚敏

"严蔚敏《数据结构（C语言版）》讲义是关于学习数据结构的提纲，涵盖了数据结构的基本概念、术语、抽象数据类型的表示与实现、算法和算法分析等内容。" 《数据结构（C语言版）》是由严蔚敏编著的一本经典教材，对于计算机科学的学习者来说，数据结构是必不可少的知识领域。本书通过清晰的讲解和实例，帮助读者理解数据结构的本质和应用。 1. **什么是数据结构** 数据结构是研究数据的组织方式、存储和访问的方法。在计算机科学中，数据结构是程序设计的基础，它涉及如何有效地存储和操作数据。例如，电话号码查询系统中的名字和电话号码可以组织成二维数组、表结构或向量，不同的结构会影响查找算法的效率。数据结构不仅包括数据的逻辑结构，还涉及数据在内存中的物理存储方式，以及对这些结构进行操作的算法。 2. **基本概念和术语** - **逻辑结构**：数据元素之间的逻辑关系，独立于存储硬件，如线性结构、树形结构、图形结构等。 - **物理结构**：数据在内存中的实际存储方式，如顺序存储、链式存储等。 - **数据元素**：数据的基本单位，可以是单一的值或更复杂的数据结构。 - **数据项**：数据元素的不可分割的部分。 - **抽象数据类型（ADT）**：一种逻辑上的数据类型，定义了数据的操作而不考虑其内部实现。 - **数据操作**：对数据结构执行的运算，如插入、删除、查找等。 3. **抽象数据类型的表示与实现** 抽象数据类型允许我们专注于数据结构的逻辑特性，而无需关心底层的实现细节。C语言中，可以通过结构体和指针来实现ADT。例如，可以定义一个结构体来表示电话簿条目，包含姓名和电话两个字段，然后通过指针操作这些结构体来实现数据结构的运算。 4. **算法和算法分析** - **算法**：解决问题或完成特定任务的精确步骤集合。 - **算法设计**：创建有效、简洁的算法。 - **算法效率的度量**：通常通过时间复杂度和空间复杂度来评估，时间复杂度表示算法运行时间与输入数据规模的关系，空间复杂度则表示算法在运行过程中所需的内存空间。 - **算法的存储空间需求**：考虑算法执行时需要的额外内存空间。 5. **实例解析** - **电话号码查询系统**：展示了数据结构在信息检索中的应用，强调了选择合适数据结构对算法效率的重要性。 - **图书馆的书目检索系统自动化**：类似的问题，体现了数据结构在信息管理中的作用。 - **教师资料档案管理系统**：进一步说明了数据结构在实际管理系统中的应用。 - **多叉路口交通灯的管理问题**：揭示了数据结构在解决复杂系统控制问题中的角色。 通过学习严蔚敏《数据结构（C语言版）》讲义，读者可以掌握数据结构的核心概念，学会分析和设计适用于各种问题的高效算法，为编写高质量的计算机程序打下坚实基础。