liste chainee, revenir a l'element precedent

Version imprimable

16/10/2006, 20h23
Pitou5464

liste chainee, revenir a l'element precedent

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.
16/10/2006, 21h41
Trap D

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.
16/10/2006, 21h48
Médinoc

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...
16/10/2006, 22h32
Pitou5464

ok mais je sais pas encore faire de liste doublement chainee
16/10/2006, 22h37
Médinoc

C'est pas beaucoup plus difficile, tu sais.
Essaie, on t'aideras à corriger si ça ne marche pas.
16/10/2006, 22h39
Pitou5464

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

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

Code:

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

16/10/2006, 23h01
mat.M

Citation:

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

Citation:

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

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

17/10/2006, 09h36
Médinoc

tete doit correspondre à begin...

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:

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.

17/10/2006, 14h12
elghadi_mohamed
Citation:
Envoyé par Pitou5464

Code:

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

:king:
17/10/2006, 14h22
Franck.H

Voici un tutoriel complet sur la création et gestion d'une liste doublement chaînée: Les listes doublement chaînées en C
17/10/2006, 14h26
Médinoc

Il aime bien la modification de pointeurs pointés en paramètre, ce tuto...