liste chainée

**molesqualeux** · 20/11/2005, 16h28

Bonjour , je suis débutant en C .

Je dois réaliser mon premier programme traitant des listes chainées chose élémentaire en C qui utilise les pointeurs (chose nouvelle pour moi).

J'aimerais avoir un peu d'aide .

Je dois réaliser une fonction premier_elem_sup_ou_egal qui a pour argument un entier u et qui est de type pointeur .

Ma structure est

Code :

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

1
2
3
4
5
 
struct elem{
	int val;
	struct elem *lien;
};

voici l'exercice

Voici ma production (après avoir lu la FAQ de developpez etc)

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
struct elem *premier_elem_sup_ou_egal(int u)
{
	struct elem *p;
 
	struct elem *L;
 
 
	L = (elem*)malloc(sizeof(struct elem));
 
	p = L;
 
 
 
	while (p != NULL && p->val < u)
	{
		p = p->lien;
	}
 
	return p;
}
 
 
 
main()
 
{
	struct elem *L;
 
	struct elem *P;
 
free(L);
L->val = 10;
free(L->lien);
(L->lien)->val = 11;
free((L->lien)->lien);
(L->lien->lien)->val = 12;
free((L->lien->lien)->lien);
(L->lien->lien->lien)->val = 13;
L->lien->lien->lien)->lien = NULL;
 
p = premier_element_sup_ou_egal(14);
 
if(p != NULL)
{
printf("%d",p->val);
}
else
{
printf("L'element recherche n'existe pas");
}
}
 
 
}

J'ai un peu du mal avec le c(p) <- c(L) ai je le droit d'écrire p = L?

merci beaucoup de votre aide .

**pk960** · 20/11/2005, 17h10

J'ai un peu du mal avec le c(p) <- c(L) ai je le droit d'écrire p = L?

Oui. Tu as le droit de copier la valeur d'un pointeur dans un autre pointeur.

Par contre, on voit que tu débutes en C :

Code :

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

1
2
3
 
free(L);
L->val = 10;

Commencer par supprimer un espace avant d'écrire dedans est plus que déconseillé ! C'est le contraire qu'il faut faire :

Code :

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

1
2
3
 
L = (struct elem *)malloc(sizeof(struct elem));
L->val = 10;

**molesqualeux** · 20/11/2005, 17h15

mon c(p) c'est en fait struct elem *p?

Code :

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

struct elem * p = struct elem * L

? merci

**pk960** · 20/11/2005, 17h38

Pour moi, c'est simplement

Code :

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

p=L;

**molesqualeux** · 20/11/2005, 20h28

ok donc en fait DISPO en algorythme c'est un malloc?

**Médinoc** · 20/11/2005, 20h40

Ici, on dirait bien...

**molesqualeux** · 20/11/2005, 20h41

ok merci je mets ma dernière version . Serait -il possible de jeter un oeil sur une eventuelle erreur de logique . Merci

Pour l'algo voir premier post

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
#include<stdio.h>
#include <stdlib.h>
 
struct elem {  /* ma structure liste chainée*/
int val;
struct elem *lien ;
};
 
 
//fonction qui renvoit l'adresse de la première valeur supérieure ou égale à u
 
 
struct elem *premier_elem_sup_ou_egal(int u)
{
   struct elem *p;
 
   struct elem *L;
 
 
//l'équivalent du c(p) <- c(L)
 
   p = L; 
 
 
 
   while (p != NULL && p->val < u)
   {
      p = p->lien;
   }
 
   return p;
}
 
 
 
main()
 
{
   struct elem *L;
 
   struct elem *P;
 
L = (elem*)malloc(sizeof(struct elem));
free(L);
L->val = 10;
L->lien = (elem*)malloc(sizeof(struct elem));
(L->lien)->val = 11;
(L->lien)->lien = (elem*)malloc(sizeof(struct elem));
(L->lien->lien)->val = 12;
(L->lien->lien)->lien = (elem*)malloc(sizeof(struct elem));
(L->lien->lien->lien)->val = 13;
L->lien->lien->lien)->lien = NULL;
 
p = premier_element_sup_ou_egal(14);
 
if(p != NULL)
{
printf("%d",p->val);
}
else
{
printf("L'element recherche n'existe pas");
}
}

**Trap D** · 20/11/2005, 20h58

Salut
Y aurait pas comme un problème ici ?

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
struct elem *premier_elem_sup_ou_egal(int u)
{
   struct elem *p;
 
   struct elem *L;
 
 
//l'équivalent du c(p) <- c(L)
 
   p = L; // intéressant mais L n'étant pas initialisé ça va se promene joyeusement en mémoire.
 
 
   // ça devrait planter rapidement
   while (p != NULL && p->val < u)
   {
      p = p->lien;
   }
 
   return p;
}

**molesqualeux** · 20/11/2005, 21h00

pour l'initialisation de L , dans l'algo on en parle pas.
Enfin si on l'initialise mais aprés donc comment faire ? la déclarer en variable globale?

**Trap D** · 20/11/2005, 21h04

Non, la passer en argument de la fonction "premier_elem_sup_ou_egal"

**Emmanuel Delahaye** · 20/11/2005, 21h41

Envoyé par molesqualeux

ok merci je mets ma dernière version . Serait -il possible de jeter un oeil sur une eventuelle erreur de logique .

Mes remarques (-ed-). A lire dans le detail. Pose des questions si tu ne comprends pas.

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
#include<stdio.h>
#include <stdlib.h>
 
struct elem
{  /* ma structure liste chainée*/
    int val;
    struct elem *lien ;
};
 
/* -ed- Attention, les commentaires '//' sont C99 uniquement. */
/* fonction qui renvoit l'adresse de la première valeur supérieure ou égale à u */
struct elem *premier_elem_sup_ou_egal(int u)
{
    struct elem *p;
    struct elem *L;
 
    /* l'équivalent du c(p) <- c(L) */
    p = L;
    /* -ed- OUCH! 'L' n'est pas initialise.
    Mettre une valeur non initialisee dans une variable invoque 
    un comportement indefini. Lire une telle valeur aussi... 
    */
 
    while (p != NULL && p->val < u)
    {
        p = p->lien;
    }
 
    return p;
}
 
 
/*
 -ed- 
main()
 
En C99, le type retourne doit etre explicite.
*/
int main(void)
{
    struct elem *L;
    struct elem *P;
    /* -ed-
    L = (elem*)malloc(sizeof(struct elem));
     
    Une facon compliquee d'ecrire 
    */
    L = malloc(sizeof*L);
    /* -ed- attention, malloc() peut echouer. Tester si non NULL */
 
    /* -ed-
    free(L);
     
    What the hell! 
    */
 
    L->val = 10;
 
    /* -ed-
    L->lien = (elem*)malloc(sizeof(struct elem));
     
    'elem' n'existe pas. C'est 'struct elem'. 
    De toutes facon, on en a pas besoin.
    */
    L->lien = malloc(sizeof*L->lien);
 
    /* -ed-
    (L->lien)->val = 11;
     
    parentheses inutiles. 
    */
    L->lien->val = 11;
 
    L->lien->lien = malloc(sizeof(struct elem));
    L->lien->lien->val = 12;
    L->lien->lien->lien = malloc(sizeof(struct elem));
    L->lien->lien->lien->val = 13;
    L->lien->lien->lien->lien = NULL;
    /* -ed- c'est une methode barbare pour creer une liste chainee...
    En principe, on utilise une fonction d'ajoute (en tete, en queue...) 
    de creation... 
    */
 
    /* -ed- 
    p = premier_element_sup_ou_egal(14);
 
    'p' : variable non definie... 
    'P' est defini. attention, le C est sensible a la casse... 
    */
 
    /* -ed-
    P = premier_element_sup_ou_egal(14);
    fonction indefinie. La fonction que tu as definie est 
    'premier_elem_sup_ou_egal'. C'est pas pareil...
    */
    P = premier_elem_sup_ou_egal(14);
 
    if(P != NULL)
    {
        /* -ed-
        printf("%d",p->val);
        manque un '\n' pour terminer la ligne... 
        */
        printf("%d\n",P->val);
    }
    else
    {
        printf("L'element recherche n'existe pas\n");
    }
 
    /* -ed- la memoire allouee n'est jamais liberee. 
    
SYSALLOC Err: Not-matched list:
SYSALLOC Bloc 003D2470 (8 bytes) malloc'ed at line 48 of 'main.c' not freed
SYSALLOC Bloc 003D2460 (8 bytes) malloc'ed at line 65 of 'main.c' not freed
SYSALLOC Bloc 003D24E0 (8 bytes) malloc'ed at line 74 of 'main.c' not freed
SYSALLOC Bloc 003D24F0 (8 bytes) malloc'ed at line 76 of 'main.c' not freed    
    */    
    /* -ed- en C90, il est obligatoire de preciser ce qu'on retourne de main(). */
    return 0;
}

**molesqualeux** · 20/11/2005, 22h12

tout d'abord merci

quelques questions me viennent à l'esprit :

Pourquoi un free(L);

Code :

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

1
2
3
4
5
 
L = (struct elem*)malloc(sizeof(struct elem));
free (L);
L->val = 10;
L->lien = (struct elem*)malloc(sizeof(struct elem));

Comment initialiser L (tête de liste)? avec un L = (struct elem*)malloc(sizeof(struct elem)); ?

Pour libérer la mémoire je dois le faire à la fin du programme free(L->lien) ; free(L->lien->lien) ; ..... ?

merci

**Emmanuel Delahaye** · 20/11/2005, 22h35

Envoyé par molesqualeux

quelques questions me viennent à l'esprit :
Pourquoi un free(L);

Ca, je me le demande encore...

Code :

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

1
2
3
4
5
 
L = (struct elem*)malloc(sizeof(struct elem));
free (L);
L->val = 10;
L->lien = (struct elem*)malloc(sizeof(struct elem));

Je ne veux plus voir ces casts inutiles polluants et dangereux...

http://emmanuel-delahaye.developpez....tes.htm#malloc

D'autre part, après un free (p), on a plus le droit de déreférencer p (comportement indéfini). D'ailleurs, je recommande

Code :

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

free (p), p = NULL;

ça calme... (essaye...)

Il y a donc bien un problème de conception dans ton code...

Comment initialiser L (tête de liste)? avec un L = (struct elem*)malloc(sizeof(struct elem)); ?

C'est bien ce que tu as fait, non ? Bon en principe, on initialise à NULL, et on traite le cas dans la fonction d'ajout...

Pour libérer la mémoire je dois le faire à la fin du programme free(L->lien) ; free(L->lien->lien) ; ..... ?

Il faut defaire ce qui a été fait.

**molesqualeux** · 21/11/2005, 11h30

Code :

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

1
2
3
L = (struct elem*)malloc(sizeof(struct elem));
free (L);
L->val = 10;

C'est ici que je comprends pas , malloc alloue un espace pour L ? Puis après on le libère et après on l'assigne ...

Ici c'est particulier on a pas de fonction d'ajout(c'est un exercice) , on initialise la liste comme dans l'algorythme.

Merci

**Emmanuel Delahaye** · 21/11/2005, 13h02

Envoyé par molesqualeux

Code :

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

1
2
3
L = (struct elem*)malloc(sizeof(struct elem));
free (L);
L->val = 10;

C'est ici que je comprends pas , malloc alloue un espace pour L ? Puis après on le libère et après on l'assigne ...

Moi non plus, je ne comprends pas. On se tue à te dire que ce code est faux. Pourquoi tu insistes ?

malloc() crée un espace mémoire, et retourne l'adresse de celui-ci. Cette adresse est stockée dans L.
free() libère le bloc. La valeur de L est inchangée, mais le bloc pointé n'est plus valide. Il est désormais interdit de lire ce bloc ou d'écrire dedans.

liste chainée

C

Discussions similaires

Partager

Partager