Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

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!!!!

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>::CircularL

head=new Node;

head->right=head;

head->left=head;

size=0;

}

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

template <class T>

CircularList<T>::~Circular

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

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!!!!

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

Node *cur=head->right;

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

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

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.

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.

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.

All Courses

From novice to tech pro — start learning today.

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!