数据结构：广义表的链表存储结构与ADT概念解析

"数据结构 严蔚敏版" 在数据结构领域，广义表是一种重要的抽象数据类型（ADT），它可以用来表示嵌套序列。在严蔚敏版的数据结构教材中，广义表的存储结构被详细阐述。广义表可能包含原子（基本单元）和子表，具有以下特点： 1. 空广义表与表头指针：如果广义表为空，表头指针为空。否则，表头指针总是指向一个表结点。这个表结点可以是一个原子结点或另一个表结点，其中`hp`指针指向广义表的表头，而`tp`指针则指向表尾。若表尾为空，`tp`指针为空；否则，它指向另一个表结点。 2. 操作效率：这种存储结构使得对广义表的常见操作如获取长度、深度、表头和表尾变得非常高效。例如，通过表头指针可以直接访问到表的第一个元素，而表尾指针则能快速定位到最后一个元素或子表。 3. 空间效率：然而，由于每个表结点都需要额外的指针字段，当广义表中包含大量原子时，可能会造成空间的浪费。为了优化空间使用，可以采用如图5-15所示的结点结构，其中原子结点仅包含一个标记`tag=0`和一个值，而表结点包含`tag=1`、表头指针`hp`和表尾指针`tp`。 在实际应用中，数据结构的设计往往与特定问题紧密相关。例如，电话簿查找系统需要设计一个算法，能够在给定姓名时快速找到对应的电话号码，如果不存在则返回相应标志。类似的应用还包括图书馆的书目检索、教师资料管理系统和交通灯控制等，这些都需要高效的数据结构和算法来支持。 ADT（Abstract Data Type）是一种更高层次的数据类型概念，不仅包括系统预定义的类型，还允许用户自定义数据类型。ADT由三部分组成：定义、表示和实现。其核心特性是抽象和信息隐蔽。抽象意味着只关注问题的关键方面，忽略非关键细节，从而提高代码的通用性和可复用性。信息隐蔽则确保用户仅通过接口与数据交互，而不需关心底层实现细节。 举例来说，整数ADT包括整数的概念和与之相关的算术运算。在C语言中，数组是另一种常见数据结构，其下标从0开始。顺序存储的线性表（如数组）的优点在于随机访问速度快，但插入和删除操作可能涉及大量元素的移动，可能导致空间浪费和难以扩展。 在讲解数据结构时，通常会涉及各种指针操作，包括赋值、解引用、指针的加减运算以及动态内存分配等，这些都是理解复杂数据结构和算法的基础。