<nobr>1<br>
2<br>
3<br>
4<br>
5<br>
6<br>
7<br>
8<br>
9<br>
10<br>
11<br>
12<br>
13<br>
14<br>
15<br>
16<br>
17<br>
18<br>
19<br>
20<br>
21<br>
22<br>
23<br>
24<br>
25<br>
26<br>
27<br>
28<br>
29<br>
30<br>
31<br>
32<br>
33<br>
34<br>
35<br>
36<br>
37<br>
38<br>
39<br>
40<br>
41<br>
42<br>
43<br>
44<br>
45<br>
46<br>
47<br>
48<br>
49<br>
50<br>
51<br>
52<br>
53<br>
54<br>
55<br>
56<br>
57<br>
58<br>
59<br>
60<br>
61<br>
62<br>
63<br>
64<br>
65<br>
66<br>
67<br>
68<br>
69<br>
70<br>
71<br>
72<br>
73<br>
74<br>
75<br>
76<br>
77<br>
78<br>
79<br>
80<br>
81<br>
82<br>
83<br>
84<br>
85<br>
86<br>
87<br>
88<br>
89<br>
90<br>
91<br>
92<br>
93<br>
94<br>
95<br>
96<br>
97<br>
98<br>
99<br>
100<br>
101<br>
102<br>
103<br>
104<br>
105<br>
106<br>
107<br>
108<br>
109<br>
110<br>
111<br>
112<br>
113<br>
114<br>
115<br>
116<br>
117<br>
118<br>
119<br>
120<br>
121<br>
122<br>
123<br>
124<br>
125<br>
126<br>
127<br>
128<br>
129<br>
130<br>
131<br>
132<br>
133<br>
134<br>
135<br>
136<br>
137<br>
138<br>
139<br>
140<br>
141<br>
142<br>
143<br>
144<br>
145<br>
146<br>
147<br>
148<br>
149<br>
150<br>
151<br>
152<br>
153<br>
154<br>
155<br>
156<br>
157<br>
158<br>
159<br>
160<br>
161<br>
162<br>
163<br>
164<br>
165<br>
166<br>
167<br>
168<br>
169<br>
170<br>
171<br>
172<br>
173<br>
174<br>
175<br>
176<br>
177<br>
178<br>
179<br>
180<br>
181<br>
182<br>
183<br>
184<br>
185<br>
186<br>
187<br>
188<br>
189<br>
190<br>
191<br>
192<br>
193<br>
194<br>
195<br>
196<br>
197<br>
198<br>
199<br>
200<br>
201<br>
202<br>
203<br>
204<br>
205<br>
206<br>
207<br>
208<br>
209<br>
210<br>
211<br>
212<br>
213<br>
214<br>
215<br>
216<br>
217<br>
218<br>
219<br>
220<br>
221<br>
222<br>
223<br>
224<br>
225<br>
226<br>
227<br>
228<br>
229<br>
230<br>
231<br>
232<br>
233<br>
234<br>
235<br>
236<br>
237<br>
238<br>
239<br>
240<br>
241<br>
242<br>
243<br>
244<br>
245<br>
246<br>
247<br>
248<br>
249<br>
250<br>
251<br>
252<br>
253<br>
254<br>
255<br>
256<br>
257<br>
258<br>
259<br>
260<br>
261<br>
262<br>
263<br>
264<br>
265<br>
266<br>
267<br>
268<br>
269<br>
270<br>
271<br>
272<br>
273<br>
274<br>
275<br>
276<br>
277<br>
278<br>
279<br>
280<br></nobr>
|
|
#include"hash.h" #include"common.h" #include<assert.h>
typedefenumentry_status
{
EMPTY,
ACTIVE,
DELETED
}entry_status_t;
typedefstructhash_node
{ enumentry_statusstatus; void*key; unsignedintkey_size;//在拷贝进新的哈希表时有用 void*value; unsignedintvalue_size;//在拷贝进新的哈希表时有用 }hash_node_t;
structhash
{ unsignedintbuckets; unsignedintsize;//累加,如果size>buckets/2,则需要开裂建立新表 hashfunc_thash_func;
hash_node_t*nodes;
};
unsignedintnext_prime(unsignedintn); intis_prime(unsignedintn);
unsignedinthash_get_bucket(hash_t*hash,void*key);
hash_node_t*hash_get_node_by_key(hash_t*hash,void*key,unsignedintkey_size);
hash_t*hash_alloc(unsignedintbuckets,hashfunc_thash_func)
{
hash_t*hash=(hash_t*)malloc(sizeof(hash_t)); //assert(hash!=NULL); hash->buckets=buckets;
hash->hash_func=hash_func; intsize=buckets*sizeof(hash_node_t);
hash->nodes=(hash_node_t*)malloc(size);
memset(hash->nodes,0,size);
printf("Thehashtablehasallocate.\n"); returnhash;
}
voidhash_free(hash_t*hash)
{ unsignedintbuckets=hash->buckets; inti; for(i=0;i<buckets;i++)
{ if(hash->nodes[i].status!=EMPTY)
{
free(hash->nodes[i].key);
free(hash->nodes[i].value);
}
}
free(hash->nodes);
printf("Thehashtablehasfree.\n");
}
void*hash_lookup_entry(hash_t*hash,void*key,unsignedintkey_size)
{
hash_node_t*node=hash_get_node_by_key(hash,key,key_size); if(node==NULL)
{ returnNULL;
}
returnnode->value;
}
voidhash_add_entry(hash_t*hash,void*key,unsignedintkey_size, void*value,unsignedintvalue_size)
{ if(hash_lookup_entry(hash,key,key_size))
{
fprintf(stderr,"duplicatehashkey\n"); return;
}
unsignedintbucket=hash_get_bucket(hash,key); unsignedinti=bucket; unsignedintj=i; intk=1; intodd=1;
while(hash->nodes[i].status==ACTIVE)
{ if(odd)
{
i=j+k*k;
odd=0;
//i%hash->buckets; while(i>=hash->buckets)
{
i-=hash->buckets;
}
} else
{
i=j-k*k;
odd=1;
while(i<0)
{
i+=hash->buckets;
}
++k;
}
}
hash->nodes[i].status=ACTIVE; if(hash->nodes[i].key)////释放原来被逻辑删除的项的内存 {
free(hash->nodes[i].key);
}
hash->nodes[i].key=malloc(key_size);
hash->nodes[i].key_size=key_size; //保存key_size;
memcpy(hash->nodes[i].key,key,key_size); if(hash->nodes[i].value)//释放原来被逻辑删除的项的内存 {
free(hash->nodes[i].value);
}
hash->nodes[i].value=malloc(value_size);
hash->nodes[i].value_size=value_size; //保存value_size;
memcpy(hash->nodes[i].value,value,value_size);
if(++(hash->size)<hash->buckets/2) return;
//在搜索时可以不考虑表装满的情况; //但在插入时必须确保表的装填因子不超过0.5。 //如果超出,必须将表长度扩充一倍,进行表的分裂。
unsignedintold_buckets=hash->buckets;
hash->buckets=next_prime(2*old_buckets);
hash_node_t*p=hash->nodes; unsignedintsize;
hash->size=0; //从0 开始计算
size=sizeof(hash_node_t)*hash->buckets;
hash->nodes=(hash_node_t*)malloc(size);
memset(hash->nodes,0,size);
for(i=0;i<old_buckets;i++)
{ if(p[i].status==ACTIVE)
{
hash_add_entry(hash,p[i].key,p[i].key_size,p[i].value,p[i].value_size);
}
}
for(i=0;i<old_buckets;i++)
{
// active or deleted if(p[i].key)
{
free(p[i].key);
} if(p[i].value)
{
free(p[i].value);
}
}
free(p); //释放旧表
}
voidhash_free_entry(hash_t*hash,void*key,unsignedintkey_size)
{
hash_node_t*node=hash_get_node_by_key(hash,key,key_size); if(node==NULL) return;
//逻辑删除 node->status=DELETED;
}
unsignedinthash_get_bucket(hash_t*hash,void*key)
{ unsignedintbucket=hash->hash_func(hash->buckets,key); if(bucket>=hash->buckets)
{
fprintf(stderr,"badbucketlookup\n");
exit(EXIT_FAILURE);
}
returnbucket;
}
hash_node_t*hash_get_node_by_key(hash_t*hash,void*key,unsignedintkey_size)
{ unsignedintbucket=hash_get_bucket(hash,key); unsignedinti=1; unsignedintpos=bucket; intodd=1; unsignedinttmp=pos; while(hash->nodes[pos].status!=EMPTY&&memcmp(key,hash->nodes[pos].key,key_size)!=0)
{ if(odd)
{
pos=tmp+i*i;
odd=0;
//pos%hash->buckets; while(pos>=hash->buckets)
{
pos-=hash->buckets;
}
} else
{
pos=tmp-i*i;
odd=1;
while(pos<0)
{
pos+=hash->buckets;
}
i++;
}
}
if(hash->nodes[pos].status==ACTIVE)
{ return&(hash->nodes[pos]);
}
//如果运行到这里,说明pos为空位或者被逻辑删除
//可以证明,当表的长度hash->buckets为质数且表的装填因子不超过0.5时, //新的表项x一定能够插入,而且任何一个位置不会被探查两次。 //因此,只要表中至少有一半空的,就不会有表满问题。
returnNULL;
}
unsignedintnext_prime(unsignedintn)
{ //偶数不是质数 if(n%2==0)
{
n++;
}
for(;!is_prime(n);n+=2);//不是质数,继续求 returnn;
}
intis_prime(unsignedintn)
{ unsignedinti; for(i=3;i*i<=n;i+=2)
{ if(n%i==0)
{ //不是,返回0 return0;
}
}
//是,返回1 return1;
}
|
相关推荐
散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组... 处理冲突的方法:1)开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列) 2)再哈希法 3)链地址法 4)建立一 公共溢出区
选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是在0-10的散列地址中,对关键序列(22,41,53,46,30,01,67)构造哈希表并求等概率情 况下查找成功与不成功过的平均查找长度
1.问题描述 为某个单位建立一个员工通讯录管理系统,可以方便查询每一个员工的电话与地址。...(3)采用二次探测再散列法解决冲突; (4)查找并显示给定电话号码的记录; (5)通讯录信息文件保存。
(4)哈希函数用除留余数法构造,采用二次探测再散列法解决冲突; (5)查找并显示给定电话号码的记录; (6)通讯录信息保存。 测试数据 取周围熟悉的30个人的姓名及相关信息。 实现提示 人名长度均不超过19个...
通信录查询系统-课程设计报告书.doc 设计以姓名为关键字的散列表(哈希表),实现通讯录查找系统,完成相应的建表和查表程序。...(4)哈希函数用除留余数法构造,采用二次探测再散列法解决冲突;
1、散列函数的设计 2、冲突的处理 1、直接地址法 2、除留余数法 3、数字分析法 4、平方取中法 1、线性探测法 3、随机探测法 2、二次探测法 4、拉链法:
(4)哈希函数用除留余数法构造,采用二次探测再散列法解决冲突; (5)根据姓名查找,找到显示给定记录的电话号码和地址;找不到提示通讯录无此人。 (6)通讯录信息保存到文件。 ==============================...
设计散列表实现通讯录查找系统,使得平均查找长度不超过R,完成相应的建表和查表程序。从键盘输入各记录,分别以姓名为关键字建立散列表。...哈希函数用除留余数法构造,采用二次探测再散列法解决冲突。
首先用C++实现单链表编程,再基于编写好的单链表类,实现堆栈类的定义和实现。 c. 链表类和堆栈类都要包含必要的成员函数(按照教材要求)。 2、 已知a[n]为整数数组,试写出实现下列运算的递归代码(C或C++...
6,线性探测法处理冲突,构造该散列表。 关键字序列: 14,7,11,4,49,54,写出直接插入排序,起泡排序,简单选择排序(快速排序)每趟结果。 初始序列:{14,7,11,4,49,54} 第一趟{4,7,11},14,{49,54} ...