哈希表的设计与实现（以电话号码查找系统为实例）

//////////////////////////////////////////////////////////// ////////////////////哈希表的设计与实现///////////////////// ///////////////软件0802:鲁锦樑 0810024238///////////////// //////////////////////////张柯 0810024237//////////////// ////////////////////////张晓琳 0810024212/////////////// #include<iostream> #include<string> #include<fstream> using namespace std; #define MAXSIZE 100 //数组元素最大个数 /************************************************/ /**********定义一个类（用户Consumer）***********/ /**********************************************/ class Consumer { public: Consumer():telephone("0"),addre("0") { memset(name,0,20); } //构造函数（初始化变量） ~Consumer() //析构函数 { } Consumer* Create(); //创建数组 void ShowInformation(Consumer Array1[MAXSIZE]);//显示输入的用户信息 Consumer* HashTel1(Consumer Array1[MAXSIZE]); //以电话号码建立哈希表(再哈希法解决冲突) void HashTel2(Consumer Array1[MAXSIZE]); //再哈希法解决冲突 Consumer* HashNam1(Consumer Array1[MAXSIZE]); //以姓名建立哈希表(再哈希法解决冲突) void HashNam2(Consumer Array1[MAXSIZE]); //再哈希法解决冲突 bool HashSearch1(Consumer array1[40]); //查找并显示给定电话号码的记录 bool HashSearch2(Consumer array2[40]); //查找并显示给定姓名的记录 void Save(Consumer Array1[MAXSIZE]); //保存用户信息 protected: char name[20]; //姓名 string telephone; //电话号 string addre; //地址 }; Consumer array[MAXSIZE]; //定义一个类类型的全局数组 Consumer Array2[130]; //定义一个类类型的全局数组 unsigned int Num; //总的用户个数 int tu; //冲突发生的地点(下标) /***********************************************/ /**********定义一个类（用户Consumer）**********/ /*********************************************/ void main() { Consumer object,*Array1,*array1,*array2; //定义一个对象和三个指针 Array1=object.Create(); //创建数组 while (1) { cout<<" ┏━━━━━━━━━━━━━┓ "<<endl; 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<<" ┃ 温馨提示： ┃"<<endl; cout<<" ┃ Ⅰ.进行3操作前 请先输出1 ┃"<<endl; cout<<" ┃ Ⅱ.进行4操作前 请先输出2 (此系统只处理含有两个或以 ┃"<<endl; cout<<" ┃ 下的姓名或电话号相同的元素)┃"<<endl; cout<<" ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛"<<endl; cout<<"请输入一个任务选项>>>"<<endl; string num; cin>>num; switch(atoi(num.c_str())) //转化为整型 { case 1: array1=object.HashTel1(Array1); //以电话号码建立哈希表(再哈希法解决冲突) break; case 2: array2=object.HashNam1(Array1); //以姓名建立哈希表(再哈希法解决冲突) break; case 3: object.HashSearch1(array1); //查找(以电话号码为关键字) break; case 4: object.HashSearch2(array2); //查找(以姓名为关键字) break; case 5: object.ShowInformation(Array1); //显示输入的用户信息 break; case 6: object.Save(Array1); //保存用户信息 break; default: cout<<"你输错了，请重新输入!"<<endl; } } } /************************************************/ /**********定义一个类（用户Consumer）***********/ /**********************************************/ Consumer* Consumer::Create() //创建数组 { loop: string pnum; while(atoi(pnum.c_str())<=0||atoi(pnum.c_str())>MAXSIZE) { cout<<"请输入用户的个数(1到100)："<<endl; cin>>pnum; Num=atoi(pnum.c_str()); //强制转化为整型，防止输入一些不当数据导致系统崩溃 if(Num>MAXSIZE||Num<=0) cout<<"输入值无效！"<<endl; } for(int i=0;i<Num;i++) { cout<<"请输入第"<<i+1<<"个用户的姓名，电话，地址"<<endl; cin>>array[i].name>>array[i].telephone>>array[i].addre; if (atoi(array[i].telephone.c_str())==0) { cout<<"电话号码输入有误，请重新输入！>>>"<<endl; goto loop; } if (atoi(array[i].name)!=0) { cout<<"姓名输入有误，请重新输入！>>>"<<endl; goto loop; } } return array; } void Consumer::ShowInformation(Consumer Array1[MAXSIZE])//显示输入的用户信息 { for(int i=0;i<Num;i++) cout<<"第"<<(i+1)<<"个用户信息："<<" 姓名："<<Array1[i].name<<" 电话号码：" <<Array1[i].telephone<<" 地址："<<Array1[i].addre<<endl; } Consumer* Consumer::HashTel1(Consumer Array1[MAXSIZE]) //以电话号码建立哈希表(再哈希法解决冲突) { int t1=0; for(int i=0;i<Num;i++) { t1=atoi(Array1[i].telephone.c_str())%127; if (atoi(Array2[t1].telephone.c_str())>0) //如果该单元放了数据（产生冲突） { tu=i; //保留发生冲突的数组下表 HashTel2(Array1); } else //如果该单元未放数据（未产生冲突） Array2[t1]=Array1[i]; } cout<<"成功的以电话号码建立哈希表"<<endl; return Array2; } void Consumer::HashTel2(Consumer Array1[MAXSIZE]) //再哈希法解决冲突 { cout<<"产生冲突，用再哈希解决冲突"<<endl; int j=tu,t2; t2=atoi(Array1[j].telephone.c_str())%126; Array2[t2]=Array1[j]; //该单元未放数据（未产生冲突） cout<<"经过再哈希法解决冲突，成功的以电话号码建立哈希表"<<endl; } Consumer* Consumer::HashNam1(Consumer Array1[MAXSIZE]) //以姓名建立哈希表(再哈希法解决冲突) { int t3=0,a1,key1; for(int i=0;i<Num;i++) { a1=0; key1=0; while(Array1[i].name[a1]!=0) //逐个读入字符 { key1+=(int)Array1[i].name[a1]; //将字符型转化为整型 a1++; } t3=key1%127; if ((int)Array2[t3].name[0]>0) //如果该单元放了数据（产生冲突） { tu=i; //保留发生冲突的数组下表 HashNam2(Array1); } else //如果该单元未放数据（未产生冲突） Array2[t3]=Array1[i]; } cout<<"成功的以姓名建立哈希表"<<endl; return Array2; } void Consumer::HashNam2(Consumer Array1[MAXSIZE]) //再哈希法解决冲突 { cout<<"产生冲突，用再哈希解决冲突"<<endl; int t4=0,a2=0,key2=0,i=tu; while(Array1[i].name[a2]!=0) //逐个读入字符 { key2+=(int)Array1[i].name[a2]; //将字符型转化为整型 a2++; } t4=key2%126; Array2[t4]=Array1[i]; //该单元未放数据（未产生冲突） cout<<"经过再哈希法解决冲突，成功的以姓名建立哈希表"<<endl; } bool Consumer::HashSearch1(Consumer array1[40]) //查找并显示给定电话号码的记录 { string keytelephone; cout<<"请输入要查找的关键字(电话号码)>>>"<<endl; cin>>keytelephone; int local1=atoi(keytelephone.c_str())%127; int local2=atoi(keytelephone.c_str())%126; if(atoi(array1[local1].telephone.c_str())==atoi(keytelephone.c_str())&&atoi(array1[local2].telephone.c_str())==atoi(keytelephone.c_str())) { //找到发生冲突和未发生冲突的元素 cout<<"姓名:"<<array1[local1].name<<" " <<"电话:"<<array1[local1].telephone<<" " <<"地址:"<<array1[local1].addre<<endl; cout<<"---------------------------------"<<endl; cout<<"姓名:"<<array1[