Tableaux, enregistrements et fonctions en langage C

Corrigé de l'exercice 1

#include <stdio.h>

#define MAX 100

int main(void)
{
    int tab[MAX];
    int n, i;

    printf("Nombre d'elements (1 a %d) : ", MAX);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX) {
        printf("Taille invalide.\n");
        return 1;
    }

    for (i = 0; i < n; i++) {
        printf("tab[%d] = ", i);
        scanf("%d", &tab[i]);
    }

    printf("Tableau inverse : ");
    for (i = n - 1; i >= 0; i--)
        printf("%d ", tab[i]);
    printf("\n");

    return 0;
}

Deux points méritent attention. D'abord l'indexation : un tableau de n cases va de l'indice 0 à n-1. La boucle d'affichage part donc de n-1 et descend jusqu'à 0 inclus, d'où la condition i >= 0.

Ensuite la taille : en C, un tableau statique doit avoir une taille connue à la compilation. On réserve donc MAX cases et on n'en utilise que n. Sans le test sur n, une saisie de 500 déborderait du tableau : l'erreur la plus courante, et la plus difficile à diagnostiquer.

Corrigé de l'exercice 2

#include <stdio.h>

#define MAX 100

int main(void)
{
    float tab[MAX];
    float somme = 0.0f, min, max;
    int n, i;

    printf("Nombre de valeurs : ");
    scanf("%d", &n);
    if (n < 1 || n > MAX) {
        printf("Taille invalide.\n");
        return 1;
    }

    for (i = 0; i < n; i++) {
        printf("Valeur %d : ", i + 1);
        scanf("%f", &tab[i]);
    }

    /* on part du premier element, jamais de 0 :
       sinon un tableau de valeurs negatives donnerait un maximum faux */
    min = max = tab[0];
    for (i = 0; i < n; i++) {
        somme += tab[i];
        if (tab[i] < min) min = tab[i];
        if (tab[i] > max) max = tab[i];
    }

    printf("Somme   : %.2f\n", somme);
    printf("Moyenne : %.2f\n", somme / n);
    printf("Minimum : %.2f\n", min);
    printf("Maximum : %.2f\n", max);

    return 0;
}

L'initialisation de min et max est le piège de cet exercice. Les initialiser à 0 paraît naturel, mais sur un tableau comme {-5, -2, -9} le maximum resterait 0, une valeur absente du tableau. On part donc toujours du premier élément.

Noter aussi somme / n : somme étant un float, la division est réelle. Si les deux opérandes étaient des entiers, le C ferait une division entière et la moyenne de 5 et 2 vaudrait 3 au lieu de 3,5.

Corrigé de l'exercice 3

#include <stdio.h>

#define MAX 100

int recherche(const int tab[], int n, int valeur)
{
    int i;
    for (i = 0; i < n; i++)
        if (tab[i] == valeur)
            return i;        /* trouve : on sort aussitot */
    return -1;               /* parcours complet, rien trouve */
}

int main(void)
{
    int tab[MAX];
    int n, i, x, pos;

    printf("Taille : ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("tab[%d] = ", i);
        scanf("%d", &tab[i]);
    }

    printf("Valeur cherchee : ");
    scanf("%d", &x);

    pos = recherche(tab, n, x);
    if (pos == -1)
        printf("%d est absent du tableau.\n", x);
    else
        printf("%d se trouve a l'indice %d.\n", x, pos);

    return 0;
}

Le return i à l'intérieur de la boucle arrête la fonction dès la première occurrence : inutile de parcourir le reste. C'est pour cela que la fonction renvoie la première position.

Le const devant int tab[] annonce que la fonction ne modifiera pas le tableau. Ce n'est pas obligatoire, mais le compilateur refusera alors toute écriture dedans : une erreur de moins.

Enfin, -1 est un bon code d'absence parce qu'aucun indice valide ne peut valoir -1. Renvoyer 0 serait ambigu : 0 est l'indice de la première case.

Corrigé de l'exercice 4

#include <stdio.h>

int dichotomie(const int tab[], int n, int valeur)
{
    int debut = 0, fin = n - 1, milieu;

    while (debut <= fin) {
        /* ecriture sure : debut + (fin - debut) / 2 evite le depassement
           que produirait (debut + fin) / 2 sur de tres grands indices */
        milieu = debut + (fin - debut) / 2;

        if (tab[milieu] == valeur)
            return milieu;
        else if (tab[milieu] < valeur)
            debut = milieu + 1;   /* la valeur est a droite */
        else
            fin = milieu - 1;     /* la valeur est a gauche */
    }
    return -1;
}

int main(void)
{
    int tab[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(tab) / sizeof(tab[0]);
    int x, pos;

    printf("Valeur cherchee : ");
    scanf("%d", &x);

    pos = dichotomie(tab, n, x);
    if (pos == -1)
        printf("%d est absent.\n", x);
    else
        printf("%d se trouve a l'indice %d.\n", x, pos);

    return 0;
}

À chaque tour, la moitié du tableau restant est écartée. Pour 1 000 éléments, 10 comparaisons suffisent là où la recherche séquentielle en demanderait 1 000 dans le pire cas : on passe de O(n) à O(log n).

sizeof(tab) / sizeof(tab[0]) calcule le nombre d'éléments : taille totale divisée par la taille d'un élément. Attention, cette astuce ne marche que là où le tableau est déclaré. Passé à une fonction, il se réduit à un pointeur et sizeof renverrait la taille du pointeur.

La dichotomie exige un tableau trié. Sur un tableau quelconque, elle rend des résultats faux sans rien signaler.

Corrigé de l'exercice 5

#include <stdio.h>

#define MAX 100

/* renvoie 1 si valeur figure deja dans les n premieres cases de tab */
int existe(const int tab[], int n, int valeur)
{
    int i;
    for (i = 0; i < n; i++)
        if (tab[i] == valeur)
            return 1;
    return 0;
}

int main(void)
{
    int tab[MAX], sans_doublon[MAX];
    int n, i, nb = 0;

    printf("Taille : ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("tab[%d] = ", i);
        scanf("%d", &tab[i]);
    }

    for (i = 0; i < n; i++)
        if (!existe(sans_doublon, nb, tab[i]))
            sans_doublon[nb++] = tab[i];

    printf("Sans doublon (%d valeurs) : ", nb);
    for (i = 0; i < nb; i++)
        printf("%d ", sans_doublon[i]);
    printf("\n");

    return 0;
}

La variable nb joue deux rôles : elle compte les valeurs déjà retenues et donne l'indice de la prochaine case libre. sans_doublon[nb++] = tab[i] écrit dans la case nb puis incrémente nb, c'est la post-incrémentation.

On cherche dans sans_doublon, pas dans tab : la question est « ai-je déjà gardé cette valeur ? », pas « apparaît-elle plusieurs fois ? ».

Le coût est en O(n²), puisque chaque élément est comparé à tous ceux déjà retenus. Sur un tableau trié, un simple parcours comparant chaque élément au précédent suffirait, en O(n).

Corrigé de l'exercice 6

#include <stdio.h>

void fusion(const int a[], int na, const int b[], int nb, int c[])
{
    int i = 0, j = 0, k = 0;

    /* tant que les deux tableaux ont encore des elements */
    while (i < na && j < nb) {
        if (a[i] <= b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }

    /* un seul des deux restes s'execute reellement */
    while (i < na) c[k++] = a[i++];
    while (j < nb) c[k++] = b[j++];
}

int main(void)
{
    int a[] = {1, 4, 7, 12};
    int b[] = {2, 3, 9, 15, 20};
    int na = sizeof(a) / sizeof(a[0]);
    int nb = sizeof(b) / sizeof(b[0]);
    int c[20];
    int k;

    fusion(a, na, b, nb, c);

    printf("Fusion : ");
    for (k = 0; k < na + nb; k++)
        printf("%d ", c[k]);
    printf("\n");

    return 0;
}

Trois indices avancent en parallèle : i dans a, j dans b, k dans le résultat. À chaque tour on recopie le plus petit des deux éléments en tête, et seul l'indice correspondant avance.

Les deux boucles finales vident le tableau qui n'est pas épuisé. Une seule des deux s'exécute vraiment : la première boucle s'est arrêtée parce que l'un des deux était fini.

Le <= plutôt que < rend la fusion stable : à valeurs égales, celle de a passe en premier. C'est le cœur du tri fusion, en O(n+m) ici, là qu'un tri complet du résultat coûterait au mieux O((n+m) log(n+m)).

Corrigé de l'exercice 7

#include <stdio.h>

#define N 10

int main(void)
{
    int m[N][N];
    int n, i, j, somme = 0;

    printf("Taille de la matrice carree : ");
    scanf("%d", &n);
    if (n < 1 || n > N) {
        printf("Taille invalide.\n");
        return 1;
    }

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            printf("m[%d][%d] = ", i, j);
            scanf("%d", &m[i][j]);
        }

    /* diagonale principale : les cases ou la ligne egale la colonne */
    for (i = 0; i < n; i++)
        somme += m[i][i];
    printf("Somme de la diagonale : %d\n", somme);

    printf("Transposee :\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("%4d", m[j][i]);   /* ligne et colonne echangees */
        printf("\n");
    }

    return 0;
}

La diagonale principale rassemble les cases dont les deux indices sont égaux : un seul parcours sur m[i][i] suffit, pas besoin de double boucle.

Pour la transposée, aucun calcul n'est nécessaire : il suffit d'afficher m[j][i] au lieu de m[i][j]. Si l'on voulait réellement transposer la matrice en mémoire, il faudrait échanger les cases symétriques en ne parcourant que la moitié supérieure (j partant de i+1), sinon chaque échange serait fait deux fois et la matrice reviendrait à son état initial.

%4d réserve quatre caractères par nombre : les colonnes restent alignées à l'affichage.

Corrigé de l'exercice 8

#include <stdio.h>

typedef struct {
    int   matricule;
    char  nom[50];
    float notes[3];
} Etudiant;

int main(void)
{
    Etudiant e;
    float somme = 0.0f;
    int i;

    printf("Matricule : ");
    scanf("%d", &e.matricule);

    printf("Nom : ");
    scanf("%49s", e.nom);     /* 49 au plus : la 50e case garde le '\0' */

    for (i = 0; i < 3; i++) {
        printf("Note %d : ", i + 1);
        scanf("%f", &e.notes[i]);
        somme += e.notes[i];
    }

    printf("\n%s (matricule %d)\n", e.nom, e.matricule);
    printf("Moyenne : %.2f\n", somme / 3);

    return 0;
}

Un enregistrement regroupe sous un seul nom des données de types différents, là où un tableau impose un type unique. On accède à chaque champ avec le point : e.matricule, e.notes[0].

typedef permet d'écrire ensuite Etudiant e; au lieu de struct Etudiant e;.

Deux détails sur la saisie du nom. %49s limite la lecture à 49 caractères : la 50^e case reçoit le '\0' qui termine toute chaîne en C. Sans cette limite, un nom trop long écraserait la mémoire voisine. Et e.nom s'écrit sans & : le nom d'un tableau est déjà son adresse.

Corrigé de l'exercice 9

#include <stdio.h>

#define MAX 50

typedef struct {
    char  nom[50];
    float notes[3];
    float moyenne;
} Etudiant;

float calculer_moyenne(const Etudiant *e)
{
    return (e->notes[0] + e->notes[1] + e->notes[2]) / 3.0f;
}

int main(void)
{
    Etudiant promo[MAX];
    int n, i, j, admis = 0;

    printf("Nombre d'etudiants : ");
    scanf("%d", &n);
    if (n < 1 || n > MAX) return 1;

    for (i = 0; i < n; i++) {
        printf("Nom de l'etudiant %d : ", i + 1);
        scanf("%49s", promo[i].nom);
        for (j = 0; j < 3; j++) {
            printf("  note %d : ", j + 1);
            scanf("%f", &promo[i].notes[j]);
        }
        promo[i].moyenne = calculer_moyenne(&promo[i]);
    }

    printf("\n--- Admis ---\n");
    for (i = 0; i < n; i++)
        if (promo[i].moyenne >= 10.0f) {
            printf("%-20s %.2f\n", promo[i].nom, promo[i].moyenne);
            admis++;
        }

    printf("\nTaux de reussite : %.1f%% (%d sur %d)\n",
           100.0f * admis / n, admis, n);

    return 0;
}

Un tableau de structures se manipule comme un tableau ordinaire : promo[i] est un Etudiant complet, et promo[i].notes[j] descend dans son tableau de notes.

calculer_moyenne reçoit un pointeur plutôt que la structure elle-même. Passer la structure par valeur en recopierait les 60 octets à chaque appel ; le pointeur n'en coûte que 8. D'où la flèche e->notes[0], qui abrège (*e).notes[0].

Dans printf, %% affiche un signe pour cent littéral : un seul % serait lu comme le début d'un format.

Corrigé de l'exercice 10

#include <stdio.h>

#define MAX 50

typedef struct {
    char  nom[50];
    float moyenne;
} Etudiant;

void trier(Etudiant t[], int n)
{
    int i, j, max;
    Etudiant tmp;

    for (i = 0; i < n - 1; i++) {
        max = i;
        for (j = i + 1; j < n; j++)
            if (t[j].moyenne > t[max].moyenne)
                max = j;

        if (max != i) {          /* echange de deux structures entieres */
            tmp    = t[i];
            t[i]   = t[max];
            t[max] = tmp;
        }
    }
}

int main(void)
{
    Etudiant promo[MAX] = {
        {"Awa",    12.5f},
        {"Bello",   8.0f},
        {"Chimi",  15.75f},
        {"Diane",  11.0f},
        {"Eyenga", 17.25f}
    };
    int n = 5, i;

    trier(promo, n);

    printf("--- Classement ---\n");
    for (i = 0; i < n; i++)
        printf("%d. %-10s %.2f\n", i + 1, promo[i].nom, promo[i].moyenne);

    return 0;
}

Le point à retenir : tmp = t[i]; copie la structure entière, champ par champ, y compris le tableau nom. L'affectation de structures est l'une des rares opérations globales que le C autorise : elle ne fonctionnerait pas sur deux tableaux nus.

Le tri par sélection cherche à chaque tour la plus forte moyenne du reste et l'amène en position i. On compare les .moyenne, mais on déplace les enregistrements complets : le nom suit sa note.

La boucle externe s'arrête à n-1 : une fois les n-1 premiers placés, le dernier l'est forcément.

Corrigé de l'exercice 11

#include <stdio.h>

typedef struct {
    int jour;
    int mois;
    int annee;
} Date;

int bissextile(int a)
{
    return (a % 4 == 0 && a % 100 != 0) || (a % 400 == 0);
}

int jours_du_mois(int mois, int annee)
{
    int jours[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    if (mois < 1 || mois > 12)
        return 0;
    if (mois == 2 && bissextile(annee))
        return 29;
    return jours[mois - 1];      /* le tableau commence a l'indice 0 */
}

int date_valide(Date d)
{
    int max = jours_du_mois(d.mois, d.annee);
    return (max > 0 && d.jour >= 1 && d.jour <= max && d.annee > 0);
}

int main(void)
{
    Date d;

    printf("Date (jj mm aaaa) : ");
    scanf("%d %d %d", &d.jour, &d.mois, &d.annee);

    if (date_valide(d))
        printf("%02d/%02d/%d est une date valide.\n",
               d.jour, d.mois, d.annee);
    else
        printf("Date invalide.\n");

    return 0;
}

La règle des bissextiles tient en une ligne : divisible par 4, sauf les multiples de 100 qui ne sont pas multiples de 400. Ainsi 2024 est bissextile, 1900 ne l'était pas, 2000 l'était.

jours[mois - 1] : le mois 1 correspond à l'indice 0. Oublier ce décalage est l'erreur classique : elle donne 28 jours à janvier.

jours_du_mois renvoie 0 pour un mois invalide, ce qui permet à date_valide de rejeter la date sans test supplémentaire : aucun jour ne peut être inférieur ou égal à 0.

Corrigé de l'exercice 12

#include <stdio.h>
#include <math.h>

typedef struct {
    double re;
    double im;
} Complexe;

Complexe somme(Complexe a, Complexe b)
{
    Complexe r;
    r.re = a.re + b.re;
    r.im = a.im + b.im;
    return r;
}

Complexe produit(Complexe a, Complexe b)
{
    Complexe r;
    r.re = a.re * b.re - a.im * b.im;
    r.im = a.re * b.im + a.im * b.re;
    return r;
}

double module(Complexe a)
{
    return sqrt(a.re * a.re + a.im * a.im);
}

void afficher(const char *titre, Complexe c)
{
    if (c.im >= 0)
        printf("%s : %.2f + %.2fi\n", titre, c.re, c.im);
    else
        printf("%s : %.2f - %.2fi\n", titre, c.re, -c.im);
}

int main(void)
{
    Complexe a = {3.0, 4.0};
    Complexe b = {1.0, -2.0};

    afficher("a    ", a);
    afficher("b    ", b);
    afficher("a + b", somme(a, b));
    afficher("a * b", produit(a, b));
    printf("|a|   : %.2f\n", module(a));

    return 0;
}

Une fonction C peut renvoyer une structure entière, comme ici Complexe. C'est ce qui permet d'écrire produit(a, b) directement en argument de afficher, sans variable intermédiaire.

Le produit applique la règle (a+bi)(c+di) = (ac − bd) + (ad + bc)i. Sur a = 3 + 4i et b = 1 − 2i, on obtient 11 − 2i, et |a| = √(9 + 16) = 5.

sqrt vient de math.h. Sous Linux, la compilation réclame l'option de liaison : gcc prog.c -o prog -lm.

Corrigé de l'exercice 13

#include <stdio.h>

typedef struct {
    int jour, mois, annee;
} Date;

typedef struct {
    char  nom[50];
    float salaire;
    Date  embauche;      /* une structure dans une structure */
} Employe;

int anciennete(Date embauche, Date aujourdhui)
{
    int ans = aujourdhui.annee - embauche.annee;

    /* l'anniversaire d'embauche n'est pas encore passe cette annee */
    if (aujourdhui.mois < embauche.mois ||
       (aujourdhui.mois == embauche.mois && aujourdhui.jour < embauche.jour))
        ans--;

    return ans;
}

int main(void)
{
    Employe e = { "Nkolo", 450000.0f, {15, 9, 2019} };
    Date today = {10, 10, 2026};
    int ans;

    ans = anciennete(e.embauche, today);

    printf("Employe  : %s\n", e.nom);
    printf("Salaire  : %.0f FCFA\n", e.salaire);
    printf("Embauche : %02d/%02d/%d\n",
           e.embauche.jour, e.embauche.mois, e.embauche.annee);
    printf("Anciennete : %d an(s)\n", ans);

    return 0;
}

Un champ peut lui-même être une structure. L'accès s'enchaîne alors avec des points : e.embauche.annee se lit de gauche à droite, dans e, le champ embauche, puis son champ annee.

L'initialisation suit la même imbrication : { "Nkolo", 450000.0f, {15, 9, 2019} }, les accolades internes correspondant à la Date.

La soustraction des années ne suffit pas. Au 10 octobre 2026, un employé entré le 15 septembre 2019 a bien 7 ans ; s'il était entré le 15 novembre 2019, il n'en aurait encore que 6. D'où le test sur le mois et le jour.

Corrigé de l'exercice 14

#include <stdio.h>

typedef struct {
    char  nom[50];
    float salaire;
} Employe;

/* par valeur : la fonction travaille sur une copie, l'original ne bouge pas */
void augmenter_copie(Employe e, float taux)
{
    e.salaire += e.salaire * taux / 100.0f;
}

/* par adresse : la fonction atteint l'original */
void augmenter(Employe *e, float taux)
{
    e->salaire += e->salaire * taux / 100.0f;
}

int main(void)
{
    Employe e = { "Nkolo", 450000.0f };

    printf("Depart          : %.0f\n", e.salaire);

    augmenter_copie(e, 10.0f);
    printf("Apres la copie  : %.0f\n", e.salaire);   /* inchange */

    augmenter(&e, 10.0f);
    printf("Apres l'adresse : %.0f\n", e.salaire);   /* 495000 */

    return 0;
}

Le programme affiche 450000, puis 450000, puis 495000. augmenter_copie reçoit un double de la structure : elle augmente bien un salaire, mais celui de la copie, détruite au retour.

augmenter reçoit l'adresse. e->salaire désigne alors le champ de l'original, et la modification subsiste.

D'où la règle : une fonction qui doit modifier son argument reçoit son adresse. C'est aussi la raison du & dans scanf("%d", &n) : sans lui, scanf remplirait une copie de n.

Corrigé de l'exercice 15

#include <stdio.h>

void echange_faux(int a, int b)
{
    int t = a;
    a = b;
    b = t;              /* n'agit que sur les copies locales */
}

void echange(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;             /* agit sur les variables de l'appelant */
}

int main(void)
{
    int x = 3, y = 8;

    echange_faux(x, y);
    printf("Apres echange_faux : x = %d, y = %d\n", x, y);   /* 3 et 8 */

    echange(&x, &y);
    printf("Apres echange      : x = %d, y = %d\n", x, y);   /* 8 et 3 */

    return 0;
}

En C, un argument est toujours passé par valeur : la fonction reçoit une copie. echange_faux permute donc deux copies, qui disparaissent au retour : x et y restent à 3 et 8.

Pour atteindre les originaux, on passe leurs adresses. int *a déclare un pointeur sur entier, *a désigne la case pointée, et &x fournit l'adresse de x.

Remarquer que la règle n'est pas contournée : ce sont les adresses qui sont copiées. Mais deux copies d'une même adresse mènent au même emplacement.

Corrigé de l'exercice 16

#include <stdio.h>

/* renvoie 1 si le calcul a pu se faire, 0 sinon ;
   les deux resultats sortent par les pointeurs */
int division(int a, int b, int *quotient, int *reste)
{
    if (b == 0)
        return 0;

    *quotient = a / b;
    *reste    = a % b;
    return 1;
}

int main(void)
{
    int a, b, q, r;

    printf("Dividende : ");
    scanf("%d", &a);
    printf("Diviseur  : ");
    scanf("%d", &b);

    if (division(a, b, &q, &r))
        printf("%d = %d x %d + %d\n", a, b, q, r);
    else
        printf("Division par zero impossible.\n");

    return 0;
}

Le procédé est courant en C : la valeur de retour sert à dire si l'opération a réussi, et les résultats sortent par des pointeurs. On parle de paramètres de sortie.

&q et &r transmettent les adresses ; la fonction écrit dedans avec *quotient et *reste.

Le test b == 0 vient en premier : en C, une division entière par zéro ne lève pas d'exception, elle provoque l'arrêt brutal du programme. C'est à l'auteur de l'empêcher.

Corrigé de l'exercice 17

#include <stdio.h>

unsigned long factorielle(int n)
{
    if (n <= 1)                       /* cas d'arret : sans lui, appels sans fin */
        return 1;
    return (unsigned long)n * factorielle(n - 1);
}

unsigned long factorielle_iterative(int n)
{
    unsigned long r = 1;
    int i;
    for (i = 2; i <= n; i++)
        r *= i;
    return r;
}

int pgcd(int a, int b)
{
    if (b == 0)
        return a;
    return pgcd(b, a % b);            /* Euclide : pgcd(a,b) = pgcd(b, a mod b) */
}

int main(void)
{
    int n = 10;

    printf("%d! (recursif) = %lu\n", n, factorielle(n));
    printf("%d! (iteratif) = %lu\n", n, factorielle_iterative(n));
    printf("pgcd(1071, 462) = %d\n", pgcd(1071, 462));

    return 0;
}

Toute fonction récursive a besoin de deux choses : un cas d'arrêt et un appel qui s'en rapproche. Ici n <= 1 arrête la descente, et n - 1 y mène à coup sûr. Sans cas d'arrêt, les appels s'empilent jusqu'au débordement de pile.

Euclide repose sur le fait que le PGCD de deux nombres est aussi celui du plus petit et du reste de leur division. On obtient 1071, 462, 147, 21, puis 0 : le résultat est 21.

unsigned long parce que les factorielles croissent vite : 13! dépasse déjà la capacité d'un int de 32 bits. Même ainsi, au-delà de 20! le résultat déborde silencieusement.

Corrigé de l'exercice 18

#include <stdio.h>

void afficher(const int t[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", t[i]);
    printf("\n");
}

void trier(int t[], int n)
{
    int i, j, min, tmp;

    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
            if (t[j] < t[min])
                min = j;

        if (min != i) {
            tmp    = t[i];
            t[i]   = t[min];
            t[min] = tmp;
        }
    }
}

int main(void)
{
    int tab[] = {29, 10, 14, 37, 13, 5};
    int n = sizeof(tab) / sizeof(tab[0]);

    printf("Avant : ");
    afficher(tab, n);

    trier(tab, n);

    printf("Apres : ");
    afficher(tab, n);

    return 0;
}

Un tableau fait exception à la règle du passage par valeur : son nom se convertit en l'adresse de sa première case. trier travaille donc sur le tableau de main, et non sur une copie, c'est pourquoi elle n'a rien à renvoyer.

Conséquence directe : la taille doit être transmise à part. À l'intérieur de la fonction, sizeof(t) donnerait la taille d'un pointeur, pas celle du tableau.

const dans afficher exprime que la fonction lit sans écrire. Le compilateur refuserait toute modification, ce qui documente l'intention et prévient les erreurs.

Corrigé de l'exercice 19

#include <stdio.h>

#define N 3

/* la seconde dimension est obligatoire : sans elle, le compilateur
   ne sait pas de combien avancer d'une ligne a la suivante */
void produit(int a[][N], int b[][N], int c[][N])
{
    int i, j, k;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) {
            c[i][j] = 0;
            for (k = 0; k < N; k++)
                c[i][j] += a[i][k] * b[k][j];
        }
}

void afficher(int m[][N])
{
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            printf("%5d", m[i][j]);
        printf("\n");
    }
}

int main(void)
{
    int a[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int b[N][N] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}};
    int c[N][N];

    produit(a, b, c);

    printf("Produit A x B :\n");
    afficher(c);

    return 0;
}

Le coefficient en ligne i, colonne j du produit est la somme des a[i][k] * b[k][j] pour k parcourant la dimension commune : d'où les trois boucles imbriquées, et le c[i][j] = 0 avant d'accumuler.

La déclaration int a[][N] laisse le nombre de lignes libre mais exige le nombre de colonnes. En mémoire, un tableau 2D est une suite continue de valeurs : pour atteindre a[i][j], le compilateur calcule i * N + j. Sans N, ce calcul est impossible.

Sur les matrices données, la première ligne du résultat vaut 30, 24, 18.

Corrigé de l'exercice 20

#include <stdio.h>
#include <stdlib.h>

int *creer_carres(int n)
{
    int *t;
    int i;

    if (n <= 0)
        return NULL;

    t = (int *)malloc(n * sizeof(int));
    if (t == NULL)              /* l'allocation peut echouer */
        return NULL;

    for (i = 0; i < n; i++)
        t[i] = (i + 1) * (i + 1);

    return t;
}

int main(void)
{
    int *carres;
    int n = 8, i;

    carres = creer_carres(n);
    if (carres == NULL) {
        printf("Allocation impossible.\n");
        return 1;
    }

    for (i = 0; i < n; i++)
        printf("%d ", carres[i]);
    printf("\n");

    free(carres);               /* rendre la memoire empruntee */
    carres = NULL;              /* eviter de reutiliser une adresse liberee */

    return 0;
}

Une fonction ne peut pas renvoyer un tableau local : celui-ci disparaît au retour, et l'adresse rendue ne désignerait plus rien. malloc prend la mémoire sur le tas, qui survit à la fonction.

malloc(n * sizeof(int)) réserve le bon nombre d'octets. Écrire sizeof(int) plutôt que 4 garde le code juste sur toute machine.

Trois réflexes vont ensemble : vérifier que malloc n'a pas renvoyé NULL, appeler free quand le tableau ne sert plus, et remettre le pointeur à NULL. Sans free, la mémoire reste occupée jusqu'à la fin du programme : c'est une fuite.