1

对于这个源代码有多长，我提前道歉。我不完全确定我在哪里出错了。我写了一个二叉树实现和一些树遍历的函数。向树中添加一项是可行的，但添加多项会导致分段错误。DDD 在 backtrace 中列出了几个函数：命名为 isfull、addToTree 和 isEmpty。

该程序跨越三个源文件（对不起）。

/*----------------------------------Tree.h----------------------------------*/

#ifndef TREE
#define TREE

#define MAXHEIGHT 4

typedef struct cat{
    char *name; 
    int age; 
}Item; 

typedef struct node{
    Item thing; 
}Node; 

typedef struct tree{
    Node *root;
    struct tree *left, *right;  
    int leafcount; 
}Tree; 

void initializeTree(Tree *); 
void closeTree(Tree *); 
int isEmpty(const Tree *);
int isFull(const Tree*); 
Tree *searchTree(Item *thing, Tree *t, int (*)(const Item *, const Item *)); 
int addToTree(Item *, Tree *, int (*)(const Item *, const Item *)); 
int removeFromTree(Item *, Tree *);

int itemComp(const Item *, const Item *); 

#endif

/*----------------------------------Tree.c----------------------------------*/

#include "Tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

Node *copyToNode(Item *); 

/*Definition: Tree
  Node *root; 
  int leafcount; */

Node *copyToNode(Item *thing){
    Node *tmp = malloc(sizeof(Node)); 
    if(tmp == NULL)
        return tmp; 
    tmp->thing = *thing; 
    return tmp; 
}

void initializeTree(Tree *t){
    t->root = NULL; 
    t->right = t->left = NULL; 
    t->leafcount = 0; 
}

int isEmpty(const Tree *t){
    return t->root == NULL; 
}

int isFull(const Tree *t){
    return t->leafcount == (int)pow(2,MAXHEIGHT) - 1;  
} 

int addToTree(Item *thing, Tree *t, int (*fp)(const Item *, const Item *)){
    if(isFull(t))
        return 0;

    if(isEmpty(t)){
        Node *current = copyToNode(thing);
        if(current == NULL){
            puts("Couldn't copy to tree!");
            return 0; 
        } 
        t->root = current;
        t->leafcount++; 
        return 1; 
    } 

    if(fp(thing, &t->root->thing) <= 0)
       return addToTree(thing, t->left, fp); 
    else
       return addToTree(thing, t->right, fp);  
}

Tree *searchTree(Item *thing, Tree *t, int (*fp)(const Item *, const Item *)){
    int temp; 

    if(t->root == NULL) 
        return NULL; 
    else if((temp = fp(&t->root->thing, thing)) == 0)
        return t;
    else if(temp = -1)
        return searchTree(thing, t->left, fp);
    else
        return searchTree(thing, t->right, fp);  
}


int removeFromTree(Item *thing, Tree *t){
    /*Tree *tmp = searchTree(thing, t); 
    Not finished*/ 
}

void closeTree(Tree *t){
    return; 
}

    /*------------------------------TreeDriver.c-------------------------------*/
#include "Tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXNAME 30 
int promptUser(void); 
int itemComp(const Item *, const Item *);
Item * createUserItem(); 

int main(){
    int userChoice;
    Item * userItem = NULL; 
    Tree userTree; 

    initializeTree(&userTree); 

    do{
        userChoice = promptUser();
        switch(userChoice){
            case 1:
                puts("Enter cat information to add"); 
                userItem = createUserItem(); 
                if(addToTree(userItem, &userTree, itemComp))
                    puts("Cat successfully added!"); 
                else
                    puts("Could not add cat!"); 
                break;
            case 2:
                puts("Enter cat information to search for"); 
                userItem = createUserItem();
                if(searchTree(userItem, &userTree, itemComp))
                   puts("Cat found!");
                else
                   puts("Cat not found!"); 
                break; 
            case 3:
                if(isEmpty(&userTree))
                    puts("Tree is empty!");
                else
                    puts("Tree is not empty!");
                break;
            case 4:
                if(isFull(&userTree))
                    puts("Tree is full!");
                else
                    puts("Tree is not full!"); 
                break;
            case 0:
                break;
            default:
                puts("Not an option!"); 
                break;
        }

    }while(userChoice); 

}

int itemComp(const Item *thing_one, const Item *thing_two){
    int comparison;

    if(comparison = strcmp(thing_one->name, thing_two->name))
        return comparison; 

    return !(thing_one->age == thing_two->age);
}

int promptUser(){
    int tmp; 

    puts("--------MENU---------");
    puts("1. Create cat"); 
    puts("2. Search for cat"); 
    puts("3. Check empty");
    puts("4. Check full"); 
    puts("0. Quit"); 

    scanf("%d", &tmp); 
    while(getchar() != '\n')
        ;

    return tmp; 
}

Item * createUserItem(){
    Item *tmp = malloc(sizeof(Item));  
    static char namebuf[MAXNAME];

    printf("Enter cat name: "); 
    if(fgets(namebuf, MAXNAME, stdin) == NULL)
        return NULL; 

    tmp->name = malloc(strlen(namebuf)); 
    strcpy(tmp->name, namebuf);

    printf("Enter cat age:\t");
    scanf("%d", &tmp->age); 

    while(getchar() != '\n')
       ;

    return tmp; 
}

无论如何，我不确定如何解释调试器的回溯。我哪里做错了？它可能与我如何处理在驱动程序文件中为用户输入创建一个虚拟项目有关吗？我不认为我处理得很好（或者这个程序的其余部分）。

谢谢

4

1 回答 1

3

免责声明：由于您指定您认为错误存在于您的addToTree函数中，因此我没有在其他任何地方寻找错误（除了您的结构定义）。

您的addToTree函数中有两个错误。首先，您没有leafcount正确处理。当您将节点推送到树中时，您会发现它是不正确的（我下面的解决方案没有解决这个问题）。其次，您需要将双指针传递给struct tree（或Tree），传递单指针不会让您插入到空树中，因为您将传递NULL.

第一个插入有效而后面的插入无效的唯一原因是因为您已经创建了一个节点（而如果您使用了包装器结构，它应该是NULL）。

要修复第二个错误，请执行以下操作：

int addToTree( Item *thing, Tree **t, int ( *fp )( const Item *, const Item * ) ) {
    if( isFull( *t ) == true) return 0;

    if( isEmpty( *t ) == true ) {
        Node *current = copyToNode( thing );

        if( current == NULL ) {
            puts( "Couldn't copy to tree!" );

            return 0; 
        }

        ( *t ) = current;

        return 1; 
    } 

    if( fp( thing, t->root->thing ) <= 0 )
       return addToTree( thing, &( ( *t )->left ), fp ); 
    else
       return addToTree( thing, &( ( *t )->right ), fp );  
}

旁白：我也会考虑以不同的方式命名您的结构。结构Node和Tree具有误导性，Node应该成为Item并且Tree应该成为BstNode（或任何您认为适合的命名方案），然后有一个名为的包装器结构BstTree，其定义如下：

struct BstTree {
  struct Tree *root;
  int height;
};

...其中root指向根Node，height是二叉搜索树的高度。这不仅可以更好地传达您的意图，还可以使您的实现更易于使用。

于 2013-08-14T01:38:29.110 回答