# nietod..Josephus algorithm with circular list

I have made so fa this circular list and I'm trying to implement the Josephus algorithm which you solved using arrys with it. I'm stuck. it doesn't do what I want and i can't find my error.
here is the Cicular List class:

#ifndef CIRCLIST_H

#define CIRCLIST_H

#include <iostream.h>

template <class T>

class CircularList {

public:

CircularList();

~CircularList();

int Add(T item);                     // return -1 if out of memory

int Remove(int index);

int Get(int index, T&item) const;    // return -1 if not gotten

int Empty() const { return size==0; }

int Size() const { return size; }

struct Node {

T data;

Node *left, *right;

};

private:

int size;

};

//----------------------------//

template <class T>

CircularList<T>::CircularList() {

size=0;

}

//----------------------------//

template <class T>

CircularList<T>::~CircularList() {

while (Size()>0) Remove(0);

}

//----------------------------//

template <class T>

Node *temp, *cur;

temp = new Node;                    // get a new node and fill with data

if (temp==NULL) { cout << "Out of memory for linked list node allocation: Add() failed." << endl; return -1; }

temp->data = item;

while(cur != head  &&  cur->data < temp->data) {

cur=cur->right;

}

temp->right = cur;

temp->left = cur->left;

cur->left->right = temp;

cur->left = temp;

return 1;

}

//----------------------------//

template <class T>

int CircularList<T>::Remove(int index) {

if (Empty() || index<0 || index>=Size() ) return -1;

Node *cur;

for (int i=0; i<index; i++) {

cur=cur->right;

}                                   // at end of loop, cur is pointing

// to the node to delete

cur->left->right = cur->right;

cur->right->left = cur->left;

delete cur;                         // free up space

return size;

}

//----------------------------//

template <class T>

int CircularList<T>::Get(int index, T &item) const {     // similar to Remove

if (Empty() || index<0 || index>=Size() ) return -1;

Node *cur;

for (int i=0; i<index; i++) {

cur=cur->right;

}                                   // at end of loop, cur is pointing

// to the node to get

item=cur->data;                     // transfer data

return 1;

}

//----------------------------//

template <class T>

int CircularList<T>::Find(T item) const {

if (Empty()) return -1;

int index=0;

cur=cur->right;

index++;

}

return (cur==head ? -1 : index);

}

#endif

Here is the main I have done so far:

/*Josephus*/
#include <iostream.h>
#include "Circlist.h"
main()
{
CircularList <int> P;
int n;
int m;

cout<<"Enter the amount of people in the circle:\n";
cin>>n;
cout<<"Enter what m-th person you want to take out:\n";
cin>>m;
int z=n;

for(int i=1; i<=n; i++)
{
}
int x=1;
for(i=1; i<=z; i++)
{
while(n!=1)
{
if(x==m)
{
P.Remove(i);
x=0;
n--;
}
x++;
}
cout<<i;
}

cout<<P.Find(n);

return(0);
}

Need Help!!!!
###### Who is Participating?

Commented:
>> CircularList<T>::CircularList()
Is a little strange  it initalizes the empty list to have 1 node!  That is sort of weird.  You will need to take precautions to never use that node because the data it stores (T data) is neverset to anything useful.   I can't even image a good way to take that precaution.

A better idea is to initailzie the head node to NULL to indicate an empty list.

Your
function woudl be easier to do if the list maintains a "tail" pointer.  This is just like "head" but it points to the end of the list.  This will require changes in other places in the program too.  But the end result is simpler and faster code.  For example, the Add code does a search through the whole list.  This takes time to do and it is a potential source for errors.  With a tail pointer it isn't necesary.

>> int CircularList<T>::Remove(int index)
It is unusuall to allow any item to be removed.  usually a queue would only allow the first item (0) to be removed.  Not a problem at all, just a little unusual.  (Not unheard of either, I do it in my queue class.)

However, you have a bug here.  You update the pointers within the list okay--I think, I'm only giving it a quick look at the moment--but you don't ever update the head pointer (or the tail pointer, if you add it--which you really should.)  So if the first item is removed (or the last if you have a tail) the head pointer (or tail) is left pointing to a deleted item.  BAD!
0

Commented:
What are you exactly trying to do here:

for(i=1; i<=z; i++)
{
while(n!=1)
{
if(x==m)
{
P.Remove(i);
x=0;
n--;
}
x++;
}
cout<<i;
}

The 'while' loop works only when i=1,
and when i=2,3,...,z it is not even entering this 'while',so the outputs will be 123456789100 .The last zero was added because of

cout<<P.Find(n);

The function don't find the 'n' numberby the reason that you already deleted all your Nodes in your list in the 'while' loop.

Explain the algorithm you want to use.

Yura
0

Commented:
I see how you are getting out of the problem I mentioned of that unused first node.  i.e when the list is created you create a node, but don't initialize its "data" member.  and you don't ever want to use this as a real node since its "data" is not set.  You are not ever using this node.  When you start a search you start the search with the Next pointer in this node, like

So you always skip the node that head points to.  Well that works, but it is a waste.  All your are using that first node for is to store a pointer.  So your "head" member stores a pointer to something that stores a pointer for you.  Cut out the "something"--the node.  Let the head pointer store the pointer to the first useful node.  Not to this wasted node.

In
>> nt CircularList<T>::Find(T item) const {

You have

Why do you have the test "cur!=head"  I assume you are trying to detect when you reach the end of the list.  Will that work?

Oh maybe it will work.  I think you are trying to make the pointers at the end of the list "wrap"  i.e the "head" node's previous pointer points to the last node and the last node's next pointer points to the head node.  Is that right?  I've seen it done that way.  Its not the easiest way.  A better way is to place NULL pointers at the end of the list.  The first (head) node's previous pointer is NULL and the last node's next pointer is NULL.

See if you can fix that stuff and post what you get.
0

Author Commented:
Didn't quite understood what you meant. I'm really stuck in all of this and every stuff I tried make it worst
0

Commented:
>> Didn't quite understood what you meant.
I said alot.  you don't understand any of it?

The first thing you need to do is to make the queue class work, then worry about making the code that uses it work.
0

Author Commented:
it is without queue
0

Commented:
Huh?
0

Author Commented:
nevermind
0

Commented:
Well what do you want to do?  Are you trying what I suggested?  Do you still want help?
0

Author Commented:
I'm trying what you said but i get too many errors. So I haven't paste it. Is worst that one pasted in here
0

Commented:
If you think you can do it by yourself, go ahead and try, otherwise paste it in.  Or paste in portions and see if my help on one portion will help you fix others.
0

Commented:
Do you want to paste the results for a "final review"
0

Author Commented:
don't worry...i test it and it runs
thanx
=)
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.