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. 哈希表定义为定长的数组结构；实验要求：输出等概率散列完成后在屏幕上输出数组内容或链表；4. 地址法解决冲突；3.完成散列后，输入关键字完成查找操作，要分别测查找下的平均查找长度；5. 试查找成功与不成功两种情况。
可尝试使用不同解决不同解决冲突的方法会使得平均查找长度不同，注意：（根据完成情况自选，但至少能使用一种方法冲突的办法，比较平均查找长度。
解决冲突）实验过程及运行结果三#include<stdio.h>#include <stdlib.h>#include <string.h>#define hashsize 16#define q 13int sign=2;typedef struct Hash{值域 // int date; //标记 int sign;}HashNode;线性冲突处理void compare(HashNode H[],int p,int i,int key[]) // { p++; if(H[p].sign!=0) { sign++;compare(H,p,i,key);}elseH[p].date=key[i];H[p].sign=sign; sign=2;}}void Hashlist(HashNode H[],int key[]){ int p;for(int i=0;i<12;i++) {p=key[i]%q; if(H[p].sign==0) { H[p].date=key[i];H[p].sign=1;}else compare(H,p,i,key);}}查找冲突处理int judge(HashNode H[],int num,int n) //{n++; if(n>=hashsize) return 0; if(H[n].date==num) {位置\t 数据\n); 牰湩晴尨 printf(%d\t %d\n\n,n,H[n].date);return 1;}elsejudge(H,num,n);}int search(char num,HashNode H[]) //查找{ int n;n= num % q;if(H[n].sign==0) {牰湩晴尨失败);return 0; } if(H[n].sign!=0&&H[n].date==num) {数据\t 牰湩晴尨位置\n);printf(%d\t %d\n\n,n,H[n].date);} else if(H[n].sign!=0&&H[n].date!=num) {if(judge(H,num,n)==0) return 0;}return 1;}int main(void){ int key[q]={19,14,23,1,68,20,84,27,55,11,10,79}; float a=0;HashNode H[hashsize];for(int i=0;i<hashsize;i++)H[i].sign=0;Hashlist(H,key);数据\n\n);\t 牰湩晴尨位置 for(inti=0;i<hashsize;i++){if(H[i].sign!=0){printf(%d\t %d\n,i,H[i].date);else{H[i].date=0;printf(%d\t %d\n,i,H[i].date);} } int num;'查找完成）:\n); 请输入查找数值（‘-1牰湩晴尨for(int i=0;;i++){scanf(%d,&num);if(num==-1)break;if(search(num,H)==0)不存在\n); 牰湩晴尨 } for(inti=0;i<hashsize;i++){printf(%d ,H[i].sign);a=a+H[i].sign; } printf(\%2.0f,a);%0.2f\n,a/12);平均查找长度：牰湩晴尨return 0;}四调试情况、设计技巧及体会首先得确定哈希函数，虽然冲突是无法避免的，但是我们应该选择合适的函数，减少冲突，最简单的可以采用开放定止法，出现冲突后，以原地址为基点再次寻找下一个地址。
