Liste doublement chainée

Version imprimable

Voir 40 message(s) de cette discussion en une page

Salut !

Je me lance dans les listes doublement chainées.
J'ai implémenté les 2 premieres fonctions de base : l'ajout en tete, et l'affichage.
Elles ont l'air correctes, mais je préfère en être sur avant de continuer donc je vous poste mon code et si des choses ne vont pas n'hesitez pas ! :D

Le .h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
 
typedef struct noeud
{
	int val;
	struct noeud *pSuiv;
	struct noeud *pPrec;
}noeud;
 
typedef struct list
{
	noeud *pTete;
	noeud *pQueue;
}list;

listed.c :

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
#include "listed.h"
 
/* Fonction qui ajoute un element en debut de liste */
void ajouter(list *p, int valeur)
{
	noeud *nouv = malloc(sizeof(*nouv));
 
	if(nouv)
	{
		nouv->val = valeur;
		/* Si la liste est vide */
		if(!p->pTete)
		{
			nouv->pSuiv = NULL;
			nouv->pPrec = NULL;
			p->pTete = nouv;
			p->pQueue = nouv;
		}
		else
		{
			nouv->pPrec = NULL;
			nouv->pSuiv = p->pTete;
			p->pTete->pPrec = nouv;
			p->pTete = nouv;
		}
	}
	else
	{
		perror("malloc()");
	}
}
 
/* Fonction qui affiche la liste */
void afficher(list *p)
{
	noeud *tmp = p->pTete;
 
	while(tmp)
	{
		printf("%d\n",tmp->val);
		tmp = tmp->pSuiv;
	}
}

Et le main :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "listed.h"
 
int main()
{
	list maListe = {0};
 
	ajouter(&maListe,1);
	ajouter(&maListe,2);
	ajouter(&maListe,3);
	afficher(&maListe);
 
	system("Pause");
	return 0;
}

Voila, merci à vous pour vos remarques :wink:

Re: Liste doublement chainée

Citation:

Envoyé par sorry60

Salut !

Je me lance dans les listes doublement chainées.
J'ai implémenté les 2 premieres fonctions de base : l'ajout en tete, et l'affichage.
Il manque les gardes dans le listed.h (idem dans le code de la liste simple : liste.h)
Il manque les prototypes des fonctions dans listed.h
Avec les listes doubles (et simples, aussi, d'ailleurs), il faut préciser si on ajoute en tête ou en queue. C'est soit un paramètre, soit deux fonctions séparées...
Fuites mémoire...
Code:

1 2 3 SYSALLOC Bloc 003D24C8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24E0 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24F8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed

Re: Liste doublement chainée

Citation:
Envoyé par Emmanuel Delahaye
Il manque les gardes dans le listed.h (idem dans le code de la liste simple : liste.h)
Il manque les prototypes des fonctions dans listed.h
Avec les listes doubles (et simples, aussi, d'ailleurs), il faut préciser si on ajoute en tête ou en queue. C'est soit un paramètre, soit deux fonctions séparées...
Fuites mémoire...
Code:

1 2 3 SYSALLOC Bloc 003D24C8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24E0 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24F8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed
Ok merci pour ces critiques, je m'occuppe de ça tres vite.
Juste une question : c'est quoi une garde ? (ifdef _cplusplus...?)

01/12/2005, 19h11
Emmanuel Delahaye

Re: Liste doublement chainée

Citation:

Envoyé par sorry60

Juste une question : c'est quoi une garde ? (ifdef _cplusplus...?)

Protection anti inclusions multiples.

http://emmanuel-delahaye.developpez....ganiser_source
http://emmanuel-delahaye.developpez.....htm#organiser
01/12/2005, 20h55
Médinoc

D'ici, je ne vois pas vraiment de problème. Ta fonction d'ajout en tête semble OK...
Sinon, oui, il faudra prévoir une fonction pour vider...

Et si tu es maniaque, tu fais une version const et une versin non-const de chaque fonction: http://www.isty-info.uvsq.fr/~fbenoit/ListeDblChainee.h
:D

(Oui, c'est là-dessus que je bosse en ce moment... Les grands esprits se rencontrent :) )
01/12/2005, 22h03
sorry60

Citation:

Envoyé par Médinoc

D'ici, je ne vois pas vraiment de problème. Ta fonction d'ajout en tête semble OK...
Sinon, oui, il faudra prévoir une fonction pour vider...

Et si tu es maniaque, tu fais une version const et une versin non-const de chaque fonction: http://www.isty-info.uvsq.fr/~fbenoit/ListeDblChainee.h
:D

(Oui, c'est là-dessus que je bosse en ce moment... Les grands esprits se rencontrent :) )

J'y vais petit à petit avec les listes, merci pour ton exo, ça en fait un de plus, c'est pas un mal :D

Re: Liste doublement chainée

Citation:
Envoyé par Emmanuel Delahaye
[*]Fuites mémoire...
Code:

1 2 3 SYSALLOC Bloc 003D24C8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24E0 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24F8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed
Comment tu fais pour reperer les fuites memoires ? Qu'utilises tu ?

Re: Liste doublement chainée

Citation:
Envoyé par Jack_serious
Citation:
Envoyé par Emmanuel Delahaye
[*]Fuites mémoire...
Code:

1 2 3 SYSALLOC Bloc 003D24C8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24E0 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24F8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed
Comment tu fais pour reperer les fuites memoires ? Qu'utilises tu ?
Son propre traqueur il me semble... SYSALLOC il s'appelle, je crois (sur son site, dans les modules si cela n'a pas changé depuis le temps...)

Re: Liste doublement chainée

Citation:
Envoyé par Pouic
Citation:
Envoyé par Jack_serious
Citation:
Envoyé par Emmanuel Delahaye
[*]Fuites mémoire...
Code:

1 2 3 SYSALLOC Bloc 003D24C8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24E0 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed SYSALLOC Bloc 003D24F8 (12 bytes) malloc'ed at line 8 of 'listed.c' not freed
Comment tu fais pour reperer les fuites memoires ? Qu'utilises tu ?
Son propre traqueur il me semble... SYSALLOC il s'appelle, je crois (sur son site, dans les modules si cela n'a pas changé depuis le temps...)
Voui.

http://emmanuel-delahaye.developpez.com/clib.htm
Module SYSALLOC

Re: Liste doublement chainée

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par sorry60

Juste une question : c'est quoi une garde ? (ifdef _cplusplus...?)

Protection anti inclusions multiples.

http://emmanuel-delahaye.developpez....ganiser_source
http://emmanuel-delahaye.developpez.....htm#organiser

Oui je les avais mais ça compilait pas 8O
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #ifndef LISTED_H #define LISTED_H #include <stdio.h> #include <stdlib.h> typedef struct noeud { int val; struct noeud *pSuiv; struct noeud *pPrec; }noeud; typedef struct list { noeud *pTete; noeud *pQueue; }list;
Citation:

1 C:\Documents and Settings\Thomas\Mes documents\Langage C\Exercices\Listes\DoublementChainée\listed.c In file included from listed.c
1:2 C:\Documents and Settings\Thomas\Mes documents\Langage C\Exercices\Listes\DoublementChainée\listed.h invalid preprocessing directive #ifndef

02/12/2005, 11h22
Emmanuel Delahaye

Re: Liste doublement chainée

Citation:

Envoyé par sorry60

Citation:

Envoyé par -ed-

Protection anti inclusions multiples.

http://emmanuel-delahaye.developpez....ganiser_source
http://emmanuel-delahaye.developpez.....htm#organiser

Oui je les avais mais ça compilait pas 8O

Et le #endif, il est où ? Et je recommande H_LISTED pour éviter de commencer un jour par E, qui est reservé...
02/12/2005, 11h23
sorry60

Re: Liste doublement chainée

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par sorry60

Oui je les avais mais ça compilait pas 8O

Et le #endif, il est où ?

Arf quel idiot ! :sm: :scarymov:

J'ai corrigé mon projet..
Voilà ce que ça donne

listed.h

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
#ifndef H_LISTED
#define H_LISTED
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct noeud
{
	int val;
	struct noeud *pSuiv;
	struct noeud *pPrec;
}noeud;
 
typedef struct list
{
	noeud *pTete;
	noeud *pQueue;
}list;
 
/* Fonction qui ajoute un element en debut de liste */
void ajouterTete(list *p, int valeur);
 
/* Fonction qui affiche la liste */
void afficher(list *p);
#endif

listed.c

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
#include "listed.h"
 
/* Fonction qui ajoute un element en debut de liste */
void ajouterTete(list *p, int valeur)
{
	noeud *nouv = malloc(sizeof(*nouv));
 
	if(nouv)
	{
		nouv->val = valeur;
		/* Si la liste est vide */
		if(!p->pTete)
		{
			nouv->pSuiv = NULL;
			nouv->pPrec = NULL;
			p->pTete = nouv;
			p->pQueue = nouv;
		}
		else
		{
			nouv->pPrec = NULL;
			nouv->pSuiv = p->pTete;
			p->pTete->pPrec = nouv;
			p->pTete = nouv;
		}
	}
	else
	{
		perror("malloc()");
	}
}
 
/* Fonction qui affiche la liste */
void afficher(list *p)
{
	noeud *tmp = p->pTete;
 
	while(tmp)
	{
		printf("%d\n",tmp->val);
		tmp = tmp->pSuiv;
	}
}
 
/* Fonction qui libère la liste */
void clearListe(list *p)
{
	while(p->pTete)
	{
		free(p->pTete);
		p->pTete = p->pTete->pSuiv;
	}
}

le main

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifdef __cplusplus
#error Be sure you are using a C compiler...
#endif
 
#include "listed.h"
 
int main()
{
	list maListe = {0};
 
	printf("On ajoute 3 elements...:\n");
	ajouterTete(&maListe,1);
	ajouterTete(&maListe,2);
	ajouterTete(&maListe,3);
	afficher(&maListe);
	printf("On clear la liste...:\n");
	clearListe(&maListe);
	afficher(&maListe);
 
	system("Pause");
	return 0;
}

C'est ok ?

Citation:

Envoyé par sorry60

J'ai corrigé mon projet..
Voilà ce que ça donne
<...>
C'est ok ?

Manque le prototype de clearListe() dans le header... Il ne le voit pas ton compilateur ?

avec "-Wall -Wextra -O2", il devrait.

J'ai un peu instrumenté l'affichage
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 /* Fonction qui affiche la liste */ void afficher(list *p) { noeud *tmp = p->pTete; #if DBG printf(" pTete = %p\n",(void *) p->pTete); printf("pQueue = %p\n",(void *) p->pQueue); #endif while(tmp) { printf("%d\n",tmp->val); tmp = tmp->pSuiv; } }
et on voit que le pointeur de queue n'est pas mis à jour...
Code:

1 2 3 4 5 6 7 8 9 10 On ajoute 3 elements...: pTete = 003D24F8 pQueue = 003D24C8 3 2 1 On clear la liste...: pTete = 00000000 pQueue = 003D24C8

02/12/2005, 11h34
sorry60

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par sorry60

J'ai corrigé mon projet..
Voilà ce que ça donne
<...>
C'est ok ?

Manque le prototype de clearListe() dans le header... Il ne le voit pas ton compilateur ?

avec "-Wall -Wextra -O2", il devrait.

Je compile avec les options

Citation:

-Wall -Wextra -ansi -O2

et non il ne voit pas :? et moi non plus..je suis mal reveillé ce matin :roll:
02/12/2005, 11h44
Emmanuel Delahaye

Citation:

Envoyé par sorry60

Je compile avec les options

Citation:

-Wall -Wextra -ansi -O2

et non il ne voit pas :? et moi non plus..je suis mal reveillé ce matin :roll:

Il n'y a pas de warning ? -Wextra est bien pris (les gcc plus anciens utilisaient -W)
02/12/2005, 11h47
sorry60

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par sorry60

Je compile avec les options

Citation:

-Wall -Wextra -ansi -O2

et non il ne voit pas :? et moi non plus..je suis mal reveillé ce matin :roll:

Il n'y a pas de warning ? -Wextra est bien pris (les gcc plus anciens utilisaient -W)

Non pas de warning 8O
J'ai la derniere version de DevCpp

Voici une fonction qui supprime un élément :

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
/* Fonction qui supprime un element */
void supprimer(list *p, int valeur)
{
	/* Si la liste est deja vide */
	if(!p->pTete)
	{
		return;
	}
	/* Si c'est le seul element */
	if( (!p->pTete->pSuiv) && (p->pTete->val == valeur) )
	{
		free(p->pTete);
		p->pTete = NULL;
		return;
	}
	/* Si l'element à supprimer est en tete */
	if(p->pTete->val == valeur)
	{
		noeud *tmp = p->pTete->pSuiv;
		free(p->pTete);
		tmp->pPrec = NULL;
		p->pTete = tmp;
		return;
	}
	/* Sinon on parcourt la liste...*/
	{
		noeud *tmp = p->pTete;
 
		while(tmp && (tmp->val != valeur) )
		{
			tmp = tmp->pSuiv;
		}
		if(tmp)
		{
			/* Si c'est la queue */
			if(tmp == p->pQueue)
			{
				tmp = p->pQueue->pPrec;
				free(p->pQueue);
				tmp->pSuiv = NULL;
				p->pQueue = tmp;
			}
			/* Sinon */
			else
			{
				noeud *tmp2 = tmp->pSuiv;
				tmp2->pPrec = tmp->pPrec;
				tmp2 = tmp->pPrec;
				tmp2->pSuiv = tmp->pSuiv;
				free(tmp);
			}
		}
	}
}

Elle semble bien fonctionner.
Par contre, je saisis pas trop l'interet d'une liste doublement chainée par rapport à la simplement chainée dans les fonctions que j'ai faite..

Si vous avez des idées d'exercices qui mettraient en valeur ça :wink:

02/12/2005, 17h18
Médinoc

La liste doublement chaînée peut être parcourue à l'envers, et aussi, on peut retrouver le début et la fin à partir de n'importe que chaînon, on peut supprimer un chaînon sans avoir besoin de garder un pointeur sur le précédent, etc.

La liste est assez longue, mais voici ce qui me vient le plus vite à l'esprit.

Citation:

Envoyé par sorry60

Voici une fonction qui supprime un élément :

Ca a l'air correct, mais il y a toujours un problème de mise à jour de pQueue à la fin...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 On ajoute 3 elements...: pTete = 003D24F8 pQueue = 003D24C8 3 2 1 Suppression 2 pTete = 003D24F8 pQueue = 003D24C8 3 1 Suppression 1 pTete = 003D24F8 pQueue = 003D24F8 3 Suppression 3 pTete = 00000000 pQueue = 003D24F8 On clear la liste...: pTete = 00000000 pQueue = 003D24F8
avec
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 #include "listed.h" int main() { list maListe = {0}; printf("On ajoute 3 elements...:\n"); ajouterTete(&maListe,1); ajouterTete(&maListe,2); ajouterTete(&maListe,3); afficher(&maListe); printf("Suppression 2\n"); supprimer(&maListe,2); afficher(&maListe); printf("Suppression 1\n"); supprimer(&maListe,1); afficher(&maListe); printf("Suppression 3\n"); supprimer(&maListe,3); afficher(&maListe); printf("On clear la liste...:\n"); clearListe(&maListe); afficher(&maListe); return 0; }
Citation:

Par contre, je saisis pas trop l'interet d'une liste doublement chainée par rapport à la simplement chainée dans les fonctions que j'ai faite..

Si vous avez des idées d'exercices qui mettraient en valeur ça :wink:

Ca sert, par exemple, à réaliser un traitement de texte. On peut facilement parcourir les lignes de haut en bas, insérer, supprimer... Pour des déplacemements relatifs (top, end, up, down) les fonctions du même nom peuvent aider. Elle s'appuient sur un troisième pointeur (pCurrent)

top : pCurrent := pHead
end : pCurrent := pQueue
up : pCurrent := pCurrent->pPrec
down : pCurrent := pCurrent->pNext

évidemment, on fait attention aux limites...

Pareil avec des menus dynamiques...

Voir 40 message(s) de cette discussion en une page