Java - Verkettete Liste - Komm nich weiter

[Peter-Griffin]

Hi,
ich bin am lernen für meine Algorithmen und Datenstrukturen Klausur und bin grad an einer Aufgabe zu verkettete Liste, an der ich mir die Zähne ausbeiße

Es geht um folgendes:
In einer früheren Aufgabe habe ich Objekte vom Typ Student angelegt. Diese haben jeweils die Attribute Name, Vorname, Telefonnummer und Matrikelnummer. Diese Attribute habe ich über get und set Methoden implementiert. Ich habe 5 Studenten angelegt und diese in einem Array gespeichert. Das funktioniert alles wunderbar.
Die neue Aufgabe ist jetzt, dass ich die 5 Studenten anstatt in einem Array in einer verketteten LIste speichere.
Dazu habe ich erstmal eine Klasse Node geschrieben, die die Knoten erzeugt:
public class Node {

public Student item;
public Node next;

public Node(Student v){
item=v;
next=null;
}
}

Dazu brauch ich eine Methode, die einen neuen Knoten einfügt:
public static Node head=null;
public void putelement(Student item){

for(Node t=head;t!=null;t=t.next){

if(head==null){
head=new Node(item);
return;
}
else {
t.next=new Node(item);
return;
}
}
}

So und jetzt noch eine Methode, die mir die Daten des jeweiligen Studenten ausgibt. Ich hab hier 2 verschiedene Methoden, die erste ist meine eigene, die zweite von einem Komilitonen:

public void print1(){
for(Node i=head;i!=null;i=i.next){
System.out.println(i.item);

}
}

public void print2()
{
Node current=head;
while(current!=null)
{
System.out.println(current.item);
current=current.next;
}
}

In der Main-Methode lege ich einen neuen Studenten und einen neuen Knoten an:

public static void main(String[] args){

Student neuerStudent=new Student();
Node testNode=new Node(neuerStudent);
so jetzt kann ich mittels einer read-Methode die Studentendaten mit der Tastatur eingeben. Die ist hier nicht weiter wichtig, denke ich.

neuerStudent.read();

Jetzt füge ich mit meiner Methode putelement einen neuen Knoten hinzu, dem ich jeweils den Studenten übergebe, den ich mit der read() Methode angelegt habe.

So nun zu meinem Probelm:
Das Programm gibt mir die Daten der Studenten einfach nicht aus! Ich weiß jetzt nicht, ob es an der putelement- oder an der print-Methode liegt.

Kann mir jemand helfen?
Gruß

 

[skicu]

Ich steig bei deinem Codewirrwarr mit Funktionen, Klassen und Kommentaren dazwischen auf die Schnelle nicht ganz durch - kannst du nicht einfach mal den gesamten Code posten? Zusammenhängend und mit einem Kommentar über jeder Funktion, wozu die gedacht ist?
(Am besten zwischen [ code ] ... [ / code ] Tags?)

 

[Peter-Griffin]

Ok hier mal der gesamte Code, wenn du die Klasse Student auch noch sehen willst, poste ich die auch

package Aufgabe3;
import java.util.Scanner;
import Aufgabe1.Student;

public class Node {

public Student item; //Object, dass mit dem Knoten verknüpft ist
public Node next; //Referenz auf den nächsten Knoten
public Node end; //Letzter Knoten

//Konstruktor, dem ein Objekt vom Typ Student übergeben wird
public Node(Student v) {

item=v;
next=null;
}

public Node(){

}

public static Node head=null; //Kopf-Knoten
public void putelement(Student item){ //Methode zum einfügen von Knoten

for(Node t=head;t!=null;t=t.next){

if(head==null){ //Testet, ob die Liste leer ist
head=new Node(item);
return;
}
else{
t.next=new Node(item);
return;
}
}
}

public void print1(){
for(Node i=head;i!=null;i=i.next){
System.out.println(i.item);

}
}

public void print2(Student s)
{
Node current=head;
while(current!=null)
{
s.toString();
current=current.next;
}
}

/*public void insert(Node vorgaenger, Student s){
if(vorgaenger!=null && vorgaenger!=end){
Node newNode=new Node(s);
newNode.next=vorgaenger.next;
vorgaenger.next=newNode;
}
}*/

public static void main(String[] args){

Student neuerStudent=new Student(); //neuer Student wird angelegt
Node testNode=new Node(neuerStudent); //Neuer Knoten
System.out.println("Student Nr. 1");
neuerStudent.read(); //Einlesemethode für die Attribute
testNode.putelement(neuerStudent);
System.out.println("Student Nr. 2");
neuerStudent.read();
testNode.putelement(neuerStudent);
System.out.println("Student Nr. 3");
neuerStudent.read();
testNode.putelement(neuerStudent);
System.out.println("Student Nr. 4");
neuerStudent.read();
testNode.putelement(neuerStudent);
System.out.println("Student Nr. 5");
neuerStudent.read();
testNode.putelement(neuerStudent);
System.out.println("So und jetzt diese verdammte Ausgabe");
testNode.print1(); //Ausgabe

}

}

 

[skicu]

Erkläre bitte, was du mit jeder einzelnen Schleife und Anweisung in putelement machen wolltest. Wenn, dann liegt der Fehler dort und nicht in den print Methoden (die müssen beide gehen).

Tipp: Imho liegt es schon an der ersten Schleife in putelement.
(Müsste jetzt erst eine VM hochfahren, um das wirklich zu testen, aber ich tippe schwer auf die for Schleife. Mal sehen, ob du das auch so siehst. )

 

[Peter-Griffin]

Erkläre bitte, was du mit jeder einzelnen Schleife und Anweisung in putelement machen wolltest. Wenn, dann liegt der Fehler dort und nicht in den print Methoden (die müssen beide gehen).

Tipp: Imho liegt es schon an der ersten Schleife in putelement.
(Müsste jetzt erst eine VM hochfahren, um das wirklich zu testen, aber ich tippe schwer auf die for Schleife. Mal sehen, ob du das auch so siehst. )

meinst die for-Schleife ist falsch? Die hab ich aus dem Skript abgeschrieben.
Die erzeugt einen Kopfknoten t, die Abbruchbedingung ist das t nicht null werden darf und dann wird der Knoten t auf den nächsten Knoten verwiesen mit t.next.

Hab es jetzt mach mit einer while-Schleife probiert, der gibt mr aber immernoch nix aus.
ich hab mir das so gedacht:

public void putelement (Node item)
if (head==null) //Test, ob die Liste leer ist und setze item als ersten Knoten
{
head=item;
}
else
{
Node current=head; //Hilfsvariable, die als Kopfknoten dient
while(head!=null) //Gibt es schon ein erstes Element, dann gehe alle Elemente durch und finde das letzte (current.next==null)
{
current=current.next;
}
current.next=item;
}
}
}

 

[skicu]

Ok. Bei deiner ersten putelements Methode wäre es unmöglich gewesen, in die for Schleife zu kommen, da du anfangs ein null Objekt zuweist, und dann als Bedingung t!=null angibst -> die Schleife wird nie durchlaufen.

Bei deiner neuen Methode seh ich auf den ersten Blick kein Problem, bis auf die fehlerhafte Klammersetzung. Hab aber gerade kein Eclipse zum Ausprobieren da.. So siehts mit richtigen Klammern aus:

public void putelement (Node item){
	if (head==null) //Test, ob die Liste leer ist und setze item als ersten Knoten
	{
		head=item;
	}
	else
	{
		Node current=head; //Hilfsvariable, die als Kopfknoten dient
		while(head!=null) //Gibt es schon ein erstes Element...
		{
			current=current.next;
		}
		current.next=item;
	}
}

Ach ja: Bei deiner print1 Methode würde der letzte Node nicht ausgegeben.

edit: So ganz steig ich bei deiner Klasse aber nicht durch. Was ist "end" und warum speicherst du einen "head" (Kopf?) (in einer verketteten Liste speichert ein Element ja nur das nächste Element, klassischerweise in der Variable "next" - sonst nichts. )

Ich hol mal kurz mein Notebook und schreib ne verkettete Liste, wie ich die bauen würde..

 

[skicu]

public class testkette
{
	static Node firstNode;
	static Node curNode;
	public static void main(String[] args)
	{
		Student newStud = new Student("Student1");
		curNode = new Node(newStud);
		firstNode = curNode;
		curNode = gotoEnd(curNode);
		newStud = new Student("Student2");
		curNode = curNode.newNodeAfter(newStud);
		curNode = gotoEnd(curNode);
		newStud = new Student("Student3");
		curNode = curNode.newNodeAfter(newStud);
		curNode = gotoEnd(curNode);
		newStud = new Student("Student4");
		curNode = curNode.newNodeAfter(newStud);
		curNode = gotoEnd(curNode);
		newStud = new Student("Student5");
		curNode = curNode.newNodeAfter(newStud);
		printChain(firstNode);
	}
	
	private static Node gotoEnd(Node node)
	{
		while(node.next != null)
		{
			node = node.next;
		}
		return node;
	}
	
	private static void printChain(Node node)
	{
		do
		{
			System.out.println(node.getStudName());
			if(node.next != null)
				node = node.next;
		}
		while(node.next != null);
		System.out.println(node.getStudName());
		return;
	}
}

class Node
{
	Student thisStud;
	public Node next;
	public Node(Student newStud)
	{
		thisStud = newStud;
	}
	
	public Node newNodeAfter(Student newStud)
	{
		next = new Node(newStud);
		return next;
	}
	
	public String getStudName()
	{
		return thisStud.Name;
	}
}

class Student
{
	public String Name;
	
	public Student(String newName)
	{
		Name = newName;
	}
}

edit: Zu beachten:
Node könnte man theoretisch von Student erben lassen. War ich jetz zu faul für. *g*
Und: Die Kettenverwaltung findet außerhalb statt (in meinem Fall in "testkette").

 

[Peter-Griffin]

Cool, vielen Dank!
Das bringt mich schon sehr viel weiter. Jetzt muss ich nur noch das so hinbekommen, dass er mir nicht nur den Namen des Studenten ausgibt, sonderen auch noch Vorname, Telefonnummer und Matrikelnummer.
Wenn ich Probleme hab, dann post ich das hier nochmal

 

[skicu]

Was studierst du denn?

 

[Peter-Griffin]

Was studierst du denn?

Ich studiere Wirtschaftsinformatik und muss das für Algorithmen und Datenstrukturen können.
Jetzt muss ich noch Rekursion, Binärbäume und Graphen lernen

 

[skicu]

Was studierst du denn?

Ich studiere Wirtschaftsinformatik und muss das für Algorithmen und Datenstrukturen können.
Jetzt muss ich noch Rekursion, Binärbäume und Graphen lernen

Hui, damit darf ich im Oktober höchstwahrscheinlich auch anfangen.

 

[Peter-Griffin]

Willst du auch Wirtschaftsinformatik studieren? Oder meinst du jetzt das Java-Programmieren? Wenn du das jetzt schon so gut kannst, dann haste im Studium erstmal keine Probleme

 

[skicu]

Willst du auch Wirtschaftsinformatik studieren? Oder meinst du jetzt das Java-Programmieren? Wenn du das jetzt schon so gut kannst, dann haste im Studium erstmal keine Probleme

Wirtschaftsinformatik fang ich im Oktober an.
Habe jetzt vorher eine Ausbildung als Fachinformatiker Anwendungsentwicklung gemacht, daher kann ich zwar programmieren, werde aber im August / September nochmal massiv Mathe und ähnliches aus der Schule wiederholen müssen, hab das jetzt drei Jahre lang nicht mehr gemacht.

 

[Peter-Griffin]

Mathe ist in Wirtschaftsinformatik nicht wirklich schwer. Da kommen erstmal so Sachen wie Kurvendiskusion, lineare Algebra, Folgen und Reihen, Grenzwertberechnung, Integrieren, Mengenlehre, Relationen usw. dran.
Das wirklich schwere war bei uns Digitaltechnik
Wo willst du studieren?

 

[skicu]

Mathe ist in Wirtschaftsinformatik nicht wirklich schwer. Da kommen erstmal so Sachen wie Kurvendiskusion, lineare Algebra, Folgen und Reihen, Grenzwertberechnung, Integrieren, Mengenlehre, Relationen usw. dran.
Das wirklich schwere war bei uns Digitaltechnik
Wo willst du studieren?

Ja, das scheint dann im Grunde das zu sein, was ich auch in der Schule gemacht habe... ist nur schon lange her.
Studieren will ich an der FH Hof.
Naja, mal sehen wie das wird...

 

[Peter-Griffin]

Hört sich ja nicht schlecht an!
Ich hab hier nochmal ein kleines Problem zur verketteten Liste:
Das Programm nennt sich Josephus Problem. Es ist eine zirkuläre Liste, in der eine Bestimmte Anzahl von Personen (=Knoten) m von der Tastatur eingegeben wird. Dann gibt man noch eine Zahl n an, n besagt, die wievielte Person (Knoten) pro durchgang aus der Liste rausgeschmissen wird, bis nur noch eine Person übrig ist.
Das hab ich hinbekommen, aber jetzt muss ich noch eine Methode schreiben, die die Anzahl der Knoten berechnet. Dazu ist eine Referenz auf einen Knoten gegeben (ich denk mal das ist ein next-Verweis)
Hier mal der Quellcode:

package Liste;
import java.util.Scanner;
public class Josephus
{
static class Node //Konstruktor
{
int val;
Node next;

Node (int v)
{
val=v;
}
}
public int knotenanzahl(Node a) //Methode, die die Anzahl der Knoten berechnen soll
{

int i=0;
for(Node b=a.next;b!=null;b=b.next)
{


b.next=a.next;

if(b.next==a) //wenn die Referenz vom letzten Knoten auf den ersten Knoten verweist, ist die Liste durchlaufen
{
return i;
}
else if(a.next==null)
{
return 1;
}
i++;
}
}

public static void main(String[] args)
{
Scanner Eingabe=new Scanner(System.in);
System.out.println("Geben Sie die Anzahl der Personen ein:");
int n=Eingabe.nextInt();
System.out.println("Geben Sie bitte ein, welche n-te Person pro Durchlauf rausgeschmissen werden soll:");
int m=Eingabe.nextInt();
Node t=new Node(1);
Node x=t;
for (int i=2;i<=n;i++)
{
x.next=new Node(i);
x=x.next;
}
x.next=t;
while(x!=x.next)
{
for(int i=1;i<m;i++)
{
x=x.next;
}
x.next=x.next.next;
}
System.out.println("Anführer ist " + x.val);
}

}

 

[skicu]

Habe gerade nichts zum Testen da; habe in deiner Methode auf den ersten Blick keinen Fehler gesehen. So würde ich's machen:

	public int knotenanzahl(Node a)
	{
		int i = 0;
		Node reference = a;
		do
		{
			i++;
			a = a.next;
		}
		while(reference != a);
		return i;
	}

 

[Peter-Griffin]

Sauber, dankeschön!
Dass es so einfach ist, hätte ich jetzt euch nicht gedacht.