指针设置为 NULL 但不在调试器中

Question

所以我正在使用 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

在我的测试中，我检查根是否已设置为 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;
}

Answer 1

这是一个错误：

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。

freeTree 函数中的 node = NULL; 行设置函数参数（它是参数的副本），它不会修改调用上下文中的参数。

该函数确实释放了指向的内存，这使得所有指向该内存的指针都不确定，因此测试 tree->root == NULL 实际上通过使用不确定的值导致未定义的行为。

您的编译器应该警告 node=NULL; 的死存储，如果您没有看到警告，请尝试在编译器中调高警告 and/or 优化级别，或者运行静态分析器，例如 clang-tidy。 freeNode 有类似的问题。

要解决此问题，请更改调用代码，例如freeTree(tree->root); tree->root = NULL;，否则你将不得不使用传递指针，即传递你想要释放的节点的地址。

指针设置为 NULL 但不在调试器中

Pointer set to NULL but not in debugger

c

heap-memory

avl-tree