Übungsaufgaben aus "Algorithmen und Datenstrukturen"

[Cinematic]

Aufgabe 5 (Queue)
In der Vorlesung haben wir eine Queue mit Hilfe eines Arrays realisiert.
Überlegen Sie sich, wie man eine Queue mit Hilfe einer Liste realisieren kann.
Schreiben Sie Prozeduren in Pseudocode, um die Operationen enqueue ( ) und
dequeue ( ) einer Queue zu beschreiben. Benutzen Sie dazu die Operationen
insert ( ) und delete ( ) der erweiterten Liste (Bezeichnung extended_list) aus
Aufgabe 3.

Also ein Array hat ja eine festgelegte Anzahl von Werten vom index 0 bis index n-1.
Was ist denn der Unterschied zur Liste ?

Also bei der Queue ist es ja so, dass wenn ein Element hinzukommt, kann das nur ans Ende drangehangen werden. Und nur das erste Element kann die Queue verlassen, dabei rücken dann alle anderen Elemente ein Platz nach links.

Ich weiß nur nicht, wie ich für das Aufrücken einen Algorithmus schreiben kann bei einer Liste ? Wie sieht eine Liste überhaupt aus ? Also haben die Elemente einer Liste einen Index usw. ?

 

[GregoryH]

Google? Naja eigentlich gegen die Regeln aber ich bin mal so nett: Bei einer Liste kannst du

a) auch komplexere Typen speichern (Array nur Grundtypen soweit ich mich erinnere)
b) du kannst gezielt einzelne Einträge löschen und der Rest "rückt nach"
c) du kannst sofort von einem Element auf das nächste schliessen (die sind "verkettet")

uvm google & wikipedia ist dein freund.

inb4 close

 

[maxFrisch]

hey,
vermutlich geht es um eine einfach verkettete liste? dann siehts so aus:

in einer liste gibt es keinen index. jedes element hat einen zeiger, der auf das nächstfolgende element zeigt.

beispiel:
a zeigt auf b, b zeigt auf c, c zeigt auf d

um ein element einzuhängen: a zeigt auf b, b zeigt auf x, x zeigt auf c
um ein element zu entfernen: a zeigt auf b, b zeigt auf d

du musst also den zeiger eines elements, der auf das nächste element zeigt, immer entsprechend anpassen.


hoffe das war verständlich, AuD ist schon ein paar jährchen her bei mir .

 

[Cinematic]

Ah okay verstehe, nur eine Sache noch: wie schreib ich das im Pseudocode, wenn ich den Zeiger eines Elements anpassen will ?

 

[~purplet~]

Ich tippe auf ne verkettete Liste, google das mal. Ist aber n bisl naja fies, wer von sowas nie gehört hat kann ohne zu wissen was ne verkettete Liste is nicht oder nur schwer draufkommen.
Zum grübeln is die aufgabe aber gut^^

E: okay zu lahm...
Pseudocode: schreib einfach hin was du machst, z.b. "zeiger auf a mit zeiger auf b überschreiben" und bei ner schleife halt while das tue jenes, da gibts keine Syntax es sollte einfach nachvollziehbar sein. Schön an Pseudocode ist, dasses ansich die ganze Arbeit erledigt, danach kann mans in jede gewünschte Syntax schreiben solange die Sprachen nicht grundsätzlich verschieden aufgebaut sind.

 

[MaTT90]

eigentlich ganz einfach:

struct kette{
struct kette *pnext;
#irgendwelche variablen
};

das letzte element zeigt immer auf NULL/0
jetzt erzeugst du mit dynamischer speicherverwaltung z. b. new ein neues element.. indem im zeiger NULL/0 steht.. in dem vorherigen element wo gerade noch NULL/0 drinsteht hängst du den Pointer auf das neu erzeuge elemnt.. jetzt kannst du die kette solange durchlaufen bis NULL/0 zurückgegeben wird, weas das ende der verketteten liste angibt.. fertig ist die einfach verkettete liste

 

[ElfenLied]

Queue mit Hilfe einer Liste: 2.1

so will ich auch mal meine Hausaufgaben machen können

 

[MaTT90]

http://de.wikipedia.org/wiki/Liste_(Datenstruktur) gibts sogar bei wikipedia

 

[Cinematic]

Danke, hat mir alles gut geholfen

 

[Backslash]

Vermutlich sind einfach verkettete Listen gemeint, aber es wäre wohl eigentlich (wenn erlaubt) besser doppelt verkettete zu nehmen, brauchen zwar etwas mehr Speicher, allerdings kann man auch auf das letzte Element direkt zugreifen, was enqueue schneller macht.

PS: eigentlich ist das hier ja kein Hausaufgabenforum

 

[ice-breaker]

Auch einfach verkettete Listen können eine Referenz auf das letzte Element haben
Und oftmals haben die Implementierungen auch neben dem first einen last Zeiger. Eine verkettete Liste wäre hier also wirklich nur viel mehr Arbeit.