c语言哈希表简单实现

散列表
散列表也被称为哈希表。
把表中的数值以键值的形式映射到表中。然后可以直接通过键值来查找到该数据。

给定表格M,可以通过函数 f(x) 来快速定位该表中某一个数据。那么表格M称为
哈希表(散列表), 用来定位的函数 f(x)称为哈希函数(哈希映射)

除留取余： 对于有M个数值的无序数列，用小于M的最大质数来做除数，把余数当成key(键值)

冲突:通过哈希函数以后，得到键值是同一个，那么这个时候称为冲突

案例:
假设有10000个数的无序数列，建立哈希表，快速查找其中的某一个数值
如果要排除相同键值的数，可以采用链表的方式继续遍历。

#include<stdio.h>
#include<time.h>
#include <stdlib.h>

#define NUM 10000

//结构体体
typedef struct list{
	int data;
	int set;
	struct list *next;
}Hash,*HASH;

//节点创建
HASH creat_node(int data,int set)
{
	HASH node = (HASH)malloc(sizeof(Hash));
	if(node == NULL)
	{
		printf("node malloc failed\n");
		return NULL;
	}
	node->data=data;
	node->set=set;
	node->next=NULL;
	return node;
}

//尾插
void push_tail(HASH head,HASH node)
{
	HASH p=head;
	while(p->next!=NULL)
	{
		p=p->next;
	}
	
	p->next=node;
}
//创建随机数组
int *creat_arr()
{
	int *arr = (int *)calloc(NUM,sizeof(int )); //申请堆空间
	for(int i=0;i<NUM;i++)
	{
		arr[i]=rand()%NUM;//生成随机数
	}

	return arr;
}
//创建哈希表
HASH *creat_hash(int *arr)
{
	int i=0,key=0;
	HASH *h=malloc(sizeof(HASH)*100);
	for(i=0;i<100;i++)
	{
		h[i]=malloc(sizeof(Hash));
		h[i]->next=NULL;
	}
	HASH node=NULL;
	for(i=0;i<NUM;i++)
	{
		key=arr[i]%100;//键值计算
		node = creat_node(arr[i],i);//创建节点保存数据和位数
		push_tail(h[key],node);//将节点加入哈希表
	}
	printf("OK\n");
	return h;
	
}

int main()
{
	int key=0;
	HASH p = NULL;
	int number = 0; 
	srand(time(NULL));//开启随机种子
	int *arr=creat_arr();//创建随机数组
	HASH *h=creat_hash(arr);//创建哈希表
	while(1)
	{
		printf("输入一个数");
		scanf("%d",&number);
		while(getchar()!='\n');//清除缓冲区
		key=number%100; 
		p=h[key]->next;
		if(number==-1)//等于-1跳出循环程序结束
		{
			break;
		}
		while(p!=NULL)
		{
			if(p->data==number)
			{
				printf("找到了%d他在第%d个\n",p->data,p->set);
				break;
			}
			p=p->next;
		}
	}
	

	return 0;
}














1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119