云南大学数学与统计学实验教学中心实验报告课程名称：数据结构与算法学期：2011-2012学年第二学期成绩：指导教师：xxx学生姓名：xxx学生学号：xxxxx实验名称：哈希表及其查找实验要求：必做实验学时：4（+2）学时实验编号：4（及5）实验日期：第6-8周完成日期：2012.5.10学院：数学与统计学院专业：信息与计算科学年级：2010级一、实验目的通过实验掌握散列存储的基本概念，进行哈希问题的处理，同时附带进行字符串的处理的练习。

二、实验内容为某单位的人名（n=30人）设计一个哈希表，使得平均查找长度<2，要求完成相应的哈希建表和查表。

三、实验环境Windows XP程序设计语言C四、实验过程1．实验要求：1、设人名长度<10个字符，用二维字符数组存储哈希表：char hash[ ][10];2、要求哈希函数用除留余数法，并用人名的10个字符代码和作为分子；用（补偿性）线性探测再散列处理冲突。

3、依题意有：平均查找长度=（1+1/(1-α)）/2< 2，∴取α=0.6，由此哈希表长m=n/α=30/0.6=50; 所以有char hashlist [ 50][10]；令：除留余数法中的P取47；（补偿性）线性探测再散列的地址：j=(j+Q)% m中的Q取17。

4、对程序结构的要求：①要求为哈希建表和哈希查表分别编写和设计相应的函数：createhash( ... ... ); hashsearch(... ...)；②再设计一个哈希函数表的输出函数printhash( )，对构造的哈希表进行输出，注意输出格式要在屏幕好看，先输出序号（1~30），再输出该序号的人名或null，每行输出10项，共输出5行。

③还应有一个初始化char hashlist [ 50][10]的函数Inithashlist( )，初始时将50个人名全赋值为null.5、在主函数中：调用Inithashlist( )初始化哈希表；调用createhash( hashlist，30 )构造哈希表；调用printhash( )输出所建立的哈希表；接受待查找人名到字符数组name[ ]；调用hashsearch(hashlist，name )进行查找，若查到显示"found！"并显示人名在数组中的序号；若未查到显示"no found！"[测试数据]：健表时输入以下数据：January February march april may june july august septemberOctober November DecemberSunday Monday Tuesday wednesday thurday f riday SaturdayOne two three four five six serve eight nine ten data[实现提示]：参照杨秀清主编《数据结构》西安电子科技大学出版社P171。

[附加要求]：1．在哈希查表时考虑插入。

当查找失败，且查找时的冲突次数<规定数字(如表长之半)时插入待查找的字符串，并给出“已插入”的显示；2．在哈希查表时考虑删除。

接受待删除人名到字符数组name[ ]；在hash表中找到，并删除之。

须注意，删除后不能影响以后的查找。

2．实验设计的（各）流程图：（以下内容请同学认真填写）3．程序设计的关键代码及解释：（注意对程序代码给出必要的注解，保证可读性）#include<stdio.h>#define N 50#define D 30#define M 10int m,hi;/*-------------------------------------------------------------------*/main(){void Inithashlist(char a[N][M]);void createhash(char a[D][M],char h[N][M]);void hashsearch(char h[N][M],char a[1][M]);void printhash(char a[][M],int n);char a[M],hashlist[N][M],data[D][M]={/*----------------------------------------------------------*/"January", "February", "March", "April", "May","June", "July", "August", "September", "October","November", "December", "Sunday", "Monday", "Tuesday","Wednesday","Thursday", "Friday", "Saturday", "One","Two", "Three", "Four", "Five", "Six","Serve", "Eight", "Nine", "Ten", "Data"};/*----------------------------------------------------------*/Inithashlist(hashlist);createhash(data,hashlist);printhash(hashlist,50);printf("please enter the name:\n");gets(a);hashsearch(hashlist,a);getchar();getchar();}/*-------------------------------------------------------------------*/void Inithashlist(char a[N][M]){int i;for(i=0;i<N;i++) strcpy(a[i],"null");}/*-------------------------------------------------------------------*//*-------------------------------------------------------------------*/int H(int key,int p){return(key%p);}/*-------------------------------------------------------------------*//*-------------------------------------------------------------------*/void createhash(char a[D][M],char h[N][M]){int i,j,key=0,hi=0,di[N-1];for(i=0;i<N-1;i++) di[i]=i+1;for(i=0;i<D;i++){key=0;j=0;while(a[i][j])key+=a[i][j++];hi=H(key,47);if(!strcmp(h[hi-1],"null")) strcpy(h[hi-1],a[i]);else{m=0;while(strcmp(h[hi-1],"null")) hi=H(hi+17,N);strcpy(h[hi-1],a[i]);}}}/*-------------------------------------------------------------------*//*-------------------------------------------------------------------*/void hashsearch(char h[N][M],char a[M]){char ch2,ch[M]="yes",ch1[M]="yes";int i=0,j,key=0,hi=0;for(;a[i]!='\0';)key+=a[i++];hi=H(key,47);m=0;while(strcmp(h[hi-1],"null")&&strcmp(h[hi-1],a)&&(strcmp(h[hi-1],"Deleted"))) while(strcmp(h[hi-1],"null")) hi=H(hi+17,N);if(!strcmp(h[hi-1],a)){printf("**************\n");printf("found! \n");printf("[%d]%s\n",hi,h[hi-1]);printf("**************\n");while(strcmp(ch1,"No")&&strcmp(ch1,"no")){printf("Delete it?(Y/N)\n");scanf("%s",ch1);ch2=getchar();if(!strcmp(ch1,"Yes")||!strcmp(ch1,"yes")){strcpy(h[hi-1],"Deleted");printf("**************\n");printf("Deleted! \n");printf("**************\n");printhash(h,N);break;}}}else if(m<(N/2)||!(strcmp(h[hi-1],"Deleted"))){strcpy(h[hi-1],a);printf("**************\n");printf("已插入！\n");printf("[%d]%s\n",hi,h[hi-1]);printf("**************\n");printhash(h,N);}else{printf("**************\n");printf("no found!\n");printf("**************\n");}while(strcmp(ch,"No")&&strcmp(ch,"no")){printf("continue to search?(Yes/No)\n");scanf("%s",ch);ch2=getchar();if(!strcmp(ch,"Yes")||!strcmp(ch,"yes")){printf("please enter the name:\n");gets(a);hashsearch(h,a);}}}/*-------------------------------------------------------------------*//*-------------------------------------------------------------------*/void printhash(char a[][M],int n){int i;for(i=0;i<=8;i++){system("color 03");printf("[0%-d] %-11s",i+1,a[i]);if((i+1)%5==0) printf("\n");}for(i=9;i<n;i++){printf("[%-d] %-11s",i+1,a[i]);if((i+1)%5==0) printf("\n");}printf("---------------------");printf("-----------------END-----------------");printf("---------------------\n\n");}/*-------------------------------END---------------------------------*/4．实验（程序运行）结果的粘贴：（必需是你的程序运行结果）[01] Three [02] Nine [03] null [04] null [05] Monday [06] Wednesday [07] null [08] One [09] null [10] Six [11] null [12] null [13] May [14] Ten [15] null [16] null [17] Sunday [18] Five [19] Data [20] null [21] March [22] August [23] Thursday [24] null [25] January [26] June [27] Eight [28] null [29] null [30] October [31] November [32] Two [33] February [34] April [35] Serve [36] Four [37] null [38] null [39] December [40] null [41] null [42] September [43] Friday [44] July [45] null [46] Saturday [47] Tuesday [48] null [49] null [50] null--------------------------------------END--------------------------------------please enter the name:friday**************已插入！[28]friday**************.........[26] June [27] Eight [28] friday [29] null [30] October .........--------------------------------------END--------------------------------------continue to search?(Yes/No)yesplease enter the name:friday**************found![28]friday**************Delete it?(Y/N)yes**************Deleted!**************.........[26] June [27] Eight [28] Deleted [29] null [30] October .........continue to search?(Yes/No)please enter the name:friday**************已插入！[28]friday**************.........[26] June [27] Eight [28] friday [29] null [30] October.........continue to search?(Yes/No)no五、实验总结1．遇到的问题及分析：（请结合你的试验过程认真总结）①没采用（补偿性）线性探测再散列，导致第二次查找同一元素不能够找到；②删除元素之后用null代替，导致之后的查找操作失败2．解决方案（列出遇到的问题和解决办法，列出没有解决的问题）：①改用（补偿性）线性探测再散列；②改用Deleted代替被删元素3．体会和收获。