milalik
asked on
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:
// 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!!!!
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!!!!
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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.
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.
ASKER
Didn't quite understood what you meant. I'm really stuck in all of this and every stuff I tried make it worst
>> 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.
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.
ASKER
it is without queue
Huh?
ASKER
nevermind
Well what do you want to do? Are you trying what I suggested? Do you still want help?
ASKER
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
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.
Do you want to paste the results for a "final review"
ASKER
don't worry...i test it and it runs
thanx
=)
thanx
=)
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