哈希表的建立与查找，用链地址法处理冲突，用除留余数法构造哈希函数

盛夏的果实

完整代码：

#include<iostream>
using namespace std;
typedef struct Hash{
int data;//值
Hash *next;//下一个
}Hash;
void insert(Hash ha[], int k, int num)
{//第k个位置，值num
Hash *p = &ha[k];
Hash *q = new Hash;
q->data = num;
q->next = p->next;//头插法
p->next = q;
}
void Creat_hash(Hash ha[],int p)
{
for (int i = 0; i < p; i++)//初始化
{
ha[i].data = -1;
ha[i].next = NULL;
}
int m;//数据元素个数
cout << "请输入数据个数" << endl;
cin >> m;
cout << "依次输入各个数据" << endl;
while (m--)
{
int num;
cin >>num;
insert(ha, num%p, num);
}
}
void search(Hash ha[], int k, int num)
{
Hash *p = &ha[k];
int sum = 0;
while (p != NULL)
{
sum++;//记录在链表的第几个位置
if (p->data == num)//找到退出循环
break;
p = p->next;//没找到后移
}
if (p == NULL)cout << "没找到";
else cout <<num<<"位于"<< k << "," << sum-1<<endl;
}
int main()
{
char ch1, ch2;
char u;//起始点
int p;//哈希函数的除数
Hash *ha;
ch1 = 'y';
while (ch1 == 'y')
{
cout << "----------哈希表的建立和查找----------" << endl;
cout << "------1.哈希表的建立  ------" << endl;
cout << "------2.哈希表的查找  ------" << endl;
cout << "------0.退出      ------" << endl;
cout << "------请选择菜单号  ------" << endl;
cin >> ch2;
getchar();
cout << endl;
switch (ch2)
{
case'1':
//哈希表的建立
   cout << "请输入hash函数的除数p:" << endl;
   cin >> p;
   ha = new Hash[p];
   Creat_hash(ha, p);
break;
case'2':
//哈希表的查找
int x;
cout << "请输入要查找的数" << endl;
cin >> x;
search(ha, x%p, x);
break;
case'0':
ch1 = 'n';
//delete[]ha;
break;
default:
cout << "输入有误" << endl;
}//switch
}//while
return 0;
}

运行结果：