c - 地址未被堆叠、分配或(最近)释放

Question

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

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

但是，我一直遇到段错误，我使用 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;
}

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 table[TABLE_SIZE] = { 0 };

然后您不需要为条目本身分配内存，只需为内容分配内存。

在你的初始化循环中

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]，也是null。而en并没有改变，它仍然指向前面malloc的结果。然后将 table[1] 设置为 en，这与您之前的值相同。因此，完成后，表的每个元素都设置为相同的值，并且 en->next 为 NULL。

我没有通过散列函数进行追踪，但我没有立即看到 任何将散列值的使用限制为表的可能索引的东西。当我测试它时，“kkj\0”(顺便说一句，C 中的字符串文字已经以 null 终止，因此不需要\0。)的哈希值为 29，超出了有效值 表的索引。所以你正在访问表限制之外的内存 大批。到那时，所有的赌注都落空了，几乎任何事情都有可能发生。 A 在这种情况下，段错误实际上是一个很好的结果，因为它立即 显然出了什么问题。您需要对表取哈希值模 修复数组边界问题的大小，即 h % TABLE_SIZE。