C/C++

Vorwort ... 19

1. Einige Grundbegriffe ... 21
1.1 ... Algorithmus ... 24
1.2 ... Datenstruktur ... 28
1.3 ... Programm ... 30
1.4 ... Programmiersprachen ... 31
1.5 ... Aufgaben ... 33

2. Einführung in die Programmierung ... 35
2.1 ... Softwareentwicklung ... 35
2.2 ... Die Programmierumgebung ... 40

3. Ausgewählte Sprachelemente von C ... 45
3.1 ... Programmrahmen ... 45
3.2 ... Zahlen ... 46
3.3 ... Variablen ... 46
3.4 ... Operatoren ... 48
3.5 ... Kontrollfluss ... 56
3.6 ... Elementare Ein- und Ausgabe ... 67
3.7 ... Beispiele ... 73
3.8 ... Aufgaben ... 81

4. Arithmetik ... 83
4.1 ... Folgen ... 85
4.2 ... Summen und Produkte ... 96
4.3 ... Aufgaben ... 100

5. Aussagenlogik ... 107
5.1 ... Aussagen ... 108
5.2 ... Aussagenlogische Operatoren ... 108
5.3 ... Boolesche Funktionen ... 116
5.4 ... Logische Operatoren in C ... 119
5.5 ... Beispiele ... 120
5.6 ... Aufgaben ... 126

6. Elementare Datentypen und ihre Darstellung ... 129
6.1 ... Zahlendarstellungen ... 130
6.2 ... Bits und Bytes ... 137
6.3 ... Skalare Datentypen in C ... 139
6.4 ... Bitoperationen ... 146
6.5 ... Programmierbeispiele ... 150
6.6 ... Zeichen ... 156
6.7 ... Arrays ... 159
6.8 ... Zeichenketten ... 164
6.9 ... Programmierbeispiele ... 173
6.10 ... Aufgaben ... 178

7. Modularisierung ... 181
7.1 ... Funktionen ... 181
7.2 ... Arrays als Funktionsparameter ... 186
7.3 ... Lokale und globale Variablen ... 190
7.4 ... Rekursion ... 192
7.5 ... Der Stack ... 198
7.6 ... Beispiele ... 200
7.7 ... Aufgaben ... 218

8. Zeiger und Adressen ... 223
8.1 ... Zeigerarithmetik ... 230
8.2 ... Zeiger und Arrays ... 232
8.3 ... Funktionszeiger ... 235
8.4 ... Aufgaben ... 239

9. Programmgrobstruktur ... 241
9.1 ... Der Präprozessor ... 241
9.2 ... Ein kleines Projekt ... 249

10. Die Standard C Library ... 253
10.1 ... Mathematische Funktionen ... 254
10.2 ... Zeichenklassifizierung und -konvertierung ... 256
10.3 ... Stringoperationen ... 257
10.4 ... Ein- und Ausgabe ... 260
10.5 ... Variable Anzahl von Argumenten ... 263
10.6 ... Freispeicherverwaltung ... 265
10.7 ... Aufgaben ... 271

11. Kombinatorik ... 273
11.1 ... Kombinatorische Grundaufgaben ... 274
11.2 ... Permutationen mit Wiederholungen ... 274
11.3 ... Permutationen ohne Wiederholungen ... 275
11.4 ... Kombinatorische Algorithmen ... 283
11.5 ... Beispiele ... 293

12. Leistungsanalyse und Leistungsmessung ... 305
12.1 ... Leistungsanalyse ... 308
12.2 ... Leistungsmessung ... 320
12.3 ... Laufzeitklassen ... 324

13. Sortieren ... 347
13.1 ... Sortierverfahren ... 347
13.2 ... Leistungsanalyse der Sortierverfahren ... 376
13.3 ... Leistungsmessung der Sortierverfahren ... 383
13.4 ... Grenzen der Optimierung von Sortierverfahren ... 388

14. Datenstrukturen ... 393
14.1 ... Strukturdeklarationen ... 395
14.2 ... Zugriff auf Strukturen ... 400
14.3 ... Datenstrukturen und Funktionen ... 405
14.4 ... Ein vollständiges Beispiel (Teil 1) ... 409
14.5 ... Dynamische Datenstrukturen ... 415
14.6 ... Ein vollständiges Beispiel (Teil 2) ... 421
14.7 ... Die Freispeicherverwaltung ... 432
14.8 ... Aufgaben ... 435

15. Ausgewählte Datenstrukturen ... 437
15.1 ... Listen ... 439
15.2 ... Bäume ... 448
15.3 ... Treaps ... 470
15.4 ... Hash-Tabellen ... 482

16. Abstrakte Datentypen ... 493
16.1 ... Der Stack als abstrakter Datentyp ... 495
16.2 ... Die Queue als abstrakter Datentyp ... 500

17. Elemente der Graphentheorie ... 507
17.1 ... Graphentheoretische Grundbegriffe ... 510
17.2 ... Die Adjazenzmatrix ... 511
17.3 ... Beispielgraph (Autobahnnetz) ... 512
17.4 ... Traversierung von Graphen ... 514
17.5 ... Wege in Graphen ... 516
17.6 ... Der Algorithmus von Warshall ... 518
17.7 ... Kantentabellen ... 522
17.8 ... Zusammenhang und Zusammenhangskomponenten ... 523
17.9 ... Gewichtete Graphen ... 530
17.10 ... Kürzeste Wege ... 532
17.11 ... Der Algorithmus von Floyd ... 533
17.12 ... Der Algorithmus von Dijkstra ... 539
17.13 ... Erzeugung von Kantentabellen ... 546
17.14 ... Der Algorithmus von Ford ... 548
17.15 ... Minimale Spannbäume ... 551
17.16 ... Der Algorithmus von Kruskal ... 552
17.17 ... Hamiltonsche Wege ... 557
17.18 ... Das Travelling-Salesman-Problem ... 562

18. Zusammenfassung und Ergänzung ... 575

19. Einführung in C++ ... 677
19.1 ... Schlüsselwörter ... 677
19.2 ... Kommentare ... 678
19.3 ... Datentypen, Datenstrukturen und Variablen ... 679
19.4 ... Funktionen ... 690
19.5 ... Operatoren ... 701
19.6 ... Auflösung von Namenskonflikten ... 711

20. Objektorientierte Programmierung ... 717
20.1 ... Ziele der Objektorientierung ... 717
20.2 ... Objektorientiertes Design ... 719
20.3 ... Klassen in C++ ... 725
20.4 ... Aufbau von Klassen ... 725
20.5 ... Instanziierung von Klassen ... 740
20.6 ... Operatoren auf Klassen ... 745
20.7 ... Ein- und Ausgabe in C++ ... 748
20.8 ... Der this-Pointer ... 755
20.9 ... Beispiele ... 756
20.10 ... Aufgaben ... 771

21. Das Zusammenspiel von Objekten ... 775
21.1 ... Modellierung von Beziehungen ... 775
21.2 ... Komposition eigener Objekte ... 776
21.3 ... Eine Klasse text ... 786
21.4 ... Übungen/Beispiel ... 797
21.5 ... Aufgabe ... 803

22. Vererbung ... 805
22.1 ... Darstellung der Vererbung ... 805
22.2 ... Vererbung in C++ ... 808
22.3 ... Beispiele ... 831

23. Zusammenfassung und Überblick ... 879
23.1 ... Klassen und Instanzen ... 879
23.2 ... Member ... 881
23.3 ... Vererbung ... 900
23.4 ... Zugriffsschutz und Vererbung ... 916
23.5 ... Der Lebenszyklus von Objekten ... 922
23.6 ... Typüberprüfung und Typumwandlung ... 946
23.7 ... Typumwandlung in C++ ... 948

24. Die C++-Standardbibliothek und Ergänzung ... 953
24.1 ... Generische Klassen (Templates) ... 954
24.2 ... Ausnahmebehandlung (Exceptions) ... 962
24.3 ... Die C++-Standardbibliothek ... 973
24.4 ... Iteratoren ... 973
24.5 ... Strings (string) ... 976
24.6 ... Dynamische Arrays (vector) ... 990
24.7 ... Listen (list) ... 998
24.8 ... Stacks (stack) ... 1014
24.9 ... Warteschlangen (queue) ... 1017
24.10 ... Prioritätswarteschlangen (priority_queue) ... 1019
24.11 ... Geordnete Paare (pair) ... 1024
24.12 ... Mengen (set und multiset) ... 1025
24.13 ... Relationen (map und multimap) ... 1030
24.14 ... Algorithmen der Standardbibliothek ... 1032

Aufgaben und Lösungen ... 1041
Kapitel 1 ... 1042
Kapitel 3 ... 1055
Kapitel 4 ... 1069
Kapitel 5 ... 1090
Kapitel 6 ... 1103
Kapitel 7 ... 1120
Kapitel 8 ... 1144
Kapitel 10 ... 1155
Kapitel 14 ... 1162
Kapitel 20 ... 1186
Kapitel 21 ... 1203

Index ... 1209