C语言数据结构：广义表的特点与链表实现

在C语言版的《数据结构》（严蔚敏、吴伟民编著，清华大学出版社）中，章节讨论了广义表这种特殊的存储结构。广义表的特点主要体现在以下几个方面： 1. 表头指针与表尾指针: - 如果广义表为空，表头指针hp会为空。非空表头指针hp总是指向表的第一个元素，可能是原子结点（存储单个值），也可能是表结点，负责链接其他元素。 - 表尾指针tp则表示广义表的结尾。如果表尾为空，tp为NULL；否则，它指向表中的最后一个表结点。 2. 操作便捷: - 这种存储结构使得求取广义表的长度（元素个数）、深度（层数）以及访问表头和表尾都非常方便，因为只需要遍历相应指针即可。 3. 空间效率: - 虽然广义表可以表示复杂的数据结构，但当表结点过多时，可能会占用较多的空间。为减少空间浪费，有时会采用另一种更紧凑的结点结构，如图5-15所示，将表尾指针tp包含在每个表结点内。 4. 实际应用: - 数据结构这门课程关注如何用数据形式描述问题，以及如何在计算机中存储数据并体现数据之间的关系。例如，电话号码查询系统可以通过广义表的形式存储名字和电话号码，形成一对一的关系，如表1-1所示。 5. 数据结构与算法课程的地位: - 《算法与数据结构》是一门重要的计算机科学基础课程，它连接数学、硬件和软件，对于编程和系统设计至关重要，不仅对一般程序设计起基础作用，还是高级系统如编译器、操作系统和数据库设计的基础。 通过学习这些特性，学生能够更好地理解和设计高效的数据结构来解决实际问题，包括处理大量数据、组织复杂的层次关系等。例如，磁盘目录文件系统的实现就是一种典型的数据结构应用，它体现了数据间的层次关系。通过深入理解这些概念，程序员可以编写出更加高效和灵活的程序。