Échanger deux noeuds

Version imprimable

Comment fait-on pour échanger deux nœuds d'une liste chainée passée en paramètres ??? Voici un exemple de structures pour les exemples :)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 typedef struct { char nom[100]; char profession[100]; } Citoyen; typedef struct n { struct n *suiv; struct n *prec; Citoyen citoyen; } N; N *echange(N *liste, char *nom1, char *nom2);

24/02/2009, 08h24
Melem

En supposant que le nom est unique pour chaque Citoyen (le prototype de ta fonction echange impose) :

- Tu recherches l'élément de la liste ayant pour nom nom1. Fais-en une copie (e1).
- Tu recherches l'élément de la liste ayant pour nom nom2. Fais-en une copie (e2).
- Soient p1 et s1 les précédent et suivant de e1 et p2 et s2 les précédent et suivant de e2
- Remplace p1.suivant par e2, s1.precedent par e2, p2.suivant par e1 et s2.precedent par e1.
- Adapte pour le C et optimise l'algorithme.

Je ne suis pas sur que ça fonctionne voici ce que j'ai implémenté :
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 N *echange(N *liste, char *nom1, char *nom2) { N *e1,*e2,*p1,*p2,*s1,*s2; N *i; N *a,*b; N *temp = NULL; i = liste; a = liste; b = liste; if(strcmp(nom1,i->citoyen.nom)==0) { a = i; } while(i->suiv !=NULL) { i=i->suiv; if(strcmp(nom1,i->citoyen.nom)==0) { a = i; } } i = liste; if(strcmp(nom2,i->citoyen.nom)==0) { b = i; } while(i->suiv !=NULL) { i=i->suiv; if(strcmp(nom2,i->citoyen.nom)==0) { b = i; } } e1 = a; e2 = b; p1 = e1->prec; s1 = e1->suiv; p2 = e2->prec; s2 = e2->suiv; p1->suiv = e2; s1->prec = e2; p2->suiv = e1; s2->prec = e1; if(e1->prec == NULL) liste = e1; if(e2->prec == NULL) liste = e2; return liste; }
En gros ce que ça doit faire c'est d'échanger deux nœuds dans la liste chainée double duquel on retrouve les noms passés en paramètre. La fonction retourne le premier nœud de la liste.

Si vous avez une façon plus efficace je serai preneur. :mrgreen:

J'ai une erreur d'exécution dés que j'arrive à cette ligne.

p1->suiv = e2;

25/02/2009, 13h14
diogene

La remise en état du chaînage est un peu plus complexe.

soit a et b les pointeurs sur les structures à rechaîner.
1- si a ou b est NULL ou si a == b, il n'y a rien à faire.
2- sinon les deux structures existent et sont différentes.

* les pointeurs concernés sont :
-les deux pointeurs suiv et prec de a
-le pointeur suiv du prédécesseur de a (si il existe)
-le pointeur prec du suiv de a (si il existe)
- et autant pour b
soit un total de 8 pointeurs

* Le pointeur suiv de a doit être placé sur le nouveau suivant de a. Celui-ci est l'ancien suivant de b à moins que celui-ci n'ai changé dans l'opération d'échange, c'est à dire était b (ce qui n'est pas possible, b ne peut être son propre suivant) ou a (qui doit devenir b).
Si b->suiv == a alors le nouveau a->suiv = b
Sinon le nouveau a->suiv = l'ancien b->suiv

* Le pointeur prec de a doit être placé sur le nouveau précédent de a. Celui-ci est l'ancien précédent de b à moins que celui-ci n'ai changé dans l'opération d'échange, c'est à dire était b (ce qui n'est pas possible, b ne peut être son propre précédent) ou a (qui doit devenir b).
Si b->prec == a alors le nouveau a->prec = b
Sinon le nouveau a->prec = l'ancien b->prec

* Si a a un prédécesseur, le nouveau suiv de ce prédécesseur est b

* Si a a un suivant, le nouveau prec de ce suivant est b

* idem pour b

Enfin, la tête de liste a pu changer pour devenir a si elle était b ou b si elle était a
26/02/2009, 22h42
dj.motte

Citation:

Envoyé par diogene

La remise en état du chaînage est un peu plus complexe.

soit a et b les pointeurs sur les structures à rechaîner.
1- si a ou b est NULL ou si a == b, il n'y a rien à faire.
2- sinon les deux structures existent et sont différentes.

* les pointeurs concernés sont :
-les deux pointeurs suiv et prec de a
-le pointeur suiv du prédécesseur de a (si il existe)
-le pointeur prec du suiv de a (si il existe)
- et autant pour b
soit un total de 8 pointeurs

* Le pointeur suiv de a doit être placé sur le nouveau suivant de a. Celui-ci est l'ancien suivant de b à moins que celui-ci n'ai changé dans l'opération d'échange, c'est à dire était b (ce qui n'est pas possible, b ne peut être son propre suivant) ou a (qui doit devenir b).
Si b->suiv == a alors le nouveau a->suiv = b
Sinon le nouveau a->suiv = l'ancien b->suiv

* Le pointeur prec de a doit être placé sur le nouveau précédent de a. Celui-ci est l'ancien précédent de b à moins que celui-ci n'ai changé dans l'opération d'échange, c'est à dire était b (ce qui n'est pas possible, b ne peut être son propre précédent) ou a (qui doit devenir b).
Si b->prec == a alors le nouveau a->prec = b
Sinon le nouveau a->prec = l'ancien b->prec

* Si a a un prédécesseur, le nouveau suiv de ce prédécesseur est b

* Si a a un suivant, le nouveau prec de ce suivant est b

* idem pour b

Enfin, la tête de liste a pu changer pour devenir a si elle était b ou b si elle était a

Oui c'est une belle explication. Mais codée en C cela donne quoi ?
Certes les directives sont plus faciles que les réalisations.

La solution par l'exemple est encore plus facile, pour lancer une directive supplémentaire

Codée en C ça donne :

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
#include <stdio.h>
#include <string.h>
 
typedef struct {
    char nom[100];
    char profession[100];
} Citoyen;
 
typedef struct n {
    struct n *suiv;
    struct n *prec;
    Citoyen citoyen;
} N;
 
void EchangerNoeuds(N * e1, N * e2);
void AfficherListe(N * pListe);
 
int main()
{
    N A, B, C, D;
 
    strcpy(A.citoyen.nom, "A");
    A.prec = NULL;
    A.suiv = &B;
 
    strcpy(B.citoyen.nom, "B");
    B.prec = &A;
    B.suiv = &C;
 
    strcpy(C.citoyen.nom, "C");
    C.prec = &B;
    C.suiv = &D;
 
    strcpy(D.citoyen.nom, "D");
    D.prec = &C;
    D.suiv = NULL;
 
    /* A est actuellement la tete de liste */
 
    AfficherListe(&A);
 
    EchangerNoeuds(&A, &C);
 
    /* C est maintenant la tete de liste */
 
    AfficherListe(&C);
 
    return 0;
}
 
void EchangerNoeuds(N * e1, N * e2)
{
    if (e1 != e2)
    {
        N * p1, * s1, * p2, * s2;
 
        p1 = e1->prec;
        s1 = e1->suiv;
 
        p2 = e2->prec;
        s2 = e2->suiv;
 
        e2->prec = (p1 != e2 ? p1 : e1);
        e2->suiv = (s1 != e2 ? s1 : e1);
 
        e1->prec = (p2 != e1 ? p2 : e2);
        e1->suiv = (s2 != e1 ? s2 : e2);
 
        if (p1 != NULL && p1 != e2)
            p1->suiv = e2;
 
        if (s1 != NULL && s1 != e2)
            s1->prec = e2;
 
        if (p2 != NULL && p2 != e1)
            p2->suiv = e1;
 
        if (s2 != NULL && s2 != e1)
            s2->prec = e1;
    }
}
 
void AfficherListe(N * pListe)
{
    N * i;
 
    for(i = pListe; i != NULL; i = i->suiv)
        printf("%s\n", i->citoyen.nom);
 
    printf("\n");
}