我正在尝试使用链表实现哈希表，但有一件事无法正常工作。 首先，我编写了链表代码，并确保它按照预期工作，所以我发现它必须与哈希表实现或它们之间的交互有关。
发生的情况是我可以添加多个对象并再次找到它们，没有问题。但是，如果两个或多个对象使用相同的 key 进行哈希处理，它们应该创建一个链接列表，但由于某种原因我只能在链接列表中找到最新添加的对象。
之前添加的对象在那里，因为我可以成功删除使用“lookup_string”函数找不到的对象，因此我知道该对象存储在该位置。
所以函数“lookup_string”应该传递我在哈希表中搜索的对象，而“Search”函数是我在仅实现链表时使用的函数。值得一提的是，“搜索”功能用于删除过程，但不在我只想查找对象的过程中使用，我不确定这是否重要，因为我相信“lookup_string”应该能够找到没有“搜索”功能的对象。
为了简单起见，我存储了两个对象:
对象 1:
name(key) = bcd
telephone number = 123
对象2:
name(key) = ace
telephone number = 910
现在对象 1 和 2 将获得相同的哈希键值，因此它们将存储在哈希表中的同一槽中。他们应该创建一个链接列表，但是当我搜索对象(菜单中的选择号 3)时，我只能找到最新添加的对象，即对象 2。 但我仍然可以删除对象1，它会告诉我对象1已成功删除。
代码:
struct post
{
char name[30];
int tel;
struct post *next;
};
typedef struct post Post;
Post *head = NULL;
Post *current;
struct hash_table
{
Post **table;
int size;
};
typedef struct hash_table Post_table;
unsigned int Hash(Post_table *hash_table, char tempname[30])
{
int i;
int sum;
int key;
for(i = 0; i < strlen(tempname); i++)
{
sum += (int)tempname[i];
}
key = sum % hash_table->size;
return key;
}
Post_table *create_hash_table(int size)
{
int i;
Post_table *new_table;
if (size < 1)
{
return NULL;
}
//attempt to allocate memory for the table structure
if ((new_table = malloc(sizeof(Post_table))) == NULL)
{
return NULL;
}
//attempt to allocate memory for the table itself
if ((new_table->table = malloc(sizeof(Post *) * size)) == NULL)
{
return NULL;
}
//Initialize the elements of the table
for(i = 0; i < size; i++)
{
new_table->table[i] = NULL;
new_table->size = size;
}
return new_table;
}
Post *lookup_string(Post_table *hash_table, char tempname[30])
{
Post *list;
unsigned int hashkey = Hash(hash_table, tempname);
for(list = hash_table->table[hashkey]; list != NULL; list = list->next)
{
if (strcmp(tempname, list->name) == 0)
{
return list;
}
}
return NULL;
}
int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
Post *new_list;
Post *current_list;
unsigned int hashkey = Hash(hash_table, tempname);
/* Attempt to allocate memory for list */
if ((new_list = malloc(sizeof(Post))) == NULL)
{
return 1;
}
/* Does item already exist? */
current_list = lookup_string(hash_table, tempname);
/* item already exists, don't insert it again. */
if (current_list != NULL)
{
return 2;
}
/* Insert into list */
printf("\nHash-key: %d\n", hashkey);
hash_table->table[hashkey] = AddList(tempname, temptel);
return 0;
}
Post* CreateList(char tempname[30], int temptel)
{
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
printf("\n creating list with headnode as [%s]\n",tempname);
head = current = ptr;
return ptr;
}
Post* AddList(char tempname[30], int temptel)
{
if (NULL == head)
{
return (CreateList(tempname, temptel));
}
printf("\n Adding node to end of list with value [%s]\n",tempname);
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
current->next = ptr;
current = ptr;
return ptr;
}
void skrivMeny(void)
{
printf("\n1: Register name and telephone number\n");
printf("2: Remove name and telephone number\n");
printf("3: Search for name\n");
printf("5: Exit\n");
}
Post* Search(char tempname[30], Post **prev)
{
Post *ptr = head;
Post *tmp = NULL;
int found = 0;
char structname[sizeof(tempname)];
printf("\n Searching the list for value [%s] \n",tempname);
while(ptr != NULL)
{
if (strcmp(ptr->name, tempname) == 0)
{
found = 1;
break;
}
else
{
tmp = ptr;
ptr = ptr->next;
}
}
if(found == 1)
{
if(prev)
{
*prev = tmp;
}
return ptr;
}
else
{
return NULL;
}
}
void free_entry(Post_table *hash_table, char tempname[30])
{
Post *del_list;
Post *temp;
int ret = 0;
unsigned int hashkey = Hash(hash_table, tempname);
del_list = lookup_string(hash_table, tempname);
ret = Delete(tempname);
if(ret != 0)
{
printf("\n delete [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n delete [name = %s] passed \n",tempname);
}
}
int Delete(char tempname[30])
{
Post *prev = NULL;
Post *del = NULL;
printf("\n Deleting value [%s] from list\n",tempname);
del = Search(tempname,&prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
{
prev->next = del->next;
}
if(del == current && del != head)
{
current = prev;
}
else if(del == head)
{
head = del->next;
}
}
free(del);
del = NULL;
return 0;
}
int main()
{
printf("\nHej och välkommen till hashlistan\n\n");
int menyval = 1;
char tempname[30];
int temptel;
int key;
Post * ptr;
Post_table *hash_table;
int table_size = 10;
hash_table = create_hash_table(table_size);
while (menyval > 0 && menyval <= 5)
{
skrivMeny();
scanf("%d", &menyval);
if (menyval == 1)
{
printf("[Name] [Number] = ");
scanf("%s %d", &tempname[0], &temptel);//inmatning
add_string(hash_table, tempname, temptel);
}
if (menyval == 2)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
free_entry(hash_table, tempname);
}
if (menyval == 3)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
ptr = lookup_string(hash_table, tempname);
if(ptr == NULL)
{
printf("\n Search [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n Search passed [name = %s tel = %d]\n",ptr->name, ptr->tel);
}
}
if (menyval == 5)
{
break;
}
}
return 0;
}
感谢所有帮助或提示解决我的问题!
编辑: 这就是我的代码现在的样子，我将文件分为两个文件； hash.c 和 lista.h，其中我将头文件包含在 c 文件中。
lista.h:
struct post
{
char name[30];
int tel;
struct post *next;
};
typedef struct post Post;
struct list
{
Post *head = NULL;
Post *current;
};
typedef struct list List;
Post* CreateList(char tempname[30], int temptel)
{
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
printf("\n creating list with headnode as [%s]\n",tempname);
return ptr;
}
Post* AddList(char tempname[30], int temptel, int emptyElement)
{
if (emptyElement == 1)
{
return (CreateList(tempname, temptel));
}
printf("\n Adding node to end of list with value [%s]\n",tempname);
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
return ptr;
}
int Delete(Post_table *hash_table, char tempname[30])
{
Post *prev = NULL;
Post *del = NULL;
printf("\n Deleting value [%s] from list\n",tempname);
del = Search(tempname,&prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
{
prev->next = del->next;
}
if(del == hash_table->table[hashkey].current && del != hash_table->table[hashkey].head)
{
hash_table->table[hashkey].current = prev;
}
else if(del == hash_table->table[hashkey].head)
{
hash_table->table[hashkey].head = del->next;
}
}
free(del);
del = NULL;
return 0;
}
哈希.c:
struct hash_table
{
List *table;
int size;
};
typedef struct hash_table Post_table;
unsigned int Hash(Post_table *hash_table, char tempname[30])
{
int i;
int sum;
int key;
for(i = 0; i < strlen(tempname); i++)
{
sum += (int)tempname[i];
}
key = sum % hash_table->size;
return key;
}
Post_table *create_hash_table(int size)
{
int i;
Post_table *new_table;
if (size < 1)
{
return NULL;
}
//attempt to allocate memory for the table structure
if ((new_table = malloc(sizeof(Post_table))) == NULL)
{
return NULL;
}
//attempt to allocate memory for the table itself
if ((new_table->table = malloc(sizeof(Post *) * size)) == NULL)
{
return NULL;
}
//Initialize the elements of the table
for(i = 0; i < size; i++)
{
new_table->table[i] = NULL;
new_table->size = size;
}
return new_table;
}
Post *lookup_string(Post_table *hash_table, char tempname[30])
{
Post *list;
unsigned int hashkey = Hash(hash_table, tempname);
for(list = hash_table->table[hashkey]; list != NULL; list = list->next)
{
if (strcmp(tempname, list->name) == 0)
{
return list;
}
}
return NULL;
}
int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
int emptyElement = 0;
Post *new_list;
Post *current_list;
unsigned int hashkey = Hash(hash_table, tempname);
/* Attempt to allocate memory for list */
if ((new_list = malloc(sizeof(Post))) == NULL)
{
return 1;
}
/* Does item already exist? */
current_list = lookup_string(hash_table, tempname);
/* item already exists, don't insert it again. */
if (current_list != NULL)
{
return 2;
}
/* Insert into list */
if (hash_table->table[hashkey] == NULL)
{
emptyElement = 1;
}
printf("\nHash-key: %d\n", hashkey);
hash_table->table[hashkey] = AddList(tempname, temptel);
if (emptyElement == 1)
{
hash_table->table[hashkey].head = hash_table->table[hashkey];
hash_table->table[hashkey].current = hash_table->table[hashkey];
}
if (emptyElement == 0)
{
hash_table->table[hashkey].current = hash_table->table[hashkey];
}
return 0;
}
void free_entry(Post_table *hash_table, char tempname[30])
{
Post *del_list;
Post *temp;
int ret = 0;
unsigned int hashkey = Hash(hash_table, tempname);
del_list = lookup_string(hash_table, tempname);
ret = Delete(tempname);
if(ret != 0)
{
printf("\n delete [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n delete [name = %s] passed \n",tempname);
}
}
void skrivMeny(void)
{
printf("\n1: Register name and telephone number\n");
printf("2: Remove name and telephone number\n");
printf("3: Search for name\n");
printf("5: Exit\n");
}
Post* Search(char tempname[30], Post **prev)
{
Post *ptr = head;
Post *tmp = NULL;
int found = 0;
char structname[sizeof(tempname)];
printf("\n Searching the list for value [%s] \n",tempname);
while(ptr != NULL)
{
if (strcmp(ptr->name, tempname) == 0)
{
found = 1;
break;
}
else
{
tmp = ptr;
ptr = ptr->next;
}
}
if(found == 1)
{
if(prev)
{
*prev = tmp;
}
return ptr;
}
else
{
return NULL;
}
}
int main()
{
printf("\nHej och välkommen till hashlistan\n\n");
int menyval = 1;
char tempname[30];
int temptel;
int key;
Post * ptr;
Post_table *hash_table;
int table_size = 10;
hash_table = create_hash_table(table_size);
while (menyval > 0 && menyval <= 5)
{
skrivMeny();
scanf("%d", &menyval);
if (menyval == 1)
{
printf("[Name] [Number] = ");
scanf("%s %d", &tempname[0], &temptel);//inmatning
add_string(hash_table, tempname, temptel);
}
if (menyval == 2)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
free_entry(hash_table, tempname);
}
if (menyval == 3)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
ptr = lookup_string(hash_table, tempname);
if(ptr == NULL)
{
printf("\n Search [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n Search passed [name = %s tel = %d]\n",ptr->name, ptr->tel);
}
}
if (menyval == 5)
{
break;
}
}
return 0;
}
但是正如我所说，这部分似乎有问题:
struct list
{
Post *head = NULL;
Post *current;
};
由于这是不正确的，它会导致其他几个错误，因此我首先尝试看看这部分有什么问题。
最佳答案
好的，这里是对您的代码的一些改进:我已经用我的标签“Leo”标记了它们
在list.c中:
struct post // structure of node
{
char name[30]; // stored data
int tel; // stored data
struct post *next; // reference to next node
};
typedef struct post Post; // Post = struct post
struct list
{
Post *head;
Post *current;
};
typedef struct list List;
struct hash_table
{
List *table;
int size;
};
typedef struct hash_table Post_table;
Post* CreateList(char tempname[30], int temptel);
Post* AddList(char tempname[30], int temptel, int emptyElement, Post *current);
void skrivMeny(void);
void PrintList(void);
int Delete(Post_table *hash_table, char tempname[30], unsigned int hashkey);
Post* Search(Post_table *hash_table, unsigned int hashkey, char tempname[30], Post **prev);
Post* CreateList(char tempname[30], int temptel)
{
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
printf("\n creating list with headnode as [%s]\n",tempname);
return ptr;
}
// Leo: emptyElement isn't neccessary, we use current==null
Post* AddList(char tempname[30], int temptel, Post *current)
{
if( current == null )
{
return (CreateList(tempname, temptel));
}
printf("\n Adding node to end of list with value [%s]\n",tempname);
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
// Leo: we must append the new element to current
current->next = ptr;
return ptr;
}
在 hash.c 中
unsigned int Hash(Post_table *hash_table, char tempname[30])
{
int i;
int sum;
int key;
for(i = 0; i < strlen(tempname); i++)
{
sum += (int)tempname[i];
}
key = sum % hash_table->size;
return key;
}
Post_table *create_hash_table(int size)
{
int i;
Post_table *new_table;
if (size < 1)
{
return NULL;
}
//attempt to allocate memory for the table structure
if ((new_table = malloc(sizeof(Post_table))) == NULL)
{
return NULL;
}
//attempt to allocate memory for the table itself
// Leo: replaced malloc() by calloc() so all head and current are initialized with NULL
if ((new_table->table = calloc(size, sizeof(List *) )) == NULL)
{
return NULL;
}
//Initialize the elements of the table
/* Leo: What's that loop for ?
for(i = 0; i < size; i++)
{
new_table->table[i]; // Leo: that line doen't do anything
new_table->size = size; // Leo: once is enough, let's have it otside the loop
}
*/
new_table->size = size; // Leo: once is enough, let's have it otside the loop
return new_table;
}
Post *lookup_string(Post_table *hash_table, char tempname[30])
{
Post *list;
unsigned int hashkey = Hash(hash_table, tempname);
/* Go to the correct list based on the hash value and see if str is
* in the list. If it is, return return a pointer to the list element.
* If it isn't, the item isn't in the table, so return NULL.
*/
// Leo: we must start with head instead of current
for(list = hash_table->table[hashkey].head; list != NULL; list = list->next)
{
if (strcmp(tempname, list->name) == 0)
{
return list;
}
}
return NULL;
}
int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
//Leo: emptyElement is not used any more (see AddList()
//int emptyElement = 0;
//Leo: new_list is never used
//Post *new_list;
Post *current_list;
unsigned int hashkey = Hash(hash_table, tempname);
/* Attempt to allocate memory for list */
/* Leo: new_list is never used
if ((new_list = malloc(sizeof(Post))) == NULL)
{
return 1;
}
*/
/* Does item already exist? */
current_list = lookup_string(hash_table, tempname);
/* item already exists, don't insert it again. */
if (current_list != NULL)
{
return 2;
}
/* Insert into list */
/* Leo: emptyElement isn't used any more
if (hash_table->table[hashkey].head == NULL)
{
emptyElement = 1;
}
*/
printf("\nHash-key: %d\n", hashkey);
//This line of code under used to store my element in the hash-table but gives now an error
// hash_table->table[hashkey] = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);
/* Leo: in case of emptyElement == 1 you have called AddList() twice and so created two new list elemens, we replace all of this by the code below
if (emptyElement == 1)
{
hash_table->table[hashkey].head = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);
hash_table->table[hashkey].current = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);
}
if (emptyElement == 0)
{
hash_table->table[hashkey].current = AddList(tempname, temptel, emptyElement, hash_table->table[hashkey].current);
}
*/
// Leo: Note: if the list for hashKey has not been created yet then both head and current are NULL, otherwise both are != NULL
hash_table->table[hashkey].current = AddList(tempname, temptel, hash_table->table[hashkey].current);
// Leo: if the list has been created just now, then both head and current must point to the only list element
if( hash_table->table[hashkey].head == NULL )
hash_table->table[hashkey].head = hash_table->table[hashkey].current;
return 0;
}
void free_entry(Post_table *hash_table, char tempname[30])
{
Post *del_list;
Post *temp;
int ret = 0;
unsigned int hashkey = Hash(hash_table, tempname);
del_list = lookup_string(hash_table, tempname);
ret = Delete(hash_table, tempname, hashkey);
if(ret != 0)
{
printf("\n delete [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n delete [name = %s] passed \n",tempname);
}
}
void skrivMeny(void)
{
printf("\n1: Register name and telephone number\n");
printf("2: Remove name and telephone number\n");
printf("3: Search for name\n");
printf("5: Exit\n");
}
Post* Search(Post_table *hash_table, unsigned int hashkey, char tempname[30], Post **prev)
{
Post *ptr = hash_table->table[hashkey].head;
Post *tmp = NULL;
int found = 0;
char structname[sizeof(tempname)];
printf("\n Searching the list for value [%s] \n",tempname);
while(ptr != NULL)
{
if (strcmp(ptr->name, tempname) == 0)
{
found = 1;
break;
}
else
{
tmp = ptr;
ptr = ptr->next;
}
}
if(found == 1)
{
if(prev)
{
*prev = tmp;
}
return ptr;
}
else
{
return NULL;
}
}
int main()
{
printf("\nHej och välkommen till hashlistan\n\n");
int menyval = 1;
char tempname[30];
int temptel;
int key;
Post * ptr;
Post_table *hash_table;
int table_size = 10;
hash_table = create_hash_table(table_size);
while (menyval > 0 && menyval <= 5)
{
skrivMeny();
scanf("%d", &menyval);
if (menyval == 1)
{
printf("[Name] [Number] = ");
scanf("%s %d", &tempname[0], &temptel);//inmatning
add_string(hash_table, tempname, temptel);
}
if (menyval == 2)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
free_entry(hash_table, tempname);
}
if (menyval == 3)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
ptr = lookup_string(hash_table, tempname);
if(ptr == NULL)
{
printf("\n Search [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n Search passed [name = %s tel = %d]\n",ptr->name, ptr->tel);
}
}
if (menyval == 5)
{
break;
}
}
return 0;
}
int Delete(Post_table *hash_table, char tempname[30], unsigned int hashkey)
{
Post *prev = NULL;
Post *del = NULL;
printf("\n Deleting value [%s] from list\n",tempname);
del = Search(hash_table, hashkey, tempname, &prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
{
prev->next = del->next;
}
if(del == hash_table->table[hashkey].current && del != hash_table->table[hashkey].head)
{
hash_table->table[hashkey].current = prev;
}
else if(del == hash_table->table[hashkey].head)
{
hash_table->table[hashkey].head = del->next;
}
}
free(del);
del = NULL;
return 0;
}
我还没有编译它，所以现在可能有一些语法错误，但我希望它清楚整个事情应该如何工作。如果您还有其他问题，请随时提问。
关于c - 带有 bug 的链表的哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17805842/