liste circulaire, ca marche mais j ai quelque questions.

Marsh Posté le 06-03-2004 à 08:14:05

circle.h qui nous as etait donne.

Code :

**********************************************************
ADT circle of Item
A circle of Item is maintained in a clockwise direction.
There is no beginning or end but the current position
is maintained for a non-empty circle.
************************************************************/
#ifndef CIRCLE_H
#define CIRCLE_H
typedef int Item;
class circle{
public:
circle(); // Pre : none
// Post : an empty circle is created
circle(const circle & c); // copy constructor
~circle(); // destructor
// deletes all Items in circle
void insert(Item x); // Pre : none
// Post : x is inserted before (clockwise)
// the current position (if one exists);
// the new current position is the new Item
void remove(); // Pre : the circle is not empty
// Post : the current Item is removed from
// the circle;
// the new current position is the Item
// after (clockwise) the deleted Item*/
void move(int k); // Pre : the circle is not empty
// Post : have moved the current position
// k places (clockwise) around the circle */
Item getCurrent(); // Pre : the circle is not empty
// Post : returns the value of the Item at the
// current position
int size(); // Pre : none
// Post : returns the number of Items in the circle
void printCircle(); // Pre : none
// Post : circle is displayed from the current
// position clockwise around the circle;
// Items are displayed tab-separated on
// one line
bool empty(); // Pre : none
// Post : returns true if circle is empty
// and otherwise false
private:
int length; // maintains the length of the circle
struct node {
Item num;
node * next;
} * ring; // ring points to a circular linked list of
// nodes
// ring->next is the current position
};
#endif

circle.cpp que j ai fais.

Code :

#include <iostream>
#include "circle.h"
using namespace std;
circle::circle()
{
length=0;
ring = NULL;
}
circle::~circle()
{
}
circle::circle(const circle & c)
{
}
void circle::insert(Item x)
{
length++;
if (!ring)
{
ring = new node;
ring->num = x;
ring->next = ring;
}
else
{
node* temp = new node;
temp->next = ring->next;
temp->num=x;
ring->next = temp;
ring = temp;
}
}
void circle::remove()
{
ring->num = ring ->next->num;
ring->next = ring->next->next;
//node* target = ring->next;
//delete target;
length--;
}
Item circle::getCurrent() { return ring->num; }
void circle::move(int k) { for (int i=0; i<k; i++) ring = ring->next; }
int circle::size() { return length; }
bool circle::empty() { return (length==0); }
void circle::printCircle()
{
for (int i=0; i<length; i++)
{
cout << ring->num << "\t";
ring=ring->next;
}
cout << endl;
}

avec ca on devra resoudre le pb d ejosephus mais c est pas le pb.

question
pour la fonction remove
comme j ai un seul pointeur ring, et que justement c est lui qu on veut deleter.

je copie donc le numero de la case apres ring (4) dans ring.
et je "coupe" le chemin en indiquant que ring->next c est ring->next->next.
je diminue la taille de -1 et c est bon.

e.g (we c moche)

bref
est ce que je dois deleter la node en fesant.
node* target = ring->next
et delete node.
?

et aussi, copy constructor qu est que j y mais ?

Code :

node* copy;
copy=ring;
return copy;

:??:
merci,

Reply

Marsh Posté le 06-03-2004 à 08:14:05

Reply

Marsh Posté le 06-03-2004 à 08:38:09

xiluoc a écrit :

circle.h qui nous as etait donne.

Code :

void circle::remove()
{
ring->num = ring ->next->num;
ring->next = ring->next->next;
//node* target = ring->next;
//delete target;
length--;
}

est ce que je dois deleter la node en fesant.
node* target = ring->next
et delete node.
?

Oui, mais pas comme c'est fait en commentaire dans ta fonction sinon tu vas effacer le node courant. Il faut que tu fasses ton target=ring->next avant de décrocher le noeud de la liste, que tu le décroches et après que tu l'effaces. Aussi, il vaudrait mieux ajouter deux tests. Un premier pour t'assurer que le programmeur utilisant cette classe ne fait pas n'importe quoi et n'essaye pas d'effacer un élément alors que la liste est vide ; un deuxième pour remettre node à NULL lorsque le programmeur efface le dernier élément de la liste (sinon il va avoir des petits soucis lors de son prochain insert).

Citation :

et aussi, copy constructor qu est que j y mais ?

Il faut que tu y parcoures la liste à copier et que pour chaque élément d'origine, tu en crées un nouveau dans la liste de destination ; le plus simple à coder étant de parcourir la liste d'origine d'un coté et d'utiliser la fonction insert pour chaque item de l'autre.

Reply

Marsh Posté le 06-03-2004 à 08:50:22

merci,
oui le commentaire etait mal place il vas au debut pour le link et a la fin le delete target.

Code :

void circle::remove()
{
if (length==0) return;
else if (length==1) { delete ring; }
else
{
node* target = ring->next;
ring->num = ring ->next->num;
ring->next = ring->next->next;
delete target;
length--;
}
}

j ai utiliser cette classe pour resoudre josephus,
(au cas ou tu ne le saurai pas)
un cercle de n gas, tu choisis k pour intervalle et tout les k tu remove.

y a petit bug je tombe pas sur la bonne personne mais j y travaille =)

[3615 my life]
pour info c est notre premier assignement (devoir noter, y en a 4 par semestre et celui ci vaut 4% de la note final) de l unite comp225 ( programmation c++ data structure et algo) seconde annee a sydney. (macquarie uni)

Message édité par xiluoc le 06-03-2004 à 08:50:50

Reply

Marsh Posté le 06-03-2004 à 09:01:54

Code :

if (length==1) { delete ring; }

Non, non, non. Deux bugs sur cette ligne.

Reply

Marsh Posté le 06-03-2004 à 09:14:41

hummm
il reste une node.(ring)
ring->next pointe vers ring

eh ben je la delete non ?
et y a plus rien ah si je dois invoquer le deconstructor de circle peut etre ?

inplementation de josephus

Code :

int main()
{
int n,k;
cout << "\tThe Josephus Problem" << endl;
cout << "Please enter values for n and k : ";
cin >> n >> k;
// to fix : error checking
circle c;
for (int i=1; i<=n; i++) c.insert(i);
c.move(1);
c.printCircle();
while (c.size() >1)
{
c.move(k-1);
c.remove();
c.printCircle();
}
cout << "survivor : " << c.getCurrent() << endl;
}

Reply

Marsh Posté le 06-03-2004 à 09:42:14

xiluoc a écrit :

hummm
il reste une node.(ring)
ring->next pointe vers ring

eh ben je la delete non ?
et y a plus rien ah si je dois invoquer le deconstructor de circle peut etre ?

Quelles seront les valeurs de length et de ring après le delete de ce dernier élément ?

Reply

Marsh Posté le 06-03-2004 à 09:47:24

oups,
length --;
ring =NULL;

Reply

Marsh Posté le 11-03-2004 à 13:53:43

:hello: ,

j ai dut mal a comprendre le copy constructor, les bouquins que j ai n en parlent pas trop.

sinon pour le destructor :

Code :

while (length!=0) { remove(); }

<quote>
Il faut que tu y parcoures la liste à copier et que pour chaque élément d'origine, tu en crées un nouveau dans la liste de destination ; le plus simple à coder étant de parcourir la liste d'origine d'un coté et d'utiliser la fonction insert pour chaque item de l'autre.
</quote>

je cree un nouveau pointeur ring2 ?
et ensuite j insert un truc du genre :

Code :

for(int i = 0; i <= length; i++)
{
c.insert(ring->data);
ring=ring->next;
}

le pointeur ring vas donc faire un tour complet ni vu ni connu :whistle:
Ca serait sympa de m eclaircir un peu sur ce point.
:hello:

Reply

Marsh Posté le 12-03-2004 à 07:04:58

xiluoc a écrit :

:hello: ,

j ai dut mal a comprendre le copy constructor, les bouquins que j ai n en parlent pas trop.

Le copy constructor sert surtout à deux choses:
- initialiser un objet en une passe à partir d'un objet de la même classe
- copier un objet automatiquement sans faire une copie membre à membre

Par exemple, imaginons une méthode de votre classe single:

Code :

class single{
....
void test(single s)
{
}
....};

Lorsque vous appelez la méthode test, si vous n'avez pas défini de copy constructor, comme le paramètre s de type single est passé par valeur, le compilateur fera une copie membre à membre pour vous. En sortie de la fonction, cette copie est détruite. Comme il s'agissait d'une copie membre à membre, cela veut dire que le pointeur ring de votre objet d'origine est maintenant invalide. Faire un copy constructor (correct) permet d'éviter ce genre de bugs.

Un exemple pour que cela soit plus clair :

Code :

item x,y,z;
single toto, for_bug;
toto.insert(x);
toto.insert(y);
toto.insert(z);
// toto est copié membre à membre à cause du passage par valeur
// et du copy constructor qui n'est pas défini
for_bug.test(toto);
// ici, la copie de toto est détruite
// donc toto.ring est maintenant invalide
// access violation
toto.remove()
// access violation
toto.insert(z)
// access violation...

Citation :

sinon pour le destructor :

Code :

while (length!=0) { remove(); }

C'est bon.

Citation :

je cree un nouveau pointeur ring2 ?
et ensuite j insert un truc du genre :

Code :

for(int i = 0; i <= length; i++)
{
c.insert(ring->data);
ring=ring->next;
}

le pointeur ring vas donc faire un tour complet ni vu ni connu :whistle:

Il faut que vous utilisiez un autre pointeur (node * ring2=s.ring; par exemple) parce qu'une déclaration correcte du copy constructor sera :

Code :

single(const single & s)
{
//...
}

C'est-à-dire que s (c'est l'objet à copier) est une référence vers un objet "constant" et que vous ne pouvez donc pas modifier ses membres. D'où la nécessité d'utiliser un autre pointeur tel que ring2.

Reply

Marsh Posté le 12-03-2004 à 13:01:57

merci ! pour toute ces explication !

je vais expliquer ce que j ai fait, et en meme temps essayer de comprendre pourquoi ca marche pas completement.

circle::circle(const circle & c)
si c pointe vers null, alors ma copy aussi.
sinon,
on cree un nouveau pointeur ring_cursor qui pointe vers la meme chose que c.ring (deja la je ne savait pas qu on pouvait acceder a une varible private d un objet en fesant obljet.var)
tant qu on as pas fait le tour de la source,
on insert(ring_cursor->num)
et on avance ring_cursor.

Code :

circle::circle(const circle & c)
{
if (c.ring==NULL) ring=NULL;
else {
node* ring_cursor = c.ring;
for (int i=0; i <= c.length; i++)
{
insert(ring_cursor->num);
ring_cursor = ring_cursor->next;
}
}
}

pour tester le copy constructor j ai fait ca :

Code :

circle c,d;
c.insert(1);
c.insert(2);
c.insert(3);
d=c;
c.printCircle();
d.printCircle();
c.remove();
c.remove();
c.printCircle();
d.printCircle();

et helas ... j obtient ca:

Code :

3 1 2 //c bon (le 3 correspond au pointeur ring)
3 1 2 //c bon la copie a bien marche !
2 //c bon j enleve le 3 et 1
2 2 2 // :/

Message édité par xiluoc le 12-03-2004 à 13:05:35

Reply

Marsh Posté le 12-03-2004 à 13:01:57

Reply

Marsh Posté le 12-03-2004 à 13:06:39

Code :

if (c.ring==NULL) ring=NULL;

Vous avez un bug sur cette ligne (que vaut length?).

Code :

d=c;

Ici, vous n'utilisez pas le constructeur par copie mais l'opérateur d'affectation.

Pour utiliser le constructeur par copie, il faut faire à la place :

Code :

circle d(c);

Message édité par docmaboul le 12-03-2004 à 13:07:16

Reply

Marsh Posté le 12-03-2004 à 13:51:21

ca y est ca marche! , eh ben j y aurai mis le temps.

Code :

circle::circle(const circle & c)
{
if (c.ring==NULL)
{
ring=NULL;
length =0;
}
else {
ring = NULL;
length = 0;
node* ring_cursor = c.ring;
while (length != c.length)
{
ring_cursor = ring_cursor->next;
insert(ring_cursor->num);
}
}
}

Reply

liste circulaire, ca marche mais j ai quelque questions.

Sujets relatifs:

Leave a Replay