C语言中设置char*数组末尾为NULL时破坏二叉搜索树的问题排查
问题根因排查与修复方案
你遇到的“赋值最后一个元素为NULL就损坏树结构”的问题,本质是前期内存分配的类型、大小错配导致的越界写,不是赋值语句本身的逻辑错误。
具体问题点拆解
- 最核心的致命错误:键值数组的内存分配完全不符合类型要求
你定义的list_keys是char**类型,也就是一个“存储字符串指针的数组”,数组里每个元素的类型是char*(字符串指针),单元素占8字节(64位系统)或4字节(32位系统),但你当前的分配代码是:
这里有两个致命问题:char **list_keys; list_keys = (char *)malloc((tree_size(tree)+1)*sizeof(char));- 大小计算错误:用
sizeof(char)(值为1)作为单元素大小,相当于给每个指针元素只分配1字节空间。比如64位系统下一个char*指针需要8字节,你只给1字节,后续往这个数组里写指针值时会严重越界。 - 类型强转错误:把malloc返回的通用指针强转成
char*再赋值给char**变量,本身就是C语言里的类型不匹配操作。
堆内存的分配是按地址相邻排布的,你当初申请的这个过小的数组空间,旁边存的就是二叉树的节点结构。当你执行list_keys[tree_size(tree)] = NULL时,因为数组整体内存太小,这个访问位置已经超出了你的合法堆块范围,写入的0值(NULL的二进制表示)直接覆盖了旁边二叉树节点的left_child/right_child/entry指针字段,把这些字段全改成了0(空指针)。这就是为什么执行这行代码前tree_size能正常返回,执行完树结构直接损坏、调用就段错误的原因。
正确的分配逻辑应该按指针类型算大小,不需要手动强转:
int node_cnt = tree_size(tree); // 按单元素是char*的大小计算总空间,多分配1个位置存末尾的NULL终止符 list_keys = malloc((node_cnt + 1) * sizeof(char*)); - 大小计算错误:用
- 隐藏的越界风险:单个键字符串的内存分配漏了结束符
你现在存储单个键的代码是:list_keys[index] = (char *)malloc((strlen(tree->entry->key))*sizeof(char)); strcpy(list_keys[index],tree->entry->key);strlen计算的是字符串有效内容的长度,不包含字符串末尾必须的\0结束符,你分配的空间刚好装下有效内容,没有留1字节存\0,strcpy写入时会越界1字节踩坏相邻内存,只是之前堆布局刚好没覆盖到树结构,没立刻出问题。
正确写法要多预留1字节的结束符空间:size_t key_len = strlen(tree->entry->key); list_keys[index] = malloc(key_len + 1); strcpy(list_keys[index], tree->entry->key); - 收集键的递归逻辑有下标错位隐患
你当前的递归辅助函数里,遍历完当前节点把index加1后,递归左、右子树时直接把这个递增后的index传下去了,没有考虑左子树遍历完会占用连续的若干个数组位置,右子树拿到的起始下标会和左子树的存储位置重叠,最终收集的键列表会出现覆盖、错位。之前测试没触发这个问题大概率是用了只有单侧子树的简单测试用例。
正确的递归逻辑应该让函数返回分支遍历完成后的最新下标,避免位置重叠:int tree_get_keys_aux(struct tree_t *tree, char **list_keys, int index) { // 存储当前节点的键 size_t key_len = strlen(tree->entry->key); list_keys[index] = malloc(key_len + 1); strcpy(list_keys[index], tree->entry->key); index++; // 递归左子树,拿到左子树遍历完的最新下标 if (tree->left_child != NULL) { index = tree_get_keys_aux(tree->left_child, list_keys, index); } // 用左子树遍历完的下标,继续递归右子树 if (tree->right_child != NULL) { index = tree_get_keys_aux(tree->right_child, list_keys, index); } return index; } // 调用时直接拿到遍历完成的下标,不用重复调用tree_size计算大小 int final_idx = tree_get_keys_aux(tree, list_keys, 0); list_keys[final_idx] = NULL;
补充优化提示
你当前的tree_size函数没有对入参判空,如果传入的tree指针为NULL会直接访问tree->entry触发段错误,可以把函数开头加一层空判断增强鲁棒性:
int tree_size(struct tree_t *tree) { if (tree == NULL) return 0; // 原有逻辑... }
内容的提问来源于stack exchange,提问作者maf
相关产品推荐
相关产品推荐

