Modul 1: Algorithmen und DatenstrukturenWir lernen die Methoden und Konzepte kennen, die später für eine systematische Entwicklung von Software nötig sind. 1 Algorithmen 32 1.1

IK 1 Algorithmen & Datenstrukturen

29

Modul 1:Algorithmen und Datenstrukturen

„The hardware was the easy part.“

Lernziele

Algorithmen und Datenstrukturen gehören zu den klassischen Themen derInformatik und sind unerlässlich zur erfolgreichen Analyse, zum Entwurfund zur Implementierung (Umsetzung) eines Software-Systems. AmAnfang stehen dabei typische Lösungsstrategien, Standardalgorithmen undstrukturierte Datentypen. Wir lernen die Methoden und Konzepte kennen,die später für eine systematische Entwicklung von Software nötig sind.

1 Algorithmen 321.1 Definition: Was ist ein Algorithmus? 321.2 Beispiele für Algorithmen 321.3 Eigenschaften eines Algorithmus 331.4 Vom Problem zum Programm 331.5 Modellierung 35

Seymour Cray, Supercomputer Designer, 1925–1996 [W1]

Lösungsstrategien

Standard-algorithmen

Datentypen

IK_1_Datenstrukturen.fm Seite 29 Montag, 30. Dezember 2002 10:35 10


30

1.6 Modellierungs-Notationen 361.6.1 Pseudo-Code-Notation 361.6.2 Programmablaufplan (PAP) 381.6.3 Struktogramme 40

1.7 Daten- und Funktionsmodellierungsmodelle 431.8 Kontrollelemente von Algorithmen 45

1.8.1 Elementare Operation (Verarbeitung) 461.8.2 Sequenz (Folge) 461.8.3 Auswahl (Selektion) 461.8.4 Wiederholung (Schleife) 47

2 Datentypen und Datenstrukturen 482.1 Der Begriff Datenstruktur 482.2 Der Begriff Datentyp 482.3 Syntaxdiagramme 502.4 Variable und Konstante 51

2.4.1 Variable 512.4.2 Konstante 53

2.5 Idealisierte Datentypen 542.6 Konkrete Datentypen 54

2.6.1 Einfache Datentypen 542.6.1.1 Ordinale Datentypen 542.6.1.2 Datentyp BOOLEAN 552.6.1.3 Datentyp INTEGER 552.6.1.4 Datentyp CHAR 552.6.1.5 Aufzählungstyp 56

2.6.2 Datentyp REAL 562.6.3 Strukturierte Datentypen 57

2.6.3.1 Mengen 572.6.3.2 Arrays 572.6.3.3 Listen 582.6.3.4 Matrizen 592.6.3.5 Tabellen und Relationen 602.6.3.6 Bäume und Graphen 602.6.3.7 Files 642.6.3.8 Programme 642.6.3.9 Objekte, Klassen und Methoden 64

2.7 Abstrakte Datentypen 653 Beispielalgorithmen 67

3.1 Sortieralgorithmen 673.1.1 Bubblesort 673.1.2 Selection Sort 683.1.3 Quicksort 693.1.4 Insertion Sort 693.1.5 Shell Sort 703.1.6 Heapsort 70

3.2 Suchalgorithmen 713.2.1 Lineare Suche 723.2.2 Binäre Suche 723.2.3 Suche auf einem binären Baum 73

4 Modulkurzzusammenfassung 745 Modulanhang 75

5.1 Literatur 755.1.1 Bücher 755.1.2 Artikel 765.1.3 Books in English 765.1.4 Articles in English 775.1.5 Journals 78

5.2 Internet-Links 785.3 Prüfungsfragen 785.4 Lösungen 795.5 Übungen 805.6 Diskussionsfragen 805.7 Timeline: Algorithmen und Datenstrukturen 805.8 Glossar 81



31

Algorithmen und Datenstrukturen sind als „einigendes Konzept“ so zentralfür die gesamte Informatik, dass sie am Anfang jeder Beschäftigung mitInformatik stehen.

Algorithmen und Datenstrukturen gehören nahezu untrennbarzusammen, deshalb tauchen auch überall wo über Algorithmengesprochen wird, die Begriffe der Datenstrukturen auf.

Ein Ziel der Informatik ist Analyse, Entwurf und die Implementierung(Umsetzung, Realisierung, Ausprogrammierung) von Software-Systemen.Die Wirklichkeit wird dabei in Modelle abgebildet. Dazu werden sowohlAlgorithmen als auch Daten benötigt (Bild 1.1):

Ziel: Analyse, Entwurf und Implementierung

eines Software-Systems

Algorithmen(Konzepte, Bedeutung,

Konstruktion, Korrektheit)

Daten(Datentypen, Datenabstraktion, Schnittstellen, Datenstrukturen)

Abstraktion (Allgemeine Gesetze, Zusammenhänge,

Begriffsbildung, Modellbildung)

Ziel: Analyse, Entwurf und Implementierung

eines Software-Systems

Algorithmen(Konzepte, Bedeutung,

Konstruktion, Korrektheit)

Daten(Datentypen, Datenabstraktion, Schnittstellen, Datenstrukturen)

Abstraktion (Allgemeine Gesetze, Zusammenhänge,

Begriffsbildung, Modellbildung)

Bild 1.1 Algorithmen und Daten stehen zentral



32

1 Algorithmen

1.1 Definition: Was ist ein Algorithmus?

Der Begriff Algorithmus geht etwa auf das Jahr 825 und den Araber ABU DSHAFAR

MUHAMMED IBN MUSA AL-KHWARIZIMI zurück. Er schrieb ein Lehrbuch über dieÜbertragung von Gliedern einer Gleichung von einer zur anderern Seite mit dem Titel:„Kitab al jabr w’almuqabalah“. Daraus leitete sich der Begriff Algebra ab. Aus demNamen des Autors wurde algorism und daraus Algorithmus (Mehrzahl: Algorithmen).

Ein Algorithmus ist eine Verarbeitungsvorschrift.

Nach BALZERT (1999) ist ein Algorithmus eine eindeutige, endlicheBeschreibung eines allgemeinen, endlichen Verfahrens zur schrittweisenErmittlung gesuchter Größen aus gegebenen Größen. Die Beschreibungerfolgt in einem Formalismus mit Hilfe von anderen Algorithmen undletztlich elementaren Algorithmen. Ein Algorithmus muss ausführbar sein.

Ein Algorithmus dient zur Lösung allgemeiner Probleme –nicht nur zur Lösung eines speziellen Problems!

1.2 Beispiele für Algorithmen

Achtung: Was ist ein Algorithmus und was nicht? Beispiel: Ein bestimmtesModellflugzeug zu bauen ist ein Prozess. Aber eine allgemeine Anleitungzum Bau von Modellflugzeugen (nicht nur eines bestimmten Flugzeugtyps)ist ein Algorithmus. Es muss streng unterschieden werden zwischen Prozessund Algorithmus (Bild 1.3). Die einzelnen Schritte des Algorithmus könnenvon einer Maschine abgearbeitet werden. In einem Computer-System stelltdiese „Maschine“ der Prozessor dar (siehe Band 1, Modul 2).

Bild 1.2 Eine Briefmarke aus dem Jahr 1983 ist dem „Namensgeber“ des Algorithmus gewid-met [W2, W3]

Bild 1.3 Prozesse und Algorithmen



33

1.3 Eigenschaften eines Algorithmus

Welche Eigenschaften muss ein Verfahren (bzw. Prozess) haben, um alsAlgorithmus im Sinne der Informatik gelten zu können?

Viele Verfahren im Alltag kommen dem Grundgedanken eines Algorithmus schon sehrnahe. Allerdings sind oft die wesentlichen Eigenschaften eines „echten“ Algorithmus nochnicht vorhanden.

Damit ein Verfahren als Algorithmus gelten kann, müssen folgende vierEigenschaften vorhanden sein:

• Diskretheit: Der Algorithmus besteht aus einer Folge von Schritten.• Determiniertheit: Bei gleichen Startbedingungen (Anfangs- und Rand-

bedingungen) wird stets dasselbe Endergebnis erhalten. • Eindeutigkeit: Nach jedem Schritt lässt sich der Algorithmus auf

höchstens eine Art fortsetzen.• Endlichkeit: Der Algorithmus endet nach endlich vielen Schritten.

Oft werden bestimmte Werte bewusst nicht definiert, um den Algorithmusfür verschiedene Anwendungsfälle „universell“ anwenden zu können. DieseWerte werden dann als Parameter bezeichnet.

1.4 Vom Problem zum Programm

In der Informatik steht am Anfang eine Aufgabenstellung, ein Problem. DieEntwicklung eines allgemeinen Planes (Algorithmus) zur Problemlösungnennen wir Algorithmierung.

Die präzise Formulierung eines Algorithmus in einer für Computersystemeinterpretierbaren Sprache (Programmiersprache) heißt Programmierung.

Vom Problem über den Algorithmus zum Programm kommen wir durcheine analytische Vorgehensweise:

• Problem formulieren,• Problemanalyse, Problemabstraktion, Problemspezifikation,• Algorithmenentwurf,• Nachweis der Korrektheit, Verifikation,• Aufwandsanalyse,• Programmierung (Implementierung).

Die Implementierung (Ausprogrammierung) eines Software-Systems ist der letzte (und oft kleinste) Teil einer Entwicklung!

Algorithmierung

Programmierung

Analytisches Vorgehen



34

Das folgende Bild veranschaulicht diesen Prozess:

Führen wir nun Menschen (people), Prozessschritte (tasks) und Resultate(deliveries) ein, dann ergibt sich das folgende Bild:

Wir werden den Softwareentwicklungsprozess im Modul 6: Softwaretechnik& Systementwicklung noch genau besprechen. Hier konzentrieren wir unsauf die theoretischen Grundlagen.

Bild 1.4 Die „reale Welt“ wird in der Sprache der Informatik mit Hilfe der Informationstechnik (siehe Band 1) „abgebildet“

Bild 1.5 So wird in der Informatik gearbeitet; dieses streng systemati-sche und strukturierte Vorgehen ist vielen am Anfang fremd ...



35

1.5 Modellierung

Ausgehend von der Auffassung der Informatik als die Wissenschaft von der(maschinellen) Informationsverarbeitung liegt ein Schwerpunkt besondersin der Analyse, Entwurf und Konstruktion von Informationssystemen (IS).

Da es sich bei den Problemstellungen, die von der Informatikgelöst werden sollen, oft um hochkomplexe Probleme handelt,ist systematisches und analytisches Vorgehen unerlässlich.

Eine Möglichkeit ist die Modellierung eines realen Systems (aus dem „reallife“) mit Hilfe eines abstrakten Modells. Die eigentliche Problemlösungerfolgt dann in diesem Modell.

Das folgende Bild zeigt diesen Vorgang sehr anschaulich:

Modelle können oft sehr abstrakt sein (z.B. mathematische Darstellungendurch Graphen) oder sehr nahe an der Wirklichkeit sein (top-level-view).Letztere sollen Sachverhalte veranschaulichen, um eine Aufgliederung inTeilproblemstellungen zu ermöglichen.

Im Software-Engineering (siehe Modul 6) werden meistens drei Modelleunterschieden:

• Funktionsmodell,• Datenmodell und• Benutzermodell.

Bild 1.6 Problemlösung durch Modellbildung



36

1.6 Modellierungs-Notationen

Algorithmen lassen sich auf verschiedene Weise darstellen (visualisieren,modellieren). Eine Darstellung durch Symbole bzw. vereinbarte Zeichenwird Notation (aus lat. notatio = „Beschreibung“) genannt.

Selbstverständlich kann ein Algorithmus in natürlicher Sprache dargestelltwerden. Das kann in einer Aufzählung der Befehle (wie in den Beispielen inden nachfolgenden Kapiteln) erfolgen. Zur Vereinfachung und um dieBeschreibung eindeutig zu gestalten kann die sprachliche Beschreibungformalisiert werden, z.B.:

WENN „x größer als 0“ DANN „berechne Y“ SONST „tu nichts“.

Darstellung (Modellierung) und Beschreibung (Dokumentierung) vonAlgorithmen gehören zur Programmdokumentation.

Eine gute Programmdokumentation ist eine notwendige Voraussetzung zurEntwicklung und vor allem zur Wartung hochwertiger Programme.

Einige Möglichkeiten, komplexe Abläufe zu modellieren, sind:

• Pseudo-Code-Notation,• Programmablaufplan (PAP, Flussdiagramm),• Struktogramm und• Daten- und Funktionsmodellierungsmodelle (z.B. ERM, SADT, UML).

1.6.1 Pseudo-Code-Notation

Pseudo-Code ist eine textuelle und semiformale Darstellung von Kontroll-strukturen (siehe Kapitel 1.8) in Anlehnung an problemorientierte Program-miersprachen (siehe Modul 2).

Pseudo-Code stellt unabhängig von der (später) verwendetenProgrammiersprache die logische Struktur eines Programms dar.

Die drei Hauptelemente von Pseudo-Code, die in ihrer Syntax ursprünglichder Programmiersprache Pascal (siehe Modul 2) entliehen sind, heißen:

• Sequenz, • Wiederholung und • Auswahl.

Notation = Schreibweise



37

Eine Sequenz beschreibt eine Abfolge von Programmanweisungen, die inder vorgegebenen Reihenfolge von oben nach unten abgearbeitet werden.

Eine Wiederholung ist ein Anweisungsteil, der aufgrund einer eindeutigenBedingung eine bestimmte Anzahl N durchlaufen wird.

Eine Auswahl stellt eine Verzweigung aufgrund einer eindeutigen Bedin-gung innerhalb des Programmes dar. Je nach dem Ergebnis der Bedingungwird entweder der erste Block oder der zweite Block der Programmanwei-sungen ausgeführt.

Beispiel:

Einige Vorteile von Pseudocode:

• Schnell, einfach und jederzeit anzuwenden.• Schrittweise Verfeinerung kann durchgeführt werden.• Spezifikationen sind leicht nachvollziehbar.

Einige Nachteile von Pseudocode:

• Es existieren keine expliziten Regeln.• Gefahr einer zu frühen Detaillierung.• Sehr rasch Verlust der Übersichtlichkeit.

Bild 1.7 Drei Pseudo-Code-Elemente, ursprünglich der Programmiersprache Pascal entlehnt

Bild 1.8 Ein Beispiel für eine Modellierung in Pseudo-Code. Das Prin-zip dabei ist: „Wenn Be-dingung erfüllt, dann tue {Anweisungsblock}, sonst tue {Anweisungsblock}“

Ansätze zur Standardisierung von Pseudocode, siehe z.B. [W4]



38

1.6.2 Programmablaufplan (PAP)

Mit steigender Komplexität der Anforderungen wird es unmöglich, direktvon der Problemstellung zu einem lauffähigen Programm zu kommen.

Zuallererst muss eine logische Struktur in die zu lösendeProblemstellung gebracht werden.

Ein schon relativ altes und (früher) sehr oft verwendetes Hilfsmittel für diegrafische Darstellung von Programmabläufen ist der Programmablaufplan(PAP). Dieser ist auch bekannt als Flussdiagramm (flow chart) oder ein-fach Ablaufplan.

Programmablaufpläne dienen zur Visualisierung von kleinerenProblemstellungen und Algorithmen.

Die wichtigsten Bausteine eines PAP umfassen:

Bei der Erstellung eines Programmablaufplanes muss das Problem natürlichschon gelöst sein. Dann können sich die Programmierer bei der Umsetzung(Implementierung) in eine (beliebige) Programmiersprache streng an denAblaufplan halten und sich vollständig auf programmiertechnische Detailskonzentrieren.

Größere Probleme werden in kleine, voneinander unabhängigeTeilschritte zerlegt.

Bild 1.9 Die wichtigsten Bausteine eines Programmablaufplanes (PAP) nach DIN 66 001, um Lösungsansätze ver-ständlich darzustellen



39

Vorteile von Programmablaufplänen (vgl. SCANLAN (1989)):

• Gute grafische Darstellung bei einfachen Problemstellungen.• Verschiedene Abstraktionsebenen möglich.• Alle wichtigen Kontrollstrukturen sind darstellbar.

Nachteile von Programmablaufplänen:

• Bei komplexen Aufgabenstellungen kommt es zu einer oft nicht mehr zudurchschauenden Programmstruktur. Deshalb werden in der Praxis eherStruktogramme (siehe Kapitel 1.6.3) bevorzugt.

• Es gibt keine direkten Symbole für Schleifenkonstrukte und Rekursio-nen. Daher kommt es bei großen Programmen zu Unübersichtlichkeit.

• Verzweigungen und Zusammenführungen können beliebig miteinanderkombiniert werden. Das führt zu unstrukturierten Diagrammen und ent-spricht einer „GOTO-Spaghetti-Programmierung“.

Ein Beispiel für einen Programmflussplan:

Anmerkung: Oft wird der Programmflussplan mit dem Datenflussplan verwechselt. EinDatenflussplan ist eine grafische Übersicht, die Programme und Daten, die zu einer Ge-samtaufgabe gehören, miteinander verbindet. Ein Datenflussplan besitzt ähnliche Symbo-le wie ein Programmablaufplan, aber zusätzliche Sinnbilder für Daten.

Bild 1.10 Beispiel für einen typischen PAP



40

1.6.3 Struktogramme

In Anlehnung an die strukturierte Programmierung (siehe Modul 2) habenStruktogramme als grafisches Hilfsmittel zur Veranschaulichung von Pro-grammabläufen eine große Popularität erlangt.

Die Verwendung von Programmablaufplänen (PAP) verführtzu unübersichtlicher, maschinenorientierter Programmierungund zu undisziplinierter Verwendung von Programmsprüngen.

Daher wurden von NASSI & SHNEIDERMAN (1973) Struktogramme (ProgramStructure Diagrams, PSD) entwickelt. In Anlehnung an die Erfinder werdensie daher auch als Nassi-Shneiderman-Diagramme (NSD) bezeichnet.

Jede einzelne Aktion wird in einen Strukturblock eingetragen (Bild 1.11).Ein Ziel war es dabei, auch die Aktionssteuerungen von Programmier-sprachen in der Programmdokumentation zu berücksichtigen.

Elemente der Struktogramme nach NASSI-SHNEIDERMAN:

Bild 1.11 Die wichtigsten Elemente nach Nassi-Shneiderman (1973), heute DIN 66 261; vergleiche mit Bild 1.7



41

Die Sequenz umfasst eine beliebige Anzahl von Programmanweisungen,die jeweils sequentiell (schrittweise hintereinander) abgearbeitet werden.

Die Wiederholung stellt einen Anweisungsblock dar, der aufgrund einerBedingung eine bestimmte Anzahl von Durchläufen ausführt. Bei dem hierdargestellten Grundtyp wird die Ausführungsbedingung jeweils am Anfangüberprüft: Wenn die Bedingung erfüllt ist, dann wird der Anweisungsblockdurchlaufen. Sonst wird der nachfolgende Programmabschnitt abgearbeitet.

In Bild 1.11 gibt es zwei Modifikationen (Abänderungen zur Grundform):

• Bei der ersten Modifikation wird die Abbruchbedingung am Ende derWiederholungsschleife abgefragt. WENN diese erfüllt wird, DANNwird die folgende Sequenz bearbeitet, SONST wird sie wiederholt.

• Die zweite Modifikation stellt eine unendliche Wiederholung („Loop“)dar. Eingangs- und Abbruchbedingung werden nicht explizit abgefragt.Diese Struktur wird dann zum funktionsfähigen Programmbestandteil,wenn innerhalb des zu wiederholenden Blocks mindestens eine so genannteAbbruchbedingung vorgesehen ist, die das Verlassen des Blocks er-möglicht.

Die Auswahl beschreibt eine Verzweigung aufgrund einer eindeutigenBedingung (Grundtyp).

Auch hier gibt es zwei Modifikationen:

• Die erste Modifikation beschreibt die Möglichkeit einer mehrfachenVerzweigung, bei der auf jede mögliche Bedingung eine bestimmte Alterna-tive folgt.

• Bei der zweiten Modifikation werden alle Bedingungen, die nicht explizitaufgeführt sind, durch dieselbe Sequenz weiterverarbeitet – weil sie dereinzig verbleibende Pfad ist.

Ein Struktogramm ist ausschließlich von oben nach unten zudurchlaufen (top-down), wobei dies auch für einzelne Blöckegilt. Ein Block darf immer nur durch den Eingang „betreten“und durch den Ausgang „verlassen“ werden.

Die Blöcke können je nach dem zu lösenden Problem beliebig aufeinanderfolgen oder geschachtelt werden.

Die Erstellung von Struktogrammen wird durch Software-Werkzeuge (CASE-Tools)erleichtert, siehe z.B. [W5].



42

Einige Vorteile von Struktogrammen:

• Struktogramme sind auf verschiedenen Abstraktionsebenen anwendbarund ermöglichen somit eine schrittweise Verfeinerung des Entwurfs.

• Durch die stark strukturierte grafische Darstellung wird die Entwicklungvon Algorithmen zur strukturierten Programmierung gefordert.

• Struktogramme begünstigen die Zerlegung in hierarchische Blöcke.

Einige Nachteile von Struktogrammen:

• Ähnlich wie das Flussdiagramm wird auch das Struktogramm bei kom-plexen Prozessen schnell unübersichtlich.

• Wenn ein geschlossener iterativer Prozess noch als Bedingungsschleifedargestellt werden kann („ändere das Bauteil, bis es alle Anforderungenerfüllt“), dann erweist sich die Darstellung parallel ablaufender verteilterProzesse als schwierig.

• Das Struktogramm ist zur Darstellung von Entwicklungsprozessen nurbedingt geeignet.

In dem nachfolgenden Beispiel ist der gleiche Algorithmus wie bei derBeschreibung der Programmablaufpläne dargestellt, wobei sehr rasch dieUnterschiede zwischen diesen beiden Methoden ersichtlich werden.

Bild 1.12 Das Beispiel aus Bild 1.10 nochmal in einem Struktogramm dargestellt



43

1.7 Daten- und Funktionsmodellierungsmodelle

Wir wollen hier lediglich, ausgehend vom Modellierungskonzept, einigeModellierungsmodelle erwähnen. Diese werden wir dann im Modul 6 „Soft-ware-Engineering“ genau besprechen.

Das Ziel eines Datenmodells ist, bestimmte Gegebenheiten, wie z.B. die füreinen Geschäftsprozess in einem Betrieb notwendigen Informationen, inDatenstrukturen (siehe Kapitel 2) abbilden zu können.

Ein Datenmodell beschreibt die grundlegenden Eigenschaften, die für alleErscheinungen einer bestimmten (fachbezogenen) Sichtweise auf dieWirklichkeit eine einheitliche Abbildung erleichtern. Im Datenmodell wer-den die grundsätzlichen Strukturen, die Beziehungen und die Eigenschaften,die zugeordnet werden können, festgelegt.

Im Modellierungsprozess werden dann für notwendige Erscheinungender Wirklichkeit im Rahmen der Vorgaben des Datenmodells detaillierteFestlegungen getroffen. Diese Festlegungen enthalten alle Definitionenund Beschreibungen von Inhalt, Struktur und Regeln, die auf Daten überdie Erscheinungen der Wirklichkeit angewendet werden können.

Je genauer die reale Welt erfasst und im Datenmodell beschrie-ben wird, umso leichter ist es dann, entsprechende Regeln zurWahrung der Datenintegrität zu definieren.

Für die Datenmodellierung werden folgende Techniken angeboten, die einecomputergerechte Umsetzung vereinfachen und unterstützen:

• Entity-Relationship-Modell (ERM),• Petrinetze (Modell zur Beschreibung von Abläufen),• Structured Analysis and Design Technique (SADT) und die• Unified Modeling Language (UML).

Als Ordnungsvorstellung zur Strukturierung von Daten in einer Datenbank(siehe Modul 3) existieren vier Ansätze:

• hierarchisches Datenmodell (ein Datensatz wird mit allen hierarchischvon ihm abhängigen Datensätzen als Einheit betrachtet, 1:n-Beziehung),

• Netzwerkmodell (ein Datensatz kann eine beliebige Anzahl übergeord-neter Datensätze aufweisen, n:m-Beziehungen),

• relationales Datenmodell (beruht auf der Datenstruktur „Tabelle“) und• objektorientiertes Datenmodell.



44

Das relationale Datenmodell hat besondere Bedeutung für Datenbanken(Modul 3). Bei diesem Datenmodell stehen als Strukturelemente ausschließ-lich Relationen zur Verfügung, die sich durch Tabellen darstellen lassen.

Die Datensätze bilden die Zeilen, und die Merkmale des Objekts. DieDatenfelder entsprechen den Spalten der Tabelle. Beziehungen zwischenbeliebigen Datensätzen werden über gleiche Feldinhalte hergestellt. DerZugriff auf bestimmte Datensätze wird über die Feldinhalte ermöglicht. DieBenutzer arbeiten nur mit logischen bzw. mit mengenorientierten Abfragen,wobei die physische Speicherung und der Datenzugriff für sie im Hinter-grund bleiben.

Das folgende Bild gibt eine Übersicht, wo welche Basistechniken eingesetztwerden (Details in Modul 6):

Bild 1.13 Verschiedene Basistechniken zur Modellierung und wo diese hauptsächlich verwendet werden



45

1.8 Kontrollelemente von Algorithmen

Algorithmen werden entwickelt, indem kleinste Elemente (Bausteine) zugrößeren (komplexeren) Abläufen zusammengesetzt werden.

• elementare Operation (Verarbeitung)Beispiel: „Schneide Fleisch in kleine Würfel“

• Sequenz, Folge bzw. sequentielle Ausführung (ein Prozessor!)Beispiel: „Bringe das Wasser zum Kochen, dann gib das Paket Nudelnhinein, schneide das Fleisch, dann das Gemüse ...“

• Wiederholung bzw. SchleifeBeispiel: „Rühre die Soße so lange, bis diese fest ist“

• Auswahl (Selektion)Beispiel: „Nimm Erbsen oder Dosenfrüchte“

• parallele Ausführung (mehrere Prozessoren!)Beispiel: „Ich schneide das Fleisch, du das Gemüse, er stellt inzwischenWasser auf, sie holt die Gewürze ...“

• bedingte AusführungBeispiel: „Wenn Soße zu dünn, dann füge Mehl hinzu“

• Unterprogramm: Die Tätigkeit wird anderswo beschrieben und istmehrfach benutzbarBeispiel: „Bereite Soße so, wie im Anhang erklärt wird“

• Rekursion: Anwendung desselben Algorithmus auf TeilproblemBeispiel: Hol Wasser, Katharina! – Ein Loch ist im Eimer – Stopf es! -Womit denn? – Mit Kaugummi! – Der Kaugummi reicht nicht! – Dannnimm mehr Kaugummi! – Der Kaugummi ist zu trocken! – Hol Wasser,Katharina ...

Mehr wird nicht gebraucht!

Es reichen sogar elementare Operationen + Sequenzen +Wiederholungen, um alles programmieren zu können, wasüberhaupt programmierbar ist!

Oft ist es aber einfach komfortabler, mehr als diese drei Grundelemente zu verwenden.

Diese Grundelemente stellen Schemata dar, die eindeutig die Reihenfolgefestlegen („kontrollieren“), wie die Anweisungen abgearbeitet werden. Daherwerden sie als Kontrollelemente bezeichnet (historisch entstanden aus denimperativen Programmiersprachen, Modul 2, Kapitel 2.5.1.1). Im Folgendensehen wir uns die wichtigsten an, wobei in den jeweiligen Bildern links dasKontrollelement in einem Flussdiagramm nach DIN 66 001, und rechts dasgleiche Kontrollelement als Struktogramm nach NASSI-SHNEIDERMAN (DIN66 261) dargestellt wird.



46

1.8.1 Elementare Operation (Verarbeitung)

Das grundlegendste Element ist die Verarbeitung (V). Diese enthält eineAnweisung und wird oft als Prozess oder als Aktion bezeichnet:

1.8.2 Sequenz (Folge)

Die Sequenz (S), auch als Folge bezeichnet, besteht aus einer Anzahl n vonVerarbeitungen (V1 ... Vn), die sequentiell (nacheinander) durchlaufen undabgearbeitet werden. Das Wesentliche dabei ist, dass eine Sequenz nachaußen wieder als eine Verarbeitung (also ein Block) dargestellt werden kann:

1.8.3 Auswahl (Selektion)

Bei der Auswahl (Selektion) werden Verarbeitungen in Abhängigkeit voneiner oder mehreren Bedingungen ausgeführt. Damit ergeben sich dreiMöglichkeiten:

• einseitige Auswahl (bedingte Verarbeitung),• zweiseitige Auswahl (einfache Alternative),• Mehrfachauswahl (mehrfache Alternative).

Bild 1.14 Kontrollele-mente „Verarbeitung“; rechts: PAP-Element, links: Struktogramm-element

VA nw eisung

Bild 1.15 Kontrollele-mente „Sequenz“

Bild 1.16 Kontrollele-mente „Selektion“; dar-unter die Darstellung als Struktogramm (bei der einseitigen Auswahl wird einfach der Nein-Kasten leer gelassen)



47

1.8.4 Wiederholung (Schleife)

Unterschieden wird zwischen Zählschleife und Bedingungsschleife. Bei denZählschleifen bestimmt eine Laufvariable (Schleifenzähler), die Anzahl derSchleifendurchläufe (z.B. N = 10). Der Schleifenkopf enthält einen Start-und einen Endwert. Beginnend beim Startwert wird der Schleifenzähler injedem Durchlauf bis zum Endwert um einen festen Wert (Schrittweite)erhöht bzw. erniedrigt. Bei Erreichen des Endwerts wird die Schleife zumletzten Mal durchlaufen. In sehr vielen Programmiersprachen leitet dasSchlüsselwort FOR eine Zählschleife ein (siehe Syntaxdiagramm Bild 1.20).

Bei Bedingungsschleifen werden im Prinzip drei Arten unterschieden: 1) abweisende Schleife: Wiederholung mit vorangehender Bedingungsprü-fung (Bild 1.18 links); 2) nicht abweisende Schleife: Wiederholung mitnachfolgender Bedingungsprüfung (Bild 1.18 rechts) und 3) Endlosschleife:Wiederholung ohne Bedingungsprüfung.

Durch das Kontrollelement Auswahl können Schleifen dargestellt werden:

Anstelle von Wieder-holung wird häufiger die Bezeichnung Schleife (loop) verwendet; aber auch Zyklus oder Iteration werden verwendet

Bild 1.17 Bedingungs-schleifen; Achtung: Eine While-End-Schleife (Bild mitte) bricht (im Gegen-satz zu einer Zählschlei-fe) nicht immer ab, wenn z.B. die Endbedingung nicht korrekt formuliert wird – sie sind daher eine häufige Fehlerquelle!

Bild 1.18 Die Gegenüber-stellung einer „Schleife S mit Bedingung B am Anfang“ (kopfgesteuert) versus „Schleife mit Be-dingung am Ende“ (fuß-gesteuert); darunter die Darstellung mit Strukto-grammen;



48

2 Datentypen und Datenstrukturen

Die Begriffe Information, Daten, Datentyp, Information usw. wurden inBand 1, Modul 1 eingeführt, definiert und werden hier vorausgesetzt.

2.1 Der Begriff Datenstruktur

Der Begriff Datenstruktur (data structure) wird im weiteren Sinne oftgleichbedeutend mit Datentyp verwendet. Im engeren Sinne wird unterDatenstruktur jedoch der Aufbau von (zusammengesetzten) Datentypenaus elementaren Datentypen verstanden.

Beispiel: In einer objektorientierten Sprache (siehe Modul 2) sind Daten-strukturen Anordnungen von Objekten, deren Beziehungen untereinandernach bestimmten Gesetzmäßigkeiten aufgebaut sind. So genannte Objekt-klassen werden zur Datenmodellierung verwendet. Verbindungen zwischenzwei Objekten einer Datenstruktur werden durch besondere Attribute dar-gestellt, die auf andere Objekte verweisen können (oft auch „Referenzieren“genannt) – die so genannten Zeiger oder Referenzen.

In vielen nichtobjektorientierten Programmiersprachen werden statt derObjektklassen und Objekte einfachere Konstruktoren zur Beschreibungeiner Datenstruktur verwendet.

Dabei entsprechen den Objekten die so genannten Variablen und denObjektklassen die Datentypen.

2.2 Der Begriff Datentyp

Zur Erinnerung: Datentypen (data types) stellen in der Informatik „Zeichensorten“ dar,mit denen bestimmte Algorithmen arbeiten. Daten bzw. Datentypen haben immer nureine maschineninterne Bedeutung (technische Basiszeichen). Computer können erst durchdie Information über den Datentyp die Daten entsprechend verarbeiten.

Ein Datentyp ist die Festlegung der Interpretation einer gespeicherten(physikalischen) Bitfolge.

Datentypen können zunächst grob eingeteilt werden in (Bild 1.19):

• idealisierte Datentypen (für den theoretischen Entwurf),• konkrete Datentypen (die „klassischen“ Datentypen) und• abstrakte Datentypen („abstrahiert“ vom konkreten Programm).

Die konkreten Datentypen können aus Grundelementen bestehen (Zahlen,

Daten sind codierte Informationen



49

logische Werte, Zeichen) oder zusammengesetzt (strukturiert) sein. Wiruntergliedern sie in:

• einfache Datentypen (Grundelemente aller weiteren Datenstrukturen),• strukturierte Datentypen (die so genannten Datenstrukturen),• Zeiger-Datentypen (dynamische Datenstrukturen).

Das folgende Bild gibt einen Überblick über Datentypen:

Der Datentyp legt die Art der gespeicherten Information undderen Auswertungsmöglichkeit fest.

Die Festlegung des Datentyps für eine Variable wird Definition, Deklarationoder Vereinbarung genannt und besitzt folgenden Aufbau:

<definitionskennzeichnung> <identifikation> <typmerkmal> <definitionsabschluss>

Beispiel: In der Programmiersprache Pascal z.B. lautet eine Definition: varZahl integer. „Zahl“ definiert dabei eine ganzzahlige Größe.

Die Definitionskennzeichnung kann in manchen Programmiersprachenauch entfallen. Außerdem kann das Typmerkmal der Identifikation bzw.dem Variablennamen voranstehen.

Die Möglichkeit der digitalen Wertedarstellung der Informationen einesAnwendungsbereiches bestimmt wesentlich auch die Anwendbarkeit einesComputers.

Bild 1.19 Systematik der Datentypen: Hier kommt klar der Unter-schied zwischen Daten-typen (konkret, einfach) und Datenstrukturen (wie z.B. Mengen, Arrays usw.) heraus; in Anlehnung an Horn (2001), 245



50

2.3 Syntaxdiagramme

Ähnlich, wie die Struktur von Algorithmen durch Struktogramme dargestelltwerden kann (Kapitel 1.6.3), kann auch der Aufbau einer Datenstrukturbildlich dargestellt werden. Weil die Struktur eines Textes als Syntaxbezeichnet wird, sprechen wir hier von Syntaxdiagrammen.

Der formale Aufbau einer Sprache, d.h. die Aneinanderreihung von Symbolen, wird alsSyntax bezeichnet. Die Bedeutung dieser Aneinanderreihung dagegen ist die Semantik.

Die Syntax einer Zählschleife (Kapitel 1.8.4) kann durch Syntaxdiagrammeanschaulich beschrieben werden:

Die rechteckigen Kästchen stehen im Syntaxdiagramm für Komponenten,deren detaillierter Aufbau offen gelassen oder an anderer Stelle beschriebenist und auf die wir uns durch deren Namen beziehen können.

Die runden Elemente beschreiben anonyme Teile, deren Inhalt an derbetreffenden Stelle auftreten muss (Bild 1.21).

Insbesondere beschreiben Syntaxdiagramme mit Hilfe grafischer Symboledie Syntax einer Programmiersprache (Modul 2 und Modul 5).

Flussdiagramme und Struktogramme beschreiben den Ablaufeines Programmes. Syntaxdiagramme beschreiben hingegenden formalen Aufbau einer Datenstruktur und (im Modul 2)den formalen Aufbau (Syntax) einer Programmiersprache. Jedes Syntaxdiagramm hat genau einen Eingang und Ausgang.

In der Theoretischen Informatik (Modul 5) werden wir noch die Backus-Naur-Form (BNF), benannt nach JOHN BACKUS und PETER NAUR (erstmalszur Beschreibung der Syntax von ALGOL 60 verwendet) kennen lernen.

Backus-Naur-Form und Syntaxdiagramm sind die Standardbe-schreibungstechniken für nahezu alle Programmiersprachen.

Bild 1.20 Das Grundprinzip einesSyntaxdiagrammes

Bild 1.21 Die Elemente von Syntaxdiagrammen



51

2.4 Variable und Konstante

2.4.1 Variable

Eine Variable hat prinzipiell drei Bestandteile:

• Name,• Datentyp und• Wert.

Eine Variable stellt eine Art „Behälter“ für ihren Wert dar. Im Computerwird (z.B. durch den Compiler) entsprechend dem Datentyp eine bestimmteSpeicherplatzreservierung für diesen „Behälter“ ausgeführt. Hardware-technisch ist eine Variable also eine Benennung von Speicherwörtern.

Die Zuweisung eines Wertes an eine Variable ist eine fundamen-tale Operation in Computerprogrammen.

Eine Variable zeigt eine ähnliche Verhaltensweise wie eine Wandtafel: Sie kann jederzeitgelesen werden (liefert Wert), aber sie kann jederzeit gelöscht und überschrieben werden.

Die Zuweisung eines Wertes an eine Variable erfolgt oft durch das Opera-torzeichen „=“. Zur Unterscheidung vom Gleichheitszeichen verwendenmanche Programmiersprachen auch einen Linkspfeil oder „:=“.

Wichtig ist die Unterscheidung zwischen Wertzuweisung und Gleichungim mathematischen Sinn. Die Gleichung

X = X + 1

macht in der Mathematik wenig Sinn (es existiert keine Lösung). In einerProgrammiersprache bedeutet der Ausdruck jedoch „Addiere 1 zum Wertvon X und speichere das Ergebnis wieder in X“. Kürzer: „Erhöhe X um 1“.

In einem Programm kann auf eine Variable durch Nennung ihres NamensBezug genommen werden. Ihr Datentyp beschreibt die Struktur und denWertebereich des Variablenwertes. Nur der Wert der Variablen kann durchOperationen manipuliert werden, die für Variable dieses Datentyps in derProgrammiersprache definiert sind. Name und Datentyp einer Variablenwerden meistens explizit vor der ersten Benutzung durch eine Deklarationfestgelegt. In nahezu allen höheren Programmiersprachen müssen Variablevor ihrer Verwendung deklariert werden. Es wird dabei der Datentyp derVariablen und ein Bezeichner angegeben.



52

Beispiele für Variablen-Deklaration:

In der Programmiersprache FORTRAN (siehe Modul 2) können Variableexplizit deklariert werden, z.B. INTEGER V.

Variable der Datentypen INTEGER (ganze Zahl) oder REAL (rationaleZahl als Annäherung zur reellen Zahl) können jedoch auch implizit (bei derenersten Benutzung) deklariert werden. Der Anfangsbuchstabe des Variablenna-mens entscheidet darüber, von welchem Typ die Variable ist: Beginnt er mitI, J, K, L, M oder N, so hat die Variable den Typ INTEGER, beginnt er miteinem anderen Buchstaben, so ist die Variable vom Typ REAL, z.B.: IV.

Die implizite Deklaration von Variablen ist eine häufige Fehlerquelle: Ein Schreibfehlerführt sofort eine neue Variable in das Programm ein.

In Pascal (siehe Modul 2) müssen alle Variablen vor der ersten Benutzungdeklariert werden. Ein Pascal-Programm besteht daher immer aus einemDeklarationsteil und einem Ausführungsteil (dem so genannten Block).Eine eigene Komponente des Deklarationsteils ist die Variablendeklaration,die mit dem Wort VAR eingeleitet wird. Die Deklaration einer Variablen„Körpergröße“ vom Datentyp REAL und einer Variablen „Personenan-zahl“ vom Typ INTEGER hat daher das folgende Aussehen:

VAR Körpergröße : REAL;

Personenanzahl : INTEGER;

Ein letztes Beispiel aus der Programmiersprache C (siehe Modul 2):

INT Anzahl, Summe, I, J;

float EUR_Betrag;

Eine Verallgemeinerung sieht folgendermaßen aus:

TYP variable

oder

TYP v1, v2, ... vn (n > 1)

Mehrere Variable können kombiniert werden. Diesem Konstrukt kann eineigener Namen zugewiesen werden. Bei Variablen des gleichen Typs wirdvon mehrdimensionalen Variablen bzw. Feldern (Arrays, Kapitel 2.6.3.2)gesprochen.



53

2.4.2 Konstante

Konstante (Literale) sind Datenwerte, die direkt in der Anweisungsfolgeeines Programms eingetragen werden können (Standardbezeichnung, z.B.Zahlen). Eine Konstante besteht ebenfalls aus drei Bestandteilen:

• eindeutig festgelegter Bezeichner (Name),• Datentyp und• fester Wert aus der Wertemenge des Datentyps.

Als Konstante bezeichnet man üblicherweise auch Namen für Datenwerte (frei wählbareBezeichnung). Durch die eindeutige Vereinbarung von Konstanten-Namen wird ein ganzbestimmter Datenwert mit einem Namen versehen und ist damit jederzeit zugreifbar.

Konstante repräsentieren einen bestimmten Wert, der sich zurAusführungszeit des Algorithmus nicht mehr ändert.

Beispiele: Pi = 3,1415 (TYP = REAL); A = 1, B = 100

Minimum = 1, Maximum = 100; Autor = „Andreas Holzinger“

Beispiel: In der Programmiersprache C (siehe Modul 2) findet man z.B. zweiVarianten der Konstantenvereinbarungen:

const float Pi = 3,1415

#define Pi 3,1415

Die erste Form entspricht dem ANSI-Standard (siehe Band 1) und ist zu bevorzugen.Die zweite Variante ist älter und definiert ein Makro. Vor der eigentlichen Übersetzungwird im gesamten Text die Zeichenkette „Pi“ einfach durch die Zahl 3,1415 ersetzt.

Beispiel: In der Sprache Pascal sieht das Ganze so aus:

const pi = 3,1415;

Eine Zuweisung pi := ... ist im Gültigkeitsbereich von pi verboten.

Eine Konstante ist ein Datenelement, dessen Wert sich beider Ausführung eines Programms nicht ändert. Eine Variablehingegen ist ein Datenelement, dessen Wert sich während derAusführung eines Programms ändern kann.



54

2.5 Idealisierte Datentypen

Idealisierte Datentypen (ideal im Gegensatz zu real) sind durch denbeschränkten (endlichen) Speicherplatz in Computern nicht darstellbar, sindjedoch für den theoretischen Entwurf von Algorithmen hilfreich.

2.6 Konkrete Datentypen

Die konkreten Datentypen werden oft als „die“ Datentypen bezeichnet. Sieunterteilen sich in (siehe nochmals Bild 1.18):

• einfache Datentypen,• strukturierte Datentypen und• Zeigerdatentypen.

2.6.1 Einfache Datentypen

Einfache Datentypen sind die elementaren Grundbausteine aller weiterenDaten. Sie sind nur als Ganzes manipulierbar und sind nicht weiter zerlegbar.Sie unterteilen sich zunächst in zwei Unterarten:

• ordinale Datentypen und• Real-Datentypen.

2.6.1.1 Ordinale Datentypen

Zu den ordinalen Datentypen zählen die elementarsten Datentypen:

• BOOLEAN = boolesche Daten,• INTEGER = ganze Zahlen,• CHAR = Character, endliche Menge von Zeichen;

sowie durch Einschränkung abgeleitete Datentypen:

• Aufzählungsdatentypen (enumeration types) und• Teilbereichsdatentypen (subrange types).

Ordinale Datentypen besitzen folgende gemeinsame Eigenschaften:

• Die Werte eines ordinalen Typs bilden eine geordnete Menge.• Jedem Wert ist eineindeutig eine Ordnungsnummer (Ordinalzahl) zugeordnet.• Es gibt einen „kleinsten“ und einen „größten“ Wert.• Die Ordinalzahl eines Wertes vom Typ INTEGER ist der Wert selbst. • Bei Aufzählungstypen hat das erste Element die Ordinalzahl 0, das

nächste 1 usw.

Im mathematischen Sinn heißt eine Zuordnung eineindeutig, wenn sie umkehrbar eindeutig (bijektiv)ist



55

2.6.1.2 Datentyp BOOLEAN

Der Datentyp BOOLEAN umfasst nur die Werte TRUE (wahr) undFALSE (falsch). Dieser ist vor allem für die Lösung logischer Probleme undzur Konstruktion von Kontrollstrukturen von Algorithmen von Bedeutung.

In vielen Programmiersprachen werden diese Wahrheitswerte intern durch 0 bzw. 1 dar-gestellt. Dies gilt jedoch nicht generell und sollte deshalb nie vorausgesetzt werden.

Meistens stehen folgende logische Operatoren (vgl. mit Band 1, Modul 1)zur Verfügung:

• NOT Negation,• AND Logisches Und,• OR Logisches Oder,• XOR Exklusives Oder (Antivalenz).

2.6.1.3 Datentyp INTEGER

Der Datentyp INTEGER dient zur Darstellung ganzer Zahlen. Das sindZiffernfolgen ohne Dezimalpunkt mit oder ohne Vorzeichen. MöglicheINTEGER-Konstante sind z.B. 7, -4, +378, 0, usw. Der Zahlbereich fürdiesen Datentyp liegt üblicherweise zwischen zwei Konstanten MININTund MAXINT, die von der n-Bit-Zahlendarstellung des Computersystemsabhängen, also z.B. bei einem 16-Bit-System von –32768 bis +32767.

Bei der Entwicklung mit Pseudocode wird INTEGER verwendet, wennman sich noch nicht auf einen endgültigen Typ festlegen will. Erst bei derÜberführung in Programmiercode wird der Typ endgültig entschieden.

Als Operationen sind „+“, „–“, „*“, „div“ (ganzzahlige Division) und„mod“ (Rest bei ganzzahliger Division) zulässig.

2.6.1.4 Datentyp CHAR

Der Typ CHARACTER (kurz: CHAR) ist in vielen Programmiersprachenein vordefinierter Datentyp, dessen Wertebereich eine endliche, geordneteMenge von Zeichen (characters) ist. Dazu gehören (mindestens) die Groß-buchstaben A bis Z, die Ziffern 0 bis 9 und das Leerzeichen (blank).

Elemente des Typs CHAR werden meistens in Apostrophe (’) bzw. inAnführungszeichen (’’) eingeschlossen. Beispiel:

’A’, ’’a’’, ’’.’’, ’$’ usw.



56

2.6.1.5 Aufzählungstyp

Aufzählungstypen können von den Programmierern selbst definiert werden.Die allgemeine Definition eines Aufzählungstyps lautet:

type T = (t1, t2, ... tn)

T Bezeichner des Typs,t1 ... tn mögliche Werte.

Mögliche Operationen auf T sind die Vergleichsoperationen (=, , <, >,usw.) sowie eine Nachfolgeroperation succ (sucessor) und Vorgängerfunk-tion pred (predecessor).

Beispiel:

type farbe = (rot, gruen, blau)

rot < gruen < blau

2.6.2 Datentyp REAL

Der Datentyp REAL dient zur Darstellung von reellen Zahlen. Das sindZiffernfolgen mit Dezimalpunkt, mit oder ohne Vorzeichen sowie mit oderohne Exponent. Mögliche REAL-Konstante sind z.B. –2,7; 36,81;0,23623E+2 usw. Der Buchstabe E bedeutet dabei ,,mal 10 hoch“. DerZahlbereich ist naturgemäß wesentlich größer als beim Typ INTEGER.

Bei der Entwicklung in Pseudocode wird der Typ REAL verwendet, wennfeststeht, dass eine Maschinennäherung reeller Zahlen benötigt wird, dieendgültige Implementierung aber noch nicht festgelegt wird.

Variablen vom Typ REAL können als Wert prinzipiell reelleZahlen annehmen. Da Computersysteme allerdings nur einebeschränkte Speicherkapazität haben, wird der Wertebereichauf Zahlen in Gleitpunktdarstellung eingeschränkt!

Gleitpunktdarstellung (floating point) ist eine Methode zur näherungsweisen Darstellungvon reellen Zahlen in Computersystemen (siehe Band 1).

Für den Datentyp REAL sind die mathematischen Grundoperationen undmathematische Funktionen (Sinus, Logartithmus usw.) möglich.

≠



57

2.6.3 Strukturierte Datentypen

In der Praxis kommt man mit den einfachen Datentypen nicht aus. Daherkönnen in vielen Programmiersprachen beliebig kompliziert zusammengesetzteDatenstrukturen definiert und durch eigene Variablen bezeichnet werden.Zu den strukturierten Datentypen zählen:

• Mengen, Arrays, Listen und Matrizen,• Tabellen und Relationen,• Bäume und Graphen,• Files,• Programme und• Objekte, Klassen und Methoden.

2.6.3.1 Mengen

Prinzipiell ist eine Menge definiert als eine Zusammenfassung von wohlunterscheidbaren Objekten zu einem Ganzen (Bild 1.22). Die einzelnenObjekte bezeichnen wir als Elemente der Menge ( ). Um eine endlicheMenge von Elementen eines Datentyps T zu definieren, kann der folgendeTyp in vielen Programmiersprachen deklariert werden:

set of T

Eine ein-, zwei- oder mehrdimensionale Anordnung von Zahlen und Stringsin geordneten oder ungeordneten Mengen ermöglicht hohe Flexibilität zurManipulation von Daten.

Ein „set“ ist eine Zusammenfassung von Elementen des gleichenGrundtyps – im Gegensatz zu Arrays aber ohne Rangordnung.Daher können einzelne Mengenelemente auch nicht über einenIndex angesprochen werden. Die Reihenfolge der Elemente inder Menge ist nicht definiert.

2.6.3.2 Arrays

Ein Array wird oft einfach als „Feld“ bezeichnet und ist eine geordneteMenge gleichartiger Datentypen (Bild 1.23), wobei auf die Elemente mitHilfe eines Index I zugegriffen werden kann:

type arraytyp = array [I] of grundtyp

In manchen Programmiersprachen lautet das Schlüsselwort nicht Array,sondern dim (dimension).

Bild 1.22 Eine Menge

x M∈

Bild 1.23 Ein Array



58

2.6.3.3 Listen

Eine Liste ist eine verkettete Folge von elementaren oder strukturiertenDatentypen.

Eine Liste (list) ist ein vereinfachter Graph, denn jeder Knoten außer den beiden End-knoten ist mit genau zwei anderen Knoten über je eine Kante verbunden. Von den beidenListenenden gehen jeweils nur eine Kante ab.

Eine lineare Liste ist eine durch Zeiger verkettete Folge vonElementen gleichen Datentyps (üblicherweise Records). JedesElement, bis auf das letzte, hat genau einen Nachfolger.

Die lineare Liste ist die wichtigste dynamische Datenstruktur und wird mitHilfe von Zeigern realisiert. Lineare Listen werden weiter unterteilt in einfachverketteten und doppelt verketteten Listen:

Listen haben folgende Eigenschaften:

• Ihre Größe kann zu- und abnehmen,• beliebige Knotenzahl ist möglich,• Elemente können in effizienter Weise umgeordnet werden,• einziger Nachteil: Der Zugriff muss über den Listenkopf erfolgen.

Die Darstellung einer Liste in Pascal könnte wie folgt aussehen:

TYPEListe = RECORDende1, ende2 :^ListenknotenEND;

Listenknoten = RECORDnutzinformation : IrgendeinTyp;vorgänger :^Listenknoten;

Bild 1.24 Einfach und doppelt verkettete lineare Liste



59

nachfolger :^ListenknotenEND;

VAR liste: ^Liste;l,l1,l2: ^Listenknoten;

Der Knoten, auf den ende1 zeigt, hat keinen Vorgänger, und der Knoten, auf den ende2zeigt, hat keinen Nachfolger. In diesen Fällen besitzen die Komponenten-Vorgänger bzw.-Nachfolger den vordefinierten Wert NIL, der anzeigt, dass die Komponenten zur Zeitauf keinen Knoten verweisen.

Gebräuchliche Operationen auf Listen sind

• das Erzeugen eines Listenknotens (neuerknoten(l1)),• das Einfügen eines Knotens nach oder vor einem anderen Knoten (lis-

te.einfügenach(l,l1), liste.einfügevor(l,l2)),• das Entfernen eines Knotens (liste.enfernen(l)),• das Verweisen auf den Vorgänger bzw. Nachfolger (liste.nächster(l),lis-

te.voriger(l)),• das Erfragen, ob die Liste leer ist (liste.leer), und• das Feststellen der Anzahl der Listenknoten (liste.länge).

2.6.3.4 Matrizen

Ein eindimensionales Array (Feld) entspricht einem Vektor,ein mehrdimensionales Array einer Matrix.

Eine Matrix ist nichts anderes als eine mehrdimensional geordnete Mengevon gleichartigen Datentypen. In der Mathematik werden Matrizen für dieverschiedensten Zwecke eingesetzt. Ihre wesentlichen Merkmale sind:

• die lineare Anordnung ihrer Komponenten in mehreren Dimensionenund

• die Gleichartigkeit aller Komponenten.

Matrixkomponenten werden durch einen Indexvektor identifiziert.

In Anwendungen spielt die Art und Weise, wie Matrizen im Speicher abgelegt werdenund wie der Zugriff auf ihre Komponenten erfolgt, eine wesentliche Rolle. Eine Matrix mitz.B. 1000 x 1000 Komponenten benötigt bei der Speicherung als zweidimensionalerVektor eine Million Speicherzellen! Sind aber nur die Haupt- und Nebendiagonalen vonNull verschieden, so reduziert sich der Platzbedarf auf rund 3000 Speicherzellen.



60

2.6.3.5 Tabellen und Relationen

Beim Datentyp Tabelle werden Informationen unter einem bestimmten„Schlüssel“ gespeichert. Über diesen Schlüssel können die Informationenwieder abgerufen werden. Sowohl Schlüssel als auch Information könnendabei einen beliebigen Datentyp haben.

Im Bereich der Datenbanken (siehe Band 2, Modul 3) haben relationaleDatenbanken eine lange Tradition. Daten werden in Tabellen gespeichert undkönnen durch Relationen verknüpft werden. Die Relationen selbst werden inForm von Tabellen abgelegt. Eine Tabelle besteht dabei aus n Zeilen und mSpalten, ist also eine zweidimensionale geordnete Struktur. Oft enthält eineSpalte nur Elemente eines vorgegebenen Datentyps. Die Anzahl der Spaltenwird als konstant betrachtet und ist in der Regel bei Anlegen der Tabelle fest-gelegt. Die einzelnen Datensätze werden in neue Zeilen eingefügt bzw.gelöscht. Die Zeilenzahl einer Tabelle ist damit flexibel.

2.6.3.6 Bäume und Graphen

Bäume und Graphen sind Datenstrukturen, die aus Knotenund Kanten bestehen: Eine Kante verbindet stets zwei Knotenund kann somit als ein Paar von Knoten verstanden werden.

Graphen

Ein ungerichteter Graph G besteht aus zwei Mengen: einer Menge N vonKnoten (nodes) und einer Menge V von Kanten (vertices), d.h. G = (N, V).Eine Kante a aus V verbindet stets zwei Knoten A und B aus N miteinander.Wir schreiben a = {A,B} = {B,A}. Die Anzahl der Kanten, die mit demKnoten verbunden sind, wird der Grad eines Knotens genannt.

Der ungerichtete Graph in Bild 1.25 (oben) hat die Knoten A, B und Cund die Kanten a={A,B}={B,A}, b={A,C}={C,A} und c={B,C}={C,B}.

Neben den ungerichteten Graphen existieren auch gerichtete Graphen,deren Kanten mit einer Vorzugsrichtung versehen sind. Bei ihnen sind dieKanten a={A,B} und a´={B,A} verschieden. Dies wird in der grafischenDarstellung durch einen Pfeil gekennzeichnet (Bild 1.25 unten). Die Anzahlder auf einen Knoten zeigenden Kanten wird Ingrad des Knotens, dieAnzahl der aus dem Knoten herausgehenden Kanten wird Ausgrad genannt.

Die Kanten ungerichteter Graphen stellen nur die Beziehungen zwischenden Knoten dar, weisen jedoch keine Richtung aus. Sie können durch äqui-valente gerichtete Graphen ausgedrückt werden, bei denen jeder Kante des

Relation = allg. jede Beziehung zwischen Datensätzen

Achtung: Graph nicht mit Grafverwechseln!

Bild 1.25 Ungerichteter (oben) und gerichteter Graph (unten)



61

ungerichteten Graphen zwei Kanten des gerichteten Graphen zugeordnetwerden, die jedoch einander entgegengesetzt ausgerichtet sind.

Ein Pfad zwischen zwei Knoten A und B existiert genau dann, wenn eineFolge aus Kanten und Knoten existiert, die von Knoten A ausgeht und zuKnoten B führt. Ein gerichteter oder ungerichteter Graph besitzt einenZyklus, wenn von einem Knoten ein Pfad über mindestens einen weiterenKnoten wieder zu dem ersten Knoten zurück existiert. Ein Graph, der keineZyklen besitzt, wird zyklenfrei genannt.

Im Gegensatz zu ungerichteten Kanten können gerichtete Kanten direkt aufVariablen eines Datentyps abgebildet werden. Das ist etwas, das praktisch inallen modernen Programmiersprachen vorkommt: der Zeiger (pointer).Ein Knoten kann z.B. in folgender in Pascal formulierter Datenstrukturabgebildet werden:

TYPE

Knoten = RECORD

knoteninhalt : IrgendeinTyp;

kanten : ^Kantenliste

END;

Kantenliste = RECORD

kante : ^Knoten;

nächsteKante : ^Kantenliste

END;

VAR graph, k, k1, k2 : ^Knoten

Bäume

Ein Baum (Bild 1.26) ist ein gerichteter Graph mit Knoten, auf die – bis aufeine Ausnahme – nur jeweils eine Kante zeigt. Die Ausnahme ist die Wurzeldes Baumes. Sie besitzt keine eingehende Kante. Von den Knoten einesBaumes weisen ein oder auch mehrere Kanten zu weiteren Knoten, derenausgehende Kanten wiederum auf Knoten verweisen können. Ein Knotenwird – zusammen mit allen über seine Kanten referenzierten Knoten, dessenReferenzen, usw. – Teilbaum genannt (Bild 1.26).

Pointer verweisen (zeigen) auf Daten



62

Knoten, von denen keine Kanten ausgehen, werden Blätter genannt. Alleanderen Knoten heißen innere Knoten. Die Anzahl der Kanten von derWurzel des Baumes zu einem Knoten heißt die Weglänge des Knotens. DieWurzel hat also die Weglänge 0. Die größte Weglänge, über alle Knotenbetrachtet, heißt Tiefe (bzw. Höhe) des Baumes.

Einem Baum, dessen Knoten nur jeweils eine ausgehende Kante besitzen,entspricht eine einfach verkettete Liste (Bild 1.24). Die häufigste Baumart istder binäre Baum, dessen Knoten genau zwei ausgehende Kanten besitzen,die meist mit links und rechts bezeichnet werden. Besitzen Baumknotenmehr als zwei ausgehende Knoten, so werden die dazugehörenden BäumeB-Bäume oder auch Vielweg-Bäume genannt (siehe weiterführende Litera-tur z.B. OTTMANN & WIDMAYER (2002), SEDGEWICK (1997) oder GOODRICH

& TAMASSIA (1998)).

Bäume werden meistens dazu benutzt, um Daten im Arbeitsspeicher oder auf Massen-speichern geordnet abzulegen und schnell wiederzufinden. Aus diesem Grund besitzen dieKnoten neben den Nutzinformationen und den Verweisen auf die nachfolgenden Knotenauch einen oder bei B-Bäumen mehrere Schlüssel, nach deren Werten der Knoten in denBaum eingefügt wird. Zudem existiert eine Ordnungsrelation „kleiner oder gleich“. Diesegibt Antwort darauf, ob der Schlüssel kleiner oder gleich einem anderen Schlüssel ist. Diesist notwendig, da Schlüssel nicht nur Zahlen sondern auch beliebig komplexere Strukturensein können, auf denen sich eine Ordnung definieren lässt.

Beim binären Baum besitzt jeder Knoten höchstens zwei Nachfolger. Erlässt einfaches Suchen und Navigieren zu, z.B. mit Hilfe von Ja-Nein- bzw.Links-Rechts-Abfragen. Sind den Nachfolgern die Wahrheitswerte „Wahr“oder „Falsch“ zugeordnet, wird von einem logischen Baum gesprochen.Verschiedene Suchalgorithmen auf Baumstrukturen basieren auf binärenBäumen. Sie werden deshalb auch Suchbäume genannt.

B-Bäume = balanced (ausgeglichen)

Bild 1.26 Die Elemente und die Struktur eines Baumes mit der Höheh = 3; die Anzahl der Kanten von der Wurzel bis zu einem Knoten heißt Weglänge; ein Kno-ten auf der Stufe i hat die Weglänge i



63

Ein binärer Baum kann in der Sprache Pascal wie folgt dargestellt werden:

VAR wurzel, k: ^Knoten;

TYPEKnoten = RECORDschluessel: IrgendeinTyp;nutzinformation: IrgendeinWeitererTyp;links, rechts: ^KnotenEND;

Die Operationen auf einem binären Baum umfassen beispielsweise:

• das Erzeugen eines Baumknotens (neuerknoten(k)),• das Einfügen eines Knotens in einen Baum anhand des eingetragenen

Schlüssels und der auf ihm definierten Ordnungsrelation (wurzel.einfu-ege(k,relation)),

• das Löschen eines Knotens aus dem Baum (wurzel.loesche(k)),• das Suchen nach einem Knoten anhand eines Schlüssels (wurzel.su-

che(schluessel,relation)) (zurückgegeben wird ein Zeiger auf den gefun-denen Knoten oder NIL, wenn kein passender Knoten gefunden wurde)und

• das Traversieren des Baumes, d.h. das Ausführen einer Operation auf je-den Baumknoten (wurzel.traversiere(operation)).

Das Suchen in einem Baum ist sehr einfach, da ab der Wurzel für jedenbesuchten Knoten nur die folgenden Fragen beantwortet werden müssen:

• Stimmen der vorgegebene Schlüssel und der Knotenschlüssel überein,so ist der Knoten gefunden.

• Ist der vorgegebene Schlüssel von der Ordnungsrelation her kleiner alsder Knotenschlüssel, so befindet sich der gesuchte Knoten (wenn über-haupt) in dem linken Teilbaum des aktuellen Knotens.

• Ist der vorgegebene Schlüssel größer als der Knotenschlüssel, so befin-det sich der gesuchte Knoten (falls er existiert) im rechten Teilbaum desaktuellen Knotens.

Bäume werden für Darstellung von Dateien und Datensätzen,beim strukturierten Programmieren, bei Suchalgorithmen undEntscheidungsverfahren verwendet. Der große Vorteil liegt inder Möglichkeit, Informationen so zu ordnen, dass schnellund systematisch auf sie zugegriffen werden kann.



64

2.6.3.7 Files

Files sind ein Konzept, das in Zusammenhang mit Betriebssystemen (sieheModul 2) entwickelt wurde: Ein File ist eine geordnete Menge von Bytes. Eskann selbst z.B. Zahlen, Zeichen usw. enthalten.

Files sind lineare Folgen von Einzelelementen, die nicht in beliebiger Reihen-folge verarbeitet werden können. Files können nur sequentiell verarbeitetwerden, d.h. elementweise von vorne nach hinten.

Der Nachteil der eingeschränkten Verarbeitungsmöglichkeiten (nur sequen-tiell gegenüber beliebig) wird durch unbeschränkte Größe ausgeglichen:Files können (theoretisch) beliebig viele Elemente enthalten (einschließlichüberhaupt keine). Aus technischer Sicht gibt es natürlich eine Grenze, weildie Speicherkapazität von Computer-Systemen endlich ist. Ein File ohneInhalt (d.h. mit null Elementen) wird als leer bezeichnet.

2.6.3.8 Programme

Ausführbare Programme sind spezielle geordnete Mengen von Daten (phy-sikalisch von Bytes), die der Prozessor eines Computers ausführen kann. Eswird unterschieden zwischen Programmcode (auch „Quellcode“ genannt)und Maschinencode (auch „Bytecode“ genannt). Der Programmcode bestehtaus Files und ist in einer künstlichen Sprache (Programmiersprache, Band 2,Modul 3) geschrieben. Der Maschinencode hingegen besteht auf der unterstenEbene nur aus Binärcode („0“ und „1“) und kann vom Prozessor (oder einervirtuellen Maschine) direkt ausgeführt werden.

2.6.3.9 Objekte, Klassen und Methoden

Ab ca. 1990 wurden objektorientierte Datenstrukturen in viele Program-miersprachen eingeführt. Die Objekte sind dabei wieder verwendbare„Bausteine“. Die Klassen sind flexible „Ansammlungen“ verschiedensterelementarer und zusammengesetzter Datentypen. Klassen können weitereKlassen und Programme – die so genannten Methoden – enthalten.

Prinzip der Objektorientierung ist es, Objekte nur von außen zu betrachtenund ihren inneren Aufbau zu ignorieren – ihre Struktur wird durch Klassenfestgelegt. Objekte, die nach der Struktur einer Klasse aufgebaut sind, sindInstanzen dieser Klasse. Objekte erledigen ihre Aktivitäten praktisch in„eigener Verantwortung“. Für die Softwareentwicklung (Modul 6) bedeutetdas mehr Konfiguration, Ergänzung und Anpassung, statt einer komplettenNeuentwicklung.



65

2.7 Abstrakte Datentypen

Die bis jetzt vorgestellten Datentypen sind in den meisten Programmier-sprachen implementiert, daher sprachen wir auch von konkreten Datentypen.

Die Einführung konkreter Datentypen war ein bedeutender Schritt in der Entwicklungs-geschichte der Programmiersprachen. Erst die Einführung von Abstraktionsmechanismenerlauben den Programmierern, Algorithmen aus ihrer Umwelt zu entwickeln – ohne dieDetails des Computersystems zu kennen.

Komplexere Datenmodelle besitzen (manchmal) auch Strukturen, die überder Abstraktionsebene von strukturierten Datentypen liegen. Diese könnenin Klassen eingeteilt werden, zu denen ein generischer Datentyp definiertwerden kann. Auf solche Datentypen können alle in einer Klasse vorkommendenStrukturen zurückgeführt werden. Solche generischen Datentypen können insowohl in objektorientierten als auch in nichtobjektorientierten Sprachenrealisiert werden und werden als abstrakte Datentypen (ADT) bezeichnet.

Ein abstrakter Datentyp präsentiert sich einem Programmierer wie ein in der Program-miersprache schon verfügbarer Datentyp, auf den eine definierte Menge von Operationenanwendbar ist. Der abstrakte Datentyp muss jedoch in nicht-objektorientierten Program-miersprachen basierend auf schon vorhandenen Datentypen definiert worden sein, wobeiOperationen in Ablaufkonstrukten der Programmiersprache ausformuliert sein müssen.

Beispiel Vektor Vn als abstrakter Datentyp:

Ein Vektor Vn ist ein n-Tupel von: Vn = (v1, v2, ... vn). Um z.B. einen Punktim dreidimensionalen Raum zu beschreiben, kann ein Tripel V3 = (x, y, z)verwendet werden bzw. V2 = (x, y) für einen Punkt in der Ebene. Dabei istes für die Operationen unerheblich, ob die Komponenten des Vektors ganzeoder reelle Zahlen sind. Mit Vektoren können neben den GrundrechenartenAddition, Subtraktion und komponentenweiser Multiplikation mit einemFaktor auch das Skalarprodukt und das Kreuzprodukt (für n=3) gebildetwerden. Bei allen Operationen bis auf das Skalarprodukt ist das Ergebniswieder ein Vektor, beim Skalarprodukt hat das Ergebnis den gleichen Typwie die Komponenten.

Beispiel: In der Programmiersprache Ada (Modul 2) kann ein objektorien-tierter Datentyp Vektor folgendermaßen beschrieben werden (Bild 1.27):Die Deklarationen im generic-Teil legen die grundlegenden Typen, Variab-len und Operationen fest, die der Anwender des abstrakten Datentyps beidessen Benutzung näher zu spezifizieren hat. In der package-Deklarationwerden der Datentyp vektor und die auf ihn anwendbaren Operationenbeschrieben. Diese beiden Teile sind dem Benutzer sichtbar. Der darauf fol-

Generisch aus lat. genus „Art, Gattung“ sind Funktionen oder Operatoren, die unabhängig vom verwendeten Datentyp immer dieselbe Aufgabe ausüben



66

gende Teil package body enthält die Implementation des abstrakten Daten-typs. Er wird vor dem Benutzer versteckt gehalten.

In diesem Beispiel lassen sich generell zwei wichtige Eigenschaften vonmodernen Programmiersprachen erkennen:

• der Polymorphismus von Operationen und • das Überladen von Operatoren.

Polymorphismus drückt sich im Beispiel darin aus, dass zwei Operationen„*“ deklariert werden, die sich nur durch die Typen der Übergabe- undRückgabeparameter unterscheiden. Dadurch können für vom Sinn hergleichartige Operationen auch die gleichen Namen benutzt werden.

Das Überladen von Operatoren ist die Möglichkeit, Funktionsnamen nichtnur aus Buchstaben und Ziffern zu bilden, sondern auch Operationszeichenwie +, *, / zuzulassen, die normalerweise nur auf Werte von elementarenDatentypen anwendbar sind. Dadurch können Operationen mit abstraktenDatentypen so kurz wie mit elementaren ausgedrückt werden. Allerdingswird dadurch die Analyse von Programmen bei Fehlern erschwert, da nebenden Operatoren auch die Operandentypen für eine eindeutige Kennzeich-nung der aufgerufenen Operationen notwendig sind.

Bild 1.27 Ein Beispiel in der Sprache Ada



67

3 Beispielalgorithmen

Die Definition „Algorithmus“ – als allgemeines Lösungsverfahren fürein Problem – impliziert, dass zu jedem lösbaren Problem auch mindestensein Lösungsverfahren existiert. Es kann sogar bewiesen werden, dass zujedem Algorithmus unendlich viele verschiedene Algorithmen existieren, diedas gleiche Problem lösen. Um nun diese riesige Menge von Algorithmenbesser handhaben zu können, ist es sinnvoll, eine Einteilung nach Kriterienvorzunehmen. So können z.B. Algorithmen, die ein bestimmtes Problemlösen, zu einer eigenen Klasse zusammengefasst werden. Da auch Problemezu Klassen zusammengefasst werden können, ist es sinnvoll, auch auf dieseWeise eine entsprechende Einteilung von Algorithmen vorzunehmen, z.B.:

• Sortieralgorithmen,• Suchalgorithmen,• Codierungsalgorithmen usw.

Diese Beispiele sollen nur einen groben Eindruck von der Fülle an existierenden Algo-rithmen, Algorithmenklassen und -klassifikationen geben. Sie erheben keinen Anspruchauf Vollständigkeit, stellen jedoch wichtige Vertreter aus der Menge der Algorithmen dar.

3.1 Sortieralgorithmen

Das Sortieren von Objekten nach bestimmten Kriterien ist eine der häufigstenAufgaben, die mit Computersystemen gelöst werden. Die Sortierverfahrenkönnen beliebige Objekte (nicht nur Zahlen) sortieren – vorausgesetzt, eskann auf diesen eine Ordnungsrelation definiert werden.

Grundlegende Sortieralgorithmen umfassen folgende Strategien:

• Sortieren durch Austauschen (z.B. Bubblesort, Quick Sort),• Sortieren durch Auswählen (z.B. Heapsort),• Sortieren durch Einfügen (z.B. lineare Listen und Bäume) und• Sortieren durch Verschmelzen (Sortieren durch Mischen).

3.1.1 Bubblesort

Bubblesort ist ein einfaches Verfahren zum Sortieren eines linearen Arrays(Feldes). Bubblesort verfährt nach folgender Methode:

Es wird die Liste a[1] ... a[N] der Datensätze durchlaufen und dabei werdenje zwei benachbarte Elemente betrachtet: [i] und a[i+1]. Ist a[i].key >a[i+1].key, so wird a[i] und a[i+1] vertauscht. Das Durchlaufen des Arrayswird so lange wiederholt, bis keine Elemente mehr vertauscht wurden: Das



68

Array ist sortiert. Das Verfahren hat seinen Namen, da bei jedem Schleifen-durchlauf benachbarte Elemente miteinander verglichen werden und dasjeweils größere Element nach oben „steigt“. Sie steigen wie Luftblasen nachoben bzw. rechts auf.

Beispiel:

Feld B = 15,2,43,17,4,8,47

Nach 1. Durchlauf: 2,15,17,4,8,43,47

Nach 2. Durchlauf: 2,15,4,8,17,43,47

Nach 3. Durchlauf: 2,4,8,15,17,43,47

Keine Vertauschungen mehr bei 4. Durchlauf, d.h. das Feld ist sortiert.

3.1.2 Selection Sort

Algorithmus:

• 1. Finde das kleinste Element im Feld und tausche es mit dem ersten Ele-ment.

• 2. Finde das zweitkleinste Element und tausche es mit dem zweiten Ele-ment.

• 3. Wenn das größte Element am letzten Platz steht, ist die Datei sortiert.

Da jedes Element im Schnitt einmal bewegt wird, ist dieses Verfahren dazugeeignet, Dateien mit sehr großen Datensätzen und kleinen Schlüsseln zusortieren.

Beispiel mit Zahlen:

2 8 5 7 1 (das kleinste Element wird gesucht und mit dem auf Platz 1vertauscht)

1 8 5 7 2 (das zweitkleinste Element wird gesucht und mit dem auf Platz2 vertauscht)

1 2 5 7 8 (das 3. Element wird gesucht, es ist auf der richtigen Position)





69

3.1.3 Quicksort

Quicksort wurde von HOARE (1960) entwickelt und ist ein Mehrzwecksortier-verfahren, das in vielen Situationen weniger Ressourcen erfordert als andereAlgorithmen.

• Vorteile: Quicksort läuft „in Place“ (am Ort) ab und es ist gut erforscht.• Nachteile: rekursiv, wenige Operationen, störanfällig, innere kurze

Schleife.

Algorithmus:

Quicksort besteht im Wesentlichen aus dem Zerlegen der Datei in zwei Tei-len und dem anschließenden Sortieren der Teile unabhängig voneinander.

• 1. Zuerst wird ein beliebiges Element gewählt, das in die richtige Positiongebracht werden soll.

• 2. Dann wird das Feld von links untersucht, bis ein größeres Elementgefunden wird.

• 3. Danach wird das Feld von rechts untersucht, bis ein kleineres odergleiches Element gefunden wird.

• 4. Jetzt werden die beiden Elemente vertauscht. • 5. Wenn sich die beiden Zeiger treffen, wird das Element, dass auf die

richtige Position gebracht werden soll, mit dem Element vertauscht, dassich am weitesten links von der rechten Seite befindet.

• 6. Danach wird dieser Vorgang jeweils für die daraus entstehenden Teil-dateien rekursiv angewendet, bis sie vollständig sortiert sind.

3.1.4 Insertion Sort

Der Insertion Sort arbeitet schneller (N²/4 Vergleiche und N²/8 Austausch-operationen) als der Bubblesort Algorithmus (N²/2 Vergleiche und N²/2Austauschoperationen). Der Selection Sort benötigt N²/2 Vergleiche und NAustauschoperationen. Allerdings sind alle diese Sortierverfahren nicht fürgrößere Datenmengen geeignet.

Algorithmus:

• 1. Betrachte ein Element.• 2. Füge dieses Element an seinen jeweils richtigen Platz zwischen den

bereits betrachteten Elementen ein, indem das größere um eine Positionnach rechts bewegt und das Element dann auf dem freigewordenenPlatz eingefügt wird (Bild 1.22) .

• 3. Das Ende ist dann erreicht, wenn man das letzte Feld betrachtet hat.

Bild 1.28 Beispiel für die Wirkungsweise von Insertion Sort



70

3.1.5 Shell Sort

Shell Sort ist eine Erweiterung des Insertion Sort, wobei aber eine Erhöhungder Geschwindigkeit dadurch erzielt wird, dass weit entfernte Elemente aus-getauscht werden können.

Algorithmus:

• 1. Zuerst wird ein bestimmter Abstand zwischen den jeweiligen Elemen-ten gesucht, z.B. 4 Elemente Unterschied.

• 2. Es werden das 1. und das 5. Element verglichen, das 2. und das 6. Ele-ment verglichen usw. (eine solche Datei wird „4-sortiert“ genannt).

• 3. Die Elemente werden – wenn es notwendig ist – vertauscht.• 4. Wenn man am Ende der Datei ist, so wird ein neuer, kleinerer Abstand

zwischen den Elementen gewählt. • 5. Wenn der Abstand nur mehr aus 1 Element Unterschied besteht, wird

die gesamte Datei mit dem Bubblesort sortiert.

Bei Dateien mit vielen Elementen wird der Abstand entsprechend größergewählt. Die besten Abstände (also der Abstand bei dem das Sortieren ameffizientesten ist) zwischen den einzelnen Elementen Abstand * 3 +1.

Die Beschreibung der Effizienz von Shell Sort ist sehr ungenau, da bis jetztnoch niemand den Algorithmus genau analysieren konnte. Bis zu etwa 5000Elementen ist der Shell Sort von allen bisherigen Sortierverfahren das besteund wird auch bei vielen Anwendungen benutzt.

3.1.6 Heapsort

Oft müssen andere Operationen, wie das Einfügen, Löschen des größtenElements, Ersetzen, Verändern, Löschen eines beliebigen Elements und dasZusammensetzen mehrerer Daten, möglich sein. Dafür eignet sich derHeapsort („Sortierung von Haufen“) sehr gut. Der Algorithmus wurde vonWILLIAMS (1964) entwickelt und basiert auf dem Treesort-Verfahren vonFLOYD (1962).

Die Datenstruktur des Heaps ist ein vollständiger, nicht sortierter, binärerBaum. Dieser Baum muss zwei Bedingungen erfüllen:

• 1. Jeder Knoten muss größer als sein Nachfolger sein, das heißt, dergrößte Schlüssel ist die Wurzel.

• 2. Wenn ein Knoten die Position j hat, muss sein Nachfolger die Positionj*2 oder j*2+1 haben.



71

Algorithmus:

Zunächst wird ein Heap aufgebaut, der die zu sortierenden Elemente enthält:

• 1. An der (abrunden(letzten Position/2)) suchen (z.B. 9/2=4.5 -> 4).• 2. Heapbedingung überprüfen (Element an Position j muss größer sein

als Element an der Position j*2 und j*2+1).• 3. Wenn es notwendig ist, Elemente tauschen.• 4. Punkt 2 und 3 wiederholen, bis man die verglichenen Elemente nicht

mehr tauschen muss.• 5. Position um 1 vermindern.• 6. Punkt 1 bis 5 wiederholen, bis man die erste Position erreicht.

Danach werden sie in der richtigen Reihenfolge entfernt, und das jeweiligeentfernte Element wird gespeichert („Top-down-Heap“):

• 1. Erstes Element mit letztem Element tauschen.• 2. Neuen Heap aufbauen, ohne das letzte Element zu berücksichtigen.

Der Heapsort ist eine effiziente Sortiermethode (es gibt keineungünstigen Fälle, es ist kein zusätzlicher Speicherplatz not-wendig), allerdings ist er nur halb so schnell wie der Quicksort.

Die für eine Sortierung benötigte Zeit t = n × log (n), hängt also von derAnzahl n der zu sortierenden Elemente ab. Damit gehört Heapsort zu denschnellsten Sortieralgorithmen. Nur Quicksort ist noch schneller.

3.2 Suchalgorithmen

Suchen wird in der Informatik als Auffinden einer bestimmten Informationdefiniert. Dieser Begriff ist abzugrenzen von Durchsuchen (z.B. einer Dateioder eines Datenträgers), bei dem jedes Element genau einmal bearbeitetwird. Suchalgorithmen sind Verfahren um in einem Datenbestand Objektezu finden, die eine bestimmte Bedingung – das Suchkriterium – erfüllen.

Die folgenden Suchalgorithmen sind verbreitet:

• lineare (sequentielle) Suche,• binäre Suche und die• Suche auf einem (binären) Baum.

Oft wird in diesem Zusammenhang von einem „Schlüssel“ gesprochen, derdie Datensätze kurz und eindeutig kennzeichnen soll.



72

3.2.1 Lineare Suche

Bei einer linearen Suche werden sequentiell (nacheinander) die Objekteeines „Behälters“ durchgesehen – bis ein Objekt gefunden wird, das dasSuchkriterium erfüllt. Anschließend wird in gleicher Weise fortgesetzt, umweitere Objekte zu finden. Dieses Verfahren ist einfach, aber zeitaufwendig.

Allgemein lässt sich dieses Suchproblem so definieren:

• In einem Behälter B befindet sich eine Anzahl von Elementen,• Prüfe, ob ein Element e ∈ Β existiert, das die Eigenschaft E(e) erfüllt

„Behälter“ kann dabei eine beliebige Datenstruktur sein, wie z.B. Listen,Arrays, Mengen, Bäume, Graphen usw., der Anfangszustand des Behälterskann sowohl sortiert als auch unsortiert sein. Jedes Element wird einmal„angefasst“ und überprüft. Der ungünstigste Fall (worst case) kann dannsein, das alle Elemente einmal angefasst werden müssen.

Vorteile:

• einfach zu programmieren;• ist bei einfachen und kurzen Listen schneller als die binäre Suche.

Nachteile:

• ist nicht geeignet für das Suchen in verketteten Listen und Bäumen;• Zeitaufwand ist linear ansteigend, das Verfahren wird daher langsam.

3.2.2 Binäre Suche

In einer auf- oder absteigend sortierten Liste wird fortgesetzt der Bereichhalbiert, in dem sich ein gesuchtes Objekt noch befinden kann. Ein solcherAlgorithmus arbeitet schnell, da er bereits mit wenigen Schritten zum Zielkommt: Eine Verdoppelung der Objektzahl erfordert im Mittel lediglicheine zusätzliche Bereichshalbierung.

Beispiel: Suchen einer Telefonnummer in einem Telefonbuch:

• Aufschlagen des Telefonbuches in der Mitte,• nachschauen, ob der gesuchte Name in der linken oder in der rechten

Hälfte vorkommt,• dann wiederholen des Vorganges mit der entsprechenden Hälfte, bis der

Name gefunden wird.• Meistens (spätestens) nach dem 10. Vergleich fündig.



73

3.2.3 Suche auf einem binären Baum

Alle Objekte werden aus einer nach dem Suchkriterium vorsortierten undaufsteigend nummerierten Liste in einen binären Baum (Kapitel 2.6.3.6) soeinsortiert, dass die Einträge des linken Teilbaums kleinere Listennummernals der übergeordnete Knoteneintrag aufweisen. Entsprechend weisen dieEinträge des rechten Teilbaums nach dem Knoteneintrag größere Einträgeauf und das für alle Knoten. Die Suche beginnt oben an der Baumwurzel:Erfüllt der Wurzeleintrag das Suchkriterium, ist die Suche sofort erfolgreich.Wird nach einer kleineren Nummer als der des Wurzeleintrags gesucht, dannverzweigt man im Baum nach links in die nächste Knotenebene, sonst nachrechts. Anschließend setzt man an dem erreichten Knoten in gleicher Weisefort. Diese Suche endet nach (spätestens) so vielen Abfragen, wie Verzwei-gungen möglich sind. Damit ist die Suche auf einem binären Baum ein sehreffizienter Suchalgorithmus.

Bei der Suche auf nicht binären, aber geordneten Baumstrukturen wie z.B.dem B-Baum können ähnliche Suchalgorithmen verwendet werden. Aberzusätzlich werden alle Nachfolger eines Knotens wie bei einer geordnetenListe durchsucht.

Ein Baum, der speziell für effizientes Suchen eingerichtet ist,wird als Suchbaum bezeichnet.

Von Bedeutung ist auch das Hash-Verfahren: Dabei handelt es sich um einkombiniertes Speicherungs- und Suchverfahren, bei dem Datensätzegestreut gespeichert und die Adressen von Datensätzen aus den zugehörigenSchlüsseln errechnet werden. Gestreute Speicherung von Datensätzenbedeutet, dass bezüglich einer Nummerierung der gespeicherten Datensätzenach den Schlüsseln Lücken auftreten. Solche sind praktisch nur mit großemAufwand zu vermeiden, wenn die Menge aller möglichen Schlüssel wesent-lich größer als die Zahl der Datensätze ist. Eine direkte Adressierung derDatensätze nach den Schlüsseln hätte aber den Nachteil, dass unnötig vieleSpeicheradressen zur Verfügung gestellt werden müssen. Daher werdenbeim Hash-Verfahren die Datensätze einem Speicherbereich von passenderGröße zugeteilt. Die Adressierung erfolgt indirekt, d.h. über eine Vorschrift,wie sich die Adresse aus den Schlüsseln berechnet. Diese Vorschrift wirdHash-Funktion genannt und wird so entworfen, dass die Adressen schnellzu berechnen sind und sich die Adressen gleichmäßig auf den Speicherbereichverteilen. Die Auflistung aller Funktionswerte einer Hash-Funktion wirdHash-Tabelle genannt. Hash-Verfahren werden auch bei Schachprogram-men verwendet, um identische Stellungen zu finden, die durch verschiedeneZugfolgen (die die Schlüssel bilden) erreicht werden.



74

4 Modulkurzzusammenfassung

Algorithmen und Datenstrukturen sind zentral für die ganze Informatik. EinAlgorithmus dient zur Lösung allgemeiner Probleme und muss diskret,determiniert, eindeutig und endlich sein.

Darstellungsmöglichkeiten von Algorithmen umfassen die Pseudo-CodeNotation, Programmablaufplan (PAP) und Struktogramm. Im Software-Engineering (Modul 6) wird hauptsächlich mit so genannten Daten- undFunktionsmodellierungsmodellen gearbeitet (ERM, SADT, UML).

Algorithmen werden entwickelt, indem Kontrollelemente zu komplexerenAbläufen zusammengesetzt werden: Elementare Operation (Verarbeitung),Sequenz (Abfolge) und Wiederholung (Schleife) reichen, um alles program-mieren zu können, was überhaupt programmierbar ist. Komfortabel sindzusätzlich die parallele Ausführung, bedingte Ausführung, Unterprogrammund Rekursion.

Eine Konstante ist ein Datenelement, dessen Wert sich bei der Ausführungeines Programms nicht ändert. Eine Variable hingegen ist ein Datenelement,dessen Wert sich während der Ausführung eines Programms ändern kann.

Der Datentyp legt die Art der gespeicherten Information und deren Aus-wertemöglichkeit fest. Idealisierte Datentypen sind durch den beschränk-ten Speicherplatz in Computern nicht darstellbar, können jedoch für dentheoretischen Entwurf von Algorithmen hilfreich sein.

Die konkreten Datentypen werden oft als „die“ Datentypen bezeichnetund unterteilen sich in einfache Datentypen, strukturierte Datentypen undZeigerdatentypen.

Einfache Datentypen sind die elementaren Grundbausteine aller weiterenDaten. Sie sind nur als Ganzes manipulierbar und nicht weiter zerlegbar. Sieunterteilen sich in zwei Unterarten: ordinale Datentypen und Real-Datenty-pen. Zu den ordinalen Datentypen zählen: BOOLEAN, INTEGER undCHAR sowie die durch Einschränkung abgeleiteten Aufzählungsdatentypenund Teilbereichsdatentypen.

In vielen Programmiersprachen können beliebig zusammengesetzte Daten-strukturen definiert und durch eigene Variable bezeichnet werden. Zu denstrukturierten Datentypen zählen: Mengen, Arrays, Listen und Matrizen;Tabellen und Relationen; Bäume und Graphen; Files; Programme undObjekte, Klassen und Methoden.



75

5 Modulanhang

5.1 Literatur

5.1.1 Bücher

AHO, ALFRED V.; ULLMAN, JEFFREY D. (1997): Informatik. Datenstrukturen und Konzep-te der Abstraktion. Bonn: MITP-Verlag.

BALZERT, HELMUT (1999): Lehrbuch Grundlagen der Informatik: Konzepte und Notationenin UML, Java und C++, Algorithmik und Softwaretechnik und Anwendungen. Berlin u.a.:Spektrum Akademischer Verlag. 467–652.

BREUER, HANS (1995): dtv-Atlas zur Informatik: Tafeln und Texte. München: DeutscherTaschenbuch Verlag. 53–55.

ERNST, HARTMUT (2000): Grundlagen und Konzepte der Informatik. Braunschweig:Vieweg. 410–661.

FUTSCHEK, GERALD (1989): Programmentwicklung und Verifikation. Berlin, Heidelberg,New York: Springer.

GOLDSCHLAGER, LES; LISTER, ANDREW (1990): Informatik – Eine moderne Einführung.3. Auflage. München, Wien u.a.: Hanser Prentice Hall International.

GOOS, GERHARD (2001): Vorlesungen über Informatik Band 2: Objektorientiertes Program-mieren und Algorithmen. 3. Auflage. Berlin: Springer.

GUMM, HEINZ-PETER; SOMMER, MANFRED (2000): Einführung in die Informatik.4. Auflage. München, Wien: Oldenbourg. 271–356.

HEUN, VOLKER (2000): Grundlegende Algorithmen: Einführung in den Entwurf und die Ana-lyse effizienter Algorithmen. Braunschweig: Vieweg.

JUNGNICKEL, D. (1990): Graphen, Netzwerke und Algorithmen. Mannheim, Wien, Zü-rich: BI-Wissenschaftsverlag.

MEHLHORN, K. (1988): Datenstrukturen und effiziente Algorithmen. Band 1: Sortieren undSuchen. Stuttgart: Teubner.

OTTMANN, THOMAS; WIDMAYER, P. (2002): Algorithmen und Datenstrukturen. Heidel-berg u.a.: Spektrum.

OTTMANN, THOMAS, Hrsg. (1998): Prinzipien des Algorithmenentwurfs. Heidelberg:Spektrum.

SAAKE, GUNTER; SATTLER, KAI-UWE (2001): Algorithmen & Datenstrukturen: EineEinführung mit Java. Hannover: Heise.



76

SEDGEWICK, ROBERT (1992): Algorithmen in C++. Bonn: Addison Wesley.

SOLYMOSI, ANDREAS; GRUDE, ULRICH (2000): Grundkurs Algorithmen und Datenstruk-turen: Eine Einführung in die praktische Informatik mit Java. Stuttgart: Vieweg.

WIRTH, NIKOLAUS (1983): Algorithmen und Datenstrukturen. Stuttgart: Teubner.

5.1.2 Artikel

BRANDENBURG, FRANZ J.; JÜNGER, MICHAEL; MUTZEL, PETRA (1997): Algorith-men zum automatischen Zeichnen von Graphen. Informatik-Spektrum, Vol. 20, Iss. 4,199–207.

RAUH, OTTO (1995): ERMded – eine Erweiterung des Entity-Relationship-Modellszur Modellierung deduktiver Informationssysteme. Informatik Forschung und Entwick-lung, Vol. 10, Iss. 3, 128–138.

ZIEGLER, BERNHARD (1996): ESS – Ein schneller Algorithmus zur Mustersuche inZeichenfolgen. Informatik Forschung und Entwicklung, Vol. 11, Iss. 2, 69–83.

ZELLER, ANDREAS (2001): Datenstrukturen visualisieren und animieren mit DDD.Informatik Forschung und Entwicklung, Vol. 16, Iss. 2, 65–75.

5.1.3 Books in English

AHO, A. V. ; HOPCROFT, J. E.; ULLMAN, J. D. (1974): The Design and Analysis of Com-puter Algorithms. Reading (MA): Addison-Wesley.

AHUJA, RAVINDRA K.; MAGNANTI, THOMAS L.; ORLIN, JAMES B. (1993): NetworkFlows: Theory, Algorithms, and Applications. Englewood Cliffs (NJ): Prentice Hall.

CORMEN, THOMAS H.; LEISERSON, CHARLES E.; RIVEST, RONALD L. (1990): Intro-duction to Algorithms. Boston (MA): MIT Press.

DAHL, O.-J.; DIJKSTRA, E. W.; HOARE, C. A. R. (1972): Structured Programming. Lon-don, New York: Academic Press.

GOODRICH, M. T.; TAMASSIA, R. (1998): Data Structures and Algorithms in Java. NewYork: Wiley.

HOROWITZ, ELLIS; SAHNI, SARTAJ (1983): Fundamentals of Data Structures. New York:Computer Science Press.

KNUTH, D. E. (1973): The Art of Computer Programming: Volume 1: Fundamental Algo-rithms. Reading (MA): Addison Wesley.

KNUTH, D. E. (1981): The Art of Computer Programming: Volume 2: Seminumerical algo-rithms. Reading (MA): Addison Wesley.



77

KOZEN, DEXTER C. (1991): The design and analysis of algorithms (Texts and Monographs inComputer Science). Berlin et al.: Springer.

MEHLHORN, KURT (1984): Data structures and algorithms 1: Sorting and searching(EATCS Monographs on Theoretical Computer Science). Berlin et al.: Springer.

MEHLHORN, KURT (1984): Data structures and algorithms 2: Graph algorithms and NP-Completeness (EATCS Monographs on Theoretical Computer Science). Berlin et al.: Springer.

PAPADIMITRIOU, CHRISTOS H.; STEIGLITZ, KENNETH (1982): Combinatorial optimiza-tion: Algorithms and complexity. Englewood Cliffs (NJ): Prentice-Hall.

SEDGEWICK, ROBERT (1997): Algorithms in C. Reading (MA): Addison-Wesley.

SHAFFER, CLIFFORD A. (1997): A Practical Introduction to Data Structures and AlgorithmAnalysis: C++ Version. London: Prentice Hall.

SHAFFER, CLIFFORD A. (1998): A Practical Introduction to Data Structures and AlgorithmAnalysis: Java Edition. London: Prentice Hall.

STANDISH, THOMAS (1998): Data Structures in Java. Addison-Wesley.

5.1.4 Articles in English

AGARWAL, PANKAJ K.; SHARIR, MICHA (1998): Efficient Algorithms for GeometricOptimization. ACM Computing Surveys, 30 (4), 412–458.

BOYER, R. S.; MOORE, J. S. (1977): A fast string searching algorithm. Communcationsof the ACM, 20 (10).

GAEDE, VOLKER; GÜNTHER, OLIVER (1998): Multidimensional Access Methods.ACM Computing Surveys, 30 (2), 170–231.

GUPTA, P.; CHAKRABARTI, P. P.; GHOSE, S. (1992): The Towers of Hanoi: Genera-lizations, Specializations, Algorithms. Int. Journal of Computer Mathematics, 46, 149–161.

HOARE, C. A. R. (1961): Algorithm 64: Quicksort. Communications of the ACM, Vol. 4,Iss. 7, 321.

HOARE, C. A. R. (1971): Proof of a program: FIND. Communications of the ACM, Vol.14, Iss. 1, 39–45.

SCANLAN, D. A. (1989): Structured flowcharts outperform pseudocode: An experi-mental comparison. IEEE Software, 6, 28-36.

WIERINGA, ROEL (1998): A Survey of Structured and Object-Oriented SoftwareSpecification Methods and Techniques. ACM Computing Surveys, 30 (4), 459–527.



78

5.1.5 Journals

Algorithmica (ISSN: 0178-4617 printed version; ISSN: 1432-0541 electronic version)| Springer

Theory of Computing Systems, vorher: Mathematical Systems Theory (ISSN 1432-4350) | Springer

Acta Informatica (ISSN: 0001-5903 printed version; ISSN: 1432-0525 electronic ver-sion) | Springer

Discrete Applied Mathematics (ISSN: 0166-218X) | Elsevier

Information Processing Letters (ISSN: 0020-0190) | Elsevier

Informatik Forschung und Entwicklung (ISSN 0178-3564) Springer

5.2 Internet-Links

Aktualisierte Internet-Links zu diesem Modul sind auf der Buchhomepagewww.basiswissen-it.at unter IK – Modul 1: Algorithmen & Datenstruk-turen verfügbar!

5.3 Prüfungsfragen

Fragen-Typ 1: Dichotome Ja/Nein-Entscheidungen:

01 Determiniertheit heißt, dass bei gleichen Anfangs- und Rand-bedingungen stets dasselbe Endergebnis erhalten wird.

Ja Nein

02 Ein Datentyp beschreibt eine Verzweigung aufgrund einer eindeutigen Bedingung (Grundtyp).

Ja Nein

03 Struktogramme beschreiben den formalen Aufbau einer Datenstruktur und den formalen Aufbau einer Programmiersprache.

Ja Nein

04 Konstante repräsentieren einen Wert, der vor Programmausführung festgelegt wird und sich zur Ausführungszeit des Algorithmus ändert.

Ja Nein

05 Der Datentyp BOOLEAN umfasst nur die Werte TRUE (wahr) und FALSE (falsch).

Ja Nein

06 Der Datentyp INTEGER ist ein vordefinierter Datentyp und dient zur Darstellung von reellen Zahlen.

Ja Nein

07 Ein eindimensionales Array wird auch Feld genannt und entspricht einem Vektor, ein mehrdimensionales Array entspricht einer Matrix.

Ja Nein

08 Bubblesort ist eine Erweiterung des Insertion Sort und ist ein vollständiger binärer Baum.

Ja Nein

09 Ein Baum ist ein gerichteter Graph mit Knoten, auf die, bis auf eine Ausnahme, nur jeweils eine Kante zeigt.

Ja Nein

10 Quicksort besteht aus dem Zerlegen einer Datei in zwei Teile und dem anschließenden Sortieren der Teile unabhängig voneinander.

Ja Nein



79

Fragen-Typ 2: Mehrfachauswahlantworten (Multiple Choice):

5.4 Lösungen

Lösungen zu Fragen-Typ 1: 01 Ja; 02 Nein; 03 Nein; 04 Nein; 05 Ja; 06 Nein;07 Ja; 08 Nein; 09 Ja; 10 Nein

Lösungen zu Fragen-Typ 2: Richtig sind: 01 b) c); 02 b) c); 03 b); 04 d); 05a) b) d) 06 a); 07 a) b); 08 a) d

01 Beispiele für Algorithmen sind ... a) ... das Sortieren von Briefen. b) ... die Anleitung zur Behebung von Startproblemen bei Autos. c) ... die Regeln der Differentialrechnung. d) ... die Berechnung der Oberfläche einer Dose.

02 Zu den elementaren Datentypen zählen ... a) ... Graphen. b) ... Byte. c) ... Zeichen. d) ... Mengen.

03 Es kann alles programmiert werden mit den Elementen ... a) ... Rekursion + Verarbeitung + Sequenz. b) ... Verarbeitung + Wiederholung + Sequenz. c) ... Verarbeitung + Auswahl + Sequenz. d) ... Sequenz + Wiederholung + bedingter Ausführung.

04 Struktogramme ... a) ... sind auch bei komplexen Problemstellungen sehr übersichtlich. b) ... sind gut zur Darstellung parallel ablaufender Prozesse geeignet. c) ... sind zur Darstellung von Entwicklungsprozessen gut geeignet. d) ... dienen zur Veranschaulichung von Programmabläufen.

05 Zu den strukturierten Datentypen zählen ... a) ... Mengen. b) ... Graphen. c) ... Real-Datentyp. d) ... Files.

06 Ordinale Datentypen umfassen ... a) ... Aufzählungsdatentypen. b) ... Zeigerdatentypen. c) ... Objekte, Klassen und Methoden. d) ... Tabellen und Relationen.

07 Ausführbare Programme sind ... a) ... spezielle geordnete Mengen von Daten. b) ... spezielle geordnete Mengen von (physikalischen) Bytes. c) ... Ansammlungen elementarer Datentypen. d) ... lineare Folgen von Einzelelementen.

08 Gebräuchliche Operationen auf Listen sind ... a) ... das Erzeugen eines Listenknotens. b) ... das Erzeugen eines Baumknotens. c) ... das Traversieren des Baumes. d) ... das Verweisen auf den Vorgänger bzw. Nachfolger.



80

5.5 Übungen• Entwickeln Sie einen Algorithmus, der zwei Namenslisten vergleicht und

die doppelt vorhandenen Namen in eine dritte Liste schreibt. Bei mehr-fachem Aufscheinen gleicher Namen soll dieser nur einmal aufscheinen.

• Entwickeln Sie für eine (beliebige) Aufgabenstellung einen Programm-ablaufplan und ein Struktogramm. Vergleichen Sie nun die beiden Dar-stellungen und überlegen Sie deren Vorteile und Nachteile!

• Vergleichen Sie verschiedene Sortieralgorithmen. Stellen Sie in einer Ta-belle deren Vorteile und Nachteile gegenüber und messen Sie derenLaufzeit. Was fällt Ihnen auf?

5.6 Diskussionsfragen• Informieren Sie sich zuerst über Algorithmen zur Lösung von linearen

Gleichungssystemen und diskutieren Sie dann in der Gruppe darüber!Welche Ansätze sind vorteilhafter? Was gilt es zu beachten?

• Bilden Sie zwei Gruppen. Diskutieren Sie die Bedeutung des Gebietes„Algorithmen und Datenstrukturen“ für die Informatik. Eine Gruppe„verteidigt“ die Position – die andere „attackiert“.

• Jeder von Ihnen „übernimmt“ einen Datentyp und präsentiert diesender Gruppe. Jeder soll versuchen, „seinen“ Datentyp möglichst positivdarzustellen. Jemand versucht nun, die Datentypen schlecht zu machen.

5.7 Timeline: Algorithmen und Datenstrukturen1700 v. Chr. Papyrus Rhind: älteste schriftliche Rechenaufgabe (Ägypten).

300 v. Chr. EUKLID (365–300 v.Chr.) beschreibt einen Algorithmus zur Bestimmungdes größten gemeinsamen Teilers (ggT) in seinem 7. Buch der Elemente.

230 v. Chr. ERATHOSTENES (276–197 v.Chr.) entwickelt einen Algorithmus zurBerechnung von Primzahlen (Sieb des Erathostenes).

800 MOHAMMED IBN MUSA ABU DJAFAR AL CHORESMI (780–850) beschreibt Vor-gehensweisen für Testamentsvollstreckungen. Bildung des Begriffs Algorithmus ausseinem Namen und dem griechischen „arithmo“ für Zahl.

1574 Sammlung von Algorithmen im Rechenbuch von ADAM RIES (1492–1559).

1614 Nach 30 Jahren Arbeit wird die erste Logarithmentafel erstellt.

1703 Binäres Zahlensystem von LEIBNIZ.

1931 Unvollständigkeitssatz von GÖDEL.

1936 Church'sche These.

1960 HOARE stellt den Bubblesort-Algorithmus vor.

1972 Entwicklung der NP-Vollständigkeit zur Beschreibung algorithmischer Com-puter-Probleme.



81

5.8 Glossar

Algorithmus Beschreibung eines Informationsverarbeitungsmodells oder Prozess-ablaufs in einer Form, die von einer Maschine ausgeführt werden kann.

Array (Feldtyp) ist die endliche Aneinanderreihung von Datenelementen gleicherArt in einem zusammenhängenden Speicherbereich. Zugriff mit Hilfe eines Index.

Anweisung (statement) Bestandteile eines Blocks: Kontrollstruktur, Definition oderAusdruck.

Ausdruck (expression) Vorschrift zur Berechnung eines Wertes durch Kombinationvon Unterausdrücken mit Operatoren oder Funktionsaufrufen. Liefert einen Wert.

Aufzählungstyp (enumeration type) ist ein Datentyp, dessen Wertebereich voll-ständig durch die Aufzählung der Einzelelemente beschrieben wird. Durch die Rei-henfolge der Aufzählung wird eine Ordnungsrelation definiert.

average case ist eine Betrachtungsweise bei der Komplexitätsanalyse von Algorith-men, die sich am Erwartungswert des Betriebsmittelverbrauchs bei der Ausführungeines Algorithmus orientiert.

Baum ist eine nichtlineare Datenstruktur, die aus einer Menge von Knoten und auseiner Menge von diese verbindenden, gerichteten Kanten besteht. Bäume werdenhauptsächlich zur Abbildung hierarchischer Beziehungen innerhalb großer Daten-mengen oder zur Modellierung rekursiver Objektstrukturen verwendet.

Benutzerdefinierter Typ (user defined type) Typ, der als Klasse, Aufzählungstypoder durch eine Typdeklaration eingeführt wird.

Bezeichner (identifier) Name der sich auf eine Variable, einen Typ oder eine Funk-tion bezieht.

Block eine Liste von Anweisungen, die den Gültigkeitsbereich aller lokal definier-ten Bezeichner begrenzt.

binärer Baum ist ein spezieller k-närer Baum (siehe dort), der Ordnung 2. JederKnoten mit Ausnahme der Blätter besitzt höchstens zwei und mindestens einenNachfolger. Da jeder k-näre Baum in einen binären Baum durch Anwendung geeig-neter Transformationsregeln überführt werden kann, werden hier hauptsächlichDarstellungsformen und Operationen für binäre Bäume behandelt.

binäre Suche ist eine Art der Suche, bei der ein nach dem Primärschlüssel aufstei-gend oder absteigend sortierter Datenbestand sukzessive in zwei Hälften aufgeteiltwird. Das jeweils mittlere Element der aktuellen Bestandshälfte wird mit demSuchschlüssel verglichen, das Ergebnis dieses Vergleichs gibt an, ob in der vom mitt-leren Element ausgehenden linken oder rechten Bestandshälfte weitergesucht wird.



82

BOOLEAN Aufzählungstyp, dessen Wertebereich ausschließlich aus den Wahr-heitswerten FALSE und TRUE besteht.

Bubblesort ist das Sortieren durch Austauschen.

CHAR Datentyp, dessen Wertebereich den im Rechner darstellbaren Zeichenvorratumfasst (z.B. ASCII-Code).

DATA Schlüsselwort bei der Formulierung von Algorithmen, das den Beginn desDatenobjektteils anzeigt.

Datenstruktur ist die einfache bzw. komplexe verschachtelte Anordnung von Da-tenobjekten.

Datentyp ist eine Zusammenfassung von Datenobjekten gleicher Art und dazuge-hörigen Operationen zu einer begrifflichen Einheit, die es ermöglicht, Objekte alsVertreter einer bestimmten Objektmenge zu identifizieren, untereinander zu unter-scheiden und Manipulationen für die „Klasse“ von Objekten zu formulieren.

Graph ist eine nichtlineare Datenstruktur aus Knoten und Kanten. Die Kanten ei-nes Graphen können sowohl ungerichtet (ungerichteter Graph) als auch gerichtet(gerichteter Graph) sein. Bäume können und werden meistens als spezielle gerichteteGraphen aufgefasst. Im Unterschied zu Bäumen können zwei Knoten eines Gra-phen auch durch mehrere verschiedene Kantenfolgen verbunden sein.

Hashfunktion ist eine Funktion, die aus einem Primärschlüssel die (relative)Adresse berechnet, an der ein Datensatz auf einem direkt adressierbaren Speicher-medium abgelegt werden soll. Bei der direkten Adressierung ist die Hashfunktionumkehrbar eindeutig, d.h., es gibt zu jedem Primärschlüssel genau eine Adresse undumgekehrt. Bei der indirekten Adressierung können mehrere unterschiedliche Pri-märschlüssel auf die gleiche Adresse abgebildet werden, es ist daher eine Kollisions-behandlung erforderlich.

Heapsort ist ein Sortierverfahren, das sich die Effizienzvorteile von Binärbäumenbei Vergleichs- und Suchoperationen in großen Datenbeständen zu eigen macht. Diezu sortierende Objektmenge wird in ein Feld (Array) übertragen, das als ein Binär-baum in schichtenweiser Darstellung mit niveauweiser Nummerierung angesehenwird. Anschließend werden, ausgehend von den Blättern, die Elemente so ver-tauscht, dass die Wurzel eines jeden Teilbaums, jeweils den Datensatz mit dem größ-ten Schlüssel enthält. Der Heapsort weist ein günstiges Verhalten im worst case auf.

Heterogener zusammengesetzter Typ ist ein zusammengesetzter Datentyp mitElementen von möglicherweise unterschiedlichen Typen, z.B. eine Klasse.

Homogener zusammengesetzter Typ ist ein zusammengesetzter Datentyp mitlauter Elementen vom gleichen Typ, z.B. ein Array.

Invariante ist ein logischer Ausdruck, der immer gültig ist, z.B. eine Schleifeninva-riante (bei jedem Schleifendurchlauf gültig) oder Klasseninvariante (vor und nach je-dem Methodenaufruf gültig).



83

k-närer Baum ist ein Baum, für den gilt: Von jedem Knoten außer einem Blattkno-ten gehen maximal k Kanten aus, jeder Knoten besitzt damit höchstens k Söhne. DerParameter k heißt auch Ordnung des Baumes. Von einem geordneten k-nären Baumspricht man, wenn die Knoten in einer bestimmten, eindeutigen Reihenfolge notiertoder bezeichnet werden (z.B. alfabetisch, Väter vor Söhnen, Söhne vor Brüdern).

Kante ist die gerichtete oder ungerichtete Verbindung zwischen genau zwei Daten-objekten oder Knoten einer nichtlinearen Datenstruktur. Diese Verbindung kannz.B. hierarchische Beziehungen, Transformationen, die Anwendung von Operatorenoder Zustandsübergänge zwischen den Knoten zum Ausdruck bringen. Ist ein Kno-ten k von einem Knoten v aus über eine zusammenhängende Folge von Kanten zuerreichen, so bezeichnet man den Knoten v auch als (ggf. mittelbaren) Vorgängervon Knoten k und umgekehrt Knoten k als (ggf. mittelbaren) Nachfolger von Kno-ten v. In Bäumen stellen Kanten gerichtete Vater-Sohn-Beziehungen dar.

Knoten sind Elemente eines Graphen oder Baumes, die aus Datenobjekten belie-biger Komplexität zusammengesetzt sein können. Die in einzelnen Knoten oder inmehreren durch Kanten verbundenen Knoten abgelegte Information beschreibtProzesse, Sachverhalte oder (hierarchische) Zusammenhänge aus der realen Welt.

Kontrollstruktur ist ein schachtelbares Sprachmittel zum Modifizieren der norma-len, linearen Abwicklung von Anweisungen (z.B. Verzweigungen, Schleifen usw.).

Implementierung ist die Übersetzung der erarbeiteten Datenmodelle und Daten-verarbeitungsprozesse in eine von einem Computer ausführbare Form und derenEinbindung in die bereits bestehende Informationsstruktur.

INTEGER ist ein Standarddatentyp, der den computerintern darstellbaren Aus-schnitt aus der Menge der ganzen Zahlen angibt.

Komplexität von Algorithmen beschreibt Speicherplatzbedarf und die Laufzeit inAbhängigkeit von der eingegebenen Problemgröße n. Da das Verhalten des Algo-rithmus bei wachsender Problemgröße n meist nicht präzise angegeben werdenkann, wird versucht, das Wachstumsverhalten auf eine bekannte Funktion g(n) zu-rückzuführen. Die so genannte O-Notation f(n) = O(g(n)) bringt zum Ausdruck,dass durch g(n) eine obere Grenze für die Anzahl der nötigen Elementaroperationenf(n) bei wachsender Problemgröße angegeben wird.

Notation von Algorithmen ist die Darstellung von Algorithmen in verbaler, quasi-formaler oder grafischer Form. Gebräuchliche Notationsformen sind Pseudocode,Struktogramme und Flussdiagramme. Nach BÖHM und JACOPINI gibt es für jedenAlgorithmus eine äquivalente Darstellung, die mit den Strukturblöcken Sequenz,Wiederholung und Verzweigung auskommt.

Nachfolger heißt ein Knoten n, wenn dieser von einem Knoten k aus über einezusammenhängende Folge von q Kanten zu erreichen ist, falls q = 1. Er wird als mit-telbarer Nachfolger von k bezeichnet, falls q > 1 ist. Die Nachfolger eines Knotenswerden auch als Söhne dieses Knoten bezeichnet.



84

Notation ist eine bestimmte Darstellungsform von Information durch Symbole, wiezum Beispiel zum Aufzeichnen von Noten, von Schachpartien oder von mathema-tischen Modellen. Die Notation einer Programmiersprache bestimmt die zulässigenSprachelemente, wie z.B.: Konstante, Ausdrücke und Anweisungen und teilweise dieSyntax.

Quicksort Sortierverfahren, das auf den Prinzipien Austauschen und Zerlegen beruht.

Rekursion ist die Definition einer Datenstruktur, eines Verfahrens (Algorithmus)oder einer (mathematischen) Funktion durch sich selbst. Eine rekursive Verfahrens-vorschrift besteht in der Regel aus einer Terminationsbedingung, einer optionalenAusführungsanweisung und einem Selbstaufruf. Die wohl bekannteste rekursiv for-mulierte Funktion ist folgende Vorschrift zur Fakultätsberechnung: n! = n ((n – 1)!)mit der Terminationsbedingung 0! = 1.

Sortieren ist die Umordnung einer Menge von Objekten oder Datensätzen so, dassdie Objekte entsprechend einer Ordnungsrelation (numerisch, lexikografisch) auf-oder absteigend angeordnet sind. Befindet sich der zu sortierende Datenbestand zumZeitpunkt des Umordnens vollständig im Hauptspeicher, so spricht man von eineminternen Sortierverfahren, andernfalls von einem externen Sortierverfahren.

Suche ist das Auffinden eines oder aller Datenobjekte in einem Datenbestand, dieein bestimmtes Suchkriterium erfüllen. Die Effizienz der Suche wird von der Art desSuchkriteriums (einfacher oder zusammengesetzter Schlüssel), dem benutzten Such-verfahren und von der Organisation des Datenbestandes bestimmt.

Suchbaum ist eine nichtlineare Datenstruktur, in der durch Schlüssel identifizierteDatenobjekte auf effiziente Weise ordnungserhaltend eingefügt und gefunden werdenkönnen. Über die Menge aller vorhandenen Schlüssel muss eine lineare Ordnungsrela-tion (größer, gleich oder kleiner) definiert sein. Suchbäume werden meist als Binärbäumedargestellt, in denen jeder Knoten einen einzigen Schlüsseleintrag s enthält. Bei derSuche nach einem eindeutigen Schlüssel x wird in jedem Knoten des Suchbaumeszum linken Nachfolger verzweigt, wenn x kleiner ist als der Schlüsseleintrag s im ak-tuell betrachteten Knoten, und nach rechts verzweigt, wenn x größer ist als s. DieKomplexität der Schlüsselvergleiche ist damit durch O(ld n) gegeben. Um die Sor-tierfolge aller Datenobjekte zu erhalten, ist der Suchbaum lediglich in symmetrischerOrdnung zu traversieren (inorder).

Traversieren von Bäumen: Da man bei den gebräuchlichen Darstellungs- und Spei-cherungsformen für Bäume auf einzelne Knoten nur indirekt, von der Wurzel aus,zugreifen kann, ist es nötig, einen Baum in einer bestimmten Reihenfolge so zudurchlaufen, dass jeder Knoten genau einmal aufgesucht und ausgewertet wird. Nor-malerweise werden drei verschiedene Vorgehensweisen für das Durchlaufen einesBinärbaumes in Betracht gezogen: das Traversieren in Präordnung, in Postordungund in symmetrischer Ordnung. Allen Vorgehensweisen ist gemeinsam, dass der Bi-närbaum in jedem Knoten k in drei Elemente aufgeteilt wird: den von k ausgehendenrechten Teilbaum, die Wurzel k und den von k ausgehenden linken Teilbaum. Damitlassen sich Traversierungsalgorithmen relativ leicht rekursiv formulieren, indem dieReihenfolge des Abarbeitens der genannten drei Elemente festgelegt wird.



85

REAL ist ein Datentyp, der die im Rechner darstellbare Teilmenge der reellen Zah-len angibt.

Record (Verbund, Satz) ist die Zusammenfassung von mehreren, auch unterschied-lichen Datentypen zu einem neuen Datentyp. Die einzelnen Komponenten des Ver-bunds können mit Hilfe der Punktqualifizierung angesprochen werden (z.B.person.name).

Schlange (engl. queue) ist eine lineare Datenstruktur, mit der eine Folge von Daten-objekten eines bestimmten Datentyps nach dem „first-in-first-out“-Prinzip verwaltetwird. Neu hinzu kommende Elemente werden stets am Ende der Folge angefügt(Operation append). Entfernt werden Elemente ausschließlich am Anfang der Folge(Operation remove). Die Schlange lässt sich wie der Stapel als sequentielle oder alsverkettete Liste organisieren.

Set oder Mengentyp ist ein Datentyp, der eine Menge von Objekten im Sinne derMengenlehre nachbildet. Die Elemente der Menge gehören alle einem einfachen or-dinalen Datentyp an.

Stack (Stapel) ist eine lineare Datenstruktur, bei der eine Folge von Datenobjekteneines bestimmten Datentyps nach dem „last-in-first-out“-Prinzip verwaltet wird. Fürden Stapel gibt es in der Regel zwei grundlegende Operationen: Die Operation pushfügt neu hinzukommende Elemente stets am Ende der Folge an, die Operation popliefert das letzte in die Folge aufgenommene Element. Stapel können als sequentielleListe (statisches Feld) oder als verkettete Liste realisiert werden.

Standardtypen sind elementare Datentypen, die in den meisten (höheren) Program-miersprachen zur Verfügung gestellt werden. Hierzu gehören die Datentypen INTE-GER, REAL, CHAR und BOOLEAN.

Typ (type) Interpretation eines Bitmusters als Wert. Festlegung erlaubter Operatio-nen und der Auswirkungen dieser Operationen auf die Werte, d.h. Exemplare desTyps.

Typdeklaration (typedef) Neuer Bezeichner für einen anderen einfachen oder zu-sammengesetzten Typ.

Verkettete Liste ist eine Folge von Datenobjekten eines bestimmten Datentyps, beider jedes Datenobjekt aus einem Datenteil und einem Verweisteil besteht. Da im Ge-gensatz zur sequentiellen Liste die physikalische Aufeinanderfolge der Elementenicht mit der logischen Reihenfolge, die der zugrundegelegten Ordnungsrelation ent-spricht, übereinstimmt, ist eine Verzeigerung der Datenobjekte einzurichten: Ein zu-sätzliches, als Anker bezeichnetes Datenobjekt, verweist auf das erste Listenelement.In diesem sowie in jedem weiteren Element wird ein Verweis auf das Nachfolgerele-ment festgehalten. Der Zeiger des letzten Elements markiert das Ende der Liste(NIL). Werden in jedem Listenelement mehrere Verweise gepflegt, spricht man vondoppelt oder mehrfach verketteten Listen.



86

Zeichenkette (String) ist eine Zusammenhängende Folge von Zeichen aus einemendlichen Zeichenvorrat, die ein Phänomen der realen Welt repräsentiert. Im Rech-ner werden Zeichenketten in einem Array abgelegt; das Ende einer Zeichenkettewird in der Regel durch ein Sonderzeichen bestimmt.

Zeigertyp ist ein Datentyp, der einen Verweis (Zeiger, auf der Rechnerebene Adres-se) auf ein Datenobjekt eines zugrunde gelegten Datentyps beschreibt. Der Werte-bereich des Zeigers umfasst hierbei die möglichen Speicheradressen und den WertNIL. Ein Zeiger mit dem Wert NIL verweist auf kein Datenobjekt.

Zusammengesetzter Typ („compound type“) Typ, der aus Elementen zusammen-gesetzt ist. Gegenteil von primitivem Typ.

Vorgänger eines Knotens: Ist ein Knoten k von einem Knoten v aus über eine zu-sammenhängende Folge von q Kanten zu erreichen, so bezeichnet man den Knotenv als Vorgänger des Knotens k, falls q = 1, und als mittelbaren Vorgänger von k, fallsq > 1. Ein Vorgänger eines Knotens k wird auch als Vater von k bezeichnet.

Wurzel ist ein Datenobjekt oder Element eines Teilbaumes, zu dem kein Vorgängerexistiert. Von der Wurzel des Baumes aus können alle Knoten eines Baumes auf ge-nau einem Weg (d.h. einer zusammenhängenden endlichen Folge gerichteter Kan-ten) erreicht werden.


Documents

Modul 1: Algorithmen und DatenstrukturenWir lernen die Methoden und Konzepte kennen, die später für eine systematische Entwicklung von Software nötig sind. 1 Algorithmen 32 1.1