Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
17.09.2007 Aufgabe 5 ADT Warteschlange
Mein letzter Lösungsversuch zum Thema ADT:
a) Vereinfachung:
Zwischenschritt: front(enq(enq(create,3),4)) = 3
b) A6: length(create) = 0
A7: length(enq(s,x)) = 1 + length(s)
c) A8: merge(create, s) = s
A9: merge (s, t) = enq(merge(s,t), front(t))
d) static int maximum (Schlange kopf){
int maximum = wert;
if (this.nachfolger == null){
return maximum;
} else {
maximum = Math.max(this.maximum, nachfolger.maximum);
}
bei a), b) und d) stimm ich dir zu.
Bei c) verstehe ich dein zweites Axiom nicht, ich würde eher sagen:
merge(s, enq(create, y)) = enq(s,y)
Außerdem frage ich mich ob beim Basisfall merge(create, s) = merge( s, create) = s nötig wäre.
Kann mir jemand sagen ob das stimmt?
Und kennt jemand eine allgemeine Regel mit der ich erkennen kann ob ich genug Axiome angegeben hab? Ich neige nämlich immer dazu mehr anzugeben als nötig. Das heißt ich stelle Axiome auf die sich auch aus anderen herleiten lassen.
Du hast Recht, der Basisfall kann ja auch andersherum sein. Zum zweiten Axiom hat mal in nem anderen Thread jemand gesagt, dass das Verhalten, wenn man es nur mit create beschreibt meistens nicht ausreichend beschrieben ist. Deswegen der etwas kompliziertere Ausdruck.
Zu A8: Aber so hängst du doch noch ein zusätzliches Elemet nach dem mergen an?
Tatsächlich!, dann versuche ich’s mal noch komplizierter:
A9: merge (s, t) = enq(merge(s,deq(t)), front(t))
… und hoffe inständig, dass sowas nicht in der Prüfung drankommt…
d) würde denke ich nur stimmen, wenn die Schlange 2 Element hätte (Kopf und Nachfolger),
sie kann doch aber beliebig viele Werte haben, wenn ich mich nicht irre?
Dann würde ich das mit einer while-Schleife realisieren.
Hm, ich hab da:
merge(s, t) = { enq(s, front(t)) falls length(t) = 1 } { merge(enq(s, front(t)), deq(t) sonst }
1 „Gefällt mir“
@damon: sicher, dass man hier die Fallunterscheidung benötigt? Dein 1. Fall wird doch durch den 2.Fall abgedeckt oder hab ich hier einen Denkfehler?