Solved

nietod..Josephus algorithm with circular list

Posted on 2000-02-28
13
1,157 Views
Last Modified: 2012-08-14
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!!!!
0
Comment
Question by:milalik
  • 7
  • 5
13 Comments
 

Expert Comment

by:YuraPhink
ID: 2568417
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
 
LVL 22

Accepted Solution

by:
nietod earned 140 total points
ID: 2568546
>> 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
>> 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(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
 
LVL 22

Expert Comment

by:nietod
ID: 2568563
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.
0
 

Author Comment

by:milalik
ID: 2568650
Didn't quite understood what you meant. I'm really stuck in all of this and every stuff I tried make it worst
0
 
LVL 22

Expert Comment

by:nietod
ID: 2569098
>> 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 Comment

by:milalik
ID: 2571145
it is without queue
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 22

Expert Comment

by:nietod
ID: 2571149
Huh?
0
 

Author Comment

by:milalik
ID: 2575048
nevermind
0
 
LVL 22

Expert Comment

by:nietod
ID: 2576245
Well what do you want to do?  Are you trying what I suggested?  Do you still want help?  
0
 

Author Comment

by:milalik
ID: 2578801
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
 
LVL 22

Expert Comment

by:nietod
ID: 2579693
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
 
LVL 22

Expert Comment

by:nietod
ID: 2595723
Do you want to paste the results for a "final review"
0
 

Author Comment

by:milalik
ID: 2600370
don't worry...i test it and it runs
thanx
=)
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Suggested Solutions

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now