:: Enseignements :: Licence :: L3 :: 2012-2013 :: Programmation C ::
[LOGO]

Ensembles, listes, et entrées/sorties


L'objectif de ce TD est de représenter des ensembles d'entiers sous forme binaire, et de manipuler les fonctions d'entrées/sorties sur les fichiers pour stocker/charger ces ensembles. Ce TD sera également l'occasion d'utiliser la gestion d'options en ligne de commandes.

Exercice 1 - Manipulation de bits et ensembles

Écrire les fonctions de base suivantes :
  • int test_bit(unsigned char octet, int b) qui permet de savoir la valeur du b-ième bit d'un octet (encodé dans un unsigned char) ; elle renvoie la valeur de ce bit, c'est-à-dire 0 ou 1.
  • void set_bit(unsigned char* octet, int b) qui positionne le b-ième bit d'un octet à 1.
  • void unset_bit(unsigned char* octet, int b) qui positionne le b-ième bit d'un octet à 0.

Un ensemble de nombres entiers peut être représenté comme un tableau de bits. Chaque indice i du tableau correspond au nombre i ; la valeur dans le tableau à cet indice est 1 si le nombre appartient à l'ensemble, et 0 sinon.

En pratique, en C, on doit utiliser un tableau de unsigned char (ou octet). Chaque octet contient 8 bits, donc potentiellement 8 nombres.

Par exemple, si l'on suppose qu'un ensemble est représenté par un tableau de 2 octets, il pourra contenir les nombres compris entre 0 et 15. Ainsi, lour l'ensemble {3, 5, 10}, le premier octet contiendra les nombres 3 et 5 et aura pour valeur 40 (23 + 25 = 00101000); le deuxième octet contiendra le nombre 10 et aura pour valeur 4 (00000100). Attention, les bits de poids faibles sont à droite.

  • Définir une constante MAX qui sera la taille unique des tableaux représentant les ensembles.
  • Ecrire une fonction init_set qui initialise un ensemble (l'ensemble est vide).
  • Ecrire une fonction add qui ajoute un nombre dans un ensemble.
  • Ecrire une fonction print_set qui affiche un ensemble.
  • Ecrire une fonction contains qui indique si un nombre entier entier appartient à un ensemble.
  • Ecrire une fonction cardinality qui renvoie le nombre d'éléments d'un ensemble.
  • Ecrire une fonction unio qui fait l'union de deux ensembles (non, ce n'est pas une faute, il ne manque pas de n. Réfléchissez et vous comprendrez)
  • Ecrire une fonction intersection qui fait l'intersection de deux ensembles.
  • Ecrire une fonction complement qui fait la complémentation d'un ensemble.


bits.h :

bits.c :


ensemble.h :

ensemble.c :

Exercice 2 - Fichiers binaires et fichiers textes

La représentation d'ensemble par tableau d'octets se prête fort bien à des entrées/sorties binaires utilisant fwrite et fread.

Écrire les fonctions suivantes :
  • int save_set_bin(unsigned char* set, char* filename) : effectue la sauvegarde de l'ensemble set dans un fichier portant le nom filename. Attention à bien tester tous les cas d'erreurs !
  • int load_set_bin(unsigned char* set, char* filename) : effectue la lecture de l'ensemble contenu dans un fichier portant le nom filename et retourne cet ensemble, ou NULL en cas de problème.

Nous voulons maintenant un format de fichier texte dans lequel les éléments sont stockés en représentation décimale, sans ordre précis, séparés par des espaces, tabulations et/ou retours à la ligne.

Écrire les fonctions suivantes :
  • int save_set_txt(unsigned char* set, FILE *filename) : effectue la sauvegarde de l'ensemble set dans un fichier portant le nom filename, supposé avoir été ouvert correctement. Attention à bien tester tous les cas d'erreurs !
  • int load_set_txt(unsigned char* set, FILE *filename) : effectue la lecture de l'ensemble contenu dans le fichier portant le nom filename et retourne cet ensemble, ou NULL en cas de problème. La fonction affichera un avertissement sur la sortie d'erreur en cas de doublons.


save_and_load.h :

save_and_load.c :

Exercice 3 - Tri

La construction et l'affichage d'un ensemble produit en sortie une suite triée. On veut tirer partie de cela pour écrire un programme capable de trier des nombres entiers compris entre 0 et N, N étant le plus grand nombre pouvant être représenté dans ensemble codé par un tableau de MAX octets (au fait, N vaut combien ?).
  1. Écrire une première version de ce programme qui lit les nombres à trier sur l'entrée standard et qui écrit le résultat sur la sortie standard.
  2. Écrire une seconde version de ce programme qui utilise getopt_long de la façon suivante :
    • Si l'on utilise l'option -i xxx ou --input xxx, les nombres sont lus sur le fichier xxx. Par défaut, ils sont toujours lus sur l'entrée standard.
    • Si l'on utilise l'option -o yyy ou --output yyy, les nombres triés sont écrits dans le fichier yyy. Par défaut, ils sont toujours écrits sur la sortie standard.
Ajouter une option -n / --no_warning avec laquelle le programme n'émet plus de warning en cas de doublons.

Exercice 4 - Listes et ensembles

On souhaite maintenant pouvoir représenter un ensemble d'entiers compris entre 0 et N soit à l'aide de la structure d'ensemble définie ci-dessus, soit à l'aide d'une liste chaînée triée.

On utilisera le type suivant :
struct list {
	int value;
	struct list* next;
};
Écrire les fonctions suivantes, en veillant à bien réfléchir à ce qu'elles doivent éventuellement retourner :
  • allocate(int n) : alloue une cellule et l'initialise avec la valeur n
  • free_list(struct list* l) : libère toute la mémoire associée à la liste pointée par l
  • print_list(struct list* l) : affiche la liste l
  • insert(struct list* *l, int n) : insère la valeur n en tête de la liste l

Maintenant, écrire les fonctions suivantes, permettant de passer d'une représentation à l'autre :
  • unsigned char* list_to_set(struct list* l) : construit et retourne l'ensemble représenté par la liste l. La fonction renverra NULL si une des valeurs de la liste dépasse la capacité de l'ensemble (dépend de la constante MAX définie précédemment), ou si l'allocation du tableau d'octets échoue.
  • struct list* set_to_list(unsigned char* e) : construit et retourne la liste triée contenant toutes les valeurs de l'ensemble e.

Exercice 5 - Opérations sur les ensembles

La structure de liste chaînée est bien adaptée à l'application d'opérations sur chacun des éléments de l'ensemble.

Écrire les fonctions suivantes :
  • void map(struct list* l, int (*operation)(int), ...) : applique à chaque élément de la liste l toutes les opérations fournies en paramètre sous la forme de pointeurs de fonctions int (*operation)(int), dans l'ordre où celles-ci sont fournies. Il faudra utiliser la bibliothèque stdarg.h permettant de gérer le nombre variables d'opérations fournies en paramètre. Le dernier argument devra valoir NULL, donnant la possibilité de détecter la fin des arguments.
  • struct list* filter(struct list* l, int (*criteria)(int)) : retourne une liste contenant uniquement les éléments de la liste l respectant le critère fourni en paramètre sous la forme d'un pointeur de fonction criteria (il est supposé que cette fonction renvoie 1 si le critère est respecté, et 0 sinon).
Par exemple, les deux fonctions précédentes pourront être utilisées ainsi :
int mult_by_2(int n); // renvoie 2n
int sqr(int n); // renvoie n²
int even(int n); // renvoie 1 si n est pair, et 0 sinon

int main(void) {
	struct list *l1, *l2;
	...
	map(l1, mult_by_2, sqr, NULL); // chaque élément n de la liste l1 est remplacé par (2n)²
	l2 = filter(l1, even); // la liste l2 contient uniquement les nombres pairs contenus dans la liste l1
	...
}