试实现线性探测法的查找函数。
函数接口定义：
Position Find( HashTable H, ElementType Key );
其中HashTable是开放地址散列表，定义如下：文章来源：https://www.toymoban.com/news/detail-776488.html
#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */
typedef int ElementType; /* 关键词类型用整型 */
typedef int Index; /* 散列地址类型 */
typedef Index Position; /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;
typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
ElementType Data; /* 存放元素 */
EntryType Info; /* 单元状态 */
};
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
Cell *Cells; /* 存放散列单元数据的数组 */
};
函数Find应根据裁判定义的散列函数Hash( Key, H->TableSize )从散列表H中查到Key的位置并返回。如果Key不存在，则返回线性探测法找到的第一个空单元的位置；若没有空单元，则返回ERROR。文章来源地址https://www.toymoban.com/news/detail-776488.html
裁判测试程序样例：
#include <stdio.h>
#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */
typedef int ElementType; /* 关键词类型用整型 */
typedef int Index; /* 散列地址类型 */
typedef Index Position; /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;
typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
ElementType Data; /* 存放元素 */
EntryType Info; /* 单元状态 */
};
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
Cell *Cells; /* 存放散列单元数据的数组 */
};
HashTable BuildTable(); /* 裁判实现，细节不表 */
Position Hash( ElementType Key, int TableSize )
{
return (Key % TableSize);
}
#define ERROR -1
Position Find( HashTable H, ElementType Key );
int main()
{
HashTable H;
ElementType Key;
Position P;
H = BuildTable();
scanf("%d", &Key);
P = Find(H, Key);
if (P==ERROR)
printf("ERROR: %d is not found and the table is full.\n", Key);
else if (H->Cells[P].Info == Legitimate)
printf("%d is at position %d.\n", Key, P);
else
printf("%d is not found. Position %d is returned.\n", Key, P);
return 0;
}
/* 你的代码将被嵌在这里 */输入样例1：（注：-1表示该位置为空。下同。）
11
11 88 21 -1 -1 5 16 7 6 38 10
38
输出样例1：
38 is at position 9.
输入样例2：
11
11 88 21 -1 -1 5 16 7 6 38 10
41
输出样例2：
41 is not found. Position 3 is returned.
输入样例3：
11
11 88 21 3 14 5 16 7 6 38 10
41
输出样例3：
ERROR: 41 is not found and the table is full.
代码实现
// 在散列表 H 中查找关键字 Key 的位置，
// 如果 Key 在 H 中出现，则返回其下标；
// 如果 Key 在 H 中没有出现，则返回 H 中第一个空位置的下标；
// 如果散列表 H 已满，则返回 -1。
Position Find( HashTable H, ElementType Key )
{
int index = Hash(Key, H->TableSize); // 计算 Key 的散列值
int _size = 0; // 循环计数器
// 在未遍历整个散列表之前进行循环
while(_size<H->TableSize)
{
// 如果当前位置的状态为空（即未被占用），
// 或者当前位置的 Data 值等于要查找的关键字 Key，
// 即查找成功，返回当前位置的下标 index。
if(H->Cells[index].Info==Empty||H->Cells[index].Data==Key)
return index;
// 如果当前位置的 Data 值不等于要查找的关键字 Key，
// 继续计算下一位置的下标（使用线性探测算法）并继续查找。
index = (index+1)%H->TableSize; // 线性探测
_size ++; // 增加循环计数器的值
}
// 查找失败，返回 -1。
return ERROR;
}
到了这里，关于6-1 线性探测法的查找函数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
