> Home
> Algorithmen
> Datenstrukturen
> Maschinenmodelle
> Probleme
> Themen
> Mindmaps
> Aufgaben
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email
|
|
Implementation des Datentyps "Schlange" (Queue)
Datenstruktur und Operationen
Der Datentyp Schlange (engl. Queue) ist ein Abstrakter Datentyp, der nach dem First-In-Firts-Out-Prinzip (FIFO) arbeitet
und �ber folgende Standardoperationen verf�gt:
| Operation |
Erl�uterung |
| Create(Schlange) |
Legt eine neue Schlange an. |
| Empty(Schlange) |
Boolesche Operation, die �berpr�ft, ob die Schlange leer ist (R�ckgabe true)
oder noch Elemente enth�lt (R�ckgabe false). |
| Full(Schlange) |
Boolesche Operation, die �berpr�ft, ob die Schlange voll ist (R�ckgabe true)
oder noch weitere Elemente aufnehmen kann (R�ckgabe false). |
| Put(Schlange,Element) |
Gibt ein Element auf die Schlange, d.h. h�ngt das Element hinten an die Schlange an. |
| Get(Schlange,Element) |
Entfernt ein Element vorne von der Schlange. |
| Top(Schlange,Element) |
Betrachtet das erste Element der Schlange ohne es zu entfernen. |
Implementationsm�glichkeiten
Es gibt im Wesentlichen drei einfache M�glichkeiten zur Implementation des Abstrakten Datentyps Schlange:
(1) Implementation als Array
Bei der Implementation als Array ben�tigt man zwei Komponenten:
- Ein Array fester L�nge n
- Einen Zeiger î auf das letzte Element der Schlange
Dabei gilt:
- Das Array sei von 1 bis n durchnummeriert.
- Das erste Element der Schlange steht immer im ersten Arrayfeld.
- Bei der leeren Schlange hat der Zeiger auf das letzte Element den Wert Null.
|
13 |
100 |
22 |
12 |
27 |
33 |
40 |
50 |
83 |
25 |
55 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
î |
|
|
|
|
Algorithmische Umsetzung der Operationen
| Operation |
Erl�uterung |
| Create(Schlange) |
Das Array fester L�nge wird mit leeren Eintr�gen (z.B Nullelementen) initialisiert. Der Zeiger î wird mit dem Wert Null initalisiert. |
| Empty(Schlange) |
Es wird gepr�ft, ob der Zeiger î den Wert 0 (R�ckgabe true) oder >0 (R�ckgabe false) hat.
|
| Full(Schlange) |
Es wird gepr�ft, ob der Zeiger î auf das letzte Element den Wert des Index des Arrayelements hat(R�ckgabe true) oder kleiner ist (R�ckgabe false) hat. |
| Put(Schlange,Element) |
Das Element wird an die Stelle î +1 eingetragen. Der Wert des Zeigers î wird um 1 erh�ht. |
| Get(Schlange,Element) |
Das erste Element des Arrays wird entnommen. Alle anderen Elemente werden nach vorne durchgeschoben, indem
jedes Element um einen Platz nach vorne umkopiert wird. Der Wert des Zeigers î wird um 1 verringert. |
| Top(Schlange,Element) |
Das erste Arrayfeld wird ausgelesen ohne es zu entfernen. Sonst erfolgt keine Ver�nderung des Arrays. |
Diese Implementationsvariante mit einem Array hat folgende Vorteile:
- Einfache Programmierbarkeit der Datenstruktur mit einem Array und einer Integer-Variable als Zeiger
- Einfache Programmierbarkeit der Operationen
Deutlicher Nachteil dieser Variante ist allerdings:
- Hoher Aufwand f�r das Umkopieren aller Arrayelemente beim Entnehmen (get) eines Schlangenelements.
(2) Implementation als Ringstruktur
Bei der Implementaion als Ringstruktur ben�tigt man drei Komponenten:
- Ein Array fester L�nge n
- Einen Zeiger  auf das erste Element der Schlange
- Einen Zeiger Ê auf das letzte Element der Schlange
Dabei gilt:
- das Array sei von 1 bis n durchnummeriert.
- Das erste Element der Schlange steht an der Stelle, auf die der Zeiger
 verweist
- Das letzte Element der Schlange steht an der Stelle, auf die der Zeiger
Ê verweist
- Bei der leeren Schlange haben beide Zeiger den Wert Null
Bei der folgenden Abbildung enth�lt die Schlange die Elemente 12 27 33 40 50 83 25 und 55.
Auf das erste Element verweist der Anfangszeiger  .
Auf das letzte Element verweist der Endzeiger Ê .
Die Elemente 13 100 und 22 sind nicht mehr in der Schlange enthalten. Sie wurden entnommen, indem
der Zeiger  �ber sie hinweggesetzt wurde.
Solche Elemente m�ssen nicht explizit gel�scht werden. Sie k�nnen sp�ter durch neue Schlangeneintr�ge
�berschrieben werden.
|
13 |
100 |
22 |
12 |
27 |
33 |
40 |
50 |
83 |
25 |
55 |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
Ê |
|
|
|
|
Algorithmische Umsetzung der Operationen
| Operation |
Erl�uterung |
| Create(Schlange) |
Das Array fester L�nge wird mit leeren Eintr�gen (z.B Nullelemente) initialisiert. Die Zeiger  und Ê erhalten den Wert Null. |
| Empty(Schlange) |
Es wird gepr�ft, ob der Zeiger Ê den gleichen Wert wie der Zeiger  hat (R�ckgabe true) oder nicht (R�ckgabe false) hat.
|
| Full(Schlange) |
Die Schlange ist voll, falls entweder  = 1 und Ê = n oder Ê +1 = Â
(R�ckgabe tue), sonst nicht. |
| Put(Schlange,Element) |
Falls not Full(Schlange) gilt, wird das Element an der Stelle Ê +1 mod n + 1 eingef�gt und Ê := Ê +1 mod n + 1 gesetzt. |
| Get(Schlange,Element) |
Das erste Element des Arrays wird entnommen. Der Anfangszeiger wird mit  :=  +1 mod n + 1 um eine Stelle in der Ringstruktur weitergeschoben. |
| Top(Schlange,Element) |
Das erste Arrayfeld wird ausgelesen ohne es zu entfernen. Sonst erfolgt keine Ver�nderung des Arrays und der Zeiger. |
Diese Implementationsvariante mit einer Ringstruktur hat folgende Vorteile:
- Verh�ltnism��ig einfache Programmierbarkeit der Datenstruktur mit Array und Integer-Variablen als Zeiger
- Einfache Programmierbarkeit der Operationen �ber die Modulo-Operation (mod n + 1 ), wobei der Faktor 1 addiert werden mu�, wenn das Array von 1..n durchnummeriert wurde.
- Gute Ausnutzung des durch die Arrayl�nge festgesetzten Speicherplatzes
- Geringer Aufwand, weil f�r die Operationen put und get im Wesentlichen nur
Zeiger umgesetzt werden m�ssen und keine Umspeicherung von Arrayelementen notwendig ist.
Nachteil dieser Variante ist allerdings:
- Beim Initialisieren der Schlange festgelegte L�nge des Arrays.
(3) Implemenation als dynamischer Datentyp mit Zeigerstrukturen
Bei der Implementaion als dynamischer Datentyp ben�tigt man folgende elementare Datenstruktur:
- Eine Datenstrukur TElement die aus:
- einem Speicherplatz f�r ein Element und
- einem Zeiger auf das n�chste Schlangenelement
besteht.
Au�erdem wird eine Datenstruktur TSchlange ben�tigt, die aus folgenden Komponenten besteht:
- Ein Zeiger  , der auf das erste Element der Schlange verweist.
- Ein Zeiger Ê , der auf das letzte Element der Schlange verweist.
Dabei gilt:
- Der Zeiger
 verweist auf das erste Element der Schlange.
- Der Zeiger
Ê verweist auf das letzte Element der Schlange.
- Bei der leeren Schlange zeigen beide Zeiger ins Nichts (nil).
- Die Schlange besteht also aus aneinanderh�ngenden Elementarstrukturen vom Typ TElement
| Element1 |
—> |
Element2 |
—> |
Element3 |
—> |
Element4 |
—> |
| Â |
|
|
|
|
|
Ê |
|
Algorithmische Umsetzung der Operationen
| Operation |
Erl�uterung |
| Create(Schlange) |
Die Zeiger  und Ê verweisen auf nichts (nil). |
| Empty(Schlange) |
Es wird gepr�ft, ob die Zeiger Ê und  beide den Wert nil haben (R�ckgabe true) oder nicht (R�ckgabe false).
|
| Full(Schlange) |
Die Schlange ist voll falls der zur Verf�gung stehende Speicherplatz des Rechners aufgebraucht ist. |
| Put(Schlange,Element) |
Es wird eine neues Element vom Typ TElement erzeugt. Sein Zeiger wird auf das aktuelle letzte Element der Schlange gerichtet.
Der Zeiger Ê wird auf das neu eingetragene Element gerichtet. |
| Get(Schlange,Element) |
Das erste Element der Schlange wird entnommen. Der Anfangszeiger wird auf den Vorg�nger des ersten Elements gerichtet. Der f�r das entnommene Element reservierte Speicherplatz wird wieder freigegeben. |
| Top(Schlange,Element) |
Das erste Arrayfeld wird ausgelesen ohne es zu entfernen. Sonst erfolgt keine Ver�nderung der Zeiger. |
Diese Implementationsvariante als dynamische Datenstruktur mit Zeigern hat folgende Vorteile:
- Gute Ausnutzung des rechnerabh�ngigen Speicherplatzes, da immer nur so viel
Speicherplatz zur Verf�gung gestellt werden muss, wie ben�tigt wird.
- Geringer Aufwand, weil f�r die Operationen put und get im Wesentlichen nur
Zeiger umgesetzt werden m�ssen.
Nachteil dieser Variante ist allerdings:
- Aufwendige und fehleranf�llige Programmierung (pointer).
|
|