c语言 - 地址不是堆叠的、恶意的或(最近)释放的

Question

我是C语言的新手，所以我在制作哈希表和malloking空间时遇到了麻烦。

我正在做一个字谜解算器。现在我还在为这个程序创建哈希表的步骤。我正试图测试我的插入函数，看看它是否正常工作，通过调用函数一次与一些随机参数。

然而，我一直得到分段错误，我使用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", 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;
}

Answer 1

没有必要强制转换malloc的返回值，这样做可以掩盖其他错误。

下面几行malloc内存永远不会被释放，因此在您的哈希函数中存在内存泄漏。

// 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数组直接而不是指向这样的指针数组。例如

struct Entry table[TABLE_SIZE] = { 0 };

然后你不需要为条目本身malloc内存，只需要为内容malloc内存。

初始化循环

for (i = 0; i < TABLE_SIZE; i++) {
    en->word = "";
    en->len = 0;
    en->next = table[i];
    table[i] = en;
}

每个en->next被设置为自身，并且所有表元素都被设置为相同的值。第一次通过循环时，en->next被设置为table[0]，由于静态初始化器的作用，此时该表为NULL。然后将Table[0]设置为en。

第二次通过循环时，en->next被设置为table[1]，它也是空的。en没有改变，它仍然指向先前malloc的结果。然后将表[1]设置为en，这与之前的值相同。因此，当您完成后，表中的每个元素都被设置为相同的值，并且en->下一步是NULL。

我没有跟踪哈希函数，但我没有立即看到任何限制使用哈希值的表的可能索引。当我对它进行测试时，"kkj"(顺便说一句，C中的字符串字面量已经以空结束，因此不需要)的哈希值为29，超出了有效范围表的索引。所以你访问的内存超出了表的限制数组中。在这一点上，所有的赌注都被取消了，几乎任何事情都可能发生。一个在这种情况下，segfault实际上是一个好结果，因为它立即很明显有问题。你需要将哈希值对表取模size来修复数组边界问题，即h % TABLE_SIZE.