077.txt ************************************************************************ * Edit v1.011 from 2021-02-26 to 2021-12-16 by HSc * ************************************************************************ Programmdesign und Algorithmen in C Ammeraal, Leendert Hanser 1994 3-446-17116-9 Seite Auszug ======================================================================== Inhaltsverzeichnis 001 l Programmierstil, Iteration und Rekursion ------------------------------------------------------------------------ 001 l.l Einfuehrung ------------------------------------------------------------------------ 003 1.2 Einsatz eines Sentinels bei der linearen Suche ------------------------------------------------------------------------ 004 l.3 Verwendung von Zeigern als Felder ------------------------------------------------------------------------ 006 l.4 Globale Variablen und Nebenwirkungen ------------------------------------------------------------------------ 011 l.5 Grundlagen der Rekursion ------------------------------------------------------------------------ 013 l.6 Eliminierung der Rekursion ------------------------------------------------------------------------ 018 l.7 Euklid-Algorithmus fuer groeszten gemeinsamen Teiler ------------------------------------------------------------------------ 019 1.8 Homer-Regel ------------------------------------------------------------------------ 021 l.9 Basiskonvertierung ------------------------------------------------------------------------ 027 1.10 Potenzierung mit Integerexponenten ------------------------------------------------------------------------ 032 UEbungen ------------------------------------------------------------------------ 035 Kapitel 2 Manipulation von Feldern und Dateien ------------------------------------------------------------------------ 035 2.1 Direkte Sortiermethoden ------------------------------------------------------------------------ 039 2.2 Quicksort ------------------------------------------------------------------------ 044 2.3 Sortieren von Strings variabler Laenge ------------------------------------------------------------------------ 046 2.4 Sortieren einer Datei ------------------------------------------------------------------------ 056 2.5 Bibliotheksfunktion qsort und generischer Code ------------------------------------------------------------------------ 060 2.6 Binaere Suche ------------------------------------------------------------------------ 064 2.7 Hashing ------------------------------------------------------------------------ 071 UEbungen ------------------------------------------------------------------------ 073 Kapitel 3 Einige kombinatorische Algorithmen ------------------------------------------------------------------------ 073 3.l Veraenderbare Anzahl verschachtelter Schleifen ------------------------------------------------------------------------ 077 3.2 Permutationen ------------------------------------------------------------------------ 083 3.3 Kombinationen ------------------------------------------------------------------------ 087 3.4 Das Rucksackproblem ------------------------------------------------------------------------ 090 3.5 Dynamisches Programmieren ------------------------------------------------------------------------ 094 UEbungen ------------------------------------------------------------------------ 097 Kapitel 4 Verkettete Listen ------------------------------------------------------------------------ 097 4.1 Einfuehrung ------------------------------------------------------------------------ 098 4.2 Manipulation verketteter Listen ------------------------------------------------------------------------ 105 4.3 Verkettete Listen und Strings veraenderbarer Laenge ------------------------------------------------------------------------ 111 4.4 Stapel und Warteschlangen ------------------------------------------------------------------------ 115 4.5 Ringfoermig doppelt verkettete Listen ------------------------------------------------------------------------ 122 UEbungsaufgaben ------------------------------------------------------------------------ 125 Kapitel 5 Binaerbaeume ------------------------------------------------------------------------ 125 5.l (irundlegende Operationen mit binaeren Suchbaeumen ------------------------------------------------------------------------ 131 5.2 Ausgeglichene Binaerbaeume ------------------------------------------------------------------------ 143 5.3 Zeigeradressen und Loeschen von Knoten ------------------------------------------------------------------------ 152 5.4 AVL-Baeume ------------------------------------------------------------------------ 162 UEbungsaufgaben ------------------------------------------------------------------------ 165 Kapitel 6 B-Baeume ------------------------------------------------------------------------ 165 6. l Erstellen und Durchsuchen eines B-Baumes ------------------------------------------------------------------------ 179 6.2 Loeschen von Knoten in einem B-Baum ------------------------------------------------------------------------ 185 6.3 Auf Platte/Diskette gespeicherte B-Baeume ------------------------------------------------------------------------ 198 UEbungsaufgaben ------------------------------------------------------------------------ 199 Kapitel 7 Tries ------------------------------------------------------------------------ 199 7.1 Einfuehrung ------------------------------------------------------------------------ 202 7.2 Ein Demonstrationsprogramm ------------------------------------------------------------------------ 209 UEbungsaufgaben ------------------------------------------------------------------------ 211 Kapitel 8 Graphen ------------------------------------------------------------------------ 211 8.1 Gerichtete und ungerichtete Graphen ------------------------------------------------------------------------ 212 8.2 Graphenrepraesentation ------------------------------------------------------------------------ 213 8.3 Topologisches Sortieren und Vorkommen von Ringen ------------------------------------------------------------------------ 220 8.4 Taetigkeits-Netzplan und Methodik (CPM) ------------------------------------------------------------------------ 228 UEbungsaufgaben ------------------------------------------------------------------------ 231 Kapitel 9 Grundlagen von Interpretern und Compilern ------------------------------------------------------------------------ 231 9.1 Syntaxdiagramme fuer VSL ------------------------------------------------------------------------ 235 9.2 Ein Quellcode-Interpreter ------------------------------------------------------------------------ 238 9.3 Konvertierung von Infix in Suffix ------------------------------------------------------------------------ 243 9.4 Ein Suffix-Interpreter ------------------------------------------------------------------------ 246 9.5 Objektprogramm und Laufzeitsystem ------------------------------------------------------------------------ 249 9.6 Ein VSL-Compiler ------------------------------------------------------------------------ 252 UEbungsaufgaben ------------------------------------------------------------------------ 255 Anhang A Naeheres zu C und C++ ------------------------------------------------------------------------ 255 A. l Funktionsdeklarationen ------------------------------------------------------------------------ 257 A. 2 Verbleibende Fallen in ANSI C und C++ ------------------------------------------------------------------------ 259 Anhang B Programme in den Kapiteln ------------------------------------------------------------------------ 259 Kapitel l ------------------------------------------------------------------------ 259 Kapitel 2 ------------------------------------------------------------------------ 260 Kapitel 3 ------------------------------------------------------------------------ 260 Kapitel 4 ------------------------------------------------------------------------ 260 Kapitel 5 ------------------------------------------------------------------------ 260 Kapitel 6 ------------------------------------------------------------------------ 261 Kapitel 7 ------------------------------------------------------------------------ 261 Kapitels ------------------------------------------------------------------------ ------------------------------------------------------------------------ ******** EOF ***********************************************************