数据结构哈希表,急对以下关键字序列建立哈希表{16,29,45,37,58,55,49,26,50,24,36,38},要求填充率为80%,用二次探测再散列法处理冲突:请给出哈希函数,画出此哈希表,并计算在等概率情况下查找成功
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 03:55:36
![数据结构哈希表,急对以下关键字序列建立哈希表{16,29,45,37,58,55,49,26,50,24,36,38},要求填充率为80%,用二次探测再散列法处理冲突:请给出哈希函数,画出此哈希表,并计算在等概率情况下查找成功](/uploads/image/z/10230472-64-2.jpg?t=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%93%88%E5%B8%8C%E8%A1%A8%2C%E6%80%A5%E5%AF%B9%E4%BB%A5%E4%B8%8B%E5%85%B3%E9%94%AE%E5%AD%97%E5%BA%8F%E5%88%97%E5%BB%BA%E7%AB%8B%E5%93%88%E5%B8%8C%E8%A1%A8%7B16%2C29%2C45%2C37%2C58%2C55%2C49%2C26%2C50%2C24%2C36%2C38%7D%2C%E8%A6%81%E6%B1%82%E5%A1%AB%E5%85%85%E7%8E%87%E4%B8%BA80%25%2C%E7%94%A8%E4%BA%8C%E6%AC%A1%E6%8E%A2%E6%B5%8B%E5%86%8D%E6%95%A3%E5%88%97%E6%B3%95%E5%A4%84%E7%90%86%E5%86%B2%E7%AA%81%EF%BC%9A%E8%AF%B7%E7%BB%99%E5%87%BA%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0%2C%E7%94%BB%E5%87%BA%E6%AD%A4%E5%93%88%E5%B8%8C%E8%A1%A8%2C%E5%B9%B6%E8%AE%A1%E7%AE%97%E5%9C%A8%E7%AD%89%E6%A6%82%E7%8E%87%E6%83%85%E5%86%B5%E4%B8%8B%E6%9F%A5%E6%89%BE%E6%88%90%E5%8A%9F)
数据结构哈希表,急对以下关键字序列建立哈希表{16,29,45,37,58,55,49,26,50,24,36,38},要求填充率为80%,用二次探测再散列法处理冲突:请给出哈希函数,画出此哈希表,并计算在等概率情况下查找成功
数据结构哈希表,急
对以下关键字序列建立哈希表{16,29,45,37,58,55,49,26,50,24,36,38},要求填充率为80%,用二次探测再散列法处理冲突:请给出哈希函数,画出此哈希表,并计算在等概率情况下查找成功的平均查找长度
数据结构哈希表,急对以下关键字序列建立哈希表{16,29,45,37,58,55,49,26,50,24,36,38},要求填充率为80%,用二次探测再散列法处理冲突:请给出哈希函数,画出此哈希表,并计算在等概率情况下查找成功
#include
#include
#include
#define MAXSIZE 20
#define MAX_SIZE 20 //人名的最大长度
#define HASHSIZE 60 //定义表长
#define SUCCESS 1
#define UNSUCCESS -1
typedef int Status; //为现有类型添加一个同义字
typedef char NA[MAX_SIZE]; // typedef 掩饰数组类型
typedef struct //记录
{
NA name;
NA xuehao; //关键字
NA tel;
}Stu; //查找表中记录类型
typedef struct //建立哈希表
{
Stu *elem[HASHSIZE]; //数据元素存储基址
int cou; //当前数据元素个数
int siz; //当前容量
}HashTable;
Status eq(NA x,NA y)
{
if(strcmp(x,y)==0)
return SUCCESS;
else return UNSUCCESS;
}
Status NUM_BER; //记录的个数 全局变量
Status NUM_BER1;
void Create(Stu* a) //创建新的通讯录
{
system("CLS"); //调用DOS命令CLS能够清屏
int i;
FILE *fp1,*fp2;
if((fp1=fopen("record.txt","r"))!=NULL) //打开文件
{
fclose(fp1); //关闭文件
}
else
{
fp2=fopen("record.txt","w"); //如果不存在,就创建一个record.txt
fclose(fp2);
}
printf("\n输入要添加的个数:\n");
scanf("%d",&NUM_BER);
for(i=0;icou);
}
void SearchHash(HashTable* H,int c) //在通讯录里查找姓名关键字,c用来记录冲突次数,若查找成功,显示信息
{
int p,pp;NA NAME;
system("cls");
printf("\n请输入要查找记录的姓名:\n");
scanf("%s",NAME);
p=Hash(NAME);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(NAME,H->elem[pp]->name)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(NAME,H->elem[pp]->name)==1)
{
printf("\n查找成功!\n查找过程冲突次数为%d.以下是您需要要查找的信息:\n\n",c);
printf("姓名:%s\n学号:%s\n电话号码:%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
}
else printf("\n此人不存在,查找不成功!\n");
}
void Modify(HashTable* H,int c) //在通讯录里修改某人信息
{
int p,pp;NA NAME;
system("cls");
printf("\n请输入要修改记录的姓名:\n");
scanf("%s",NAME);
p=Hash(NAME);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(NAME,H->elem[pp]->tel)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(NAME,H->elem[pp]->tel)==1)
{
printf("\n以下是您需要修改的信息:");
printf("姓名:%s\n学号:%s\n电话号码:%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
(H->elem)[pp]->tel[0]='\0';
printf("请输入修改后记录的姓名:\n");
scanf("%s",H->elem[pp]->name);
printf("请输入修改后记录的学号:\n");
scanf("%s",H->elem[pp]->xuehao);
printf("请输入修改后记录的电话号码:\n");
scanf("%s",H->elem[pp]->tel);
printf("修改成功!");
}
else
printf("\n此人不存在,修改不成功!\n");
}
void Delete(HashTable* H,int c) //在通讯录里查找姓名关键字,若查找成功,显示信息然后删除
{
int m,p,pp;NA str;
m=0;
system("cls");
printf("\n请输入要删除记录的姓名:\n");
m++;
scanf("%s",str);
p=Hash(str);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1)
{
printf("\n以下是您需要要删除的信息:\n\n",c);
printf("姓名:%s\n学号:%s\n电话号码:%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
(H->elem)[pp]->name[0]='\0';
printf("删除成功!");
}
else
printf("\n此人不存在,删除不成功!\n");
}
void Save(HashTable * H) //将记录保存到指定文件
{
system("CLS");
int i;
FILE* fp;
if((fp=fopen("record.txt","w"))!=NULL)
{
fprintf(fp,"\n");
for(i=0;ielem)[i]!='\0')
{
fprintf(fp,"学生姓名:%s\n",H->elem[i]->name);
fprintf(fp,"学生学号:%s\n",H->elem[i]->xuehao);
fprintf(fp,"学生电话号码:%s\n",H->elem[i]->tel);
fprintf(fp,"");
printf("\n请输入一个任务选项>>>");
printf("\n");
scanf("%d",&num);
switch(num)
{
case 1:Create(a) ;break;
case 2:getin(a); break;
case 3:output(a); break;
case 4:CreateHash(H,a); break;
case 5:c=0;SearchHash(H,c); break;
case 6:c=0;Delete(H,c); break;
case 7:c=0;Modify(H,c); break;
case 8:Save(H); break;
case 9:return 0; break;
default:
printf("输入错误,请重新输入!");
printf("\n");
}
}
system("pause");
return 0;
}