Ошибка Strcmp при вставке дерева двоичного поиска (рекурсия)? - PullRequest
Новая
       14

Ошибка Strcmp при вставке дерева двоичного поиска (рекурсия)?

0 голосов
/ 12 марта 2012

Я пытаюсь реализовать некоторые функции, которые позволяют мне добавлять «Книги» в двоичное дерево поиска для класса «Студент», но я получаю странную ошибку:

msvcr100d.dll! strcmp (unsigned char * str1, unsigned char * str2) Строка 83 Asm

Программа полностью на C / C ++, поэтому я не уверен, почему она возвращает ошибку на языке ассемблера?Моя первая мысль - что-то не так с моим использованием strcmp, и стек вызовов показывает строку 188 в качестве последнего выполненного оператора (до вышеуказанной ошибки), что означает, что я, возможно, где-то испортил свою рекурсию.Я вызываю функцию insertBook () ученика, так что вот мой класс ученика.Любая помощь?Спасибо. 

class Student : public Personnel { //inherit from Personnel
public:
    Book *bookTree;

    Book* searchBookTree(Book *bookNode, char *title) {
        if ((strcmp(title, bookNode->title)) < 0) //***LINE 188
            return searchBookTree(bookNode->left, title); 

        else if ((strcmp(title, bookNode->title)) > 0)
            return searchBookTree(bookNode->right, title);

        else
            return bookNode;
    }

    void insertBook(Book *node) {
        Book *newBook, *parent;
        newBook = node;

        newBook->left = NULL;
        newBook->right = NULL;

        if (bookTree == NULL) { //if bookTree is empty
            bookTree = newBook; 
        }
        else {          
            parent = searchBookTree(bookTree, newBook->title);
            newBook->left = parent->left;
            newBook->right = parent->right;
        }   
    }

    void printBooks(Book *top) {
        Book *root = top;
        if (root != NULL) {
            printBooks(root->left);
            cout << "BOOK LIST" << endl;
            cout << "Title:\t\t" << root->title << endl;
            cout << "URL:\t\t" << root->url << endl;
            printBooks(root->right);
        }
    } 

    void display() {
            Personnel::display();
            cout << "STUDENT" << endl;  
            cout << "Level:\t\t" << getLevel() << endl;
            printBooks(bookTree); cout << endl;
    }

    Student(char *cName, char *cBirthday, char *cAddress, char *cPhone, char *cEmail, level gradeLevel) 
        : Personnel(cName, cBirthday, cAddress, cPhone, cEmail) 
    {
        bookTree = NULL;
        setLevel(gradeLevel);
    }

};

Ответы [ 3 ]

1 голос
/ 12 марта 2012 
Book* searchBookTree(Book *bookNode, char *title) {
        if ((strcmp(title, bookNode->title)) < 0) //***LINE 188
            // What happens if bookNode->left == NULL ???
            return searchBookTree(bookNode->left, title); 

        else if ((strcmp(title, bookNode->title)) > 0)
            // What happens if bookNode->right== NULL ???
            return searchBookTree(bookNode->right, title);

        else
            return bookNode;
    }

вам понадобится точка завершения в вашей функции поиска. Вверху я бы сначала проверил, если bookNode == NULL.

1 голос
/ 12 марта 2012

Ваш рекурсивный поиск важного теста завершения отсутствует!В какой-то момент вы попадаете на низ дерева, не найдя предмет.И поэтому ваша поисковая функция вызывается с нулевым указателем для узла дерева!Проблема не в strcmp, а в нулевом указателе в одном из выражений аргумента.

Вы рассматривали только случай, когда элемент существует в дереве и в конечном итоге найден, пренебрегая не найденным случаем.

Программисты не должны измеряться их изобретательностью иих логика, но полнота анализа их случая.

  • Алан Дж. Перлис, Эпиграмма # 32
0 голосов
/ 12 марта 2012

У вашей insert рутины есть проблемы. Я предлагаю вам сделать searchBookTree просто вернуть нулевой указатель, когда он ничего не находит. Не используйте эту процедуру при реализации insertBook. Скорее, вы можете написать insertBook также рекурсивно: 

private:
    // Inserts bookNode into tree, returning new tree:

    Book *insertBookHelper(Book *tree, Book *bookNode) {
        if (tree == NULL)
            return bookNode; // bookNode becomes new tree

        // no need to call strcmp twice!!!
        int cmp = strcmp(title, bookNode->title);

        if (cmp < 0) {
            tree->left = insertBookHelper(tree->left, bookNode->title); 
        else if (cmp > 0)
            tree->right = insertBookHelper(tree->right, bookNode->title);
        else {
            // Uh oh! Tree already contains that title, what to do?
            // Answer: update!
            // I don't know how to write this because I don't know
            // how your Book class handles the memory for the strings,
            // and what other members it has besides the title.
            // this could be a possibility:
            // bookNode->left = tree->left;    // install same child pointers
            // bookNode->right = tree->right;  // into bookNode.
            // *tree = *bookNode; // if Book has a sane copy constructor!!!
        }
        return tree;
    }

 public:
    void insertBook(Book *node) {
        tree = insertBookHelper(tree, node);
    }

Вы видите, как работает рекурсия? Это немного отличается от чистого поиска. Каждый рекурсивный уровень обрабатывает вставку в поддерево и возвращает новое поддерево. Часто возвращаемое дерево точно такое же, как и дерево, которое вошло! Но при вставке в пустое дерево возвращаемое дерево не то же самое: вошедшее дерево является нулевым указателем, но выходит ненулевой указатель. Этот трюк, делающий вид, что мы создаем новое дерево и возвращаем его в качестве замены старого дерева, делает код гладким.

...