Neuestes Algorithmus-Wörterbuch in C-Sprache (geschrieben von Haruhiko Okumura / 1991, erste Ausgabe der technischen Überprüfungsfirma: 206 Seiten)
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.
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;
}
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?
Recommended Posts