一.实验目的
1.理解散列表的存储结构;
2.掌握常用散列函数构造方法和处理冲突方法;
3.在散列表上实现查找的算法。
二.实验内容
为小于n个关键字设计一个散列表,使得查找成功时平均查找长度<2.0,要求完成相应的散列表建立和查找。假设关键字为整型数据,散列函数用除留余数法,采用开放定址法的线性探测法处理冲突。
1.从键盘输入关键字个数n及关键字数据;
2.根据输入的关键字个数及平均查找长度要求,设计散列函数和计算表长;
3.构造散列表;
4.在散列表中进行查找。
三.代码
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
//顺序表存储结构
typedef struct
{
KeyType key; //关键字(数据项)
int time; //探测次数
} ElemType;
typedef struct
{
ElemType *elem; //数据元素存储空间基址
int length; //查找表的长度
} HashTable;
void inputData(KeyType KeyData[],int n)
{
printf("请输入%d个关键字:",n);
for(int i=0; i<n; i++)
{
scanf("%d",&KeyData[i]);
}
}
void calcpm(int n,int &p, int &m){
int i,j;
float Snl=2.0; //平均查找长度
float a;
//求m
a=1-1/(2*Snl-1);
m=int(n/a)+1;
//求p
for (i = m; i < 2 * m; i++) {
for (j = 2; j < i; j++) {
if (i % j == 0) {
break;
}
}
if (j == i) {
p = i;
break;
}
}
}
int hashFunc(KeyType key, int p)
{
return key % p;
}
int linearProbing(HashTable HT,int addr,int m,int &addri)
{
int time=1; //探测次数
if (HT.elem[addr].key == -1){ //不冲突
addri = addr;
return time;
}else{ //处理冲突
addri = (addr+1)%m;
while (HT.elem[addri].key != -1 && addri != addr){
time++;
addri = (addri+1)%m;
}
if (HT.elem[addri].key == -1){
return time;
}else{
addri = -1;
return -1;
}
}
}
void initHashTable(HashTable &HT,int m)
{
int i;
HT.elem=(ElemType *)malloc(m*sizeof(ElemType));
HT.length=m;
for(i=0; i<HT.length; i++)
{
HT.elem[i].key=-1; //赋初值
HT.elem[i].time=0;
}
}
void createHashTable(HashTable &HT,KeyType KeyData[],int n, int p, int m)
{
int i,addr,addri,time;
for(i=0; i<n; i++)
{
addr=hashFunc(KeyData[i],p);//求散列地址
time=linearProbing(HT,addr,m,addri);//处理冲突
HT.elem[addri].key=KeyData[i];
HT.elem[addri].time=time;
}
}
int search(HashTable HT, KeyType key,int p,int m)
{
int i,addr,addri;
addr=hashFunc(key,p); //求散列地址
if (HT.elem[addr].key==key)
return addr;
else if(HT.elem[addr].key==-1)
return -1;
else
for(i=1; i<m; i++)
{
addri=(addr+i) % m;
{
if (HT.elem[addri].key==key)
return addri;
else if (HT.elem[addri].key==-1)
return -1;
}
}
return -1;
}
void outputHashTable(HashTable HT)
{
printf("地址\t关键字\t探测次数\n");
for(int i=0; i<HT.length; i++){
if(HT.elem[i].key != -1){
printf("%d\t%d\t%d\n", i, HT.elem[i].key, HT.elem[i].time);
}
}
}
void menu()
{
int i;
system("cls");
printf("\n");
printf("%50s\n", "散列表的构造和查找\n");
for (i = 0; i < 80; i++)
putchar('=');
putchar('\n');
printf(" 1 输入数据 \n");
printf(" 2 构造散列函数 \n");
printf(" 3 构造散列表\n");
printf(" 4 查看散列表\n");
printf(" 5 散列表查找\n");
printf(" 0 退出\n");
printf(" \n");
for (i = 0; i<= 79; i++)
putchar('=');
putchar('\n');
printf("请输入操作序号:");
}
int main()
{
HashTable HT;
KeyType KeyData[50]; //存放关键字数据
int choice,n,m,p,addr;
KeyType key;
while (1)
{
menu();
scanf("%d", &choice);
getchar(); /*接收回车键*/
switch(choice)
{
case 1:
printf("请输入关键字个数:");
scanf("%d",&n);
inputData(KeyData,n);
break;
case 2:
calcpm(n,p,m);
printf("p=%d,m=%d\n",p,m);
printf("成功构造散列函数.\n");
break;
case 3:
initHashTable(HT,m);
createHashTable(HT,KeyData,n,p,m);
printf("成功构造散列表.\n");
break;
case 4:
printf("散列表:\n");
outputHashTable(HT);
printf("\n");
break;
case 5:
printf("请输入要查找的关键字:");
scanf("%d", &key);
addr = search(HT, key, p, m);
if(addr == -1){
printf("未找到关键字:%d\n", key);
}else{
printf("已找到关键字:%d,地址为%d,探测次数为%d\n", key, addr, HT.elem[addr].time);
}
break;
case 0:
exit(0);
break;
default:
printf("\n输入错误!");
break;
}
system("pause");
}
return 1;
}
标签:typedef,int,KeyType,列表,---,关键字,查找,数据结构
From: https://blog.csdn.net/2301_79235379/article/details/140863518