哈希表的设计与实现 课程设计报告

问题描述：设计哈希表实现电话号码查询系统。

基本要求

1、设每个记录有下列数据项：电话号码、用户名、地址

2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；

3、采用再哈希法解决冲突；

4、查找并显示给定电话号码的记录；

5、查找并显示给定用户名的记录。

6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。

二: 概要设计

进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。

   具体流程图如下所示:

三: 详细设计（含代码分析）

1.程序描述: 

本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储

struct node

{ string phone;  //电话号码

string name;   //姓名

string address;//地址

node *next;    //链接下一个地址的指针

};

2具体步骤

1.  要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node *infor_phone[MAX]; node *infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息

用链式法和再哈希法解决冲突：

int hash(string key)      //以姓名或者电话号码的前四位运算结果作为哈

{                         //希码

int result=1,cur=0,i;

if(key.size()<=4)

i=key.size()-1;

else   i=4;

for(;i>=0;i--)

{

cur=key[i]-'0';

result=result*9+cur;

}

result%=(MOD);

return result;

}

2.得到输入信息的哈希码以后，将相应的信息插入对应的地址，若产生冲突，则循环到这个地址的最后一个节点，然后再将节点插入到这个位置，这样就避免了冲突,在查找的时候便可直接找到这个地址然后快速的查找到信息:

void add_infor_phone(string phone,string name,string address)

{

    int value=hash(phone);

    node *infor=build_infor(phone,name,address);

    if(infor_phone[value]==NULL)

        infor_phone[value]=infor;

    else             

    {

        node *cur=infor_phone[value];

     while(cur->next)

cur=cur->next;

cur->next=infor;

    }

}

3.  再哈希法也是解决冲突的常见方法，当同义词产生地址冲突时计算另一个哈希函数地址，知道冲突不再发生，这种方法不易产生聚义，但是增加了计算时间：

int hash_agin(int numble,int key) //将关键字的前四位数经过计算的结果

{                                 //模上一个定义的数然后返回的数字为

   return numble%key;             //哈希码

}

int create(string key)           

{

   int result=1,cur=0,i;

if(key.size()<=4)

       i=key.size()-1;

   else

       i=4;

    for(;i>=0;i--)

    {

       cur=key[i]-'0';

        result=result*9+cur;

    }

    return result;

}

4. 同样用链表为储存信息的数据结构，当产生冲突时，将模数减去一然后再寻找地址直到不再产生冲突：

void  add_infors(string phone,string name,string address)

{

   int numble_phone=create(phone),key=MOD,pos_phone,pos_name;

   while(infor_phone[pos_phone=hash_agin(numble_phone,key)]!=NULL)

        key--;

   key=MOD;

   int numble_name=create(name);

   while(infor_name[pos_name=hash_agin(numble_name,key)]!=NULL)

        key--;

   node *inforphone=new node;

   node *inforname=new node;

inforphone->name=inforname->name=name;

inforphone->phone=inforname->phone=phone;

inforphone->address=inforname->address=address;

inforphone->next=inforname->next=NULL;

   infor_phone[pos_phone]=inforphone;

   infor_name[pos_name]=inforname;

}

5 .帮主函数bool usersayyes()，返回一个bool值，要求用户输入一个正确的选项，减少程序因错误输入而出现的问题:

bool usersayyes()

{

     string sig;

     bool continu=true;

cout<<"请输入(N/n)或(Y/y),(N/n)代表退出,(Y/y)代表继续:";

while(cin>>sig&&(sig!="Y"&&sig!="y")&&(sig!="N"&&sig!="n"))

     cout<<"输入错误,请重新输入!"<     return sig=="Y"||sig=="y";

}

四 调试分析和测试结果

1.用链式法将用户信息添加到哈希表：

2.以姓名为关键字检索用户信息:

3.当哈希表中不存在此项记录时:

4．再哈希法将用户信息添加到哈希表：

5．以姓名为检索在哈希表中查找用户信息:

6.以电话为检索在哈希表中查询信息:

使用哈希表能在较短的时间内查找出数据，程序的结果基本和理论相符合。

五，总结

通过做这个课程设计，使我们对如何去解决分析一个没有接触过的问题有深刻的认识，我们开始对题目有很多误解，根本没有思路，经过老师的几次讲解和我们自己很多的讨论，最终把问题进行转换，老师的要求是为了一个映射关系，我们找到了一个算法，算法和公式是可以相互转换的，在这个过程我们发现自己的程序有很多问题，经过我们不断对算法进行修改使得我们的程序运行的更快。哈希表的设计与实现这一算法始终围绕怎样解决冲突和怎样快速查找数据为目的，要求用在哈希法和链式法设计和实现哈希表，经过查阅资料请教同学问题渐渐的变得清晰，在分析问题，思考问题和解决问题的过程中，很大程度上培养了我们的动手和动脑的能力，开始选择一个合适的数据结构，然后依据算法编码，调试，最后得出正确结论，整个过程虽然遇到了很多问题，特别是指针的冲突，这样在不知不觉中培养了我的耐性，“数据结构与算法”课程是计算机专业的一门十分重要的核心基础课程。这次的课程设计，，拓广了我解决实际问题的程序设计的思路，也培养了对于问题进行深入探究的习惯。我更加深刻的体会到各种路由算法的特点，以及性能的优劣。为我今后专业课程的学习奠定了坚实的理论基础！

六.参考文献;

1. 数据结构 严蔚敏，吴伟明（c语言版）清华大学出版社

2. 算法导论 Thoms.H.Cormen , Charles E.Leiserson , Ronald L.Rivest, Clifford Stein著

潘金贵，顾铁成，李成法译 第二版 机械工业出版社

3. 数据结构基础(C语言版)(第2版) Ellis Horowitz，Sartaj Sahni，Susan Anderson-Freed  

   著 朱仲涛译 清华大学出版社

4. 数据结构与算法分析：C语言描述(英文版.第2版) Mark Allen Weiss 著 

机械工业出版社

 5. 算法之道 邹恒明 (第2版)  机械工业出版社

七.致谢

在这次课程设计的撰写过程中，我得到了许多人的帮助。

首先我要感谢我的老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是老师帮我解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。

其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计商的难题。同时也感谢学院为我提供良好的做毕业设计的环境。

最后再一次感谢所有在设计中曾经帮助过我的良师益友和同学

八.附录

#include

#include

using namespace std;

#define MAX 10000

#define MOD 9873

struct node        //定义储存学生信息的结构体

{

    string phone;

    string name;

    string address;

    node *next;

};

node *infor_phone[MAX];    //存放信息的指针数组

node *infor_name[MAX];

void init()                //初始化初始化指针数组

{

for(int i=0;i    {

        infor_phone[i]=NULL;

        infor_name[i]=NULL;

    }

}

bool usersayyes()             //帮助函数要求用户输入正确的选项

{

     string sig;

     bool continu=true;

cout<<"请输入(N/n)或(Y/y),(N/n)代表退出,(Y/y)代表继续:";

while(cin>>sig&&(sig!="Y"&&sig!="y")&&(sig!="N"&&sig!="n"))

     cout<<"输入错误,请重新输入!"<     return sig=="Y"||sig=="y";

}

//再哈希法

int hash_agin(int numble,int key)    //再哈希法获得地址的函数

{

   return numble%key;

}

int create(string key)

{

   int result=1,cur=0,i;

if(key.size()<=4)

       i=key.size()-1;

   else

       i=4;

for(;i>=0;i--)

   {

       cur=key[i]-'0';

        result=result*9+cur;

   }

   return result;

}

void  add_infors(string phone,string name,string address) 

//再希法添//加用户信息到哈希表

{

   int numble_phone=create(phone),key=MOD,pos_phone,pos_name;

   while(infor_phone[pos_phone=hash_agin(numble_phone,key)]!=NULL)

        key--;

   key=MOD;

   int numble_name=create(name);

   while(infor_name[pos_name=hash_agin(numble_name,key)]!=NULL)

        key--;

   node *inforphone=new node;

   node *inforname=new node;

inforphone->name=inforname->name=name;

inforphone->phone=inforname->phone=phone;

inforphone->address=inforname->address=address;

inforphone->next=inforname->next=NULL;

   infor_phone[pos_phone]=inforphone;

   infor_name[pos_name]=inforname;

}

void find_byname(string name)        //以名字为关键字查询用户信息

{

   int numble_name=create(name),key=MOD,pos_name;

   while(true)

   {

       pos_name=hash_agin(numble_name,key);

       if(infor_name[pos_name]==NULL)

       {

         cout<<"不存在你要查找的信息!"<         cout<<"-------------------------------------------"<            return;

       }

if(infor_name[pos_name]->name==name)

       {

     cout<<"姓名:";

cout<name< cout<<"电话:";

         cout<phone<         cout<<"地址:";

         cout<address<         cout<<"-------------------------------------------"<            return ;

       }

       key--;

   }

}

void find_byphone(string phone)   //以电话为关键字查询用户信息

{

   int numble_phone=create(phone),key=MOD,pos_phone;

    while(true)

   {

       pos_phone=hash_agin(numble_phone,key);

       if(infor_phone[pos_phone]==NULL)

       {

         cout<<"不存在你要查找的信息!"<         cout<<"-------------------------------------------"<            return;

       }

if(infor_phone[pos_phone]->phone==phone)

       {

cout<<"姓名:";

cout<name< cout<<"电话:";

         cout<phone<         cout<<"地址:";

         cout<address<         cout<<"-------------------------------------------"<            return ;

       }

       key--;

   }

}

void find()

{

     string sig,infor;

cout<<"请输入(1)或(2),(1)代表姓名,(2)代表电话:";

while(cin>>sig&&(sig!="1"&&sig!="2"))

     cout<<"输入错误,请重新输入!"< cout<<"请输入要查找的信息:";

cin>>infor;

     if(sig=="1")

         find_byname(infor);

     else

          find_byphone(infor);

}

//链表法

int hash(string key)            //链表法获得哈希码

{

   int result=1,cur=0,i;

if(key.size()<=4)

       i=key.size()-1;

   else

       i=4;

for(;i>=0;i--)

   {

       cur=key[i]-'0';

       result=result*9+cur;

   }

   result%=(MOD);

   return result;

}

node * build_infor(string phone,string name,string address) 

{                              //存储用户信息到哈希表

    node *information=new node; 

information->phone=phone;

information->name=name;

information->address=address;

information->next=NULL;

    return information;

}

void add_infor_phone(string phone,string name,string address)

{

    int value=hash(phone);

    node *infor=build_infor(phone,name,address);

    if(infor_phone[value]==NULL)

        infor_phone[value]=infor;

    else             

    {

        node *cur=infor_phone[value];

     while(cur->next)

cur=cur->next;

cur->next=infor;

    }

}

void add_infor_name(string phone,string name,string address)

{

    int value=hash(name);

    node *infor=build_infor(phone,name,address);

    if(infor_name[value]==NULL)

        infor_name[value]=infor;

    else

    {

        node *cur=infor_name[value];

     while(cur->next)

cur=cur->next;

cur->next=infor;

    }

}

void findinfor()            //分别以名字和电话为关键字查询用户信息

{

    string infor;

    int sig,pos;

cout<<"请输入要供查找的信息代号:1代表电话号码,2代表姓名:";

while(cin>>sig&&(sig!=1&&sig!=2))

     cout<<"输入错误,请重新输入!"< cout<<"请输入要供查找的信息:";

cin>>infor;

    if(sig==1)

    {

          bool flag=true;

          pos=hash(infor);

          node * cur=infor_phone[pos];

          while(cur)

          {

if(cur->phone==infor)

             {

cout<<"姓名:"<name<             cout<<"电话:"<phone<             cout<<"地址:"<address<                flag=false;

                break;

             }

         cur=cur->next;

          }

          if(flag)

         cout<<"不存在要查找的记录!"<     cout<<"-------------------------------------------"<    }

    else if(sig==2)

    {

          bool flag=true;

          pos=hash(infor);

          node * cur=infor_name[pos];

          while(cur)

          {

if(cur->name==infor)

             {

cout<<"姓名:"<name<                 <<"电话:"<phone<                 <<"地址:"<address<                

                flag=false;

                break;

             }

         cur=cur->next;

          }

          if(flag)

         cout<<"不存在要查找的记录!"<     cout<<"--------------------------------------"<    }

    else

    {

     cout<<"输入错误,请重新输入:"<     cout<<"--------------------------------------"<        findinfor();

    }

}

void hash_frist()

{

   int numble;

   string phone,name,address,sig;

   init();

cout<<"请输入添加的人数:";

cin>>numble;

   while(numble--)

   { 

cout<<"请输入----姓名:";

cin>>name;

cout<<"请输入电话号码:";

cin>>phone;      

cout<<"请输入----地址:";

cin>>address;

cout<<"--------------------------------------"<       add_infor_phone(phone,name,address);

       add_infor_name(phone,name,address);      

   }

   do findinfor();

   while(usersayyes());   

}

void hash_second()

{

   int numble;

   string phone,name,address,sig,infor;

   init();

cout<<"请输入添加的人数:";

cin>>numble;

   while(numble--)

   {

cout<<"请输入----姓名:";

cin>>name;

cout<<"请输入电话号码:";

cin>>phone;

cout<<"请输入----地址:";

cin>>address;

cout<<"--------------------------------------"<       add_infors(phone,name,address);    

   } 

   do  find();

   while(usersayyes());

}

int main()              //主函数

{

    string chois;

cout<<"请输入(1)或(2)--(1)链式法(2)再哈希:";

while(cin>>chois&&(chois!="1"&&chois!="2"))

     cout<<"输入错误,请重新输入!"<    if(chois=="1")

      hash_frist();

    if(chois=="2")

      hash_second();

    return 0;

}