xdoj用除留余数法和线性探测再散列的冲突解决方法构造哈希表

标题

哈希表

时间限制

2 S

内存限制

10000 Kb

问题描述：

用除留余数法和线性探测再散列的冲突解决方法构造哈希表

输入：

输入数据第一行为两个正整数分别为：哈希表表长m（m<100）和除数p（p<=m）。后面每一行是一个整数关键字，以-1作为输入的结束。

输出：

若输入的关键字在哈希表中已存在，则输出该关键字在哈希表中的位置，继续等待输入下一个关键字。

若输入的关键字在哈希表中不存在，则判断当前哈希表中关键字的个数是否等于m-1，若相等，则输出“Table full”，程序结束；否则将关键字插入哈希表，并输出该关键字插入在哈希表中的位置，继续等待输入下一个关键字。

示例输入：

5 3

1

2

3

4

5

-1

示例输出：

1

2

0

3

Table full

#include <bits/stdc++.h>
// #include <iostream>
#define HASHSIZE 100// 定义散列表为数组的长度
#define NULLKEY -1
typedef struct
{int elem[HASHSIZE];int count;
} HashTable;// 初始化哈希表
void Init(HashTable *hashtable, int l)
{hashtable->count = 0;for (int i = 0; i < HASHSIZE; i++){hashtable->elem[i] = NULLKEY;}
}// 哈希函数
int Hash(int data, int d)
{return data % d;
}// 将元素映射到哈希表
void Insert(HashTable* hashtable, int data, int d, int l)
{int hashAddress = Hash(data, d);while (hashtable->elem[hashAddress] != NULLKEY){// 解决冲突hashAddress += 1;}hashtable->elem[hashAddress] = data;printf("%d\n", hashAddress);hashtable -> count++;
}// 查找数据data，返回对应的下表
int SearchHash(HashTable *hashtable, int data, int divisor, int length)
{int hashAddress = Hash(data, divisor);while (hashtable->elem[hashAddress] != data){ // 解决冲突hashAddress += 1;if (hashtable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data, divisor))// 出现了NULLKEY值或者经过了一个周期都说明找不到了{return -1;}}return hashAddress;
}
using namespace std;int main(void)
{int length, divisor; // printf("请输入表长和除数：");scanf("%d %d", &length, &divisor);if(length >= 100 || divisor > length)return 0;HashTable hashTable;Init(&hashTable, length);//初始化为-1int temp;for(;;){// printf("请输入关键字：");scanf("%d", &temp);if(temp == -1)break;int result = SearchHash(&hashTable, temp, divisor, length);if(result != -1){printf("%d\n", result);} else {if(hashTable.count == length - 1){printf("Table full\n");break;} else Insert(&hashTable, temp, divisor, length);}}return 0;
}