数据结构与算法题目集（中文）7-42 整型关键字的散列映射 (25分) （线性探测）

1.题目

给定一系列整型关键字和素数P，用除留余数法定义的散列函数将关键字映射到长度为P的散列表中。用线性探测法解决冲突。

输入格式:

输入第一行首先给出两个正整数N（≤1000）和P（≥N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个整型关键字。数字间以空格分隔。

输出格式:

在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3

2.题目分析

注意：对于重复的数字，只输出它第一次出现的位置，而不是实际存储的位置。。。。。

3.代码

#include<iostream>
using namespace std;
int list[1002] = {0};
int visited[1002] = { 0 };
int main()
{
	int n, m;
	cin >> n >> m;
	int len = 0;
	bool flag = true;
	for (int i = 0; i < n; i++)
	{
		flag = true;
		int temp;
		cin >> temp;
		for (int j = 0; j < m;j++)
		{
			if (list[j] == temp)
			{
				cout << " " << j;
				flag = false;
			}
		}
		if (flag == false)
			continue;
		
		int r = temp%m;
		while (visited[r])//线性探测
		{
			r++;
			if (r == m)r = 0;
		}
		list[r] = temp;
		visited[r] = 1;
		if (i == 0)cout << r;
		else
			cout << " " << r;
	}
}