一、实验目的
1．熟悉散列查找方法和特点。
2．掌握散列查找解决冲突的方法。
3．用C语言完成算法和程序设计并上机调试通过；
4．撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
二、实验要求
1、程序要求包含头文件以及main函数
2、实验中所设计的函数（算法）需要满足实验的要求
3、程序的编译、运行要成功通过
4、运行的结果正确，且有相应的提示
三、实验环境
WIND10、VC++6.0或C与C++程序设计学习与实验系统
四、实验内容
1．闭散列表（也称开地址方法）查找的实现
2．开散列表（也称拉链法）查找的实现
五、源代码及算法分析
1．闭散列表（也称开地址方法）查找的实现
# include# include # define MAXSIZE 20 typedef int keytype; typedef keytype HTable[MAXSIZE]; // 创建长度为m的散列表函数，p为除留余数中的除数 void creHT(HTable HT, int m, int p) { int i, n = 0; keytype x; for(i = 0; i < m; i++) HT[i] = -1; printf("Input data(-1:End):"); scanf("%d", &x); while(x != -1) { n++; if(n > m) break; i = x % p; while(HT[i] != -1) i = (i+1) % m; HT[i] = x; scanf("%d", &x); } } // 查找指定元素 int search(HTable HT, int m, keytype x, int p) { int i, j; i = x % p; j = i; while(HT[j] != -1) { if(HT[j] == x) return j; j = (j + 1) % m; if(j == i) break; } return -1; } int main() { int m, p, i, j; keytype x; HTable HT; printf("请输入散列表的长度m："); scanf("%d", &m); printf("请输入除数p(p<=m)："); scanf("%d", &p); creHT(HT, m, p); printf("请输入你要查找的元素："); scanf("%d", &x); j = search(HT, m, x, p); printf("查找的元素地址为：%d", j); }
算法思路：
（1）创建散列表：在creHT()中先对散列表进行初始化，然后依次输入关键字x，通过除留余数法计算散列地址，如果该地址已使用，则进行线形探测寻找没有被使用的地址，最后将元素存进该空闲单元。
（2）查找指定元素：在search()中先对用户要查找的元素x进行取余计算出其地址，如果在HT[]中的该地址的元素等于x，则返回该数组下标（地址），如果没有找到，则进行线形探测继续寻找，如果没有找到则返回-1。
算法分析：
（1）创建散列表creHT()的时间复杂度为：T(n)=O(n2)，空间复杂度为：S(n)=O(1)。
（2）查找指定元素search()的时间复杂度为：T(n)=O(n2)，空间复杂度为：S(n)=O(1)。
2．开散列表（也称拉链法）查找的实现
# include# include typedef int keytype; typedef struct node { keytype data; struct node *next; }slink; // 建立表长为m的散列表，p为除数 void creHT(slink *HT[], int m, int p) { int i; keytype x; slink *s; for(i = 0; i < m; i++) HT[i] = NULL; printf("Input data(-1:End):"); scanf("%d", &x); while(x != -1) { i = x % p; s = (slink *)malloc(sizeof(slink)); s->data = x; s->next = HT[i]; HT[i] = s; scanf("%d", &x); } } // 查找指定元素 int search(slink *HT[], int p, keytype x) { slink *q; int i; i = x % p; q = HT[i]; while(q) { if(q->data == x) return i; q = q->next; } return -1; } int main() { int m, p, i, j; keytype x; slink *HT[100]; printf("请输入散列表的长度m："); scanf("%d", &m); printf("请输入除数p(p<=m)："); scanf("%d", &p); creHT(HT, m, p); printf("请输入你要查找的元素："); scanf("%d", &x); j = search(HT, p, x); printf("查找的元素地址为：%d", j); }
算法思路：
（1）先定义链表结点类型slink，该结构体内包含元素data，指针域next。
（2）建立散列表：creHT()，先对散列表HT[]初始化，然后依次输入关键字x，通过除留余数法计算x的散列地址，接着生成结点，用首插法插入结点。
（3）查找指定元素search(),首先对用户输入的查找元素计算其散列地址，将该地址作为散列表HT[]的下标，然后在相应的链表中查找，在该链表中依次访问data域，如果等于x则返回该下标，如果不等于x则继续访问next，直到next为空，跳出while循环返回-1。
算法分析：
（1）建立散列表creHT()的时间复杂度为：T(n)=O(n)；空间复杂度为：S(n)=O(n)。
（2）查找指定元素search()的时间复杂度为：T(n)=O(n)；空间复杂度为：S(n)=O(n)。
六、运行测试（对实验结果进行相应分析，总结实验的心得体会，并尝试提出算法的改进意见）
1．闭散列表（也称开地址方法）查找的实现
2．开散列表（也称拉链法）查找的实现
心得体会：
通过本次实验我熟悉了散列查找方法和特点并掌握了散列查找解决冲突的方法。