Dynamische Datenstrukturen in Pascal Flashcards
Unterschied zwischen statischen und dynamischen Datenstrukturen
Speicheplatzbedarf steht bei statischen Datenstrukturen schon bei der Übersetzung fest.
Bei dynamischen Datenstrukturen wird Speicherplatz erst während der Laufzeit (Standardprozedur new()) angelegt bzw. (Standardprozedur deipose()) wieder freigegeben.
Standad-Verbundobjekt als Listenelement
record
info : type;
next : tRefListe;
end;
Nachteile Linearer Listen gegenüber Feldern
- Liste kann nur entlang der Verzeigerung durchlaufen werden
- Suchen und “Anwählen” eines Objektes sowie damit jede darauf zurückgrufende Funktion (Löschen eines bestimmten Elements etc.)
=> einfach aber zeitaufwändig
Unterschied zwischen Zeigervariable und Variable
- Zeigervariable enthält Verweis (Speicheradresse) des zugehörigen Objekts
- Variable enthält Wert des Objekts direkt
Dereferenzierung
Zugriff auf ein Objekt über Zeigervariable
Wie wird ein Zeigertyp definiert?
tRefTyp = ^tTyp;
tTyp ist beliebiger Datentyp; Wertemenge für tReftyp sind alle Verweise auf Objekte vom Typ tTyp.
Beispiel:
tRefListe = ^tListe;
tListe = record
info : integer;
next : tRefListe;
end;
Wie wird ein Objekt durch eine Zeigervariable angesprochen?
var
Zeig : tRefTyp;
[…]
Zeig^;
Wie wird eine Info-Komponente eines Objekts durch eine Zeigervariable ausgelesen?
var
Zeig : tRefTyp;
[…]
Zeig^.info;
Was macht dieser Befehl?
Zeig1 := Zeig2
Zeig1 verweist anschließend auf das gleiche Objekt wie Zeig2.
Was macht dieser Befehl?
Zeig1^ := Zeig2^
Das Objekt, auf das Zeig1 verweist, hat anschließend den gleichen Wert wie jenes, auf das Zeig2 verweist. Die Zeiger zeigen immernoch auf zwei verschiedene Objekte.
Was macht die Standardprozedur new ?
new(Zeig) legt ein neues Objekt vom Wertetyp von Zeig an und weist Zeig die Referenz auf dieses Objegt zu. Der Wert von Zeig^ ist bis zur initialisierung undefiniert.
Wie wird ein “Zeigerobjekt” initialisiert?
Normale Zuweisung:
Zeig^ := WERT;
Was macht die Standardprozedur dispose ?
dispose(Zeig) löscht das Detenobjekt, auf das Zeig verweist. Zeig^ ist anschließend undefiniert, ebenso wie alle anderen Zeigervariablen, die auf Zeig^ verwiesen haben.
Wann ist Zeig1 = Zeig2 true?
Wenn Zeig1 und Zeig2 auf das gleiche Datenobjekt verweisen.
Wann ist Zeig1^ = Zeig2^ true?
Wenn die Datenobjekte, auf die die Zeigervariablen verweisen, den gleichen Wert haben, unabhängig davon, ob sie auf das gleiche oder zwei verschiedene Objekte zeigen.
Was ist der Vorteil einer Linearen Liste gegenüber einem Feld?
Da der Speicherplatz dynamisch zugewiesen wird, wird kein solcher verschwendet.
Welche Schritte sind zur Initialisierung einer Liste zu ergreifen?
- Definition Zeigertyp (type)
- Definition Listenelementtyp (gleich unter Zeigertyp)
- Deklaration Anker (var)
- Initialisierung im Programmrumpf (:= nil)
Wie funktionieren Lineare Listen?
- Anfangszeiger zeigt auf erstes Objekt
- Objekt besteht aus Wert-Komponente und
- Verweis auf zweites Objekt
- usw.
- letztes Objekt verweist auf nil
Code: Listenelement am Listenanfang einfügen
Zeiger^.next := RefAnfang;
RefAnfang := Zeiger;
Code: Referenz auf Wert in Liste suchen
if Zeiger <> nil then
{ Liste nicht leer }
begin
while (Zeiger^.next <> nil) and (Zeiger^.info <> Wert) do
Zeiger := Zeiger^.next;
if Zeiger^.info <> Wert then
{ Listenende }
Zeiger := nil;
Ausgabe := Zeiger;Typisches Vorgehen bei der Bearbeitung von Linearen Listen
- Sonderfälle abdecken:
- leere Liste
- Operation am Listenanfang
- Normalfall
- evtl. Sonderfall: Operation am Listenende
Algorithmus: sortiert in Liste einfügen
if RefAnfang = nil
{ Liste leer }
Listenelement am Anfang einfügen
else if RefAnfang^.info > Neuer Wert
{ Operation am Listenanfang }
Listenelement am Anfang einfügen
else
{ Position suchen }
gefunden := false;
Hilfszeiger := RefAnfang;
Referenz auf Wert in Liste suchen; modifiziert durch Vergleich; gefunden true setzen
if gefunden then
Listenelement in der Mitte einfügen
else
Listenelement am Ende anhängenCode: Listenelement in der Mitte einfügen
- Hilfszeiger zeigt auf Element vor dem neuen Element
NeuerZeiger^.next := Hilfszeiger^.next;
Hilfszeiger^.next := NeuerZeiger;
Code: Listenelement am Listenende anhängen
- Hilfszeiger zeigt auf letztes Element
Hilfszeiger^.next := NeuerZeiger;
NeuerZeiger^.next := nil;
Code: Listenelement löschen
Hilfszeiger := ZuEntfernenZeiger;
ZuEntfernenZeiger := ZuEntfernenZeiger^.next;
dispose(Hilfszeiger);
Algorithmus: Element mit gesuchtem Wert löschen
if RefAnfang = nil then
{ Liste leer }
nicht gefunden
else
Element mit Wert suchen
- Hilfszeiger auf Anfangszeiger;
- while (Hilfszeiger^.next <> nil) do
- entlanghangeln bis Wert im Feld hinter Hilfszeiger gefunden
(if Hilfszeiger^.next^.info = Wert then) - Listenelement hinter Hilfszeiger löschen
(Hilfszeiger^.next wird nil; Ende while-Schleife) - else
Zeiger := Zeiger^.next;
Liste oder Baum als Parameter an Funktion übergeben
übergeben wird der Anfangszeiger bzw. Zeiger auf die Wurzel
Transposition Rule
Durch Vertauschen eines gesuchten gefundenen Elementes mit seinem Vorgänger rutschen häufig gesuchte Elemente immer weiter nach vorne. Dadurch sinkt der durchschnittliche Zeitaufwand für Suchen.
Wurzel
Startknoten eines Baumes
Sohn / Kind
Nachfolger eines Baumknotens
Vater
Vorgänger eines Baumknotens
innerer Knoten
Knoten mit Vorgänger und Nachfolger
Blatt
Knoten ohne Nachfolger
Teilbaum
Jeder Knoten eines Baumes öffnet einen Teilbaum mit aus ihm entspringenden Knoten.
Eigenschaften eines Baumes mit nichtleerer Knotenmenge
- Hat genau einen Knoten ohne Vorgänger (Wurzel)
- Von der Wurzel aus ist jeder andere Knoten durch genau eine Folge von Kantewn erreichbar.
binärer Baum
Jeder Knoten hat maximal zwei Nachfolger (links, rechts).
Wie wird der Typ binär Baum implementiert?
type
tRefBinBaum = ^tBinBaum;
tBinBaum = record
info : type;
links : tRefBinBaum;
rechts : tRefBinBaum;
end;
binärer Suchbaum
- die Werte im linken Teilbaum eines Knotens sind alle kleiner als der Wert des Wurzelknotens
- die Werte im rechten Teilbaum eines Knotens sind alle größer als der Wert des Wurzelknotens
- kein Wert kommt doppelt vor (genau so viele Knoten wie Werte)
Suchpfad
Folge der Knoten, die zu einem gesuchten Wert führen
Tiefe
- Ebene des gesuchten Knotens
- Menge der Knoten auf Suchpfad
Höhe
Länge des längsten auftretenden Suchpfades in einem Suchbaum
Berechnung minimaler Höhe eines Suchbaumes
|’ log(tief2) (n+1) ‘|
n = Anzahl der enthaltenen Werte
natürlicher Suchbaum
Suchbaum, der durch iteriertes Einfügen einer Zahlenfolge in einen anfangs leeren Baum entsteht.
Jede mögliche Eingabefolge für eine Wertemenge ergibt einen natürlichen Suchbaum.
degenerierte Suchbaum
zu Liste degenerierter Suchbaum der Höhe n bei n = Anzahl der enthaltenen Werte
vollständiger Suchbaum
Suchbaum mit minimaler Höhe, bei dem die Tiefe der Blätter um maximal eins abweicht
Rekursion
Rückgriff einer Funktion etc. auf sich selbst
Welche Voraussetzungen müssen beim Einsatz einer Rekursion unbedingt erfüllt werden?
- Problemverkleinerung
- Abbruchbedingung
rekursive Datenstrukturen
andere Bezeichnung für Listen und Bäumen, da diese sich hervorragend rekursiv bearbeiten lassen.
Laufzeitstack
Stapel, die der Compiler bei Bedarf während der Laufzeit (bspw. bei Rekursionen) zur Verfügung stellt.
Rekursionstiefe
Menge der gleichzeitig nicht abgeschlossenen Rekursionen
Wann ist ein rekursiver Ansatz einem iterativen Ansatz vorzuziehen?
- IMMER, wenn die iterative Variante auf einen Stapel zurückgreifen müsste (Laufzeitstapel günstiger)
- u.U. auch dann, wenn er die Programmkomplexität stark verringert
LIFO
Last In First Out:
iteratives Einlesen und anschließendes Auslesen einer Liste am Listenanfang
Code: rekursive Suche in Liste
function ListenElementSuchen (inRefAnfang : tRefListe; inWert : tType)
var
Zeiger : tRefListe;
begin
Zeiger := inRefAnfang;
if inRefAnfang <> nil then
if inRefAnfang^.info <> inWert
ListenElementSuchen (inRefAnfang^.next, inWert);
ListenElementSuchen := Zeiger;
end;
preorder (Erklärung)
Hauptreihenfolge
Folge der Knoten nach Zweig und Stufe in einem Baum
Durchlaufen preorder (rekursiver Algorithmus)
- Ist der Baum leer, dann STOP, sonst:
- Betrachte Wurzel
- Durchlaufe linken Teilbaum der Wurzel preorder
- Durchlaufe rechten Teilbaum der Wurzel preorder
inorder (Erklärung)
symmetrische Reihenfolge
Folge der Knoten von links nach rechts. Ergibt für einen Suchbaum die Werte in sortierter Reihenfolge.
Durchlaufen inorder (Algorithmus)
- Ist der Baum leer, dann STOP, sonst:
- Durchlaufe linken Teilbaum der Wurzel inorder
- Betrachte Wurzel
- Durchlaufe rechten Teilbaum der Wurzel inorder
