Voir la source de Programmation:C:Bases

== Introduction ==

Le langage C est l'un des langages les plus utilisés aujourd'hui, sa syntaxe à inspirer de nombreux autres langages (Java, C++, D ... ) et ses qualités en font le langage de référence pour la programmation impérative de manière générale et pour la programmation système en particulier.

Ce premier cours sur le langage C présente une histoire rapide du langage, une description de la nature du langage, les bases de sa syntaxe, les méthodes de compilation et enfin quelques exemples.

== Présentation du C ==

L'histoire du langage C est un point important pour la compréhension des difficultés que la programmation en C pose. C'est pourquoi une description du langage nécessite quelques rappels d'histoire.

=== Un peu d'histoire ===

==== 1972: Les débuts ====

D'après Denis Ritchie<ref>Dennis M. Ritchie, "The Development of the C Language", 1993, [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html] </ref> (l'auteur principal du C) le langage C est apparu entre 1969 et 1973 avec pour objectif d'écrire (enfin réécrire) l'un des premiers noyeaux du système UNIX.

Pour faire court, les premières versions d'UNIX (''UNICS'' à l'époque) étaient écrites directement en assembleur pour le ''PDP-7''. Ken Thompson (l'auteur d'UNIX) voulait disposer d'un langage de ''haut niveau'' pour programmer sur son nouveau système, il construisit donc le langage B [http://en.wikipedia.org/wiki/B_(programming_language)], une version ''simplifiée'' du langage BCPL [http://en.wikipedia.org/wiki/BCPL].

Lors du passage au ''PDP-11'', Dennis Ritchie eu besoin d'étendre le langage pour supporter les nouvelles possibilités de l'assembleur ''PDP-11''. Ces extensions (principalement l'introduction d'une forme restreinte de typage) conjointement avec l'apparition du pré-processeur donnère naissance au langage C.

==== Le C '''K&R''' ====

On considère que la première édition du '''K&R''' <ref>Brian W. Kernighan and Dennis M. Ritchie, "The C Programming Language", 1978</ref> comme la première référence du langage dans sa version appelée (justement) '''K&R'''. Bien que parfois encore utilisée, cette version a cédé la place à la version '''ANSI''' normalisée en 1989.

Cette version diffère des versions actuelles sur quelques détails de syntaxe et surtout sur l'abscence de vérification des paramètres de fonction (ni sur leur nombre, ni sur leur type.)

Parmis les points importants qui détache C d'autres langage, la gestion des entrées/sorties (I/O) est l'une des caractéristiques majeures: au lieu de fournir des I/O sous forme de primitives, le langage passe par des routines fournies par le système et une bibliothèque standard. Cette approche est l'un des éléments déterminants dans la portabilité du langage.

==== Le C '''ANSI''' ====

En 1989, le langage C a bénéficié d'une normalisation complète par l'organisme américain '''ANSI''', il s'agit de la norme <tt>ANSI X3.159-1989 "Programming Language C"</tt>, souvent appellée ''ANSI C'' ou ''C89''. Cette norme a été reprise par l'organisme internationnale '''ISO''' en 1990, sous le code <tt>ISO/IEC 9899:1990</tt> souvent appellé ''ISO C'' ou ''C90''. Les deux normes font références à la même description du langage.

Le ''C89'' introduit de nombreux changements (syntaxique et sémantique) issus des différentes variantes du langage. On peut noter en particulier le typage des paramètres des fonctions, la possibilité de renvoyer des types non-atomiques, l'introduction du type <tt>enum</tt> ...

Aujourd'hui, le ''C89'' est la référence pour la programmation en C. Même si des extensions existent (et même une nouvelle norme), elles restent dans l'esprit de la norme de 1989.

La norme décrit également la bibliothèque standard qui accompagne tout implantation du langage (que l'on appelle générallement la ''libC''.) Cette bibliothèque contient des fonctions permettant la gestion des I/O et les routines ''systèmes'' classiques. Cette bibliothèque standard est souvent complétée par les routines spécifiques au monde UNIX et le découpage entre le standard C et le monde UNIX n'est pas toujours clair.

On peut citer par exemple les ''sockets'' BSD (API réseau) qui sont intégrées dans la ''libC'' des systèmes UNIX sans pour autant faire parti de la norme ''C89''. Certaines ''libC'' (en particulier celle de GNU) considère que en mode ''standard ansi'' les fonctions spécifiques à UNIX ne sont pas définies.

Les normes POSIX (''Portable Operating System Interface [for Unix]''[http://standards.ieee.org/regauth/posix/]) et SUS (''Single UNIX Specification''[http://www.unix.org/what_is_unix/single_unix_specification.html] complètement intégrée depuis la version 3 dans POSIX) fournissent une spécification pour la ''libC'' qui complète celle de la norme ANSI. Historiquement, les deux normes (POSIX et ANSI) ont été développé à la même époque de manière concurrente ce qui explique le manque de cohérence entre les deux.

==== C99 et C1X ====

En 1999, la norme ISO du C (''C90'') a été étendue pour inclure certains aspects ajoutés par divers versions des compilateurs C. Cette norme est référencée sous le nom <tt>ISO/IEC 9899:1999</tt>.

Cette norme ajoute quelques assouplissement dans la syntaxe et des nouveaux types de données. On notera la possibilité de déclarer des variables à l'intérieur des blocs de code (et non pas uniquement au début des blocs), les commentaires de ligne à la BCPL/C++ ...

Enfin, depuis 2007, un nouveau projet de normalisation a été lancé, le nom actuel est ''C1X''.

=== Principales caractéristiques du langage ===

Le langage C (dans sa version primitive) hérite de nombre des traits qui caractèrise B et BCPL. En particulier, le langage fournit une abstraction ''structurelle'' par rapport à l'assembleur: il est possible d'organiser le code en fonction et procédure, les branchements conditionnels sont organisés sous forme d'alternatives (''if - else'') ou de boucles. Le C introduit également quelques rudiments de typage, permettant de différencier les caractères, les ''valeurs entières'' et les pointeurs, mais surtout il introduit la notion de types structurés qui n'existaient ni en B, ni en BCPL.

Le langage dispose également d'un pré-processeur (l'un des ajouts par rapport à B) permettant d'effectuer des opérations purement syntaxique sur le code source ''avant'' la phase de compilation. Le pré-processeur permet d'inclure des fichiers externes (notamment les en-têtes pour la compilation séparée), de définir des macros et des constantes qui seront remplacées directement dans le code et d'effectuer des tests ''statiques'' (à la compilation, enfin avant) affectant le code source.

Le langage C fut probablement le premier langage proposant un à la fois de contrôler le ''bas niveau'' avec des ''constructions abstraites''. Encore aujourd'hui, il reste le langage de référence dans la programmation système (notamment pour la programmation ''kernel''.)

En contre partie, le système de types est ''pauvre'' et faible et n'offre pas les garanties d'un système plus élaboré et encore celles des langages dont le typage et la sémantique sont bien fondés (comme [[OCaml]] par exemple.) Du coup, la programmation en C implique une plus grande attention et une plus grande rigueur de la part du programmeur que pour d'autres langages modernes. Les erreurs sont souvent difficiles à détecter et à trouver et peuvent parfois avoir des conséquences dramatiques. On prendra comme exemple ce que l'on appelle les ''buffer overflows'': il s'agit d'exploiter des copies non bornées dans un programme pour en modifier le comportement, pouvant entrainner des failles des sécurités importantes (voir à ce sujet [http://insecure.org/stf/smashstack.html] ou en version française [http://www.ouah.org/p49fr.txt], attention il s'agit d'un article très technique !)

=== Bibliothèque standard et documentation ===

Lorsque vous travaillerez en C, vous aurez à votre disposition, la plus part du temps, la bibliothèque standard décrite par la norme ''C89'' (au moins) et si vous êtes sur un système UNIX cette bibliothèque sera étendue par les opérations de la norme POSIX.

La bibliothèque standard du C (norme ISO et ANSI, donc ''C89'', ''C90'' et ''C99'') définie les en-tête suivant:

:* <tt><assert.h></tt>
:* <tt><complex.h></tt> ''(C99)''
:* <tt><ctype.h></tt>
:* <tt><errno.h></tt>
:* <tt><fenv.h></tt> ''(C99)''
:* <tt><float.h></tt>
:* <tt><inttypes.h></tt> ''(C99)''
:* <tt><iso646.h></tt>
:* <tt><limits.h></tt>
:* <tt><locale.h></tt>
:* <tt><math.h></tt>
:* <tt><setjmp.h></tt>
:* <tt><signal.h></tt>
:* <tt><stdarg.h></tt>
:* <tt><stdbool.h></tt> ''(C99)''
:* <tt><stddef.h></tt>
:* <tt><stdint.h></tt> ''(C99)''
:* <tt><stdio.h></tt>: gestion des entrées/sorties ''évoluées''
:* <tt><stdlib.h></tt>: la bibliothèque de ''base'' (conversions, génération de nombres aléatoires, allocation mémoire, contrôle des processus et de l'environnement ... )
:* <tt><string.h></tt>: gestion des chaînes de caractères
:* <tt><tgmath.h></tt> ''(C99)''
:* <tt><time.h></tt>
:* <tt><wchar.h></tt>
:* <tt><wctype.h></tt>

La norme POSIX ajoute (entre autre) les en-têtes suivants:

:* <tt><unistd.h></tt>: constantes et appels systèmes
:* <tt><sys/types.h></tt>: définitions des types utilisés dans le reste de la bibliothèque
:* <tt><fcntl.h></tt>: ouverture et gestion ''bas niveau'' des fichiers
:* <tt><pthread.h></tt>: POSIX Thread
:* et de nombreux autres en-têtes orientés ''système'' ou réseau.

Vous pouvez trouver assez facilement de la documentation sur la plus part des ces en-têtes (ANSI/ISO ou POSIX) sur internet, mais vous pouvez également utiliser les pages de manuels des systèmes UNIX. Si ces pages sont installées (ces le cas sur FreeBSD par défaut), vous trouverez les descriptifs des fonctions fournies dans deux sections:
:* la section 2 décrit les appels systèmes (<tt>fork</tt>, <tt>write</tt>, <tt>read</tt>, <tt>mmap</tt>, <tt>wait</tt> ... )
:* la section 3 décrit les fonctions de la bibliothèque (<tt>printf</tt>, <tt>atoi</tt>, <tt>strlen</tt> ... )

Chaqu'une de ces pages décrit les fichiers à inclure, le (ou les) prototype(s) de la (ou les) fonction(s) et surtout une description de ce qu'elle fait et de comment s'en servir.

En règle générale, lorsque l'on parle d'une fonction (ou d'une commande, ou de tout autre élément qui peut disposer d'une page de manuel) on écrira: <tt>nom(X)</tt> où <tt>nom</tt> est le nom de la fonction et <tt>X</tt> la section du manuel où se trouve la page. Pour accéder à la page de manuel d'une telle fonction il faut passer en premier paramètre de la commande <tt>man</tt> le numéro de la section et en second paramètre le nom de la fonction. Par exemple, pour obtenir la page de manuel de <tt>printf</tt>, il faut faire:

<pre>
> man 3 printf
PRINTF(3)              FreeBSD Library Functions Manual              PRINTF(3)

NAME
     printf, fprintf, sprintf, snprintf, asprintf, vprintf, vfprintf,
     vsprintf, vsnprintf, vasprintf -- formatted output conversion

LIBRARY
     Standard C Library (libc, -lc)

SYNOPSIS
     #include <stdio.h>

     int
     printf(const char * restrict format, ...);

     int
     fprintf(FILE * restrict stream, const char * restrict format, ...);

     int
     sprintf(char * restrict str, const char * restrict format, ...);

     int
     snprintf(char * restrict str, size_t size, const char * restrict format,
         ...);

     int
     asprintf(char **ret, const char *format, ...);

     #include <stdarg.h>

     int
     vprintf(const char * restrict format, va_list ap);

     int
     vfprintf(FILE * restrict stream, const char * restrict format,
         va_list ap);

     int
     vsprintf(char * restrict str, const char * restrict format, va_list ap);

     int
     vsnprintf(char * restrict str, size_t size, const char * restrict format,
         va_list ap);

     int
     vasprintf(char **ret, const char *format, va_list ap);

DESCRIPTION

                   ...
</pre>

Dans certains cas (en fait la plus part du temps), le numéro de section n'est pas nécessaire. Le mécannisme des pages de manuels recherche la page demandée dans les sections par ordre croissant, donc à moins qu'il existe une page de même nom dans la section 1, on peut omettre le numéro la plus part du temps. Mais attention, la section 1 contient les commandes de bases du système (<tt>cp</tt>, <tt>ls</tt> ... ), or il existe des commandes portant le même que certaines fonctions de la bibliothèque standard comme <tt>printf(1)</tt>, <tt>write(1)</tt>, <tt>open</tt> (<tt>builtin(1)</tt>), <tt>read</tt> (<tt>builtin(1)</tt>), <tt>exit</tt> (<tt>builtin(1)</tt>) ...

== Syntaxe générale ==

Le langage dispose d'une syntaxe relativement ''simple'' avec peu de mots clefs et une structure générale organisée en fonctions. Il est possible de définir des types (ou plutôt des alias de types) ou des variables globales (mais on ne le fait pas <ref>Krisboul: ''Certains voudront se rebeller en mettant des variables globales. Bah qu'ils se rebellent, je leur mettrai zéro. Ils se rebellent, zéro. Ils se rebellent, zéro. Ils se rebellent, zéro... Curieusement ils se lassent toujours avant moi...''</ref>.)

Un fichier C contient:
* des définitions de types;
* des définitions de fonctions;
* des définitions de variables globales;
* des définitions de macros, constantes;
* des inclusions de fichiers externes.

=== Déclarations de variables ===

Quelque soit le contexte, les déclarations de variables ont toujours la même forme: <tt>t x;</tt> où <tt>t</tt> est le nom du type et <tt>x</tt> le nom de la variable. On peut cumuler plusieurs déclarations sur la même ligne: <tt>t x, y, z;</tt>.

On peut également affecter une valeur directement à chaque variable lors d'une déclaration (attention, en ''C89'', il faut que cette valeur soit une constante, ou une expression constante ne faisant pas intervenir de calcul qui ne peuvent pas être résolu à la compilation): <tt>int x=1, y, z=2;</tt>

Enfin, il est possible de déclarer des pointeurs sur un type donné en ajoutant une étoile: <tt>int *x;</tt>. Attention l'étoile est attachée à la variable, pas au type: <tt>int *x, y;</tt> déclare un pointeur sur entier <tt>x</tt> et un entier <tt>y</tt>.

Reste le cas particulier des pointeurs sur fonction: <tt>int (*f)(int)</tt> déclare une variable <tt>f</tt> qui est un pointeur sur une fonction prennant un entier et renvoyant un entier.

Quelques exemples:
<source lang="C">
  int	        x, y=1, z;
  char          c1, *s = "toto", c2='a';
  void         *p;
  float         f = 3.14;
  int           (*f) (int,int);
</source>

=== Expressions ===

On dispose des valeurs immédiates usuelles: entiers, floattants, caractères (entre simple cote <tt>'</tt>), chaînes de caractères (entre guillemet <tt>"</tt>) ...

Il n'y a pas de type booléen, comme toutes les valeurs peuvent être assimilés à des entiers d'une manière ou d'une autre, les entiers servent des références: <tt>0</tt> correspond à faux et toutes les autres valeurs à vraie. Attention, pour les chaînes de caractères, la chaînes vides (<tt>""</tt>) n'est pas la valeur <tt>0</tt>.

Les opérations arithmétiques classiques et les comparaisons s'appliquent à presque tous les types de données. Notamment, il est possible de faire des additions, des soustractions, des comparaisons et des opérations logiques sur les pointeurs (sans conversion préalable.)

On retrouve évidement l'utilisation classiques des variables ou des appels de fonctions. On notera que le nom d'une fonction (sans ses paramètres) peut être considérés comme un pointeur sur cette fonction.

Il est aussi possible d'écrire une forme particulière d'alternative, appelée ''opérateur ternaire'', utilisable dans les expressions: <tt>c?e1:e2</tt> qui renvera la valeur de l'expression <tt>e1</tt> si l'expression <tt>c</tt> renvoie une valeur non-null et la de <tt>e2</tt> sinon.

Enfin, certaines opérations usuellement considérés comme des instructions dans les langages impératifs, sont des expressions et renvoient une valeur. C'est le cas de l'affectation et de ses variantes: <tt>x=e</tt> affecte la valeur de <tt>e</tt> dans <tt>x</tt> et renvoie cette valeur. Les incréments et décréments (qui sont des ''racourcis'') renvoient également une valeur:
* <tt>x++</tt> renvoie la valeur de <tt>x</tt> puis affecte <tt>x+1</tt> à <tt>x</tt>
* <tt>x--</tt> renvoie la valeur de <tt>x</tt> puis affecte <tt>x-1</tt> à <tt>x</tt>
* <tt>++x</tt> affecte <tt>x+1</tt> à <tt>x</tt> puis renvoie la valeur de <tt>x</tt>
* <tt>--x</tt> affecte <tt>x-1</tt> à <tt>x</tt> puis renvoie la valeur de <tt>x</tt>

Il existe une forme particulière d'affectation combinant un opérateur arithmétique avec l'opérateur d'affectation: <tt>x ''op''= e1</tt> est évalué comme <tt>x = x ''op'' e1</tt> (où <tt>''op''</tt> peut remplacer par des opérations classiques comme <tt>+, -, *, /, % ... </tt>.)

On dispose enfin d'opérations spécifiques à différents types: <tt>e1[e2]</tt> pour accéder aux cases des tableaux; <tt>*e</tt> pour déréférencer un pointeur, <tt>&e</tt> pour référencer l'adresse (obtenir le pointeur) d'une valeur gauche, <tt>e.champ</tt> pour accéder au champ d'une structure ou d'une union, <tt>e->champ</tt> pour accéder au champ d'une structure référencée par un pointeur ...

==== Valeur gauche ====

Dans les langages impératifs, il existe deux manières d'évaluer certaines expressions: évaluation droite et évaluation gauche. Cette appelation vient du fait que lorsque l'on évalue une affectation <tt>e1=e2</tt>, l'expression <tt>e1</tt> sera évaluée ''à gauche'', tandis que <tt>e2</tt> sera évaluée à droite.

Bien évidement, toutes les expressions ne peuvent pas être évaluées à gauche: seule les '''valeurs gauches''' peuvent être évaluées à gauche.

Une valeur gauche est une ''cellule mémoire'' sur lequel on peut effectuer une affectation. Les valeurs sont (non-exhaustif):
* des variables
* des champs de structure ou d'union
* des cases de tableaux
* un déréférencement de pointeur (<tt>*e</tt>)

Outre les affectations (et donc les incréments/décréments), l'opération de référencement (<tt>&e</tt>) ne peut s'appliquer que sur une valeur gauche.

==== Tableaux et chaîne de caractères ====

Techniquement parlant, les tableaux n'existent pas en C ! Le langage fournit un raccourcis de syntaxe sur les pointeurs permettant de manipuler des blocs de mémoire comme des tableaux.

En pratique, tout se passe comme avec des tableaux classiques: il est possible d'accéder à la ''i-''ème case d'un tableau avec la notation <tt>e[i]</tt>.

Le compilateur remplace l'expression <tt>e[i]</tt> par <tt>*(e+i)</tt> (voir plus loin l'arithmétique des pointeurs.)

Les tableaux à plusieurs dimensions n'existe qu'en version statique (pour faire simple) car des informations de taille sont nécessaires pour calculer le décalage: soit un tableau à deux dimesions avec <tt>N</tt> lignes, l'expression <tt>e[i][j]</tt> sera remplacée par <tt>*(e + i*N + j)</tt>.

Attention, il ne faut pas confondre les tableaux à plusieurs dimension et les tableaux de tableaux. En effet, un tableau à deux dimesions correspond à la concaténation des lignes les une à la suite des autres, alors qu'un tableau de tableaux est un tableau de pointeurs, chaque pointeur correspondant chaqu'un à tableau.

Les chaînes de caractères sont des pointeurs sur une zone mémoire contenant ''logiquement'' les caractères de la chaîne plus un caractère de code ASCII <tt>0</tt> (à ne pas confondre avec le caractère <tt>'0'</tt>.) On peut donc considérer qu'une chaîne de caractères est un tableau de caractères et donc un pointeur.

==== Arithmétique sur les pointeurs ====

L'arithmétique sur les pointeurs est un peu particulière. Un pointeur est une adresse dont la précision est en générale l'octet, il s'agit donc en pratique d'un simple entier. Seulement, les opérations arithmétiques sur les pointeurs ne se font pas forcément à l'octet pret.

Soit un pointeur déclaré de la manière suivante: <tt>t *p</tt>. Lorsque l'on écrit <tt>p + x</tt> (avec <tt>x</tt> un entier), l'adresse obtenue est <tt>p + x*N</tt> où <tt>N</tt> est la taille (déduite par le compilateur) des données de type <tt>t</tt>.

Par exemple:
<source lang="C">
/* pointeur sur caractère*/
char *s;

/* ... */ s+1 /* ... */
/* correspond à l'adresse s plus un octet */

int *p;
/* pointeur sur entier (en 32bits) */

/* ... */ p+1 /* ... */
/* correspond à l'adresse p plus quatre octets */
</source>

=== Instructions ===

==== Instructions et blocs ====

Basiquement une instruction est soit un contrôle de flot, soit une expression suivie d'un point virgule, soit la primitive <tt>return expr</tt>, soit un bloc.

Les blocs sont composés d'une liste de déclarations puis d'une liste d'instruction. Les variables déclarées en début de bloc ont la même durée de vie que le bloc, elles sont locales au bloc.

La primitive <tt>return expr</tt> sort de la fonction courante et renvoie la valeur résultat de l'expression <tt>expr</tt>. Il existe également deux autres primitives, <tt>break</tt> et <tt>continue</tt>, qui permettent de sortir de la boucle courante (<tt>break</tt>) ou passe à la prochaine itération de la boucle courante (<tt>continue</tt>.)

==== Contrôle de flot ====

Les contrôles de flot sont des tous instructions et ne peuvent donc pas être utilisés comme expression (contrairement au <tt>if then else</tt> d'[[OCaml]] par exemple.)

Ils reposent tous sur le test d'une condition qui prend toujours la forme suivante <tt>(expr)</tt> (les parenthèses font parties de la syntaxe.)

* L'alternative utilise la construction classique <tt>if</tt> avec un <tt>else</tt> optionnel:
<source lang="C">
if (expr)
  /* instruction ou bloc */
else
  /* instruction ou bloc */

/* no else */
if (expr)
  /* instruction ou bloc */
</source>

* La boucle ''while'' est également très classique:
<source lang="C">
while (expr)
  /* instruction ou bloc */
</source>

* Il existe une boucle ''while'' avec test en fin plutôt qu'au début:
<source lang="C">
do
  /* instruction ou bloc */
while (expr);
</source>

* La boucle ''for'' de C n'est pas une vraie boucle ''for'' (ce n'est pas une itération bornée):

<source lang="C">
for (e1; e2; e3)
  /* instruction ou bloc */
</source>

Cette boucle peut être traduite en ''while'':
<source lang="C">
e1;
while (e2)
  {
    /* contenue de la boucle for */
    e3;
  }
</source>

* Il faut noter que les boucles peuvent être ''vide'', c'est à dire ne pas avoir de ''corps''. Dans ce cas, on utilise l'''instruction vide'' représentée par un point virgule seul. Voici par exemple une boucle utilisée pour écrire la fonction <tt>strlen</tt> (enfin, l'une des versions possible):

<source lang="C">
  for (res=0; s[res]; res++);
</source>

=== Déclarations des fonctions ===

La déclaration des fonctions est relativement simple:
<source lang="C">
type nom(type1 p1, type2 p2, ...)
{
  /* Corps de la fonction */
}
</source>

<tt>type</tt> est le type de retour de la fonction, <tt>nom</tt> son nom et <tt>typei pi</tt> les paramètres de la fonction. On notera qu'il n'existe pas de procédure au sens propre, mais qu'il est possible pour une fonction de renvoyer le type <tt>void</tt> (''vide'') lorsque l'on a rien à renvoyer (dans ce cas là, <tt>return</tt> est facultatif.)

Les fonctions sont ''récursives'' par défaut, mais sinon, comme dans tout langage, il faut les déclarer avant de les utiliser. Il existe une possibilité pour utiliser une fonction avant (voir même sans) la définition de la fonction: les ''prototypes''. Un prototype est la déclaration du type de la fonction sans son corps, il prend la forme:

<source lang="C">
type nom(type1 p1, type2 p2, ...) ;
</source>

=== Définitions de types et de structures ===

Il est possible de définir des structures, des unions ou des types énumérés et enfin de déclarer des alias sur des expressions de types (pointeur sur structure ... )

==== Définition des structures ====

Une structure est l'agrégation de valeurs hétérogènes identifiées par une étiquette. Pour pouvoir utiliser une structure, il faut en déclarer la forme (le nom, le type et l'ordre des champs.) Il est important de comprendre qu'une structure est tout simplement la concaténation des valeurs en mémoire, les une à la suite des autres, par conséquent l'ordre et le type des champs est important pour permettre au compilateur d'écrire les opérations d'accès aux différents champs.

La syntaxe de déclaration est la suivante:
<source lang="C">
struct s_ma_struct
{
  type1                 champ1;
  type2                 champ2;
  /* ... */
};
</source>

===== Taille et alignement des structures =====

La taille d'une structure est déterminée par la taille de ses différents champs, plus l'espace utilisé pour aligner les champs et la structure. S'il n'y a pas de problème d'alignement, la taille est tout simplement la somme des tailles des différents champs. Pennons par exemple la structure d'une liste chaînéee d'entiers:

<source lang="C">
struct s_list
{
  int			val;
  struct s_list        *next;
};
</source>

Cette structure fait 8 octets sur une machine 32bits (4 octets pour l'entier et 4 pour le pointeur.) Les ''problèmes'' d'alignement surviennent lorsque les tailles des champs ne sont pas homogènes: les champs doivent se trouver à des adresses multiples de leur taille et la structure elle même doit avoir une taille multiple du mot (32bits dans notre exemple précédant.) Prenons par exemple ces deux structures, qui contiennent les mêmes champs:

<source lang="C">
struct s_v1
{
  char                  c1;
  size_t                i1;
  unsigned short        s1;
};
struct s_v2
{
  size_t                i1;
  unsigned short        s1;
  char                  c1;
};
</source>

<tt>struct s_v1</tt> fait 12 octets contre 8 pour <tt>struct s_v2</tt> (le tout pour 7 octets vraiment utiles ... )

===== Utilisations des structures =====

En théorie, pour déclarer une variable comme une structure, il faut le faire avec la description de la structure:

<source lang="C">
  struct nom { /* description */ } variables;
</source>

Le nom est optionnel et ne sert que si la structure est ''récursive''.

Heureusement, il existe une syntaxe plus simple et plus pratique. En effet, si l'on se contente d'indiquer le nom et pas la description des champs, le compilateur cherchera une autre déclaration de structure avec le même nom (s'il en trouve plusieurs elle doivent être cohérentes.) Dans certains cas, s'il n'a pas besoin de réserver l'espace nécessaire ou d'accéder aux champs, on pourra se passer complètement de la description des champs.

''En pratique,'' on décrit les structures (en entier, avec un nom et les champs) en début de code, en dehors de toute fonction, puis lorque l'on déclare une variable, on omet la description des champs. Voici quelques exemples, toujours avec les listes chaînées:

<source lang="C">
struct s_list
{
  int                   val;
  struct s_list        *next;
};

void add(int x, struct s_list **l)
{
  struct s_list        *tmp;
  tmp = malloc(sizeof (struct s_list));
  tmp->val = x;
  tmp->next = *l;
  *l = tmp;
}

size_t len(struct s_list *l)
{
  size_t                s;
  for (s=0; l; l = l->next)
    s++;
  return s;
}
</source>

L'accès aux champs peut se faire de deux manière:
* la notation ''pointé'': <tt>s.champ</tt> avec <tt>s</tt> une variable représentant directement la structure.
* la notation ''fléché'': <tt>p->champ</tt> avec <tt>p</tt> un pointeur sur une structure.

La seconde notation, <tt>p->champ</tt>, est un ''racourci'' pour la l'expression <tt>(*p).champ</tt>.

===== Structures et tableaux =====

Il existe ''deux sortes'' de tableaux imbriqués dans les structures. En effet, si un champ est un pointeur, on peut l'utiliser comme un tableau mais celui-ci n'est pas inclu dans la structure.

Par contre, on peut également intégrer un tableau explicitement dans la structure, dans ce cas, le contenu du tableau est à l'intérieur de la structure à la position du champ dans la déclaration. Dans ce cas le compilateur se charge de remplacer les références au champ en question soit par le pointeur sur la zone où se trouve le tableaux, s'il est utilisé directement, soit par le décalage opportun lorsqu'il est utilisé comme un tableau.

Prenons un exemple, une structure contenant (au moins) un tableau, la taille de ce tableau est statique (le compilateur doit pouvoir calculer la taille de la structure et les décalages pour l'accès aux champs.)

<source lang="C">
struct s_vect
{
  char                  tab[256];
  size_t                size;
};
</source>

On observe assez simplement que l'adresse correspondant au tableau (affichée avec <tt>printf</tt>) est la même que celle de la structure, la taille du tableau correspond également à notre intuition. Le programme suivant montre ce résultat:

<source lang="C">
/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

struct s_vect
{
  char                  tab[256];
  size_t                size;
};


int main(void)
{
  struct s_vect	       *s;
  s = malloc(sizeof (struct s_vect));

  printf("s:\t%p\ns->tab:\t%p\nsizeof (struct s_vect): %d\n",
	 (void*)s,(void*)(s->tab),sizeof (struct s_vect));

  return (0);
}
</source>

La sortie donnera quelque chose comme:
<pre>
s:      0x28201040
s->tab: 0x28201040
sizeof (struct s_vect): 260
</pre>

On utilise souvent cette forme de tableaux pour accompagner un tableau de données par des ''méta-données'' (informations complémentaires.) En mettant le tableau en fin de structure, on peut jouer sur sa taille au moment de l'allocation pour avoir un tableau dynamique, même si dans ce cas, le calcul de la taille de la structure doit être fait à la main.

<source lang="C">
struct s_matrix
{
  size_t		w, h;
  float			mat[1];
};

struct s_matrix *make_matrix(size_t w, size_t h)
{
  struct s_matrix      *s = NULL;
  size_t		i;

  /* the size of the structure already count one element in the array
     thus we add the place for (w * h - 1) floats. */
  s = malloc(sizeof (struct s_matrix) + (w * h - 1) * sizeof (float));
  s->w = w;
  s->h = h;
  for (i=0; i < w*h; i++)
    s->mat[i] = 0;
  return s;
}

/* Line by line matrix average */
float lbl_avg(struct s_matrix *m)
{
  float			res = 0, tmp;
  size_t		i, j;

  for (i=0; i < m->h; i++)
    {
      tmp = 0;
      for (j = 0; j < m->w; j++)
	tmp += m->mat[j + i * m->w];
      res += tmp/(m->w);
    }
  return (res/(m->h));
}
</source>

==== Union ====

Les types union sont une forme duale des structures: ils permettent de conserver un seul type de donnée parmis plusieurs possibles. Contrairement aux injections (types somme) des langages fonctionnels, il n'existe pas de moyen de savoir quel est le type de la donnée stockée, c'est pourquoi ils sont en général utilisés à l'intérieur de structures accompagnés d'un champ permettant de connaître le type de contenu.

On utilise les unions également pour utiliser une même donnée avec des types différents sans ''cast''.

La syntaxe des unions est sensiblement la même que celle des structures, voici un exemple complet montrant comment utiliser une donnée à la fois comme un entier ou une structure contenant quatre octets:

<source lang="C">
/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

#define DIM 8

struct s_pix
{
  unsigned char		alpha, r, g, b;
};

typedef union
{
  unsigned int		val;
  struct s_pix		argb;
}			t_pixel;

void print_img(t_pixel img[DIM][DIM])
{
  size_t		i, j;

  for (i=0; i < DIM; i++)
    {
      for (j=0; j < DIM; j++)
	{
	  struct s_pix	p;
	  p = img[i][j].argb;
	  printf("(%3hhu,%3hhu,%3hhu) ",p.r,p.g,p.b);
	}
      printf("\n");
    }
}

int main(int argc, char *argv[])
{
  t_pixel		img[DIM][DIM];
  size_t		i, j;
  unsigned long		seed = 42;
  unsigned char		tmp;

  if (argc > 1)
    seed = atoi(argv[1]);

  /* remplissage aléatoire, sans "alpha" */
  srandom(seed);
  for (i=0; i < DIM; i++)
    {
      for (j=0; j < DIM; j++)
	{
	  img[i][j].val = random();
	  img[i][j].argb.alpha = 0;
	}
    }

  print_img(img);

  /* passage en niveau de gris avec "correction gamma" */
  for (i=0; i < DIM; i++)
    {
      for (j=0; j < DIM; j++)
	{
	  tmp = 0.3 * img[i][j].argb.r
	    + 0.59 * img[i][j].argb.g
	    + 0.11 * img[i][j].argb.b;
	  img[i][j].argb.r = img[i][j].argb.g = img[i][j].argb.b = tmp;
	}
    }

  printf("\n");

  print_img(img);

  return (0);
}
</source>

== Compilation ==

La compilation de programme C est assez classique, il est quand même important de faire attention aux options utilisées, notamment l'activation des ''warnings'' et le choix du standard de C utilisé.

Nous utiliserons cette année le compilateur GNU, le fameux <tt>gcc</tt>, mais il existe d'autres compilateurs:

* <tt>icc</tt>: le compilateur Intel
* <tt>pcc</tt>: une résurgance du compilateur ''portable'' développé sur les premiers UNIX (la base de <tt>gcc</tt>.)
* ''TenDRA'': un projet de compilateur validant issue d'un projet militaire.
* ''Sun Studio'': la suite d'outil de compilateur de Sun Microsystem

=== Phases de la compilation ===

La compilation se fait (comme pour tout langage) en plusieurs phases:

# '''Preprocess''' : c'est traitement qui se charge de remplacer les macros, d'inclure les fichiers externes et ainsi que d'autres opérations statiques (sur le code source directement.)
# '''Parsing''' : c'est la phase de transformation du code source vers une représentation machine ''exploitable''.
# '''Analyse sémantique''' : cette phase correspond aux vérifications de types et autres contrôles sémantique du code.
# '''Production de code''' : c'est dans cette phase que le langage source est converti en langage machine (avec quelques intermédiaires) et optimisé.
# '''Édition de liens''' : dans cette phase, le code machine de la phase précédante est ''lié'' pour produire l'exécutable final. Cette phase est aussi là pour regrouper les différents ''modules'' du programme et pour établir les liens vers les bibliothèques dynamiques (qui ne seront chargées qu'à l'usage.)

Les trois premières phases sont en générales effectuées en une seule passe sur chaque fichier séparément, tandis que l'édition de liens se fait une seule fois à la fin.

Il est possible de récupérer le code produit par les phases intermédiaires avec les options appropriés, notamment pour récupérer le code après le passage du préprocesseur (option <tt>-E</tt>), le code assembleur avant la production de la version binaire (option <tt>-S</tt>.)

Si le programme ne contient qu'un seul fichier, il est également possible d'effectuer l'ensemble des passes en une seule fois.

=== Invoquer le compilateur ===

La syntaxe d'appel du compilateur est relativement simple:

<pre>
> gcc <options> [-o <fichier de sortie> <fichiers objets> <fichiers C>]
</pre>

Dans le cas le plus simple, nous avons un simple fichier C (<tt>toto.c</tt>) à compiler:

<pre>
> gcc toto.c
</pre>

Si tout se passe bien, on récupère un exécutable nommé <tt>a.out</tt>. Si on veut nommer notre programme, on peut utiliser l'option <tt>-o</tt> suivie du nom du fichier à produire:

<pre>
> gcc toto.c -o toto
</pre>

En règle générale, on utilise un certain nombre d'options classiques pour activer un maximum de ''warnings'', choisir la version de C que l'on veut utiliser et activer le niveau d'optimisation. Les options ''usuelles'' (à l'EPITA) que nous utiliserons cette année sont les suivantes: <tt>-O2 -W -Wall -Werror -pedantic</tt>.

* <tt>-O2</tt>: active le second niveau d'optimisation (ainsi que certains messages d'erreurs suplémentaires.)
* <tt>-Wall</tt>: active les ''warnings'' classiques
* <tt>-W</tt>: active les ''warnings'' suplémentaires (synonyme de <tt>-Wextra</tt>.)
* <tt>-Werror</tt>: les ''warnings'' sont traités comme des erreurs.
* <tt>-pedantic</tt>: le nom parle de lui même ...

Si on veut faire du ''C89'' on peut ajouter l'option <tt>-ansi</tt>, pour activer le standard ''C99'' on peut utiliser l'option <tt>-std=c99</tt>.

Attention, l'option <tt>-ansi</tt> active des restrictions sur le langage et sur l'API de la bibliothèque standard (''libC''.) Par exemple, le programme sur les unions dans la section précédante utilisent des ''flags'' de <tt>printf</tt> qui ne sont pas dans le standard ''C89''.

La ligne de compilation avec l'ensemble des options est un peu ''longue'', on peut utiliser <tt>make</tt> (sans <tt>Makefile</tt>) pour simplifier les appels au compilateur. <tt>make</tt> dispose d'une règle par défaut pour engendrer un executable à partir du fichier C correspondant. Cette règle utilise deux variables qui peuvent être modifier: <tt>CC</tt> (le nom du compilateur) et <tt>CFLAGS</tt> (les options.) Les définitions dans le <tt>Makefile</tt> ressemble à l'extrait suivant:

<source lang="make">
.SUFFIXES: .c

.c:
	${CC} ${CFLAGS} $< -o $@

</source>

Il suffit donc de renseigner ces deux variables, voici un exemple de session sur un shell de type ''sh'' (<tt>zsh</tt>, <tt>ksh</tt> ou <tt>bash</tt>):

<pre>
> export CC=gcc
> export CFLAGS="-O2 -W -Wall -Werror -pedantic"
> ls
toto.c
> make toto
gcc -O2 -W -Wall -Werror -pedantic toto.c -o toto
>
</pre>

En <tt>tcsh</tt>, on manipule les variables de cette manière:

<pre>
> setenv CC gcc
> setenv CFLAGS "-O2 -W -Wall -Werror -pedantic"
</pre>

Vous pourrez ajouter ces variables dans la configuration de votre shell.

Si vous souhaitez ''debugger'' votre code avec <tt>gdb</tt>, il faut ajouter de l'information suplémentaire à l'aide de l'option <tt>-g</tt>. <tt>gdb</tt> est très utile pour ''chasser'' les bugs de votre programme, prennons par exemple ce petit bout de code qui ''segfault'':

<source lang="C">
/*
 * segfault.c : messup with pointer  *
 */

/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

int main(void)
{
  int		       *p = NULL;

  *p = 42;

  printf("*p = %d\n",*p);

  return (0);
}
</source>

Ce qui donne à l'exécution:

<pre>
> make segfault
gcc -W -Wall -Werror -ansi -pedantic -g  segfault.c  -o segfault
> ./segfault
Segmentation fault
</pre>

On peut utiliser <tt>gdb</tt> pour retrouver le point du programme incriminé:

<pre>
> gdb segfault
GNU gdb 6.1.1 [FreeBSD]
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-marcel-freebsd"...
(gdb) r
Starting program: /usr/home/feanor/Enseignement/Epita/Prog/CoursWIKI/Programmation:C/Examples/segfault 

Program received signal SIGSEGV, Segmentation fault.
0x0804841b in main () at segfault.c:14
14	  *p = 42;
(gdb) c
Continuing.

Program terminated with signal SIGSEGV, Segmentation fault.
The program no longer exists.
(gdb) quit
>
</pre>

=== Fichiers En-tête et compilation séparée ===

Si vous avez besoin de diviser votre code en plusieurs fichiers, la combinaison de l'édition de lien et du préprocesseur, vous permet de construire un projet sous forme modulaire.

Avant la phase d'édition de liens, seules les informations de typage sont nécessaires à la compilation du code, donc les prototypes des fonctions et les définitions de types. L'usage est de regrouper (pour chaqu'un des fichiers C du projet) ces définitions dans un fichier d'en-tête (d'extension <tt>.h</tt>.)

Chaque fichier C incluera les en-têtes nécessaires et sera compilé indépendament avec l'option <tt>-c</tt> pour produire le code binaire intermédiaire (fichier d'extension <tt>.o</tt>.)

Le plus simple est de prend un exemple:

<source lang="C">
/*
 * list.h : linked lists header *
 */

/* to prevent multiple inclusion */
#ifndef _LIST_H
#define _LIST_H

typedef struct s_list	       *t_list;
struct s_list
{
  int			val;
  t_list		next;
};

/* size of list struct */
#define LIST_SIZE (sizeof (struct s_list))

/* Macro for operations on empty list */
#define list_empty() (NULL)
#define list_is_empty(l) (!(l))

/* Operations' Prototypes */

/* add(x,l): head insert x in l */
t_list add(int x, t_list l);

/* rev(l) : reverse list l */
/* return a fresh new list */
t_list rev(t_list l);

/* macro for next element */
#define next(l) ((l) = (l)->next)

#endif
</source>

 

<source lang="C">
/*
 * list.c : linked lists implementation *
 */

/* Standard headers */
#include <stdlib.h>
#include <unistd.h>

/* module's header */
#include "list.h"

t_list add(int x, t_list l)
{
  t_list		tmp;
  tmp = malloc(LIST_SIZE);
  tmp->val = x;
  tmp->next = l;
  return tmp;
}

t_list rev(t_list l)
{
  t_list		tmp;
  for (tmp=NULL; l; l = l->next)
    tmp = add(l->val,tmp);
  return tmp;
}
</source>

 

<source lang="C">
/*
 * main.c: list examples *
 */

/* Standard headers */
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>

/* module's header */
#include "list.h"

int main(int argc, char *argv[])
{
  t_list		l, l2, tmp;
  size_t		i, seed=42, size=5;

  if (argc>1)
    seed = atoi(argv[1]);
  srandom(seed);

  if (argc>2)
    size = atoi(argv[2]);

  l = list_empty();
  for (i=0; i<size; i++)
    l = add(random()%32,l);

  printf("l = [");
  for (tmp = l; !list_is_empty(tmp); next(tmp))
    printf("%d; ", tmp->val);
  printf("]\n");

  l2 = rev(l);

  printf("rev(l) = [");
  for (tmp = l2; !list_is_empty(tmp); next(tmp))
    printf("%d; ", tmp->val);
  printf("]\n");

  exit(0);
}
</source>

 
 
<source lang="make">
# Makefile for example
CFLAGS= -O2 -W -Wall -Werror -ansi -pedantic
CC=gcc

all: list_ex

list_ex: list.o main.o
	${CC} ${CFLAGS} $> -o $@

clean::
	rm -f *~ *.o
	rm -f list_ex

#
# END
#
</source>

La compilation et l'exécution de ce programme nous donne les résultats suivants:

<pre>
> make
gcc -O2 -W -Wall -Werror -ansi -pedantic -c list.c
gcc -O2 -W -Wall -Werror -ansi -pedantic -c main.c
gcc -O2 -W -Wall -Werror -ansi -pedantic list.o main.o -o list_ex
> ./list_ex
l = [4; 9; 17; 4; 6; ]
rev(l) = [6; 4; 17; 9; 4; ]
>
</pre>

== Premiers Exemples ==

Pour compiler les exemples suivants, vous pouvez fixer votre environnement pour que <tt>make</tt> compile directement vos programmes avec les options de compilations que nous utilisons.

Ajout des variables dans l'environnement si vous utilisez <tt>bash</tt> ou <tt>zsh</tt>:
<source lang="bash">
export CFLAGS="-O2 -W -Wall -Werror -ansi -pedantic"
export CC=gcc
</source>

Ajout des variables dans l'environnement si vous utilisez <tt>tcsh</tt>:
<source lang="bash">
setenv CFLAGS "-O2 -W -Wall -Werror -ansi -pedantic"
setenv CC gcc
</source>

Maintenant, si votre programme se trouve dans le fichier <tt>foo.c</tt>, vous pouvez obtenir le programme <tt>foo</tt> avec la commande suivante:

<pre>
> ls
foo.c
> make foo
gcc -O2 -W -Wall -Werror -ansi -pedantic foo.c -o foo
> ls
foo	foo.c
> ./foo
...
</pre>

=== Bases ===

==== <tt>Hello World!</tt> ====

<source lang="C">
/*
 * 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);
}
</source>

 

<source lang="C">
/*
 * hello.c : traditional "Hello World" prog *
 * using write(2)                           *
 */

/* Standard headers */
#include <unistd.h>
#include <stdlib.h>

int main(void)
{
  write(STDOUT_FILENO, "Hello World!\n", 13);
  return (0);
}
</source>

==== Factorielle ====

<source lang="C">
/*
 * fact.c : integer factorial *
 * recursive version          *
 */

/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

/* we use unsigned integer to avoid negative numbers issues */
size_t fact(size_t n)
{
  if (n)
    return (n * fact(n-1));
  else
    return 1;
}

/* we use main arguments to retrieve a test value */
int main(int argc, char *argv[])
{
  /* if no arg is provided, we compute fact(5) */
  size_t		n=5;

  if (argc > 1)
    n = atoi(argv[1]);

  printf("fact(%d) = %u\n",n,fact(n));
  return 0;
}
</source>

 

<source lang="C">
/*
 * fact.c : integer factorial *
 * iterative version          *
 */

/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

/* we use unsigned integer to avoid negative numbers issues */
size_t fact(size_t n)
{
  size_t		res = 1;
  while (n)
    res *= n-- ;
  return res;
}

/* we use main arguments to retrieve a test value */
int main(int argc, char *argv[])
{
  /* if no arg is provided, we compute fact(5) */
  size_t		n=5;

  if (argc > 1)
    n = atoi(argv[1]);

  printf("fact(%d) = %u\n",n,fact(n));
  return 0;
}
</source>

 

<source lang="C">
/*
 * fact.c : integer factorial *
 * recursive one line version *
 */

/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

/* we use unsigned integer to avoid negative numbers issues */
size_t fact(size_t n)
{
  return (n ? n * fact(n-1) : 1);
}

/* we use main arguments to retrieve a test value */
int main(int argc, char *argv[])
{
  /* if no arg is provided, we compute fact(5) */
  size_t		n=5;

  if (argc > 1)
    n = atoi(argv[1]);

  printf("fact(%d) = %u\n",n,fact(n));
  return 0;
}
</source>

=== Chaînes de caractères ===

<source lang="C">
/* mystrings.c : string fonctions */

/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

size_t my_strlen(char *s)
{
  size_t		res;
  for (res=0; s[res]; res++);
  return res;
}

/* one line recursive version */
size_t mystrlen(char *s)
{
  return (*s?1+mystrlen(s+1):0);
}

char *my_strncpy(char *dst, char* src, size_t len)
{
  size_t		i;

  /* first copy */
  for (i=0; src[i] && i<len; i++)
    dst[i] = src[i];

  /* if necessary, fill the trailling space with 0 */
  while (i<len)
    dst[i++] = 0;

  return dst;
}

int main(int argc, char *argv[])
{
  char	       *s = "toto";
  char		d[256];

  if (argc > 1)
    s = argv[1];

  /* Compare strlen with libC's one */
  printf("strlen(\"%s\") = %d\n", s, strlen(s));
  printf("my_strlen(\"%s\") = %d\n", s, my_strlen(s));
  printf("mystrlen(\"%s\") = %d\n", s, mystrlen(s));

  /* Copy string */
  my_strncpy(d, s, my_strlen(s) + 1);
  printf("d = \"%s\"\n",d);
  return 0;
}
</source>

 

<source lang="C">
/* Fun with char */

#define CAPS ('a' - 'A')

void uppercase(char *s)
{
  size_t		i;
  for (i=0; s[i]; i++)
    if (s[i] >= 'a' && s[i] <= 'z')
      s[i] -= CAPS;
}

void lowercase(char *s)
{
  size_t		i;
  for (i=0; s[i]; i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
      s[i] += CAPS;
}
</source>

=== Listes chaînées ===

<source lang="C">
/* list.c : integer linked lists */

/* Standard headers */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

/* type description */
typedef struct s_list  *t_list;
struct s_list
{
  int			val;
  t_list		next;
};

/* some classical operations */

#define empty_list() NULL
#define is_empty(l) (!(l))

size_t len(t_list l)
{
  size_t		s=0;
  for (;l; l = l->next)
    s++;
  return s;
}

t_list add(int x, t_list l)
{
  t_list		t = NULL;

  t = malloc(sizeof (struct s_list));
  t->next = l;
  t->val = x;
  return t;
}

t_list rev(t_list l)
{
  t_list		r;

  for (r = NULL; l; l = l->next)
    r = add(l->val, r);
  return r;
}

/* tests */

t_list random_list(size_t s)
{
  return (s?add(random()%32,random_list(s-1)):NULL);
}

void print_list(t_list l)
{
  printf("[");
  for (;l;l = l->next)
    printf("%i; ", l->val);
  printf("]\n");
}

int main(int argc, char *argv[])
{
  t_list		l, l2;
  size_t		s = 5;

  if (argc>1)
    s = atoi(argv[1]);

  l = random_list(s);
  printf("l = ");
  print_list(l);
  printf("len(l) = %i\n",len(l));
  l2 = rev(l);
  printf("l2 = rev(l)\nl2 = ");
  print_list(l2);
  printf("len(l2) = %i\n",len(l2));
  return 0;
}
</source>

== Conclusion ==

== Référence ==

<references />

[[Category:EPITA:Cours:cours20092010]]
[[Category:EPITA:Cours:Programmation]]
{| style="background-color: #f9ffff; border: 1px solid #c0c0c0" cellspacing="0" cellpadding="8" width="100%"
! style="background-color: #f9ffff; border: 1px solid #c0c0c0" | Cours !! style="background-color: #f9ffff; border: 1px solid #c0c0c0" | Partie
|-  style="background-color: #f9ffff; border: 1px solid #c0c0c0"
| style="background-color: #f9ffff; border: 1px solid #c0c0c0" | Cours de Programmation EPITA/spé
| style="background-color: #f9ffff; border: 1px solid #c0c0c0" | [[Programmation:C]]
|}