Programmierung und Software-Entwicklung – Daten, ihre Strukturierung und Organisation

Programmaufbau

subprogram_declaration ::= [overriding_indicator] subprogram_specification ;
subprogram_specification ::= procedure_specification | function_specification
procedure_specification ::= procedure defining_program_unit_name parameter_profile
function_specification ::= function defining_designator parameter_and_result_profile

subprogram_body ::= [overriding_indicator] subprogram_specification is declarative_part
 begin handled_sequence_of_statements end [designator] ;
overriding_indicator ::= [not] overriding

Lexikalische Einheiten

Lexikalische Einheit:  Ein Programm ist eine Folge von Zeichen aus dem Zeichensatz.
Die Zeichen bilden eine Folge von sog. lexikalischen Einheiten. Zu diesen gehören:

• Bezeichner zur Identifizierung von Programmobjekten

• Literale zur Bezeichnung von festen Werten (Zahlen, Zeichen, Strings)

• Begrenzer (delimiter), die eine spezielle Bedeutung besitzen und gleichzeitig lexikalische Einheiten voneinander trennen (z. B. &, ’, +, (, ), :=, >= usw.)

• Wortsymbole (reservierte Wörter der Sprache) mit spezieller Bedeutung (for, if,
  procedure, …), dürfen nicht als Bezeichner verwendet werden

• Trennzeichen (separator) zur Trennung von lexikalischen Einheiten aus Lesbarkeitsgründen (Zwischenraum, Whitespace)

• Kommentare dienen der Erläuterung und Lesbarkeit (in Ada Zeichenfolgen ab --)

Zeigertypen

Interne/externe Namen:  Jede Variable hat einen internen (Speicheradresse) und einen externen Namen (symbolische Bezeichnung für die Speicheradresse).
In Ada dürfen „normale“ Zeigervariablen nur auf Variablen zeigen, die ausschließlich über Zeiger ansprechbar sind (sich also im Heap befinden).

Speicherbereiche:  Es gibt drei große Speicherbereiche: Programmspeicher (Programmcode), Stack/Keller (Speicher für deklarierte Variablen, Blockstruktur) und Heap/Haufen (Variablen ohne externen Namen).

Eine Zeigervariable wird bei Deklaration im Stack angelegt. Mittels new wird dann eine Variable im Heap allokiert, bei Wertzuweisung erhält der Zeiger die Adresse des erzeugten Objekts.

Dynamische Datenstrukturen in Ada:  Dynamische Datenstrukturen sind durch Zeiger „zusammengehaltene“ Daten. Mit Zeiger können sich ständig verändernde Daten gut beschrieben werden. In Ada geht dies z. B. so:

type Zelle;                  -- Vorwaertsdeklaration
type Ptr_Zelle is access Zelle; -- Zeigertyp
type Zelle is record         -- Datentyp
  Inhalt : Character;
  Naechster : Ptr_Zelle;
end record;
...
Anker : Ptr_Zelle;           -- Zeigervariable
Test : constant Ptr_Zelle := new Zelle; -- konstante Zeigervariable
...
Anker := new Zelle'('a', null); -- Allokation eines neues Objekts, Nullpointer
Put (Anker.Inhalt);
-- oder Anker.all.Inhalt (automatische Dereferenzierung bei Records!)

Wertzuweisung bei Zeigern:  Bei einer Zuweisung zwischen Zeigern müssen linke und rechte Seite den gleichen Datentyp (Zeigertyp) besitzen. Prinzipiell muss in Ada jede Dereferenzierung mittels .all angegeben werden. Bei Records darf dies jedoch weggelassen werden.

Gleichheit bei Zeigern:  Zwei Zeiger sind gleich, wenn sie auf dieselbe Variable zeigen.

Listen

Lineare Liste:  In einer linearen Liste sind die Elemente linear angeordnet, es gibt keine Verzweigungen. Lineare Listen können als einfach (jedes Element zeigt auf seinen Nachfolger) oder doppelt verkettete Liste (Zeiger für den Vorgänger) realisiert werden. Bei einer zyklischen Liste zeigt das letzte Element nicht auf null, sondern auf das erste Element der Liste.

Operationen der linearen Liste: Empty (gibt leere Liste zurück, Nullpointer),
Isempty(A) (überprüft, ob A leer ist), First(A) (gibt das erste Element der Liste zurück), In_Front(E, A) (fügt am Anfang ein Element hinzu), Append(E, A) (fügt am Ende ein Element hinzu), Delete(E, A) (löscht alle Elemente mit dem Inhalt aus der Liste).

Stack (Stapel):  Ein Stack ist eine lineare Liste mit genau den Operationen Empty(A) (leert eine Liste durch Setzen auf Nullpointer), Isempty(A) (überprüft, ob A leer ist), Top(A) (gibt das letzte Element zurück), Push(A, E) (fügt ein Element ans Ende an), Pop(A) (löscht das letzte Element der Liste).
Ein Stack ist eine Liste, die nach dem LIFO-Prinzip (last in first out) arbeitet.

Queue (Schlange):  Eine Queue ist eine lineare Liste mit genau den Operationen Empty(A) (leert eine Liste durch Setzen auf Nullpointer), Isempty(A) (überprüft, ob A leer ist),
First(A) (gibt das erste Element zurück), Enter(A, E) (fügt ein Element ans Ende an), Remove(A) (löscht das erste Element der Liste).
Eine Queue ist eine Liste, die nach dem FIFO-Prinzip (first in first out) arbeitet.

Graphen (Geflechte):  Ein Graph ist ein beliebig vernetztes Gebilde (also i. A. keine lineare Liste). Dieses besteht aus Knoten (Elemente des Datentyps) und Kanten (Verweise zwischen ihnen).

Zeiger auf Stackvariablen:  Dies ist in Ada möglich, falls der Zeigertyp mit all und die referenzierte Variable mit aliased (Warnung für den Programmierer und Compiler optimiert nicht) deklariert wurde:

type Ptr_Integer is access all Integer;
I    : aliased Integer;
Zeiger : Ptr_Integer := I'Access;

Dangling pointers sind Zeiger, deren referenzierte Variable irgendwann nicht mehr existiert. Daher sollte die Lebensdauer des referenzierten Objekts mindestens so groß sein wie die des Zeigers.

Referenzkonzept

Interne Namen:  Jedes Objekt erhält in der Programmierung einen Namen, auch wenn dies nicht im Programmtext geschieht (z. B. implizite Typdeklaration bei Variablendeklaration). Im Programm ist es wichtig, dass alle Namen unterschieden werden können, da man sonst die Objekte nicht auseinander halten kann.

Konstanten im Speicher:  Bisher wurden Konstanten als Inhalte der Variablen aufgefasst. Diese Vorstellung kann modifizieren, indem man die normalen Variablen als „Zeiger auf Konstanten“ ansieht. Man nimmt dabei an, dass sich alle Konstanten im Speicher befinden und die Variablen nur noch Adressen enthalten, wo sich die Konstanten befinden. Eine Wertzuweisung bewirkt dann nur noch eine Änderung des Zeigers.

Referenzkonzept:  Jedes Objekt erhält eine Referenzstufe. Konstanten erhalten hierbei die Referenzstufe $0$, Variablen $1$ usw. Allgemein erhält ein Objekt, das auf Objekte der Referenzstufe $k$ verweist, die Referenzstufe $k+1$.

Bäume

Gerichteter Graph, Weg:  $G=(V,E)$ heißt gerichteter Graph/Digraph, falls $V$ eine nicht-leere endliche Menge ist (Knoten) und $E\subseteq V\times V$ (Kanten).
Eine Folge von Knoten $(u_1,\dots ,u_r)$ (mit $r\in \mathbb{N}$) heißt (gerichteter) Weg im Graphen $G$, falls $(u_i,u_{i+1})\in E$ für $i=1,\dots ,r-1$ gilt. $r-1$ ist die Länge des Weges.

Wurzel, Baum:  Ein Knoten $w$ heißt Wurzel eines Graphen $G$, falls es von $w$ zu jedem Knoten des Graphen einen Weg gibt und $w$ keinen direkten Vorgänger besitzt (s. u.).
Ein gerichteter Graph heißt Baum, falls er eine Wurzel $w$ besitzt und jeder Knoten außer der Wurzel genau einen direkten Vorgänger hat, d. h. für $x\in V$, $x\ne w$ gibt es genau ein $y\in V$ mit $(y,x)\in E$. $y$ heißt Vater/direkter Vorgänger. $x$ ist dann das Kind/direkter Nachfolger.
Ein Knoten ohne direkten Nachfolger heißt Blatt.
Ein Graph heißt Wald, wenn er sich als disjunkte Vereinigung von Bäumen schreiben lässt.
Ein Baum mit $n$ Knoten besitzt $n-1$ Kanten. Knoten mit gleichem Vater heißen Geschwister. Knoten, die auf dem Weg von der Wurzel $w$ zu einem Knoten $v$ liegen, heißen Vorgänger von $v$. Die Länge des längsten Wegs von der Wurzel $w$ zu einem Blatt ist die Tiefe/Höhe des Baums.
Jedem Knoten ist ebenfalls eindeutig ein Level/Niveau zugeordnet: $w$ hat den Level $0$, die direkten Nachfolger eines Knoten mit Level $k$ haben den Level $k+1$.

Rekursive Definition für Bäume:  Die leere Menge ist ein Baum. Wenn $w$ ein Knoten und $U$ eine endliche Menge von Bäumen sind, dann ist auch $w(U)$ ein Baum.
$w$ heißt Wurzel von $w(U)$, die Elemente von $U$ heißen Unterbäume. Sind die Unterbäume geordnet, so spricht man von einem geordneten Baum.

Binäre Bäume:  Die leere Menge ist ein binärer Baum. Wenn $w$ ein Knoten und $B_L$ sowie $B_R$ binäre Bäume sind, dann ist auch $w(B_L,B_R)$ ein binärer Baum.
$B_L$/$B_R$ heißen linker/rechter Unterbaum des Knotens $w$. Ein binärer Baum ist ein geordneter Baum, in dem jeder Knoten genau zwei (evtl. leere) Unterbäume hat.

Suchbaum:  Ein binärer Baum mit Knoten, die Werte eines geordneten Datentyps beinhalten, heißt Suchbaum, falls für jeden Knoten $u$ gilt: Alle Inhalte von Knoten im linken Unterbaum von $u$ sind echt kleiner als der Inhalt von $u$ und alle Inhalte von Knoten im rechten Unterbaum von $u$ sind größer/gleich dem Inhalt von $u$.

Durchlauf von binären Bäumen: 

procedure Inorder (b : Ref_BinBaum)
is begin
  if b /= null then
    Inorder (b.L);
    -- Knoten b bearbeiten
    Inorder (b.R);
  end if;
end Inorder;

-- Knoten b bearbeiten
Preorder (b.L);
Preorder (b.R);

Postorder (b.L);
Postorder (b.R);
-- Knoten b bearbeiten

Ist $n$ die Zahl der Knoten, so erfolgt der Durchlauf in $3n$ Schritten.
Im ungünstigsten Fall benötigt man $n$ Speicherplätze, im günstigsten proportional zu $\log n$.

Relationen und Graphen

Relation:  Seien $M,M_1\dots ,M_n$ Mengen. Eine Teilmenge $R\subseteq M_1\times \cdots \times M_n$ heißt $n$-stellige Korrespondenz. Eine Teilmenge $R\subseteq M^n$ heißt $n$-stellige Relation über $M$. Eine Teilmenge $R\subseteq M^2$ heißt (binäre) Relation über $M$. Für $(x,y)\in R$ schreibt man $xRy$.

Eigenschaften:  Sei $R\subseteq M\times M$ eine Relation. $R$ heißt reflexiv, falls ${\mathrm{\forall }}_{x\in M}xRx$. $R$ heißt irreflexiv, falls ${\mathrm{\forall }}_{x\in M}\mathrm{\neg }(xRx)$. $R$ heißt symmetrisch, falls ${\mathrm{\forall }}_{x,y\in M}(xRy\iff yRx)$. $R$ heißt antisymmetrisch, falls ${\mathrm{\forall }}_{x,y\in M}(xRy\wedge yRx\Rightarrow x=y)$. $R$ heißt transitiv, falls
${\mathrm{\forall }}_{x,y,z\in M}(xRy\wedge yRz\Rightarrow xRz)$. $R$ heißt alternativ, falls ${\mathrm{\forall }}_{x,y\in M}(xRy\vee yRx)$.

Relationsarten:  Eine reflexive, symmetrische und transitive Relation heißt Äquivalenzrelation. Eine reflexive, antisymmetrische und transitive Relation heißt Ordnung. Eine irreflexive, antisymmetrische und transitive Relation heißt echte Ordnung. Eine Ordnung heißt totale/lineare Ordnung, falls sie alternativ ist.

Gerichteter Graph:  $G=(V,E)$ heißt gerichteter Graph/Digraph, falls $V$ eine nicht-leere endliche Menge ist (Knoten) und $E\subseteq V\times V$ (Kanten).

Ungerichteter Graph:  $G=(V,E)$ heißt ungerichteter Graph, falls $V$ eine nicht-leere endliche Menge ist (Knoten) und $E\subseteq \{\{x,y\}|x,y\in V,x\ne v\}\cup \{\{x\}|x\in V\}$ (Kanten).

Umwandeln von Graphen:  Ist $G=(V,E)$ ein ungerichteter Graph, so ist der gerichtete Graph $G_{ger}=(V,E_{ger})$ mit $E_{ger}=\{(x,y),(y,x)|\{x,y\}\in E\}\cup \{(x,x)|\{x\}\in E\}$ die gerichtete Version des Graphen $G$.
Ist $G=(V,E)$ ein gerichteter Graph, so ist der ungerichtete Graph $G_{ung}=(V,E_{ung})$ mit $E_{ung}=\{\{x,y\}|(x,y)\in E\vee (y,x)\in E\}\cup \{\{x\}|(x,x)\in E\}$ die ungerichtete Version des Graphen $G$.   Ein gerichteter Graph $H$ heißt Orientierung/Ausrichtung des ungerichteten Graphen $G$, falls $G$ die ungerichtete Version von $H$ ist.

Teilgraph:  Ist $G=(V,E)$ ein Graph, so heißt ein Graph $G^{\prime }=(V^{\prime },E^{\prime })$ Teilgraph von $G$, falls $V^{\prime }\subseteq V$ und $E^{\prime }\subseteq E$.   $G^{\prime }=(V^{\prime },E^{\prime })$ heißt der von $V^{\prime }$ induzierte Teilgraph, falls im
ungerichteten Fall $E^{\prime }=\{\{x,y\}\in E|x,y\in V^{\prime }\}$ bzw. im gerichteten Fall
$E^{\prime }=\{(x,y)\in E|x,y\in V^{\prime }\}$.

Nachbarn:  Jede Kante $\{x,y\}$ bzw. $(x,y)$ heißt inzident zu ihren Knoten $x$ und $y$. Zwei Knoten $x,y$ mit $\{x,y\}\in E$ bzw. $(x,y)\in E$ (oder $(y,x)\in E$) heißen adjazent/benachbart.
Die Menge $N(x)=\{y\in V|\{x,y\}\in E\}$ bzw. $N(x)=\{y\in V|(x,y)\in E\vee (y,x)\in E\}$ heißt die Menge der (direkten) Nachbarn von $x$. Ist $G$ gerichtet, so heißt $S(x)=\{y\in V|(x,y)\in E\}$ bzw. $P(x)=\{y\in V|(y,x)\in E\}$ die Menge der (direkten) Nachfolger bzw. Vorgänger von $x$. Eine Kante $\{x\}$ bzw. $(x,x)$ heißt Schlinge.

Grad:  Ist $G$ ungerichtet, so heißt $d(x)=|N(x)\setminus \{x\}|$ ($+2$ für $\{x\}\in E$) der (Knoten-)Grad von $x$. Der maximale Knotengrad heißt Grad $d(G)$ des Graphen $G$.
Ist $G$ gerichtet, so heißen $d^{\mathbf{+}}(x)=|S(x)|$ Ausgangs- und $d^{\mathbf{-}}(x)=|P(x)|$ Eingangsgrad von $x$. $d(x)=d^{\mathbf{+}}(x)+d^{\mathbf{-}}(x)$ heißt (Knoten-)Grad von $x$.
Ein Graph heißt geordnet, falls für jeden Knoten $x$ die Menge der Nachbarn $N(x)$ (ungerichteter Fall) bzw. die Menge der Nachfolger $S(x)$ (gerichteter Fall) linear geordnet ist.

Adjazenzmatrix:  Sei $G=(V,E)$ mit $V=\{x_1,\dots ,x_n\}$ ein Graph. Die Adjazenzmatrix $A=(a_{ij})$ ist definiert durch $a_{ij}=1$ (ggf. Kantengewicht) falls $\{x_i,x_j\}\in E$ (ungerichtet) bzw. $(x_i,x_j)\in E$ (gerichtet) und $a_{ij}=0$ sonst ($1\le i,j\le n$).
Die erweiterte Adjazenzmatrix $A^{\prime }=(a_{ij}^{\prime })$ ist $a_{ij}^{\prime }=a_{ij}$ für $i\ne j$ und $a_{ij}=1$ für $i=j$.
($A^k$ gibt die Anzahl der verschiedenen Wege der Länge $k$ zwischen zwei Knoten an.)

Adjazenzliste:  Man erstellt eine Liste der Knoten (mit Inhalt und ID-Nummer). Jeder Knoten enthält wieder eine Liste der inzidenten Kanten, deren Einträge das Gewicht und einen Verweis auf den Endknoten enthalten.

Inzidenzliste:  Man erstellt jeweils eine (lineare) Liste der Knoten und eine Liste der Kanten.
Die Einträge der Kanten entalten zwei Verweise auf die zugehörigen Knoten.

Graphendurchlauf:  Ein Graphendurchlauf lässt sich durch Adjazenzlisten realisieren. Man kann alle Knoten nacheinander durchgehen und bei jedem Knoten die entsprechenden Kanten ablaufen, um den Algorithmus mit dem Zielknoten rekursiv aufzurufen.

Ungerichtete Wege und Pfade:  Eine Folge von Knoten $(u_1,\dots ,u_r)$ ($r\ge 1$) heißt Weg in $G$, falls $\{u_i,u_{i+1}\}\in E$ für $i=1,\dots ,r-1$. $r-1$ heißt die Länge des Weges. $u$ und $v$ heißen verbunden, falls es einen Weg von $u$ nach $v$ gibt. Der zugehörige Pfad des Wegs ist $(\{u_1,u_2\},\dots ,\{u_{r-1},u_r\})$.

Zusammenhang für ungerichtete Graphen:  Ein Weg heißt doppelpunktfrei/einfach, falls $u_i\ne u_j$ für $i\ne j$. Ein Weg heißt geschlossen, falls $u_r=u_1$. Ein Weg heißt Kreis/Zyklus, falls $r\ge 4$, der Weg geschlossen ist und $(u_1,\dots ,u_{r-1})$ einfach. Ein Graph heißt zyklenfrei/azyklisch, falls er keine Zyklen besitzt.
Ein Graph heißt zusammenhängend, falls jeder Knoten mit jedem Knoten verbunden ist.
$Z(u)=\{v\in V|u,v\text{ sind verbunden}\}$ heißt Zusammenhangskomponente des Knotens $u$.

Gerichtete Wege und Pfade:  Eine Folge von Knoten $(u_1,\dots ,u_r)$ ($r\ge 1$) heißt
(gerichteter) Weg in $G$, falls $(u_i,u_{i+1})\in E$ für $i=1,\dots ,r-1$. $r-1$ heißt die Länge des Weges. $u$ und $v$ heißen verbunden, falls es einen Weg von $u$ nach $v$ und von $v$ nach $u$ gibt. Der zugehörige Pfad des Wegs ist $((u_1,u_2),\dots ,(u_{r-1},u_r))$.

Zusammenhang für gerichtete Graphen:  Ein Weg heißt doppelpunktfrei/einfach, falls $u_i\ne u_j$ für $i\ne j$. Ein Weg heißt geschlossen, falls $u_r=u_1$. Ein Weg heißt Kreis/Zyklus, falls $r\ge 4$, der Weg geschlossen ist und $(u_1,\dots ,u_{r-1})$ einfach. Ein Graph heißt zyklenfrei/azyklisch, falls er keine Zyklen besitzt.
Ein Graph heißt stark zusammenhängend, falls jeder Knoten mit jedem Knoten verbunden ist. $Z(u)=\{v\in V|u,v\text{ sindverbunden}\}$ heißt starke Zusammenhangskomponente des Knotens $u$. $SwZ(u)=Z(u)\text{ in }{G}_{ung}$ heißt schwache Zusammenhangskomponente.

Transitive Hülle:  Zu einem gerichteten bzw. ungerichteten Graphen $G=(V,E)$ heißt der gerichtete bzw. ungerichtete Graph $G_{tH}=(V,E_{tH})$ mit
$E_{tH}=\{(x,y)|\text{es gibt einen Weg von }x\text{ nach }y\}$ bzw.
$E_{tH}=\{\{x,y\}|\text{es gibt einen Weg von }x\text{ nach }y\}$ die transitive Hülle des Graphen $G$.
Ein vollständiger Graph ist ein Graph, in dem zwei verschiedene Knoten durch nur eine Kante miteinander verbunden sind. Ein Graph, bei dem $n$ Knoten einen Ring bilden, heißt Kreis.