Datenstrukturen und Algorithmen
The Update
Vorwort
Obgleich die Demoszene als solche ihre Ursprünge nicht in der akademischen Informatik hat, bedient sie sich doch vieler Techniken, die die Demos, wie wir sie heute kennen, erst möglich gemacht haben. Um die Daten eines Programms geschickt zu verwalten, seien es einfache Bilder, 3D-Objekte oder ganze 3D-Level, die Samples eines MOD-Players oder Puffer eines modularen Software-Synthesizers, bedarf es eines soliden Grundwissens über die zur Verfügung stehenden Datenstrukturen. Die zu Grunde liegenden Anforderungen sind nicht einheitlich: Bei einem Bild kommt es nicht so sehr darauf an, einzelne Pixel hinzuzufügen oder wegzunehmen oder alle Pixel einer bestimmten Farbe zu finden, es geht viel mehr darum, möglichst schnell den kompletten Datenbestand in einem Rutsch zu verarbeiten. Hingegen ist es bei 3D Engines oft relevant, die Objekte zu bestimmen, die überhaupt sichtbar sind, und dann erst anzufangen, diese zu Rendern.
Dieser Artikel beschreibt die elementaren Datenstrukturen der Informatik zusammen mit den wichtigsten Klassen der Algorithmen: dem Suchen und dem Sortieren. Dabei werde ich nicht so sehr auf Details eingehen oder versuchen, alle Algorithmen einer Klasse vorzustellen, wer also z.B. besonders schnelle Sortieralgorithmen sucht, ist mit den zahlreichen Spezialtutorials besser bedient. Dieser Artikel richtet sich eher an all die, die Grundkenntnisse in der Programmierung mitbringen, aber eine strukturierte Einführung in die Welt der Datenstrukturen suchen. Die Beispiele sind in C++ geschrieben, sollten aber mit wenig Mühe in allen anderen Sprachen, die imperative Programmierung1] erlauben, analog zu implementieren sein. Der Code dient nur als Beispiel, weshalb ich sämtliche Sicherheitsabfragen weglasse.
Grundlagen in der Darstellung von Datentypen, auf die ich im folgenden zurückgreifen werde, sind im Artikel Datentypen von T$ nachzulesen.
Inhalt
Suchen
Anhang
Records, auch zusammengesetzte Datentypen genannt, sind im
Prinzip eine Ausnahme unter den hier vorgestellten Strukturen. Ein Record
dient nicht zur Speicherung vieler gleichförmiger Daten sondern zur logischen
Zusammenfassung verschiedener Datentypen. Vergleichbar ist das mit einem
Adressbuch: Jede einzelne Adresse setzt sich aus Name, Straße, Hausnummer,
Postleitzahl und Ort zusammen, also drei Strings und zwei Nummern. Das Buch an
sich besteht aber aus einer Vielzahl dieser logischen Einheiten, weshalb ich
hier auch auf diesen Typ eingehe. Ein Record fasst also zusammengehörige Daten zusammen, so dass
man sie als Einheit betrachten kann: Arrays sind oft die erste Datenstruktur, die man neben den
elementaren Datentypen kennenlernt. Sie brauchen keinen zusätzlichen
Speicherplatz für Verwaltungsinformationen, lassen sich einfach Anlegen
('new') und Löschen ('delete') und bieten den schnellstmöglichen Zugriff auf
Elemente bekannter Position ('x = array[ pos ];'). Allerdings sind sie völlig
unflexibel. Wer schon mal mit dem Gedanken gespielt hat, in ein Array in der
Mitte etwas einzufügen, der dürfte schnell bemerkt haben, dass er dazu zum
einen die bestehende Struktur vergrößern müßte, was oft einem kompletten
Neuanlegen und Umkopieren gleich kommt. Aber selbst wenn man am Ende noch
Platz für eventuelle Vergrößerungen gelassen hat, muss man alle Elemente von
der gewünschten neuen Position an ein Feld nach hinten verschieben, um den
Platz für das neue Element zu gewinnen. Abhilfe schaffen hier Listen. Listen bestehen aus Ketten, deren einzelne Glieder zum einen
die zu speichernden Datenelemente enthalten, zum anderen aber auch Verweise
auf das folgende und u.U. auf das vorherige Glied: [Daten01|Verweis]-->[Daten02|Verweis]-->[Daten03|Verweis] Dadurch ist es relativ einfach, Elemente einzufügen, da man
nur den Verweis des vorherigen Elementes auf das neue setzen muss, sowie dessen
Verweis auf das folgende: Das Löschen funktioniert analog, man setzt einfach den
Verweis des Vorgängers des zu löschenden Elements auf dessen Nachfolger. Diese Flexibilität erkauft man sich allerdings durch zwei
Nachteile: Man kann nicht mehr direkt auf das n-te Element zugreifen, da
dessen Position im Speicher nicht direkt bekannt ist. Wann immer man nicht
zufällig alle Elemente von Anfang bis Ende nacheinander abarbeiten möchte, muss
man sich immer vom Anfang der Kette bis zum gesuchten Element durchhangeln,
was natürlich entsprechend Rechenzeit kostet. Ein anderer Nachteil ist, dass
die Listendarstellung auch immer noch Speicherplatz für die Verweise braucht,
was bei kleinen Datensätzen, z.B. einfachen Integer-Werten, schon zu einer
Verdopplung des Bedarfs führt. Listen machen also immer dann Sinn, wenn man zum einen die
Möglichkeit braucht, Elemente problemlos einfügen und löschen zu können, zum
anderen aber die Elemente bei der Verarbeitung immer in der gegebenen
Reihenfolge benötigt. Eine einfache Liste lässt sich wie folgt aufbauen: MeineListe ist nun ein Verweis auf das erste Listenelement.
Auf diesem Verweis bauen sämtliche Listenoperationen auf. Operationen, die den
Anfang der Liste betreffen, arbeiten direkt auf MeineListe, alle
anderen nehmen es alS Startpunkt, um das zu modifizierende Element zu
finden. Anlegen des ersten Elements MeineListe = new Liste; Anfügen eines Elements an eine bestehende Liste Löschen eines Elements aus der Mitte Einfügen eines Elements in der Mitte Die weiteren denkbaren Operationen sind mit ein wenig Übung
leicht selbst zu implementieren, wie immer hilft das gedankliche Durchspielen
in Kombination mit Papier und Bleistift. Um den ersten Nachteil der Listen, das aufwendige Suchen
von bestimmten Elementen, zu umgehen, lassen sich diese zu Bäumen erweitern.
Bäume gleichen Listen, erlauben aber Verzweigungen. Ein Element hat nun nicht
immer einen Nachfolger, es können je nach Baumart auch zwei oder mehr sein.
Die einfachste Sorte ist hierbei die mit maximal zwei Nachfolgern, welche
dementsprechend Binärbaum genannt wird. Der Sinn ist, dass man bei jedem
Element direkt weiß, ob man in der einen oder in der anderen Richtung weiter
suchen muss. So kann man z.B. sagen: Links folgen nur Werte die kleiner sind
als der Wert des Elements, rechts folgen die größeren. Bei einem geschickt aufgebauten Baum kann man so mit jedem
Schritt die Anzahl der möglichen Elemente halbieren, während bei den Listen
die Anzahl immer um eins verringert wurde. Die Anzahl der Schritte, um einen
Baum mit 1024 Elementen zu durchsuchen ist somit maximal 10 (210 = 1024),
bei einer Liste sind es genau die 1024, was 100 mal länger dauert. Das Arbeiten mit einem Baum gestaltet sich aber etwas anders
als von Listen gewohnt. So muss man z.B. bei der gegebenen Vorschrift (links
kleiner, rechts größer) nicht unbedingt in der Mitte des Baumes Elemente
einfügen. Statt dessen hängt man sie einfach den Regeln folgend an's Ende. Ein
möglicher Aufbau sähe so aus: Die einzelnen Elemente eines Baumes heißen Knoten (engl:
Node), wobei der Anfangsknoten Wurzel (engl: Root) genannt wird. Hinzufügen eines Knotens Suchen eines Knotens Das Löschen von Knoten gestaltet sich etwas schwieriger. Ich
werde es in dieser kurzen Vorstellung nicht weiter behandeln, da es in vielen
einfachen Anwendungen auch nicht erforderlich ist. Nähere Erklärungen finden
sich in den Literaturhinweisen. Stacks als solche bezeichnen nicht direkt eine
Implementierung, so wie Listen, sondern ein Funktionsprinzip, welches sich auf
verschiedene Weise umsetzen lässt. Auf einem Stack kann man Daten ablegen.
Herunternehmen kann man immer nur das Element, welches man als letztes
hinzugefügt hat. Im wirklichen Leben bietet sich das Verfahren z.B. beim
Auseinandernehmen einer Playstation zwecks Einbau eines MOD-Chips an: Zuerst
entfernt man den Gehäusedeckel und legt ihn beiseite. Danach entnimmt man das
CD-Laufwerk, dann die metallische Abschirmung. Und in jedem Schritt fallen
noch ein paar Schrauben an. Wenn man das Ding wieder zusammensetzen möchte,
ist es ganz sinnvoll, das genau in umgekehrter Reihenfolge zu tun, und genau
dieses Problem taucht auch ab und an in der Programmierung auf, weshalb es den
Stack gibt. Ein Stack ist am einfachsten als Array zu implementieren. Man
merkt sich in einer zusätzlichen Variablen, welches das nächste freie Element
des Arrays ist, und speichert dann entweder dort den neuen Wert und
inkrementiert den Zähler bzw. dekrementiert ihn beim Auslesen und gibt dann
den vorhandenen Wert zurück. Natürlich bedarf es noch weiterer Abfragen um
sicherzustellen, dass nicht z.B. auf einen vollen Stack ein weiteres Element
abgelegt wird, aber im Prinzip reicht dieser Code für einen handelsüblichen
Stack aus. Queues sind Verwandte der Stacks, der Unterschied ist, dass
man bei ihnen nur das Element abrufen kann, das als erstes gespeichert wurde.
Sinn macht das beispielsweise in der Druckerwarteschlange, in die jedes
Programm hinten seine Druckaufträge einreiht und der Drucker sie dann in der
gegebenen Reihenfolge abarbeitet. Aber auch an allen anderen Stellen, an denen
eine Ein-/Ausgabe gepuffert wird, sei es bei der Übertragung von Daten zum
CD-Brenner oder den Windowsnachrichten zwischen OS und Applikation, kommen
Queues zum Einsatz. Sie ermöglichen, dass Schreib- und Lesezyklen nicht
synchron laufen müssen, wie es bei einer ungepufferten Übertragung der Fall
wäre, da die Daten so schon mal eine gewisse Zeit im Puffer verbleiben
können. Implementieren lässt sich ein Queue ganz analog zum Stack: Zu beachten ist allerdings, dass man hier noch zusätzliche
Abfragen braucht, um den Queue als Ring nutzen zu können. Schließlich will man
ja nicht nach 1000 Einträgen einen neuen Queue anlegen, obwohl davon schon 500
schon wieder ausgelesen wurde, also die ersten 500 Einträge wieder frei sind.
Hier bietet es sich an, ein Ende %= 1000 einzufügen. Wenn man die Implementierung einer Datenstruktur außer Acht
lässt und die Sicht nur auf die Funktionalität beschränkt, erhält man einen
abstrakten Datentyp. So kann man z.B. zuerst spezifizieren, was die
Datenstruktur ermöglichen soll (Element hinzufügen, Element auslesen, Element
suchen) und darauf das weitere Programm aufbauen. Die Implementierung kann
sich dann problemlos von Version zu Version ändern, ohne dass man die Teile des
Programms, die auf die Datenstruktur zugreifen, ändern muss. Dieses Konzept
manifestiert sich zum einen in der traditionellen Trennung von C-Header und
-Quellcode (bzw. Interface/Implementation in Pascal), zum anderen aber auch in
den sogenannten Containern in C++. Eine Spezifikation für einen Stack sähe dann z.B. so aus: Im nächsten Schritt erstellt man dann die passenden
Funktionen: Bis dahin wurde noch nicht festgelegt, um was es sich bei dem
Stack eigentlich handelt, nur, was er kann. Die Implementierung kann man nun
analog zur oben genannten schreiben: Obgleich die Technik des ADT elementar für die rein
imperativen Sprachen ist, sollte jeder, der objektorientiert arbeitet, von der
Verwendung dieser Art ADT absehen. Die Klasse ist das logische Äquivalent zum
ADT, weshalb der Stack in C++ als solche umgesetzt werden sollte: Man sieht leicht, dass die durch die Sprache ermöglichte
Zusammenfassung von Daten und Methoden eine sauberere Schreibweise ermöglicht,
in der umständliches Casten praktisch überflüssig wird. Die Idee, die dahinter
steckt, ist jedoch die gleiche. Auch hier kann man die Klasse nach Belieben
neu implementieren, ohne dass der Rest des Programms (oder des
Programmier-Teams) etwas davon mitbekommt. Da die Umsetzung der ADT nun recht komplex ist, aber in
gleichem Maße sprachspezifisch, möchte ich an dieser Stelle nicht näher darauf
eingehen. C++-Programmierern sei aber geraten, sich mit den Begriffen Template
und Container vertraut zu machen. Allgemeine Sortieralgorithmen kann man grob in zwei
Kategorien einteilen: Die einfachen und die fortgeschrittenen. Einfache
Sortieralgorithmen sind leicht zu verstehen, in wenigen Codezeilen zu
implementieren und dadurch bei kleinen Mengen (10 bis 20 Einträge) auch durchaus
sinnvoll. Allerdings beträgt ihr Aufwand im Schnitt n2. Das heißt, dass sich
die Anzahl der Schritte, die sie benötigen, bis die Menge sortiert ist, sich
für für die doppelte Anzahl Elemente vervierfacht. Fortgeschrittenere Sortieralgorithmen sind meist etwas
komplizierter, haben aber den Vorteil, dass sie bei größeren Mengen weitaus
schneller sind, da sie nur einen Aufwand von n * log(n) haben, d.h. bei einer
verdoppelten Anzahl Elemente benötigen sie nur wenig mehr als doppelt so viele
Schritte, welche allerdings einzeln betrachtet mehr Rechenzeit benötigen als
die der einfachen Verfahren. Bei einigen hundert zu sortierenden Elementen ist
der Unterschied aber schon mehr als deutlich. Zu beachten ist, dass es sich bei immer um den
durchschnittlichen Aufwand handelt, also den bei einer zufälligen Menge. Ist
die Menge z.B. schon praktisch sortiert und nur das letzte Element steht an
der falschen Stelle, so sind einfache Verfahren oft die bessere Variante, da
sie diese Eigenschaften leicht ausnutzen können. Auf der anderen Seite kann
man sie genauso austricksen, in dem man die Menge z.B. absteigend sortiert,
was bei einigen einfachen Verfahren zu einer weitaus längeren Laufzeit
führt. Insertionsort zählt zu den einfachen Verfahren. Hierbei
unterteilt man die Menge in einen sortierten und einen unsortierten Abschnitt.
Zu Anfang besteht der sortierte Abschnitt nur aus einem einzigen Element, dem
ersten Element der Gesamtmenge. In jedem Schritt wird nun das erste Element
aus der unsortierten Menge genommen und an die richtige Stelle im bereits
sortierten Abschnitt eingefügt. Ein Beispiel: Man sieht leicht, dass die sortierten Elemente dabei oft
verschoben werden müssen, um Platz für die neu eingefügten zu machen. Um genau
zu sein, muss für jedes der n Elemente im Schnitt die Hälfte der schon
sortierten Elemente verschoben werden, also n/4. Zusammen ergibt das einen
Aufwand von n2/4. (2500 für n=100) Und als Quellcode: Mergesort ist ein gutes Lehrbeispiel für fortgeschrittene
Sortierverfahren, da es im Gegensatz zu beispielsweise Quicksort gut
nachvollziehbar ist. Bei Mergesort wird die Ausgangsmenge zunächst immer
weiter rekursiv in Hälften zerteilt, bis man nur noch einzelne Elemente hat.
An dieser Stelle stoppt die Rekursion, um auf dem Rückweg die einzelnen
Untermengen zusammenzufügen. Dabei hat man ja jedesmal zwei Teile, die für
sich sortiert sind, weshalb man immer nur die ersten Elemente der beiden Teile
betrachten muss. Das kleiner übernimmt man in die sortierte Menge, entfernt sie
in dem Teil, aus dem man sie entnommen hat und wiederholt das so lange, bis
die beiden Teile leer sind. Die Beispielmenge von oben wird dann so sortiert Da die Rekursion die Mengen halbiert, endet sie nach
ld(n)2] Schritten. In jedem Schritt werden alle n
Elemente bewegt, weshalb der Gesamtaufwand n*ld(n) beträgt. (~665 für
n=100) Das Suchen ist eine sehr datenstrukturspezifische
Angelegenheit. Die bereits vorgestellen Bäume sind geradezu darauf optimiert,
eine effiziente Suche zu ermöglichen, die Listen hingegen lassen sich
ausschließlich linear, d.h. Element für Element, durchsuchen. Dazwischen gibt
es aber noch zwei weitere Varianten, die auf Arrays aufbauen. Dieses Verfahren ist die logische Konsequenz auf der linearen
Suche. In einer sortierten Menge bietet es sich an, zuerst mal das mittlere
Element zu prüfen. Wenn dies größer als das gesuchte ist, kann man seine Suche
direkt auf die erste Hälfte einschränken und dort wieder halbieren, so lange,
bis man entweder das gewünschte Element gefunden hat oder aber der zu
durchsuchende Bereich auf Null schrumpft, was bedeutet, dass das Element gar
nicht vorhanden ist. Hashing geht die Suche von einer ganz anderen Seite an. Jedem
Element wird ein Schlüssel zugeordnet, anhand dessen die Position im Speicher
bestimmt wird. Am einfachsten wird das an einem Beispiel deutlich: Man legt
sich eine Datenbank an, die die Rückwärtssuche von den Telefonnummern des
eigenen Adressbuches erlaubt, so dass man eingehende Anrufe direkt den Namen
zuordnen kann. Der einfachste Ansatz wäre nun, ein Array anzulegen, was so
jeder möglichen Telefonnummer einen Namen zuordnet: GesuchterName = Namen[ Telefonnummer ]; Jetzt kann man in einem einzigen Schritt den richtigen Namen
finden, langwierige Suchen werden überflüssig. Bei im Schnitt 4 Stellen
Vorwahl (die führende Null kann man ja weglassen) und 6 Stellen Rufnummer
wären das aber 10 Stellen oder 10 Milliarden Einträge, was selbst bei Namen,
die nur ein Zeichen lang sind, 10 GB Speicher erforderte. Da man aber nur
vielleicht 100 Nummern speichern möchte, braucht man einen geeigneteren
Schlüssel. Die Konsequenz ist dann, z.B. nur die letzten drei Stellen der
Telefonnummer zu betrachten: GesuchterName = Namen[ Telefonnummer % 1000 ]; Jetzt braucht man nur noch ein Array mit 1000 Einträgen, hat
allerdings ein Problem: Wenn mehrere Telefonnummern die gleichen drei letzten
Stellen haben, landen sie auf dem gleichen Speicherplatz. Abhilfe schafft hier
das sogenannte offene Hashing. Dabei nimmt man kein Array aus Namen sondern
eines aus Listen. So bestimmt man zuerst über Hashing die richtige Liste und
muß dann nur noch in dieser den richtigen Eintrag finden. Da man via Hashing
die Suche aber schon sehr gut eingrenzen kann, ist der Aufwand, die Liste zu
durchsuchen, oft gering. Liste = NamensListen[ Telefonnummer % 1000 ]; Jetzt sollte auch klar sein, warum man am besten die letzten
und nicht die ersten drei Stellen der Telefonnummer nimmt: Wenn man z.B. in
Köln wohnt und die Hälfte der Einträge aus der eigenen Stadt kommen, beginnen
50 von 100 Nummern mit 221, landen also in der gleichen Liste. Nimmt man
hingegen die letzten drei Stellen, erhält man eine weitaus zufälligere
Verteilung, was die Listen verkürzt und die Suche beschleunigt. Hashing steht und fällt mit dem Algorithmus, der die
Schlüsselwerte berechnet. Wenn man an dieser Stelle nicht aufpasst, bleibt man
leicht auf dem Niveau einer einfachen linearen Liste. Findet man aber eine
Möglichkeit zur gleichmäßigen Verteilung, ist es die schnellste denkbare
Suche, da man das Ergebnis nach ein, zwei Schritten erhält. Wie man nun am
besten die Schlüssel berechnet hängt immer von den Ausgangsdaten ab, ein
totsicheres Konzept gibt es nicht. Oft ist ein Pseudo-Zufallszahlen-Generator
eine gute Ausgangsbasis: int a = 5; Dabei erzielt man mit Primzahlen die besten Ergebnisse, nur
sollten a und b in der gleichen Größenordnung wie m liegen. Je nachdem, wie
viel Speicher man hat und wie schnell man das Ergebnis braucht, sollte man
zusehen, dass m irgendwo im Bereich von n bis 3*n liegt, wenn n die Anzahl der
Einträge ist. Das ist natürlich auch nur eine Faustregel, Ausprobieren wirkt
Wunder. Abschließend sei noch darauf hingewisen, dass es auch das
sogenannte geschlossene Hashing gibt. Der Unterschied ist, dass man die
Elemente mit dem gleichen Schlüssel nicht in lineare Listen packt sondern für
ein Element, was an einer schon belegten Position gespeichert werden soll,
eine Ersatzposition sucht, z.B. die nächste freie im Array. Als Basis dieses Artikels diente eine
Vorlesungsmitschrift
zu "Algorithmen und Datenstrukturen" SS 2000 an der RWTH Aachen bei Prof. Ney
von Maximilian Bisani, Jörg Dahmen, Wolfgang Macherey und Sonja Nießen. Aus
dieser stammen auch die folgenden Literatur-Tipps. 2] ld(n) ist der "Logarithmus Dualis", also der
Logarithmus zur Basis 2. Eine ausführliche Darstellung findet sich im Artikel
Datentypen von T$.
The Update/CoPro
struct Adresse
{
string Name;
string Straße;
int Hausnummer;
int PLZ;
string Ort;
};
// Adress-Variable anlegen
Adresse MeineAdresse;
// Auf die Bestandteile zugreifen
MeineAdresse.PLZ = 52062;
1) [Daten01|Verweis]------------------------>[Daten02|Verweis]
[Daten03|Verweis]
2) [Daten01|Verweis]- ->[Daten02|Verweis]
\ /
->[Daten03|Verweis]-
struct Liste
{
int Wert;
Liste* Next;
};
Liste* MeineListe;
MeineListe->Next = NULL;
// Hilfs-Zeiger 'Element'
Liste* Element = MeineListe;
// Suche Listen-Ende
while( Element->Next != NULL )
Element = Element->Next;
// Füge Element an
Element->Next = new Liste;
Element->Next->Next = NULL;
// Hilfs-Zeiger 'Element'
Liste* Element = MeineListe;
// suche Vorgänger des zu löschenden Elements
while( Element->Next->Wert != GesuchterWert )
Element = Element->Next;
// Hilfs-Zeiger 'Next'
Liste* Next = Element->Next;
// Entferne Element aus der Liste
Element->Next = Element->Next->Next;
// Entferne gelöschtes Element aus dem Speicher
delete Next;
// Hilfs-Zeiger 'Element'
Liste* Element = MeineListe;
// suche Einfüge-Stelle (zukünfigen Vorgänger)
while( Element->Next->Wert != GesuchterWert )
Element = Element->Next;
// Hilfs-Zeiger 'Neu'
Liste* Neu = new Liste;
// Füge Element in die Liste ein
Neu->Next = Element->Next->Next;
Element->Next = Neu;
[ 10 ]
/ \
[ 5 ] [ 20 ]
/ \
[ 2 ] [ 9 ]
struct Knoten
{
int Wert;
Knoten* Links;
Knoten* Rechts;
};
Knoten* Wurzel;
void Hinzufuegen( Knoten* knoten, int Wert )
{
if( Wert < knoten->Wert ) // links
{
if( knoten->Links == NULL ) // Blatt erreicht
{
// neuen Knoten erzeugen
knoten->Links = new Knoten;
// Knoten initialisieren
knoten = knoten->Links;
knoten->Links = NULL;
knoten->Rechts = NULL;
knoten->Wert = Wert;
}
else
{
// rekursiv das passende Blatt suchen
Hinzufuegen( knoten->Links, Wert );
}
}
else // rechts
{
// analog zu links
}
}
bool Suchen( Knoten* knoten, int Wert )
{
if( knoten == NULL )
{
// Ende erreicht, ohne den Wert zu finden
return false;
}
else
{
if( Wert == knoten->Wert ) // Wert gefunden
{
return true;
}
else if( Wert < knoten->Wert ) // links suchen
{
return Suchen( knoten->Links, Wert );
}
else // rechts suchen
{
return Suchen( knoten->Rechts, Wert );
}
}
}
int Stack[1000];
int Position;
void Speichern( int Wert )
{
Stack[ Position ] = Wert;
Position++;
}
int Laden()
{
Position--;
return Stack[ Position ];
}
int Queue[ 1000 ];
int Anfang;
int Ende;
void Speichern( int Wert )
{
Queue[ Ende ] = Wert;
Ende++;
}
int Laden()
{
Anfang++;
return Queue[ Anfang ];
}
Elemente : x
Stack : s
Element dem Stack hinzufügen : Push( s, x );
Element vom Stack holen : x = Pop( s );
Stack initialisieren : Init( s );
// Header [stack.h]
// benutze Elemente vom Typ INT
typedef int Element;
// der konkrete Datentyp des Stacks ist irrelevant
typedef void* Stack;
void Push( Stack s, Element x );
Element Pop( Stack s );
// Sourcecode [stack.c]
// Beschreibe das Aussehen des Stacks
struct StackStruct
{
Element Array[ 1000 ];
int Position;
};
void Push( Stack s, Element x )
{
((StackStruct*) s)->Array[ ((StackStruct*) s)->Position ] = x;
Position++;
}
// Header [stack.h]
typedef int Element;
class Stack
{
public:
void Push( Element x );
Element Pop();
protected:
Element Array;
int Position;
}
// Sourcecode [stack.cpp]
void Stack::Push( Element x )
{
Array[ Position ] = x;
Position++;
}
unsortierte Menge
[8 3 1 0 2 9 4 5]
Initialisierung
sortiert : [8]
unsortiert: [3 1 0 2 9 4 5]
Schritte
[3 8] [1 0 2 9 4 5]
[1 3 8] [0 2 9 4 5]
[0 1 3 8] [2 9 4 5]
[0 1 2 3 8] [9 4 5]
[0 1 2 3 8 9] [4 5]
[0 1 2 3 4 8 9] [5]
[0 1 2 3 4 8 9 5]
void InsertionSort( int* Menge, int Anzahl )
{
for( int i=0; i < Anzahl; i++ )
{
// wähle nächstes Element
int Element = Menge[ i ];
// Suche Einfüge-Position;
for( int j=0; ( Menge[ j ] < Element ) && j < i; j++ );
// folgende Elemente verschieben
for( int k=i; k > j; k-- )
Menge[ k ] = Menge[ k-1 ];
// Element einfügen
Menge[ j ] = Element;
}
}
unsortierte Menge
[8 3 1 0 2 9 4 5]
Aufteilen
[8 3 1 0 2 9 4 5]
[8 3 1 0] [2 9 4 5]
[8 3] [1 0] [2 9] [4 5]
[8] [3] [1] [0] [2] [9] [4] [5]
Zusammensetzen
[3 8] [0 1] [2 9] [4 5]
[0 1 3 8] [2 4 5 9]
[0 1 2 3 4 5 8 9]
void MergeSort( int* Menge, int Anzahl )
{
// weiter aufteilen
if( Anzahl > 1 )
{
// bestimme die beiden Hälften
int AnzahlLinks = Anzahl / 2;
int AnzahlRechts = Anzahl - AnzahlLinks;
// rekursiver Aufruf
MergeSort( Menge, AnzahlLinks );
MergeSort( Menge + AnzahlLinks, AnzahlRechts );
// füge sie zusammen
int l=0; // Counter für Links
int r=AnzahlRechts; // Counter für Rechts
int i=0; // Counter für die Zielmenge
int* ZielMenge = new int[ Anzahl ];
// vermische Teilmengen
while( i < Anzahl )
{
// nimm das Element von links wenn...
// a) nur noch links welche sind
// b) das linke kleiner ist
if( ( l < AnzahlLinks ) &&
( ( r >= Anzahl ) || ( Menge[ l ] < Menge[ r ] ) ) )
{
ZielMenge[ i ] = Menge[ l ];
l++;
}
else
{
ZielMenge[ i ] = Menge[ r ];
r++;
}
i++;
}
// schreibe Zielmenge zurück
for( i=0; i < Anzahl; i++ )
Menge[ i ] = ZielMenge[ i ];
}
}
SucheInListe( Liste, Telefonnummer );
int b = 17;
int m = 23;
Liste = NamensListen[ ( a * Telefonnummer + c ) % m ];
SucheInListe( Liste, Telefonnummer );