Recherche en table

5.2 Recherche en table

Une table contient des informations sur certaines clefs. Dans l'exemple suivant, les clefs sont des abréviations et l'information est constituée par le sens des ces abréviations. L'instruction char bar[32]="foo" définit une variable bar et on lui affecte la chaîne de caractères ``foo''. On peut donc définir deux tableaux :

#define N 100

char *ABR[N] ;
char *EXP[N] ;

int NbTotal = 13 ;

ABR[1]="ANSI";
EXP[1]="American National Standards Institute";
ABR[2]="ASCII";
EXP[2]="American Standard Code for Information Interchange";
ABR[3]="BIOS";
EXP[3]="Basic Input/Output System";
ABR[4]="GRUB";
EXP[4]="Grand Unified Bootloader";
ABR[5]="IDE";
EXP[5]="Integrated Drive Electronics";
ABR[6]="ISA";
EXP[6]="Instruction Set Architecture";
ABR[7]="ISO";
EXP[7]="International Standards Organization";
ABR[8]="OS";
EXP[8]="Operating System";
ABR[9]="PCI";
EXP[9]="Peripheral Component Interconnect";
ABR[10]="ROM";
EXP[10]="Read Only Memory";
ABR[11]="RTFM";
EXP[11]="Read The F... Manuel";
ABR[12]="SCSI";
EXP[12]="Small Computer System Interface";
ABR[13]="VLSI";
EXP[13]="Very Large Scale Integration";

Une table peut être construite à partir d'une liste ou d'un arbre. Pour l'instant, nous allons utiliser deux tableaux --- ABR et EXP --- indicés en parallèle pour coder notre table : l'abréviation de EXP[i] étant ABR[i].

La table ci-dessus peut contenir 100 éléments au maximum mais, on n'utilise que nbtotal cellules. On ne gère pas ici la taille courante de la table dans notre exemple par une variable car on se propose d'utiliser une sentinelle en bout de table qui indique qu'après elle, il n'y a plus de cellule affectée.

5.2.1 Recherche séquentielle

La première méthode pour rechercher le sens d'une abréviation est d'examiner successivement tous les éléments de la table. Il s'agit d'une recherche séquentielle ; cette recherche est aussi qualifiée de linéaire parce que le nombre d'opérations nécessaires est linéaire dans la taille de la table.

Exercice 5.4 --- Recherche séquentielle.

Écrivez une procédure basée sur la recherche séquentielle qui affiche le sens d'une abréviation saisie au clavier tant que l'utilisateur le demande.

Il faut noter que

si la variable chaine est définit par l'instruction char *chaine, la fonction scanf s'utilise par l'appel scanf("%s",chaine) (ce point sera éclairci dans la section 7) ;
l'égalité de deux chaînes de caractères se teste à l'aide de la fonction strcmp. Cette fonction est définie dans la librairie string.h ; elle prend en argument deux chaînes de caractères et retourne 0 si elles sont identiques, une valeur positive si le premier argument est plus grand que le second et une valeur négative dans le cas contraire. N'hésitez pas à utiliser le manuel d'unix man strcmp à partir de votre shell.
la conditionnel if considère qu'une expression est fausse si elle retourne 0. La boucle for exécute les instructions spécifiées tant que la seconde expression est fausse ;

Insertion d'éléments

Si on utilise une recherche séquentielle dans une table, on peut rajouter des éléments nouveaux en bout de table et produire une erreur s'il n'y a plus de place. Afin que cette opération puisse être réalisée en temps constant (ne pas nécessiter de parcours dans la table), on se doit d'utiliser une variable qui indique la dernière cellule affectée.

Exercice 5.5 --- Recherche séquentielle avec insertion d'éléments.

Modifiez votre programme afin que l'utilisateur puisse insérer ses propres données dans la table.

5.2.2 Recherche dichotomique

Supposons que la table soit triée en ordre alphabétique. On peut alors utiliser une recherche dichotomique pour explorer notre table i.e. utiliser la méthode suivante :

on compare notre clé à une abréviation qui se trouve au milieu de la table des abréviations ;
si c'est la même, on retourne son sens tiré de la table des expressions ;
sinon, on recommence l'étape 1 sur la première (resp. seconde) moitié de table si le nom recherché est plus petit (resp. plus grand) que le nom rangé au milieu de la table.

Exercice 5.6 --- Recherche dichotomique.

Écrivez une procédure basée sur la recherche dichotomique qui affiche le sens d'une abréviation saisie au clavier tant que l'utilisateur le demande.

Remarques sur la complexité

Notons u_n le nombre de comparaisons nécessaires pour une table de taille n. On a u₁=1 et u_n=1+u_n/2. Le nombre u_n est logarithmique dans la taille n de la table. C'est donc une amélioration par rapport à la recherche séquentielle ;
Si on veut insérer un nouvel élément dans la table afin d'effectuer une recherche dichotomique, cette dernière devant être ordonnée, il nous faut trouver sa place dans la table et déplacer tous les éléments plus grand. On retombe ainsi sur une complexité linéaire en la taille de la table.

Pour tout commentaire : Alexandre Sedoglavic.