哈希表的实例

一、课程设计的目的与要求
    1. 目的: 应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力，完成创新能力和实践能力的训练。
    2. 要求: 用高级程序设计语言C编码，用VC++开发平台调试。
二、设计正文
（一）  课程设计题目
    设计哈希表实现电话号码查询系统
（二）  需求分析
 设每个记录有下列数据项：电话号码、用户名、地址；
 (1)数据导入（从文件中读取各记录，分别以电话号码为关键字建立哈希表）；
 (2)从键盘读记录，并插入到哈希表中；
 (3)查找并显示给定电话号码的记录；
 (4)将电话号码记录保存在文件中；
 (5)尝试各种不同类型处理冲突的方法,考察平均查找长度的变化。
分析:由于题目要求以电话号码为关键字建表，考虑到电话号码长短不一，如果直接以表示电话号码的字符串为关键字，可能会造成一定的麻烦。故而，利用一个函数将表示电话号码的字符串转换成其相应的数字，然后把这些数字之和作为关键字即可将上述麻烦解除。
（三）  概要设计
     为了实现上述程序的功能，需要定义下列抽象数据类型：
     ADT hashtable {
         数据对象：哈希表中存储的个条电话记录；
         数据关系：表中相邻元素之间有前去和后继的关系；
         基本操作：
            init(Hashtable &h)
              操作结果：初始化了哈希表；
        int exchange(char str[])
          操作结果：球取关键字；
        int HashSearch1(Hashtable &h,char *str,int &p)
          操作结果：在表中线性探测数据，返回数据的插入位置；
int HashSearch2(Hashtable &h,char *str,int &p)
  操作结果：在表中二次探测数据，返回数据的插入位置；
void disp(Hashtable h)
  操作结果：显示出哈希表中储存的电话记录；
}ADT hashtable
将每个人的信息作为一条记录，包括电话号码、用户名、地址，还有一个整型变量用来记录冲突的次数，便于计算ASL,然后哈希表由记录数组、表现存量、容量组成,具体数据类型见下：
typedef struct {
   char name[30];
    char address[20];
   char num[30];
 }record;
 
typedef struct{
   record data[Size];
   int count;
   int size;
}Hashtable;
   
    关键字处理-----利用一个函数将表示电话号码的字符串转换成其相应的数字，然后把这些数字之和作为关键字。具体函数见下：
 int exchange(char str[])
 {
   int i,n,sum=0;
   n=strlen(str);
   for(i=0;i<n;i++)
       sum=sum+str[i]-'0';
   return sum;
 }
 最后就是用两种方法建表，分别用线性和二次探测的方法来处理冲突。
 本程序所有函数清单：
 void init(Hashtable &h)；//哈希表的初始化
 int exchange(char str[])；//求取关键字
 int HashSearch1(Hashtable &h,char *str,int &p)；//线性探测处理冲突
 int HashSearch2(Hashtable &h,char *str,int &p)；//二次探测处理冲突
 void disp(Hashtable h)；//显示哈希表
 int menu()；//主菜单
 void main()；//主函数
各函数之间的调用关系是：
 
主函数main（）
      
 
 
 
菜单函数menu（）
 
 
 
 
 
 
 
 
 
 

 
 
线性探测解决冲突hashserch1（）
查找用户
考察ASL1
二次探测解决冲突hashsearch2（）
查找用户
考察ASL
显示电话簿disp（）
 
（四）  详细设计
 1）为了实现上述程序的功能，需要定义下述数据类型：
   typedef struct{
   char name[30];
    char address[20];
   //float  num;
   char num[30];
   int c;//统计比较次数
 }record;      //记录
 
 typedef struct{
   record data[Size];
   int count;
   int size;
 }Hashtable;    //哈希表
 2）一些主要的函数：
 int exchange(char str[])    //关键字处理函数
 {
   int i,n,sum=0;
   n=strlen(str);
   for(i=0;i<n;i++)
       sum=sum+str[i]-'0';
   return sum;
 }
 int HashSearch1(Hashtable &h,char *str,int &p) //线性探测
 {
   int i,j,k=exchange(str);
   j=k%Size;
   if(strcmp(str,h.data[j].num)==0)
   {
       return j;
       h.data[j].c++;//!
   }//没有发生冲突，比较一次查找成功
   if(h.data[j].num[0]==0)
   {
       p=j;
       return 0;
   }
   else
   {
       h.data[j].c++;//!
       i=(j+1)%Size;//第1次解决冲突
       while(h.data[i].num[0]!=0&&i!=j) 
       {     
          if(strcmp(str,h.data[j].num)==0)
          {
              h.data[j].c++;//!
              return i;
          }//发生冲突，比较若干次查找成功
          i=(i+1)%Size;    //向后探测一个位置
       }
       if (i==j)
          printf("溢出\n");
       else        
       {
          p=i;
          h.data[j].c++;//!
          return 0;//查找不成功
       }
   }
}
 
int HashSearch2(Hashtable &h,char *str,int &p) //二次探测
{
   int i,j,t=1,d=1;
   int k=exchange(str);
   j=k%Size;
   if(strcmp(str,h.data[j].num)==0)
   { 
       h.data[j].c++;//!
       return j;
   }  //没有发生冲突，比较一次查找成功
   if(h.data[j].num[0]==0)
   {
       p=j;
       return 0;
   }
   else
   {
       i=(j+d)%Size;//第1次解决冲突
       while(h.data[i].num[0]!=0&&i!=j) 
       {  
           if(strcmp(str,h.data[j].num)==0)
          {
               h.data[j].c++;//!
               return i;
          }
          if(t>0)
              t=-1*d*d;
          else
          {
              d=d+1;
              t=-1*d*d ;
          }
          i=(j+t+Size)%Size;    //探测一个新的位置
          while(i<0)
          {
              h.data[j].c++;//!
              i=(i+Size)%Size;             
          }
           if (i==j)
              printf("溢出\n");
           else
          {
              p=i;
              h.data[j].c++;//!
              return 0;//查找不成功时插入
          }
        }
    }
  }
（五）  调试分析
本实验的运行环境是VC++。按照要求，应该事先导入一些记录，以下为本实验的测试数据：
4
侯进斌 北京 6627584
王璐 太原 6650370
 唐磊 天津 6626074
 高启波 太原 6651805
 然后按照菜单中的提示操作即可
 
（六）  使用说明
  程序名为hashtable.exe，运行环境为VC++。由于菜单中有详细的操作提示，您只要按照上面的提示一步一步进行操作即可。
（七）测试数据
  程序运行后将会出现以下菜单：
 
 
 
               
   选择1，立即会显示下面窗口，显示已存在的记录：      
 
    再选操作2，可以向电话簿1里添加记录，如下：
 
  操作3，向电话簿2中添加记录，如下：
 
  然后还可以进行查询操作，选4，可以在电话簿1中查询您想要的找的人的信息：
 
 同理，选5还可以在电话簿2中作相应的查询：
 
 如果您想比较着看一下在电话簿1中查找的速度（专业术语：ASL），可以选择操作6：
 
同理还可以查看电话簿2的这项功能：
 
如果您想结束操作，直接选0，即可退出该系统：
  
     以上就是本系统的主要功能。
三、课程设计总结或结论
1．完成的工作
该实验的所有要求：哈希表的创建，用两种不同的方法处理冲突，考察各种处理冲突方法的ASL；
2．未完成的工作
无；
3．所需做的改进
应该尝试更多的处理冲突的方法
一些代码的效率很低，有待改进
四、参考文献
《数据结构》（C语言版）  清华大学出版社 严蔚敏 吴伟民 编著