[C-Sprachalgorithmus] binärer Suchbaum

Implementierung eines 2-Minuten-Suchbaumalgorithmus in C-Sprache

Lernumgebung

Referenzmaterial

Neuestes Algorithmus-Wörterbuch in C-Sprache (geschrieben von Haruhiko Okumura / 1991, erste Ausgabe der technischen Überprüfungsfirma: 206 Seiten)

2 Minuten Erkundungsbaumübersicht

Zitiert aus den folgenden Referenzmaterialien

Ein gegabelter Baum, der zum Suchen verwendet wird. Jeder Knoten hat Daten und zwei Zeiger, alle Daten von Nachkommen, die durch den linken Zeiger links verbunden sind, sind kleiner als Sie selbst, und alle Daten von Nachkommen, die durch den rechten Zeiger rechts verbunden sind, sind größer als Sie. Eine 2-minütige Suche im Suchbaum beginnt an der Wurzel und folgt dem linken oder rechten Zeiger, je nachdem, ob das gesuchte Objekt kleiner oder größer als der Knoten ist. Ein perfekt ausbalancierter, gegabelter Baum kann n-mal verglichen werden, um den gewünschten von 2 bis n-1 zu finden.

Quellcode

postfix.c


//2-Minuten-Suchbaum Binärer Suchbaum

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

//Typdeklaration des für die Suche verwendeten Schlüssels
typedef char keytype[21];

//Typdeklaration eines gegabelten Knotens
typedef struct node {
    struct node *left, *right;  //Zeiger auf den linken und rechten untergeordneten Knoten
    keytype key;                //Suchschlüssel
} *nodeptr;     //Zeiger zeigt auf einen Knoten

struct node nil;    //Knoten, der das Ende des Baums darstellt
nodeptr root = &nil;    //Zeiger zeigt auf die Wurzel

//In einen Baum einfügen(Anmeldung)Funktion
nodeptr insert(keytype insertkey){
    int cmp;
    nodeptr *p;     //Zeiger zeigt auf einen Knoten
    nodeptr q;      //Knotenentität

    strncpy(nil.key,insertkey,sizeof(keytype));  //Kopieren Sie den Argumentschlüssel in den Schlüssel des Bewahrers

    p = &root;  //Weisen Sie dem internen Variablenzeiger den Root-Zeiger zu

    //Schleife, bis die Tasten übereinstimmen
    while((cmp = strncmp(insertkey, (*p)->key, sizeof(keytype))) != 0)
    {
        //Wenn die Einfügetaste kleiner ist als die Taste des Knotens, auf den der Zeiger zeigt, gehen Sie zum kleineren Knoten links
        //Wenn der Einfügeschlüssel größer ist als der Schlüssel des Knotens, auf den der Zeiger zeigt, gehen Sie zum größeren Knoten rechts
        if(cmp < 0){
            //Bewegen Sie den Zeiger nach links
            p = &((*p)->left);
        } 
        else{
            //Bewegen Sie den Zeiger nach rechts
            p = &((*p)->right);
        }
    }

    //Wenn der Schlüssel bereits registriert ist
    if(*p != &nil){
        return NULL;
    }

    //Ordnen Sie dem Knoten Speicherbereich zu
    if((q = malloc(sizeof(*q))) == NULL){
        printf("insert:Speicherbereich konnte aufgrund unzureichenden Speichers nicht gesichert werden.\n");
        exit(EXIT_FAILURE);
    }
    
    //Kopieren Sie den Knotenschlüssel
    strncpy(q->key, insertkey, sizeof(keytype));

    q->left = &nil;
    q->right = *p;
    *p = q;

    //Gibt den registrierten Knoten zurück
    return q;

}

//Funktion löschen
//Gibt 0 zurück, wenn es gelöscht werden kann, 1, wenn es fehlschlägt
int delete(keytype deletekey){
    int cmp;

    nodeptr *p, *q;
    nodeptr r, s;

    strncpy(nil.key, deletekey, sizeof(keytype));   //Bewahrer

    p = &root;

    //Schleife, bis die Tasten übereinstimmen
    while((cmp = strncmp(deletekey, (*p)->key, sizeof(keytype))) != 0)
    {
        //Wenn die Einfügetaste kleiner ist als die Taste des Knotens, auf den der Zeiger zeigt, gehen Sie zum kleineren Knoten links
        //Wenn der Einfügeschlüssel größer ist als der Schlüssel des Knotens, auf den der Zeiger zeigt, gehen Sie zum größeren Knoten rechts
        if(cmp < 0){
            p = &((*p)->left);
        }
        else{
            p = &((*p)->right);
        }
    }

    //Wenn der Schlüssel nicht gefunden wird
    if(*p == &nil){
        return 1;
    }

    r = *p;

    if(r->right == &nil){
        *p = r->right;
    }else if(r->left == &nil){
        *p = r->right;
    } else{
        q = &(r->left);
        
        while((*q)->right != &nil){
            q = &((*q)->right);
        }

        s = *q;
        *q = s->left;
        s->left = r->left;
        s->right = r->right;
        *p = s;
    }

    //Platz freigeben
    free(r);

    return 0;

}

//Suchfunktion
//Wenn der Schlüssel gefunden wird, gibt er einen Zeiger auf den Knoten zurück, der den Schlüssel enthält.
//Gibt NULL zurück, wenn nicht gefunden
nodeptr search(keytype searchkey){
    int cmp;
    nodeptr p;

    strncpy(nil.key, searchkey, sizeof(keytype));
    p = root;

    while((cmp =strncmp(searchkey, p->key, sizeof(keytype))) != 0){
        if(cmp < 0){
            p = p->left;
        }else{
            p = p->right;
        }
    }
    
    if(p != &nil){
        //Wenn gefunden
        return p;
    }else{
        //Wenn nicht gefunden
        return NULL;
    }

}

void printtree(nodeptr p){
    static int depth = 0;

    //Zeigen Sie den Knoten links
    if((p->left) != &nil){
        depth++;
        //Rekursiver Aufruf
        printtree(p->left);
        depth--;
    }

    //Zeigen Sie den vom Argument empfangenen Knoten an
    printf("%*c%s\n", 5*depth, ' ', p->key);

    //Zeigen Sie den Knoten rechts
    if(p->right != &nil){
        depth++;
        //Rekursiver Aufruf
        printtree(p->right);
        depth--;
    }
}

int main(void) {

    char buf[22];
    short count;

    printf( "Befehl Iabc:Abc einfügen\n"
            "       Dabc:Abc entfernen\n"
            "       Sabc:Suche nach abc\n");
    
    for(;;){
        printf("Wie ist die Reihenfolge?");
        
        //Empfangen Sie Daten von der Standardeingabe für die Puffergröße
        if(scanf("%21s%*[^\n]", buf) != 1){
            break;
        }

        switch(buf[0]){
            //Prozess einfügen
            case 'I': case'i':
                //Funktion einfügen
                if(insert(&buf[1])){
                    printf("%21s%*[^\n]: Hat sich registriert\n",buf);
                }else{
                    printf("%21s%*[^\n]: Eingetragen\n",buf);
                }

                break;

            //Prozess löschen
            case 'D': case 'd':
                //Funktion löschen
                if(delete(&buf[1])){
                    printf("%21s%*[^\n]: Nicht gelöscht\n",buf);
                }else{
                    printf("%21s%*[^\n]: Es wurde gelöscht\n",buf);
                }

                break;

            //Suchvorgang
            case 'S': case 's':
                //Funktion löschen
                if(search(&buf[1])){
                    printf("%21s%*[^\n]: Eingetragen\n",buf);
                }else{
                    printf("%21s%*[^\n]:nicht registriert\n",buf);
                }

                break;
            default:
                printf("ich kann nutzen, D,Nur S.\n");
                break;
        }

        if(root != &nil){
            printf("\n");
            printtree(root);
            printf("\n");
        }

        count++;
        
    }

	return EXIT_SUCCESS;
}

Ausführungsergebnis

stdin.txt(Irgendein)


Iabc
Sabc
Dabc

stdout.txt(Irgendein)


Befehl Iabc:Abc einfügen
       Dabc:Abc entfernen
       Sabc:Suche nach abc
Wie ist die Reihenfolge? Hat sich registriert

 abc

Wie ist die Reihenfolge?
Success #stdin #stdout 0s 4368KB
Befehl Iabc:Abc einfügen
       Dabc:Abc entfernen
       Sabc:Suche nach abc
Wie ist die Reihenfolge? nicht registriert
Wie ist die Reihenfolge?
Success #stdin #stdout 0s 4516KB
Befehl Iabc:Abc einfügen
       Dabc:Abc entfernen
       Sabc:Suche nach abc
Wie ist die Reihenfolge? Nicht gelöscht
Wie ist die Reihenfolge?

Impressionen

Recommended Posts

[C-Sprachalgorithmus] binärer Suchbaum
C-Sprache ALDS1_4_B Binäre Suche
Algorithmus in Python (ABC 146 C Dichotomie
[C-Sprachalgorithmus] Endianness
[C-Sprachalgorithmus] Blockbewegung
Binäre Suche in Python / C ++
C-Sprache ALDS1_4_A Lineare Suche
Visualisieren Sie die binäre Suche
String-Suchalgorithmus
ABC146C (Dichotomie)
[C-Sprachalgorithmus] Postfix-Notation (oder umgekehrte polnische Notation)
Dichotomie mit Python
C-Sprache ALDS1_3_B Warteschlange
Memo zur Bisektionssuche (python2.7)
[Python] Bisection-Suche ABC155D
Dichotomie mit Python
Dichotomie mit Python 3
Ein 2-minütiger Suchbaum ist ein Verwandter der Hash-Kette !?
Binäre Suche in Python
Einbettung der Maschinensprache in die Sprache C.
Heap-Sortierung in C-Sprache
Suchalgorithmus mit word2vec [Python]
[C Sprache] readdir () vs readdir_r ()
Minimaler Gesamtflächenbaum in C #