Verständnisproblem_Verkettete Liste_JosephunsProblem

[valentina2013]

Hallo,

ich möchte eine Methode void addNode() implementieren, die einen neuen Knoten an das ende der Liste (eine zyklische verkettete Liste) hinzufügt.Der Wert des neuen Knotens muss ich durch Inkrementieren der Variable int capacity, welche gleichzeitig die Knotenanzahl representiert. und eine andere void Josephus(int k) die sukzessiv den k-ten Knoten im Kresi entfernt bis der Kreis leer ist

class Node {
	    
		private Node next;
		private int value;
		
		Node () {}
		
		Node (Node next, int value) {
			this.next  = next;
			this.value = value;		
		}
		
		
		public Node getNext() {
			return next;
		}
		
		public int getValue() {
			return value;
		}
		
		public void setNext(Node next) {
			this.next = next;
		}
		
		public void setValue(int value) {
			this.value = value;
		}
	}

dann noch die klasse mit den zu implementierenden Methoden

class CircularList {
	
	private Node head, tail;
	private int capacity;
	
	CircularList() {
		capacity = 0;
	}
	
	public boolean isEmpty() {
		return capacity == 0;
	}

			
			public void addNode() {
			    
			    // meine code
			Node head = new Node(tail, capacity++);    
					Node teil = new Node(head, capacity++);
					do{
						capacity++;
						Node newTile=new Node(head,capacity);//Erzeugt einen neuen Knoten für das Ende
						teil.setNext(newTile);//Erzeugt eine Referenz auf den neuen Knoten
						
					}while(capacity!=41);
			    }
				
				public void Josephus (int k) {
					
					Node iterator = head;
					Node predecessor = tail;
					
			        // meine code
				}
		
		 @Override
			public String toString() {

				String representation = "< circular list: ";
				
				Node iterator = head;
				
				for (int i = 0; i < capacity; i++) {
					representation += iterator.getValue()+" ";
					iterator = iterator.getNext();
				}
				
				return capacity == 0 ? "< empty circular list>" : representation+">"; 
			}	
			
		}

und letztendlich die klasse mit main

public class Josephus {

	public static void main(String args[]) {
		
		CircularList cl = new CircularList();
	
		for (int i = 0; i < 41; i++)
			cl.addNode();
		
		System.out.println(cl);
		
		cl.Josephus(3);
	}
}

Mein Problem: in main wird add 40 mal aufgerufen, wie kann ich add so implementieren dass beim jeden aufruf nur ein Knote angefügt wird?

Danke sehr

 

[eMmiE]

Ersetze das do-while (eine Schleife, die das solange immer wieder ausführt [DO] bis die Bedingung nicht mehr erfüllt ist [while]) durch ein if

if (capacity < 40) {
addNode();
}

Gruß eMmiE

 

[valentina2013]

ok,habe gemacht jetzt meckert er :
Exception in thread "main" java.lang.NullPointerException
CircularList.toString(CircularList.java:52)
at java.lang.String.valueOf(String.java:2854)
at java.io.PrintStream.println(PrintStream.java:821)
at Josephus.main(Josephus.java:14)

 

[Gucky]

Dann wird in CircularList irgendwas null sein, du versuchst aber trotzdem darauf zuzugreifen. Das passiert in Zeile 52 der Klasse CircularList.

Vermutlich ist

head

oder iterator.getNext() null.

Befüll die Liste mal und lass dir dann mit dem Debugger anzeigen, was überhaupt in der Liste gelandet ist.
Wie oft wird die for-Schleife durchlaufen?


BTW: Ich würde am Anfang von toString() auf eine leere Liste prüfen und ggf. "< empty circular list>" zurückgeben und erst danach in die for-Schleife gehen.
BTW2: Nur als Tipp. Ich weiß nicht, wie oft du ihn verwendest: Der Gebrauch des

?:

Operators ist mit äußerster Vorsicht zu genießen, da er den Code schnell unleserlich machen kann.

 

[valentina2013]

ja hattest absolut recht, jetzt bin ich soweit dass kein nullPointerException ausgegeben wird, dafür wird aber in addNode keine Knoten hinzugefügt sondern nur die values erhöht.eigentlich möchte ich dass am ende meine liste aus zyklisch verbundenne 41 knoten besteht.falls ihr mir helfen könnt wäre ich sehr dankbar

public void addNode() {

		head=new Node();//sonst nullPointerException
		tail=new Node();
		head.setNext(tail);
		head.setValue(capacity++);
		System.out.println(capacity+"******");
		tail.setNext(head);
		tail.setValue(capacity+1);
		
		Node newTail = new Node(head, capacity+1);// Erzeugt einen neuen Knoten
													// für das Ende
		tail.setNext(newTail);// Erzeugt eine Referenz auf den neuen Knoten
}

 

[knilch]

Hi,
Du hast in der addNode- Methode einen Denkfehler:

public void addNode() {
 
        head=new Node();//sonst nullPointerException
        tail=new Node();
        head.setNext(tail);
        head.setValue(capacity++);
        System.out.println(capacity+"******");
        tail.setNext(head);
        tail.setValue(capacity+1);
        
        Node newTail = new Node(head, capacity+1);// Erzeugt einen neuen Knoten
                                                    // für das Ende
        tail.setNext(newTail);// Erzeugt eine Referenz auf den neuen Knoten
}

Jedes mal wenn du einen node addest, dann erstellt du eine neue Instanz vom head und tail dies kann so nicht gehen.
Sie hier mal wie eine append- Methode von einer singleLinkedList aussehen könnte:
Diese nimmt die head- Instanz, die beim Initialisieren erstellt wurde. Dann wird innerhalb der append- Methode die head- Instanz updated:

private Node head;
private int nodeCounter;

/**
 * constructor to set the head element of list
 */
public CircularList() {
	head = new Node(0);
	head.setNext(null);
	nodeCounter = 0;
}
...
/**
 * Method to insert node at end of list
 * @param node
 */
public void append(Node node) {		
	Node lastNode = head;
	while (lastNode.getNext() != null) {
		lastNode = lastNode.getNext();		
	}
	lastNode.setNext(node);
	nodeCounter++;
}

Du musst dies nun so ändern, damit die append- Methode für die zirkuläre Liste funktioniert, also die tail- instanz muss auch noch geändert werden, (aber keine neue Instanz von tail erzeugen..) wenn der add gemacht wird.

 

[valentina2013]

danke für deine Antwort, ich komme immer noch nicht auf die richtige implementierung
wenn ich so was mache:

head.setNext(tail);
tail.setNext(head);

gibt wieder nullPointerException aus.

 

[knilch]

gibt wieder nullPointerException aus.

Kannst du mal posten, wo genau die NPE geworfen wird? (Code der Klasse posten und die Zeile in der NPE geworfen wird.)

 

[valentina2013]

ja klar:
hier die exception:Exception in thread "main" java.lang.NullPointerException
at verkListe.CircularList.addNode(CircularList.java:20)
at verkListe.Josephus.main(Josephus.java:10)

class CircularList {
	
	private Node head, tail;
	private int capacity;
	
	CircularList() {
		capacity = 0;
	}
	
	public boolean isEmpty() {
		return capacity == 0;
	}

			
			public void addNode() {
			    
			    // meine code
				
				head.setNext(tail);//hier diese zeile wirft exception aus
				tail.setNext(head);
				
				
					
			    }
public void Josephus (int k) {
					
					Node iterator = head;
					Node predecessor = tail;
					
			        // meine code
				}
		
		 @Override
			public String toString() {

				String representation = "< circular list: ";
				
				Node iterator = head;
				
				for (int i = 0; i < capacity; i++) {
					representation += iterator.getValue()+" ";//und hier
					iterator = iterator.getNext();
				}
				
				return capacity == 0 ? "< empty circular list>" : representation+">"; 
			}	
			
		}

und hier main:

public class Josephus {

	public static void main(String args[]) {
		
		CircularList cl = new CircularList();
	
		for (int i = 0; i < 41; i++)
			cl.addNode();//und diese zeile wirft auch exception aus :(
		
		System.out.println(cl);
		
		cl.Josephus(3);
	}
}

 

[knilch]

Hi,
Ich denke die NPE kommt daher, weil tail und/oder head nicht initialisiert werden? Jedenfalls sehe ich es in deinem letzten post nicht.
Ich hab deine Klassen mal ein wenig geändert:
Node.java:

public class Node {
    private Node next;
    private int value;
   
    public Node (int value) {
    	this.value = value;
    }
   
    public Node getNext() {
        return next;
    }
   
    public int getValue() {
        return value;
    }
   
    public void setNext(Node next) {
        this.next = next;
    }
   
    public void setValue(int value) {
        this.value = value;
    }
}

CircularList.java:

package test2;

class CircularList {

	private Node head, tail;
	private int nodeCounter;

	public CircularList() {
	    head = new Node(0);
	    head.setNext(null);
	    nodeCounter = 0;
	    
	    tail = new Node(0);
	    tail.setNext(null);    
	}

	public boolean isEmpty() {
		return nodeCounter == 0;
	}

	public int size() {
		return nodeCounter;
	}

	 public void addNode() {       
         head.setNext(tail);//hier diese zeile wirft exception aus
         tail.setNext(head);
         }
	
	/**
	 * Method to insert node at end of list
	 * @param node
	 */
	public void append(Node node) {    
	    Node lastNode = head;
	    while (lastNode.getNext() != null) {
	        lastNode = lastNode.getNext();     
	    }
	    lastNode.setNext(node);
	    nodeCounter++;
	}

	public void Josephus (int k) {

		Node iterator = head;
		Node predecessor = tail;

		// meine code
	}

	@Override
	public String toString() {
		String representation = "< circular list: ";

		Node iterator = head;

		for (int i = 0; i < nodeCounter; i++) {
			representation += iterator.getValue()+" ";
			iterator = iterator.getNext();
		}
		return isEmpty() ? "< empty circular list>" : representation+">";
	}  
}

und Test.java

public class Test {
    public static void main(String args[]) {    
        CircularList cl = new CircularList();
        for (int i = 0; i < 41; i++) {
            cl.append(new Node(i));
        }
        System.out.println(cl);
       
        cl.Josephus(3);
    }
}

Nimm diese mal als Basis und ändere sie so, damit sie die Aufgabe lösen.

ps. die Methode addNode von dir hab ich mal als Beispiel durch append ersetzt. aber diese musst du noch anpassen damit die referenz von tail auch angepasst wird.

 

[valentina2013]

sehr lieb von dir-danke für deine mühe-aber,ich kann der restcode leider nicht ändern,muss nur die beide methoden implementieren,

 

[knilch]

...ich kann der restcode leider nicht ändern, muss nur die beide methoden implementieren,

also nur die Methoden: public void addNode(){} und public void Josephus (int k){}.
Für addNode:

public void addNode() {    
   if(head == null) {
      head = new Node();
      head.setNext(null);
      head.setValue(0);
   }
   if(tail == null) {
      tail = new Node();
      tail.setValue(0);
   }
   tail.setNext(head);
   Node node = new Node();     
   Node lastNode = head;
   while (lastNode.getNext() != null) {
      lastNode = lastNode.getNext();   
      ...// hier musst du noch die tail- Instanz updaten 
   }
   node.setValue(capacity);
   node.setNext(tail);
   lastNode.setNext(node);
   nodeCounter++;
}

 

[valentina2013]

bekomme immer noch nicht hin sehr frustrierend

 

[valentina2013]

aktueller standder imemer noch nicht richtig ist):

public void addNode() {

		// die code ist leider nicht richtig, denn ich verändere nur
		// die node.values,head und tail bleiben unverändert, war aber so
		// vorgesehen dass head.getValue()==1 sein musste und
		// tail.getValue()==41.
		// ich denke daher funktioniert die untere Methode auch nichtif (head == null) {// sonst nullPointerException da der Zeiger auf
							// "nichts" zeigt
			head = new Node();
			head.setNext(null);
			head.setValue(1);
		}
		if (tail == null) {
			tail = new Node();
			tail.setValue(1);
		}
		tail.setNext(head);
		Node node = new Node();
		Node lastNode = head;
		while (lastNode.getNext() != null) {// wird geprüft ob es zum aktuellen
											// lastNode einen nachfolger gibt
			lastNode = lastNode.getNext(); // wenn ja soll der aktuelle lastNode
											// auf seinen Nachfolger zeigen
			tail.setNext(lastNode);
		}
		lastNode.setNext(node);// wenn nein wird der Nachfolger des aktuellen
								// lastNodes auf den neuen Knoten
		// gesetzt,sprich die liste wird um einen Knoten erweitert
		node.setValue(capacity + 2);

		capacity++;
	}

	public void Josephus(int k) {

		Node iterator = head;
		Node predecessor = tail;

		while (capacity != 0) {
			for (int i = 0; i < k - 1; i++) {
				iterator = iterator.getNext();
				predecessor = predecessor.getNext();
			}
			predecessor.setNext((iterator.getNext()));
			iterator = iterator.getNext();
			capacity--;
		}

 

[Gucky]

Die while-Schleife mit der du versuchst vom letzten Knoten zum letzten zu iterieren kannst du dir sparen. In head hat der letzte Knoten zu stehen.

Wenn ich das richtig sehe, addest du in der addNode Methode 3 Knoten. tail wird ein Neuer, wenn head null ist, kommt da noch einer rein und dann wird noch einer hinten dran gehängt. Du müsstest die drei nur zu bestimmten Bedingungen adden und zwar so, dass immer nur einer geaddet wird. Z. B. mit einem else if Block.