c - 指针设置为 NULL 但不在调试器中
问题描述
所以我正在处理 AVL 树,但是我似乎既无法使删除功能正常工作,也无法正确释放树。delete 函数每次都会出现段错误,但 free 函数在调试器中会出现段错误。这是 gdb 的堆栈跟踪:
#0 0x00007fffd935a87a in msvcrt!_memicmp_l () from C:\WINDOWS\System32\msvcrt.dll
#1 0x0000000000402811 in isPresentRecurs (root=0xb756d0, searchedValue=0xb795b0 "aaa", found=0x61fcec) at ../.source/binTree.c:206
#2 0x00000000004027d6 in isPresent (root=0xb756d0, searchKey=0xb795b0 "aaa") at ../.source/binTree.c:200
#3 0x0000000000401c3d in main () at test.c:110
在我的测试中,我检查 root 是否已设置为 NULL,正常运行它会完成,但是在调试器中运行它不会,而是进入 else 语句:最小示例(test.c):
#include "binTree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TRACE 0
#define MAX_SEARCH_ITEMS 20
void fillTree(binTree **tree);
void fillSearchValues( char **valArray);
void fillTree(binTree** tree){
printf( "Constructing tree\n\n" );
char key[200] ="";
for(int j=1 ;j<4;j++ ){
memset(&key,0,199);
for(int i=0; i<26; i++){
for(int k = 0;k<j;k++) key[k]= i+'a';
Var value;
value.data = malloc(sizeof(varData));
value.data->iData = j;
value.type =INTEGER;
(*tree)->root= insert((*tree)->root,key,value);
if(TRACE) printf("key: %s, value: %d\n",(*tree)->root->key,(*tree)->root->value.data->iData);
}
}
(*tree)->nodeCount = getSizeBinaryTree((*tree)->root);
printf( "\n\nTree constructed\n\n" );
}
void fillSearchValues( char **valArray){
char key[200]="";
for(int j=1 ;j<4;j++ ){
memset(&key,0,199);
for(int i=0; i<26; i++){
if(i*j>MAX_SEARCH_ITEMS) break;
for(int k = 0;k<j;k++) key[k]= i+'a';
*(valArray+i*j) = strdup(key);
if (TRACE)printf ("%s read; %s inserted\n", key, valArray[i*j] );
}
}
}
int main(){
binTree *tree = createNewTree();
fillTree(&tree);
printTree(tree->root);
/* //Fails at delete
for(int i=0;i<26;i++){
char string = i+'a';
tree->root = Delete(tree->root,&string);
}*/
printf("\nFreeing Tree: \n=================================\n");
freeTree(tree->root);
if(tree->root==NULL) printf("Tree has been freed successfully\n");
else printf("Failed to free tree \n");
// searching after freeing
int found =0; int lost =0;
char *values[MAX_SEARCH_ITEMS];
fillSearchValues(values);
for(int i=0;i<MAX_SEARCH_ITEMS;i++){
if(isPresent(tree->root,values[i])){
if (TRACE)printf("found search value %s\n",values[i]);
found++;
}else{
lost++;
if(TRACE)printf("didnot find search value %s\n",values[i]);
}
}
printf("found %d of %d while cleared %d\n", found,MAX_SEARCH_ITEMS,lost);
free(tree);
return 0;
}
binTree.h:
#ifndef BINTREE_H
#define BINTREE_H
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define COUNT 10
typedef enum TYPE {INTEGER, FLOAT, CHARACTER} TYPE;
typedef union {
float fData;
int iData;
char cData;
} varData;
typedef struct Var{
varData * data;
TYPE type;
} Var;
typedef struct Node{
char* key;
Var value;
int height;
struct Node *left;
struct Node *right;
}Node;
typedef struct binTree{
Node *root;
unsigned int nodeCount;
}binTree;
int max(int a,int b);
binTree *createNewTree();
Node *newNode(char *key,Var value);
void freeTree(Node *node);
void freeNode(Node *node);
Node *insert(Node *node,char *key,Var value);
Node *rightRotate(Node *n);
Node *leftRotate(Node *n);
int height(Node *node);
int getBalance(Node *N);
void printTree(Node *root);
void printTreeS(Node *root,int space);
int isPresent(Node *root,char *searchKey);
void isPresentRecurs(Node *root,char *searchedValue,int *found);
Node *minValueNode(Node *node);
Node *search(Node *node,char *key);
Node *Delete(Node *root,char *key);
int getSizeBinaryTree(Node* root);
#endif
binTree.c
#include "binTree.h"
int max(int a, int b){
return (a > b)? a : b;
}
binTree* createNewTree(){
binTree *t = (binTree *) malloc(sizeof(binTree));
if(!t){
printf("Failed at allocationg tree\n");
exit(-1);
}
t->root = NULL;
return t;
}
Node* newNode(char * key,Var value){
Node *p = (Node*)malloc(sizeof(Node));
if(!p){
printf("Failed at allocationg node\n");
exit(-1);
}
p->key = strdup(key);
p->value = value;
p->left=p->right=NULL;
p->height = 1;
return p;
}
void freeTree(Node* node){
if (node==NULL) return;
freeTree(node->left);
freeTree(node->right);
freeNode(node);
node=NULL;
}
void freeNode(Node *node){
free(node->value.data);
node->value.data = NULL;
free(node->key);
node->key = NULL;
free(node);
node = NULL;
}
Node* insert(Node *node, char *key,Var value){
if (node == NULL) return newNode(key,value);
if ( strcasecmp(key ,node->key)<0) node->left = insert(node->left, key,value);
else if (strcasecmp(key ,node->key)>0) node->right = insert(node->right, key,value);
else if(strcasecmp(key,node->key)==0){
if(memcmp(&value.data,&node->value,sizeof(Var))!=0){
memcpy(&node->value,&value,sizeof(Var));
}
return node;
};
node->height = max(height(node->left),height(node->right))+1;
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && strcasecmp(key, node->left->key)<0)
return rightRotate(node);
// Right Right Case
if (balance < -1 && strcasecmp(key, node->right->key)>0)
return leftRotate(node);
// Left Right Case
if (balance > 1 && strcasecmp(key, node->left->key)>0){
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && strcasecmp(key,node->right->key)<0){
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
Node *rightRotate(Node *n){
Node *leftNode =n->left;
if(!leftNode) return n;
Node *rightOfLeft =leftNode->right;
leftNode->right = n;
n->left = rightOfLeft;
n->height = max(height(n->left), height(n->right)) + 1;
leftNode->height = max(height(leftNode->left), height(leftNode->right)) + 1;
return leftNode;
}
Node *leftRotate(Node *n){
Node *rightNode = n->right;
if(!rightNode) return n;
Node *leftOfright = rightNode->left;
rightNode->left = n;
n->right = leftOfright;
n->height = max(height(n->left), height(n->right)) + 1;
rightNode->height = max(height(rightNode->left), height(rightNode->right)) + 1;
return rightNode;
}
int height(Node *node){
if (!node) return 0;
return node->height;
}
int getBalance(Node *N){
if (N == NULL) return 0;
return height(N->left) - height(N->right);
}
void printTree(Node *root){
printTreeS(root, 0);
}
void printTreeS( Node *root, int space){
if (root == NULL)
return;
space += COUNT;
printTreeS(root->right, space);
printf("\n");
for (int i = COUNT; i < space; i++) printf(" ");
if (root->value.type == CHARACTER)printf("type: CHAR key: %s value: %s\n", root->key, root->value.data->cData);
if (root->value.type == INTEGER)printf("type: INT key: %s value: %d\n", root->key, root->value.data->iData);
if (root->value.type == FLOAT)printf("type: FLOAT key: %s value: %f\n", root->key, root->value.data->fData);
printTreeS(root->left, space);
}
int isPresent(Node* root, char* searchKey){
int found = 0;
isPresentRecurs( root, searchKey, &found );
return found;
}
void isPresentRecurs( Node *root,char *searchedValue,int* found ){
if (root) {
if (strcasecmp(root->key,searchedValue)==0)
*found = 1;
else {
isPresentRecurs(root->left, searchedValue, found);
if (!(*found))
isPresentRecurs( root->right, searchedValue, found);
}
}
}
Node * minValueNode(Node* node){
if(!node) return NULL;
if(node->left )return minValueNode(node->left);
return node;
}
Node *search(Node *node, char *key){
if (node == NULL || strcmp(node->key, key)==0)return node;
if (strcmp(node->key, key)<0) return search(node->right, key);
return search(node->left, key);
}
int getSizeBinaryTree(Node* root){
if (root) return 1 +getSizeBinaryTree( root->left ) + getSizeBinaryTree( root->right );
else return 0;
}
Node* Delete(Node* root,char *key) {
if (root==NULL) return root;
else if (strcasecmp(key ,root->key)>0) root->left =Delete(root->left,key);
else if (strcasecmp(key ,root->key)<0) root->right = Delete(root->right,key);
else {
if(root->right==NULL && root->left==NULL) {
free(root);
root = NULL;
}
else if(root->left!=NULL && root->right==NULL) {
Node* temp = root->left;
root = root->left;
freeNode(temp);
}
else if(root->right!=NULL && root->left==NULL) {
Node* temp = root->right;
root = root->right;
freeNode(temp);
}
else {
Node* temp = minValueNode(root->right);
root->key= temp->key;
root->value = temp->value;
root->right = Delete(root->right,temp->key);
}
}
if(root==NULL) return root;
root->height = 1 + max(height(root->left),height(root->right));
int balance = getBalance(root);
//Left Left Case
if(balance > 1 && getBalance(root->left) >=0) return rightRotate(root);
// Right Right Case
if(balance < -1 && getBalance(root->right) <=0) return leftRotate(root);
// Left Right Case
if(balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
//Right Left Case
if(balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
解决方案
这是个错误:
freeTree(tree->root);
if(tree->root==NULL) printf("Tree has been freed successfully\n");
else printf("Failed to free tree \n");
C 使用按值传递,因此无法freeTree
设置tree->root
为NULL
.
node = NULL;
函数内的行freeTree
设置函数参数(它是参数的副本),它不会修改调用上下文中的参数。
该函数确实释放了指向的内存,这使得指向该内存的所有指针都是不确定的,因此测试tree->root == NULL
实际上通过使用不确定的值导致了未定义的行为。
您的编译器应该警告您的死存储node=NULL;
,如果您没有看到警告,请尝试在您的编译器中调高警告和/或优化级别,或运行静态分析器,例如 clang-tidy。freeNode
有类似的问题。
要解决此问题,要么更改调用代码,例如freeTree(tree->root); tree->root = NULL;
,要么您将不得不使用传递指针,即传递您要释放的节点的地址。
推荐阅读
- python - 对象不存在错误:用户没有个人资料
- php - 重用准备好的语句会产生分段错误
- javafx - 单元格背景超过单元格高度
- python - 计算矩阵行和向量行之间的 KL 散度
- typescript - @Watch('$router') 未被触发并引发异常
- sql - Oracle Pivot - 分配不带引号的列名
- docker - 当它们构建在主机上时,docker 图像存储在哪里。它在注册表中吗?
- c++ - clang 在 std::async 中因 char * 异常而崩溃
- c# - NAudio WaveFileReader.ReadNextSampleFrame() 返回无效幅度
- tibco-business-works - 如何遍历 CSV 文件并在写入文件活动中写入每一行?