清华大学严蔚敏教授详解广义表的存储结构特点

在《数据结构(C语言版)》这本书中，关于广义表的存储结构有以下几点重要的特点： 1. 空表与指针定义：广义表为空时，表头指针hp为空；否则，表头指针始终指向一个表结点，这个结点可能是个原子结点（存储的是基本数据类型），也可能指向另一个表结点。表头结点的下一个元素通过表头指针hp指示，表尾则通过表尾指针tp指示。当表尾为空时，tp为NULL。 2. 操作便捷性：这种存储结构使得求广义表的长度（即表结点个数，包括原子结点）和深度（即最长路径上的结点数）变得非常方便，只需要遍历即可。同时，获取表头和表尾也相对容易，只需要跟踪相应指针即可。 3. 空间效率：然而，过多的表结点可能导致空间浪费，特别是当广义表中存在大量嵌套时。为了优化，可以采用图5-15所示的结点结构，通过链式存储减少冗余。 4. 数据结构的抽象与应用：数据结构是计算机科学中的核心课程，它研究如何有效地表示和组织数据，以及如何在计算机中存储数据并体现它们之间的关系。在实际问题中，比如电话号码查询系统和磁盘目录文件系统，数据结构的应用表现为数据间的简单一对一关系（如线性表结构）和层次关系（如树形结构）。 5. 算法与数据结构的关系：数据结构是算法设计的基础，一个好的数据结构可以提高算法的效率。例如，搜索算法在不同的数据结构上执行速度可能会大相径庭，如顺序查找在数组中高效，而在链表中则较慢。 6. 编程实践：学习数据结构有助于编写程序，如确定数据的存储方式、确定合适的数据结构来支持所需的操作，以及评估程序性能。在解决实际问题时，需要从问题抽象出数学模型，考虑数据量、数据关系、存储需求和运算需求，并确保编写的程序具有良好的性能。 理解并掌握这些特点和应用实例对于理解和设计高效的算法至关重要，无论是对于日常编程还是开发复杂系统都有着深远的影响。