Josephus Problem with circular link lists

In your program you will read in the number of soldiers, the eliminati

Page 1 of 1

2 Replies - 9081 Views - Last Post: 10 April 2008 - 05:39 PM Rate Topic: -----

#1 chicadie002  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 09-April 08

Josephus Problem with circular link lists

Post icon  Posted 09 April 2008 - 09:50 PM

 class Link
{
	 public int iData;
	 public Link next;

	 // Constructor
	 public Link ( int item )
	 {
		iData = item;
		next = null;
	 }

	 // Print contents
	 public String toString ()
	 {
		String str = "( " + iData + " ) ";
		return str;
	 }

}

class CircularList
{
	private Link head;
  
	// Constructor
  public CircularList () 
  {
	head = null;  
  }

  // Insert an element in the list
  public void insert ( int item )
  {
	  //new temp object made every time called
	  Link temp = head;
	  Link newLink = new Link(item);
	  if( head != null)
	  {
		 
		  while(temp.next != head)
		  {
			  temp = temp.next;
			  newLink.next = head;
			  temp.next = newLink;
			  head = newLink;
		  }
	  }
	  if ( head == null)
	  {
		  head = newLink;
		  newLink.next = head;
	  }
  }

  // Find the link with the given key NOT FINISHED
  public Link find ( int key )
  {
	  Link current = head;
		while ( current.iData != key )
		{
		  if ( current.next == null )
			return null;
		  else
		current = current.next;
		}

		return current;

   }
  // Delete a link with a given key
  public Link delete ( int key )
  {
	  Link current = head;
	  Link previous = head;
	  Link tail = current;
	  
	  while ( current.iData != key)
	  {
		  if ( current.next == null)
		  
			  return null;
		  else
		  {
			  previous = current;
			  current = current.next;
			  
		  }
	  }
	  
	  if ( current == head )
		  head = head.next;
	  else
	 	  previous.next = current.next;
	  
	  
	  if ( current != null)
	  {
		  if (current.next == current)
		  {
			  current = null;
			  return current;
		  }
		  
		  if (current.next != current)
		  {
			  while(tail.next != current)
			  {
				  tail = tail.next;
			  }
			  current = current.next;
			  tail.next = current;
		  }
	  }
	  return current;
  }
  // Delete the nth link starting from the Link start 
  // Return the next link from the deleted Link
  public Link deleteAfter ( Link start, int n )
  {
	  
  }

  // Return a string representation of a Circular List
  public String toString ()
  {
	  StringBuffer buf = new StringBuffer();
		int count = 0;

		Link current = head;
		while ( current != null )
		{
		  if ( count == 4 )
		  {
			buf.append ( current.toString() + "\n" );
		 count = 0;
		  }
		  else
		  {
			buf.append ( current.toString() + " " );
		count++;
		  }

		  current = current.next;
		}

		return buf.toString();
	  }


  }

public class Josephus
{
//  program  will read in the number of soldiers, the elimination number n, and the soldier from whom the counting starts. 
//havent done this yet
}




[b]I am not sure if my logic is correct for a circular link list in my delete, insert, find and toString method. I am also slightly confused as to what should be done in delete after?! should i just call the delete method? delete the key and print the new link?

Is This A Good Question/Topic? 0
  • +

Replies To: Josephus Problem with circular link lists

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8327
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Josephus Problem with circular link lists

Posted 10 April 2008 - 04:45 PM

If you want a circular link list your object link needs a head and a tail not only a head.

Link head, tail;

for the first link head and tail point to itself

then new need an insertAfter() and insertBefore() methods.
Was This Post Helpful? 0
  • +
  • -

#3 chicadie002  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 09-April 08

Re: Josephus Problem with circular link lists

Posted 10 April 2008 - 05:39 PM

View Postpbl, on 10 Apr, 2008 - 04:45 PM, said:

If you want a circular link list your object link needs a head and a tail not only a head.

Link head, tail;

for the first link head and tail point to itself

then new need an insertAfter() and insertBefore() methods.



i changed it, to have a head and a tail earlier today, but i keep getting a null pointer exception.

import java.util.*;
class Link
{
 public Object element;
 public Link next;

 // Constructor
 public Link ( Object o)
 {
	element = o;
	next = null;
 }

}

class CircularList 
{
  private Link tail;
  private Link head = tail.next;

  // Constructor
  public CircularList ()
  {
	head = null;
	tail = null;
  }

  // Insert a link at the head of the list
  public void insert ( Object o )
  {
	Link newLink = new Link ( o );
	newLink.next = head;
	head = newLink;
  }

  // Find the link with the given key. Assumes non-empty linked list
  public Link find ( Object key )
  {
	Link current = head;
	while ( current.element != key )
	{
	current = current.next;
	}
	return current;
  }

  // Delete a link with a given key. Assumes non-empty linked list
  public Link delete ( Object key )
  {
	Link current = head;
	Link previous = tail;

	while ( current.element != key )
	{
		previous = current;
		current = current.next;
	}

	if ( current == head )
	  head = head.next;
	else
		//not sure what this part does
	  previous.next = current.next;
	return current;
  }

  // Return a string representation of a Linked List
  public String toString ()
  {
	StringBuffer buf = new StringBuffer();
	int count = 0;

   Link current = head;
	while ( current != null )
	{
	  if ( count == 4 )
	  {
		buf.append ( current.toString() + "\n" );
	count = 0;
	  }
	  else
	  {
		buf.append ( current.toString() + " " );
	count++;
	  }

	  current = current.next;
	}

	return buf.toString();
  }
  
  
//Delete the nth link starting from the Link start 
  // Return the next link from the deleted Link
  //public Link deleteAfter ( Link start, int n )
  {
	  
  }
}
  



public class Josephus 
{
	public static void main (String[]args) 
	{
		Scanner sc = new Scanner(System.in);
		//read in # of solders
		System.out.print( "Enter the Number of Soldiers:");
		int numSoldiers= sc.nextInt();
		//read in N the elimination number
		System.out.print("Enter the Elimination Number N:");
		int elimNum= sc.nextInt();
		//read in the starting soldier
		System.out.print("Enter the Starting Soldier's Capital Letter ID:" );
		String iD = sc.next();
		//assume input is only one character long
		char ch = iD.charAt(0);
		CircularList theList = new CircularList();
	 
		//fill list
		for (int i = 0; i < numSoldiers; i++)
		{
		 ch = (char)((int)ch + i);
		 Character charObj = new Character ( ch );
		 theList.insert(charObj);
		System.out.println(" the " + i + " object inserted" +theList.toString());
		}	
	
	}

}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1