"这篇讲义主要讲解了数据结构中的结点类型定义以及查找技术，包括静态查找表和动态查找表的概念、操作以及相关的平均查找长度计算。此外，还提到了哈希表的应用，并通过学生招生录取登记表的例子来阐述关键码和记录的定义。"
在数据结构中，结点是构建数据结构的基本单元。在链式存储结构中，结点不仅包含数据元素（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的计算涉及查找表中各元素被查找的概率及其对应的比较次数。
我的内容管理
展开
