la concaténation de deux listes chainées

Version imprimable

salut j'ai un exercice et je n'arrive pas à l'exécuter correctement ,merci de m'aider !
il s'agit de:
on considère deux listes dont les adresses de tête et de queue sont mémorisées dans des variables T1,T2,Q1 et Q2.Écrivez les instructions qui concatènent ces deux listes,sans création de maillon.A la fin du travail T1 et Q1 pointeront sur la tête et la queue du résultat.
voilà non essai :

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
96
97
98
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
//exercice 2 la concéténation de deux listes
//definition du structure element
typedef struct element
{
       int val;
       struct element *suivant;
}maillon;
typedef maillon* liste;
 /*1.ajout en tête d'une liste */ 
liste ajoutEnTete(liste l,int valeur)
     {
      liste nv=(liste)malloc(sizeof(maillon));
      nv->val=valeur;
  if(l==NULL)
      {
               l=nv;
      nv->suivant=NULL;
 
      }
  else
      {
      nv->suivant=l;
      l=nv;
       }
       return l;
       }
liste concat(liste T1,liste T2)
{
      liste Q1=NULL;
      liste Q2=NULL;
      liste tmp=NULL;
      if(T1==NULL)//si la liste T1 était vide 
         {
                       if(T2==NULL)//si la liste T2 était vide donc on retrun NULL(une liste vide )
                           return NULL;
                       else
                           {      
                                  T1=T2;
                                  tmp=T2;
                                  while(tmp->suivant!=NULL)
                                  {
                                                  tmp=tmp->suivant;
                                  }
                                  Q1=tmp;
                                  return T1;
                                  }
         }      
      else
         {     //cherchons Q1
                      tmp=T1;
                      while(tmp->suivant!=NULL)
                          {
                                 tmp=tmp->suivant;
                          }
                          Q1=tmp;
                      if(T2==NULL)
                          {
                                  return T1;
                          }
                      else
                          {
                                  tmp=T2;
                                  while(tmp->suivant!=NULL)
                                     {
                                                           tmp=tmp->suivant;
                                     }
                                     Q2=tmp;
                                     Q1->suivant=T1;
                                     Q1=Q2;
                                     return T1;
                          }
         }                       
}                                                
void affiche(liste l)
     {
                   liste tmp=l;
                   while(tmp!=NULL)
                   {
                                   printf("%d->",tmp->val);
                                   tmp=tmp->suivant;
                   }
 
     }         
int main()
{
    liste T1=NULL,T2=NULL;
       T1=ajoutEnTete(T1,1);
       T2=ajoutEnTete(T2,2);
       affiche(T1);
       getch();
       T1=concat(T1,T2);
       affiche(T1);
       getch();
       return 0;
}

j'ai poster la totalité du code pour que vous pussiez l'exécuter chez vous .
en exécutant ce code j'ai une boucle infinie lors de l'affichage de liste finale(c à d la liste e concaténation).

merci d'avance .

29/01/2010, 14h32
jabbounet

pour la concaténation c'est simple le dernier element de la première liste doit pointer sur le premier élément de la seconde pour n'en former qu'une seule (cela se fait en jouant avec le champ suivant de ta structure).

Après comme c'est un exercice je ne vais pas aller beaucoup plus loin car cela reviendrai a te donner la solution.
29/01/2010, 15h44
hindou90

Citation:

Envoyé par jabbounet

pour la concaténation c'est simple le dernier element de la première liste doit pointer sur le premier élément de la seconde pour n'en former qu'une seule (cela se fait en jouant avec le champ suivant de ta structure).

oui je suis d'accord avec vous sur le principe ,mais bien entendue il faut le précéder par par des contrôler tels que si la 1 liste était vide ou l'inverse .

Bonjour,

Dans "liste concat(liste T1,liste T2)"
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 liste concat(liste T1,liste T2) { // [...] if (T1 == NULL) { if (T2 == NULL) { // Cas 1 } else { // Cas 2 } } else { if (T2 == NULL) { // Cas 3 } else { // Cas 4 } } }
- Cas 1: Ok.
- Cas 2: Inutile, retourne directement T2
- Cas 3: 1ère partie du code inutile, retourne directement T1
- Cas 4:
C'est là que tu fais une boulette, tu mets comme maillon suivant du dernier maillon de la chaine T1 le premier maillon de la chaine ... T1 !
Du coup, petite boucle sur l'affichage !

29/01/2010, 17h00
hindou90

salut
merci pour votre participation

Citation:

- Cas 1: Ok.
- Cas 2: Inutile, retourne directement T2
- Cas 3: 1ère partie du code inutile, retourne directement T1
- Cas 4:
C'est là que tu fais une boulette, tu mets comme maillon suivant du dernier maillon de la chaine T1 le premier maillon de la chaine ... T1 !
Du coup, petite boucle sur l'affichage !

c'est unitile de modifier la tête et la queue de T1 puis ce que c'est demander .

Citation:

C'est là que tu fais une boulette, tu mets comme maillon suivant du dernier maillon de la chaine T1 le premier maillon de la chaine ... T1 !
Du coup, petite boucle sur l'affichage !

4 cas si les deux chaines étaient remplisses donc on relie la queue de T1 avec la tête de T2 :

Code:

Q1->suivant=T1;

et comme la queue de la liste à retourner doit être Q1:

Code:

Q1=Q2;
29/01/2010, 17h15
Fabllot
Citation:

Envoyé par hindou90

c'est unitile (ndr: utile ?) de modifier la tête et la queue de T1 puis ce que c'est demander .

Certes, je n'avais pas bien lu l'énoncé, donc
Cas 2: Ok.
Cas 3: Ok.
Cas 4: Je maintiens ce que j'ai dis : tu fais une boucle...
Code:

1 2 3 4 5 6 7 else { // Cas 4 [...] Q1->suivant=T1; // BOUCLE !!! Q1=Q2; return T1; }
A cet endroit, Q1 pointe sur le dernier élément de T1, or tu assignes comme élément suivant (le dernier élément de T1), le premier élément de T1...
Le dernier pointe sur le premier = boucle !!!

salut oui c'est ça effectivement !
Code:

1 2 3 4 5 6 else { // Cas 4 [...] Q1->suivant=T2; Q1=Q2; return T1; }
merci c genial

30/01/2010, 00h39
hindou90

salut
malgré votre correction le programme ne marche pas
j'ai sous le console:

Citation:

1->

!!!
17/02/2010, 17h05
hindou90

salut
please aidez moi à trouve mon erreur :oops:

Quelle erreur ?
Si tu as fait la modif du code, tu dois obtenir un résultat qui semble correct.
Chez moi, ce code
Code:

1 2 3 4 5 6 7 8 9 10 T1=ajoutEnTete(T1,1); T1=ajoutEnTete(T1,3); T2=ajoutEnTete(T2,2); T2=ajoutEnTete(T2,4); affiche(T1); printf("\n"); affiche(T2); printf("\n"); T1=concat(T1,T2); affiche(T1);
donne :

Citation:

3->1->
4->2->
3->1->4->2->

19/02/2010, 09h20
hindou90

merci ça marche :)