数据结构讲解：查找与结点类型定义

"这篇讲义主要讲解了数据结构中的结点类型定义以及查找技术，包括静态查找表和动态查找表的概念、操作以及相关的平均查找长度计算。此外，还提到了哈希表的应用，并通过学生招生录取登记表的例子来阐述关键码和记录的定义。" 在数据结构中，结点是构建数据结构的基本单元。在链式存储结构中，结点不仅包含数据元素（data），还包含指向下一个结点的指针（next）。如以下定义所示： ```c typedef struct node { int data; // 数据域，存储实际数据 struct node *next; // 指针域，指向下一个结点 } LinkNode, *LinkList; // LinkNode是结构体类型，LinkList是LinkNode类型的指针，通常用于表示链表 ``` 查找是数据处理中的常见操作，它涉及在数据集合中寻找特定信息。根据查找过程中是否能修改表，查找表可以分为静态查找表和动态查找表。静态查找表只进行查找操作，而动态查找表则允许插入和删除数据元素。 7.1 基本概念与术语： - 查找操作：查找某个特定数据元素是否存在，检索其属性，或者在表中进行插入和删除操作。 - 关键码（key）：能唯一确定数据元素的一个或多个项的值，是记录的重要标识。 - 记录：数据元素，通常包含多个字段，如例子中的学生招生录取登记表，每个记录包含学号、姓名、性别等字段。 - 查找表：由具有相同类型数据元素（记录）组成的数据集合。 7.2 静态查找表： - 顺序存储结构：一种简单的数据结构，如数组，这里用`SqList`表示，包含数据数组`data[MaxSize+1]`和记录数量`length`。 - （1）顺序表：数据按顺序存储，查找时通常采用顺序搜索，即从头到尾逐个比较。 - （2）其他可能的结构，如二分查找表，要求数据已排序，查找效率更高。 7.3 动态查找表： 动态查找表允许在查找过程中进行插入和删除操作，如二叉查找树、AVL树等，它们在保持数据有序的同时，可以快速地进行增删查改。 7.4 哈希表： 哈希表是通过哈希函数将数据映射到表的特定位置，实现快速查找。理想的哈希函数能确保数据均匀分布，减少冲突，提高查找效率。 在实际应用中，选择哪种查找表结构取决于数据的特性、预期的查找操作频率以及对空间和时间效率的需求。平均查找长度（ASL）是衡量查找效率的重要指标，它反映了在查找表中找到目标元素所需的平均比较次数。ASL的计算涉及查找表中各元素被查找的概率及其对应的比较次数。