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:

// Circular Linked 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 Find(T item) const; // return -1 if not found

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

int Size() const { return size; }

struct Node {

T data;

Node *left, *right;

};

private:

Node *head;

int size;

};

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

template <class T>

CircularList<T>::CircularList() {

head=new Node;

head->right=head;

head->left=head;

size=0;

}

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

template <class T>

CircularList<T>::~CircularList() {

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

delete head;

}

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

template <class T>

int CircularList<T>::Add(T item) {

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;

cur = head->right;

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

cur=cur->right;

}

temp->right = cur;

temp->left = cur->left;

cur->left->right = temp;

cur->left = temp;

size++; // adjust size

return 1;

}

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

template <class T>

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

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

Node *cur;

cur = head->right;

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

size--; // adjust size

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;

cur = head->right;

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;

Node *cur=head->right;

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

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

{

P.Add(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!!!!

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

>> int CircularList<T>::Add(T item)

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(in

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!