Lösungsbeispiel zu Blatt 8 (Aufgabe 12)

tree.c

/*
 *      tree.c  - Beispielprogramm fuer binaere Baeume
 *
 *      Synopsis: tree [-o outputfile] [-i inputfile] anzahl
 *
 *      Erzeugen eines ausgeglichenen binaeren Baums mit (anzahl) Datensaetzen,
 *      die in sortierter Folge aus (inputfile) oder der Standardeingabe
 *      gelesen werden;
 *
 *      Einfuegen und Loeschen von Datensaetzen (ohne Aufrechterhaltung
 *      der Ausgeglichenheit);
 *
 *      Schreiben der Daten in (outputfile) oder die Standardausgabe.
 *
 *      Martin Hasch, Universitaet Ulm, Januar 1997.
 */

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

typedef struct tree {
        char *t_key;
        char *t_info;
        struct tree *t_left, *t_right;
} *Tree;

static Tree root;               /* Wurzel des zu verwaltenden Baumes */

/*
 *      Duplizieren einer Zeichenkette in den dynamischen Speicher.
 *      Resultat ist die Kopie.  Erfolg wird garantiert.
 */
static char * str_save(char *str)
{
        char * result;

        result = (char *) malloc( strlen(str)+1 );
        if ( result == NULL ) {
                fprintf(stderr, "out of memory!\n");
                exit(2);
        }
        return strcpy(result, str);
}

/*
 *      Allokation eines neuen Knotens ohne Initialisierung.
 *      Resultat ist der neue Knoten.  Erfolg wird garantiert.
 */
static Tree new_tree(void)
{
        Tree result;

        result = (Tree) malloc( sizeof(struct tree) );
        if ( !result ) {
                fprintf(stderr, "out of memory!\n");
                exit(2);
        }
        return result;
}

/*
 *      Ausgabe eines Datensatzes in die Datei (output).
 */
static void print_element(Tree element, FILE *output)
{
        (void) fprintf(output, "%s:%s\n", element->t_key, element->t_info);
}

/*
 *      Ueberlesen der Standardeingabe bis zum Zeilenende.
 */
static void read_newline(void)
{
        int ch;

        ch = getchar();
        while ( ch != EOF && ch != '\n' )
                ch = getchar();
}

/*
 *      Lesen eines Schluessels aus der Standardeingabe.
 *      Resultat ist 1 bei Erfolg, sonst 0.
 */
static int read_key(char **key)
{
        char buf[BUFSIZ];

        if ( gets(buf) == NULL )
                return 0;
        if ( strchr(buf, ':') != NULL ) {
                fprintf(stderr, "':' not expected!\n");
                return 0;
        }
        *key = str_save(buf);
        return 1;
}

/*
 *      Lesen eines Datensatzes aus der Datei (input).
 *      Resultat ist 1 bei Erfolg, sonst 0.
 */
static int read_element(char **key, char **info, FILE *input)
{
        char buf[BUFSIZ];
        char *pos;
        char *eos;

        if ( fgets(buf, BUFSIZ, input) == NULL )
                return 0;
        if ( (pos = strchr(buf, ':')) == NULL ) {
                fprintf(stderr, "':' expected!\n");
                return 0;
        }
        *pos++ = '\0';
        if ( (eos = strchr(pos, '\n')) != NULL ) {
            *eos = '\0';
        }
        *key = str_save(buf);
        *info = str_save(pos);
        return 1;
}

/*
 *      Einlesen eines Baumes mit (size) Elementen aus der Datei (input).
 *      Korrekte Syntax und Reihenfolge wird vorausgesetzt.
 */
void buildTree(Tree *tree, int size, FILE *input)
{
        Tree this;

        if ( size <= 0 ) {
                this = NULL;
        } else {
                this = new_tree();
                buildTree(&this->t_left, size/2, input);
                if ( !read_element(&this->t_key, &this->t_info, input) ) {
                        fprintf(stderr, "invalid or missing data!\n");
                        exit(1);
                }
                buildTree(&this->t_right, (size-1)/2, input);
        }
        *tree = this;
}

/*
 *      Ausgabe der Struktur eines Baumes in zweidimensionaler Form.
 */
void printTree(Tree tree, int level)
{
        if ( tree != NULL ) {
                printTree(tree->t_left, level+1);
                printf("%*s%s\n", level*4, "", tree->t_key);
                printTree(tree->t_right, level+1);
        }
}

/*
 *      Ausgabe aller Datensaetze eines Baumes in inorder-Reihenfolge
 *      in die Datei (output).
 */
void inorder(Tree tree, FILE *output)
{
        if ( tree != NULL ) {
                inorder(tree->t_left, output);
                print_element(tree, output);
                inorder(tree->t_right, output);
        }
}

/*
 *      Ausgabe aller Datensaetze eines Baumes in preorder-Reihenfolge
 *      in die Datei (output).
 */
void preorder(Tree tree, FILE *output)
{
        if ( tree != NULL ) {
                print_element(tree, output);
                preorder(tree->t_left, output);
                preorder(tree->t_right, output);
        }
}

/*
 *      Ausgabe aller Datensaetze eines Baumes in postorder-Reihenfolge
 *      in die Datei (output).
 */
void postorder(Tree tree, FILE *output)
{
        if ( tree != NULL ) {
                postorder(tree->t_left, output);
                postorder(tree->t_right, output);
                print_element(tree, output);
        }
}

/*
 *      Suche eines Datensatzes mit Schluessel (key) in einem Baum;
 *      Falls noch nicht vorhanden, Einfuegen und dabei key und info kopieren.
 *      Resultat ist ein Zeiger auf den Datensatz.
 */
Tree * insert(Tree *tree, char *key, char *info)
{
        int cmp;

        while ( *tree != NULL ) {
                cmp = strcmp(key, (*tree)->t_key);
                if ( cmp < 0 )
                        tree = &(*tree)->t_left;
                else if ( cmp > 0 )
                        tree = &(*tree)->t_right;
                else
                        return tree;
        }
        *tree = new_tree();
        (*tree)->t_key = str_save(key);
        (*tree)->t_info = str_save(info);
        (*tree)->t_left = (*tree)->t_right = NULL;
        return tree;
}

/*
 *      Loeschen des Datensatzes mit Schluessel (key) aus einem Baum,
 *      falls vorhanden.
 */
void delete(Tree *tree, char *key)
{
        int cmp;
        Tree *next;                     /* ggf. naechstgroesserer Datensatz */

        do {
                if ( *tree == NULL )
                        return;                 /* Schluessel unbekannt. */
                cmp = strcmp(key, (*tree)->t_key);
                if ( cmp < 0 )
                        tree = &(*tree)->t_left;
                else if ( cmp > 0 )
                        tree = &(*tree)->t_right;
        } while ( cmp );

        /*
         *      tree ist jetzt die Adresse des (einzigen) Zeigers auf den
         *      zu loeschenden Datensatz.
         */

        free( (*tree)->t_key );
        free( (*tree)->t_info );

        if ( (*tree)->t_right == NULL ) {
                free( *tree );
                (*tree) = (*tree)->t_left;
        } else {
                next = &(*tree)->t_right;
                while ( (*next)->t_left != NULL )
                        next = &(*next)->t_left;
                (*tree)->t_key = (*next)->t_key;
                (*tree)->t_info = (*next)->t_info;
                free( *next );
                *next = (*next)->t_right;
        }
}

/*
 *      Ausgabe der Aufrufsyntax und Programmabbruch.
 */
static void usage(void)
{
        fprintf(stderr, "usage: tree [-o outputfile] [-i inputfile] anzahl\n");
        exit(1);
}

/*
 *      Testprogramm mit kleinem Kommandointerpreter.
 *      Zeilen, die mit '+', '-' oder '=' beginnen, stehen fuer Einfuegen,
 *      Loeschen oder Struktur anzeigen.
 */
int main(int argc, char *argv[])
{
        char *infile = NULL;
        char *outfile = NULL;
        int count = -1;
        int i;
        int ch;

        /* Kommandozeile */
        for ( i=1; i<argc; ++i ) {
                if ( outfile == NULL && !strcmp(argv[i], "-o") ) {
                        if ( i+1 < argc )
                                outfile = argv[++i];
                        else
                                usage();
                } else if ( infile == NULL && !strcmp(argv[i], "-i") ) {
                        if ( i+1 < argc )
                                infile = argv[++i];
                        else
                                usage();
                } else if ( count < 0 && isdigit(argv[i][0]) ) {
                        count = atoi(argv[i]);
                } else
                        usage();
        }
        if ( count < 0 )
                usage();

        /* Initialisierung */
        if ( infile != NULL ) {
                FILE *input;
                if ( (input = fopen(infile, "r")) == NULL ) {
                        perror(infile);
                        exit(1);
                }
                buildTree(&root, count, input);
                (void) fclose(input);
        } else
                buildTree(&root, count, stdin);

        /* Bearbeitung der Eingabe */
        while ( (ch = getchar()) != EOF ) {
                char *key, *info;
                switch ( ch ) {
                case '+':
                        if ( read_element(&key, &info, stdin) ) {
                                (void) insert(&root, key, info);
                                free(key);
                                free(info);
                        } else
                                fprintf(stderr, "?\n");
                        break;
                case '-':
                        if ( read_key(&key) ) {
                                delete(&root, key);
                                free(key);
                        } else
                                fprintf(stderr, "?\n");
                        break;
                case '=':
                        read_newline();
                        printTree(root, 0);
                        break;
                default:
                        fprintf(stderr, "?\n");
                        read_newline();
                        break;
                }
        }

        /* Ausgabe */
        if ( outfile != NULL ) {
                FILE *output;
                if ( (output = fopen(outfile, "w")) == NULL ) {
                        perror(outfile);
                        exit(1);
                }
                inorder(root, output);
                if ( fclose(output) ) {
                        perror(outfile);
                        exit(1);
                }
        } else
                inorder(root, stdout);

        return 0;
}