Discussion :

[tomsoyer]

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 :

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
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; 
}

[Luc Hermitte]

Ca y ressemble bien.

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

[Aurelien.Regat-Barrel]

Il utilise new.

[la drogue c'est mal]

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

[hegros]

C'est pour seul but d'exercice ? il existe deja dans la stl de quoi faire des list

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

[Ca$ul]

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 :

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
 
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 ^^'

[professeurr]

Salut,

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

Explication

Code :

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

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 :

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

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 :

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

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

....
et à la fin

Code :

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

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 :

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

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;

[Luc Hermitte]

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

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

[jmv]

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 :

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

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

[JolyLoic]

une question: si on écrit

Code :

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

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

[jmv]

Le preprocesseur... je l'avais oublié celui-la , lol
merci pour ta réponse

[Trap D]

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

[tomsoyer]

Merci à tous pour ces précieuses explications,


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

Sinon, je me pose la même question que Lucpardon si j'ai pas compris)
quel est l'intérêt d'utiliser un struct ici plutôt qu'une classe noeud? :

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

[tomsoyer]

bien bien à tous et à Luc