试图在 C 中制作哈夫曼树，但它一直说堆缓冲区溢出

Question

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "huffman.h"

// Structures defined here.
struct hmNode {
  struct hmNode *left;
  char ch;
  freq f;
  bool used;
  struct hmNode *right;
};
typedef struct hmNode hmNode;

struct nodeArr {
  int capacity;
  struct hmNode **arr;
};
typedef struct nodeArr nodeArr;

//-----------------------------------------------------------------------------
// Functions defined here.

hmNode *new_node(char ch, freq f){
  hmNode *p = malloc(sizeof(hmNode));
  *p = (hmNode) {NULL, ch, f, false, NULL};
  return p;
}

nodeArr *make_arr(char *chs, freq  *fs){
  nodeArr *nodeArr = malloc(sizeof(nodeArr));
  int n = strlen(chs);
  nodeArr->capacity = n;
  nodeArr->arr = malloc( sizeof(hmNode*) * (n+1) );
  for(int i=0; i<nodeArr->capacity; i++){
    nodeArr->arr[i] = new_node(chs[i], fs[i]);
  }
  nodeArr->arr[nodeArr->capacity] = new_node('[=10=]', -1);
  return nodeArr;
}

int extract_min_idx(nodeArr *nodeArr){
  int smaller;
  hmNode **arr = nodeArr->arr;
  int idx = 0;
  while(arr[idx]->used) idx++;
  smaller = idx;
  int val = arr[idx]->f;
  while(idx < nodeArr->capacity){
    idx++;
    while(arr[idx]->used) idx++;
    if(arr[idx]->ch != '[=10=]' && arr[idx]->f < val) {
      val = arr[idx]->f;
      smaller = idx;
    }
  }
  arr[smaller]->used = true;
  return smaller;
}

void insert_node(nodeArr *nodeArr){
  int s1 = extract_min_idx(nodeArr);
  int s2 = extract_min_idx(nodeArr);
  hmNode *new = malloc(sizeof(hmNode));
  new->left = nodeArr->arr[s1];
  new->right = nodeArr->arr[s2];
  new->f = new->left->f + new->right->f;
  new->used = false;
  nodeArr->arr[s1] = new;
}

bool is_tree_done(nodeArr *nodeArr){
  int cnt = 0;
  for(int i=0;i<nodeArr->capacity;i++){
    if(!(nodeArr->arr[i]->used)) cnt++;
  }
  if(cnt == 1) return true;
  else return false;
}

//void free_nodeArr(nodeArr *nodeArr){
//  for(int i=0;i<nodeArr->capacity; i++){
//    free(nodeArr->arr[i]);
//    }
//  free(nodeArr->arr[nodeArr->capacity]);
//  free(nodeArr->arr);
//  free(nodeArr);
//}

hmNode *build_tree(char chs[], freq fs[]){
  hmNode *root;
  nodeArr *nodeArr = make_arr(chs, fs);
  while(!(is_tree_done(nodeArr))){
    insert_node(nodeArr);
  }
  for(int i=0;i<nodeArr->capacity;i++){
    if(!(nodeArr->arr[i]->used)) {
      root = nodeArr->arr[i];
      root->used = true;
    }
  }
  return root;
}

int is_leaf(hmNode *hmNode){
  return !(hmNode->left) && !(hmNode->right);
}

void encode(hmNode *root, int idx, char code[]){
  if(root->left){
    code[idx]='0';
    encode(root->left, idx + 1, code);
  }
  if(root->right){
    code[idx]='1';
    encode(root->right, idx + 1, code);
  }
  if(is_leaf(root)){
    printf("%c: ", root->ch);
    printf("%s\n", code);
  }
}

// void free_tree(hmNode *root){
//   if(is_leaf(root))
//   free_tree(root->left);
//   free_tree(root->right);
//   free(root);
// }
//-----------------------------------------------------------------------------
// Tests

void test_new_node(){
  char chs[] = "ab";
  freq fs[] = {1,2};
  hmNode *new = new_node(chs[0], fs[0]);
  assert(new->ch  == 'a');
  assert(new->f == 1);
  free(new);
}

void test_new_arr(){
  char chs[] = "ab";
  freq fs[] = {1,2};
  nodeArr *newArr = make_arr(chs, fs);
  assert(newArr->arr[0]->ch == 'a');
  assert(newArr->arr[0]->f  ==  1);
  assert(newArr->arr[1]->ch == 'b');
  assert(newArr->arr[1]->f  ==  2);
  assert(newArr->arr[2]->ch == '[=10=]');
  assert(newArr->arr[2]->f  ==  -1);
  //free_nodeArr(newArr);
}

//-----------------------------------------------------------------------------
int main(){
  test_new_node();
  test_new_arr();
  printf("Completed\n");

  //hmNode *root = build_tree(chs, fs);
  //free_tree(root);
  // printf("%d\n", root->f);
  // printf("%d\n", root->left->f);
  // printf("%d\n", root->right->f);
  // printf("%d\n", root->right->left->f);
  // printf("%d\n", root->right->right->f);
  // char code[10];
  // encode(root, 0, code);

  return 0;
}

我尝试使用优先级排队算法构建哈夫曼树，并在使用 'clang -std=c11 -Wall -pedantic -g (NAMEOFTHEFILE).c -o (NAMEOFTHEFILE)' 编译它时检查它是否有效。但是，当我用 'clang -std=c11 -Wall -pedantic -g (NAMEOFTHEFILE).c -o (NAMEOFTHEFILE) -fsanitize=undefined -fsanitize=address -fsanitize=leak' 编译它时，它一直说 'heap-buffer-overflow'，我猜 'make_arr' 函数有问题。

谁能告诉我如何处理这个错误？

Answer 1

您的问题在这里：

 nodeArr *nodeArr = malloc(sizeof(nodeArr));

sizeof(nodeArr)是指针的sizeof(8)，不是同名结构的sizeof(16)。这是将变量命名为与类型相同不是一个好主意的众多原因之一。

您应该考虑配置 ASAN_SYMBOLIZER_PATH 以便在清理时有更好的符号。我就是这样找到的。

试图在 C 中制作哈夫曼树，但它一直说堆缓冲区溢出

Trying to make a Huffman tree in C, but it keeps saying heap-buffer-overflow

c

huffman-code