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