我是C新手,所以我在制作哈希表和malloc空间时遇到了困难。
我在做一个字谜解算器。现在我还在为这个程序创建哈希表的步骤中。我试着用一些随机参数调用一次insert函数来测试它是否正常工作。
然而,我不断地得到分割错误,我使用valgrind来追踪它崩溃的地方。
你能指出我遗漏了什么吗?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int hash(char *word)
{
int h = 0;
int i, j;
char *A;
char *a;
// an array of 26 slots for 26 uppercase letters in the alphabet
A = (char *)malloc(26 * sizeof(char));
// an array of 26 slots for 26 lowercase letters in the alphabet
a = (char *)malloc(26 * sizeof(char));
for (i = 0; i < 26; i++) {
A[i] = (char)(i + 65); // fill the array from A to Z
a[i] = (char)(i + 97); // fill the array from a to z
}
for (i = 0; i < strlen(word); i++) {
for (j = 0; j < 26; j++) {
// upper and lower case have the same hash value
if (word[i] == A[j] || word[i] == a[j]) {
h += j; // get the hash value of the word
break;
}
}
}
return h;
}
typedef struct Entry {
char *word;
int len;
struct Entry *next;
} Entry;
#define TABLE_SIZE 20 // test number
Entry *table[TABLE_SIZE] = { NULL };
void init() {
// create memory spaces for each element
struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));
int i;
// initialize
for (i = 0; i < TABLE_SIZE; i++) {
en->word = "";
en->len = 0;
en->next = table[i];
table[i] = en;
}
}
void insertElement(char *word, int len) {
int h = hash(word);
int i = 0;
// check if value has already existed
while(i < TABLE_SIZE && (strcmp(table[h]->word, "") != 0)) {
// !!!! NEXT LINE IS WHERE IT CRASHES !!!
if (strcmp(table[h]->word, word) == 0) { // found
table[h]->len = len;
return; // exit function and skip the rest
}
i++; // increment loop index
}
// found empty element
if (strcmp(table[h]->word, "") == 0) {
struct Entry *en;
en->word = word;
en->len = len;
en->next = table[h];
table[h] = en;
}
}
int main() {
init(); // initialize hash table
// test call
insertElement("kkj\0", 2);
int i;
for ( i=0; i < 10; i++)
{
printf("%d: ", i);
struct Entry *enTemp = table[i];
while (enTemp->next != NULL)
{
printf("Word: %s, Len:%d)", enTemp->word, enTemp->len);
enTemp = enTemp->next;
}
printf("\n");
}
return 0;
}
最佳答案
不需要从malloc强制转换返回值,这样做可以屏蔽其他错误。
下面几行是malloc memory,它永远不会被释放,所以散列函数中存在内存泄漏。
// an array of 26 slots for 26 uppercase letters in the alphabet
A = (char *)malloc(26 * sizeof(char));
// an array of 26 slots for 26 lowercase letters in the alphabet
a = (char *)malloc(26 * sizeof(char));
根据定义,sizeof(char)保证为1,因此不必乘以sizeof(char)。
您的代码还采用字符的ascii布局,这是不保证的。
在init()函数中,有
// create memory spaces for each element
struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));
不照评论说的做。它只为一个结构项分配足够的内存。也许你是想把这个放进循环中。
对于固定的表大小,也可以只使用一个struct Entry数组
直接的而不是指向这样的指针数组。即。
struct Entry table[TABLE_SIZE] = { 0 };
然后就不需要对条目本身使用malloc内存,只需要内容。
在初始化循环中
for (i = 0; i < TABLE_SIZE; i++) {
en->word = "";
en->len = 0;
en->next = table[i];
table[i] = en;
}
每个en->next都被设置为自身,所有表元素都被设置为相同的值。第一次通过循环时,en->next被设置为表[0],此时由于静态初始值设定项的缘故,该表为空。然后将表[0]设置为en。
第二次通过循环时,en->next被设置为表[1],该表也是空的。而且en没有改变,它仍然指向早期malloc的结果。然后将表[1]设置为en,这与以前的值相同。所以,完成后,表中的每个元素都被设置为相同的值,en->next为空。
我没有通过hash函数进行跟踪,但是我没有立即看到
任何将哈希值的使用限制为表的可能索引的操作。当我测试它时,“kkj\0”(顺便说一句,C中的字符串文本已经以空结尾,所以不需要使用\0)的哈希值是29,它超出了有效的
表的索引。所以你访问的内存超出了表的限制
阵列。在那一点上,所有的赌注都结束了,几乎任何事情都有可能发生。一个
在这种情况下seg fault实际上是一个很好的结果,因为它是立即
显然出了什么问题。您需要将哈希值取为表的模
用于修复数组边界问题的大小,即h%表大小。
关于c - 地址未堆叠,未分配或(最近)未释放,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/31364441/