数据结构定义详解——严蔚敏《数据结构》

"严蔚敏数据结构ppt中的广义表链表结点结构" 在计算机科学中，数据结构是组织和管理数据的重要工具，它直接影响到程序的效率和性能。这里我们关注的是广义表（Generalized List）的链表结点结构，这是在数据结构中常见的非线性结构之一。在严蔚敏的《数据结构》中，广义表的链表结点被定义为一个结构体`GLNode`，包含一个标志域`tag`和一个联合体`Gdata`。 `tag`字段是一个整型变量，用来标记当前结点的类型。当`tag`等于0时，表示该结点是一个原子结点，即存储单一数据元素的结点；当`tag`等于1时，表明该结点是一个表结点，含有一个表头指针`hp`和一个表尾指针`tp`，用于连接其他结点，形成链表结构。这种设计允许广义表既可以存储单个数据元素，也可以存储嵌套的子表。 在广义表的链表结点结构中，`Gdata`是一个联合体，用于节省内存空间。如果`tag`为0，`Gdata`的`value`字段将存储原子结点的值；如果`tag`为1，`Gdata`的`ptr`结构体将包含`hp`和`tp`指针，`hp`指向子表的第一个结点，`tp`指向子表的最后一个结点。 图5-13展示了广义表结点的两种形式：(a) 原子结点，(b) 表结点。在原子结点中，只有`value`字段有效；在表结点中，`ptr.hp`和`ptr.tp`用于构建链表。 学习数据结构有助于我们理解如何高效地存储和操作数据。例如，电话号码查询系统和磁盘目录文件系统的例子展示了线性表和树形结构的应用。电话号码薄可以看作一个线性表，每个名字对应一个电话号码；而磁盘目录文件系统则涉及到更复杂的层次结构，类似一棵树，每个目录或文件可能包含子目录和文件。 在实际编程中，选择合适的数据结构对于算法的设计至关重要。比如，如果需要频繁地在数据中间插入或删除元素，链表可能比数组更适合，因为链表不需要移动大量元素。另一方面，数组在访问特定位置的元素时速度更快，适合索引访问。因此，了解并熟练掌握各种数据结构的特性，能够帮助我们编写出更加高效和灵活的代码。 《数据结构》是计算机科学的基础课程，它涵盖了诸如栈、队列、树、图、排序和查找等各种数据结构。通过学习这些概念，我们可以更好地设计和分析算法，优化程序性能，并为高级主题如编译器设计、操作系统、数据库等打下坚实基础。同时，掌握数据结构也有助于应对复杂问题，如大数据处理和云计算中的挑战。