1、背景引入
(1)线性表和树等线性结构中,记录在结构中的相对位置是随机的,和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需要进行一系列和关键字的比较。理想的情况是希望不经过任何比较,一次存取便能够取到所查找的记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时,只要根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,因此,不需要进行比较便可以直接取得所查记录。在此,我们称这个对应关系f为哈希函数,按照这个思想建立的表为哈希表。
哈希函数的构造方法很多,常用的有直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等,,这里我选择了除留余数法。
(2)然而,对于不同的关键字可能得到同一哈希地址,即key1!=key2,而f(key1)=f(key2),这种现象叫做冲突,在一般情况下,冲突只能尽可能的少,而不能完全避免。因为,哈希函数是从关键字集合到地址集合的映像。通常,关键字集合比较大,它的元素包括多有可能的关键字,而地址集合的元素因为哈希表中的地址值。既然如此,那么,如何处理冲突则是构造哈希表不可缺少的一个方面了。。
通常用于处理冲突的方法有:开放定址法、再哈希法、链地址法、建立一个公共溢出区等。。。
(3)在哈希表上进行查找的过程和哈希造表的过程基本一致。给定K值,根据造表时设定的哈希函数求得哈希地址,若表中此位置没有记录,则查找不成功;否则比较关键字,若何给定值相等,则查找成功;否则根据处理冲突的方法寻找“下一地址”,知道哈希表中某个位置为空或者表中所填记录的关键字等于给定值时为止。
2、问题描述
编写Hash表程序(女友软件技术基础的作业,要求哈希表、矩阵运算等,这里是哈希表的实现。。。)
关键字为整数,冲突解决用单向链表
Hash表建立函数 关键字搜素函数
3、解决方法:
(1)采用除留余数法构造哈希函数,冲突解决采用链地址法。
(2)具体的关键字列表为(19,14,23,01,68,20,84,27,55,11,10,79),则哈希函数为H(key)=key MOD 13。则采用除留余数法和链地址法后得到的预想结果应该为:
(3)哈希造表完成后,进行查找时,首先是根据哈希函数找到关键字的位置链,然后在该链中进行搜索,如果存在和关键字值相同的值,则查找成功,否则若到链表尾部仍未找到,则该关键字不存在。
4、具体的实现代码:
其中2.txt中内容为:12
19 14 23 1 68 20 84 27 55 11 10 79 第一个值12表示关键字的个数。其他为具体的关键字
1 #include<stdio.h> 2 #include<stdlib.h> 3 struct keyNum*hash[100]; 4 struct keyNum* insertHash(struct keyNum*,int);//关键字插入链表 5 int searchHash(struct keyNum*,int m);//查找链表中是否存在值为m的整数 6 void print(struct keyNum*);//打印链表 7 struct keyNum 8 { 9 int key;//关键字 10 struct keyNum *next; 11 }; 12 void main() 13 { 14 printf("关键字列表保存在2.txt文件中,其中第一个值为关键字的个数\n其他值为具体的关键字,各个关键字之间用空格隔开\n"); 15 int i,k,m,n,num,flag,l,j; 16 FILE *p; 17 struct keyNum *head=NULL; 18 //关键字列表保存在2.txt文件中,其中第一个值为关键字的个数 19 //其他值为具体的关键字,各个关键字之间用空格隔开 20 p=fopen("2.txt","r"); 21 if(p==NULL) 22 { 23 printf("cannot open file 2.txt"); 24 exit(0); 25 } 26 fscanf(p,"%d",&num); 27 for(i=0;i<num;i++) 28 hash[i]=NULL; 29 for(i=0;i<num;i++) 30 { 31 fscanf(p,"%d",&k);//获取关键字 32 m=k%(num+1);//计算得到关键字的哈希值 33 hash[m]=insertHash(hash[m],k);//将关键字k插入到哈希值为m的链表中 34 } 35 printf("-----------------------------------------------\n请选择要进行的操作:\n1、打印采用链地址法得到的哈希表\n"); 36 printf("2、进行关键字查找\n3、退出\n------------------------------------------------\n"); 37 scanf("%d",&flag); 38 while((flag==1)||(flag==2)) 39 { 40 if(flag==1)//打印哈希表 41 { 42 printf("采用链地址法得到的哈希表为:\n"); 43 for(i=0;i<num+1;i++) 44 { 45 printf("第%d行:",i); 46 print(hash[i]); 47 printf("\n"); 48 } 49 } 50 else //查找 51 { 52 printf("请输入要查找的整数值:\n"); 53 scanf("%d",&n); 54 for(i=0;i<num+1;i++) 55 { 56 l=searchHash(hash[i],n); 57 if(l==1) 58 { 59 j=i; 60 break; 61 } 62 } 63 if(l==1)printf("整数值%d在哈希表中,位置为链表%d\n",n,j); 64 else printf("整数值%d不在哈希表中!\n"); 65 } 66 printf("-----------------------------------------------\n请选择要进行的操作:\n1、打印采用链地址法得到的哈希表\n"); 67 printf("2、进行关键字查找\n3、退出\n------------------------------------------------\n"); 68 scanf("%d",&flag); 69 } 70 } 71 struct keyNum * insertHash(struct keyNum*head,int m) 72 { 73 struct keyNum *p0,*p1,*p2,*temp; 74 temp=(struct keyNum*)malloc(sizeof(struct keyNum)); 75 temp->key=m; 76 p1=head; 77 p0=temp;//要插入的节点(值为m); 78 if(head==NULL)//1,原来的链表为空,插入到head后 79 { 80 head=p0; 81 p0->next=NULL; 82 } 83 else//原来的链表不为空 84 { 85 while((p0->key>p1->key)&&(p1->next!=NULL))//移动到适当位置 86 { 87 p2=p1; 88 p1=p1->next; 89 } 90 if(p0->key<=p1->key) 91 { 92 if(head==p1)head=p0;//2,插入到第一个节点之前 93 else p2->next=p0;//3,插入到p2指向的节点之后 94 p0->next=p1; 95 } 96 else//4,插入到结尾处 97 { 98 p1->next=p0; 99 p0->next=NULL; 100 } 101 } 102 return(head); 103 } 104 int searchHash(struct keyNum*head,int m)//查找链表head中是否存在m 105 { 106 int k=0; 107 struct keyNum*p; 108 p=head; 109 if(head!=NULL) 110 do 111 { 112 if(p->key==m) //存在m 113 { 114 k=1; 115 break; 116 } 117 p=p->next; 118 }while(p!=NULL); 119 return(k);//存在m值则返回1,否则返回0; 120 } 121 122 void print(struct keyNum*head)//打印链表head 123 { 124 struct keyNum*p; 125 p=head; 126 if(head!=NULL) 127 { 128 do 129 { 130 printf(" -> %d ",p->key); 131 p=p->next; 132 }while(p!=NULL); 133 } 134 else 135 printf("null"); 136 } 137 138 139 140 141
5、参考:
(1)数据结构,严蔚敏
相关推荐
哈希表 用链地址法解决冲突:(哈希函数是按名字第一个大写字母分的) 输入内容:学生的姓名跟成绩 操作:插入、修改、查找、删除学生;以及输出哈希表
哈希表处理。。。用链地址法处理。。。建立关键字的头指针,然后依次插入。。。
哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 测试数据 取读者周围较熟悉的30个人名。 选作内容 (1) 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数,比较...
构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法分别封装为2个函数。 提交实验报告/ 程序分析 1、将姓名表各个名字得ASCII码相加...
(1) 采取除留余数法构造哈希表; (2) 采用线性探测再散列方法解决冲突,输出哈希表结果; (3) 采用链地址法处理冲突,输出哈希表结果; (4) 考查两种冲突方法的平均查找长度。
针对某个集体中人名设计一个哈希表,使得平均查找长度不超过R,并完成相应的建表和查表程序。假设人名为中国人姓名的汉语拼音形式。...哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
hash表一般都采用取余构造(将一个数对n取余然后根据余数来查找是否存在该数),当两个数的余数相同时仅仅凭借余数作为下标来查找就会发生错误即hash冲突,那么链地址法其实就是将余数相同的数用链表储存起来,那么...
对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
数据结构算法\哈希表开放地址法解决冲突
哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一...哈希表用除留余数法构造,用伪随机探测在散列法处理冲突。 1.4 在输入人名过程中能自动识别非法输入,并给与非法输入的反馈信息要求重新输入。
1)设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合做实验)。...(3)在哈希函数确定的前提下尝试各种不同处理冲突的方法,考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
用拉链法处理哈希表,用floyd方法求最短路径.
设定哈希函数 H key key MOD 11 表长 11 输入一组关键字序列 根据线性探测再散列解决冲突的方法建立哈希表的存储结构 显示哈希表 任意输入关键字 判断是否在哈希表中
} /*构造哈希表*/ int CreateHash(HashTable *H,int ds[],int len,int d[]){ int i; for(i=0;i;i++){ if(SearchHash(H,ds[i],d)!=-1) return DUPLICATE; InsertHash(H,ds[i],d); if(H->count>=MAXSIZE) return ...
从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录,并计算查找长度, 哈希表保存到文件中,并能从文件中读取数据。...
散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置的表。 哈希函数的构造方法:1)...
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。...(3)分别采用线性法、随机法、溢出法解决冲突,比较不同方法的冲突率,计算不同方法的平均查找长度。 (4)查找并显示给定图书编码的记录。
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录,并计算查找长度, 哈希表保存到文件中,并能从文件中读取数据。...
//使用哈希函数:H(k)=3*k MOD length,并采用开放定址法处理冲突。试对输入的关键字序列构造哈希表,哈希表长度为length, //求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。