Pointers + Joesphus Problem

[NickLSSU]

Hi everyone
I'm doing a c++ program that simulates the Josephus Problem:
http://en.wikipedia.org/wiki/Josephus_problem

I have to use and linked list, but I think I have some pointers not pointing to the right place. Can anybody help me out?

Here's the code:

#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

int main()
{

struct ListRec
{
  ListRec *leftLink;
  int info;
  ListRec *rightLink;
};

 typedef ListRec * List;

  List survivors = NULL;
  List selected = NULL;
  List start = NULL;
  List end = NULL;
  ofstream out("output.txt");


  for (int i = 1; i <=41; i++) //Attach survivor to end of list
    {
      List newSurv;
      newSurv->info = i;
      newSurv->rightLink = NULL;
      newSurv->leftLink = survivors;
      survivors = newSurv;
      if(i == 1)
	start = survivors;
      if(i == 41)
        end = survivors;
    }


  start->leftLink = end;
  end->rightLink = start;
  survivors = start;
  //At this point, survivors points to the node containing 1

  for(int i = 1; i <40; i++)
    {
      for(int j = 0; j < 3; j++)
	{
	  selected = survivors;
	  survivors = survivors->rightLink;
	}
      cout<<"The next vitctim will be the one in position "
	  <<selected->info<<endl;

      //Delete selected from survivors

      selected->leftLink->rightLink = selected->rightLink;
      selected->rightLink->leftLink = selected->leftLink;
      //Points the survivor on the left of selected to the right and the
      //survivor on the right of selected to the left

    }
  cout<<"The two survivors are initially in positions "
      <<survivors->info<<" and "
      <<survivors->rightLink->info<<endl;
  

  return 0;
}

And here is the output:

The next vitctim will be the one in position 41
The next vitctim will be the one in position 41
..........
The next vitctim will be the one in position 41
The two survivors are initially in positions 41 and 41

Thank you!

[Ivan Sidarau]

why you don't want to use std::list ?

[clanmjc]

See below...

for (int i = 1; i <=41; i++) 
{
  List newSurv; //First off you are trying to use an uninitialized pointer??
  newSurv->info = i;

Your implementation is wrong too. Do a little more research if on anything connecting a head to a node.

[Vins3Xtreme]

declare the struct and typedef outside the main, then you must use 'new' to allocate space in memory for a new 'ListRec':

#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

struct ListRec
{
  ListRec *leftLink;
  int info;
  ListRec *rightLink;
};

typedef ListRec * List;

int main(){
   
    List selected = NULL;
    List start = NULL;
    List end = NULL;
    List survivors = NULL;
    ofstream out("output.txt",ios::out);
    //insert
    for (int i = 1; i <=41; i++){
      List newSurv = new ListRec;  //you must use 'new' to allocate space in memory, because 'newSurv' is undefined
      newSurv->info = i;
      newSurv->rightLink = NULL;
      newSurv->leftLink = survivors;
      survivors = newSurv;
      if(i == 1)
	start = survivors;
      if(i == 41)
        end = survivors;
    }

    start->leftLink = end;
    end->rightLink = start;
    survivors = start;

    for(int i = 1; i <40; i++) {
        for(int j = 0; j < 3; j++){
	    selected = survivors;
	    survivors = survivors->rightLink;
	}
        cout<<"The next vitctim will be the one in position " <<selected->info<<endl;

        //delete
        selected->leftLink->rightLink = selected->rightLink;
        selected->rightLink->leftLink = selected->leftLink;
    }

    cout<<"The two survivors are initially in positions "<<survivors->info<<" and"<<survivors->rightLink->info<<endl;
  

  return 0;

[Gaminic]

Personally I detest this kind of thing: typedef ListRec * List;
It hides the fact that List is not an object. Like clanmjc said, you're using an unitialized pointer. It should point to an object, but it doesn't [yet]. newSurv->info dereferences a meaningless pointer (a nullptr in the best scenario).

I'd suggest breaking up the concept of a linked list into Nodes (= elements) and the List (head and tail pointers plus possibly metadata). Now, you have an odd mix (Why does every Survivor keep track of the head and tail of the list? That defeats the entire point of a linked list).

Also, the problem seems to be perfectly suited for a circular list (head->prev = tail and tail->next = head), which means that keeping the tail isn't that useful, because you can immediately find it by head->prev. Lastly, since you're moving in one direction (the k'th next person), a singly-linked list might be sufficient (in which case you can still avoid the tail pointer).