la concaténation de deux listes chainées

**hindou90** · 29/01/2010, 14h11

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 :

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

**jabbounet** · 29/01/2010, 14h32

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.

**hindou90** · 29/01/2010, 15h44

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 .

**Fabllot** · 29/01/2010, 16h05

Bonjour,

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

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

**hindou90** · 29/01/2010, 17h00

salut
merci pour votre participation

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

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 :

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

Q1->suivant=T1;

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

Code :

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

   Q1=Q2;

**Fabllot** · 29/01/2010, 17h15

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 :

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

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

**hindou90** · 29/01/2010, 23h55

salut oui c'est ça effectivement !

Code :

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

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

merci c genial

**hindou90** · 30/01/2010, 00h39

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

1->

!!!

**hindou90** · 17/02/2010, 17h05

salut
please aidez moi à trouve mon erreur

**diogene** · 17/02/2010, 17h59

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

Code :

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

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 :

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

**hindou90** · 19/02/2010, 09h20

merci ça marche

la concaténation de deux listes chainées

C

Discussions similaires

Partager

Partager