河南工业大学试验报告_试验三查找和排序一——查找

1、xxx 大学实验报告 ) 查找 查找和排序 ( 一课程名称数据结构实验项目 实验三1501计类信息学院计类系专业班级院系号学姓名期日指导老师绩成批改日期实验目的一1 掌握哈希函数除留余数法的应用； 2.掌握哈希表的建立；3. 掌握冲突的解决方法；4. 掌握哈希查找算法的实现。实验内容及要求二 哈希，实验内容：已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)。实现该哈希表的散列，并 m=16函数定义为： H(key)=key MOD 13,哈希表长为 。计算平均查找长度（设每个记录的查找概率相等）使用线性探测再散列或链2.1. 哈希表定义为定长的数组结构；

2、 实验要求：输出等概率散列完成后在屏幕上输出数组内容或链表； 4. 地址法解决冲突； 3.完成散列后，输入关键字完成查找操作，要分别测查找下的平均查找长度；5.试查找成功与不成功两种情况。可尝试使用不同解决不同解决冲突的方法会使得平均查找长度不同，注意： （根据完成情况自选，但至少能使用一种方法冲突的办法，比较平均查找长度。解决冲突） 实验过程及运行结果三#include<stdio.h>#include <stdlib.h>#include <string.h>#define hashsize 16#define q 13int sign=2;typede

3、f struct Hash值域 / int date;/ 标记 int sign; HashNode;线性冲突处理 void compare(HashNode H,int p,int i,int key)/p+;if(Hp.sign!=0)sign+;compare(H,p,i,key);elseHp.date=keyi;Hp.sign=sign;sign=2;void Hashlist(HashNode H,int key)int p;for(int i=0;i<12;i+)p=keyi%q;if(Hp.sign=0)Hp.date=keyi;Hp.sign=1;elsecompare

4、(H,p,i,key);查找冲突处理int judge(HashNode H,int num,int n)/n+;n);if(n>=hashsize) return 0;if(Hn.date=num)牰湩晴尨printf(%dt %dnn,n,Hn.date);位置 t数据return 1;elsejudge(H,num,n);int search(char num,HashNode H)/查找int n;n= num % q;if(Hn.sign=0)牰湩晴尨失败);return 0;if(Hn.sign!=0&&Hn.date=num)数据 t牰湩晴尨位置 n);pr

5、intf(%dt %dnn,n,Hn.date);else if(Hn.sign!=0&&Hn.date!=num)if(judge(H,num,n)=0)return 0;return 1;int main(void)int keyq=19,14,23,1,68,20,84,27,55,11,10,79;float a=0;HashNode Hhashsize;for(int i=0;i<hashsize;i+)Hi.sign=0;Hashlist(H,key); 数据 nn);t 牰湩晴尨 位置 for(int i=0;i<hashsize;i+)if(Hi.s

6、ign!=0)printf(%dt %dn,i,Hi.date);elseHi.date=0;printf(%dt %dn,i,Hi.date);intnum; ' 查找完成） :n);请输入查找数值（ -1 牰湩晴尨for(inti=0;i+)scanf(%d,&num);if(num=-1)break;if(search(num,H)=0)不存在 n);牰湩晴尨for(inti=0;i<hashsize;i+)printf(%d ,Hi.sign);a=a+Hi.sign;printf(%2.0f,a); %0.2fn,a/12); 平均查找长度：牰湩晴尨 return