C语言 无法找出为什么我的HashInsert和HashFind函数是错误的

xcitsw88  于 2023-03-22  发布在  其他
关注(0)|答案(1)|浏览(98)

这个问题是关于合并散列的。这是一个学校作业,我没有人可以问。我设法通过了示例用例,但无法通过任何隐藏的测试用例。
我的内心现在正在死去。
请派人来帮忙。
我已经附上了完整的代码,我只应该工作的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;
}

我不知道代码出了什么问题,我已经尝试了许多示例测试用例,但仍然没有弄清楚。

vyswwuz2

vyswwuz21#

你的方法不正确:你永远不会测试哈希槽indicator来检查空槽。
HashFind()函数中,如果插槽indicatorEMPTY,则应立即停止,并遵循next链,当next-1时停止。
HashInsert()函数中,在可用位置插入密钥时,必须更新nextindicator字段。
还要注意,hash函数必须确保返回值在0TABLESIZE-1的范围内。当前的实现可能会为负键返回负值。
以下是修改后的版本:

int hash(int key) {
    // return index in range 0 to TABLESIZE-1
    return (unsigned)key % TABLESIZE;
}

int HashFind(int key, HashSlot hashTable[]) {
    int index = hash(key);
    for (;;) {
        if (hashTable[index].indicator == EMPTY)
            return -1;
        if (hashTable[index].key == key)
            return index;
        // follow the next chain
        index = hashTable[index].next;
        if (index < 0)
            return -1;
    }
}

int HashInsert(int key, HashSlot hashTable[]) {
    int index = hash(key);
    for (;;) {
        if (hashTable[index].indicator == EMPTY) {
            // empty slot: insert key here
            hashTable[index].indicator = USED;
            hashTable[index].key = key;
            return index;
        }
        if (hashTable[index].key == key) {
            // key already present
            return -1;
        }
        if (hashTable[index].next >= 0) {
            // follow the next chain
            index = hashTable[index].next;
        } else {
            // otherwise try and allocate a new slot
            int index2 = index;
            for (int x = 1; x < TABLESIZE; x++) {
                index2 = (index2 + PRIME) % TABLESIZE;
                if (hashTable[index2].indicator == EMPTY) {
                    // use the empty slot and link it in the chain
                    hashTable[index2].indicator = USED;
                    hashTable[index2].key = key;
                    hashTable[index].next = index2;
                    return index2;
                }
            }
            return TABLESIZE;   // table is full
        }
    }
}

相关问题