Discussion :

[kilinette]

Bonsoir

Voici un algo d'insertion ds une liste chaîné double :

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
 
/* Définition du type "liste doublement chaînée d'entiers"
 */
typedef struct liste *ptr_liste;
 
typedef struct liste {
  int info;
  ptr_liste suiv, prec;
} Liste;
 
 
void insere(ptr_liste *l, int aAjouter)
{
  // Itérateur sur la liste
  ptr_liste courant;
  // Pointeur sur le nouveau chaînon
  ptr_liste nouveau ;
 
  // De toute manière, il faudra bien l'allouer ce chaînon!
  nouveau = malloc(sizeof(Liste));
  nouveau->info = aAjouter;
 
  // Le cas où *l est vide est équivalent au cas où il faut ajouter
  // le nouveau maillon en début de liste
  if (*l == NULL || (*l)->info > aAjouter) {
    // Le nouveau est le premier de la liste
    nouveau->prec = NULL;
    nouveau->suiv = *l;
 
    // Seule différence: le chaînage de l'ancien premier doit être modifié
    // s'il existe!
    if (*l != NULL)
      (*l)->prec = nouveau;
 
    // Le début de la liste (paramètre E/S) est modifié
    *l = nouveau;
  }
  else {
    // Dans les autres cas, il faut trouver où insérer le chaînon
    // On s'arrête sur celui qui doit être juste à droite du nouveau
    // chaînon (éventuellement le dernier de la liste)
    courant = *l;
    while (courant->suiv != NULL && courant->suiv->info < aAjouter) {
      courant = courant->suiv;
    }
 
    // Le chaînage du nouveau maillon est mis-à-jour
    nouveau->suiv = courant->suiv;
    nouveau->prec = courant;
    // est-on à la fin? si non, le nouveau est le précédent d'un maillon
    if (courant->suiv != NULL) {
      courant->suiv->prec = nouveau;
    }
 
    // Dans tous les cas, c'est le suivant du chaînon courant
    courant->suiv = nouveau;
  }
}

Une chose me turlupine... Pourquoi est-ce de partout *l qui est écrit ? Par exemple :

Code :

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

1
2
 
  if (*l == NULL || (*l)->info > aAjouter)

Personnellement, et je sais que c'est faux, j'aurais écrit l tout court... Le pointeur pointe sur NULL.

En fait là, l est un pointeur sur une liste ? *l correspond à quoi ?

J'aurais fait ainsi moi :

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
 
/* Définition du type "liste doublement chaînée d'entiers"
 */
typedef struct liste {
  int info;
  liste *suiv, *prec;
} Liste;
 
 
void insere(liste *l, int aAjouter)
{
 
  liste *courant;
 
  liste *nouveau ;
 
 nouveau = malloc(sizeof(Liste));
 
 nouveau->info = aAjouter;
 
 if (l == NULL || l->info > aAjouter) { /*si || est un "ou alors" */
 
    nouveau->prec = NULL;
    nouveau->suiv = l;
 
    if (l != NULL)
      l->prec = nouveau;
 
    l = nouveau;
  }
  else {
    courant = l;
    while (courant->suiv != NULL && courant->suiv->info < aAjouter) {
      courant = courant->suiv;
    }
 
    nouveau->suiv = courant->suiv;
    nouveau->prec = courant;
 
    if (courant->suiv != NULL) {
      courant->suiv->prec = nouveau;
    }
 
 
    courant->suiv = nouveau;
  }
}

Ce n'est pas juste j'imagine^^

[diogene]

Une chose me turlupine... Pourquoi est-ce de partout *l qui est écrit ? Par exemple :

Parce que, si il y a une insertion en tete de liste, l'adresse du début de liste doit changer

Code :

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

if (*l == NULL ...

Si la liste est vide

Code :

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

*l = nouveau;

Alors , le début de la liste est nouveau.
Puisqu'il faut pouvoir modifier la tete de liste, son ADRESSE est passée à la fonction. Du coup, le premier de la liste (si il existe est) *l
Soit dit en passant, utiliser l comme identificateur est chercher les problèmes, ca ressemble trop à 1 ( de même pour O et 0)

[kilinette]

Vi mais pourquoi passer par un pointeur sur pointeur de liste (ptr_liste *l) et non un pointeur sur liste directement (comme j'ai fait après, je ne sais pas si c'est juste).
C'est ça qui m'embrouille

[diogene]

Vi mais pourquoi passer par un pointeur sur pointeur de liste (

C'est ma réponse précédente : Le début de la liste est repéré par un pointeur sur le premier élément de la liste appelons le Debut (de type Liste * par conséquent). Si dans la fonction je veux (et je dois) pouvoir modifier ce pointeur je dois passer son adresse, & Debut , à la fonction. Cette valeur est donc du type Liste ** ou ptr_liste *l

[kilinette]

Et ds la solution que j'ai écrite c'est une copie locale du pointeur qui est modifiée alors et non l ?

[Nasky]

Oui.
Si tu veux modifier l'endroit où pointe le pointeur, il faut passer son adresse.
Dans les fonctions du types fgets(), on passe le pointeur par valeur car on modifie la valeur de l'endroit pointé par la chaine et non l'endroit où doit pointer la chaine. C'est là la différence à comprendre.

Nas'

[Emmanuel Delahaye]

Oui.
Si tu veux modifier l'endroit où pointe le pointeur, il faut passer son adresse.
Dans les fonctions du types fgets(), on passe le pointeur par valeur car on modifie la valeur de l'endroit pointé par la chaine et non l'endroit où doit pointer la chaine. C'est là la différence à comprendre.

Nas'

J'aimerais bien qu'on essaye de ne plus confondre pointeur, qui est une variable et adresse qui est la valeur d'un pointeur.

http://emmanuel-delahaye.developpez.....htm#pointeurs

Je réécris et tout devient clair et simple :

Si tu veux modifier la valeur du pointeur, il faut passer son adresse.
Dans les fonctions du types fgets(), on passe l'adresse du tableau de char car on modifie la valeur des char du tableau et non la valeur de l'éventuel pointeur contenant l'adresse du tableau.