Obligement - L'Amiga au maximum

Samedi 16 novembre 2019 - 21:54  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Quizz
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Trucs et astuces
 · Articles divers

 · Articles in english
 · Articles en d'autres langues


Twitter

Suivez-nous sur Twitter




Liste des jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Galeries

 · Menu des galeries

 · BD d'Amiga Spécial
 · Caricatures Dudai
 · Caricatures Jet d'ail
 · Diagrammes de Jay Miner
 · Images insolites
 · Fin de jeux (de A à E)
 · Fin de Jeux (de F à O)
 · Fin de jeux (de P à Z)
 · Galerie de Mike Dafunk
 · Logos d'Obligement
 · Systèmes d'exploitation
 · Trombinoscope Alchimie 7
 · Vidéos


Téléchargement

 · Documents
 · Jeux
 · Logiciels
 · Magazines
 · Divers


Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Logiciels
 · Jeux
 · Scène démo
 · Divers


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


A Propos

A propos d'Obligement

A Propos


Contact

David Brunet

Courriel

 


En pratique : Algorithmes et structures de données - Les arbres binaires
(Article écrit par Lucien Turski-Marcon et Bruno Bailluet et extrait d'Amiga News Tech - août 1992)


L'arbre binaire est une structure de données très utilisée en informatique. Très simple à mettre en oeuvre, il permet une gestion efficace des grosses masses de données et est à ce titre souvent utilisé dans les SGBD.

Passons tout de suite au principe du programme d'exemple. Chaque décision d'ajout de nouvelles données dans le fichier principal entraîne deux actions : tout d'abord, la création d'un noeud dans l'arbre comportant la clé et la mémorisation de la position actuelle du pointeur de fichier (l'arbre est trié, ce qui autorise une recherche très rapide et une reconstruction facile). En second lieu, les données elles-mêmes sont ajoutées à la fin du fichier data (dans notre exemple, ESSALDAT).

Pour résumer, nous nous trouvons à ce stade avec un index en mémoire qui nous permet de nous positionner sur le fichier de données quand nous le désirons.

Intervient alors la phase de sauvegarde de l'index. Pour cela, il suffit de parcourir l'arbre de la même manière que pendant la phase de création d'un noeud. De ce fait, l'ordre de création des noeuds est respecté. La clé et la position sont sauvegardées dans un fichier séquentiel puisque, je le répète, l'ordre est conservé. Pour le chargement, rien de plus simple, on lit les données séquentiellement et on appelle la fonction de création.

Désormais, plus rien ne vous empêche de vous lancer dans la réécriture de SuperBase IV !

/* compile le plus simplement du monde : LC -L */
#include <stdio.h>

struct Info 
{
    int indice ;
    char nom[20] ;
} ;

/* Structure d'un noeud de l'arbre. */
struct Noeud 
{
    struct Noeud *gauche ;
    struct Info  info   ;
    struct Noeud *droit ;
} ;

typedef struct Noeud ARBRE ;

/* Declaration globale de la racine et de l'element courant. */
ARBRE *racine = NULL, *elem = NULL ;

/* Position des infos dans le fichier de donnees */
/* indispensable pour le seek.                   */
int position ;

/* Buffer de lecture ecriture des donnes. */
char buffer[50] ;

/* Pointeurs pour le fichier d'index et de donnees. */
FILE *index, *fichier ;

/* Prototype des fonctions. */
void Cree        (ARBRE *, ARBRE *) ;
void Liste       (ARBRE *) ;
void Cherche     (char *, ARBRE *) ;
void Sauve_Tree  (ARBRE *) ;
void Charge_Tree (void) ;

main()
{
/* Initialisation de la variable du menu. */
    int choix = 5 ;
    ARBRE *nouveau ;
    char nom[20], prenom[20] ;

/* Ouverture du fichier de donnees en consultation, en ajout. */
    fichier = fopen ("ESSAI.DAT","a+") ;
    if (! fichier)
    {
        puts ("Ouverture du fichier de donnees impossible") ;
        exit (5) ;
    }

/* Positionnement en fin de fichier. */
    fseek (fichier,0,2) ;

/* Recuperation de la taille du fichier. */
    position = ftell (fichier) ;

    printf ("pos : %d\n",position) ;

/* Ouverture du fichier d'index en lecture. */
    index = fopen ("ESSAI.IDX", "a+")  ;
    if (! index)
    {
         puts ("Ouverture fichier index impossible") ;
         exit (5) ;
    }

/* Reconstruction en memoire de l'arbre d'index a partir */
/* du fichier ESSAI.IDX. */
    Charge_Tree () ;
    fclose (index) ;

/* Menu principal. */
    while (choix != 0)
    {
        puts ("1. Ajouter Un Noeud") ;
        puts ("2. Lister  L' Arbre") ;
        puts ("3. Lister  Un Noeud") ;
        printf ("\n\n") ;
        puts ("0. Sortir et Sauver INDEX") ;
        printf ("\n\nVotre choix : ") ;
        scanf ("%d",&choix) ;

        switch (choix)
        {
            case 1 :
                printf ("\nEntrez le nom : ") ;
                scanf ("%s",nom) ;
                printf ("Entrez le prenom : ") ;
                scanf ("%s",prenom) ;

/* La position a "seeker" dans le fichier de donnees  */
/* afin d'y recuperer rapidement les informations est */
/* recuperee juste en dessous.                        */
                position = ftell (fichier) ;
                printf ("pos : %d\n",position) ;

/* Si premier noeud, alors il s'agit de la racine. */
                if (! racine)
                {
                    racine = (ARBRE *) malloc (sizeof (ARBRE)) ;
                    racine -> gauche      = NULL ;
                    racine -> droit       = NULL ;
                    racine -> info.indice = position ;

                    strcpy (racine -> info.nom, nom) ;
                }
                else
                {
                    nouveau = (ARBRE *) malloc (sizeof (ARBRE)) ;
                    nouveau -> gauche      = NULL ;
                    nouveau -> droit       = NULL ;
                    nouveau -> info.indice = position ;

                    strcpy (nouveau -> info.nom,nom) ;
                    Cree (nouveau, racine) ;
                }

/* Ecriture dans le fichier sequentiel des donnees avec un */
/* format. Ce dernier permet de visualiser proprement les  */
/* donnees par un simple type.                             */

                fprintf (fichier,"%s %s\n", nom, prenom) ;
                break ;

            case 2 :
                Liste (racine) ;
                fseek (fichier, 0, 2) ;

/* Cette position doit etre constemment tenue a jour */
/* sous peine d'ecrasement des donnees car le seek   */
/* utilise cette valeur de positionnement            */
                position = ftell (fichier) ;
                break ;

            case 3 :
                printf ("Entrez le nom du noeud : ") ;
                scanf ("%s", nom) ;
                Cherche (nom, racine) ;

                if (! elem)
                    puts ("Element inexistant")  ;
                else
                {

/* Le plus interessant. Apres avoir retrouve le noeud, on */
/* recupere la place dans le noeud, positionnement et     */ 
/* extraction des donnees.                                */
                    fseek (fichier, elem -> info.indice, 0) ;
                    fgets (buffer, 50, fichier) ;

                    printf ("%s\n",buffer) ;

/* On se remet en fin au cas ou il y aurait un ajout. */
                    fseek (fichier, 0, 2) ;
                    position = ftell(fichier) ;
                }
                break  ;

            default :
                choix = 0  ;
                break  ;

        }
    }

/* Fermeture du fichier de donnees */
    fclose (fichier)  ;

/* Reouverture du fichier index, afin de le mettre a jour */
    index = fopen ("ESSAI.IDX", "w")  ;
    if (! index)
    {
        puts ("Ouverture fichier index impossible") ;
        exit (5) ;
    }

/* Sauvegarde complete du nouvel arbre dans le fichier index */
    Sauve_Tree (racine)  ;

/* Fermeture du fichier d'index. */
    fclose (index)  ;
    exit (0)  ;
}

/* Fonction de creation d'un noeud dans l'arbre. */
void Cree (ARBRE *tree, ARBRE *base)
{

/* Si le nom du nouveau noeud est superieur a la racine   */
/* ou au noeud courant, on descend a droite sauf si c'est */
/* une feuille. Dans ce cas on ajoute le nouveau noeud    */
	if (strcmp(tree -> info.nom, base -> info.nom) >= 0)
        if (base -> droit == NULL)
            base -> droit = tree  ;
        else
            Cree (tree, base -> droit)  ;

/* Meme chose, mais cette fois-ci on descend a gauche */           
    if (strcmp(tree -> info.nom, base -> info.nom) < 0)
        if (base -> gauche == NULL)
            base -> gauche = tree  ;
        else
            Cree (tree, base -> gauche)  ;
}

/* Fonction d'affichage du contenu du fichier de donnees */
/* a partir du parcours de l'arbre.                      */
void Liste (ARBRE *tree)
{
    if (tree)
    {
/* Positionnement dans le fichier de donnees */
        fseek (fichier, tree -> info.indice, 0) ;

/* Recuperation des donnees. */
        fgets (buffer, 50, fichier) ;

/* Affichage des donnees. */
        printf ("%s",buffer) ;

/* Et on repart a gauche. */
        Liste (tree -> gauche)  ;        
        Liste (tree -> droit)  ;
    }
}

/* Fonction generique de recherche d'un noeud dans un arbre. */
/* A conserver et a reutiliser.                              */
void Cherche (char *chaine, ARBRE *tree)
{
    if (tree)
    {
        if (strcmp(chaine, tree -> info.nom) > 0)
            Cherche(chaine, tree -> droit)  ;

        if (strcmp(chaine, tree -> info.nom) < 0)
            Cherche(chaine, tree -> gauche)  ;

        if (strcmp(chaine, tree -> info.nom) == 0)
            elem = tree  ;
    }
    else
        elem = NULL  ;
}

/* Fonction de sauvegarde de l'arbre dans l'index. */
void Sauve_Tree (ARBRE *tree)
{
    struct Info temp  ;

    if (tree)
    {
        temp.indice = tree -> info.indice  ;
        strcpy (temp.nom, tree -> info.nom)  ;

/* A ce stade nous sauvegardons toute la structure info qui */
/* represente notre cle. La vrai cle est en fait le nom et  */
/* l'indice la position des donnees l'accompagnant. Rien ne */
/* vous empeche d'agrandir les datas ou la cle.             */
        fwrite (&temp, sizeof(struct Info), 1, index)  ;
        Sauve_Tree(tree -> gauche)  ;
        Sauve_Tree(tree -> droit)  ;
    }
}


/* Fonction de reconstruction de l'arbre a partir de l'index */
void Charge_Tree (void)
{
    ARBRE *temp ;
    struct Info tempo ;

    temp = (ARBRE *) malloc (sizeof(ARBRE)) ;
    fread (&tempo, sizeof (tempo), 1, index) ;

/* Creation de la racine. */
    if (! racine)
        racine = (ARBRE *) malloc (sizeof (ARBRE))  ;

    racine -> gauche = NULL  ;
    racine -> droit = NULL  ;
    racine -> info.indice = tempo.indice  ;
    strcpy (racine -> info.nom, tempo.nom)  ;

/* Lecture sequentielle du fichier index. */ 
    while (fread(&tempo, sizeof(tempo), 1, index))
    {
        temp -> gauche = NULL ;
        temp -> droit = NULL ;
        temp -> info.indice = tempo.indice ;
        strcpy (temp -> info.nom, tempo.nom)  ;

/* Creation du nouveau noeud. */
        Cree (temp, racine)  ;
        temp = (ARBRE *) malloc (sizeof(ARBRE))  ;
    }
 
/* Liberation du dernier pointeur sur ARBRE alloue en trop. */
    free (temp)  ;
}


[Retour en haut] / [Retour aux articles] [Article précédent]