Implementierung Listen-ADT

Diskutiere Implementierung Listen-ADT im Java Basics - Anfänger-Themen Bereich.
J

jono

Hallo,
ich habe folgendes Problem:
Java:
Implementieren Sie einen Listen-ADT anhand der Spezifikation "SortedList.asl".
Die Elemente in der Liste sollen stets aufsteigend sortiert sein.

Beachten Sie folgende Punkte:
- Das Nat in der Spezifikation muss als int in Java übersetzt werden.
- Alle Variablen und Methoden müssen public sein.
- In Node müssen die Variablen value und next heißen.
- In SortedList muss die Variable first heißen.
- Die Methodennamen müssen identisch mit den functions aus der Spezifikation sein.
- Das Verhalten innerhalb der Methoden muss dem Verhalten der equations aus der Spezifikation entsprechen.
- Sie dürfen keine imports oder sonstige vorgefertigte Typen wie z.B. Arrays verwenden. 
Bitte benutzen Sie folgendes Schema für die Dateinamen Ihrer Lösung: SortedList.java, Node.java.
Hier die Spezifikation:
Java:
specification SortedList
imports
  bool
  nat
sorts
  SortedList
constructors
  nil : -> SortedList  // Empty list
hidden constructors
  cons' : Nat x SortedList -> SortedList // Head element and tail list
functions
  cons : Nat x SortedList -> SortedList //add element to SortedList
  head : SortedList -> Nat? // Head element
  tail : SortedList -> SortedList? // SortedList without head
  isNil : SortedList -> Bool // Test for nil SortedList
  length : SortedList -> Nat // Number of elements in the SortedList
  append : SortedList x SortedList -> SortedList // Append two SortedLists
  last : SortedList -> Nat? // Last element
  init : SortedList -> SortedList? // SortedList without last
variables
  n : Nat
  n1 : Nat
  l : SortedList
  l1 : SortedList
equations
  cons(n, nil) = cons'(n, nil)
  cons(n, cons'(n1, l)) = if(greater(n,n1)) then cons'(n1, cons(n, l)) else cons'(n, cons'(n1, l))
  head(cons'(n, l)) = n
  tail(cons'(n, l)) = l
  isNil(nil) = true
  isNil(cons'(n, l)) = false
  length(nil) = zero
  length(cons'(n, l)) = succ(length(l))
  append(l,nil) = l
  append(l, cons'(n, l1)) = append(cons(n,l),l1)
  last(cons'(n,l)) = if isNil(l) then n else last(l)
  init(cons'(n,l)) = if isNil(l) then nil else cons'(n, init(l))
Dazu habe ich bisher folgenden Quellcode:
Java:
public class SortedList {
	private Node first;
	private int n;
	private int n1;
	private SortedList l;
	private SortedList l1;

	public void cons() {
		if (l == null) {

		}
	}

	public int head() {
		return first.value;
	}

	public void tail() {
		first = first.next;
	}

	public boolean isNil() {
		if (first == null) {
			return true;
		}
		return false;
	}

	public int length() {
		
	}

	public void append() {

	}

	public int last() {
		if (l == null) {

		}

	}

	public void init() {

	}

}
Erstmal meine Frage, wie gehe ich das jetzt bei "cons" an, mit imports soll es ja nicht umgesetzt werden.
 
J

jono

Klasse Node:
Java:
public class Node {
	public int value;
	public Node next;
}
 
J

jono

Bei den anderen Methoden fällt es mir auch schwer. Bei "append" z.B. kann ich doch nicht einfach l+l1 schreiben.
Bei "length" gibt es ja auch keine spezielle Funktion die einem direkt die Länge einer Liste ausgibt. Kann mir jemand ein
Tipp geben wie ich das am besten angehe, da ich wirklich kein Plan habe, wie ich das machen soll. Stift und Zettel hilft mir
da auch nur bedingt weiter.
 
H

httpdigest

Ich denke nicht, dass die Variablen `n`, `n1`, `l` und `l1` als Instanzvariablen in `SortedList` implementiert werden sollen. Es sind Variablen, die in der Spezifikation benutzt werden, um den Zusammenhang von mehreren Dingen zu beschreiben.
Es sind aber sicherlich keine Instanzvariablen im Sinne der Java Klasse `SortedList`.
Die Variablen `n` und `n1` beschreiben den Wert eines Knotens (also quasi `Node.value`), denn ein `Node` selber wird in der Spezifikation nicht gebraucht.
 
J

jono

Ja, da war ich mir zunächst auch unsicher, dient ja eher der Semantik.
 
J

jono

@httpdigest Kannst du mir evtl. einen Tipp geben wie ich denn ein Element einer Liste hinzufügen kann?
Denn mit LinkedList ist es verboten, und ich weiß nicht wie ich eine Liste darstellen soll.
 
J

jono

Kannst du mir einen tipp geben wie ich eine das letzte element einer liste ausgebe ohne eine Arraylist zu benutzen ?
 
J

jono

Ja, den Tipp verstehe der ist auch schon sehr GUT. Frage mich nur durch welchen Code ich die Liste darstellen kann. First. Next oder was? Ich glaube nicht.
 
mihe7

mihe7

First. Next oder was? Ich glaube nicht.
1. In einer verketteten Liste kann jeder Knoten als Kopf einer verketteten Liste gesehen werden.
2. Um eine verkettete Liste anzugeben, reicht die Angabe des Kopfes.

Bei (k,n) ist k nichts anderes als das Kopfelement, n das diesem folgende Element (next).
 
J

jono

Okay, danke.
Java:
	public int last(int value) {
		Node n = new Node();
		n.value = value;
		if(first.next == null) {
			n = this.first;
		} else {
			last(first.next);
	}
Wie kann ich denn jetzt das letzte Element herausfiltern ..?
 
J

jono

Java:
last(first.next);
last wird hier rot unterstrichen logischerweise
 
mihe7

mihe7

In Node:

Java:
public int last() {
    if (next == null) {
        return value;
    } else {
        return next.last();
    }
}
 
J

jono

Gehört der Code in die Klasse Node? Dachte es gehört in die Klasse Sorted.List, da es so in den Programmierfolien der Fall war..
 
J

jono

Also nicht am Beispiel last, aber war dann dementsprechend eher naheliegend es in die Klasse Sorted.List zu implementieren.
 
mihe7

mihe7

Gehört der Code in die Klasse Node? Dachte es gehört in die Klasse Sorted.List, da es so in den Programmierfolien der Fall war..
Der Code würde in die Klasse Node gehören und dient dazu, Dir die grundsätzliche Idee zu zeigen. Du wirst es vermutlich in SortedList implementieren müssen. Das geht natürlich nicht 1:1, da musst Du Dir zusätzlich was überlegen (s. im ADT die "hidden constructors").
 
J

jono

Wenn ich jetzt daran denke, dass ich erst dachte die equations einfach in Code umzusetzen, und jetzt daran einen hidden constructor zu implementieren, weiß ich beim hidden constructor zwar welche Aufgabe er erfüllt, aber nicht wie ich diesen einbauen kann , denn
Java:
-versteckte Konstruktoren lassen nur das Einfügen weiterer Elemente in eine Menge zu, falls diese Elemente noch nicht in der Menge enthalten sind
-Aufruf von versteckten Konstruktoren nur indirekt durch öffentliche Funktionen gleichen Namens möglich
Problem: Wie kann ich mir das vorstellen, wenn es darum geht das letzte Element zu returnen. Da kann ich keinen Zusammenhang sehen im Sinne von Zulassen von Einfügen weiterer Elemente in eine Menge, falls diese noch nicht in der Menge enthalten sind, damit hat das last-Element doch nichts zu tun, weil es nicht um Einfügen geht?
Das habe ich aus der Vorlesungsfolie, klingt ziemlich abstrakt.
 
mihe7

mihe7

Naja, wenn Du last() als rekursive Methode in SortedList einbaust, brauchst Du ja die "nächste" SortedList und nicht den nächsten Node.
 
Thema: 

Implementierung Listen-ADT

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben