6-3 哈希表的创建及查找(线性探查法) (10分)_数据结构实验7_羊卓的杨_输入不大于m的n个不为0(0表示空值)的数,用线性探查法解决冲突构造散列表。输入一

6-3 哈希表的创建及查找(线性探查法) (10分)

实现哈希表创建及查找算法，哈希函数使用除余法，用线性探测法处理冲突。

函数接口定义：

void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0（0表示空值）的数，用线性探查法解决冲突构造散列表
int SearchHash(HashTable HT[],int key); //输入一个值key，在散列表中查找key位置
1
2

其中 HT 表示哈希表， n表示记录数，key要查找的关键字

裁判测试程序样例：

#include<iostream>
using namespace std;

#define m 16 
#define NULLKEY 0 //单元为空的标记

struct HashTable{
   int  key;
};

void CreateHash(HashTable HT[],int n);
int SearchHash(HashTable HT[],int key);

int main()
{    int value,key;
    int result;
    int i,j,n;
    HashTable HT[m];
    for(i=0;i<m;i++)
     HT[i].key=0;
    cin >> n;
    if(n>m) return 0;
    CreateHash(HT,n);
    cin >> key;
    result=SearchHash(HT,key);
    if(result!=-1)
        cout << "search success，The key is located in "<< result+1;
    else
        cout << "search failed";
    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

输入样例:

12
19 14 23 1 68 20 84 27 55 11 10 79
55
1
2
3

输出样例:

search success，The key is located in 6 
1

答案样例:

//输入不大于m的n个不为0（0表示空值）的数，
//用线性探查法解决冲突构造散列表
void CreateHash(HashTable HT[], int n) {//创作不易，点个赞吧，新春快乐~
	int hash_table[m];//创建一个辅助数组 
	int temp;//存放余数 
	for(int i=0; i<n; i++)
		cin >> hash_table[i]; 
	for(int i=0; i<m; i++)
		HT[i].key = 0;//初始化HT数组 
	for(int i=0; i<n; i++) {
		temp = hash_table[i] % 13;//求余数 
		if(HT[temp].key==0) {//如果正好有空就放进去 
			HT[temp].key = hash_table[i];
		} else { 
			int flag=0;
			for(int j=temp+1; j<n; j++) {//从余数位置往后看有没有空余位置 
				if(HT[j].key==0) {//如果有位置就放进去 
					HT[j].key = hash_table[i];
					flag = 1;
					break;
				}
			}
			if(flag==0) {//如果还是没有位置 
				for(int j=0; j<temp; j++) {//就从0位置往后找，找到余数位置之前 
					if(HT[j].key==0) {
						HT[j].key = hash_table[i];
						break;
					}
				}
			}
		}
	}
}
//输入一个值key，在散列表中查找key位置
int SearchHash(HashTable HT[],int key) {
	int temp = key % 13;//求余数
	for(int i=temp; i<m; i++) {//从余数位置往后查 
		if(HT[i].key == key)
			return i;
	}
	for(int i=0; i<temp; i++) {//从头查到余数位置之前 
		if(HT[i].key == key)
			return i;
	}
	return -1;
}
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

感谢您的阅读，点个赞吧❤⭐
哔哩哔哩/bilibili：羊卓的杨
公众号：羊卓的杨