liste chainee, revenir a l'element precedent

**Pitou5464** · 16/10/2006, 20h23

Salut,

Je voudrais savoir comment apres avoir identifier un element en comparant ces donnees, le supprimer en faisant pointer l'element precedent vers celui d'apres, celui que je desire supprimer a l'aide de free.

**Trap D** · 16/10/2006, 21h41

Il faut garder un pointeur sur le précédent c'est la seule solution ou alors travailler avec une liste doublement chaînée.

**Médinoc** · 16/10/2006, 21h48

Je pense que la liste doublement chaînée est la meilleure solution.
En plus, tu peux plus facilement vérifier qu'une liste est OK et ne se termine pas en boucle...

**Pitou5464** · 16/10/2006, 22h32

ok mais je sais pas encore faire de liste doublement chainee

**Médinoc** · 16/10/2006, 22h37

C'est pas beaucoup plus difficile, tu sais.
Essaie, on t'aideras à corriger si ça ne marche pas.

**Pitou5464** · 16/10/2006, 22h39

ok je vais tenter ca demain dans la journee, je posterai mon code en meme temps merci pour vos reponses

**Trap D** · 16/10/2006, 22h48

Tu sais pour une liste simplement chaînée c'est facile quand même :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
liste *precedent = NULL
liste *ptrcourant = tete
tant que ptrcourant != NULL et ptrcourant->donnee != donnee_cherchee faire
  precedent  <- ptrcourant
  ptrcourant <- ptrcourant->suite
fin tant que
si ptrcourant != NULL alors
  si precedent == NULL alors
    tete <- tete->suite
  sinon
     precedent->suite <- ptrcourant->suite
  fin si
fin si

mat.M · 16/10/2006, 23h01

Envoyé par Pitou5464

ok mais je sais pas encore faire de liste doublement chainee

? C'est pas compliqué voire plus simple qu'une liste simple ; il suffit de déclarer des pointeurs vers noeuds suivants et précédents

typedef struct element { int numero; int valeur;};
typedef struct gestionnaire_liste{ element *noeud ; gestionnaire_liste*precedent ;
gestionnaire_liste*suivant ;
};

**Pitou5464** · 17/10/2006, 08h53

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
typedef struct  s_list
{
  void          *data;
  struct s_list *next;
}               t_list;
 
int     my_rm_all_eq_from_list(t_list **begin,void *data_ref,int (*cmp)())
{
  t_liste       *precedent;
  t_liste       *ptrcourant;
 
  *precedent = NULL;
  *ptrcourant = tete;
  while (ptrcourant != 0 && ptrcourant->data != data_ref)
    {
      precedent = ptrcourant;
      ptrcourant = ptrcourant->next;
    }
  if (ptrcourant != 0)
    if (precedent == 0)
      tete = tete->next;
    else
      precedent->next = ptrcourant->next;
}
 
void    *xmalloc(int size)
{
  void  *temp;
 
  temp = malloc(size);
  if (temp == 0)
    exit(1);
  return (temp);
}

voila le code mais je sais pas a a quoi correspond tete

**Médinoc** · 17/10/2006, 09h36

tete doit correspondre à begin...

**Médinoc** · 17/10/2006, 10h01

Tiens, voici un petit exemple pour une liste doublement-chaînée, avec trois fonctions utilitaires et une implémentation de ce que tu semblais chercher à faire:

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
#include <stddef.h>
 
typedef struct s_dlist
{
struct s_dlist * pPrev;
struct s_dlist * pNext;
void           * pData;
} t_dlist;
 
typedef int (*VOIDCOMPAREPROC)(void const *, void const *);
/*typedef int (*LISTCOMPAREPROC)(t_dlist const *, t_dlist const *);*/
typedef void (*DELETEPROC)(t_dlist *);
 
/* Aller au premier élément
   ------------------------ */
t_dlist * GetFirst(t_dlist * pElem)
{
if(pElem==NULL)
	return NULL;
 
while(pElem->pPrev != NULL)
	pElem = pElem->pPrev;
 
return pElem;
}
 
/* Aller au dernier élément
   ------------------------ */
t_dlist * GetLast(t_dlist * pElem)
{
if(pElem==NULL)
	return NULL;
 
while(pElem->pNext != NULL)
	pElem = pElem->pNext;
 
return pElem;
}
 
/* Détacher un élément d'une liste
   ------------------------------- */
int Detach(t_dlist * pElem)
{
if(pElem==NULL)
	return -1;
 
/* S'il y a un précédent, on le fait pointer sur le suivant (ou NULL) */
if(pElem->pPrev != NULL)
	pElem->pPrev->pNext = pElem->pNext;
/* S'il y a un suivant, on le fait pointer sur le précédent (ou NULL) */
if(pElem->pNext != NULL)
	pElem->pNext->pPrev = pElem->pPrev;
/* isole l'élément */
pElem->pPrev = NULL;
pElem->pNext = NULL;
 
return 0;
}
 
/* Supprimer tous les éléments dont les données sont égales à pcDataRef
   -------------------------------------------------------------------- */
int MyRemoveAllEqFromList(
 t_dlist ** ppBegin,     /*[in/out] Pointeur vers le début (ou n'importe quel élément) */
 void const * pcDataRef, /*[in] Données de référence */
 VOIDCOMPAREPROC pCmp,   /*[in] Fonction de comparaison */
 DELETEPROC pDelete      /*[in] Fonction pour effacer un élément et ses données */
 )
{
t_dlist * pBegin = NULL;
t_dlist * pCurrent = NULL;
if(ppBegin==NULL || pCmp==NULL || pDelete==NULL)
	return -1;
 
pBegin = GetFirst(*ppBegin);
if(pBegin == NULL)
	return -1;
 
for(pCurrent = pBegin ; pCurrent != NULL ; )
	{
	t_dlist * const pNext = pCurrent->pNext;
 
	if(pCmp(pCurrent->pData, pcDataRef)==0)
		{
		Detach(pCurrent);
		pDelete(pCurrent);
		if(pCurrent==pBegin)
			pBegin = pNext;
		}
	pCurrent = pNext;
	}
 
*ppBegin = pBegin;
 
return 0;
}

Grâce au chaînage double, on peut retrouver le premier élément de la liste à partir de n'importe lequel.
Comme la fonction détruit des éléments de la liste, il faut passer une fonction définie par l'utilisateur pour savoir comment on détruit les données contenues.

**elghadi_mohamed** · 17/10/2006, 14h12

Envoyé par Pitou5464

Code :

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

1
2
3
4
5
typedef struct  s_list
{
  void          *data;
  struct s_list *next,*before;
}               t_list;

je t'ai ajouter le champ before comme ça tu pourrais parcourir la liste dans deux sens et meme faire la chaine circulaire !!

n'oublie pas au debut before=NULL et la fin next=NULL