Informatique et recherche
opérationnelle
IFT2030

Concepts des langages de programmation

Automne 2002


Accueil

Professeur et
Démonstrateurs

Horaires et locaux

Notes de cours

Démonstrations
et devoirs

Examens

Liens utiles

Au sujet du
livre de cours

Consultez vos notes

Foire aux questions
(FAQ)

Démonstration 2: Introduction moins légère au langage C

Note: le texte qui précède les exercices (et donc qui suit) provient d'une planche de démonstration d'une session précédante.


NOTIONS ADDITIONNELLES

Mot-clé sizeof:
    sizeof(t) /* vaut la longueur en octet du type t */

Typecasting(Conversion de types):
    float a=1.2;
    int b;
    char *ptr1=get_ptr();
    int *ptr2;
    b=(int)a;    /* b=1 */
    ptr2=(int *)ptr1; /* même emplacement que ptr1, mais maintenant
                         considéré comme pointant sur des entiers */


OPÉRATIONS SUR LES FICHIERS

    Nous étudierons les streams en C, qui sont définis dans stdio.h.

Le pointeur fichier:
    Le pointeur fichier, de type FILE *, est utilisé pour accéder aux fichiers, il pointe vers une structure qui contient plusieurs informations à propos du fichier en question.
    FILE *ap;

Ouverture d'un fichier:
    Pour ouvrir un fichier, on utilisera la fonction fopen, qui prend deux chaînes de caractères en paramètres, soient le nom du fichier et des instructions de contrôle. Cette fonction retourne un pointeur fichier.
    ap=fopen("test.txt","rt");
    Ici, on ouvre le fichier test.txt dans le répertoire courant, avec les options r et t qui signifient lecture en mode texte et pointeur au début du fichier. Si une erreur système survient(par exemple, le fichier n'existe pas), le pointeur retourné sera NULL. Il est donc préférable de prévoir cette éventualité lors de la composition de nos programmes.
-Options disponibles:
    -Option obligatoire(une seule):
    r    Ouvrir en lecture, position début
    w    Ouvrir en écriture, position début(destruction si fichier existant)
    a    Ouvrir en écriture, position fin
    -Suffixes optionnels(un seul), inutile sur UNIX:
    b    Mode binaire(ignoré par certains compilateurs)
    t    Mode texte(certains compilateurs seulement)
    -Spécial:
    +    Mode ajournement (lecture et écriture permises).
Fermeture d'un fichier:
    Pour fermer un fichier ouvert, on utilise:
    fclose(ap);
    La fermeture d'un fichier permet de finaliser les opérations qui l'ont affecté, par exemple, les systèmes munis de write-behind pourront vider leurs tampons. Un bon programme ferme tout fichier dont il ne se sert plus(ou ne se servira pas avant longtemps).
Opérations de lecture:
    fgetc(ap) /* lis un caractère et le retourne(EOF si impossible) */
    fgets(buf,n,ap) /* lis n caractères dans buf et retourne
                       buf(NULL si impossible) */
    fread(buf,size,n,ap) /* lis n éléments de longueur size dans buf
                            et retourne le nombre d'éléments lus */
    On peut aussi utiliser fscanf(ap,format,...); qui lira les éléments selon le format fournis, semblable à prinft.
-Exemple:
    fscanf(ap,"%d %s\n",&i,str);
    Ici, on lira un entier, suivi d'un espace, suivi d'une chaine de caractères, suivi du newline. L'entier i et la chaîne str seront changés en conséquence. fscanf retourne le nombre d'élément qu'elle a réussi à "matcher", ou EOF si la fin du fichier est atteinte avant d'avoir fini.
Opérations d'écriture:
    fputc(ap) /* écris un caractère(retourne EOF si impossible) */
    fputs(str,ap) /* écris la chaine str(retourne EOF si impossible) */
    fwrite(buf,size,n,ap) /* écris n éléments de longueur size dans buf
                             et retourne le nombre d'éléments écrits */
    fprintf(ap,format,...) /* comme printf, mais dans le fichier */


ALLOCATION DYNAMIQUE

    L'allocation de grands tableaux ou de structures à taille variable(telles les listes), doit souvent se faire dynamiquement. Les deux fonctions principales à utiliser sont:
    void *malloc(int size);
    void free(void *ptr);
    Avec malloc, vous pouvez allouer de l'espace mémoire en spécifiant la taille en octets. La fonction retourne un pointeur vers cet espace mémoire, ou NULL si le système ne peut vous allouer cet espace. Il est préférable de prévoir cette éventualité. Exemple:
    int *tableau;
    /* On veut un tableau de 10000 entiers */
    tableau=(int *)malloc(10000*sizeof(int));
    if(tableau==NULL) printf("Pas assez de mémoire!");
    else {...}
    Avec free, vous pouvez désallouer de l'espace mémoire en spécifiant un pointeur vers cet emplacement. ATTENTION, comme C passe ses arguments par valeur, le pointeur pointe toujours vers cet emplacement, même après la désallocation! Il est primordial d'être conscient que l'utilisation de ce pointeur inchangé par la suite peut causer des erreurs système! Une bonne pratique est de changer la valeur du pointeur juste après le free, soit vers un autre emplacement valide ou soit par NULL, afin de bien identifier ce pointeur comme étant non utilisable. Exemple:
    free(tableau);tableau=NULL;

ARITHMÉTIQUE DE POINTEURS

    Les pointeurs sont des adresses d'espace mémoire, il peut être utile de les incrémenter, de les comparer, etc.
    int val;
    int *ptr1,**ptr2,*ptr3[10];
    int tab1[10],tab2[20][10];
    Description des éléments présentés:
    val    un entier
    ptr1   un pointeur sur un entier
    ptr2   un pointeur sur un pointeur sur un entier
    ptr3   tableau de 10 pointeurs sur des entiers
    tab1   tableau de 10 entiers
    tab2   tableau de 20 tableaux de 10 entiers
    Pour obtenir l'adresse d'une variable(toutes les variables ont une adresse, seules les adresses des constantes, bien qu'existantes, ne peuvent en principe être obtenues) nous utilisons le préfixe &, juste avant le nom de la variable. Pour accéder à la case mémoire pointée par un pointeur, nous utilisons le préfixe *. L'accès aux éléments d'un tableau se fait en ajoutant un indexe entre brackets. Exemple:
    ptr1=&val;    /* ptr1 pointe sur l'entier val */
    *ptr1=2;      /* val est égal à 2 maintenant  */
    val=tab1[2];  /* val est égal au 3e élément de tab1  */
    Au niveau des calculs sur les pointeurs, le type d'objet pointé est très important. Un exemple:
    char c[10],*ptr1=c;    /* ptr1 pointe sur le premier élément de c */
    int *ptr2=(int *)ptr1; /* ptr2 pointe la même place */
    /* Ici, ptr1==ptr2 */
    ptr1++;ptr2++;
    /* Ici, ptr1!=ptr2 !!!! */
    Il faut bien voir que lorsque l'on ajoute un entier à un pointeur, le compilateur le considère comme un index, alors au lieu d'incrémenter de 1 l'adresse, il incrémente de sizeof(T) où T* est le type du pointeur. Cela correspond à pointer vers le prochain caractère pour ptr1 et vers le prochain entier pour ptr2, c'est très pratique dans certaines situations. En général, si p est un pointeur, i un entier, *T le type de p, Alors p+i est égal à la valeur de p plus i multiplié par sizeof(T). Examinez les deux fonctions suivantes:
    /* Presence d'un entier i dans un tableau de n>0 entiers */
    int present_idx(int i,int *tableau,int n)
    {
        int idx=0;
        while(tableau[idx]!=i && idx<n-1) idx++;
        return tableau[idx]==i;
    }
    /* Presence d'un entier i dans un tableau de n>0 entiers */
    int present_ptr(int i,int *tableau,int n)
    {
        int *ptr=tableau,*limit=&tableau[n-1];
        while(*ptr!=i && ptr<limit) ptr++;
        return *ptr==i;
    }
   L'avantage d'utiliser la version avec les pointeurs, c'est qu'elle est plus rapide. En effet, la version avec index doit calculer sizeof(int)*idx à chaque itération, contrairement à la version pointeur, qui n'effectue aucune multiplication. Par contre, l'avantage d'utiliser la version avec index est qu'elle est plus claire et lisible. À vous de faire le choix!

Notes sur les tableaux:

    La notation (tab1[i]) est équivalente à la notation (*(tab1+i)), en autant que i soit un entier. Il en découle donc qu'elle est aussi équivalente à la notation i[tab1], ce qui implique dans notre exemple que 2[tab1] évalue lui aussi au 3e élément du tableau.

    Il n'est pas tout à fait exact de prétendre qu'un tableau est un pointeur vers son premier élément. En fait, un tableau n'est représenté en mémoire que par ses éléments, les uns à la suite des autres. À la différence d'un pointeur qui est représenté en mémoire par un entier(adresse) pointant vers un élément. Donc, la variable ptr1 possède une case mémoire, accessible avec &ptr1, qui contient une adresse. De son coté, tab1 n'est pas une variable proprement dite,  dans le sens où l'expression (tab1) évalue à l'adresse du premier élément(&tab1[0]), mais cette valeur retournée n'a pas d'adresse, c'est une r-value. Puisque la "variable" tab1 n'a pas d'adresse, la plupart des compilateurs posent (&tab1)=(tab1). Avec cc, vous aurez un avertissement vous le spécifiant(& before "tab1" is ignored) .

    Quant à tab2, un tableau de tableaux, il n'est représenté en mémoire que par ses 20 tableaux de 10 entiers, les uns à la suite des autres, pour un total de 200 cases mémoires contigües. Encore ici, la valeur de l'expression (tab2) est l'adresse du premier élément(numériquement, tab2=&tab2=tab2[0]=&tab2[0]=&tab2[0][0]). Pour montrer que tab2 n'est vraiment pas une variable ordinaire, l'expression (*tab2), bien que tab2 soit l'adresse du premier élément, ne correspond pas au contenu de la première case du tableau, mais évalue numériquement à la même chose que tab2, ce n'est que le type qui change et est maintenant un tableau d'entier à une dimension. Il est important de noter cette différence de comportement pour l'opérateur d'indirection selon que c'est un pointeur(ou un tableau unidimensionnel) ou un tableau multi-dimensionel.

    Il faut bien être conscient que le programme qui roule n'a que les éléments en mémoire et qu'il n'a aucune idée de combien il y en a. La clé est dans le type des éléments. Pour calculer la vraie adresse de la case tab2[12][5], qui est équivalent à calculer (*(tab2+12)+5), c'est le type de tab2 qui déterminera par quoi l'index 12 devra être multiplié, dans le cas présent c'est 10*sizeof(int), puisque les éléments de tab2 sont de type int[10], des tableaux de 10 entiers. Donc cette information(le type des éléments) doit être connue pour passer un tableau en paramètre, et nous avons vu que le nombre d'éléments fait partie intégrante du type à ce niveau. Il est donc essentiel, pour passer un tableau en paramètre, de spécifier la taille des éléments, sauf pour la première dimension(inutile dans le calcul). Plus spécifiquement:
    void foo1(char tab[][][])
    {tab[1][2][0]='a';}    /* Illégal, impossible de calculer l'adresse */
    void foo2(char *tab)
    {tab[1][2][0]='a';}    /* Illégal, impossible de calculer l'adresse */
    void foo3(char tab[][3][3])
    {tab[1][2][0]='a';}    /* Légal */
    void foo4(char ***tab)
    {
      tab[1][2][0]='a';    /* Légal, mais segmentation fault fort probable si
                              l'appel à été fait avec un tableau a 3 dimensions
                              de type char [X][Y][Z] */
      /* les types de pointeurs successifs n'auront pas la bonne information
         pour calculer la bonne adresse */
    }
    main()
    {
        char tableau[3][3][3];
        foo3(tableau);
        foo4(tableau);    /* Risque fortement de planter! */
    }

    Pour généraliser, voici les règles concernant les opérateurs *,& et [], selon le type de l'opérande(note:T est un type quelconque qui n'est pas un tableau):
 

Type de x expr Type de expr Valeur de expr
T x T Valeur de la variable x
T &x T * Adresse de la variable x
T * x T * Valeur numérique du pointeur x(une adresse)
T * *x T Case mémoire à l'adresse x
T * &x T ** Adresse du pointeur x
T * x[i] T Case mémoire à l'adresse (x + i*sizeof(T))
T[N] x T[N] Adresse du premier élément du tableau
T[N] *x T Case mémoire à l'adresse x
T[N] &x T[N] Même chose que x
T[N] x[i] T Case mémoire à l'adresse (x + i*sizeof(T))
T[A1][A2]...[An] x T[A1][A2]...[An] Adresse du premier élément du tableau
T[A1][A2]...[An] *x T[A1][A2]...[An-1] Même chose que x
T[A1][A2]...[An] &x T[A1][A2]...[An] Même chose que x
T[A1][A2]...[An] x[i] T[A1][A2]...[An-1] x + i*A2*A3*...*An*sizeof(T)
 
Conversion de représentation tableau vers indirections(pointeurs):
    Soient les déclarations suivantes:
T tab1[N];
T tab2[N][M];
T *ptr1;
T **ptr2;

    L'affectation avec typecast ptr1=(T *)tab1 est tout à fait légale et utile, puisque ptr1 pointe maintenant sur la case mémoire du premier élément de tab1, l'opérateur [] sur ptr1 donne les même résultats que ceux qu'il donnait sur tab1. Il faut comprendre que tab1 est une chaîne de T et ptr1 est un pointeur sur le premier élément de cette chaîne. Mais je répète: tab1 n'est pas tout à fait équivalent à ptr1. Quoique leur évaluation donne la même valeur numérique, c'est leurs types qui sont fondamentalement différents.

    La conversion du tableau tab2 vers la représentation T ** est moins simple, voici comment on pourrait la faire:
ptr2=(T **)malloc(N*sizeof(T *));
for(i=0;i<N;i++)
  ptr2[i]=(T *)tab2[i];
/* Après ce bout de code, ptr2[x][y] est le même élément que tab2[x][y] */

    On voit donc clairement le fait que pour les chaînes multi-dimensionnelles représentées par des pointeurs, l'information pour accéder aux éléments est dynamique et en mémoire(chaînes de pointeurs), tandis que pour celles représentées par des tableaux multi-dimensionnels, l'information est statique et réside dans le type du tableau. Les avantages d'utiliser le type tableau pour les chaînes multi-dimensionnelles est un gain potentiel de rapidité dans l'accès aux éléments et la nature automatique de l'allocation, mais son plus gros désavantage est que sa taille est fixe et ne peut être définie ou changée dynamiquement.


Travail pratique (pas noté mais fortement recommandé)

Liste chaînée de structures

Définissez une structure Personne abritant les informations suivantes:
  • nom et prénom (char *),
  • âge (int)
Notez que les champs des structures existantes devront être alloués dynamiquement en fonction des besoins (en clair: si votre programme doît créer une Personne ayant pour nom Tremblay seuls 9 caractères sont nécessaires (8 pour le nom, plus le caractère de fin de chaîne)).

Le but de cet exercice est de vous faire coder les méthodes de gestion d'une liste chaînée de Personnes que vous allez utiliser pour maintenir une base de Personnes.

Écrivez un programme qui propose en boucle à l'utilisateur le menu suivant:

1- Ajouter une Personne dans la base
2- Supprimer une Personne dans la base
3- Chercher une Personne dans la base
4- Trier les Personnes de la base en ordre alphabétique
5- Trier les Personnes de la base en ordre croissant d'âge
6- Afficher les Personnes de la base
7- Quitter l'application

Votre code sera plus simple si vous écrivez des fonctions spécifiques pour gérer l'allocation dynamique d'une fiche Personne ainsi que la destruction d'une telle fiche. Ces méthodes seront systématiquement appelées respectivement lors de l'ajout d'une Personne et lors de sa destruction.

Vous prendrez soin à ce que la mémoire soit restituée complétement à la fin du programme (destruction complète de la liste et des champs de chaque structure).

[top]


Dernière mise à jour : Fri Sep 20 02:10:57 EDT 2002
dift2030@iro.umontreal.ca