parcourir une pile (liste simple chaînée)

Version imprimable

Bonjour,
(J e précise que je suis autodidacte et que ce n'est pas un exercice à résoudre pour un devoir qcq)
En m'inspirant du tuto de CGI j'ai écrit:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <stdio.h> #include <stdlib.h> /* ======= * pile3.c * ======= */ typedef struct pile { int valeur; struct pile * prec; } pile; void Push(pile ** p, int Val) { pile * element = malloc(sizeof(pile)); if (!element) exit(1); /* Si l'allocation a échouée et stdlib.h est pour exit . */ element->valeur = Val; element->prec = *p; *p = element; /* Le pointeur pointe sur le dernier élément. */ } int main() { int i; pile * MaPile = NULL, * index = NULL; for (i = 1; i <= 8; i++) Push(&MaPile, i); printf("%d\n", MaPile->valeur); printf("%d\n", MaPile->prec->valeur); printf("%d\n", MaPile->prec->prec->valeur); printf("==\n"); index = MaPile; /* Pour parcourir la pile */ for (i = 0; i < 8; i++) printf("%d\n", (index - i)->valeur); return 0; }
Le résultat m'affiche ce que je veux: 8, 7, 6 d'une part.
Mais la boucle avec l'index m'affiche:
8, 0, 7, 0, 6, 0, 5, 0
Je ne comprends pas pourquoi (index - 1)->valeur ne contient pas 7 et à quoi correspond le 0.

Merci pour une explication.
Pardonnez moi si c'est évident mais comme dit l'anglais je suis stuck.

Qu'essaies-tu de faire là:

Code:

1
2
 
printf("%d\n", (index - i)->valeur);

L'indexation ne fonctionne pas sur une liste chainee. Qui te dis que l'adresse (index - i) est valide? Tu dois parcourir ta liste noeud par noeud. Voici mes corrections:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <stdlib.h>
 
typedef struct pile
{
    int  valeur;
    struct pile * prec;
} pile;
 
int Push(pile ** p, int Val)
{
    int err = 0;
 
    /*-tc- programmation defensive: tu dois tester si p vaut NULL */
    if (p != NULL)
    {
        pile * element = malloc(sizeof *element);
        /* -tc-éviter les exit() sauvages*/
        if (element != NULL)
        {
            element->valeur = Val;
            element->prec = *p;
            *p = element;       /* Le pointeur pointe sur le dernier élément. */
        }
        else
        {
            /* -tc- Erreur d'allocation memoire */
            err = 1;
        }
    }
    else
    {
        /* -tc- Erreur: p doit etre different de NULL */
        err = 2;
    }
    return err;
}
 
int main(void)
{
    /*-tc- une définition par ligne, ça ne mange pas d'pain... */
    int i;
    pile * MaPile = NULL;
    pile * index = NULL;
    int err = 0;
    int ret = EXIT_FAILURE;
 
    for (i = 1; i <= 8 && err == 0; i++)
    {
        err = Push(&MaPile, i);
    }
 
    if (err == 0)
    {
        printf("%d\n", MaPile->valeur);
        printf("%d\n", MaPile->prec->valeur);
        printf("%d\n", MaPile->prec->prec->valeur);
        printf("==\n");
 
        for (index = MaPile; index != NULL; index = index->prec)
        {
            printf("%d\n", index->valeur);
        }
    }
    else
    {
        ret = EXIT_FAILURE;
    }
    return ret;
}

Par ailleurs, pour vraiment définir pile comme un type abstrait de donnée qui se comporte comme une pile, tu dois encore définir les fonctions Pop() et IsEmpty(). Une pile n'est en effet pas faite pour être parcourue, mais pour empiler et dépiler.

Thierry

Citation:
Envoyé par Thierry Chappuis
Qu'essaies-tu de faire là:
Code:

1 2 printf("%d\n", (index - i)->valeur);
L'indexation ne fonctionne pas sur une liste chainee. Qui te dis que l'adresse (index - i) est valide? Tu dois parcourir ta liste noeud par noeud. Voici mes corrections:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 #include <stdio.h> #include <stdlib.h> typedef struct pile { int valeur; struct pile * prec; } pile; int Push(pile ** p, int Val) { int err = 0; /*-tc- programmation defensive: tu dois tester si p vaut NULL */ if (p != NULL) { pile * element = malloc(sizeof *element); /* -tc-éviter les exit() sauvages*/ if (element != NULL) { element->valeur = Val; element->prec = *p; *p = element; /* Le pointeur pointe sur le dernier élément. */ } else { /* -tc- Erreur d'allocation memoire */ err = 1; } } else { /* -tc- Erreur: p doit etre different de NULL */ err = 2; } return err; } int main(void) { /*-tc- une définition par ligne, ça ne mange pas d'pain... */ int i; pile * MaPile = NULL; pile * index = NULL; int err = 0; int ret = EXIT_FAILURE; for (i = 1; i <= 8 && err == 0; i++) { err = Push(&MaPile, i); } if (err == 0) { printf("%d\n", MaPile->valeur); printf("%d\n", MaPile->prec->valeur); printf("%d\n", MaPile->prec->prec->valeur); printf("==\n"); for (index = MaPile; index != NULL; index = index->prec) { printf("%d\n", index->valeur); } } else { ret = EXIT_FAILURE; } return ret; }
Par ailleurs, pour vraiment définir pile comme un type abstrait de donnée qui se comporte comme une pile, tu dois encore définir les fonctions Pop() et IsEmpty(). Une pile n'est en effet pas faite pour être parcourue, mais pour empiler et dépiler.

Thierry
Merci beaucoup !
Ce que j'essaie de faire, c'est de décortiquer ce qu'a écrit CGI pour être sûr que je comprends ...
Donc si je comprends bien le malloc dans la fonction Push ne réserve pas des places contigües en mémoire.(J'aurais dû y penser ;-)
D'autre part je comprends que l'on doit contrôler que malloc peut allouer de la mémoire mais si dans main on déclare : *MaPile
normalement &MaPile (l'adresse de MaPile) doit exister et donc ne doit pas être NULL ? (Mais c'est peut-être comme pour malloc s'il n'y a plus de place en mémoire le pointeur MaPile n'est pas créé ...)

Merci encore pour cette aide de qualité.

04/10/2007, 16h08
Thierry Chappuis
Citation:

Envoyé par rutabagas

mais si dans main on déclare : *MaPile
normalement &MaPile (l'adresse de MaPile) doit exister et donc ne doit pas être NULL ? (Mais c'est peut-être comme pour malloc s'il n'y a plus de place en mémoire le pointeur MaPile n'est pas créé ...)

Merci encore pour cette aide de qualité.

Il se peut que lorsque tu auras bien travaillé sur ton type abstrait de donnée (TAD) pile, et que tu seras satisfait de son fonctionnement, tu ais envie de le réutiliser dans d'autres projets. La programmation défensive te préserve des mauvaises surprise.

Par ailleurs, si il t'arrivait d'oublier que le premier argument de Push() est de type pointeur sur pointeur sur pile et que tu passes par erreur:
Code:

1 2 pile *MaPile = NULL; Push(MaPile, 10);
au lieu de

Code:

Push(&MaPile, 10);

La stratégie décrite dans mon code te permettra de trouver l'erreur à l'aide du code retourné par la fonction Push(). C'est toujours une bonne idée de vérifier la validité des arguments passés à la fonction.

Thierry