Skip to topic | Skip to bottom
Home
Linfo
Linfo.CTPSurArbresr1.1 - 05 Dec 2004 - 08:43 - MichelBuffatopic end

Start of topic | Skip to actions

TPs langage C L3 informatique 2004/005, séance 4 ou 5

Exercice 1 : types abstraits, pointeurs, analyse des options de la ligne de commande

La structure de données Table

Nous allons définir une table d'identificateurs triée par ordre croissant dont l'implémentation est masquée pour l'utilisateur. A chaque identificateur est associé le nombre d'occurrences de celui-ci (nombre de fois ou il a été ajouté dans la table).

Pour ce faire, nous allons définir un type pointeur vers une structure C non definie. Nous allons aussi définir un ensemble de fonctions permettant la manipulation de cette table.

Le type Table sera un pointeur vers une structure C non definie. Le type t_fonction sera un pointeur vers une fonction ayant le prototype suivant :

   void  (char *elt, int nb);

On vous fournit les fichiers suivants :

  • table.h: définition du type abstrait et des fonctions le manipulant
  • table.c: programme principal créant la table, la remplissant, affichant les résultats, etc...
  • table_liste.c: une implémentation de la table sous la forme d'une liste chaînée.

Travail à faire :

  • Etudiez ces fichiers. Remarquez que nulle part dans table.c on ne voit l'implémentation de la table. L'utilisateur du "module" table (le fichier table.c) se contente d'inclure le fichier table.h. Il travaille ensuite sur une table dont il ignore tout. Est-ce un tableau, une liste, un arbre ? On s'en fiche ! Il n'a pas à "voir" le fichier table_liste.c ni celui que vous allez écrire bientôt, renfermant une autre implémentation.

  • Regardez comment est défini le type abstrait Table et le type t_fonction,
  • Remarquez qu'on autorise le passage d'une fonction pour initialiser les éléments lors d'une insertion.
  • Les fonctions "exportées" par le module table sont assez proches de celles que vous avez définies la semaine dernière dans le TP sur les listes :

   - Table creer_table();                   /* Creation d'une table vide */
   - int ajouter(Table *table, char *elt ); /* Insertion triee d'un element dans la table 
                                               si l'element est deja present dans la table, 
                                               le compteur d'occurrence est incremente */
   - void imprimer(Table table);            /* Impression triee des elements de la table */
   - void appliquer(Table table, t_fonction fonction); /* Appel d'une fonction sur chacun des 
                                                          elements de la table */
   - int rechercher(Table table, char *elt); /* Recherche du nombre d'occurrences d'un element
                                                dans une table */
   - void detruire(Table *table);           /* destruction d'une table */

  • Regardez l'implémentation de la table sous forme de liste (dans table_liste.c). Regardez comment le type Table a été concrètement défini, tout en restant caché pour l'utilisateur. A quoi sert l'appel de la fonction assert(expression) provenant de la librairie d'assertions du C (cd l'inclusion de assert.h en début de fichier). Faire man assert pour avoir la réponse.

Implementation de la table sous la forme d'un arbre binaire GRD

Vous allez maintenant implementer la table sous la forme d'un arbre binaire ordonné GaucheRacineDroite. :

  • Cette implementation se fera dans le fichier table_arbre.c (ne pas oublier d'inclure table.h).
  • Ne touchez pas à table.h !!!
  • Définissez concrètement le type correspondant au type Table, c'est la structure t_table. Ce sera, dans votre implémentation une structure contenant : une chaîne de caractères, un entier et deux pointeurs pour les sous-arbres gauche et droit).
  • Implementez les fonctions de manipulation de la table travaillant sur votre type Table !
  • Compilez, exécutez table.c, le résultat doit être identique à celui obtenu avec les listes.

Correction

Exercice 2 : analyseur d'options UNIX

Un petit analyseur d'options

Ecrire la commande option qui analyse les options et les paramètres passés sur la ligne de commande et qui les affiche sur la sortie standard.
$ option -xdf -y - -kj toto -z
option x
option d
option f
option y
option k
option j
argument toto
argument -z
$

Correction

La commande cat

En utilisant l'analyseur d'option de la question précédente, écrire une version simplifiée de la commande cat. Ce programme ne gérera que les options '-n' '-v' et '-s' de la commande standard (Cf. manuel unix).

Correction A venir...

-- MichelBuffa - 05 Dec 2004
to top

I Attachment sort Action Size Date Who Comment
table.h manage 0.6 K 05 Dec 2004 - 08:39 MichelBuffa  
table.c manage 1.3 K 05 Dec 2004 - 08:39 MichelBuffa  
table_liste.c manage 1.9 K 05 Dec 2004 - 08:39 MichelBuffa  
table_arbre.c manage 2.1 K 05 Dec 2004 - 08:40 MichelBuffa  
option.c manage 0.4 K 05 Dec 2004 - 08:40 MichelBuffa  

You are here: Linfo > CTPSurArbres

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback