二进制搜索树在有效输入上意外崩溃

Question

程序应该在二进制搜索树中进行基本操作，例如搜索项、添加新元素等。然而，它经常崩溃，即使是在有效的输入。

/* Edit: Translated the symbols from Portuguese into
 * English for readibility's sake. Please base any
 * answers upon the original post, as I could have made
 * something wrong in the process. I translated string
 * literals, too, and that may cause input to the original
 * program to become invalid. Again, read the original post.
 *  - KemyLand
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXP 40
#define MAXT 100

typedef enum
{
    false,
    true
} bool;

struct node
{
    char *word, *translation;
    bool marker;
    struct node *leftChild;
    struct node *rightChild;
};

void loader(char *word, char *translation);
void add(char *word, char *translation);
void mark(char *word);
void alphanum_list();
void mark_list();
struct node *root = NULL;
struct node* search(char *word);
struct node* load();


int main()
{
    char word[MAXP];
    char translation[MAXT];
    char option[15];

    while(1)
    {
        scanf("%s", option);
        printf("%s", option);

        if(strcmp(option, "LOAD") == 0) {
            load();
        } else if(strcmp(option, "ADD") == 0) {
            scanf("%s", word);
            scanf("%s", translation);
            load(word, translation);
        } else if(strcmp(option, "SEARCH") == 0) {
            scanf("%s", word);
            search(word);
        } else if(strcmp(option, "MARK") == 0) {
            scanf("%s", word);
            mark(word);
        } else if(strcmp(option, "ALPHANUM_LIST") == 0) {
            alphanum_list();
        } else if(strcmp(option, "MARK_LIST") == 0) {
            mark_list();
        }
    }

    return 0;
}

struct node* search(char *word)
{
    struct node *current=root;

    while(strcmp(current->word, word) != 0) {
        if(current != NULL) {
            if(strcmp(current->word,word) < 0) {
                current = current->leftChild;
            } else {
                current = current->rightChild;
            }

            if(current == NULL) {
                printf("WORD DOESN'T EXIST\n");
                return NULL;
            }
        }
    }

    printf("%s %s\n", current->word, current->translation);
    return current;
}

应该加载输入树。

struct node* load()
{
    char str[1000];
    char word[MAXP];
    char translation[MAXT];

    while(1) {
        do {
            gets(str);
            sscanf("%s %s", word, translation);
            loader(word, translation);
        } while(strcmp(str,"end$dictionary") != 0);
        printf("DICTIONARY LOADED\n");
    }
}

这里定义了带有树的操作。

void loader(char *word, char *translation)
{
    struct node *tempNode = (struct node*)malloc(sizeof(struct node));
    struct node *current;
    struct node *father;

    tempNode->word = word;
    tempNode->translation = translation;
    tempNode->leftChild = NULL;
    tempNode->rightChild = NULL;

    /* If tree is empty */
    if(root == NULL) {
        root = tempNode;
    } else {
        current = root;
        father = NULL;
    }

    while(1) {
        father = current;

        /* Goes to the left side of the tree */
        if(strcmp(word,father->word) < 0) {
            current = current->leftChild;
            /* Insert to the left */

            if(current == NULL) {
                father->leftChild = tempNode;
                return;
            }
        } else {
            current = current->rightChild;

            if(current == NULL) {
                father->rightChild = tempNode;
                return;
            }
        }
    }
}

void add(char *word, char *translation)
{
    struct node *tempNode = (struct node*)malloc(sizeof(struct node));
    struct node *current;
    struct node *father;

    tempNode->word = word;
    tempNode->translation = translation;
    tempNode->leftChild = NULL;
    tempNode->rightChild = NULL;

    /* If tree is empty */
    if(root == NULL) {
        root = tempNode;
    } else {
        current = root;
        father = NULL;
    }

    while(1) {
        father = current;

        /* Goes to the left side of the three */
        if(strcmp(word,father->word) < 0) {
            current = current->leftChild;
            /* Insert to the left */

            if(current == NULL) {
                father->leftChild = tempNode;
                printf("WORD ADDED\n");
                return;
            } else {
                printf("WORD ALREADY EXISTS\n");
            }
        } else {
            current = current->rightChild;

            if(current == NULL) {
                father->rightChild = tempNode;
                printf("WORD ADDED\n");
                return;
            } else {
                printf("WORD ALREADY EXISTS\n");
            }
        }
    }
}

void mark(char *word)
{
    struct node *tempWord = search(word);

    if(tempWord != NULL) {
        tempWord->marker = true;
        printf("%s MARKED\n", tempWord->word);
    } else {
        printf("WORD NOT FOUND\n");
    }
}

void alphanum_list()
{
    struct node *tempNode = root;
    if(tempNode != NULL) {
        alphanum_list(tempNode->leftChild);
        printf("%s\n", tempNode->word);
        alphanum_list(tempNode->rightChild);
    }

    printf("END OF LIST\n");
}

void mark_list()
{
    struct node *tempNode = root;
    if(tempNode != NULL) {
        mark_list(tempNode->leftChild);
        if(tempNode->marker == true) {
            printf("%s\n", tempNode->word);
        }

        mark_list(tempNode->rightChild);
    }

    printf("END OF MARKED ENTRIES\n");
}

Answer 1

loader函数不复制插入字典节点中的单词.它们都指向load函数中的本地数组，这将在load函数返回后立即失效。以这样的方式修正代码：

tempNode->word = strdup(word);
tempNode->translation = strdup(translation);
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;

当字典为空时，将新节点存储到root，但随后应从函数返回。然后，由于current未初始化，当前代码将调用未定义的行为。

以下是一个简化和更正的版本：

void loader(const char *word, const char *translation) {
    struct node *tempNode = malloc(sizeof(*tempNode));
    struct node *current;

    if (tempNode == NULL) {
        fprintf(stderr, "cannot allocate memory\n");
        return;
    }
    tempNode->word = strdup(word);
    tempNode->translation = strdup(translation);
    tempNode->leftChild = tempNode->rightChild = NULL;

    /* If tree is empty */
    if (root == NULL) {
        root = tempNode;
        return;
    }
    for (current = root;;) {
       /* Goes to the left side of the tree */
        int cmp = strcmp(word, current->word);
        if (cmp == 0) {
            fprintf(stderr, "duplicate word: %s\n", word);
            free(tempNode->word);
            free(tempNode->translation);
            free(tempNode);
            return;
        }
        if (cmp < 0) {
            if (current->leftChild == NULL) {
                current->leftChild = tempNode;
                return;
            }
            current = current->leftChild;
        } else {
            if (current->rightChild == NULL) {
                current->rightChild = tempNode;
                return;
            }
            current = current->rightChild;
        }
    }
}

您的搜索函数崩溃在一个空字典上，因为在current == NULL上的测试是在取消引用指针之后完成的。顺便说一句，这棵树是朝错误的方向穿过的。

以下是修正后的版本：

struct node *search(const char *word) {
    struct node *current = root;

    while (current) {
        int cmp = strcmp(word, current->word);
        if (cmp == 0) {
            printf("%s %s\n", current->word, current->translation);
            return current;
        }
        if (cmp < 0) {
            current = current->leftChild;
        } else {
            current = current->rightChild;
        }
    }
    printf("WORD DOESN'T EXIST: %s\n", word);
    return NULL;
}