Solved
nietod..Josephus algorithm with circular list
Posted on 2000-02-28
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!!!!