L'implémentation la plus simple d'une table se fait à l'aide d'un tableau, et l'algorithme de recherche le plus élémentaire est la recherche séquentielle ; on parcourt le tableau jusqu'à ce qu'un objet de clé donnée soit trouvé ou bien que la fin du tableau soit atteinte :
data table[N]; data empty_data = {""} ; data search(const char s[]) { int i; for (i=0; i<N; i++) { if (strcmp(table[i].key,s) == 0) { return table[i]; } return empty_data; }
On notera que le << return table[i]; >> placé dans la boucle permet de s'en échapper (c'est-à-dire de ne pas exécuter les itérations suivantes) en retournant immédiatement une valeur. Si l'on souhaitait s'échapper de la boucle sans retourner immédiatement, on placerait un << break; >> à la méme place. On peut réécrire cette fonction ainsi :
data search(const char s[]) { int i; for (i=0; i<N; i++) { if (strcmp(table[i].key,s) == 0) { break; } if (i<N) { return table[i]; } else { return empty_data; } }
La fonction strcmp de comparaison de deux chaînes, déclarée dans le fichier string.h retourne 0 si ses deux arguments sont égaux, un entier <0 (resp. >0) si son premier argument est le plus petit (resp. le plus grand) pour l'ordre lexicographique ; à cause de ces valeurs de retour, cette fonction se comporte comme un test d'inégalité, à la manière de !=, et non d'égalité. Compte tenu de l'interprétation logique des entiers, on peut simplifier le test
if (strcmp(table[i].key,s) == 0)
en
if (!strcmp(table[i].key,s))
La définition de cette fonction est facile :
int strcmp(const char s[], const char t[]) { int i; for (i=0; s[i] == t[i]; i++) { if (s[i] == '\0') { /* s et t sont egales */ return 0; } } return s[i] - t[i]; /* la différence des 2 premiers caractères différents */ }
La technique bien connue de la sentinelle permet de faire l'économie, à chaque itération, du test i<N, en réservant une position à la fin du tableau pour placer la chaîne cherchée :
data table[N+1]; data search(const char s[]) { int i = 0; strcpy(table[N].key, s); while (strcmp(table[i].key,s) != 0) { i++; } if (i<N) { return table[i]; } else { return empty_data; } }
Le nombre maximum de comparaisons effectuées par ce dernier algorithme est de N (quand la clé cherchée n'est pas trouvée) ; en moyenne, il procède à N/2 comparaisons. Cela est très mauvais, et on sait faire beaucoup mieux.