Recherche séquentielle dans une table

    

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.