Exercice 1 - Manipulation de bits

  • Écrire les fonctions de base suivantes :
    • teste_bit qui permet de savoir la valeur d'un des bits d'un octet (unsigned char); elle renvoie 0 ou 1.
    • allume_bit qui positionne un bit donné d'un octet à 1.
    • eteint_bit qui positionne un bit donné d'un octet à 0.

Exercice 2 - Ensembles

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, elle est 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. Pour 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 les fonctions init_ensemble qui initialise un ensemble (l'ensemble est vide).
  • Ecrire une fonction ajoute qui ajoute un nombre dans un ensemble.
  • Ecrire une fonction affiche_ensemble qui affiche un ensemble.
  • Ecrire une fonction appartient qui indique si un nombre entier entier appartient à un ensemble.
  • Ecrire une fonction cardinal 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 complementation qui fait la complémentation d'un ensemble.

Exercice 4 - Fichiers binaires

La représentation d'ensemble par tableau d'octets se prête fort bien à des E/S binaires utilisant fwrite et fread. Écrire les fonctions suivantes:
  • int sauver_ensemble(unsigned char* e,char* nom_fichier): effectue la sauvegarde de l'ensemble donné dans un fichier portant le nom indiqué. Attention à bien tester tous les cas d'erreurs.
  • unsigned char* charger_ensemble(char* nom_fichier): effectue la lecture de l'ensemble contenu dans un fichier portant le nom indiqué et retourne cet ensemble, ou NULL en cas de problème.

Exercice 5 - Fichiers texte

Cette fois-ci, nous voulons 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 sauver_ensemble2(unsigned char* e,FILE* fichier): effectue la sauvegarde de l'ensemble donné dans le fichier donné, supposé avoir été ouvert correctement. Attention à bien tester tous les cas d'erreurs.
  • unsigned char* charger_ensemble2(FILE* fichier): effectue la lecture de l'ensemble contenu dans le fichier donné 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.

Exercice 6 - 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 ?).

É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.

É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.