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