Slauncha

Supposons que nous voulions traiter le problème général consistant à compter le nombre d'occurrences de tous les mots lus en entrée et de les trier.

Puisque la liste de mots n'est pas connue à l'avance, il n'est pas pratique de la trier et d'utiliser une recherche dichotomique.

Cependant, nous ne pouvons pas non plus effectuer une recherche séquentielle à l'arrivée de chaque mot pour vérifier si on l'a déjà rencontré ; le temps d'exécution du programme serait trop long.

Comment pouvons-nous organiser les données pour faire face efficacement à liste de mots arbitraires ?

Nous allons utiliser une structure appelée arbre binaire. L'arbre contient un "nœud" pour chaque mot, chaque nœud contient :

• un pointeur sur le texte du mot
• un compte du nombre d'occurrences
• un pointeur sur le nœud fils gauche
• un pointeur sur le nœud fils droit

Aucun nœud ne peut avoir plus de deux fils ; il est possible qu'un nœud n'en ait qu'un seul, ou aucun.

On place les nœuds de telle façon que les sous-arbre gauche d'un nœud quelconque contienne uniquement des mots de valeurs lexicographique inférieur au mot de ce nœud, et le sous-arbre droit, des mots de valeurs lexicographique supérieure.

Code source du fichier : btree.c

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

#define SIZECACHE 100
#define MAXWORD 100

char cache[SIZECACHE]; /* tampon pour writeChar */
int pcache = 0; /* prochaine position
                        libre dans cache */

struct node {
    char *word;
    int cpt;
    struct node *left;
    struct node *right;
};


/* readWord : lit le mot ou le caractere suivant
    sur l'entree */
int readWord (char *word, int lim)
{
    int c, readChar(void);
    void writeChar(int);
    char *m = word;
    while (isspace(c = readChar()))
        ;
    if (c != EOF)
        *m++ = c;
    if (!isalpha(c)) {
        *m = '\0';
        return c;
    }

    for (; --lim > 0;  m++)
        if (!isalnum(*m = readChar())) {
            writeChar(*m);
            break;
        }
    *m = '\0';
    return word[0];

}

/* lit un caractere (eventuellement remis sur l'entree) */

int readChar(void)
{
    return (pcache > 0) ? cache[--pcache] : getchar();
}

/* remet c sur l'entree */
void writeChar(int c)
{
    if (pcache >= SIZECACHE)
        printf("writeChar : trop de caractere\n");
    else
        cache[pcache++] = c;
}

/* allocNode cree un noeud */
struct node *allocNode(void) {
    return (struct node *) malloc (sizeof(struct node));
}

/* copyString : copie la chaine de caractere donnee en argument
 dans un endroit sur obtenu par un appel a malloc */
char *copyString(char *s)
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 pour '\0' */
    if (p != NULL)
        strcpy (p, s);
    return p;

}

/* addTree : ajoute un noeud contenant la chaine m au niveau de p ou en dessous */
struct node *addTree(struct node *p, char *m) {
    int cond;
    if (p == NULL) {
        p = allocNode();
        p->word = copyString(m);
        p->cpt = 1;
        p->left = p->right = NULL;
    } else if ((cond = strcmp(m, p->word)) == 0) {
        p->cpt++;
    } else if (cond < 0) {
        /* mot dans le sous arbre gauche */
        p->left = addTree(p->left, m);
    } else
        /* mot dans le sous arbre droit */
        p->right = addTree(p->right, m);
    return p;
}

/* Affiche l'arbre passe en parametre */
void displayTree(struct node *p)
{
    if (p != NULL) {
        displayTree(p->left);
        printf("%4d %s\n", p->cpt, p->word);
        displayTree(p->right);
    }
}

int main()
{
    struct node *root;
    char word[MAXWORD];

    root = NULL;
    while (readWord(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
            root = addTree(root, word);
    displayTree(root);
    return 0;
}

  Exécution

$gcc btree.c -o btree
$chmod +x btree
$./btree

Le programme attends la saisie utilisateur à savoir une liste de mots. La saisie se termine en saississant EOF (ctrl+d)

un pointeur sur le texte du mot un compte du nombre 
d'occurrences un pointeur sur le noeud fils gauche
 un pointeur sur le noeud fils droit
EOF

Affichage du résultat 

1 compte
1 d
1 droit
2 du
2 fils
1 gauche
3 le
1 mot
2 noeud
1 nombre
1 occurrences
3 pointeur
3 sur
1 texte
4 un