Member Avatar for c++lover

hi, im working on josepus problem but this programe is not working well it is working in unlimited loop any one can point out the mistakes?????????

#include<iostream>
using namespace std;

class node
{
      private:
      int object;
      node *nextnode;
      public:
      int get(){return object;};
      void set(int object){this->object=object;};
      node *getnext(){return nextnode;};
      void setnext(node *nextnode){this->nextnode=nextnode;};
};
class List
{
      private:
      int size;
      node *headnode;
      node *currentnode;
      node *lastcurrentnode;
      public:
      bool next();
      int get();
      void add(int addobject);
      List();
      friend void traverse(List list);
      friend List addnodes();
      void remove();
      void start();
      int length();
};
List::List()
{
 headnode=new node();
 headnode->setnext(NULL);
 currentnode=NULL;
 lastcurrentnode=NULL;
 size=0;
}
void List:: start()
{
 lastcurrentnode=headnode;
 currentnode=headnode->getnext();
}
void List::add(int addobject)
{
 node *newnode=new node();
 newnode->set(addobject);
 if(currentnode!=NULL)
 {
  newnode->setnext(headnode->getnext());
  currentnode->setnext(newnode);
  lastcurrentnode=currentnode;
  currentnode=newnode;
 }
 else
 {
  newnode->setnext(headnode->getnext());
  headnode->setnext(newnode);
  lastcurrentnode=headnode;
  currentnode=newnode;
  }
  size++;
}

int List::get()
{
 if(currentnode!=NULL)
  return currentnode->get();
}

bool List:: next()
{
 if(currentnode==NULL) return false;
  lastcurrentnode=currentnode;
  currentnode=currentnode->getnext();
  if(currentnode==NULL||size==0)
   return false;
  else
   return true;
}

void List:: remove()
{
 if(currentnode!=NULL&& currentnode!=headnode)
 {
  lastcurrentnode->setnext(currentnode->getnext());
  delete currentnode;
  if (lastcurrentnode->getnext() == headnode)
   currentnode = lastcurrentnode;
  else
   currentnode=lastcurrentnode->getnext();
  size--;
 }
}
int List:: length()
{
 return size;
}                          

void traverse(List list)
{
 node *savedcurrentnode=list.currentnode;
 list.currentnode=list.headnode;
 for(int i;list.next()<=list.length();i++)
 {
  cout<<"\nElement"<<list.get();
 }
 list.currentnode=savedcurrentnode;
}

List addnodes()
{
 List list;
 int count=0;
 cout<<"\n please specify the list length";
 cin>>count;
 int temp;
 for(int i=0;i<count;i++)
 {
  cout<<"please enter element no"<<i+1<<":";
  cin>>temp;
  list.add(temp);
 }
 cout<<"\nlist size is="<<list.size<<endl;
 return list;
}

main()
{
 List list;


 int i,m=3;

 for(i=1;i<=10;i++)list.add(i);
traverse(list);
list.start();
 while(list.length()>1){
  for(i=1;i<=m;i++)
  list.next();
  cout<<"remove"<<list.get()<<endl;
  list.remove();
 }
 cout<<"leader is"<<list.get()<<endl;
 system("PAUSE");
}
Edited by mike_2000_17 because: Fixed formatting
  • 2 Contributors
  • 1 Reply
  • 128 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by chrjs

Dani AI

Generated

— is right to flag the traversal condition as a key problem. Beyond that, several other issues commonly produce infinite loops or undefined behaviour in this kind of linked-list Josephus code: an uninitialized loop counter, passing the list object by value (shallow copy of raw pointers), a movement method that returns a boolean but is compared numerically, missing return paths when the current node is null, and weak ownership semantics (no destructor / copy-control). Fixing those will stop the loop and avoid memory errors.

Practical fixes

  • Make traversal take the list by (const) reference or iterate with a local pointer so you do not copy the object.
  • Initialize loop counters (e.g., int i = 0).
  • Keep the movement method’s return type and its use consistent (either return a pointer/index or a boolean; do not compare that boolean to the length).
  • Either implement proper copy constructor/operator= and destructor, or explicitly delete copying and manage nodes in one owner (or use smart pointers/standard containers).

A much simpler approach is to avoid hand-rolled pointer management entirely. Two concise options:

  • O(n) mathematical solution (fast, no list needed):
int josephus(int n, int k) {
    int res = 0;
    for (int i = 2; i <= n; ++i)
        res = (res + k) % i;
    return res + 1; // 1-based result
}
  • Practical simulation using the STL:
std::list<int> circle;
for (int i = 1; i <= n; ++i) circle.push_back(i);
auto it = circle.begin();
while (circle.size() > 1) {
    for (int count = 1; count < k; ++count) {
        ++it;
        if (it == circle.end()) it = circle.begin();
    }
    it = circle.erase(it);
    if (it == circle.end()) it = circle.begin();
}
int survivor = *circle.begin();

Debugging tips: run with small n and print size, current index/pointer, and the removed value each step; use a debugger or Valgrind to catch invalid reads/deletes. For algorithm background, see the Josephus problem overview: Josephus problem.

Member Avatar for chrjs

In your for loop in the traverse function you have the condition list.next()<=list.length() , but list.next returns a bool value, meaning that it is either 1 or 0. And since the length never changes inside that loop, that loop is infinite unless you enter the loop with the list having a length of 0.

Use code tags, and its Josep[B]h[/B]us, not josepus
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.