#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 100;
int n;//记录个数
int n1, n2; //n1,n2分别表示两个散列表里面的用户数
int m;//散列表大小
//用户信息
struct record {
char telnum[maxn]; //电话号码
char telname[maxn]; //用户名
char teladd[maxn]; //地址
bool flag; //标志位，如果flag=false，说明此处无数据。反之，则有数据
int count = 0; //记录发生冲突的次数
};
struct record rec1[maxn]; //电话号码散列表
struct record rec2[maxn]; //用户名散列表
//判断素数
bool isprime(int n) {
if (n <= 1) return false;
long long m = floor(sqrt(n) + 0.5);
for (long long i = 2; i <= m; ++i) {
if (n%i == 0) return false;
}
return true;
}
//确定除留取余法的除数
int confirm(int m) {
while (!isprime(m)) { //如果函数返回值是false，说明m不是素数，就把m--
--m;
}
return m;
}
//构建电话号码散列表
void init1() {
while (n1--) {
char telnum[maxn], telname[maxn], teladd[maxn];
cout << "请输入电话号码：";
cin >> telnum;
cout << "请输入用户名：";
cin >> telname;
cout << "请输入地址：";
cin >> teladd;
int sum(0);
bool flag = false;
int count(0); //记录发生冲突的次数
for (int i = 0; i <strlen(telnum); ++i) {
sum += telnum[i] - '0'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
while (rec1[sum].flag == true) { //如果该位置已经有数据了，就向后移动一位
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << telnum << "插入不进散列表" << endl;
break;
}
}
if (count != m) {
strcpy(rec1[sum].telnum, telnum);
strcpy(rec1[sum].telname, telname);
strcpy(rec1[sum].teladd, teladd);
rec1[sum].flag = true;
rec1[sum].count = count;
}
}
}
//通过电话号码查询信息
void print1() {
char t[20];
cout << "请输入需要查找的电话号码：";
cin >> t;
int sum(0);
for (int i = 0; i <strlen(t); ++i) {
sum += t[i] - '0'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
int count(0); //记录判断的次数
while (strcmp(rec1[sum].telnum, t) != 0) {
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << "查询失败" << endl;
cout << t << "不在散列表中" << endl;
break;
}
}
if (count != m) {
cout << "查询成功" << endl;
cout << "电话号码：" << rec1[sum].telnum << endl;
cout << "用户名：" << rec1[sum].telname << endl;
cout << "地址：" << rec1[sum].teladd << endl;
cout << "冲突次数：" << rec1[sum].count << endl;
}
}
//根据电话号码插入用户
void insert1() {
char telnum[maxn], telname[maxn], teladd[maxn];
cout << "请输入需要插入的用户的电话号码 ";
cin >> telnum;
ll sum(0);
bool flag = false;
int count(0); //记录发生冲突的次数
for (int i = 0; i <strlen(telnum); ++i) {
sum += telnum[i] - '0'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
while (rec1[sum].flag == true) { //如果该位置已经有数据了，就向后移动一位
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << "通讯录已满，用户电话号码为" << telnum << "的用户插入失败" << endl;
break;
}
}
if (count != m) {
cout << "插入成功，请完善该用户的其他信息" << endl;
cout << "请输入用户名：";
cin >> telname;
cout << "请输入地址：";
cin >> teladd;
strcpy(rec1[sum].telnum, telnum);
strcpy(rec1[sum].telname, telname);
strcpy(rec1[sum].teladd, teladd);
rec1[sum].flag = true;
rec1[sum].count = count;
}
}
//根据电话号码删除用户
void Delete1() {
char telnum[maxn], telname[maxn], teladd[maxn];
cout << "请输入需要删除的用户的电话号码 ";
cin >> telnum;
int sum(0);
bool flag = false;
int count(0); //记录发生冲突的次数
for (int i = 0; i <strlen(telnum); ++i) {
sum += telnum[i] - '0'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
while (strcmp(rec1[sum].telnum, telnum) != 0||rec1[sum].flag==false) {
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << "删除失败，电话号码为" << telnum << "的用户不在通讯录中" << endl;
break;
}
}
if (count != m) {
cout << "删除成功" << endl;
rec1[sum].flag = false;
}
}
//显示电话号码散列表的信息
void fun1() {
cout << "******************************" << endl;
cout << "********电话号码通讯录********" << endl;
cout << "******************************" << endl;
for (int i = 0; i < m; ++i) {
if (rec1[i].flag == true) {
cout << i << "号用户的信息" << "电话号码：" << rec1[i].telnum << " " << "用户名：" << rec1[i].telname << " " << "地址：" << rec1[i].teladd << " " << "冲突次数：" << rec1[i].count << endl;
}
}
}
//计算电话号码通讯录查找成功的ASL
void succ_asl1() {
int counter = 0; //统计发生冲突的次数
int counter1 = 0; //统计散列表里面有多少个数据
for (int i = 0; i < m; ++i) {
if (rec1[i].flag) {
counter += rec1[i].count+1;
++counter1;
}
}
double succ_asl;
if (counter1 != 0) {
succ_asl = (double)((double)counter / (double)counter1);
}
cout << counter << endl;
cout<<"查找成功的ASL为 "<< setprecision(5) << fixed <<succ_asl<< endl;
}
//计算电话号码通讯录查找失败的ASL
void fail_asl1() {
int counter = 0; //统计发生冲突的次数
int counter1; //统计连续有数据的个数
for (int i = 0; i < m; ++i) {
counter1 = 0;
int temp = i;
while(rec1[temp].flag) {
if (temp == m) {
temp = 0;
}
++counter1;
++temp;
}
counter1++;
counter += counter1;
}
double fail_asl;
fail_asl = (double)((double)counter / (double)m);
cout << counter << endl;
cout << "查找失败的ASL为 " << setprecision(5) << fixed << fail_asl << endl;
cout << counter << endl;
}
//构建用户名散列表
void init2() {
while (n2--) {
char telnum[maxn], telname[maxn], teladd[maxn];
cout << "请输入用户名（请输入英文名）：";
cin >> telname;
cout << "请输入电话号码：";
cin >> telnum;
cout << "请输入地址：";
cin >> teladd;
int sum(0);
bool flag = false;
int count(0); //记录发生冲突的次数
for (int i = 0; i <strlen(telname); ++i) {
sum += telname[i] - 'A'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
while (rec2[sum].flag == true) { //如果该位置已经有数据了，就向后移动一位
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << telnum << "插入不进散列表" << endl;
break;
}
}
if (count != m) {
strcpy(rec2[sum].telnum, telnum);
strcpy(rec2[sum].telname, telname);
strcpy(rec2[sum].teladd, teladd);
rec2[sum].flag = true;
rec2[sum].count = count;
}
}
}
//通过用户名查询信息
void print2() {
char t[20];
cout << "请输入需要查找的用户名（请输入英文名)：";
cin >> t;
int sum(0);
for (int i = 0; i <strlen(t); ++i) {
sum += t[i] - 'A'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
int count(0); //记录判断的次数
while (strcmp(rec2[sum].telname, t) != 0) {
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << "查询失败" << endl;
cout << t << "不在用户名通讯录中" << endl;
break;
}
}
if (count != m) {
cout << "查询成功" << endl;
cout << "用户名：" << rec2[sum].telname << endl;
cout << "电话号码：" << rec2[sum].telnum << endl;
cout << "地址：" << rec2[sum].teladd << endl;
cout << "冲突次数：" << rec2[sum].count << endl;
}
}
//根据用户名插入用户
void insert2() {
char telnum[maxn], telname[maxn], teladd[maxn];
cout << "请输入需要插入的用户的用户名 ";
cin >> telname;
int sum(0);
bool flag = false;
int count(0); //记录发生冲突的次数
for (int i = 0; i <strlen(telname); ++i) {
sum += telname[i] - 'A'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
while (rec2[sum].flag == true) { //如果该位置已经有数据了，就向后移动一位
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << "通讯录已满，用户名为" << telname << "的用户插入失败" << endl;
break;
}
}
if (count != m) {
cout << "插入成功，请完善该用户的其他信息" << endl;
cout << "请输入电话号码：";
cin >> telnum;
cout << "请输入地址：";
cin >> teladd;
strcpy(rec2[sum].telnum, telnum);
strcpy(rec2[sum].telname, telname);
strcpy(rec2[sum].teladd, teladd);
rec2[sum].flag = true;
rec2[sum].count = count;
}
}
//根据用户名删除用户
void Delete2() {
char telnum[maxn], telname[maxn], teladd[maxn];
cout << "请输入需要删除的用户的用户名 ";
cin >> telname;
int sum(0);
bool flag = false;
int count(0); //记录发生冲突的次数
for (int i = 0; i <strlen(telname); ++i) {
sum += telname[i] - '0'; //计算key值
}
sum = sum % m; //除留取余，找到key值在散列表中对应的位置
while (strcmp(rec2[sum].telname, telname) != 0||rec2[sum].flag==false) {
if (sum < m - 1) sum++; //如果已经移动到最后一位了，就
else sum = 0; //从头开始判断
++count; //记录冲突次数
if (count == m) {
cout << "删除失败，用户名为" << telname << "的用户不在通讯录中" << endl;
break;
}
}
if (count != m) {
cout << "删除成功" << endl;
rec2[sum].flag = false;
}
}
//显示用户名散列表的信息
void fun2() {
cout << "****************************" << endl;
cout << "********用户名通讯录********" << endl;
cout << "****************************" << endl;
for (int i = 0; i < m; ++i) {
if (rec2[i].flag == true) {
cout << i << "号用户的信息" << "用户名：" << rec2[i].telname << " " << "电话号码：" << rec2[i].telnum << " " << "地址：" << rec2[i].teladd << " " << "冲突次数：" << rec2[i].count << endl;
}
}
}
//计算用户名通讯录查找成功的ASL
void succ_asl2() {
int counter = 0; //统计发生冲突的次数
int counter1 = 0; //统计散列表里面有多少个数据
for (int i = 0; i < m; ++i) {
if (rec2[i].flag) {
counter += rec2[i].count + 1;
++counter1;
}
}
double succ_asl;
if (counter1 != 0) {
succ_asl = (double)((double)counter / (double)counter1);
}
cout << counter << endl;
cout << "查找成功的ASL为 " << setprecision(5) << fixed << succ_asl << endl;
}
//计算用户名通讯录查找失败的ASL
void fail_asl2() {
int counter = 0; //统计发生冲突的次数
int counter1; //统计连续有数据的个数
for (int i = 0; i < m; ++i) {
counter1 = 0;
int temp = i;
while (rec2[temp].flag) {
if (temp == m) {
temp = 0;
}
++counter1;
++temp;
}
counter1++;
counter += counter1;
}
double fail_asl;
fail_asl = (double)((double)counter / (double)m);
cout << counter << endl;
cout << "查找失败的ASL为 " << setprecision(5) << fixed << fail_asl << endl;
cout << counter << endl;
}
//主函数
int main() {
cout << "请输入用户个数: "<<"\n";
cin >> n;
n1 = n; n2 = n;
m = confirm(n + 10); //确定散列表的大小
cout << "散列表大小为" << m << endl;
while (1) {
int counter(0);
cout << "* * * * * * * * * * * * * " << endl;
cout << "* * * 欢迎使用电话号码查询系统 * * * " << endl;
cout << "* *" << endl;
cout << "* *1.根据电话号码构建散列表 * *" << endl;
cout << "* *2.根据用户名构建散列表 * *" << endl;
cout << "* *3.根据电话号码查询相关信息 * *"<<endl;
cout << "* *4.根据用户名查询相关信息 * *" << endl;
cout << "* *5.根据电话号码插入用户信息 * *"<<endl;
cout << "* *6.根据用户名插入用户信息 * *" << endl;
cout << "* *7.根据电话号码删除散列表信息 * *" << endl;
cout<< "* *8.根据用户名删除散列表信息 * *" << endl;
cout << "* *9.显示电话号码散列表信息 * * "<<endl;
cout << "* *10.显示用户名散列表信息 * *" << endl;
cout << "* *11.求电话号码散列表查找成功的ASL *" << endl;
cout << "* *12.求用户名散列表查找成功的ASL * *" << endl;
cout << "* *13.求电话号码散列表查找失败的ASL * *" << endl;
cout << "* *14.求用户名散列表查找失败的ASL * *" << endl;
cout << "* *15.清屏 * *"<<endl;
cout << "* *16.安全退出 * *" << endl;
cout << " * *" << endl;
cout << "* * * * * * * * * * * * * " << endl;
cout << "请输入数字进行操作 "<<endl;
cin >> counter;
switch (counter) {
case 1: {
init1();
cout << endl << endl;
}; break;
case 2: {
init2();
cout << endl << endl;
}; break;
case 3: {
print1();
cout << endl << endl;
}; break;
case 4: {
print2();
cout << endl << endl;
}; break;
case 5: {
insert1();
cout << endl << endl;
}; break;
case 6: {
insert2();
cout << endl << endl;
}; break;
case 7: {
Delete1();
cout << endl << endl;
}; break;
case 8: {
Delete2();
cout << endl << endl;
}; break;
case 9: {
fun1();
cout << endl << endl;
}; break;
case 10: {
fun2();
cout << endl << endl;
}; break;
case 11: {
succ_asl1();
cout << endl << endl;
}; break;
case 12: {
succ_asl2();
cout << endl << endl;
}; break;
case 13: {
fail_asl1();
cout << endl << endl;
}; break;
case 14: {
fail_asl2();
cout << endl << endl;
}; break;
case 15: {
system("cls");
}; break;
case 16: {
return 0;
}; break;
}
}
}
京公网安备 11010502036488号