Datenstrukturen Objektorientiert Mit Modula-2

ISBN-13: 9783519029847 / Niemiecki / Miękka / 1994 / 204 str.

Werner Burhenne; Heinz-Erich Erbs; Werner Burhenne

Opis

Daten ohne Algorithmen sind wie Algorithmen ohne Daten: Eines sC) nutzlos wie das andere. Keines kann ohne das andere existieren. Genauso sind Objekte der (naturlichen) Umwelt stets mit Handlungen verbunden, seien sie moglich und zugelassen oder auch moglich und (z.T. lei der) verboten. Und dabei hat jedes Objekt seinen eigenen Satz von Handlungsmoglichkeiten: Was man mit dem einen Objekt machen kann, kann man mit einem anderen nicht oder zumin dest so nicht machen. Dass solch eine "naturliche" Beziehung zwischen Objekten und Handlun gen oder eben zwischen Daten und Algorithmen besteht, will dieses Buch zeigen. Dass es kei nen Sinn macht, das eine losgelost vom anderen zu entwickeln, will es auch nachweisen. Jede Entscheidung auf der einen Seite hat nunmal Konsequenzen fiir die andere Seite. Dem passt sich in dieser Zeit die Informatikausbildung an: Fruher ging es in der Erstausbildung allein um die algorithmische Aufbereitung eines Problems bis hin zur Implementation auf einer Rechenanlage mithilfe einer Programmiersprache. Datenstrukturen wurden eher am Rande oder sehr viel spater - etwa im Rahmen von Ausbildungsgangen wie z.B. "Einfiihrung in Da tenbanken" gelehrt und gelernt. Heutige Informatik-Studienprogramme wie z.B. das der Fach hochschule Darmstadt sehen eine moglichst fruhe Beschaftigung mit Datenstrukturen vor: Pa rallel zur Erstausbildung in der Implementation von Algorithmen lernen Studenten den syste matischen Entwurfvon Datenstrukturen kenn

Spis treści

1. Einführung.- 1.1. Begriffe.- 1.2. Definitionsmethoden.- 1.2.1. Die konstruktive Methode.- 1.2.2. Die axiomatische Methode.- 1.3. Klassifizierungen.- 1.4. Daten oder Ablauf: Was zuerst entwerfen?.- 2. Fundamentale Datentypen und Ablaufstrukturen.- 2.1. Anweisungen/Ablaufstrukturen in Modula-2.- 2.1.1. Elementare Anweisungen.- 2.1.2. Ablaufstrukturen.- 2.1.3. Zusätzliche Anweisungen.- 2.2. Elementare und strukturierte Datentypen einfacher Art.- 2.2.1. Einfache Datentypen.- 2.2.1.1. Die Standarddatentypen.- 2.2.1.2. Benutzerdefinierte Datentypen.- 2.2.1.3. Maschinennahe Datentypen.- 2.2.2. Der Reihentyp.- 2.2.3. Der Satztyp.- 2.2.4. Satztyp mit varianten Komponententypen.- 2.2.5. Der Mengentyp.- 2.3. Prozeduren und Rekursion.- 2.31 Das Prozedurenkonzept in Modula-2.- 2.3.2. Prozedur-Typ und Prozedurvariable.- 2.3.3. Rekursive Prozeduren.- 2.4. Anwendung: Sortieren in Reihen.- 2.4.1. Grundsätze.- 2.4.2. Einfache, direkte Sortierverfahren.- 2.4.2.1. Sortieren durch Einfeigen (insertion sort).- 2.4.2.2. Sortieren durch Auswählen (selection sort).- 2.4.2.3. Sortieren durch direktes Vertauschen (bubble sort).- 2.4.3. Schnelle, indirekte Sortierverfahren.- 2.4.3.1. Sortieren durch Einfügen mit variabler Schrittweite (Shellsort).- 2.4.3.2. Sortieren mit Halde (Heapsort).- 2.4.3.3. Sortieren durch Zerlegen (Quicksort).- 2.4.4. Quicksort.- 2.5. Modulkonzept und Datenkapselung — der abstrakte Datentyp.- 2.5.1. Der Modulbegriff und seine Realisierung in Modula-2.- 2.5.2. Abstrakte Datentypen in Modula-2.- 2.5.3. Anwendung: Bücherstapel.- 2.6. Objektorientiertes Programmieren.- 2.6.1. Klassische Ziele der Objektorientierung.- 2.6.2. Wo liegt der Mehrwert?.- 2.6.3. Was Topspeed-Modula bietet.- 3. Lineare dynamische Strukturen.- 3.1. Einleitung.- 3.2. Sequenzen.- 3.2.1. Definition.- 3.2.2. Modula-Realisierung und Standardoperationen.- 3.2.3. Anwendung: Sortieren mit Sequenzen.- 3.3. Verkettete Repräsentationen.- 3.3.1. Zeigertyp.- 3.3.2. Verkettete Listen.- 3.3.3. Standardoperationen mit verketteten Listen.- 3.3.4. Liste objektorientiert.- 3.3.5. Spezielle Liste “Keller” objektorientiert.- 3.3.6. Spezielle Liste “Schlange” objektorientiert.- 3.4. Prozessverwaltung.- 3.4.1. Coroutinen.- 3.4.2. Anwendung: Hangman.- 3.4.3. Von der Coroutine zum Prozeß.- 3.4.4. Anwendung: Würfelexperiment.- 3.4.5. Prozeßverwaltung und Listenstrukturen.- 4. Nichtlineare dynamische Datenstrukturen.- 4.1. Bäume im Allgemeinen.- 4.2. Sortierte binäre Schlüsselbäume.- 4.2.1. Grundlagen — binäre Bäume.- 4.2.2. Operationen auf sortierten binären Schlüsselbäumen.- 4.3. Datenstruktur “Baum” objektorientiert.- 4.4. Anwendung: Register.- 4.5. Vielwegbäume.- 4.6. Allgemeine Graphen.- 5. Datenorganisation auf externem Speicher.- 5.1. Grundbegriffe und Ziele.- 5.2. Stapelorganisation.- 5.3. Sequentielle Datenorganisation.- 5.4. Index-sequentielle Datenorganisation.- 5.5. Indizierte Datenorganisation.- 5.6. Direkte Datenorganisation.- 5.6.1. Grundsätze.- 5.6.2. Hash-Verfahren.- 5.6.2.1. Divisions-Rest-Verfahren.- 5.6.2.2. Faltung.- 5.6.2.3. Basistransformation.- 5.6.2.4. Ziffernanalyse.- 5.6.3. Kollisionsbehandlung.- 5.6.3.1. Grundsätze.- 5.6.3.2. Hashverfahren ohne Überlaufbereich.- 5.6.3.3. Hash-Verfahren mit Überlaufbereich.- 5.6.3.4. Bucket-Flash-Verfahren.- 5.6.4. Anwendung: Bucket-Hash-Verfahren.- 5.6.5. Ausblick: Dynamische Hash-Verfahren.- 6. Fallstudie: m2dB.- 6.1. Erstes Problem: Wie sieht eine einfache und sichere Programmierschnittstelle aus?.- 6.2. Zweites Problem: die Mengenschnittstelle.- 6.3. Architektur von m2dB.- 6.4. Anwendungsbeispiele.- Literatur.- Hinweise zur Diskette.- Stichwortverzeichnis.