|
一.t头文件hash.h的实现
#ifndef __HASH_H__
#define __HASH_H__
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<unistd.h>
#define N 11
typedef int datatype_el;
typedef struct listnode
{
datatype_el data;
struct listnode *next;
}list_node,*list_pnode;
typedef list_pnode datatype;
typedef struct hastbl
{
datatype *h;
int length;
}hash_tbl,*hash_tp;
extern void init_hash(hash_tp *hp,int m);
extern void create_hash(hash_tp hp,datatype_el *a);
extern list_pnode hash_search(hash_tp hp,int key);
extern void hash_show(hash_tp hp,int hash_val,list_pnode new);
#endif
二.函数实现hash.c
#include"hash.h"
int p;
void init_hash(hash_tp *hp,int m)
{
(*hp) = (hash_tp)malloc(sizeof(hash_tbl));
if(NULL == *hp)
{
perror("malloc");
exit(1);
}
(*hp)->length = m;
(*hp)->h =(datatype*)malloc((*hp)->length * sizeof(datatype));
if(NULL == (*hp)->h)
{
perror("malloc");
exit(1);
}
for(int i = 0;i <(*hp)->length;i++)
(*hp)->h[i] = NULL;
}
int fun(int m)
{
int i;
for(;m > 1;m--)
{
for(i = 2;i < m;i++)
{
if(m % i == 0)//求质数
break;
}
if(i >= m)
return m;
}
return -1;
}
void create_hash(hash_tp hp,datatype_el *a)
{
int hash_val,i;
list_pnode new;
p = fun(hp -> length);
if(p == -1)
exit(1);
for(i = 0;i < N;i++)
{
//1.用除留余数法构建hash函数用链地址法处理冲突
hash_val = a[i] % p;
//申请结点空间
new = (list_pnode)malloc(sizeof(list_node));
if(NULL == new)
{
perror("malloc");
exit(1);
}
new -> data = a[i];
//3.将记录存储在hash_val的位置
new ->next = hp ->h[hash_val];
hp->h[hash_val] = new;
hash_show(hp,hash_val,new);
sleep(1);
}
}
list_pnode hash_search(hash_tp hp,int key)
{
int hash_val;
list_pnode tp;
hash_val = key % p;//用除留余数法得到hash地址
for(tp = hp->h[hash_val];tp != NULL; tp=tp->next)
if(tp->data == key)
return tp;
return NULL;
}
void hash_show(hash_tp hp,int hash_val,list_pnode new)
{
list_pnode p;
int i;
for(i = 0;i < hp->length;i++)
{
printf("hp-sh[%02d]:",i);
for(p = hp->h[i];p!=NULL;p = p->next)
{
printf("--->%d",p->data);
}
if(i == hash_val)
printf(" 正在插入%d",new->data);
puts("");
}
printf("***************************************");
}
三包含主函数的test.c文件
#include"hash.h"
int main()
{
hash_tp hp;
int m,key;
char ch;
list_pnode ret;
datatype_el a[N] = {23,34,14,38,46,16,68,15,7,31,26};
//1.根据记录个数得到hash表的长度
m =(int) ceil(N/0.75); //向下取整
//2,初始化哈系表空间
init_hash(&hp,m);
//3.创建hash表
create_hash(hp,a);
//4.hash表查找
while(1)
{
printf("pls input key");
scanf("%d",&key);
ret = hash_search(hp,key);
if(ret == NULL)
{
printf("search error!\n");
}
else
{
printf("search %d : %d\n",key,ret->data);
}
printf("continue?(Y/y)");
while(getchar() != '\n');
scanf("%c",&ch);
if(ch == 'y' || ch == 'Y')
continue;
else
break;
}
return 0;
}
四.makefile 文件
CC = gcc
CFLAGS= -Wall -g -O0
test:hash.c test.c
$(CC) $(CFLAGS) -o $@ $^
clean:
$(RM) hash_search .*.sw?
| 
转播
