数据结构上机作业（c++）—— 线性探测再散列法构造哈希表_线性探测再散列法代码

题目概述

设定哈希函数H(key)=key MOD 11(表长=11)。输入一组关键字序列，根据线性探测再散列解决冲突的方法建立哈希表的存储结构，显示哈希表，任意输入关键字，判断是否在哈希表中。

算法分析

线性探测再散列，取di = c*i；本题中采取最简单的情况 c=1。

C++ 源代码

/*
上机序号：24
功能： mod(11) 线性探测再散列建立 哈希表， 输入任意关键字并进行查找 
*/
#include <stdio.h>
#include <stdlib.h> 

/* 宏定义 */
#define DUPLICATE -1						//表中已存在关键字
#define NULLKEY   -2						//标记此处无关键字 
#define FULL      -3						//表已满（冲突次数达上限就认为表满） 
#define SUCCESS 1
#define OK 1
#define EQ(a,b) ((a)==(b))
#define UNSUCCESS -1
#define ERROR -1
typedef int Status;

/* 查找表类型定义 */
typedef int KeyType;			//关键字类型 
typedef struct
{
	int key;					//关键字域	
	//float weight;				//其他域（此处可设为权重） 
}ElemType_Search;				//有序表元素类型 

//0号单元弃用 
typedef struct
{
	ElemType_Search* elem;		//数据元素存储空间基址，0号单元为空
	int length;					//表长度
}Table;

	/* 类型定义 */
	typedef struct								//开放定址哈希表存储表示
	{
		KeyType* elem;							//数据元素存储基址，动态分配数组 
		int count;								//当前哈希表包含的关键字个数 
		//int sizeindex;							//hashsize[sizeindex]为当前容量 
	}HashTable;

	//初始化空的哈希表 
	void InitHash(HashTable* H)
	{
		(*H).count = 0;
		//(*H).sizeindex = -1;
		(*H).elem = NULL;
	}

	//哈希函数
	int fHash(HashTable H, KeyType K)	
	{
		return K % 11;
	}

	//线性探测再散列
	void collision(HashTable H, int* p)	
	{
		*p = (*p + 1) % 11;
	}

	//哈希表关键字搜索，p指向查找成功后的元素的位置
	Status SearchHash(HashTable H, KeyType K, int* p)
	{
		int c, sup;
		c = 0;							//记录冲突次数 	
		sup = 11/ 2;	//冲突上限 
		*p = fHash(H, K);				//p指向K应该插入的地址 	
		while (1)						//该位置有记录且与K不等
		{
			if (H.elem[*p] == NULLKEY)		
				return NULLKEY;
			else if (EQ(H.elem[*p], K))     //表中已有此关键字
				return DUPLICATE;		
			else if (++c == sup)			//已达冲突上限 
				return FULL;
			else
				collision(H, p);		//重新定位p的地址 
		}
	}

	//重建哈希表
	Status RecreateHashTable(HashTable* H)
	{
		int i,v;
		HashTable* p;

		(*H).count = 0;
		//(*H).sizeindex++;
		v =11;

		if ((*H).elem != NULL)
			free((*H).elem);
		(*H).elem = (KeyType*)malloc(v * sizeof(KeyType));
		if ((*H).elem == NULL)
			return ERROR;
		for (i = 0; i < v; i++)
			(*H).elem[i] = NULLKEY;
		return OK;
	}

	//哈希表关键字的插入
	Status InsertHash(HashTable* H, KeyType K)
	{
		int flag, p;
		flag = SearchHash(*H, K, &p);
		if (flag == FULL)				//表已满 
		{
			RecreateHashTable(H);	//重建哈希表  
			return UNSUCCESS;
		}
		else
		{
			if (flag == NULLKEY)
			{
				H->elem[p] = K;		//插入K
				++(*H).count;
			}
			return SUCCESS;
		}
	}

	//创建哈希表 
	Status CreateHash(HashTable* H, Table T)
	{
		int i, tag;
		InitHash(H);
		RecreateHashTable(H);
		i = 1;
		while (i <= T.length)				//将T中关键字依次插入到哈希表中
		{
			tag = InsertHash(H, T.elem[i].key);
			if (tag == SUCCESS)			//表中已有关键字或关键字顺利插入 
				i++;
			else						//重建哈希表后重新填充 
				i = 1;
		}
		return OK;
	}

	//输出哈希表中的关键字
	void PrintHash(HashTable H)
	{
		int i, v;
		v = 11;
		printf("哈希表容量为：%d，现有元素：%d 个，表中元素为：\n", v, H.count);
		for (i = 0; i < v; i++)
		{
			if (H.elem[i] != NULLKEY)
				printf("%d ", H.elem[i]);
		}
		printf("\n");
	}

	int main()
	{
		printf("------------------------创建并输出一个查找表----------------------\n");
		Table* T = (Table*)malloc(sizeof(Table));
		int len;
		printf("请输入要存储的结点数目：\n");
		scanf("%d", &len);
		T->length = len;
		T->elem = (ElemType_Search*)malloc(sizeof(int) * (len + 1));
		int i;
		printf("请输入键值：\n");
		for (int i = 1; i <= len; i++)
			scanf("%d", &T->elem[i]);
		HashTable H;
		CreateHash(&H, *T);
		PrintHash(H);
		printf("-------------------------------查找测试----------------------------\n");										//查找测试

			printf("请输入要查找的次数\n");
			int x;
			scanf("%d", &x);
			Status r;
			for (int i = 0; i < x; i++)
			{
				KeyType key;
				printf("请输入要查找的关键字\n");
				scanf("%d", &key);
				int p = 0;
				r = SearchHash(H, key, &p);
				if (r == DUPLICATE)
					printf("查找成功，%d 在哈希表下标为 %d 的位置。\n", key, p);
				else
					printf("查找失败！\n");
			}
	}
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
'
运行
运行

测试用例

• 测试用例一
  

• 测试用例二
  

• 测试用例三