liste doublement chainée

Version imprimable

05/06/2007, 22h28
Ucom-C++

liste doublement chainée
salut tout le monde

j'ai le exercice suivant:

comment peut on inversé une liste double chaînée;

merci bien
Code:

1 2 3 4 5 6 7 typedef struct list { int val; list *suivant; list *precedent; }
05/06/2007, 22h40
Franck.H

Salut !

Tu le fait et tu nous montre ton code, alors seulement nous serons disposés à t'aider mais nous n'allons certainement pas le faire à ta place ! Si tu as un problème quelconque dans ton code ou ton algorithme, montre et nous t'aiderons !
05/06/2007, 22h40
souviron34

on n'est pas sur www.onfaittesdevoirs.com ... :mrgreen:

Donc travaille un peu, réfléchis, essaye de coder....

Et on t'aidera... peut-être 8-)

[EDIT]

Grillé...

[/EDIT]
05/06/2007, 22h52
GyZmoO

[HS] J'ai quand même cliquer sur www.onfaittesdevoirs.com :aie: [/HS]
05/06/2007, 22h54
Franck.H

http://franck.hecht.free.fr/images/D...rt_de_rire.gif

Citation:

Envoyé par GyZmoO

[HS] J'ai quand même cliquer sur www.onfaittesdevoirs.com :aie: [/HS]

voila mon code

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
 
#include <stdio.h>
#include <stdlib.h>
 
struct maillon
{
  int valeur;
  struct maillon * suivant;
};
 
typedef struct maillon * VersMaillon ;
 
VersMaillon construire();
void ecrire(VersMaillon);
VersMaillon renverser(VersMaillon);
 
int main()
{  
	VersMaillon debut;
 
	debut=construire();
	printf("Voici la liste de vos entiers dans l'ordre de la liste chaînée construite : \n");
	ecrire(debut);
	debut=renverser(debut);
	printf("Voici la liste de vos entiers dans l'ordre de la liste chaînée renversée : \n");
	ecrire(debut);
   return 0;
}
 
VersMaillon construire()
{
	VersMaillon deb, p;
	int donnee;
 
 
	deb=NULL;
	printf("Donnez vos données, tapez -1 pour terminer : \n");
	scanf("%d",&donnee);
	while (donnee!=-1)
	{
		p=(VersMaillon) malloc(sizeof(struct maillon));
		p->valeur=donnee;
		p->suivant=deb;
		deb=p;
		scanf("%d",&donnee);
	}
	return deb;
}
 
VersMaillon renverser(VersMaillon deb)
{
 
		VersMaillon p, q ,r;
 
  if ((deb==NULL)||(deb->suivant==NULL)) return deb;
  q=deb->suivant;
  deb->suivant=NULL; 
  r=q->suivant;
  q->suivant=deb;
  while (r!=NULL)
    {
      p=q;
      q=r;
      r=r->suivant;
      q->suivant=p;
    }
  deb=q;
  return deb;
 
 
}
 
void ecrire(VersMaillon deb)
{
	VersMaillon p;
 
	p=deb;
 
	while (p!=NULL)
	{
		printf("%d ",p->valeur);
		p=p->suivant;
	}
	printf("\n");
}

06/06/2007, 00h35
Emmanuel Delahaye

Citation:

Envoyé par Ucom-C++

j'ai le exercice suivant:

comment peut on inversé une liste double chaînée;

Foutage de gueule detected.
06/06/2007, 09h49
Médinoc

En parlant de listes doublement chaînée, je viens de découvrir un truc tellement gore que je ne pensais même pas que quelqu'un aurait une idée pareille: Les XOR linked lists.
Un truc à ne PAS connaître, sauf pour l'éviter comme là peste.
06/06/2007, 09h51
Médinoc

Au passage, "inverser une liste doublement chaînée", ce n'est pas si foutage de gueule que ça: Si l'on veut vraiment en changer le sens (et non pas juste la parcourir à l'envers), j'ai l'impression que ce n'est pas aussi simple que ça le parait au premier abord...
06/06/2007, 11h01
Emmanuel Delahaye

Citation:

Envoyé par Médinoc

Au passage, "inverser une liste doublement chaînée", ce n'est pas si foutage de gueule que ça: Si l'on veut vraiment en changer le sens (et non pas juste la parcourir à l'envers), j'ai l'impression que ce n'est pas aussi simple que ça le parait au premier abord...

Déjà, pourquoi inverser une liste doublement chainée ?

Bah si c'est nécessaire, il suffit d'en recréer une autre en lisant la première à l'envers et en déplaçant les éléments au fur et à mesure dans la nouvelle. Tout l'intérêt des listes chainées, c'est de ne manipuler que les chainages sans modifier les noeuds ni leurs données.

perso j'avais fait ça sur une liste simplement chainée, le code doit être adaptable pour une doublement chainée, c'était pas super super compliqué

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* --------------------------------------------------------------------------
   inverser_liste ()
   --------------------------------------------------------------------------
   Role : inverse une liste (sans header)
   -------------------------------------------------------------------------- */
void inverser_liste (noeud_s *p_liste)
{
   /* pointeur sur le noeud precedent (initialiser a NULL : fin de liste) */
   noeud_s *p_tmp1 = NULL;
   /* pointeur pour sauvegarder l'adresse de l'element courant (initialise au
      debut de la liste) */
   noeud_s *p_tmp2 = p_liste;
   /* pointeur sur le noeud suivant */
   noeud_s *p_tmp3;
 
   while (p_tmp2 != NULL)
   {
      p_tmp3 = p_tmp2->p_suivant;
      p_tmp2->p_suivant = p_tmp1;
      p_tmp1 = p_tmp2;
      p_tmp2 = p_tmp3;
   }
}

Citation:

Envoyé par Emmanuel Delahaye

Déjà, pourquoi inverser une liste doublement chainée ?

ça reste un très bon exercise pour les méninges ;)

07/06/2007, 13h34
Ucom-C++

merci bien

merci bien exhortae c'est un code facile est efficace

merci bien une autre fois;

résolu o_O