Aufgabe 10.1


ich hab vorsichtshalber gleich mal am roten platz gezeltet über die feiertage,
damit ich auch ja nix wichtiges verpasse… :wink: :-p :cool:


wollte nur mal fragen, ob ihr die a) auch über ein array gelöst habt, die ganze sache funktioniert nur hänge ich gerade bei der b) und bin mir da nicht sicher, ob ein array für die zirkulärereihung die richtige wahl war. danke im vorraus.


“Reihung” ist der Versuch, den Begriff “array” ins Deutsche zu übersetzen. Und eine zirkuläre Reihung ist dann halt ein Array, das in einer Klasse gekapselt ist und dessen Anfang und Ende zusammengekleistert werden.

Was mich an dieser Stelle noch interessieren würde: Habt ihr mit [m]implements Schlange[/m] gearbeitet oder nicht?


also ich soweit net, ich lass mir in

public void einpacken() throws IOException {

eine neue ZirkuläreReihung erstellen und werfs da rein. Denke das ist auch so gedacht.


Also in der Klasse [m]ZirkulaereReihung[/m] verwende ich auch ein array und ich hab auch [m]implements Schlange[/m] verwendet.
Was hier zirkuläre Reihung heißt ist eigentlich eine ganz normale Queue, die den Vorteil hat, dass man halt einfach Elemente hinzufügen und entfernen kann, ohne dass man sich groß um die Indizes kümmern muss. Der Head hat halt immer den Index 0, unabhängig davon, wo er im array jetzt wirklich liegt.

@schniggie: Eigentlich solltest du in der b) gar nicht mehr merken, dass deine ZirkulaereReihung ein array verwendet, da du ja nur über die Methoden des Schlange-Interface darauf zugreifst.


@TheFlow

das ist mir schon klar, dass ich in meinem Packer nicht mehr sehe ob ich ein Array benutze, aber wenn ich in meinem Einpack Code, mir eine neue Instanz von ZirkuläreReihung mache, muss ich doch nichts implementieren … oder bin ich nun total neben der Spur. in dem Packer Source werden ja auch nur Instanzen von Einpacken und Auspacken erstellt. Wenn ich total falsch bin tut es mir leid :wink:


Mal eine dämliche Frage…was ist 'n jetz so besonders an einer Zirkulären Reihung im Vergleich zu einer “normalen” Schlange…?
Ich werd aus dem Skript und dem post weiter oben nicht sonderlich schlau…

Hab mal versucht das ungefähr zu realisieren…vllt. mag sich mal jemand mein File anschauen und mir sagen ob das einigermaßen hinkommt…

Attachment:
A.java: https://fsi.cs.fau.de/unb-attachments/post_30716/A.java


Also so wie ich das aus dem Skript und anderen Unterlagen verstanden habe, ist eine zirkuläre Reihung fast das gleiche wie eine normale Schlange. Nur da eine zirkuläre Reihung eigentlich nie ein Ende und einen Anfang hat weil sie ja zirkulär ist. D.h. konkret wenn man auf ein Element in der Reihung zugreift, so kann es nie sein das man auf ein Element ausserhalb dieser Reihung zugreift weil man ja immer in einem Kreis ist. Und wie im Skript bereits steht berechnet man den Index wie folgt: “Für jeden Index ist die nächste Position modulo der max. Schlangen-größe.” (d.h. Index % maxNrOfElements).
Mein code ist deinem recht ähnlich allerdings solltest du manche sachen nochmal überdenken, aber das prinzip stimmt bis auf die oben erläuterte sache.


Okay.ich überdenke das nochmal.
Danke erstmal.


Nach außen verhält sich das Ding wie ein normaler Queue/Schlange (≠snake…)

Intern schaut das Ganze folgendermaßen aus:

Wir haben eine leere ZR:
[m]_ _ _ _ _ _[/m]

Und in die füllen wir 4 Elemente:
[m]1 2 3 4 _ _[/m]

Jetzt löschen wir ein paar davon:
[m]_ _ 3 4 _ _[/m]

Und tun wieder drei rein:
[m]7 _ 3 4 5 6[/m]

Wenn man stur eine Warte-Schlange programmieren würde, bei der die hinteren nach vorne aufrücken, wenn ein Platz frei wird, würde das bedeuten, dass man bei jedem Löschvorgang ziemlich viel Speicher verschieben muss, und das dauert…

Ich hoffe mal, das beantwortet die Frage… :slight_smile:


ah okay…prinzip ist jetz klar.jetz fehlt noch die umsetzung. g
danke.


Mann kann die Reihung auf 2 verschiedene Weisen implementieren:

  1. Das erste Element befindet sich immer auf Position 0, wobei beim Herausnehmen eines Elements
    alle verbliebenen nach links verschoben werden müssen.

  2. Ein zweiter Zeiger markiert die Position des erstem Elements.

Die zweite Methode ist meiner Meinung nach die Zirkuläre,
wobei ich dann nicht verstehe welchen sinn die getAt Methode haben soll?
Meine beiden Zeiger wandern dann zirkulär durchs Feld, wobei der untere dass erste Element der Reihung
und der obere das letzte Element der Reihung markiert.
Beim Hinzufügen inkrementier ich den oberen Zeiger modulo der Feldgrösse
und beim herausnehmen den unteren modulo der Feldgrösse.
Meiner Meinung nach entspricht diese vorgehensweise dem Ausdruck zirkulär am ehesten oder?

Das führt nun aber dazu, dass meine Elemente immer als Block irgendwo im Array liegen,
wobei jemand der die getAt methode aufrufen will sich ja immer darauf verlässt,
dass das erste Elemente bei 0 zu finden ist.
Ich könnte natürlich in der getAt methode den angeforderten Index immer relativ berechnen,
d.h eben auf die Tatsächliche Lage des Datenblocks im Array bezogen.

Bin mir langsam aber nich mehr sicher ob nicht doch die erstere Methode verlangt ist!
Wie habt ihrs denn so?


Ich hab auch die zweite Variante. Also getAt(0) liefert immer den Head der Queue, wobei Head auf den Anfang des Datenblocks zeigt, usw.

Zu solchen Sachen kann ich nur das Buch “Introduction to Algorithms” (http://www.amazon.de/exec/obidos/ASIN/0262531968/028-9935815-1996513) empfehlen. Nicht von “Introduction” in die Irre führen lassen; in dem Buch sind wirklich fast alle diese Standard-Algorithmen erklärt, meist noch mit einigen Beispielen in Pseudo-Code. Nicht ganz billig, aber IMHO eine lohnende Investition.


Auch genauso wie Flow.
IMHO machts nur so Sinn, wenn mans dann beim Packen/Entpacken verwendet.


Also ich hab jetz noch einige zeit gegrübelt…aber ich versteh einfach nicht was es mit diesem modulo auf sich hat…

Auserdem kann der Ausdruck „Index % maxNrOfElements“ gar nicht stimmen oder?!?
Denn der index ist doch i.d.R kleiner als die Max.-anzahl der Elemente.und somit liefert der ausdruck immer index zurück,oder?

Ziemlich confusing,vllt. sollt ich mal ne nacht darüber pennen… :smiley:


@Comrade

der index ist immer nur dann kleiner als die max. schlangenlänge, wenn du beim entfernen der elemente, immer wieder deine ganze reihung schön nach links verschiebst, sonst kann der index sehr wohl größer als die max. schlangenlänge werden und somit haben wir das modulo erklärt :wink:


“Für jeden Index ist die nächste Position modulo der max. Schlangen-größe”

Ich hab also in einer Schlange mit Länge 5 einen Index 0, der aber tatsächlich ein Element an der Position 4 bezeichnet, wenn ich jetzt das nächste Element (–> Index 1) nimm, bin ich bei Position (4+1) mod 5 = 0


hab mal den test von immoartl bei meiner queue ma ausgeführt,
mit folgendem ergebnis:

  • Fuellen des Queue…
    Capacity: 5
    Size: 5
    Leer: false
    Voll: true
    Inhalt: 0 1 2 3 4

  • Erstes Element entfernen…
    Capacity: 5
    Size: 4
    Leer: false
    Voll: false
    Inhalt: 0 1 2 3

  • Ein Element einfuegen…
    Capacity: 5
    Size: 5
    Leer: false
    Voll: true
    Inhalt: 5 1 2 3 4

aber es sollte eigentlich beim zweiten block: 1 2 3 4 heißen, oder irr ich mich da? verstehs aber nich, hab denk soweit alles richtig, und das neue element fügt er ja auch richtig ein…
Vielen dank!


So wie’s aussschaut, fügt er das neue Element nicht an der richtigen Stelle ein – intern muss es tatsächlich so ([m]5 1 2 3 4[/m]) aussehen, nach außen sollte sich das Ganze aber wie eine ganz normale Schlange verhalten: → [m]1 2 3 4 5[/m]

So schaut’s bei mir aus:

* Fuellen des Queue...
Capacity:  5
Size:      5
PosRead:   0
PosWrite:  5
Leer:      false
Voll:      true
Inhalt:    0 1 2 3 4


* Erstes Element entfernen...
Capacity:  5
Size:      4
PosRead:   1
PosWrite:  5
Leer:      false
Voll:      false
Inhalt:    1 2 3 4


* Ein Element einfuegen...
Capacity:  5
Size:      5
PosRead:   1
PosWrite:  6
Leer:      false
Voll:      true
Inhalt:    1 2 3 4 5

Mir ist das Grundprinzip dieser Zirkulären Reihung schon klar, aber ich steh grad bei einer Sache auf dem Schlauch.
Folgendes:
Wenn meine Queue grade erzeugt wurde, dann stehen doch meine Zeiger für ANFANG und ENDE auf dem ersten Element des Arrays, obwohl da ja eigentlich noch nix drin ist. Jetzt füge ich das erste Element mit append ein und muss da ja eigentlich noch keinen Zeiger verschieben, da ja immernoch nur ein Element in meiner Schlange ist, die Zeiger für ANFANG und ENDE also immernoch auf das selbe Element zeigen dürfen. Wenn ich das zweite Element einfüge müsste jetzt zum ersten mal der Zeiger für ENDE um 1 nach rechts rutschen.
Soweit so gut, oder ist hier schon mein Denkfehler?
Mein Problem ist jetzt, zu erkennen wann die Schlange tatsächlich leer ist. Wenn ANFANG und ENDE auf das selbe Element zeigen ist das ja kein sicherer Indikator, denn es könnte immernoch ein Element drin sein.