Dernier dictionnaire d'algorithmes en langage C (écrit par Haruhiko Okumura / Revue technique de la première édition 1991: 206 pages)
Cité à partir des matériaux de référence ci-dessous
Un arbre bifurqué utilisé pour la recherche. Chaque nœud a des données et deux pointeurs, toutes les données des descendants connectés par le pointeur gauche gauche sont plus petites que vous, et toutes les données des descendants connectés par le pointeur droit droit sont plus grandes que vous. Une recherche dans l'arborescence de recherche de 2 minutes commence à la racine et suit le pointeur gauche ou droit, selon que l'objet que vous recherchez est plus petit ou plus grand que le nœud. Un arbre bifurqué parfaitement équilibré peut être comparé n fois pour trouver celui souhaité de 2 à la puissance n-1.
postfix.c
//Arbre de recherche binaire de 2 minutes
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Déclaration de type de la clé utilisée pour la recherche
typedef char keytype[21];
//Déclaration de type d'un nœud bifurqué
typedef struct node {
struct node *left, *right; //Pointeurs vers les nœuds enfants gauche et droit
keytype key; //Clé de recherche
} *nodeptr; //Pointeur pointant vers un nœud
struct node nil; //Nœud représentant la fin de l'arbre
nodeptr root = &nil; //Pointeur pointant vers la racine
//Insérer dans un arbre(enregistrement)une fonction
nodeptr insert(keytype insertkey){
int cmp;
nodeptr *p; //Pointeur pointant vers un nœud
nodeptr q; //Entité de nœud
strncpy(nil.key,insertkey,sizeof(keytype)); //Copiez la clé d'argument dans la clé du gardien
p = &root; //Attribuer un pointeur racine au pointeur de variable interne
//Boucle jusqu'à ce que les clés correspondent
while((cmp = strncmp(insertkey, (*p)->key, sizeof(keytype))) != 0)
{
//Si la clé d'insertion est inférieure à la clé du nœud pointé par le pointeur, déplacez-vous vers le plus petit nœud sur la gauche
//Si la clé d'insertion est supérieure à la clé du nœud pointé par le pointeur, déplacez-vous vers le nœud le plus grand sur la droite
if(cmp < 0){
//Déplacez le pointeur vers la gauche
p = &((*p)->left);
}
else{
//Déplacez le pointeur vers la droite
p = &((*p)->right);
}
}
//Si la clé est déjà enregistrée
if(*p != &nil){
return NULL;
}
//Allouer une zone de mémoire pour le nœud
if((q = malloc(sizeof(*q))) == NULL){
printf("insert:Impossible de sécuriser la zone de mémoire en raison d'une mémoire insuffisante.\n");
exit(EXIT_FAILURE);
}
//Copiez la clé du nœud
strncpy(q->key, insertkey, sizeof(keytype));
q->left = &nil;
q->right = *p;
*p = q;
//Renvoie le nœud enregistré
return q;
}
//Supprimer la fonction
//Renvoie 0 s'il peut être supprimé, 1 s'il échoue
int delete(keytype deletekey){
int cmp;
nodeptr *p, *q;
nodeptr r, s;
strncpy(nil.key, deletekey, sizeof(keytype)); //Gardien
p = &root;
//Boucle jusqu'à ce que les clés correspondent
while((cmp = strncmp(deletekey, (*p)->key, sizeof(keytype))) != 0)
{
//Si la clé d'insertion est inférieure à la clé du nœud pointé par le pointeur, déplacez-vous vers le plus petit nœud sur la gauche
//Si la clé d'insertion est supérieure à la clé du nœud pointé par le pointeur, déplacez-vous vers le nœud le plus grand sur la droite
if(cmp < 0){
p = &((*p)->left);
}
else{
p = &((*p)->right);
}
}
//Si la clé n'est pas trouvée
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;
}
//Libérez de l'espace
free(r);
return 0;
}
//Fonction de recherche
//Si la clé est trouvée, elle renvoie un pointeur vers le nœud qui contient la clé.
//Renvoie NULL si non trouvé
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){
//Si trouvé
return p;
}else{
//Si non trouvé
return NULL;
}
}
void printtree(nodeptr p){
static int depth = 0;
//Afficher le nœud à gauche
if((p->left) != &nil){
depth++;
//Appel récursif
printtree(p->left);
depth--;
}
//Afficher le nœud reçu par l'argument
printf("%*c%s\n", 5*depth, ' ', p->key);
//Afficher le nœud à droite
if(p->right != &nil){
depth++;
//Appel récursif
printtree(p->right);
depth--;
}
}
int main(void) {
char buf[22];
short count;
printf( "Commande Iabc:Insérer abc\n"
" Dabc:Supprimer abc\n"
" Sabc:Rechercher abc\n");
for(;;){
printf("Quelle est la commande?");
//Recevoir les données de l'entrée standard pour la taille buf
if(scanf("%21s%*[^\n]", buf) != 1){
break;
}
switch(buf[0]){
//Insérer un processus
case 'I': case'i':
//Insérer une fonction
if(insert(&buf[1])){
printf("%21s%*[^\n]: S'est enregistré\n",buf);
}else{
printf("%21s%*[^\n]: Enregistré\n",buf);
}
break;
//Supprimer le processus
case 'D': case 'd':
//Supprimer la fonction
if(delete(&buf[1])){
printf("%21s%*[^\n]: Non supprimé\n",buf);
}else{
printf("%21s%*[^\n]: Il a été supprimé\n",buf);
}
break;
//Processus de recherche
case 'S': case 's':
//Supprimer la fonction
if(search(&buf[1])){
printf("%21s%*[^\n]: Enregistré\n",buf);
}else{
printf("%21s%*[^\n]:non enregistré\n",buf);
}
break;
default:
printf("je peux utiliser, D,Seulement S\n");
break;
}
if(root != &nil){
printf("\n");
printtree(root);
printf("\n");
}
count++;
}
return EXIT_SUCCESS;
}
stdin.txt(Tout)
Iabc
Sabc
Dabc
stdout.txt(Tout)
Commande Iabc:Insérer abc
Dabc:Supprimer abc
Sabc:Rechercher abc
Quelle est la commande? S'est inscrit
abc
Quelle est la commande?
Success #stdin #stdout 0s 4368KB
Commande Iabc:Insérer abc
Dabc:Supprimer abc
Sabc:Rechercher abc
Quelle est la commande? non enregistré
Quelle est la commande?
Success #stdin #stdout 0s 4516KB
Commande Iabc:Insérer abc
Dabc:Supprimer abc
Sabc:Rechercher abc
Quelle est la commande? Non supprimé
Quelle est la commande?
Recommended Posts