如何为散列 table int C 分配内存？

Question

我是 C 的新手，对内存分配很困惑。我正在尝试创建一个散列 table 但不知道如何处理内存，尤其是对于作为字符串数组的键参数。

我正在尝试将代码设置为扫描文本文件中的单词并打印它们的频率。我已经阅读了一下，发现我可能需要使用 realloc 函数，但我不完全确定。

感谢任何帮助，谢谢！

struct htablerec {
int capacity;
int num_keys;
int *frequencies;
char **keys;
};

htable htable_new(int capacity2){
  int i;
  htable result = malloc(sizeof *result);
  result->capacity = capacity2;
  result->num_keys = 0;

  result->frequencies = malloc(result->capacity * sizeof
            result->frequencies[0]);

  result->keys = malloc(result->capacity * sizeof(char *));

  for(i=0;i<result->capacity;i++){
    result->frequencies[i] = 0;
    result->keys[i] = malloc(1); 
    result->keys[i][0] = 0; 
  }
  return result;
}

int htable_insert(htable h, char *str){
  int i;
  int number = htable_word_to_int(str) % h->capacity;

  for(i=0; i<h->capacity; i++){

    if(number == h->capacity){
      number = 0;
    }

    if(strlen(h->keys[number]) == 0){
      h->keys[number] = str;
      h->frequencies[number]++;

      h->num_keys++;
      return h->frequencies[number];

    }
    if(h->keys[number] == str){
      h->frequencies[number]++;
      return h->frequencies[number];
    }
    number++;
  }
  return 0;
}

Answer 1

您有几个问题，但主要问题是处理 str，首先，如果您使用空字符串初始化键 - 您需要在分配给它们时释放它们，其次 - 当您比较单元格时，不要使用 ==，因为它会检查指针是否相同，使用类似 strcmp 的东西，最后 - 当你分配时，取决于你的程序实现 - 你可能需要使用类似 strdup 的东西来复制 str，否则你指向与您获得的指针相同的 space。例如：

int htable_insert(htable h, char *str){
int i;
int number = htable_word_to_int(str) % h->capacity;

for(i=0; i<h->capacity; i++){

if(number == h->capacity){
  number = 0;
}

if(strlen(h->keys[number]) == 0){
  free(h->keys[number]);
  h->keys[number] = strdup(str);
  h->frequencies[number]++;

  h->num_keys++;
  return h->frequencies[number];

}
if(!strcmp(h->keys[number], str)){
  h->frequencies[number]++;
  return h->frequencies[number];
}
number++;
}
return 0;
}

这并不完美，它不处理内存分配失败或参数中的空指针，更好的方法是将键初始化为 NULL 值 - 但它说明了主要问题

此外 - 不清楚大小是否需要保持不变，如果不需要，您需要逻辑来扩展散列 table 当它已满（检测条件，重新分配频率和键，根据新容量重新分配密钥和频率，处理重新分配失败等）

Answer 2

如果容量是 const，那么你不需要重新分配（你可以 return -1 来表示这个 str 没有位置）。

在其他地方，您可以在htable_insert中的for之后添加（如果我们到达那里，则意味着keys数组已满，因此我们需要调整它的大小）。

for(..){
...
}
h->capacity *= 2;
h->keys = realloc(h->keys, h->capacity); // copy the data into a new array, two time size than 
                               //the old one
return htable_insert(h,str);

注意，您还必须调整频率数组的大小。

如何为散列 table int C 分配内存？

How do I allocate memory for a hash table int C?

c

memory-management

hashtable