数据结构与算法分析——严蔚敏《数据结构》C语言版讲义

"严蔚敏数据结构C语言版教材讲义，主要讲解了数据结构的概念、基本术语、抽象数据类型的表示与实现，以及算法和算法分析。内容包括数据结构的逻辑结构和物理结构，以及相关的运算。" 在计算机科学中，数据结构是组织和存储数据的方式，以便更有效地访问和修改数据。在提供的描述中，提到了一种特定的数据结构类型，即`glnode`，用于表示链表。`typedef`关键字被用来创建一个新的类型别名，`elemtag`是一个枚举类型，包含两个可能的值：`ATOM`和`LIST`。`struct glnode`定义了一个结构体，包含一个`elemtag`成员来标记节点的类型，以及一个联合体（union），该联合体可以存储原子类型（atomtype）或者一个指向其他节点的指针结构。 联合体的用途在于它可以存储不同类型的数据，这里用于处理两种情况：原子类型和链表结构。当`tag`为`ATOM`时，联合体使用`atom`部分；当`tag`为`LIST`时，使用`ptr`部分，其中`hp`（head pointer）和`tp`（tail pointer）分别指向链表的头节点和尾节点。这样的设计允许在一个结构中灵活地表示不同类型的节点，是数据结构中的典型技巧，特别是处理动态数据集合时。 数据结构的选择和设计对于算法的效率至关重要。例如，在电话号码查询系统中，数据可以组织成二维数组、表或向量。每种结构都有其特定的访问和操作优势，比如数组提供随机访问，而链表则方便插入和删除。在图书馆书目检索系统、教师资料档案管理系统或多叉路口交通灯的管理问题中，数据结构的选择也会直接影响到系统的性能和复杂性。 抽象数据类型（Abstract Data Type, ADT）是数据结构的一个高级概念，它封装了数据和操作数据的方法。ADT的定义独立于其实现，允许我们关注数据结构的功能而不是具体实现细节。例如，一个栈可以作为ADT定义，但它的实现可以是数组，也可以是链表。 算法是解决问题的具体步骤，设计时需要考虑效率和可行性。算法的效率通常通过时间复杂性和空间复杂性来衡量。例如，查找电话号码的算法可能依赖于数据结构，如果使用排序的数组，二分查找的效率会比线性查找高。同时，算法还需要考虑到存储空间的需求，尤其是在处理大量数据时。 在第一章的绪论中，数据结构课程介绍了这些问题的基本概念，旨在帮助学生理解和构建高效的程序，以应对日益复杂的信息处理需求。通过对数据结构的学习，可以更好地理解和设计针对特定问题的解决方案，从而提升软件系统的性能。