数据结构之哈希表设计

数据结构之哈希表设计

1．实验题目

针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。

2．需求分析

本次实习旨在集中对几个专门的问题作较为深入的探讨和理解，也强调对某些特定的编程技术的训练。

①输入的形式和输入值的范围：根据提示输入d进行排序操作。

②输出的形式：输出排序的哈希表及平均查找长度。

③程序所能达到的功能：图的创建、遍历、插入、删除、最短路径

④测试数据：取读者周围较熟悉的 30 个人名。

3．概要设计

1）为了实现上述程序功能，需要定义哈希表的抽象数据类型：

 1 typedef struct     
 2 
 3 {   char *py;  
 4 
 5 int k;     
 6 
 7 }NAME;   //名字拼音及列表
 8 
 9 NAME NameList[HASH_LENGTH];     
10 
11 typedef struct    //哈希表
12 
13 {   char *py;  
14 
15 int k;     
16 
17 int si;    
18 
19 }HASH;

2）本程序包含 5 个函数：

主函数main()

②名字初始化函数 InitNameList()

③建立哈希表函数CreateHashList()

④查找函数 FindList()

⑤显示哈希表函数 Display()

4．详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。

1) 结点类型和指针类型

 1  typedef struct     
 2 
 3 {   char *py;  
 4 
 5 int k;     
 6 
 7 }NAME;   //名字拼音及列表
 8 
 9 NAME NameList[HASH_LENGTH];     
10 
11 typedef struct    //哈希表
12 
13 {   char *py;  
14 
15 int k;     
16 
17 int si;    
18 
19 }HASH;
20 
21   HASH HashList[HASH_LENGTH];

2）其他模块伪码算法

主函数main()

{利用子函数实现哈希表的显示和查找。}

名字初始化函数 InitNameList()

{利用for函数实现名字列表的初始化。}

建立哈希表函数CreateHashList()

{创建哈希表，利用for循环给HashList[]各参数赋初值}

查找函数 FindList()

{使用哈希函数，利用姓名拼音对应的关键字，使用if语句，

进行判断，若有记录则输出姓名，关键字和查找长度；

若无，则输出无此记录。}

显示哈希表函数 Display()

{利用for循环实现哈希表的显示，在用平均数的方法计算平均查找长度。}

5．调试分析

将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。

6．使用说明

程序执行后显示： d:显示哈希表 f:查找请选择：

按照提示键入即可。

7．测试结果

8．附代码

  1 // 实验五.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 #include<iostream>
  7 #include<string>
  8 using namespace std;
  9 #define HASH_LENGTH 50               //事先定义哈希表的长度         
 10 #define M 47                         //选取随机数
 11 #define NAME_NO 30                   //定义人名的个数        
 12 
 13 typedef struct NAME     
 14 {   char *py;    //名字的拼音
 15     int k;       //拼音所对应的整数
 16 }NAME;
 17 
 18 NAME NameList[HASH_LENGTH];    //全局变量NAME       
 19 
 20 typedef struct    //构造哈希表
 21 {   char *py;   //名字的拼音
 22     int k;      //拼音所对应的整数
 23     int si;     //查找长度
 24 }HASH;
 25 
 26 HASH HashList[HASH_LENGTH];        //全局变量HASH                     
 27 
 28 void InitNameList() //初始化姓名（结构体数组）   
 29 {   char *f;
 30     int r,s0,i;
 31 for (i=0; i<HASH_LENGTH; i++)
 32 {
 33   NameList[i].py = new char[64];
 34   NameList[i].py[0] = 0;
 35 }
 36     strcpy(NameList[0].py, "zhangsan");
 37     strcpy(NameList[1].py, "lisi");
 38     strcpy(NameList[2].py, "liang");
 39     strcpy(NameList[3].py, "lala");
 40     strcpy(NameList[4].py, "youyou");
 41     strcpy(NameList[5].py, "zhaolala");
 42     strcpy(NameList[6].py, "suner");
 43     strcpy(NameList[7].py, "zhouzhou");
 44     strcpy(NameList[8].py, "tangtag");
 45     strcpy(NameList[9].py, "qiuqiu");
 46     strcpy(NameList[10].py, "lai");
 47     strcpy(NameList[11].py, "ye");
 48     strcpy(NameList[12].py, "dai");
 49     strcpy(NameList[13].py, "linjiajia");
 50     strcpy(NameList[14].py, "shang");
 51     strcpy(NameList[15].py, "yangyang");
 52     strcpy(NameList[16].py, "duoduo");
 53     strcpy(NameList[17].py, "xihua");
 54     strcpy(NameList[18].py, "luehh");
 55     strcpy(NameList[19].py, "nkjhi");
 56     strcpy(NameList[20].py, "chenwei");
 57     strcpy(NameList[21].py, "jyuj"); 
 58     strcpy(NameList[22].py, "jgjjh");
 59     strcpy(NameList[23].py, "djtryu");
 60     strcpy(NameList[24].py, "shrt");
 61     strcpy(NameList[25].py, "dejeyy");
 62     strcpy(NameList[26].py, "sntr");
 63     strcpy(NameList[27].py, "mkyjyu");
 64     strcpy(NameList[28].py, "dtur");
 65     strcpy(NameList[29].py, "ruj");
 66 
 67     for(i=0;i<NAME_NO;i++)
 68 {   
 69   s0=0;
 70   f=NameList[i].py;
 71   for(r=0;*(f+r)!='\0';r++) 
 72   //将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
 73    s0=*(f+r)+s0;
 74   NameList[i].k=s0;
 75 
 76 } 
 77 }
 78 void CreateHashList() //建立哈希表   
 79 { 
 80 int i;
 81 for(i=0; i<HASH_LENGTH;i++) 
 82 {   
 83   HashList[i].py=new char[64];
 84   HashList[i].py[0] = 0; 
 85   HashList[i].k=0;
 86   HashList[i].si=0;
 87 }
 88 for(i=0;i<HASH_LENGTH;i++)
 89 {
 90   int sum=0;
 91   int adr=(NameList[i].k)%M;  
 92   //哈希函数
 93   int d=adr;
 94   if(HashList[adr].si==0)     //不冲突
 95   {
 96    HashList[adr].k=NameList[i].k;
 97    HashList[adr].py=NameList[i].py;
 98    HashList[adr].si=1;
 99   }
100   else   //冲突 
101   { 
102    while (HashList[d].k!=0)
103    {
104     d=(d+NameList[i].k%10+1)%M;   //伪随机探测再散列法处理冲突    
105     sum=sum+1;                    //查找次数加1    
106    };
107    HashList[d].k=NameList[i].k;
108    HashList[d].py=NameList[i].py;
109    HashList[d].si=sum+1;
110   }
111 }
112 }
113 void FindList() //查找    
114 { 
115 string name; 
116     int s0=0,r,sum=1,adr,d;
117     cout<<"请输入姓名的拼音:"<<endl;     
118     cin>>name;; 
119     for(r=0;r<20;r++)   //求出姓名的拼音所对应的整数(关键字)
120         s0+=name[r]; 
121     adr=s0%M;   //使用哈希函数
122     d=adr;
123     if(HashList[d].k==s0)          //分情况进行判断
124   cout<<"姓名:"<<HashList[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为: 1"<<endl; 
125     else if (HashList[d].k==0) 
126   cout<<"无此记录!"<<endl;
127     else
128 {   
129   int g=0;
130   while(g==0)
131   {
132    d=(d+s0%10+1)%M;       //伪随机探测再散列法处理冲突                     
133    sum=sum+1;
134    if(HashList[d].k==0)
135    {
136     cout<<"无此记录!"<<endl; 
137     g=1;     
138    }
139    if(HashList[d].k==s0)
140    {
141     cout<<"姓名:"<<HashList[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为:"<<sum<<endl;
142     g=1; 
143    }
144     };   
145 } ;
146 }
147 void   Display() // 显示哈希表       
148 { 
149 int i;
150     float average=0;
151 
152 cout<<"\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"; //显示的格式
153     for(i=0; i<50; i++)
154 {   
155   cout<<i<<" "; 
156         cout<<"\t"<<HashList[i].k<<" ";
157         cout<<"\t\t"<<HashList[i].si<<" ";
158         cout<<"\t\t"<<(HashList[i].k%M)<<" ";
159         cout<<"\t "<<HashList[i].py<<" ";
160         cout<<"\n";
161 }
162     for(i=0;i<HASH_LENGTH;i++)
163         average+=HashList[i].si; 
164     average/=NAME_NO;
165 cout<<"平均查找长度：ASL("<<NAME_NO<<")="<<average<<endl;
166 
167 }
168 int main()
169 {
170 char x;
171 InitNameList();                                
172 CreateHashList (); 
173 cout<<"***************************************************************"<<endl;
174 cout<<"                            d:显示哈希表                       "<<endl;
175 cout<<"                            f:查找                             "<<endl;
176 cout<<"                            请选择：                           "<<endl;
177 cout<<"**************************************************************"<<endl; 
178 while(cin>>x)
179 {
180   if(x=='d')
181   {
182    Display();
183    cout<<endl;
184   }
185   else if(x=='f')
186   {
187    FindList();
188    cout<<endl;
189   }
190   else break;
191 }
192 for (int i=0; i<HASH_LENGTH; i++)
193 {
194   free(NameList[i].py);
195   free(HashList[i].py);
196 }
197 return 0;
198 }

View Code

数据结构之哈希表设计

推荐阅读