c - 尝试将项目添加到链接列表的问题

标签 c linked-list hashtable

我正在使用链式哈希表并尝试附加一个条目，以防已经存在具有相同哈希键的条目。但我遇到了问题。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define TABLE_SIZE 8

typedef struct stItem item;
struct stItem {
    int key;
    item *next;
};

void init(item * H[]) {

    int i = 0;
    for (i; i < TABLE_SIZE; i++)
        H[i] = NULL;
}

int h(int k) {

    // this does not work at all (but from exercise description), replaced with temp code

    /*
    int m = TABLE_SIZE;
    int A = ( sqrt(5.0) - 1) / 2;

    return m * (k * A % 1);
    */

    return k % TABLE_SIZE;
}

void insert(int key, item * H[]) {

    int keyHashed = h(key);

    if (H[keyHashed] == NULL) {

        printf("hashkey: %d (%d)\n", keyHashed,key);

        item * temp = malloc(sizeof(item));
        temp->key = key;
        temp->next = NULL;

        H[keyHashed] = temp;
    }

    else {

        printf("hashkey: %d (%d) (duplicate)\n", keyHashed,key);

        item * temp = malloc(sizeof(item));
        temp->key = NULL;
        temp->next = H[keyHashed]->next;

        while (temp->next != NULL)
            temp = temp->next;

        temp->next = malloc(sizeof(item));
        temp->next->key = key;
        temp->next->next = NULL;
    }
}

int search(int key, item * H[]) {

        int keyHashed = h(key);

        if (H[keyHashed] == NULL)
            return -1;

        else if (H[keyHashed]->key != key) {

            item * temp = malloc(sizeof(item));
            temp->key = NULL;
            temp->next = H[keyHashed]->next;

            while (temp->key != key && temp != NULL)
                temp = temp->next;

            if (temp->key == key) {
                return keyHashed;
            }

            else
                return -1;
        }

        else
            return keyHashed;
}

void printHash(item * H[]) {

    printf("\nTable size: %d\n", TABLE_SIZE);

    int i = 0;

    for (i; i < TABLE_SIZE; i++) {

        if (H[i] != NULL) {
            printf("i: %d          key: %d",i,H[i]->key);

            if (H[i]->next != NULL) {

                printf("chaining print\n");

                item * temp = malloc(sizeof(item));
                temp->key = NULL;
                temp->next = H[i]->next;

                while (temp->key != NULL) {
                    printf(" -> %d", temp->key);
                }

                printf("\n");
            }

            else
                printf("\n");
        }

        else
            printf("i: %d          key: none\n",i);
    }
}

void test() {

    // a)
    int array[7] = {111,10112,1113,5568,63,1342,21231};

    item *h[TABLE_SIZE];
    init(h);

    int i = 0;
    for (i; i < 7; i++)
        insert(array[i], h);

    // b)
    printHash(h);

    // c)
    printf("Search result for 1: %d", search(1, h));
    printf("Search result for 10112: %d", search(10112, h));
    printf("Search result for 1113: %d", search(1113, h));
    printf("Search result for 5568: %d", search(5568, h));
    printf("Search result for 337: %d", search(337, h));
}

int main() {
    test();
}

输出:

hashkey: 7 (111)
hashkey: 0 (10112)
hashkey: 1 (1113)
hashkey: 0 (5568) (duplicate)
hashkey: 7 (63) (duplicate)
hashkey: 6 (1342)
hashkey: 7 (21231) (duplicate)

Table size: 8
i: 0          key: 10112
i: 1          key: 1113
i: 2          key: none
i: 3          key: none
i: 4          key: none
i: 5          key: none
i: 6          key: 1342
i: 7          key: 111

Process returned -1073741819 (0xC0000005)   execution time : 0.385 s
Press any key to continue.

搜索输出也没有出现。我认为这是由于代码在它到达那部分之前就被破坏造成的，可能是在它试图打印链接列表时。

感谢 Alan Au 的帮助，我发现并修复了代码中的问题(好吧，除了我仍然需要弄清楚的哈希算法)。

这是工作代码和输出:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define TABLE_SIZE 8

typedef struct stItem item;
struct stItem {
    int key;
    item *next;
};

void init(item * H[]) {

    int i = 0;
    for (i; i < TABLE_SIZE; i++)
        H[i] = NULL;
}

int h(int k) {

    // this does not work at all (but from exercise description), replaced with temp code

    /*
    int m = TABLE_SIZE;
    int A = ( sqrt(5.0) - 1) / 2;

    return m * (k * A % 1);
    */

    return k % TABLE_SIZE;
}

void insert(int key, item * H[]) {

    int keyHashed = h(key);

    if (H[keyHashed] == NULL) {

        printf("hashkey: %d (%d)\n", keyHashed,key);

        item * temp = malloc(sizeof(item));
        temp->key = key;
        temp->next = NULL;

        H[keyHashed] = temp;
    }

    else {

        printf("hashkey: %d (%d) (duplicate)\n", keyHashed,key);

        item * temp = H[keyHashed];

        while (temp->next != NULL)
            temp = temp->next;

        temp->next = malloc(sizeof(item));
        temp->next->key = key;
        temp->next->next = NULL;
    }
}

int search(int key, item * H[]) {

        int keyHashed = h(key);

        if (H[keyHashed] == NULL)
            return -1;

        else if (H[keyHashed]->key != key) {

            item * temp = H[keyHashed];

            while (temp->key != key && temp->next != NULL)
                temp = temp->next;

            if (temp->key == key) {
                return keyHashed;
            }

            else
                return -1;
        }

        else
            return keyHashed;
}

void printHash(item * H[]) {

    item *temp;
    int i;

    printf("\nTable size: %d\n", TABLE_SIZE);

    for (i = 0; i < TABLE_SIZE; i++) {
        if (H[i] != NULL) {
            printf("i: %d          key: %d",i,H[i]->key);

            temp = H[i]->next;;
            while (temp != NULL) {
                printf(" -> %d", temp->key);
                temp = temp->next;
            }

            printf("\n");
        }

        else
            printf("i: %d          key: none\n",i);
    }

    printf("\n");
}

void test() {

    // a)
    int array[7] = {111,10112,1113,5568,63,1342,21231};

    item *h[TABLE_SIZE];
    init(h);

    int i = 0;
    for (i; i < 7; i++)
        insert(array[i], h);

    // b)
    printHash(h);

    // c)
    printf("Search result for 1: %d\n", search(1, h));
    printf("Search result for 10112: %d\n", search(10112, h));
    printf("Search result for 1113: %d\n", search(1113, h));
    printf("Search result for 5568: %d\n", search(5568, h));
    printf("Search result for 337: %d\n", search(337, h));
}

int main() {
    test();
}

.

hashkey: 7 (111)
hashkey: 0 (10112)
hashkey: 1 (1113)
hashkey: 0 (5568) (duplicate)
hashkey: 7 (63) (duplicate)
hashkey: 6 (1342)
hashkey: 7 (21231) (duplicate)

Table size: 8
i: 0          key: 10112 -> 5568
i: 1          key: 1113
i: 2          key: none
i: 3          key: none
i: 4          key: none
i: 5          key: none
i: 6          key: 1342
i: 7          key: 111 -> 63 -> 21231

Search result for 1: -1
Search result for 10112: 0
Search result for 1113: 1
Search result for 5568: 0
Search result for 337: -1

Process returned 26 (0x1A)   execution time : 0.303 s
Press any key to continue.

最佳答案

您的代码中存在多个问题。很难同时修复它们。基本上你没有正确实现链表。以下是一些主要问题。

在 insert 的冲突情况下，您正在创建两个新节点，在头部之前链接一个虚拟节点，在末尾链接另一个虚拟节点。我不知道如何更好地描述它，但这完全是错误的。它应该更简单，如下所示。它只是创建一个新节点并将其放在碰撞链的前端(如果您想将其放在末尾，则作为练习留给您 - 哈希表不是必需的)。

item * temp = malloc(sizeof(item));
temp->key = key;
temp->next = H[keyHashed];
H[keyHashed] = temp;

为什么要在 printHash 函数中分配内存？这显然是错误的。永远不需要新内存来遍历链表。并且您应该使用 next 而不是 key 来确定您是否已到达链表的末尾。事实上，您永远不会在 while 循环中更新 next，因此根本不会遍历列表。这是它应该是什么样子的示例。

void printHash(item * H[]) 
{
    item *temp;
    int i;

    printf("\nTable size: %d\n", TABLE_SIZE);  
    for (i = 0; i < TABLE_SIZE; i++) {
        if (H[i] != NULL) {
            printf("i: %d          key: %d\n",i,H[i]->key);

            temp = H[i]->next;;
            while (temp != NULL) {
                printf(" -> %d\n", temp->key);
                temp = temp->next;
            }
        } else {
            printf("i: %d          key: none\n",i);
        }
    }
}

还有其他问题(特别是在 search 中，这会使您的程序崩溃)。但我认为这足以让你现在咀嚼。

我的建议:回去修改链表的基本实现。在您回来在哈希表中使用它之前，请充分理解并发挥作用。

关于c - 尝试将项目添加到链接列表的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29884563/

上一篇：c - 不确定我的贪吃蛇游戏逻辑有什么问题？

下一篇：链式哈希表没有给出正确的输出

相关文章：

C#include pbl.h路径

c - 无法反转链表 - C 语言

c# - 输入字符串的格式不正确，List<String> 到 Dictionary<int, int>

使用多线程的无序映射的 C++ 填充

c - 如何在 C 中一次原子地读取多个变量？

c - 取消引用的 union 成员字节不相同

命令行参数和字符

c - 链接栈和队列

使用append复制C中的链表

javascript - 如何在 JavaScript 中实现哈希表

©2024 IT工具网  联系我们