1

このソースコードが長いことを前もってお詫び申し上げます。ここでどこが間違っているのか完全にはわかりません。私は、バイナリ ツリーの実装と、ツ​​リー トラバーサル用のいくつかの関数を作成しました。ツリーに項目を 1 つ追加すると機能しますが、複数の項目を追加するとセグメンテーション エラーが発生します。DDD では、バックトレースにいくつかの関数がリストされています。isfull、addToTree、isEmpty などの名前が付けられています。

プログラムは 3 つのソース ファイルにまたがっています (申し訳ありません)。

/*----------------------------------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他の場所（構造定義以外）でエラーを探しませんでした。

関数に 2 つのエラーがありますaddToTree。leafcountまず、正しく処理していません。ノードをツリーにプッシュすると、それが正しくないことがわかります（以下の私の解決策では修正されません）。struct tree次に、 (または)にダブル ポインターを渡す必要がありますTree。単一のポインターを渡すと、 を渡すことになるため、空のツリーに挿入できませんNULL。

最初の挿入が機能し、後続の挿入が機能しない唯一の理由は、既にノードを作成しているためです (一方、ラッパー構造を使用した場合は、 である必要がありますNULL)。

2 番目のエラーを修正するには、次の手順を実行します。

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指し、バイナリ検索ツリーの高さです。これにより、意図がよりよく伝わるだけでなく、実装がはるかに簡単になります。Nodeheight

于 2013-08-14T01:38:29.110 に答える