lehrerbibliothek.deDatenschutzerklärung
Algorithmen mit C
Algorithmen mit C




Kyle Loudon

O'Reilly Verlag GmbH & Co. KG
EAN: 9783897211650 (ISBN: 3-89721-165-3)
612 Seiten, paperback, 18 x 23cm, 2000

EUR 40,00
alle Angaben ohne Gewähr

Umschlagtext
Es gibt viele Bücher über Datenstrukturen und Algorithmen, und einige dieser Bücher enthalten auch den Code für die entsprechenden C-Bibliotheken. Algorithmen mit C liefert Ihnen eine besondere Kombination aus theoretischem Hintergrund und praktikablem, einsetzbarem Code. Durch die Fülle robuster Lösungen für alltägliche Programmieraufgaben vermeidet dieses Buch den abstrakten Stil der meisten klassischen Titel zu Datenstrukturen und Algorithmen. Gleichzeitig werden alle Informationen zur Verfügung gestellt, die Sie benötigen, um den Zweck und die Anwendung bewährter und verbreiteter Programmiertechniken zu verstehen.



Sie finden im Buch sowohl Implementierungen als auch Beispiele realer Anwendungen für alle behandelten Datenstrukturen und Algorithmen. Der vollständige Quellcode ist auf der beiliegenden Diskette enthalten.



In einem klaren Programmier- und Schreibstil beschreibt Kyle Loudon die Verwendung elementarer Datenstrukturen wie Listen, Stacks, Queues, Mengen, Bäumen, Heaps, Priority Queues und Graphen. Er erläutert die Verwendung von Algorithmen für Sortierung, Suche, numerische Mathematik, Graphen, Datenkomprimierung und Datenverschlüsselung. Gleichzeitig bewertet er die relative Leistungsfähigkeit aller Implementierungen. Die Kapitel über Komprimierung und Verschlüsselung enthalten nicht nur den Code leistungsfähiger Lösungen, sondern behandeln die zugrundeliegenden Konzepte so, daß sie auch für diejenigen nachvollziehbar sind, die sich bisher nicht intensiv mit diesen Themen befaßt haben.



Dieses Buch ist für jeden geeignet, der über Grundkenntnisse in C verfügt. Um die Codes pflegen und erweitern zu können, wird in den Beispielen, wenn angebracht, eine zusätzliche Abstraktionsebene (etwa Zeiger auf Funktionen) eingefügt. Da diese Techniken nicht allen Programmierern vertraut sind, werden sie in den einführenden Kapiteln ausführlich erläutert.



Algorithmen mit C behandelt im einzelnen folgende Themen:



Zeiger

Rekursion

Analyse von Algorithmen

Datenstrukturen (Listen, Stacks, Queues, Mengen, Hashtabellen, Bäume, Heaps, Priority Queues und Graphen)

Sortieren und Suchen

numerische Methoden

Datenkomprimierung

Verschlüsselung von Daten

Graphen-Algorithmen

geometrische Algorithmen
Inhaltsverzeichnis
Vorwort xi


I: Grundlagen l

1: Einführung 3
Eine Einführung in Datenstrukturen 4
Eine Einführung in Algorithmen 5
Ein paar Worte zur Software-Entwicklung 9

2: Arbeiten mit Zeigern 13
Zeiger-Grundlagen 14
Speicher-Allozierung 15
Aggregate und Zeiger-Arithmetik 17
Zeiger als Parameter für Funktionen 20
Generische Zeiger und Casting 24
Zeiger auf Funktionen 27
Fragen und Antworten 28
Verwandte Themen 29

3: Rekursion 31
Einfache Rekursion 32
Endrekursion 36
Fragen und Antworten 39
Verwandte Themen 4l

4: Analyse von Algorithmen 43
Worst-Case-Analyse 44
O-Notation 45
Komplexität 47
Analysebeispiel: Insertion-Sort 50
Fragen und Antworten 53
Verwandte Themen 54


II: Datenstrukturen 55

5: Verkettete Listen 57
Beschreibung verketteter Listen 58
Schnittstelle für verkettete Listen 60
Implementierung und Analyse verketteter Listen 62
Beispielanwendung: Frame-Management 72
Beschreibung doppelt verketteter Listen 75
Schnittstelle für doppelt verkettete Listen 76
Implementierung und Analyse doppelt verketteter Listen 79
Beschreibung ringförmiger Listen 90
Schnittstelle für ringförmige Listen 91
Implementierung und Analyse ringförmiger Listen 93
Beispiel für eine ringförmige Liste: Second-Chance Page Replacement 101
Fragen und Antworten 104
Verwandte Themen 107

6: Stacks und Queues 109
Beschreibung von Stacks 111
Schnittstelle für Stacks 111
Implementierung und Analyse von Stacks 113
Beschreibung von Queues 117
Schnittstelle für Queues 117
Implementierung und Analyse von Queues 119
Beispiel für eine Queue: Ereignisverarbeitung 122
Fragen und Antworten 125
Verwandte Themen 126

7: Mengen 727
Beschreibung von Mengen 129
Schnittstelle für Mengen 131
Implementierung und Analyse von Mengen 134
Mengen-Beispiel: Überdeckung von Mengen 147
Fragen und Antworten 153
Verwandte Themen 155

8: Hashtabeilen 757
Beschreibung verketteter Hashtabellen 159
Schnittstelle für verkettete Hashtabellen 164
Implementierung und Analyse verketteter Hashtabellen 166
Beispiel für verkettete Hashtabellen: Symboltabellen 175
Beschreibung offen adressierter Hashtabellen 179
Schnittstelle für offen adressierte Hashtabellen 183
Implementierung und Analyse offen adressierter Hashtabellen 185
Fragen und Antworten 196
Verwandte Themen 197

9: Bäume 199
Beschreibung binärer Bäume 201
Schnittstelle für binäre Bäume 205
Implementierung und Analyse binärer Bäume 208
Beispiel für einen binären Baum: Verarbeitung von Ausdrücken 222
Beschreibung binärer Suchbäume 226
Schnittstelle für binäre Suchbäume 228
Implementierung und Analyse binärer Suchbäume 230
Fragen und Antworten 257
Verwandte Themen 260

10: Heaps und Priority Queues 26 Beschreibung von Heaps 262
Schnittstelle für Heaps 264
Implementierung und Analyse von Heaps 265
Beschreibung von Priority Queues 278
Schnittstelle für Priority Queues 278
Implementierung und Analyse von Priority Queues 280
Beispiel für eine Priority Queue: Paket-Sortierung 281
Fragen und Antworten 284
Verwandte Themen 286

11: Graphen 287
Beschreibung von Graphen 289
Schnittstelle für Graphen 296
Implementierung und Analyse von Graphen 299
Graph-Beispiel: Zählen der Netzwerk-Hops 315
Graph-Beispiel: Topologische Sortierung 321
Fragen und Antworten 327
Verwandte Themen 330


III: Algorithmen 331

12: Sortieren und Suchen 333
Beschreibung von Insertion-Sort 335
Schnittstelle für Insertion-Sort 336
Implementierung und Analyse von Insertion-Sort 336
Beschreibung von Quicksort 339
Schnittstelle für Quicksort 340
Implementierung und Analyse von Quicksort 34 Quicksort-Beispiel: Verzeichnisauflistungen 347
Beschreibung von Mergesort 351
Schnittstelle für Mergesort 352
Implementierung und Analyse von Mergesort 352
Beschreibung von Counting-Sort 359
Schnittstelle für Counting-Sort 359
Implementierung und Analyse von Counting-Sort 360
Beschreibung der Radix-Sortierung 364
Schnittstelle für Radix-Sortierung 365
Implementierung und Analyse der Radix-Sortierung 365
Beschreibung der binären Suche 369
Schnittstelle für die binäre Suche 370
Implementierung und Analyse der binären Suche 370
Beispiel für binäre Suche: Rechtschreibprüfung 373
Fragen und Antworten 376
Verwandte Themen 378

13: Numerische Methoden 3 79
Beschreibung der polynomialen Interpolation 380
Schnittstelle für polynomiale Interpolation 384
Implementierung und Analyse der polynomialen Interpolation 385
Beschreibung der Methode der kleinsten Quadrate 388
Schnittstelle für die Methode der kleinsten Quadrate 390
Implementierung und Analyse der Methode der kleinsten Quadrate 390
Beschreibung der Lösung von Gleichungen 392
Schnittstelle für die Lösung von Gleichungen 397
Implementierung und Analyse der Lösung von Gleichungen 398
Fragen und Antworten 400
Verwandte Themen 401

14: Datenkomprimierung 403
Beschreibung der Bitoperationen 407
Schnittstelle für Bitoperationen 407
Implementierung und Analyse der Bitoperationen 409
Beschreibung der Huffman-Codierung 414
Schnittstelle für die Huffman-Codierung 418
Implementierung und Analyse der Huffman-Codierung 419
Beispiel für die Huffman-Codierung: Optimierter Netzwerkbetrieb 437
Beschreibung von LZ77 440
Schnittstelle für LZ77 444
Implementierung und Analyse von LZ77 444
Fragen und Antworten 46 Verwandte Themen 464

15: Datenverschlüsselung 465
Beschreibung von DES 469
Schnittstelle für DES 476
Implementierung und Analyse von DES 477
Beispiel für DES: Blockverschlüsselungsmodi 490
Beschreibung von RSA 493
Schnittstelle für RSA 497
Implementierung und Analyse von RSA 498
Fragen und Antworten 502
Verwandte Themen 504

16: Graphenalgorithmen 507
Beschreibung von minimalen Spannbäumen 511
Schnittstelle für minimale Spannbäume 513
Implementierung und Analyse der minimalen Spannbäume 513
Beschreibung des Problems der kürzesten Wege 520
Schnittstelle für die kürzesten Wege 523
Implementierung und Analyse der kürzesten Wege 523
Beispiel für kürzeste Wege: Routing-Tabellen 530
Beschreibung des Traveling-Salesman-Problems 534
Schnittstelle für das Traveling-Salesman-Problem 537
Implementierung und Analyse des Traveling-Salesman-Problems 537
Fragen und Antworten 543
Verwandte Themen 545

17: Geometrische Algorithmen 547
Beschreibung des Tests, ob sich zwei Geradensegmente schneiden 551
Schnittstelle für den Test, ob sich zwei Geradensegmente schneiden 554
Implementierung und Analyse des Tests, ob sich zwei Geradensegment schneiden 554
Beschreibung von konvexen Hüllen 557
Schnittstelle für konvexe Hüllen 559
Implementierung und Analyse der konvexen Hüllen 560
Beschreibung von Bogenlängen auf Kugeloberflächen 565
Schnittstelle zur Berechnung der Bogenlänge auf Kugeloberflächen 568
Implementierung und Analyse der Berechnung von Bogenlängen au Kugeloberflächen 569
Beispiel für die Berechnung von Bogenlängen: Näherungsberechnung vo Entfernungen auf der Erde 571
Fragen und Antworten 575
Verwandte Themen 578

Index 579