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

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 #include #include #define hashsize 16

#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;

四 调试情况、设计技巧及体会

首先得确定哈希函数，虽然冲突是无法避免的，但是我们应该选择合适的

函数，减少冲突，最简单的可以采用开放定止法，出现冲突后，以原地址为基点再次寻找下一个地址。

本文来源：https://www.bwwdw.com/article/57x.html