Discussion :

[poower]

Bonsoir

Merci à ceux qui vont prendre le temps de lire. Cet exercice est simple c'est juste que j'essaye de décrire au mieux mon problème.
Tous d'abord, voici les structures :

Code :

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

1
2
3
4
5
6
 
typedef struct celem celem;
  struct celem {
  elem value;
  celem *next;
};

Code :

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

1
2
3
4
 
struct lelem {
  celem *head;
};

Voici le prototype de la fonction :

Code :

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

1
2
3
4
5
6
 
// lelem_concatenation_head : concatène en tête de la liste associée à s2 la
// liste associée à s1. À la terminaison, la liste associée à s1 est vide.
//Aucune opération d’allocation ou de désallocation n’est effectuée
 
extern void lelem_concatenation_head(lelem *s1, lelem *s2);

Code de la fonction :

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
 
void lelem_concatenation_head(lelem *s1, lelem *s2) { // AE : s1 != s2
  if (s1 -> head == NULL) {
    return;
   }
  if (s2 -> head != NULL) {
    celem *p = s1 -> head;
    while (p -> next != NULL) {
       p = p -> next;
    }
    p -> next = s2 -> head;       
  }
  s2 -> head = s1 -> head;      // Mon problème se situe
  s1 -> head = NULL;             // sur ces deux lignes
}

Voici mon dessin sur feuille, ou j'ai essayé de représenter au mieux ce que fait le code.
légende : ||header|| -> |value|next| -> |value|next|

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
s1: 
header : ||100|| - -> |1|200|  ->   ->  ->    |2|400| ->   ->  ->    |3|0|->NULL  
 
s2 :           
header: ||500|| - ->|4|600| ->   -> ->       |5|700|  ->  ->  ->    |6|0|->NULL 
 
 
if (s1 -> head == NULL) { 
return; 
}  
 
ici s1->head vaut 100 donc pas NULL on sort du if .
 
 
if (s2 -> head != NULL) { 
celem *p = s1 -> head; 
while (p -> next != NULL) { 
p = p -> next; 
} 
 
Dans le while p parcours la list s1, et  p->next = NULL donc  p se retrouve sur 0 .
 
                                                                  |p|      
s1 :            |1|200|  ->   ->  ->    |2|400| ->   ->  ->    |3|0|->NULL  
 
 
p -> next = s2 -> head;    le precedent next de s1 ( valait 0 ) devient la tête de s2 ( 500) donc : 
 
 s1:    
header: ||100|| - - ->|1|200|  -  - > |2|400| - - >   |3|500|->NULL
 
 
 
s2 -> head = s1 -> head;  , la tête de s2(500) prend la tête de s1 (100) 
 
 

s2 :  header : ||100|| - - -> |4|600| ->   -> ->       |5|700|  ->  ->  ->    |6|0|->NULL 
 
 
s1 -> head = NULL;   la tête de s1 devient NULL: 
 

s1 :          
 ||NULL|| - ->|1|200|  ->   ->  ->    |2|400| ->   ->  ->    |3|500|-> -> -> |4|600| -> -> -> NULL

Que faire ?????

A quoi servent réellement les deux derniers instructions ... ?
Pour moi, la concaténation 1 2 3 4 5 6 marchent rien qu'avec p ->next ( bout de la chaine s1 ) = s2 ->head ( tête chaine s2 ) et je trouve bien 1 2 3 4 5 6
mais avec les deux instructions je m'y perd dans le déroulement du code :



Merci

[foetus]

Ce sont des "espèces de transferts de propriétés"
(transfer of ownership en anglais)

En effet, une fois la concaténation faite il faut se poser la question: que deviennent s1 et s2?
Un truc évident: s2 pointe après au milieu de la nouvelle liste chaînée.

Dans ton cas, 1 possibilité parmi X: on détruit s1, et on met à jour s2.

Il faut le savoir

[poower]

Donc d'après ce que tu me dis , si j'ai bien compris ;

p -> next = s2 -> head
Signifie la tête de s2 ira à la fin de s1 .
Donc c'est dire , un peu le contraire (la tête de s2 va vers la fin de s1) de la description .

Code :

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

1
2
//concatène en tête de la liste associée à s2 la
// liste associée à s1.

p -> next = s2 -> head , donc suffit à concaténer en tête de la liste s2 la liste s1.

La on continue dans le if , donc tous les headers de s2 vont s'accumulé à la fin de s1. jusqu'à avoir s2 == NULL
dans ce cas on sort du if .


Donc on a un dessin avec s1 et s2 et s1 ^ s2

une question comment faire pour que s2 -> head == NULL ??
Puisque le s2 -> head reste inchangé dans s2

[Sve@r]

Donc c'est dire , un peu le contraire (la tête de s2 va vers la fin de s1) de la description .

Code :

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

1
2
//concatène en tête de la liste associée à s2 la
// liste associée à s1.

Bonjour

Généralement, une concaténation se comprend comme "à la fin de". Sinon ça se dit "insertion"...

une question comment faire pour que s2 -> head == NULL ??
Puisque le s2 -> head reste inchangé dans s2

Pourquoi faire ? Quand tu concatènes deux fichiers ensembles, tu obtiens un gros truc mais le second fichier n'est pas détruit !

Tu devrais faire des trucs "atomiques" (ne faisant qu'une seule chose). Une fonction de concaténation qui te génère une nouvelle liste à partir de deux mais rien de plus. Si tu veux ensuite détruire une des deux listes, tu passes alors par une fonction de destruction...

[Médinoc]

Tu devrais faire des trucs "atomiques" (ne faisant qu'une seule chose). Une fonction de concaténation qui te génère une nouvelle liste à partir de deux mais rien de plus. Si tu veux ensuite détruire une des deux listes, tu passes alors par une fonction de destruction...

De nos jours et dans un tel cadre (un code académique qui n'a aucune chance d'être "performance-critical"), je suis d'accord avec toi.
Quand j'étais plus jeune, j'aurais dit que "copier pour ensuite effacer l'original" (surtout pour une liste chaînée, avec toutes ces allocations et désallocations) était hautement inefficace par rapport à un déplacement.