:: Enseignements :: ESIPE :: E3INFO :: 2021-2022 :: Algorithmique ::

Manipulation de tableaux

Dans ce TP, on implante les opérations d'insertion et de recherche dans un tableau non trié et dans un tableau trié.

Exercice 1 - Insertion et recherche dans un tableau

On souhaite écrire des fonctions d'insertion et de recherche d'un élément dans un tableau.

Commencer par récupérer l'archive Base.zip et extraire les fichiers dans votre répertoire de travail. Le fichier arrays.h contient des en-têtes de quatre fonctions qui sont censées effectuer des insertions et des recherches dans des tableaux triés et non triés. Vous écrivez le code de ces fonctions dans le fichier arrays.c.
Le fichier arrays_ref.o contient des fonctions de référence avec lesquelles vous pouvez tester la correction et la performance de vos fonctions. La commande make permet de compiler le programme bench qui effectue les tests :
```
$ make
gcc -c -o bench_main.o bench_main.c -Wall -ansi
gcc -c -o benchmark.o benchmark.c -Wall -ansi
gcc -c -o arrays.o arrays.c -Wall -ansi
gcc -o bench bench_main.o benchmark.o arrays_ref.o arrays.o
$ ./bench -h
```
Si vous voulez écrire une autre fonction main qui utilise les fonctions de référence et les autres fonctions dans benchmark.h, vous pouvez le faire dans un fichier mon_prog.c et le compiler avec :
```
$ gcc -o mon_prog mon_prog.c benchmark.o arrays_ref.o arrays.o
```
Lancer ./bench -a et constater que les fonctions insert_unsorted, find_unsorted, insert_sorted et find_sorted ne fonctionnent pas correctement.
Écrire les fonctions insert_unsorted et find_unsorted pour un tableau non trié. Vérifier avec ./bench -u que vos fonctions sont correctes. Le comportement attendu de ces fonctions est décrit ci-dessous :
- void insert_unsorted(int t[], int *size, int elt);
  Insertion dans un tableau non trié. On insère l'élément elt à la fin du tableau, puis on incrémente *size de 1.
- int find_unsorted(int t[], int size, int elt);
  Recherche dans un tableau non trié. On parcourt le tableau tant qu'il y a des éléments et que l'on n'a pas trouvé la valeur elt. La fonction renvoie 1 si l'élément est présent dans le tableau et 0 sinon.
Ensuite, écrire les fonctions pour un tableau trié et les vérifier avec ./bench -s.
- void insert_sorted(int t[], int *size, int elt);
  Insertion dans un tableau trié (en ordre croissant). On décale tous les éléments de la fin du tableau jusqu'à la position où on veut insérer l'élément elt, on l'insère, puis on incrémente *size de 1.
- int find_sorted(int t[], int size, int elt);
  Recherche dans un tableau trié (en ordre croissant). La fonction renvoie 1 si l'élément elt est présent dans le tableau et 0 sinon. On effectue une recherche par dichotomie dans une partie triée, commençant à l'indice lo=0 jusqu'à l'indice hi=size-1.
  - Si la partie est vide, l'élément n'est pas présent; sinon, on détermine l'élément à l'indice mid, au milieu de la partie.
  - Si cet élément est celui recherché, c'est fini: on l'a trouvé.
  - Si l'élément à l'indice mid est supérieur à l'élément recherché, on poursuit la recherche dans la partie qui se trouve avant l'indice mid.
  - Si l'élément à l'indice mid est inférieur à l'élément recherché, on poursuit la recherche dans la partie qui se trouve après l'indice mid.
Finalement, lancer ./bench -a et comparer les temps d'exécution entre la version triée et la version non triée.
Vérifier que les temps d'exécution sont cohérents avec les complexités des fonctions. Y a-t-il un cas où l'insertion puis la recherche est significamment plus rapide dans un tableau non trié ? Pourquoi ?

Exercice 2 - Pour ceux qui s'ennuient

Sur la base de ce petit programme ci-dessous qui affiche à l'écran tous les mots d'un fichier dont le nom est passé en argument, on souhaite utiliser nos fonctions sur les tableaux pour les trois usages suivants:

obtenir un tableau dont chaque élément correspond à la longueur d'un mot du texte.
utiliser ce tableau pour trouver la longueur médiane des mots du texte correspondant à ce fichier (la valeur telle qu'il y a autant de mots sont de longueur inférieure que de mots de longueur supérieure).
utiliser ce tableau pour afficher, pour chaque longueur de mot, combien de mots dans le texte ont cette longueur.

word.c

Vous pourrez tester avec le fichier texte VictorHugo_LesMiserables-II-Cosette.txt ou avec d'autres textes que vous pourrez trouver sur le site du Projet Gutenberg.