Liste doublement chainée

**sorry60** · 01/12/2005, 18h12

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 !

Le .h

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
#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 :

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
#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 :

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

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

**Emmanuel Delahaye** · 01/12/2005, 18h33

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 :

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

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

**sorry60** · 01/12/2005, 19h02

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 :

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

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...?)

**Emmanuel Delahaye** · 01/12/2005, 19h11

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

**Médinoc** · 01/12/2005, 20h55

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

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

)

**sorry60** · 01/12/2005, 22h03

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

(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

**Jack_serious** · 01/12/2005, 22h33

Envoyé par Emmanuel Delahaye

[*]Fuites mémoire...

Code :

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

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 ?

**Pouic** · 01/12/2005, 22h37

Envoyé par Jack_serious

Envoyé par Emmanuel Delahaye

[*]Fuites mémoire...

Code :

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

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

**Emmanuel Delahaye** · 01/12/2005, 22h42

Envoyé par Pouic

Envoyé par Jack_serious

Envoyé par Emmanuel Delahaye

[*]Fuites mémoire...

Code :

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

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

**sorry60** · 02/12/2005, 11h16

Envoyé par Emmanuel Delahaye

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

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
 
#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;

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

**Emmanuel Delahaye** · 02/12/2005, 11h22

Envoyé par sorry60

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

Et le #endif, il est où ? Et je recommande H_LISTED pour éviter de commencer un jour par E, qui est reservé...

**sorry60** · 02/12/2005, 11h23

Envoyé par Emmanuel Delahaye

Envoyé par sorry60

Oui je les avais mais ça compilait pas

Et le #endif, il est où ?

Arf quel idiot !

**sorry60** · 02/12/2005, 11h26

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

listed.h

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
#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 :

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
#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 :

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
#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 ?

**Emmanuel Delahaye** · 02/12/2005, 11h32

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 :

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
 
/* 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 :

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

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

**sorry60** · 02/12/2005, 11h34

Envoyé par Emmanuel Delahaye

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

-Wall -Wextra -ansi -O2

et non il ne voit pas

et moi non plus..je suis mal reveillé ce matin

**Emmanuel Delahaye** · 02/12/2005, 11h44

Envoyé par sorry60

Je compile avec les options

-Wall -Wextra -ansi -O2

et non il ne voit pas

et moi non plus..je suis mal reveillé ce matin

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

**sorry60** · 02/12/2005, 11h47

Envoyé par Emmanuel Delahaye

Envoyé par sorry60

Je compile avec les options

-Wall -Wextra -ansi -O2

et non il ne voit pas

et moi non plus..je suis mal reveillé ce matin

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

Non pas de warning

J'ai la derniere version de DevCpp

**sorry60** · 02/12/2005, 16h59

Voici une fonction qui supprime un élément :

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
/* 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

**Médinoc** · 02/12/2005, 17h18

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.

**Emmanuel Delahaye** · 02/12/2005, 17h32

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 :

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
 
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 :

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
 
#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;
}

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

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