这个问题是关于合并散列的。这是一个学校作业,我没有人可以问。我设法通过了示例用例,但无法通过任何隐藏的测试用例。
我的内心现在正在死去。
请派人来帮忙。
我已经附上了完整的代码,我只应该工作的HashInsert()
和HashFind()
的功能。
#include <stdio.h>
#include <stdlib.h>
#define TABLESIZE 37
#define PRIME 13
enum Marker { EMPTY, USED };
typedef struct _slot {
int key;
enum Marker indicator;
int next;
} HashSlot;
int HashInsert(int key, HashSlot hashTable[]);
int HashFind(int key, HashSlot hashTable[]);
int hash(int key)
{
return (key % TABLESIZE);
}
int main()
{
int opt;
int i;
int key;
int index;
HashSlot hashTable[TABLESIZE];
for (i = 0; i < TABLESIZE; i++) {
hashTable[i].next = -1;
hashTable[i].key = 0;
hashTable[i].indicator = EMPTY;
}
printf("============= Hash Table ============\n");
printf("|1. Insert a key to the hash table |\n");
printf("|2. Search a key in the hash table |\n");
printf("|3. Print the hash table |\n");
printf("|4. Quit |\n");
printf("=====================================\n");
printf("Enter selection: ");
scanf("%d", &opt);
while (opt >= 1 && opt <= 3) {
switch (opt) {
case 1:
printf("Enter a key to be inserted:\n");
scanf("%d", &key);
index = HashInsert(key, hashTable);
if (index < 0)
printf("Duplicate key\n");
else if (index < TABLESIZE)
printf("Insert %d at index %d\n", key, index);
else
printf("Table is full.\n");
break;
case 2:
printf("Enter a key for searching in the HashTable:\n");
scanf("%d", &key);
index = HashFind(key, hashTable);
if (index != -1)
printf("%d is found at index %d.\n", key, index);
else
printf("%d is not found.\n", key);
break;
case 3:
printf("index:\t key \t next\n");
for (i = 0; i < TABLESIZE; i++)
printf("%d\t%d\t%d\n", i, hashTable[i].key, hashTable[i].next);
break;
}
printf("Enter selection: ");
scanf("%d", &opt);
}
return 0;
}
int HashInsert(int key, HashSlot hashTable[])
{
// Write your code here
int index = hash(key);
if (hashTable[index].key == key) {
return -1;
}
for (int x = 0; x < TABLESIZE; x++) {
int index2 = hash(key + x);
if (hashTable[index2].key == key) {
return -1;
}
if (hashTable[index2].indicator == EMPTY) {
hashTable[index2].key = key;
hashTable[index2].indicator = USED;
if (x > 0) {
hashTable[index].next = index2;
}
return index2;
}
}
return -1;
}
int HashFind(int key, HashSlot hashTable[])
{
// Write your code here
int index = hash(key);
for (int x = 0; x < TABLESIZE; x++) {
if (hashTable[x].key == key) {
return x;
}
}
return -1;
}
我不知道代码出了什么问题,我已经尝试了许多示例测试用例,但仍然没有弄清楚。
1条答案
按热度按时间vyswwuz21#
你的方法不正确:你永远不会测试哈希槽
indicator
来检查空槽。在
HashFind()
函数中,如果插槽indicator
是EMPTY
,则应立即停止,并遵循next
链,当next
是-1
时停止。在
HashInsert()
函数中,在可用位置插入密钥时,必须更新next
和indicator
字段。还要注意,
hash
函数必须确保返回值在0
到TABLESIZE-1
的范围内。当前的实现可能会为负键返回负值。以下是修改后的版本: