c++利用散列表设计实现电话号码查找系统

要求：

1.每个记录包括用户名、电话、地址

2.界面输入，以用户名拼音为关键字建立散列表

3.采用某个方法解决冲突

4.查找并显示给定用户的电话号码的信息

5.至少设计2种散列函数，比较冲突率

下面是源码，

#include <iostream>
using std::cout; 
using std::cin;
using std::endl;
#include <string>
using std::to_string;
using std::string;
#include <cstdlib>
#define HASHSIZE 100 //散列表的表长

//记录,用户信息
typedef struct
{
	string name;//姓名
	string teleNum;//电话号码
	string address;//地址
    int conflict;
    bool flag; //标志位，如果flag=false，说明此处无数据。反之，则有数据
}Record;

//散列表
typedef struct
{
    Record elem[HASHSIZE];
    int conflict;//冲突
}Hashtable;


//判断素数
bool isprime(int num)
{
    int count = 0;
    if (num <= 1) return false;
    for (int i = 1; i <= num; i++)
    {
        if (num % i == 0)
            count++;
    }
    if (count == 2)
        return true;
    else return false;
}

//确定除留取余法的除数
int getDivisor(int m)
{
    while (!isprime(m))
        m--;
    return m;
}

//散列函数（除留取余法）
int surplus(string name)
{
    int m = getDivisor(HASHSIZE);
    int key{ 0 };
    for (int j = 0; j < name.size(); j++)
        key += name[j] - ' ';
    key = key % m;
    return key;
}

//散列函数（折叠法）
int flod(string name)
{
    int key{ 0 };
    for (int j = 0; j < name.size(); j++)
        key += name[j] - ' ';
    if (key >= 0 && key < 100)
        return key;
    else if (key >= 100)
    {
        int count = 0;
        string str = to_string(key);
        key = 0;
        for (int i = 0; i < str.size();)
        {
            if (i + 1 < str.size())
            {
                string s = str.substr(i, i+2);
                int num = stoi(s);
                key += num;
                i = i + 2;
            }
            else
            {
                string s = str.substr(i,str.size()-1);
                int num = stoi(s);
                key += num;
                i++;
            }
        }
    }
    else
        cout << "请先切换输入法至英文状态再输入!";
    return key;
}

//初始化用户散列表
void initHashtable(Hashtable &H)
{
    for (int i = 0; i < HASHSIZE; i++)
    {
        H.elem[i].flag = false;
        H.elem[i].conflict = 0;
    }
    H.conflict = 0;
}

//清屏
void clearS()
{
    system("cls");//在dos执行cls命令进行清屏
}

//初始化菜单
void initMenu()
{
    cout << "欢迎使用电话号码查找系统!" << endl;
    cout << "   1.添加用户信息" << endl;
    cout << "   2.显示所有用户信息" << endl;
    cout << "   3.查找用户信息" << endl;
    cout << "   4.清屏" << endl;
    cout << "   5.退出" << endl;
}

//构建用户名散列表
void create(Hashtable &H)
{
    int num;
    cout << "请输入需要添加的用户的个数：";
    cin >> num;
    if (cin.fail()) {// 如果输入发生错误
        cin.clear();// 清除错误标志, 使后续正常输入, 但错误的数据还在输入缓冲区
        cin.ignore();// 清除缓冲区的一个字符               
    }
    for (int i = 0; i < num; i++)
    {
        int count = 0;
        string tname, tteleNum,taddress;
        cout << "请输入第" << i + 1 << "个用户的用户名：";
        cin >> tname;
        cout << "请输入第" << i + 1 << "个用户的电话号码：";
        cin >> tteleNum;
        cout << "请输入第" << i + 1 << "个用户的地址：";
        cin >> taddress;
        int key = surplus(tname);//除留取余法
        //int key = flod(tname);//折叠法
        if (key < 0)
            return;
        if (H.elem[key].flag == true) //记录冲突次数
            H.conflict++;
        int Key = key;
        for (;;)//采用线性探测法解决冲突
        {
            if (H.elem[key].flag==false)
            {
                H.elem[key].name = tname;
                H.elem[key].teleNum = tteleNum;
                H.elem[key].address = taddress;
                H.elem[key].flag = true;
                cout<<"第"<<i+1 << "用户个存入成功！" << endl;
                break;
            }
            else if (key < HASHSIZE - 1&& H.elem[key].flag==true)
            {
                key++;
                H.elem[Key].conflict++;
                count++;
            }
            else
            {
                key = 0;
                H.elem[Key].conflict++;
                count++;
            }
            if (count == HASHSIZE) 
            {
                cout << "已存满！无法存入！";
                break;
            }
        }
    }
}

//显示所以用户的信息
void showAll(Hashtable &H)
{
    int count = 0;
    for (int i = 0; i < HASHSIZE; i++)
    {
        if (H.elem[i].flag == true)
        {
            cout <<endl<<"用户名：" << H.elem[i].name << endl;
            cout <<"电话号码：" << H.elem[i].teleNum << endl;
            cout <<"地址：" << H.elem[i].address << endl;
            count++;
        }
    }
    if (count == 0)
        cout << "无信息！请添加用户信息！";
    //cout <<endl<< "冲突次数：" << H.conflict<<endl;//比较冲突率时使用
}

//查找用户信息
void search(Hashtable &H)
{
    int count = 0;
    int count2 = 0;
    int count3 = 0;
    string name;
    cout << "请输入要查找的用户的用户名：";
    cin >> name;
    int key = surplus(name);//除留取余法
    //int key = flod(name);//折叠法
    if (key < 0)
        return;
    int Key = key;
    for (;;)//采用线性探测法解决冲突
    {
        if (H.elem[key].flag == true && Key == surplus(H.elem[key].name))//除留取余法
        //if (H.elem[key].flag == true && Key == flod(H.elem[key].name))//折叠法
        {
            if (name == H.elem[key].name) 
            {
                cout << endl << "用户名：" << H.elem[key].name << endl;
                cout << "电话号码：" << H.elem[key].teleNum << endl;
                cout << "地址：" << H.elem[key].address << endl;
                count3++;
            }
            if (count2 == H.elem[Key].conflict)
            {
                if (count3 == 0)
                    cout << "未查找到该用户的信息！";
                break;
            }             
            else
            {
                count2++;
                key++;
            }
        }
        else if (key < HASHSIZE - 1 && H.elem[key].flag == true)
        {
            key++;
            count++;
        }
        else
        {
            key = 0;
            count++;
        }
        if (count == HASHSIZE)
        {
            cout << "未查找到该用户的信息！";
            break;
        }
    }
 
}

int main()
{
    Hashtable H;
    initHashtable(H);
    initMenu();
	for (;;) 
	{
		int num;
		cout <<endl<< "请输入操作号(1-5)：";
		cin >> num;
		switch (num) 
		{
		case 1:
            create(H);
			continue;
		case 2:
            showAll(H);
			continue;
		case 3:
            search(H);
			continue;
		case 4:
            clearS();
            initMenu();
			continue;
		case 5:
			cout <<endl<< "已退出系统！欢迎下次使用！"<<endl;
			break;
		default:
			if (cin.fail()) {// 如果输入发生错误
				cin.clear();// 清除错误标志, 使后续正常输入, 但错误的数据还在输入缓冲区
				cin.ignore();// 清除缓冲区的一个字符               
			}  
            clearS();
            initMenu();
            cout <<endl<< "消息：输入错误，请重新输入！" << endl;
			continue;
		}
		break;
	}
	return 0;
}

下面是运行结果，