xxx大学实验报告
课程名称 数据结构 实验项目 实验三 查找和排序(一)——查找 院 系 信息学院计类系 专业班级 计类1501 姓 名 学 号 指导老师 日 期
批改日期 成 绩
一 实验目的
1．掌握哈希函数——除留余数法的应用； 2. 掌握哈希表的建立； 3. 掌握冲突的解决方法； 4. 掌握哈希查找算法的实现。
二 实验内容及要求
实验内容：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数定义为：H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列，并计算平均查找长度（设每个记录的查找概率相等）。
实验要求：1. 哈希表定义为定长的数组结构；2. 使用线性探测再散列或链地址法解决冲突；3. 散列完成后在屏幕上输出数组内容或链表；4. 输出等概率查找下的平均查找长度；5. 完成散列后，输入关键字完成查找操作，要分别测试查找成功与不成功两种情况。
注意：不同解决冲突的方法会使得平均查找长度不同，可尝试使用不同解决冲突的办法，比较平均查找长度。（根据完成情况自选，但至少能使用一种方法解决冲突）
三 实验过程及运行结果
#include
#define q 13 int 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); } else {
H[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) {
printf(\位置\\t 数据\\n\
printf(\ return 1; } else
judge(H,num,n); }
int search(char num,HashNode H[]) //查找 {
int n;
n= num % q;
if(H[n].sign==0) {
printf(\失败\ return 0; }
if(H[n].sign!=0&&H[n].date==num) {
printf(\位置\\t 数据\\n\
printf(\ }
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 printf(\位置\\t 数据\\n\\n\ for(int i=0;i } { if(H[i].sign!=0) { printf(\ } else { H[i].date=0; printf(\ } } int num; printf(\请输入查找数值（‘-1’查找完成）:\\n\for(int i=0;;i++) { scanf(\ if(num==-1) break; if(search(num,H)==0) printf(\不存在\\n\} for(int i=0;i printf(\ a=a+H[i].sign; } printf(\ printf(\平均查找长度：%0.2f\\n\return 0; 四 调试情况、设计技巧及体会 首先得确定哈希函数，虽然冲突是无法避免的，但是我们应该选择合适的 函数，减少冲突，最简单的可以采用开放定止法，出现冲突后，以原地址为基点再次寻找下一个地址。 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库河南工业大学实验报告_实验三 查找和排序(一)——查找在线全文阅读。
相关推荐：
