Weiter: Der,Scheibenwischer-Task`` Hinauf: 18.8 Ein Platten-Treiber Zurück: Entwurf von Untersystemen

Das Listenobjekt

 

Bis jetzt haben wir noch keinerlei Vorstellung, welche Art von Liste wir realisieren wollen. Wir haben aber die notwendigen Operationen  schon festgelegt:

• Ist die Liste leer?
• Gehe an den Anfang der Liste.
• Gehe an das Ende der Liste.
• Füge ein Element in die Liste ein.
• Gehe zum nächst größeren Listenelement.
• Gehe zum nächst kleineren Listenelement.
• Lies den Inhalt des aktuellen Listenelementes.
• Lösche das aktuelle Element aus der Liste.

Außerdem gibt es mehrere, zu berücksichtigende Punkte :

1. Die Liste soll beliebig viele Einträge haben können.
2. Es soll immer nur ein Task darauf zugreifen können, damit die interne Struktur nicht zerstört werden kann.
3. Der Scheibenwischer-Task, also der Task, der die Listenelemente herausliest, soll die Liste sowohl in auf- als auch in absteigender Richtung bearbeiten können, da er den Lese-Schreibkopf ja in beiden Richtungen über die Platte bewegt.

Aus Punkt 1 folgt, daß wir eine verkettete Liste verwenden werden. Punkt 2 wird dadurch erledigt, daß wir ein geschütztes Objekt verwenden (vgl. Abbildung 18.22).

 
Abbildung: Struktur der geschützten Liste 

Punkt 3 aber bedeutet, daß wir am besten eine doppelt verkettete Liste   realisieren werden, die ungefähr das in Abbildung 18.23 dargestellte Aussehen haben wird.

 
Abbildung 18.23: Eine doppelt verkettete Liste 

Über die tatsächlichen Daten in den einzelnen Listenelementen brauchen wir uns vorläufig keine Gedanken machen, da wir ja schon beschlossen haben, die Liste als generisches Paket zu implementieren, wo wir einfach den ,,Inhalt`` als privaten generischen Parameter angeben. Allerdings müssen wir eine Ordnungsrelation für die Listenelemente fordern, damit wir eine sortierte Liste aufbauen können.

Eine entsprechende Ada-Spezifikation lautet:

$$
generic$$
$$
type Element is private;$$
with function "" (x,y: Element) return boolean;$$
$$
package Doppelt_verkettete_Liste is$$
$$
Anfang_der_Liste: exception;$$
Ende_der_Liste: exception;$$
$$
function Liste_leer$$
return boolean;$$
-$$
-Gibt'true'zurueck,wenndieListeleerist,$$
-sonst'false'.$$
-$$
procedure Geh_an_den_Anfang;$$
-$$
-GehtandenAnfangderListe.FallsdieListeleer$$
-ist,wirddieExceptionEnde_der_Listeausgeloest.$$
$$
procedure Geh_an_das_Ende;$$
-$$
-GehtandasEndederListe.FallsdieListeleer$$
-ist,wirddieExceptionAnfang_der_Listeausgeloest.$$
$$
procedure Fuege_ein($$
das_Element: Element);$$
-$$
-FuegtdasangegebeneElementindieListeein.$$
-$$
$$
function Geh_zu_naechst_groesserem_Element($$
aktuelles_Element: Element)$$
return Element;$$
-$$
-GehtzumnaechstgroesserenElement,fallskeinesexistiert$$
-wirddieExceptionEnde_der_Listeausgeloest.$$
-$$
$$
function Geh_zu_naechst_kleinerem_Element($$
aktuelles_Element: Element)$$
return Element;$$
-$$
-GehtzumnaechstkleinerenElement,fallskeinesexistiert$$
-wirddieExceptionAnfang_der_Listeausgeloest.$$
-$$
$$
function Lies_aktuelles_Element$$
return Element;$$
-$$
-GibtaktuellesElementzurueck.$$
-$$
$$
procedure Loesche_aktuelles_Element;$$
-$$
-LoeschtdasaktuelleElement;$$
-$$
$$
end Doppelt_verkettete_Liste ;$$

Weiter: Der,Scheibenwischer-Task`` Hinauf: 18.8 Ein Platten-Treiber Zurück: Entwurf von Untersystemen