我是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/

10-11 22:09
查看更多