Discussion :

[moonp]

bonjour

je suis débutante en c++, mais j'ai des conaissance en java et en C , je doit modifier ce programme pour créer une liste circulaire .

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
template<class Elem> class link {
public :
    Elem element ;
    Link * next ;
    Link (const Elem& elemval, Link* nextval =NULL)
    {
        element =elemval ; next =nextval ; 
    }
    Link( Link*nextval =NULL)
    {
        next= nextval ;
    }

le programme ci dessus est fait pour créer une liste chainée, et je sais qu'il faut ajouter un pointeur vers le premier élément
Ma question c'est au niveau des lignes soulignées j'ai pas très bien saisi la syntaxe


Merci pour votre aide

[camboui]

Et bien c'est presque très bien comme ça, il manque juste dans le prototype des méthodes (fonctions) le type de valeur retour. S'il n'y en a pas il faut mettre "void". Genre:

Code :

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

void Link(Link const *nextval =NULL)

EDIT:

J'ai rien dit, ce sont des constructeurs...

[moonp]

Merci beaucoup camboui
Mon problème c'est au niveau des templates et les réferences je n'ai pas très bien saisi le concept , par conséquent j'ai pas compri la syntaxe des lignes soulignés

[darkman19320]

Bonjour,

Je pense plutôt que tu voulais que ton template de classe "link" voulais s'appelait "Link".

Et par conséquent, ton code était correct.

[moonp]

ouiii ,exactement

Sinon je ne sais toujours pas comment la transformer en liste circulaire

[Emmanuel Deloget]

Sinon je ne sais tjrs pas comment la transformer en liste circulaire

Une liste circulaire est une liste dont le dernier élément pointe sur le premier élément. Vu que tu as une liste simplement chaînée, tu n'as qu'un pointeur next à traiter - il ne doit jamais être nul, sauf quand la liste est vide.

Quand on a un élément, this.next == this.

Avec deux éléments, this->next->next = this.
Avec trois éléments, this->next->next->next = this.

Et ainsi de suite.

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
 
template<class Elem> class Link {
private:
    void update_me()
    {
        if (!next) {
            next = this;
        } else {
            Link *current = next;
            while (current->next != next) {
                current = current->next;
            }
            // we found a node which already loop on next, so we must insert
            // us at that very point. 
            current->next = this;
        }
    }
    void delete_me()
    {
        if (next == this)
            return; // the list is going to die with us
        Link *prev = NULL;
        Link *current = next;
        while (current) {
            if (current == this) {
                // we just hit the "end" of the list, i.e. the point
                // where we go back to us. We need to bypass
                // us, and then we're done. 
                prev->next = next;
                break;
            }
            current = current->next;
        }
    }
public :
    Elem element ;
    Link * next ;
    Link (const Elem& elemval, Link* nextval =NULL)
    {
        element =elemval ; next =nextval ; 
        update_next();
    }
    Link( Link*nextval =NULL)
    {
        next= nextval ;
        update_next();
    }
    ~Link()
    {
        delete_me();
    }
    ...

Très honnêtement, ce n'est probablement pas la bonne manière de faire une liste circulaire. Dans ce design, c'est à l'appelant de gérer la construction correcte de la liste, ce qui n'est pas vraiment une bonne chose. Un algorithme inspiré de ce que propose la librairie standard du C++ aurait pu être plus intéressant...

[moonp]

Mercii beaucoup Emmanuel Deloget pour la réponse
Désolé pour le retard dema réplique mon pc s'est planté

[moonp]

Bonsoir

J'ai ce programme ( c'est la suite en fait du programme précedent ) que j'ai essayé toute la journée de comprendre ... ( j'avoue que ça m'a fait une bonne révision de C++ )

Y a pas mal de passage que j'ai pas très bien saisi , merci de m'aider

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
59
// linked list implementation

template <class Elem>
class LList :public List<Elem> {
private:
    Link<Elem>* head; 
    Link<Elem>* tail;
    Link<Elem>* fence;
    int leftcnt; // size of left 
    int rightcnt; // size of right , déja je ne sais pas pourquoi le prof divise la lsite en deux , ce qui est à droit de fence (élément courant) et ce qui est à gauche du fence //
    void init(){
        fence=tail=head=new Link<Elem>;  //  
        leftcnt=rightcnt=0;

// return link nodes to free stores
void removeall() {
    while(head!=NULL) { // pourqoi vider la liste alors que on l'a initialisé ??
        fence=head;
        head=head->next;
        delete fence; // les lignes rouges :est ce que ça veut dire qu'on se déplace à partir du head puis on supprime le fence ?? et pourquoi ?
    }
}

public:
LList(int size =DefaultListSize)
{init() ; }  // pourquoi on a fait ce init ???

~LList () {removeall();} // Destructor

void clear() { removeall ; init() ;}


void setStart() {
    fence =head, rightcnt+=leftcnt; // je ne comprend toujours pas pourquoi on divise la liste en left et right ? la fonction setStart fait quoi au juste ??
    leftcnt=0;
}

void setEnd(){
    fence=tail;leftcnt+=rightcnt;
    rightnct=0;

void next() {
    // don’t move fence if right empty if (fence!=tail) {
    fence=fence->next ; rightcnt--;
    leftcnt++;} //que fait la fonction next ??
}

int leftlenth() const {  //pourqoi on a ajouté const ??
    return leftcnt ; 
}

int rightlenth() const {
    return rightcnt;}

bool getValue(Elem& it) const {
    if (rightLength()==0= return false;
    it=fence->next->element;
    return;}   //le roles du code bleu

Merci encore une fois !

[camboui]

'vais essayer de me rattrapper suite à ma bêtise d'hier

Dans init() je verrais plutôt ceci:
fence=tail=head=NULL;

removeall():
Les éléments sont supprimés un par un depuis head, fence semble ne servir que de variable temporaire.

LList(int size =DefaultListSize) pourquoi on a fait ce init ???
Pour initialiser les membres de la classe.

int leftlenth() const pourqoi on a ajouté const ??
C'est important, il garantit qu'aucun membre de la classe n'est modifié.

bool getValue(Elem& it) const
(pas return; mais return true;)
Le code bleu renvoit par référence l'élément "courant" de la liste, s'il existe.

Si j'ai bien compris, "fence" joue le rôle de curseur dans la liste.
Avec setStart() tu positionnes ce curseur en début de liste, avec next() tu le fais avancer, et avec getValue() tu récupères la valeur sous ce curseur.

[moonp]

Merci beaucoup Camboui c'est beaucoup plus clair
oui fence c'est l'élement courant