哈希 table 的密钥由于上次输入而混乱
Hash table's key is messing up due to last input
我正在尝试创建一个散列 table 程序,它可以输入散列键和将存储在散列 table 中的字符串数据。一切都很好,除了 "Menu == 2",每次我尝试通过输入它的散列键来搜索字符串数据时,table 中的一个(最后定位的)散列键被更改为我在 "Menu == 2".
这是来自 "Menu == 4" 的散列 table 和 viewAll ()
函数(在我通过 "Menu == 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;
}
有什么办法可以解决这个问题吗?提前抱歉,我的代码草率且难读。
发生这种情况是因为每次调用 push 时都会分配新内存并将指向该内存的指针存储在 node:
node = (struct data*) malloc(sizeof(struct data));
之后,这个分配的数据被插入到table,但是节点仍然指向那个数据。然后当你 运行 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 将被调用。
我正在尝试创建一个散列 table 程序,它可以输入散列键和将存储在散列 table 中的字符串数据。一切都很好,除了 "Menu == 2",每次我尝试通过输入它的散列键来搜索字符串数据时,table 中的一个(最后定位的)散列键被更改为我在 "Menu == 2".
这是来自 "Menu == 4" 的散列 table 和 viewAll ()
函数(在我通过 "Menu == 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;
}
有什么办法可以解决这个问题吗?提前抱歉,我的代码草率且难读。
发生这种情况是因为每次调用 push 时都会分配新内存并将指向该内存的指针存储在 node:
node = (struct data*) malloc(sizeof(struct data));
之后,这个分配的数据被插入到table,但是节点仍然指向那个数据。然后当你 运行 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 将被调用。