地址未被堆叠、分配或（最近）释放

Question

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

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

但是，我一直遇到分段错误，我使用 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[=10=]", 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 转换 return 值，这样做可以掩盖其他错误。

下面几行永远不会释放的 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));

没有按照评论所说的去做。它只为一个结构条目分配足够的内存。也许你打算把它放在循环中。

对于固定的 table 大小，您也可以只拥有一个 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 都设置为其自身，并且所有 table 元素都设置为相同的值。第一次通过循环时，en->next 被设置为 table[0]，由于您的静态初始值设定项，此时它为 NULL。 table[0] 然后设置为 en.

第二次循环，en->next被设置为table[1]，也是null。而en并没有改变，它仍然指向前面malloc的结果。 table[1] 然后设置为 en，这与您之前的值相同。因此，完成后，table 的每个元素都设置为相同的值，并且 en->next 为 NULL。

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

地址未被堆叠、分配或（最近）释放

Address is not stack'd, malloc'd or (recently) free'd

c

malloc

hashtable