哈希表的键由于上次输入而混乱

Question

我正在尝试创建一个哈希表程序，该程序可以输入哈希键和将存储在哈希表中的字符串数据。除了在“ Menu == 2”中，一切都很好，每次我尝试通过输入其哈希键来搜索字符串数据时，表中的一个（最后定位的）哈希键都会更改为我在“ Menu == 2”中输入的内容“。

这是带有viewAll ()功能的“菜单== 4”中的哈希表（在我输入哈希键和通过“菜单== 1”中的字符串数据之后：]

//FORMAT:
//[index]: [key] (string data) -> [key] (string data) -> ..

--------------------------------------------------------------------------------

//after I finished inputting all hash keys and string datas through menu 1  

[0]: 0 (INDIA) -> 97 (PAKISTAN) -> 194 (BURMA) -> 291 (AFGHANISTAN)
[1]: 1 (UNITED STATES) -> 98 (CANADA) -> 195 (MEXICO) -> 292 (PANAMA)
[2]: 2 (THE NETHERLANDS) -> 99 (LUXEMBOURG) -> 196 (BELGIUM) -> 293 (FRANCE)
[3]: 3 (SYRIA) -> 100 (LEBANON) -> 197 (ISRAEL) -> 294 (BAHRAIN)

//this hash table is correct

--------------------------------------------------------------------------------

after menu 2 (last key inputted on menu 2 was 0)

[0]: 0 (INDIA) -> 97 (PAKISTAN) -> 194 (BURMA) -> 291 (AFGHANISTAN)
[1]: 1 (UNITED STATES) -> 98 (CANADA) -> 195 (MEXICO) -> 292 (PANAMA)
[2]: 2 (THE NETHERLANDS) -> 99 (LUXEMBOURG) -> 196 (BELGIUM) -> 293 (FRANCE)
[3]: 3 (SYRIA) -> 100 (LEBANON) -> 197 (ISRAEL) -> 0 (BAHRAIN)

//(why is BAHRAIN key 0, it should be 294)

--------------------------------------------------------------------------------

after menu 2 (last key inputted on menu 2 was 99)

[0]: 0 (INDIA) -> 97 (PAKISTAN) -> 194 (BURMA) -> 291 (AFGHANISTAN)
[1]: 1 (UNITED STATES) -> 98 (CANADA) -> 195 (MEXICO) -> 292 (PANAMA)
[2]: 2 (THE NETHERLANDS) -> 99 (LUXEMBOURG) -> 196 (BELGIUM) -> 293 (FRANCE)
[3]: 3 (SYRIA) -> 100 (LEBANON) -> 197 (ISRAEL) -> 99 (BAHRAIN)

//(why is BAHRAIN key 99, it should be 294)

如您所见，它始终是输入菜单2所要更改的最后一个位置。

下面是源代码，为了不浪费您的时间，我来看一下void viewStrData ()函数。

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

struct data {
    int key;
    char strData [100];
    struct data *next;
}*head [97], *tail [97], *node, *curr;

//index location within hash table = key % 97
int hashing (int key) {
    int result = key % 97;
    return result;
}

//input key and strData, push it to hash table
void push (int key, char strData [100]) {
    node = (struct data*) malloc(sizeof(struct data));
    node->key = key;
    strcpy (node->strData, strData);
    node->next = NULL;
    int idx = hashing (key);
    if (!head [idx]) {
        head [idx] = tail [idx] = node;
    } else {
        tail [idx]->next = node;
        tail [idx] = node;
    }
}

//see strData based on key 
void viewStrData (int key) {
    curr = head [hashing (key)];
    node->key = key;
    while (true) {
        if (curr->key == node->key) {
            printf ("[%s]\n", curr->strData);
            break;
        } else {
            curr = curr->next;
        }
    }
}

//print out current hash table
void viewAll () {
    for (int i = 0; i < 97; i++) {
        printf ("[%d]: ", i);
        if (!head [i]) {
            printf ("-\n");
        } else {
            curr = head [i];
            while (curr) {
                if (curr == head [i]) {
                    printf ("%d", curr->key);
                    printf (" (%s)", curr->strData);
                } else {
                    printf (" -> %d", curr->key);
                    printf (" (%s)", curr->strData);
                }
                curr = curr->next;
            }
            printf ("\n");
        }
    }
}

int main () {

    int menu, key;
    char strData [100];

    while (true) {
        printf ("=======================================\n");
        printf ("MENU [1-3]: \n");
        printf ("1. INPUT DATA\n");
        printf ("2. SEARCH DATA\n");
        printf ("3. EXIT\n");
        printf ("=======================================\n");

        scanf ("%d", &menu);
        if (menu == 1) {
            printf ("ENTER KEY AND STRING DATA: \n");
            scanf ("%d %[^\n]", &key, strData);
            push (key, strData);
            printf ("HASH TABLE UPDATED!\n");
        } else if (menu == 2) {
            printf ("ENTER KEY TO FIND STRING DATA: \n");
            scanf ("%d", &key);
            printf ("STRING DATA OF KEY [%d] IS: ", key);
            viewStrData (key);
        } else if (menu == 3) {
            printf ("PROGRAM EXITED\n");
            break;
        } else if (menu = 4) {
            viewAll ();
        }
    }

    return 0;
}

有什么办法可以解决这个问题？并预先抱歉，我的代码草率且难以阅读。

Answer 1

发生这种情况是因为每次调用push都会分配新的内存，并将指向该内存的指针存储在node：

中

    node = (struct data*) malloc(sizeof(struct data));

此后，已分配的数据将插入表中，但node仍指向该数据。然后，当您运行viewStrData时，您执行node-> key = key，此时node仍指向您调用push时最后插入的数据。 。这就是为什么每次调用viewStrData时，最后插入的节点的密钥都会更新为接收到的密钥。

我建议像这样直接比较接收到的密钥：

void viewStrData (int key) {
curr = head [hashing (key)];
// node->key = key;   <-- No need for this
while (true) {
    if (curr->key == key) { // <-- compare key directly, instead of storing it into node->key
        printf ("[%s]\n", curr->strData);
        break;
    } else {
        curr = curr->next;
    }
}

P.S。这行上有一个错字：

        } else if (menu = 4) {

应该为==，而不是=。当前，如果menu不是1、2或3，则它将在if语句内向其assign 4赋值，并且4的结果每次都是true。因此，即使您在此处输入7，菜单也会被4覆盖，并且会调用viewAll。