Implementierung Listen-ADT

jono

Top Contributor
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.
 

jono

Top Contributor
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.
 

httpdigest

Top Contributor
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.
 

jono

Top Contributor
@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.
 

jono

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

jono

Top Contributor
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.
 

jono

Top Contributor
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 ..?
 

mihe7

Top Contributor
In Node:

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

jono

Top Contributor
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..
 

jono

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

mihe7

Top Contributor
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").
 

jono

Top Contributor
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

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

jono

Top Contributor
Man könnte es doch eigentlich auch so machen, dass man sagt, dass das größte Element das letzte sein muss, da die Liste ja aufsteigend sortiert ist?
 

jono

Top Contributor
Ja und das Problem was ich habe ist, dass ich nicht weiß, wie ich das letzte Element anspreche wie du sagst über eine Schleife.
 

mihe7

Top Contributor
Man könnte es doch eigentlich auch so machen, dass man sagt, dass das größte Element das letzte sein muss, da die Liste ja aufsteigend sortiert ist?
Ob das letzte Element das größte ist, spielt für last() nicht die Rolle: das letze Element ist dasjenige, auf das kein weiterer Eintrag folgt.

Ja und das Problem was ich habe ist, dass ich nicht weiß, wie ich das letzte Element anspreche wie du sagst über eine Schleife.
Ich geb Dir noch einen Algorithmus an die Hand, den Code musst Du aber schon selbst hinbekommen:
Code:
letztesElement := erstes Element
so lange letztesElement nicht auf das letzte Element der Liste zeigt {
    letztesElement := das auf letztesElement folgende Element 
}
gib letztesElement zurück
 

jono

Top Contributor
Java:
so lange letztesElement nicht auf das letzte Element der Liste zeigt
Das meine ich, letzteElement habe ich initialisiert indem ich
Java:
Node last = first;
gesetzt habe und jetzt muss ich ja mit einem Zeiger auf das letzte Element zeigen.
Aber "das letzte Element" muss ja auch eine spezifische Bezeichnung haben als Code
oder nicht?
 

Snaer

Aktives Mitglied
Code:
letztesElement := erstes Element
so lange letztesElement nicht auf das letzte Element der Liste zeigt {
    letztesElement := das auf letztesElement folgende Element
}
gib letztesElement zurück
Korrigiere mich wenn ich falsch liege
Code:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) 
if(i.next=null)
Return i
 

mihe7

Top Contributor
Das meine ich, letzteElement habe ich initialisiert indem ich
Java:
Node last = first;
gesetzt habe
richtig.

und jetzt muss ich ja mit einem Zeiger auf das letzte Element zeigen.
Aber "das letzte Element" muss ja auch eine spezifische Bezeichnung haben als Code
last ist der Zeiger :)

Nachem @Snaer schon fast die Lösung angegeben hat:
Java:
Node last = first; // das erste Element könnte das letzte sein.
while (last.next != null) { // Wenn last aber noch nicht das letzte Element ist,
    last = last.next; // dann könnte das nächste Element das letzte sein
}
return last;
 

jono

Top Contributor
Java:
	public int last() {
		Node last = first;
		while(last.next != null){
			last = last.next;
		}
		return last;
	}
Problem ist nur noch dass ein int zurückgegeben werden muss, wie mache ich das hier ?
 

mihe7

Top Contributor
Was daran falsch ist? Du kannst doch nicht einfach hergehen und sagen: gut, laut Aufgabe soll ich eine Zahl zurückgeben, aber das ist mir zu kompliziert, mache ich einfach etwas anderes draus.
 

jono

Top Contributor
Wie soll ich das denn sonst machen^^? Das Problem ist ja, dass last oben wegen first vom Typ Node ist und last kann ich nicht den Datentyp Int zuordnen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
ruutaiokwu JRE-/JDK-unabhängige PBKDF2WithHmacSHA512-Implementierung Java Basics - Anfänger-Themen 16
V Hilfe bei Implementierung einer boolean Methode Java Basics - Anfänger-Themen 6
K Fehler bei der Implementierung Java Basics - Anfänger-Themen 6
J Implementierung gcd();square() Java Basics - Anfänger-Themen 98
J Implementierung von Observer und Singleton-Pattern Java Basics - Anfänger-Themen 9
A Implementierung von String toString methode() Java Basics - Anfänger-Themen 4
G Projekt architektur (implementierung) Java Basics - Anfänger-Themen 3
M Implementierung einer getNextId Methode Java Basics - Anfänger-Themen 5
J Implementierung eines Zustandsdiagramms Java Basics - Anfänger-Themen 19
I GenericQueue / Implementierung als Ringspeicher Java Basics - Anfänger-Themen 4
MiMa Log4j2 implementierung Java Basics - Anfänger-Themen 4
S Interface Interface und seine Implementierung Java Basics - Anfänger-Themen 5
G Array implementierung Java Basics - Anfänger-Themen 23
J ANTLR Installierung und Implementierung Java Basics - Anfänger-Themen 2
E Hilfe bei Implementierung von Methoden Java Basics - Anfänger-Themen 10
S SkipList Implementierung Java Basics - Anfänger-Themen 1
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
J Interface Probleme bei der Implementierung Java Basics - Anfänger-Themen 1
E hashCode implementierung Java Basics - Anfänger-Themen 9
S Implementierung der Klasse Konto und Nutzung bereits vorhandener Klassen Java Basics - Anfänger-Themen 7
H Implementierung eines Interfaces erweitern Java Basics - Anfänger-Themen 13
O Generics - Implementierung Java Basics - Anfänger-Themen 7
A Hilfestellung zur Implementierung des Gaußsches Eliminationsverfahren Java Basics - Anfänger-Themen 4
B OOP Implementierung eines Heaps Java Basics - Anfänger-Themen 13
K Bucketsort Implementierung Java Basics - Anfänger-Themen 0
K Mergesort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
K Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
S Klassen Klassendiagramm Implementierung? Java Basics - Anfänger-Themen 5
J Bucketsort Implementierung Java Basics - Anfänger-Themen 0
C Stack - listenbasierte Implementierung Java Basics - Anfänger-Themen 4
N Was bedeutet "Implementierung vor dem Client verbergen" bei Design Patterns? Java Basics - Anfänger-Themen 2
T Collections LinkedList<LinkedList<T>> - Implementierung Java Basics - Anfänger-Themen 10
F Implementierung von Interfaces -> Problem mit main Java Basics - Anfänger-Themen 12
D Resourcebundle implementierung Java Basics - Anfänger-Themen 2
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
Q Implementierung von Listenern Java Basics - Anfänger-Themen 4
B Klassen Hilfe bei Implementierung Java Basics - Anfänger-Themen 5
N Compiler-Fehler Comparable / compareTo implementierung Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Binärbaums Java Basics - Anfänger-Themen 3
I Erste Schritte Implementierung der API Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Adressbuches Java Basics - Anfänger-Themen 20
M falsche implementierung von currentTimeMillis() ? Java Basics - Anfänger-Themen 14
G Implementierung eines Kontos Java Basics - Anfänger-Themen 11
M Quicksort implementierung Java Basics - Anfänger-Themen 23
SexyPenny90 Implementierung einer doubly linked list Java Basics - Anfänger-Themen 5
N Binärbaum/Implementierung Java Basics - Anfänger-Themen 9
U Doppelte Interfcae Implementierung Java Basics - Anfänger-Themen 10
K Kleiner Fehler bei Methoden Implementierung Java Basics - Anfänger-Themen 6
M Collections Problem bei Überschreibung von hashcode() und equals() bei Hashset-Implementierung Java Basics - Anfänger-Themen 5
S OOP Implementierung Komposition, Aggregation, Assoziation und Generalisierung Java Basics - Anfänger-Themen 2
C Klassenhirarchien zur Implementierung von Fahrzegen Java Basics - Anfänger-Themen 26
BinaryLogic Datentypen Statistik Interface - untersch. Implementierung Java Basics - Anfänger-Themen 5
E Performante Implementierung eines "Hintergrundprogramms" Java Basics - Anfänger-Themen 10
S Saubere Implementierung Java Basics - Anfänger-Themen 2
K Dijkstra implementierung 2.0 Java Basics - Anfänger-Themen 19
K dijskral implementierung Java Basics - Anfänger-Themen 14
U Probleme mit Server-Client implementierung Java Basics - Anfänger-Themen 5
K Game of Life Implementierung Java Basics - Anfänger-Themen 30
B OOP Problem bei Implementierung von Interface Java Basics - Anfänger-Themen 6
J HashSet Implementierung Java Basics - Anfänger-Themen 16
R NullPointerException in Queue-Implementierung Java Basics - Anfänger-Themen 11
X Frage zur Implementierung von equals() Java Basics - Anfänger-Themen 2
B Effektive Implementierung für Darstellung großer Datenmengen in Jogl Java Basics - Anfänger-Themen 5
D Datentypen Implementierung eines Binärbaumes Java Basics - Anfänger-Themen 7
B Implementierung Java Basics - Anfänger-Themen 2
N Implementierung Tic tac toc Java Basics - Anfänger-Themen 25
O Stack Implementierung als verkettete Liste Java Basics - Anfänger-Themen 8
Y Implementierung einer Potenzturm Funktion Java Basics - Anfänger-Themen 4
S Implementierung gegen Interfaces / List, ArrayList, LinkedList Java Basics - Anfänger-Themen 11
J Quicksort Implementierung-- Exception ArrayOutOfBounds Java Basics - Anfänger-Themen 6
U Implementierung Constructor Java Basics - Anfänger-Themen 7
T Problem mit Implementierung von einer HashMap aufgabe Java Basics - Anfänger-Themen 2
G Implementierung des Observer/Observable Patterns - Gut so? Java Basics - Anfänger-Themen 3
I Zugriff auf Implementierung verhindern Java Basics - Anfänger-Themen 8
D Implementierung nach MVC Java Basics - Anfänger-Themen 6
B Theoretische Frage zum Programmbau (nun zur Implementierung) Java Basics - Anfänger-Themen 8
H Implementierung von Interfaces Java Basics - Anfänger-Themen 4
G Implementierung von Bäumen Java Basics - Anfänger-Themen 2
N Probleme mit paint() bei Implementierung in ein Panel Java Basics - Anfänger-Themen 4
B Wie funktioniert die implementierung von c code in Java? Java Basics - Anfänger-Themen 7
D Listen in Listen in Listen ... ??? Java Basics - Anfänger-Themen 2
XWing listen Java Basics - Anfänger-Themen 7
FunkyPhil94 addLast und addFirst bei Listen Java Basics - Anfänger-Themen 6
S Einfach-Verkettete-Listen Ausgabe zeigt nur 1. und letzte instanz Java Basics - Anfänger-Themen 2
J 2 listen vergleichen, die auch null Elemente haben können ! Java Basics - Anfänger-Themen 9
W Liste mit Listen in JTable darstellen Java Basics - Anfänger-Themen 1
Buroto Threads Verschiedene .txt Dateien Auf Listen und Verbinden Java Basics - Anfänger-Themen 3
M Generics Vererbung Listen Java Basics - Anfänger-Themen 2
T Collections Sind Subklassen-Objekte in Listen mit Generics erlaubt? Java Basics - Anfänger-Themen 16
S Lineare listen verkettung Java Basics - Anfänger-Themen 7
S Listen Java Basics - Anfänger-Themen 12
S Listen , Nodes am ende anängen Java Basics - Anfänger-Themen 6
P Sortieren von Listen nach Attributen Java Basics - Anfänger-Themen 3
M Java Listen Java Basics - Anfänger-Themen 4
V einfach verkettete Listen Java Basics - Anfänger-Themen 10
A PhoneBook mit verketteten listen Java Basics - Anfänger-Themen 48
F ich brauche Hilfe bei Listen Java Basics - Anfänger-Themen 13
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
G Java Listen und Iterator Java Basics - Anfänger-Themen 2
S Erklaerung Listen Java Basics - Anfänger-Themen 27

Ähnliche Java Themen

Neue Themen


Oben