20111219:TP:C:Introduction
Un article de WikiProg.
Sommaire |
Outils et Compilation
Pour écrire votre code C, vous pouvez utiliser n'importe quel éditeur de texte, notamment emacs ou vim supporte le langage C sans ajout de configuration particulière.
Un peu d'organisation:
- votre code se trouve dans un fichier .c
- les fichiers d'en-tête se termine pas .h
- il est plus que fortement conseillé d'utiliser make pour compiler vos programme
Invocation du compilateur
Programme standalone
Lorsque votre programme tient dans un seul fichier, les trois passes (preprocessing, compilation et link) de la compilation se font en une fois. Il suffit donc d'appeller le compilateur sur votre fichier source. Bien sûr, il y a quelques options:
- -o nom le nom du binaire produit, par défaut a.out
- -g génération des symboles pour le debugger.
- -On (avec n un entier) le niveau d'optimisation
- plus toutes les options de standard, warning et autres vérfications suplémentaires.
En résumé, si votre code se trouve dans un fichier nommé prog.c et que vous voulez produire le binaire prog la ligne la plus simple sera:
> gcc -o prog prog.c
Compilation séparée
Si votre projet se découpe en plusieurs fichiers, chaque fichier doit être compilé séparément:
> gcc -c mon_fic.c
Ce qui produit un fichier mon_fic.o qui sera utiliser par la phase de link qui produira le binaire (on suppose que l'on a les fichiers a.c, b.c et prog.c contenant le programme principal):
> gcc -c a.c > gcc -c b.c > gcc -o prog a.o b.o prog.c
On peut aussi faire ça en compilant le programme principal comme un module (ce que l'on fait souvent avec des règles automatiques):
> gcc -c a.c > gcc -c b.c > gcc -c prog.c > gcc -o prog a.o b.o prog.o
Options de compilation
Nous allons ajouter une série d'option de compilation qui activent un certain nombre de vérificaitons suplémentaires:
- -Wall et -W: activation de l'ensemble des warnings standards et extra
- -pedantic active la détection de pratique non-ISO C
- -Werror les warnings sont considérés comme des erreurs
- -ansi support du standard C89(ansi)/C90(ISO) peut être remplacé par -std=c89
- -O2 activation du niveau 2 d'optimisation qui au passage ajoute certaines vérifications suplémentaires.
Donc notre premier exemple devient:
> gcc -Wall -W -pedantic -Werror -ansi -O2 -o prog prog.c
Environnement et compilation
Afin de compiler simplement les exercices du TP (et des suivants) vous pouvez déjà fixer les options de compilation de gcc dans les règles automatiques de make. Pour ça, il faut renseigner deux variables de votre environnement (dans votre shell quoi) soit juste dans le terminal courrant, soit pour toutes vos sessions. Cette méthode permet de compiler du code C sans écrire de Makefile.
Voici les commandes pour fixer ces variables, vous pouvez les ajouter au fichier de configuration de votre shell où les taper directement dans votre terminal.
Commandes pour les shells de type sh classique (ksh, zsh ou bash):
> export CC=gcc > export CFLAGS="-O2 -Wall -W -Werror -pedantic -ansi"
Commandes pour les shells de type csh (tcsh en général):
> setenv CC gcc > setenv CFLAGS "-O2 -Wall -W -Werror -pedantic -ansi"
Une fois ces variables fixées, vous pouvez utiliser make pour produire un executable à partir d'un fichier C standalone (un seul fichier pour le programme):
> ls toto.c > make toto gcc -O2 -Wall -W -Werror -pedantic -ansi toto.c -o toto > ls toto toto.c
Premiers programmes
guess what ?
Devinez ? le premier programme que nous allons écrire est un ? Hello World !
Voici le code:
/* * hello.c : traditional "Hello World" prog * */ /* Standard headers */ #include <unistd.h> #include <stdlib.h> #include <stdio.h> int main(void) { printf("Hello World!\n"); return (0); }
- Compiler et exécuter ce programme !
Paramètres de la ligne de commande
Votre fonction main peut prendre deux paramètres qui vont lui permettre de récupérer les paramètres du programme. Le prototype complet de main est:
int main(int argc, char *argv[]);
- argc correspond à la taille du tableau argv
- argv est un tableau de chaînes de caractères dont la première case contient le nom du programme et les autres cases les paramètres du programme.
Ce petit exemple affiche le tableau d'arguments:
/* * argv.c: print the argv array * */ /* Standard headers */ #include <unistd.h> #include <stdlib.h> #include <stdio.h> int main(int argc, char *argv[]) { int i; printf("argc = %d\n",argc); for (i=0; i<argc; i++) printf("argv[%d]: \"%s\"\n", i, argv[i]); return 0; }
- Testez ce programme avec différents paramètres
- Comment passer des paramètres contenant un espace ?
Encore et toujours factorielle
- Écrire une fonction factorielle en version récursive:
unsigned fact(unsigned n);
- Écrire une fonction factorielle en version itérative:
unsigned fact_iter(unsigned n);
- Compléter votre fichier avec une fonction main pour tester vos deux fonctions factorielles à l'aide des paramètres du programme.
- Vous devrez utiliser la fonction atoi(3) (voir le man correspondant.)
Chaînes de caractères
Dans cette partie nous allons refaire quelques fonctions classiques de la bibliothèque standard sur les chaînes de caractères. Dans la suite, pour tester vos fonctions vous devrez utiliser soit des chaînes statiques (sous de forme de valeurs immédiates comme "toto"), soit des chaines récupérer dans le tableau d'arguments, soit des tableaux statiques de caractères lorsqu'il faudra modifier les chaînes.
En résumé, pour passer des chaînes qui ne seront que lues par vos fonctions vous pourrez utiliser des chaînes immédiates ou les cases du tableau d'arguments. Lorsque vos fonctions devront écrire des caractères dans la chaîne, vous déclarez vos chaînes sous la forme:
char s[X];
- où X-1 correspond au nombre maximal de caractères que peut contenir s (ne pas oublier le 0 terminal.)
Si vous voulez des informations complémentaires sur ces fonctions, elles disposent toutes d'une page de manuel.
Parcours de chaînes
- Écrire la fonction:
size_t my_strlen(char *s);
- Renvoie le nombre de caractères dans s jusqu'au premier caractère de code ascii 0.
- Écrire la fonction:
char *my_strchr(char *s, char c);
- Renvoie le pointeur sur la première occurrence du caractère c dans s ou NULL si c n'est pas dans s. On considère que la caractère c peut être le caractère de code 0 (dans ce cas my_strchr renvoie le pointeur sur le 0 terminal de la chaîne.
- Écrire la fonction:
int my_strncmp(char *s1, char *s2, size_t len);
- Compare lexicographiquement les deux chaînes s1 et s2 sur au plus len caractères. La fonction doit renvoyer 0 si les deux chaînes sont égales, un nombre négatif si la première est plus petite et positif sinon. La comparaison s'arrête après avoir comparer (au plus) len caractères.
Copie
On se propose ici de ré-écrire la fonction strncpy(3) de la libc. On rappelle que cette fonction copie le contenu d'une chaîne dans une autre avec une borne sur le nombre de caractères copiés. La copie s'effectue sur une chaîne déjà allouée avec assez de place pour la copie. La fonction renverra le pointeur de la chaîne de destination.
La copie s'opère en deux temps: copie des caractères puis remplissage de l'espace restant (si nécessaire) par des 0.
- Écrire la fonction:
char *my_strncpy(char *dst, char *src, size_t len);
- qui effectue la copie de src vers dst sur au plus len caractères.
- Compléter la fonction pour remplir complètement la spécification: si src est plus petite que len remplir le reste de dst (à occurrence de len caractères) de caractères de code 0.
Transformations
- Écrire la fonction qui transforme toutes les lettres d'une chaîne en caractères minuscules et renvoie le nombre de caractères modifiés. La chaîne est modifiée en place:
size_t str_downcase(char *s);
- Écrire la fonction qui transforme toutes les lettres d'une chaîne en caractères majuscules et renvoie le nombre de caractères modifiés. La chaîne est modifiée en place:
size_t str_upcase(char *s);
Listes Chaînées
Dans la suite nous utiliserons un seul fichier que nous nommerons list.c.
Construction du type
En langage Algo, les listes chaînées (d'entier pour l'exemple) se construise comme suit:
types
t_list = ^s_list
s_list = enregistrement
entier val
t_list next
fin enregistrement
Nous allons obtenir le même résultat en C. Nous suivrons la même stratégie de déclaration: définition du type t_list comme un pointeur sur la structure d'un maillon de la liste. Le code correspondant fournit cette définition:
/* Definition du type t_list */ typedef struct s_list *t_list; /* Definition de la structure s_list */ struct s_list { int val; t_list next; };
- Constuire les opérations sur les listes suivantes:
/* Renvoie une nouvelle liste vide */ t_list empty(void); /* Renvoie vraie si l est vide */ int is_empty(t_list l); /* Ajoute x en tete de la liste et renvoie la nouvelle tete */ t_list add(int x, t_list l);
- Allocation: pour ajouter un élément à une liste, il faut allouer un maillon, nous utiliserons pour ça la fonction malloc(3) et l'opérateur sizeof. Attention, la taille à allouer est la taille de la structure, pas celle du pointeur ...
Parcours de liste
Nous allons maintenant parcourir nos listes.
- écrire la fonction suivante:
/* renvoie la taille de la liste */ size_t length(t_list l);
- écrire la fonction suivante:
/* renvoie la somme des éléments de la liste */ int sum(t_list l);
- écrire la fonction suivante:
/* renvoie la moyenne des éléments de la liste */ float avg(t_list l);
- écrire la fonction suivante (utiliser free(3)):
/* libere l'ensemble de la liste */ void destroy(t_list l);
- (bonus) écrire la fonction suivante utilisant un pointeur sur fonction:
/* applique la fonction pointee par f sur chaque element de l */ void iter(void (*f)(int), t_list l);
Tester
- À partir de l'ensemble des fonctions précédante, tester vos opérations avec la fonction principale suivante:
void print_int(int x) { printf(" %d;",x); } int main(int argc, char *argv[]) { t_list l,tmp; size_t len=5, i; if (argc>1) len = atoi(argv[1]); l = empty(); for (i=1; i<=len; i++) l = add(i,l); /* avec iter */ printf("l = ["); iter(print_int, l); printf("]\n"); /* sans iter */ printf("l = ["); for (tmp = l; tmp; tmp = tmp->next) print_int(tmp->val); printf("]\n"); printf("l: %u - %d - %.2f\n",length(l),sum(l), avg(l)); destroy(l); return 0; }
- si vous n'avez pas fait la fonction iter, supprimer les lignes correspondantes.
- Compléter, compiler et tester votre programme.
Arbres
Nous allons maintenant implanter des arbres binaires de recherche (contenant une association clef/valeur.)
Pour commencer voici le type:
typedef struct s_tree *tree; struct s_tree { int key, val; tree ls, rs; };
Opérations de bases
- Implémenter les fonctions suivantes:
/* renvoie un arbre vide */ tree empty(); /* taille d'un arbre */ size_t size(tree t); /* Peut servir ... */ size_t max(size_t a, size_t b) { if (a<b) return b; else return a; } /* hauteur d'un arbre */ size_t height(tree t);
Ajout d'un élément
On va ajouter un élément. Attention, bien évidement on veut engendrer un arbre ordonné: donc la technique est simple on descend comme pour la recherche dans un arbre binaire de recherche et dès qu'on tombe sur l'arbre vide, on crée le nœud. Attention, on utilise un pointeur sur l'arbre (pour pouvoir le modifier dans le cas d'arrêt.)
void add(int k, int v, tree *t);
Cette fonction remplit un arbre à partir de deux bornes pour les clefs.
void fill_tree(int min, int max, tree *t) { int mid = (max+min)/2; if (min<max) { add(mid,random()%100,t); fill_tree(mid+1,max,t); fill_tree(min,mid-1,t); } }
