课程设计

#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;
        }
    }

}