copie de liste chainée

Version imprimable

trouvé dans le livre de Delanoy, exercices en C++

Je pense qu'en fait la liste est copiée à l'envers? pouvez-vous le confirmer ou l'infirmer?
Merci d'avance

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct noeud
{
int valeur;
noeud *suivant;
};
 
 
//creation d'une nouvelle liste identique à l'ancienne
noeud*adsouce=Debut_Liste_initiale;
noeud*adbut;
debut=NULL;
while(adsouce)
{
adbut=new noeud;                              //creation nouveau noeud
adbut->valeur=adsouce->valeur;        //copie valeur
adbut->suivant=debut;                       //insertion nouveau noeud
debut=adbut;                                    //dans la liste
adsouce=adsouce->suivant; 
}

30/08/2004, 05h18
Luc Hermitte

Ca y ressemble bien.

(T'es sûr que ce n'est pas un bouquin de C ?)
30/08/2004, 10h09
Aurelien.Regat-Barrel

Il utilise new.
30/08/2004, 10h09
la drogue c'est mal

Citation:

Envoyé par Luc Hermitte

Ca y ressemble bien.

(T'es sûr que ce n'est pas un bouquin de C ?)

avec un new j'en doute mais il est vrai que la pertinance du code est à revoir
30/08/2004, 10h50
hegros

C'est pour seul but d'exercice ? il existe deja dans la stl de quoi faire des list
30/08/2004, 10h57
freddy766

Si tu veux la liste dans le bon ordre, il te suffira de faire un "reverse" de cette meme liste.
Attention à l'implementer correctement, sinon tu risques de perdre un temps monstre à l'execution.

c'est peut etre une façon ca...

bon, j'ai pondu ça rapidement, je crois que ca marche (mais j'ai pas de compilo sous la main pour tester). Normalement ca fait une copie exacte de la chaine pointée par adSource, et la tête de la copie est accessible depuis adBut.
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 struct noeud { int valeur; noeud *suivant; }; noeud *adSource = Debut_Liste_initiale; noeud *adBut; noeud *pNoeud; // sert à se balader sur la liste copiée sans perdre la tête :) // copie de la tête de la liste chainée. adBut = new noeud; adBut->valeur = adSource->valeur; adSource = adSource->suivant; pNoeud = adBut; while(adSource) { pNoeud->suivant = new noeud; pNoeud->suivant->valeur = adSource->valeur; adSource = adSource->suivant; pNoeud = pNoeud->suivant; } pNoeud->suivant = NULL;
voila, j'espère que je n'ai pas fait de faute ^^'

30/08/2004, 13h59
professeurr
Salut,

La liste est copiée à l'envers.
Il s'agist ici d'une insertion en tete de liste.

Explication
Code:

1 2 source->|9|-> |8|-> |7|-> |6|-> |5|-> |4|-> |3|-> |2|-> |1|-> |0|-> NULL dest->NULL
le programme récupère le premier élément ici 9 et l'insère à la tete de la liste de dest ce qui donnera après la première itération:

Code:

dest->|9|->NULL

à la deuxième itération on récupère le 2e élément ici 8 on l'insère à la tete de la liste de dest ce qui donnera après la 2e itération:

Code:

dest->|8|-> |9|->NULL

....
et à la fin

Code:

dest->|0|-> |1|-> |2|-> |3|-> |4|-> |5|-> |6|-> |7|-> |8|-> |9|->NULL

Si tu veux obtenire la liste dans le bon ordre il faut dans ce cas faire une insertion en queue de liste mais cela fait parcourir à chaque fois la lsite ce qui est couteux.

Une alternative est d'utiliser une structure différente pour définir les liste:
Code:

1 2 3 4 5 6 7 8 9 10 struct noeud { int valeur; noeud *suivant; }; //definition d'une liste à double accès typedef struct _list{ noeud *tete, *queue; }List, *pList;

Pourquoi mélanger C et C++ (struct/pas struct) ?

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
struct list
{
    list() : head_(0), tail_(0) {};
    list(list const & rhs) : head_(0), tail_(0) 
    {
        node * src = rhs.head_;
        if (src) 
        {
            tail_ = head_ = new node(src->value_);
 
            for (src=src->next_ ; src != 0 ; src=src->next_)
            {
                tail_ -> next_ = new node(src->value_);
                tail_ = tail_ -> next_;
            }
        }
    }
    list & operator=(list const & rhs)
    {
        list tmp(rhs);
        swap(tmp);
        return *this;
    }
    void swap(list & other)
    {
        std::swap(head_, other.head_);
        std::swap(tail_, other.tail_);
    }
 
    ... autres trucs publics ...
 
private:
    struct node
    {
        node(T const & v, node * n=0) : value_(v), next_(n) {}
        node * next_;
        T value_;
    };
    node * head_;
    node * tail_;
};

PS: le préfixage par le tiret-bas est réservé aux personnes qui implémentent compilateurs et bibliothèques standards. Un tiret pour le C, deux pour le C++.

30/08/2004, 18h00
jmv
Citation:

Envoyé par Luc Hermitte

PS: le préfixage par le tiret-bas est réservé aux personnes qui implémentent compilateurs et bibliothèques standards. Un tiret pour le C, deux pour le C++.

une question: si on écrit
Code:

1 2 3 4 5 6 struct node { node(T const & v, node * n=0) : _value(v), _next(n) {} node * _next; T _value; };
est-ce vraiment génant ?
il n'y a pas de risque de confusion avec les symboles créés par le compilo puisque _next et _value sont des membres de node.

(C'est vrai que dans le doute, il vaut mieux éviter de le faire.)
30/08/2004, 18h19
JolyLoic
Citation:
Envoyé par jmv

une question: si on écrit

Code:

1 2 3 4 5 6 struct node { node(T const & v, node * n=0) : _value(v), _next(n) {} node * _next; T _value; };

est-ce vraiment génant ?
il n'y a pas de risque de confusion avec les symboles créés par le compilo puisque _next et _value sont des membres de node.
Il y a toujours risque de confusion, à cause du préprocesseur, qui ne respecte en rien les règles de portées.

En théorie, seules les noms commeçant par __ ou par _X avec X une lettre majuscule quelconque sont interdits tout le temps, et les noms commençant par _x avec x minuscule interdits au niveau du namespace global.

En pratique, le plus simple est d'éviter tout ce qui commence par _, c'est aussi simple, et comme les compilos ne sont pas forcément réputés pour respecter cette règle...
30/08/2004, 18h28
jmv

Le preprocesseur... je l'avais oublié celui-la :oops: , lol
merci pour ta réponse
30/08/2004, 23h09
Trap D

Citation:

Envoyé par la drogue c'est mal

Citation:

Envoyé par Luc Hermitte

Ca y ressemble bien.

(T'es sûr que ce n'est pas un bouquin de C ?)

avec un new j'en doute mais il est vrai que la pertinance du code est à revoir

Ce n'est pas la première fois qu'un livre de Delanoy est mis en cause ...
31/08/2004, 00h13
tomsoyer

intérêt l'utilisation de struct?

Merci à tous pour ces précieuses explications,

:bravo: :ange: :ccool: :chin:
ceci étant dit ça ne porte pas à conséquence dans le reste de l'exo :D
à part le fait que je doutais sérieusement de ma compréhension!!

Sinon, je me pose la même question que Luc:(pardon si j'ai pas compris)
quel est l'intérêt d'utiliser un struct ici plutôt qu'une classe noeud? :?:
31/08/2004, 00h49
Luc Hermitte

struct et class à un détail près (exploité dans mon exemple), c'est la même chose. Seule la visibilité par défaut change.

Ma remarque concernait le mélange de styles.
En C, on faisait des typedef pour se faciliter la vie avec les structures. En C++, ce n'est plus nécessaire -- dans du code limité aux compilateurs C++. En C on rapellait le struct pour définir des pointeurs sur le type que nous sommes en train de définir. (de même, cela ne se fait plus en C++).
Or ici, on a eu un typedef et pas de rappel de struct dans la définition du noeud. Soit, un mélange de styles.
31/08/2004, 18h20
tomsoyer

bien bien :merci: :lahola: à tous et à Luc