Discussion :

[rutabagas]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Thierry Chappuis]

Qu'essaies-tu de faire là:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[rutabagas]

Qu'essaies-tu de faire là:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é.

[Thierry Chappuis]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

au lieu de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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