Elemente von Feld und Liste auf Gleichheit überprüfen

[Greenhorn]

Hallo zusammen,

ich befinde mich gerade bei der Klausurenvorbereitung für ALDA in java und habe noch meine Probleme mit Listen. Siehe die Aufgabe unten:

Gegeben sei die Klasse IntList fur eine verkettete Liste von Integer-Zahlen.

public class Node {
public int value;
public Node next;
public Node(int v) {
value = v;
next = null;
}
}
public class IntList {
private Node head;
private Node tail;
public IntList() {
head = null;
tail = head;
}
}

Entwickeln Sie eine Java-Methode

boolean compArList(int[] a, IntList b)

die uberpruft, ob das Array a und die Liste b den gleichen Inhalt haben
(Ruckgabewert true). Beachten Sie, dass die verkettete Liste auch leer sein
kann.


Mir fehlt hier ein grundsätzlicher Ansatz, da ich durch eine Liste ja nur durch Travestieren komme und das array nur über eine Schleife (z.B. for-Schleife) durchlaufen kann. Daher weiß ich nicht, wie ich überprüfen kann, dass a == b.value ist?

public void traverseList(){						//Liste durchlaufen
  for(Node t = head; t!= null; t= t.next){
    visit(t.value);
}

Wäre nett wenn mir jemand auf die Sprünge helfen könnte! Danke!

 

[eRaaaa]

Du iterierst einfach ganz normal über das Array (for-each z.B.) und prüfst ob das int im Array != node.value ist. Am Anfang der Methode schreibst eeben einfach so etwas wie Node aktuellerKnoten = b.head;
Nach jedem Schleifendurchgang setzt du aktuellerKnoten auf den nächsten Knoten aktuellerKNoten = aktuellerKnoten.next; (oder getNext() oder wie auch immer du Zugriff darauf hast)

Grob so

		Node node = b.head;
		for (int i : a) {
			if(i != node.value){
				return false;
			}
			node = node.next; 
		}
		return true;

 

[Michael...]

Ist das der komplette Code der Klassen Node und IntList? Zumindest IntList müsste noch mindestends eine Methode a la

public Node getHead() {return head;}

besitzen, das die Variable head private deklariert ist und man ja irgendwie an den Anfang der Liste kommen muss.

Wenn man den Anfang hat kann man sich ja mit

aktuellerNode.next

durchhangeln. Und damit könnte man das ganze in einer for-Schleife a la

for (int i=0; i<a.length; i++)

durchlaufen.

 

[Pippl]

Anfänglich wäre auch eine Überprüfung möglich um zu schauen ob beide Listen die gleiche Länge haben. Und danach wie meine beiden Vorposter schon gesagt haben eine einfache for Schleife

 

[Greenhorn]

Danke Basti!

Kann ich das array & die Liste auch folgendermaßen durchlaufen?

for(int i=0; i<a.length; i++){
  for(Node b=head; b!=null; b=t.next){
     if(a[i] == b.value){
      return true;
    }
  return false;
  }
}

 

[eRaaaa]

Anfänglich wäre auch eine Überprüfung möglich um zu schauen ob beide Listen die gleiche Länge haben. Und danach wie meine beiden Vorposter schon gesagt haben eine einfache for Schleife

Klar, wenn man irgendwo die Länge der Liste speichern würde dann ja 🙂
Aber hier könnte man auch einfach Nodes erstellen, die miteinander verbinden und in der Liste nur das head setzen! Die Liste wüsste also von der Größe gar nichts! (normal würde man das wohl anders machen, das stimmt wohl)

@Greenhorn:

Nein so nicht, überlege doch mal wie die Schleifen durchlaufen werden würden!

 

[Michael...]

Danke Basti!

Kann ich das array & die Liste auch folgendermaßen durchlaufen?

for(int i=0; i<a.length; i++){
  for(Node b=head; b!=null; b=t.next){
     if(a[i] == b.value){
      return true;
    }
  return false;
  }
}

Grundsätzlich ja. Wenn nicht sichergestellt ist, dass in beiden Listen die Elemente in der selben Reihenfolge vorkommen (und Array und Liste, dann trotzdem als "gleich" angesehen werden) musst Du sie mit eine doppelten for Schleife durch laufen. Das return true ist hier aber nicht richtig.

 

[Greenhorn]

Also funktioniert die dopellte Schleife doch????:L

 for(int i=0; i<a.length; i++){
  for(Node b=head; b!=null; b=t.next){

Komisch siehts ja aus, wäre aber meine spotane Idee in der Klausur gewesen.

for(int i=0; i<a.length; i++){
  for(Node b=head; b!=null; b=t.next){
     if(a[i] != b.value){
        return false;
    }
  return true;
  }
}

 

[Michael...]

Also funktioniert die dopellte Schleife doch????:L

 for(int i=0; i<a.length; i++){
  for(Node b=head; b!=null; b=t.next){

Sollte funktionieren, wobei ich eher eine while als innere Schleife genommen hätte.
Du würdest halt hiermit jeden Wert aus dem Array gegen jeden Wert aus der Liste prüfen.

Das würde aber auch nicht zum gewünschten Ergebnis führen und grundsätzlich false zurückliefern -ausser alle Nodes in der Liste sind identisch bzw. haben alle den selben Wert.

Komisch siehts ja aus, wäre aber meine spotane Idee in der Klausur gewesen.

for(int i=0; i<a.length; i++){
  for(Node b=head; b!=null; b=t.next){
     if(a[i] != b.value){
        return false;
    }
  return true;
  }
}

 

[Greenhorn]

@Michel: Muss ich nicht jeden Wert aus dem Array mit Wert aus der Liste verlgeichen?

Also bräuchte ich erst eine boolsche Variable z.B.

boolean gleichheit = true;

die Wert

true

annimmt, wenn

a[i] == b.value

, andernfalls

false

.

eRaaaa´s Lösung ist wohl komfortabler?!

 

[Michael...]

@Michel: Muss ich nicht jeden Wert aus dem Array mit Wert aus der Liste verlgeichen?

Denke schon, kenne aber die genauen Vorgaben nicht.

Also bräuchte ich erst eine boolsche Variable

Denke ja, man müsste mit einem flag arbeiten.

eRaaaa´s Lösung ist wohl komfortabler?!

Die Lösung setzt voraus, dass die Wert in Array und Liste in gleicher Reihenfolge vorkommen.

Komplizierter wird das ganze wenn die Werte in unterschiedlicher Reihenfolge und auch noch mehrfach vorkommen können - deshalb wären die genauen Randbedingungen recht interessant.

 

[Greenhorn]

Weitere Randbedingungen gibt es in der Afg-Stellung nicht. Alles was es zu der Afg gibt, habe ich oben hineinkopiert.

..einen flag kenne ich gar nicht, zumindest haben wir so etwas unter den Namen noch nicht behandelt.

 

[Greenhorn]

Okay ich starte nochmal einen Neuversuch mit der Lösung:

boolean compArList (int [] a, IntList b){
  boolean ende = false;
  int i = 0;
  Node node = b.head;
  if(a.length != 0 && b.head !=null){
    while(!ende){
       if(a[i] == b.value){
         ende = true;
       }else{
         ende = false;
       }
       a++;
       b=b.next;
   }else{
     ende = false;
   }

   return ende;

}

???:L

 

[Michael...]

Lass doch den Code mal laufen oder spiele in mal mit Stift und Papier durch.

Wie würdest Du vorgehen, wenn man Dir zwei Eimer vorsetzt und Du überprüfen sollst, ob in beiden das gleiche drin ist?