Précédent Remonter Suivant

8.1  Listes chaînées

Une liste chaînée est constituée de cellules d'un type struct contenant : On peut ainsi définir une cellule par le type suivant : 
typedef struct cellule{
  struct cellule *suivante ;
  type_1 el_1 ;
    .... 
  type_n el_n ;
} cellule ;
Ceci fait, il nous reste à définir les manipulations élémentaires associée à une liste ; il nous faut des fonctions qui permettent : Pour créer une cellule, il faut allouer de l'espace mémoire : 
cellule * CreerCellule(type_1 data_1, ... type_n data_n){

  cellule * cell = (cellule *) malloc(sizeof(cellule)) ;

  cell->suivante = NULL   ; /* la cellule nouvellement cr\'ee
                             * ne pointe sur rien             */
  cell->el_1     = data_1 ;
     ....
  cell->el_n     = data_n ;

  return cell ;
}
Cette fonction crée (et remplit) une cellule. Remarquez que l'espace mémoire alloué grâce à la fonction malloc n'est pas détruit à la fin de la fonction CreerCellule contrairement à l'ensemble des variables et arguments de cette fonctions. Pour éviter d'encombrer la mémoire, il nous faut disposer d'une fonction permettant de détruire une cellule. Pour ce faire, on utilise la fonction free de la librairie standrard : 
void DetruireCellule( cellule * cell) {
  free( (void *) cell) ;
}
Pour insérer une cellule dans une liste chaînée après la cellule cell_courante, il suffit d'utiliser le code : 
void InsererCellule( cellule * cell_a_inserer, 
                     cellule * cell_courante){
  cell_a_inserer -> suivante = cell_courante -> suivante ;
  cell_courante -> suivante = cell_a_inserer ;
}
De même, pour extraire une cellule après une cellule (ici qualifiée de mère), on peut utiliser le code : 
cellule * ExtraireCellule (cellule * cell_mere){
  cellule * tmp ;
  tmp = cell_mere->suivante ;
  cell_mere -> suivante = tmp -> suivante ;
  return tmp ;
}



Exercice 8.0 --- Manipulations élémentaires.


Construire un crible d'Érathostène à l'aide d'une liste chaînée qui au départ stockera l'ensemble des nombres inférieurs à un entier saisi au clavier.

Après une étape de construction, il faudra considérer successivement les éléments de la liste et supprimer les multiples.

Pour finir, l'ensemble des nombres premiers est afficher à l'écran.
Impératif :
on prendra soin de détruire les cellules de la liste chaînée associées à des nombres composés.







Exercice 8.1 --- Distribution de fréquence des lettres d'un texte.


Étant donnée un texte codé suivant un standard ISO (dans la suite ce sera le standard 8859 cf. man iso_8859_1), on se propose dans cet exercice de déterminer la fréquences des caractères le composant.

Par exemple, si l'on saisi au clavier (azerty) la phrase :
Longtemps, je me suis couché de bonne heure.

et qu'on la stocke dans un fichier texte, on obtient le fichier composé d'entiers codés sur 8 bits :
76 111 110 103 116 101 109 112 115 32 106
101 32 109 101 32 115 117 105 115 32 99
111 117 99 104 233 32 100 101 32 98 111
110 110 101 32 104 101 117 114 101 46
Pour faire l'analyse de fréquence des lettres de ce texte, on peut procéder comme suit :
Construisez un programme prenant en entrée deux noms de fichiers foo.txt et bar.res ; ce programme calcule la distribution de fréquence du texte contenu dans foo.txt et sauve le résultat dans le fichier bar.res.

Indications :
vous pouvez utilisez le manuel unix comme texte (man gcc > foo.txt) ou télécharger un texte depuis la toile.







Exercice 8.2 --- Calcul de l'entropie d'un texte.


Soit un alphabet S munie d'une variable aléatoire X de probabilité de réalisation P(X=s). Dans notre cas, pour une lettre s d'un texte, la probabilité P(X=s) n'est que la fréquence d'apparition de cette lettre. On appelle quantité d'information du symbole s de S le nombre :
I(s) = -
logP(X=s)
log2
.
Ainsi, plus l'utilisation d'une lettre est rare, plus la quantité d'information associée est grande.


Définition 1  [C.E. Shannon 1940]   --- On appelle entropie de la source S munie d'une variable aléatoire X et de la probabilité de réalisation P la quantité moyenne d'information par symbole :
H(X) =
 
å
sÎS
P(X=s)I(s).


En utilisant la notion d'entropie de source, on fait l'hypothèse que toutes les lettres d'un texte sont indépendantes les unes des autres i.e. il est aussi probable d'avoir un e après un l qu'un z.


Ce n'est généralement pas le cas : l'occurrence une lettre dépend fortement des lettres voisines. Pour estimer l'entropie dans ce cas, on utilise la fréquence --- non plus des lettres de S --- mais des groupes de lettres m1... md avec mi dans S.

Comme une lettres dépend peu des lettres éloignées : la suite H(m1··· md)/d converge rapidement lorsque d tends vers l'infini.
Définition 2   --- L'entropie d'un texte est la limite
 
lim
d® ¥
H(m1··· md)
d
.
Questions :
  1. Modifier votre programme afin de calculer l'entropie de source d'un texte (la source étant dans ce cas l'ensemble des lettres distinctes composant le texte).
  2. Modifier votre programme afin de calculer l'entropie d'un texte.
Indications :
On dispose d'une fonction log définie dans math.h. Pour l'utiliser, il faut indiquer au compilateur la librairie correspondante par l'instruction gcc foo.c -lm.

Pour calculer l'entropie d'un texte, il est intéressant de modifier le typage des cellules de notre liste chaînée : on peut remplacer le caractère par une chaîne de caractères et profiter de l'ordre lexicographique induit par la commande stcmp.

Remarque :
L'implantation que nous venons de terminer étant naive, sa complexité --- i.e. le nombre d'opérations nécessaires --- est grande : elle est quadratique dans la taille de l'entrée. En utilisant une table de hachage, on peut effectuer la même tâche avec une complexité linéaire en la taille de l'entrée.






Pour tout commentaire : Alexandre Sedoglavic.
Précédent Remonter Suivant