Danksagung 16

1 Einige Grundbegriffe 17

1.1 Algorithmus 19
1.2 Datenstruktur 23
1.3 Programm 25
1.4 Aufgaben 28

2 Einführung in die Programmierung 31

2.1 Die Programmierumgebung 36
2.1.1 Der Editor 36
2.1.2 Der Compiler 37
2.1.3 Der Linker 38
2.1.4 Der Debugger 38

3 Ausgewählte Sprachelemente von C 39

3.1 Programmrahmen 39
3.2 Zahlen 40
3.3 Variablen 40
3.4 Operationen 42
3.4.1 Zuweisungsoperationen 42
3.4.2 Rechenoperationen 43
3.4.3 Vergleichsoperationen 45
3.5 Kommentare 46
3.6 Elementare Ein- /Ausgabe 46
3.6.1 Bildschirmausgabe 46
3.6.2 Tastatureingabe 48
3.7 Kontrollfluss 48
3.7.1 Bedingte Befehlsausführung 49
3.7.2 Wiederholte Befehlsausführung 50
3.7.3 Verschachtelung von Kontrollstrukturen 56
3.8 Beispiele 57
3.8.1 Das erste C- Programm 57
3.8.2 Das zweite C- Programm 58
3.8.3 Das dritte C- Programm 62
3.9 Aufgaben 65

4 Arithmetik 69

4.1 Folgen 69
4.2 Summen 76
4.3 Produkte 83
4.4 Aufgaben 85

5 Aussagenlogik 93

5.1 Aussagen 93
5.2 Logische Operatoren 94
5.3 Darstellung boolescher Funktionen 102
5.4 Vereinfachung boolescher Ausdrücke 106
5.5 Logische Operatoren in C 115
5.6 Programmierbeispiele 116
5.6.1 Kugelspiel 116
5.6.2 Schaltung 117
5.7 Aufgaben 120

6 Elementare Datentypen und ihre Darstellung 125

6.1 Zahlendarstellungen 125
6.1.1 Dezimaldarstellung 127
6.1.2 Dualdarstellung 127
6.1.3 Oktaldarstellung 129
6.1.4 Hexadezimaldarstellung 130
6.2 Bits und Bytes 132
6.3 Skalare Datentypen in C 136
6.3.1 Ganze Zahlen 137
6.3.2 Aufzählungstypen 138
6.3.3 Gleitkommazahlen 138
6.3.4 Buchstaben 139
6.4 Bit- Operationen 143
6.5 Programmierbeispiele mit Zeichen, Zahlen und Bit—Operationen 146
6.5.1 Zeichensatz 146
6.5.2 Bit- Editor 148
6.6 Arrays und Zeichenketten 151
6.6.1 Arrays 152
6.6.2 Zeichenketten 157
6.7 Programmierbeispiele mit Arrays und Strings 163
6.7.1 Buchstaben zählen 163
6.7.2 Matrixdruck 167
6.8 Aufgaben 169

7 Modularisierung 177

7.1 Funktionen und Unterprogramme 177
7.2 Rekursion 184
7.3 Der Stack 193
7.4 Globale, lokale und statische Variablen 196
7.5 Die C-Runtime- Library 198
7.5.1 Mathematische Funktionen 198
7.5.2 Konvertierungs- und Klassifizierungsroutinen 201
7.5.3 Stringbearbeitung 203
7.5.4 Terminal I/O 205
7.5.5 Dateioperationen 210
7.5.6 Suchen und Sortieren 214
7.5.7 Variable Anzahl von Argumenten 214
7.5.8 Ausnahme- und Fehlerbehandlung 217
7.5.9 Assertions und Programmabbruch 221
7.5.10 Freispeicherverwaltung und Speicherfunktionen 223
7.5.11 Zeit- und Datum- Funktionen 223
7.5.12 Prozess- Steuerung 224
7.6 Beispiele 224
7.6.1 Das Damenproblem 224
7.6.2 Labyrinth 232
7.7 Aufgaben 239

8 Zeiger und Adressen 253

8.1 Zeigerarithmetik 257
8.2 Arrays und Zeiger 259
8.3 Funktionszeiger 262
8.4 Komplexe Variablendeklarationen 266
8.5 Aufgaben 268

9 C-Referenz (Teil 1) 271

9.1 Reservierte Wörter 271
9.2 Identifier 271
9.3 Numerische Werte 272
9.4 Werte für Zeichen und Zeichenketten 273
9.5 Skalare Datentypen 274
9.6 Variablen 274
9.7 Arrays 279
9.8 Operatoren 279
9.8.1 Arithmetische Operatoren 283
9.8.2 Vergleichsoperatoren 284
9.8.3 Logische Operatoren 285
9.8.4 Bit- Operatoren 286
9.8.5 Zugriffsoperatoren 286
9.8.6 Auswertungsoperatoren 287
9.8.7 Datentyp- Operatoren 288
9.8.8 Ausdrücke und Zuweisungsoperatoren 289
9.9 Funktionen 293
9.10 Kontrollstrukturen 295
9.10.1 Alternativen 295
9.10.2 Sprungleisten 296
9.10.3 Schleifen 299
9.10.4 Sprunganweisungen 301
9.11 Der Preprozessor 303
9.11.1 Includes 303
9.11.2 Symbolische Konstanten 304
9.11.3 Makros 306
9.11.4 Bedingte Compilierung 307
9.12 Der Aufbau von Programmdateien 309
9.12.1 Header- Dateien 310
9.12.2 Quellcode- Dateien 311
9.13 Einige Coding- Standards 312

10 Kombinatorik 315

10.1 Kombinatorische Grundaufgaben 315
10.1.1 Permutationen mit Wiederholungen 316
10.1.2 Permutationen ohne Wiederholungen 317
10.1.3 Kombinationen ohne Wiederholungen 318
10.1.4 Kombinationen mit Wiederholungen 320
10.1.5 Zusammenfassung 321
10.2 Kombinatorische Algorithmen 324
10.2.1 Permutationen mit Wiederholungen 325
10.2.2 Kombinationen mit Wiederholungen 328
10.2.3 Kombinationen ohne Wiederholungen 330
10.2.4 Permutationen ohne Wiederholungen 332
10.3 Beispiele 335
10.3.1 Juwelenraub 336
10.3.2 Geldautomat 341
10.4 Aufgaben 346

11 Grafikprogrammierung 351

11.1 IGEL 351
11.1.1 Koordinaten und Fenstergröße 353
11.1.2 Farben 355
11.1.3 Bildpunkte und Bildschirmbereiche 355
11.1.4 Linien 356
11.1.5 Rechtecke 356
11.1.6 Kreise und Ellipsen 357
11.1.7 Text 358
11.1.8 Ablaufsteuerung 359
11.2 Beispiele 360
11.2.1 Bälle 360
11.2.2 Life 363
11.2.3 Bubblesort 369
11.3 Aufgaben 375

12 Leistungsanalyse und -messung von Algorithmen 381

12.1 Leistungsanalyse 384
12.2 Leistungsmessung 397
12.2.1 Überdeckungsanalyse 399
12.2.2 Performance- Analyse 400
12.3 Mathematische Grundfunktionen 402
12.3.1 Floor und Ceiling 403
12.3.2 Potenzfunktionen 404
12.3.3 Exponentialfunktionen 405
12.3.4 Logarithmen 406
12.4 Laufzeitklassen 409
12.5 Beispiele 416

13 Sortierverfahren 429

13.1 Bubblesort 430
13.2 Selectionsort 432
13.3 Insertionsort 435
13.4 Shellsort 437
13.5 Quicksort 441
13.6 Heapsort 447
13.7 Leistungsanalyse 452
13.7.1 Bubblesort 454
13.7.2 Selectionsort 456
13.7.3 Insertionsort 457
13.7.4 Shellsort 458
13.7.5 Quicksort 460
13.7.6 Heapsort 462
13.8 Vergleich und Bewertung 463
13.9 Grenzen der Optimierung von Sortierverfahren 469
13.10 Aufgaben 474

14 Datenstrukturen 475

14.1 Datensequenz (struct) 476
14.2 Datenalternative (union) 485
14.3 Optimierung von Datenstrukturen 492
14.4 Zeiger und Datenstrukturen 497
14.5 Dynamische Datenstrukturen 500
14.6 Verkettete Datenstrukturen (Listen) 506
14.7 Die Freispeicherverwaltung 510
14.8 Abstrakte Datentypen 513
14.8.1 Der abstrakte Datentyp ªStack´ 516
14.8.2 Der abstrakte Datentyp ªQueue´ 521
14.9 Aufgaben 526

15 C-Referenz (Teil 2) 533

15.1 Einfache Strukturen 533
15.2 Zusammengesetzte Strukturen 536
15.3 Zugriff auf Strukturen 538
15.3.1 Direkter Zugriff 538
15.3.2 Indirekter Zugriff 540
15.4 Unions 541
15.5 Datenstrukturen und Funktionen 543
15.6 Dynamische Datenstrukturen 545
15.7 Zeiger in Datenstrukturen 548
15.8 Typvereinbarungen 552
15.9 Bitfelder 553

16 Ausgewählte Datenstrukturen 557

16.1 Aufgabenstellung 557
16.2 Schnittstellenvereinbarung 559
16.3 Anwendungsprogramm 562
16.4 Listen 567
16.4.1 Grundbegriffe 568
16.4.2 Arrays oder Listen 569
16.4.3 Speicherstruktur 571
16.4.4 Implementierung 575
16.4.5 Test 581
16.5 Bäume 582
16.5.1 Grundbegriffe 582
16.5.2 Traversierung von Bäumen 586
16.5.3 Speicherstruktur 599
16.5.4 Implementierung 602
16.5.5 Test 609
16.6 Ausgeglichene Bäume 611
16.6.1 Grundbegriffe 611
16.6.2 Speicherstruktur 615
16.6.3 Implementierung 618
16.6.4 Test 633
16.7 Hashtabellen 634
16.7.1 Grundbegriffe 635
16.7.2 Speicherstruktur 637
16.7.3 Implementierung 640
16.7.4 Test 643
16.8 Vergleich und Bewertung 647
16.8.1 Speicherkomplexität 648
16.8.2 Laufzeitmessungen 648
16.9 Aufgaben 653

17 Elemente der Graphentheorie 655

17.1 Grundbegriffe 657
17.2 Darstellung von Graphen durch Datenstrukturen 664
17.3 Ausgewählte graphentheoretische Probleme 669
17.3.1 Existenz von Wegen 671
17.3.2 Kürzeste Wege 693
17.3.3 Minimal spannende Bäume 728
17.3.4 Hamiltonsche Wege 735

18 C++-Referenz (Teil 1) 749

18.1 Schlüsselwörter 749
18.2 Operatoren 749
18.3 Kommentare 752
18.4 Datentypen, Datenstrukturen und Variablen 753
18.4.1 Automatische Typisierung von Aufzählungstypen 753
18.4.2 Automatische Typisierung von Strukturen 753
18.4.3 Vorwärtsverweise auf Strukturen 754
18.4.4 Const- Deklarationen 755
18.4.5 Definition von Variablen 756
18.4.6 Referenzen 756
18.5 Funktionen und Operatoren 762
18.5.1 Funktionsdeklarationen und Prototypen 762
18.5.2 Default- Werte 762
18.5.3 Inline- Funktionen 764
18.5.4 Der Scope- Resolution-Operator 765
18.5.5 Überladen von Funktionen 766
18.5.6 Überladen von Operatoren 769
18.5.7 Einbindung von C- Funktionen in C++-Programme 771

19 Objektorientierte Programmierung 775

20 Klassen in C++ 791

20.1 Aufbau von Klassen 791
20.1.1 Daten- Member 793
20.1.2 Funktions- Member 796
20.1.3 Konstruktoren und Destruktoren 805
20.2 Instantiierung von Klassen 811
20.2.1 Automatische Instantiierung 813
20.2.2 Statische Instantiierung 814
20.2.3 Dynamische Instantiierung 815
20.2.4 Instantiierung von Arrays 818
20.3 Friends 818
20.4 Operatoren auf Klassen 823
20.5 Ein- und Ausgabe in C++ 827
20.5.1 Bildschirmausgabe 827
20.5.2 Tastatureingabe 832
20.5.3 Dateioperationen 833
20.6 Der this- Pointer 835
20.7 Beispiele 836
20.7.1 Menge 836
20.7.2 Bingo 847
20.7.3 Migration des Listen-Moduls 855
20.8 Aufgaben 862

21 Vererbung in C++ 869

21.1 Geschützte Member 875
21.2 Einfache Vererbung 878
21.3 Mehrfache Vererbung 879
21.4 Instantiierung abgeleiteter Klassen 879
21.5 Erweiterung abgeleiteter Klassen 882
21.6 Überladen von Funktionen der Basisklasse 884
21.7 Virtuelle Member- Funktionen 889
21.8 Rein virtuelle Member-Funktionen 892
21.9 Statische Member 893
21.10 Beispiele 900
21.10.1 Listen- Modul 900
21.10.2 Würfelspiel 905
21.10.3 Partnervermittlung 928
21.11 Aufgaben 949

22 C++-Referenz (Teil 2) 955

22.1 Klassen und Instanzen 955
22.2 Member 956
22.2.1 Daten- Member 957
22.2.2 Funktions- Member 959
22.2.3 Statische Member 961
22.2.4 Operatoren 963
22.3 Zugriff auf Member 964
22.3.1 Zugriff von außen 965
22.3.2 Zugriff von innen 968
22.3.3 Der this- Pointer 971
22.3.4 Zugriff durch Friends 972
22.4 Vererbung 974
22.4.1 Einfachvererbung 974
22.4.2 Mehrfachvererbung 979
22.4.3 Virtuelle Funktionen 985
22.4.4 Rein virtuelle Funktionen 988
22.5 Zugriffsschutz und Vererbung 989
22.5.1 Geschützte Member 989
22.5.2 Zugriff auf die Basisklasse 990
22.5.3 Modifikation von Zugriffsrechten 995
22.6 Der Lebenszyklus von Objekten 997
22.6.1 Konstruktion von Objekten 1000
22.6.2 Destruktion von Objekten 1003
22.6.3 Kopieren von Objekten 1004
22.6.4 Instantiierung von Objekten 1007
22.6.5 Initialisierung eingelagerter Objekte 1009
22.6.6 Initialisierung von Basisklassen 1012
22.6.7 Initialisierung virtueller Basisklassen 1014
22.6.8 Instantiierungsregeln 1016
22.7 Pointer to Member 1019
22.8 Generische Klassen (Templates) 1023
22.9 Ausnahmefallbehandlung 1029

23 Anhang: Die CD 1037

23.1 Der Compiler 1037
23.2 Installation des Compilers 1037
23.3 Die Beispielprogramme 1038
23.4 Erstellen eigener Programme 1039
23.5 Verwendung von IGEL mit dem Microsoft- Compiler 1039
23.6 Die Dokumentation zum Compiler 1040
23.7 Die Tools 1040

Index 1041

Zurück zu »C/C++«