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

2.2.1 Der Editor

41

2.2.2 Der Compiler

42

2.2.3 Der Linker

43

2.2.4 Der Debugger

43

2.2.5 Der Profiler

43

3 Ausgewählte Sprachelemente von C

45

3.1 Programmrahmen

45

3.2 Zahlen

46

3.3 Variablen

46

3.4 Operatoren

48

3.4.1 Zuweisungsoperator

48

3.4.2 Arithmetische Operatoren

49

3.4.3 Typkonvertierungen

55

3.4.4 Vergleichsoperationen

55

3.5 Kontrollfluss

56

3.5.1 Bedingte Befehlsausführung

57

3.5.2 Wiederholte Befehlsausführung

59

3.5.3 Verschachtelung von Kontrollstrukturen

65

3.6 Elementare Ein- und Ausgabe

67

3.6.1 Bildschirmausgabe

67

3.6.2 Tastatureingabe

69

3.6.3 Kommentare und Layout

72

3.7 Beispiele

73

3.7.1 Das erste Programm

73

3.7.2 Das zweite Programm

75

3.7.3 Das dritte Programm

79

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.5.1 Kugelspiel

120

5.5.2 Schaltung

122

5.6 Aufgaben

126

6 Elementare Datentypen und ihre Darstellung

129

6.1 Zahlendarstellungen

130

6.1.1 Dualdarstellung

134

6.1.2 Oktaldarstellung

135

6.1.3 Hexadezimaldarstellung

136

6.2 Bits und Bytes

137

6.3 Skalare Datentypen in C

139

6.3.1 Ganze Zahlen

140

6.3.2 Gleitkommazahlen

144

6.4 Bitoperationen

146

6.5 Programmierbeispiele

150

6.5.1 Kartentrick

150

6.5.2 Zahlenraten

152

6.5.3 Addierwerk

154

6.6 Zeichen

156

6.7 Arrays

159

6.7.1 Eindimensionale Arrays

160

6.7.2 Mehrdimensionale Arrays

162

6.8 Zeichenketten

164

6.9 Programmierbeispiele

173

6.9.1 Buchstabenstatistik

173

6.9.2 Sudoku

175

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.6.1 Bruchrechnung

200

7.6.2 Das Damenproblem

202

7.6.3 Permutationen

210

7.6.4 Labyrinth

213

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.1.1 Includes

242

9.1.2 Symbolische Konstanten

244

9.1.3 Makros

245

9.1.4 Bedingte Kompilierung

247

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.3.1 Kombinationen ohne Wiederholungen

277

11.3.2 Kombinationen mit Wiederholungen

278

11.3.3 Zusammenfassung

280

11.4 Kombinatorische Algorithmen

283

11.4.1 Permutationen mit Wiederholungen

284

11.4.2 Kombinationen mit Wiederholungen

286

11.4.3 Kombinationen ohne Wiederholungen

288

11.4.4 Permutationen ohne Wiederholungen

290

11.5 Beispiele

293

11.5.1 Juwelenraub

293

11.5.2 Geldautomat

298

12 Leistungsanalyse und Leistungsmessung

305

12.1 Leistungsanalyse

308

12.2 Leistungsmessung

320

12.2.1 Überdeckungsanalyse

322

12.2.2 Performance-Analyse

323

12.3 Laufzeitklassen

324

12.3.1 Programm 1

335

12.3.2 Programm 2

336

12.3.3 Programm 3

337

12.3.4 Programm 4

340

12.3.5 Programm 5

341

12.3.6 Programm 6

342

13 Sortieren

347

13.1 Sortierverfahren

347

13.1.1 Bubblesort

349

13.1.2 Selectionsort

351

13.1.3 Insertionsort

353

13.1.4 Shellsort

356

13.1.5 Quicksort

359

13.1.6 Heapsort

370

13.2 Leistungsanalyse der Sortierverfahren

376

13.2.1 Bubblesort

376

13.2.2 Selectionsort

377

13.2.3 Insertionsort

378

13.2.4 Shellsort

379

13.2.5 Quicksort

380

13.2.6 Heapsort

381

13.3 Leistungsmessung der Sortierverfahren

383

13.4 Grenzen der Optimierung von Sortierverfahren

388

14 Datenstrukturen

393

14.1 Strukturdeklarationen

395

14.1.1 Variablendefinitionen

398

14.2 Zugriff auf Strukturen

400

14.2.1 Direktzugriff

401

14.2.2 Indirektzugriff

403

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.2.1 Traversierung von Bäumen

451

15.2.2 Aufsteigend sortierte Bäume

461

15.3 Treaps

470

15.3.1 Heaps

471

15.3.2 Der Container als Treap

473

15.4 Hash-Tabellen

482

15.4.1 Speicherkomplexität

489

15.4.2 Laufzeitkomplexität

490

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

19 Einführung in C++

677

19.1 Schlüsselwörter

677

19.2 Kommentare

678

19.3 Datentypen, Datenstrukturen und Variablen

679

19.3.1 Automatische Typisierung von Aufzählungstypen

679

19.3.2 Automatische Typisierung von Strukturen

680

19.3.3 Vorwärtsverweise auf Strukturen

680

19.3.4 Der Datentyp bool

681

19.3.5 Verwendung von Konstanten

682

19.3.6 Definition von Variablen

683

19.3.7 Verwendung von Referenzen

684

19.3.8 Referenzen als Rückgabewerte

688

19.3.9 Referenzen außerhalb von Schnittstellen

689

19.4 Funktionen

690

19.4.1 Funktionsdeklarationen und Prototypen

691

19.4.2 Vorgegebene Werte in der Funktionsschnittstelle (Default-Werte)

692

19.4.3 Inline-Funktionen

694

19.4.4 Überladen von Funktionen

696

19.4.5 Parametersignatur von Funktionen

698

19.4.6 Zuordnung der Parametersignaturen und der passenden Funktion

699

19.4.7 Verwendung von C-Funktionen in C++-Programmen

700

19.5 Operatoren

701

19.5.1 Der Globalzugriff

702

19.5.2 Alle Operatoren in C++

703

19.5.3 Überladen von Operatoren

707

19.6 Auflösung von Namenskonflikten

711

19.6.1 Der Standardnamensraum std

715

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.4.1 Zugriffsschutz von Klassen

726

20.4.2 Datenmember

727

20.4.3 Funktionsmember

729

20.4.4 Verwendung des Zugriffsschutzes

731

20.4.5 Konstruktoren

735

20.4.6 Destruktoren

739

20.5 Instanziierung von Klassen

740

20.5.1 Automatische Variablen in C

740

20.5.2 Automatische Instanziierung in C++

741

20.5.3 Statische Variablen in C

741

20.5.4 Statische Instanziierung in C++

742

20.5.5 Dynamische Variablen in C

743

20.5.6 Dynamische Instanziierung in C++

743

20.5.7 Instanziierung von Arrays in C++

744

20.6 Operatoren auf Klassen

745

20.6.1 Friends

746

20.6.2 Operator als Methode der Klasse

747

20.7 Ein- und Ausgabe in C++

748

20.7.1 Überladen des <<-Operators

749

20.7.2 Tastatureingabe

750

20.7.3 Dateioperationen

752

20.8 Der this-Pointer

755

20.9 Beispiele

756

20.9.1 Menge

756

20.10 Aufgaben

771

21 Das Zusammenspiel von Objekten

775

21.1 Modellierung von Beziehungen

775

21.2 Komposition eigener Objekte

776

21.2.1 Komposition in C++

779

21.2.2 Implementierung der print-Methode für timestamp

780

21.2.3 Der Konstruktor von timestamp

781

21.2.4 Parametrierter Konstruktor einer komponierten Klasse

783

21.2.5 Konstruktionsoptionen der Klasse timestamp

785

21.3 Eine Klasse text

786

21.3.1 Der Copy-Konstruktor

788

21.3.2 Implementierung eines Copy-Konstruktors

790

21.3.3 Zuweisung von Objekten

791

21.3.4 Implementierung des Zuweisungsoperators

793

21.3.5 Erweiterung der Klasse text

794

21.3.6 Vorgehen für eigene Objekte

796

21.4 Übungen/Beispiel

797

21.4.1 Bingo

797

21.5 Aufgabe

803

22 Vererbung

805

22.1 Darstellung der Vererbung

805

22.1.1 Mehrere abgeleitete Klassen

806

22.1.2 Wiederholte Vererbung

807

22.1.3 Mehrfachvererbung

807

22.2 Vererbung in C++

808

22.2.1 Ableiten einer Klasse

809

22.2.2 Gezieltes Aufrufen des Konstruktors der Basisklasse

810

22.2.3 Der geschützte Zugriffsbereich einer Klasse

812

22.2.4 Erweiterung abgeleiteter Klassen

813

22.2.5 Überschreiben von Funktionen der Basisklasse

814

22.2.6 Unterschiedliche Instanziierungen und deren Verwendung

817

22.2.7 Virtuelle Memberfunktionen

820

22.2.8 Verwendung des Schlüsselwortes virtual

821

22.2.9 Mehrfachvererbung

822

22.2.10 Zugriff auf die Methoden der Basisklassen

824

22.2.11 Statische Member

826

22.2.12 Rein virtuelle Funktionen

829

22.3 Beispiele

831

22.3.1 Würfelspiel

831

22.3.2 Partnervermittlung

855

23 Zusammenfassung und Überblick

879

23.1 Klassen und Instanzen

879

23.2 Member

881

23.2.1 Datenmember

881

23.2.2 Funktionsmember

882

23.2.3 Konstante Member

885

23.2.4 Statische Member

887

23.2.5 Operatoren

889

23.2.6 Zugriff auf Member

891

23.2.7 Zugriff von außen

891

23.2.8 Zugriff von innen

894

23.2.9 Der this-Pointer

898

23.2.10 Zugriff durch friends

899

23.3 Vererbung

900

23.3.1 Einfachvererbung

900

23.3.2 Mehrfachvererbung

905

23.3.3 Virtuelle Funktionen

911

23.3.4 Virtuelle Destruktoren

914

23.3.5 Rein virtuelle Funktionen

915

23.4 Zugriffsschutz und Vererbung

916

23.4.1 Geschützte Member

917

23.4.2 Zugriff auf die Basisklasse

917

23.4.3 Modifikation von Zugriffsrechten

921

23.5 Der Lebenszyklus von Objekten

922

23.5.1 Konstruktion von Objekten

925

23.5.2 Destruktion von Objekten

928

23.5.3 Kopieren von Objekten

929

23.5.4 Instanziierung von Objekten

934

23.5.5 Explizite und implizite Verwendung von Konstruktoren

937

23.5.6 Initialisierung eingelagerter Objekte

939

23.5.7 Initialisierung von Basisklassen

941

23.5.8 Instanziierungsregeln

943

23.6 Typüberprüfung und Typumwandlung

946

23.6.1 Dynamische Typüberprüfungen

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.5.1 Ein- und Ausgabe

977

24.5.2 Zugriff

978

24.5.3 Manipulation

981

24.5.4 Vergleich

986

24.5.5 Suchen

987

24.5.6 Speichermanagement

988

24.6 Dynamische Arrays (vector)

990

24.6.1 Die Beispielklasse klasse

990

24.6.2 Einbinden dynamischer Arrays

991

24.6.3 Konstruktion

991

24.6.4 Zugriff

992

24.6.5 Iteratoren

993

24.6.6 Manipulation

994

24.6.7 Speichermanagement

998

24.7 Listen (list)

998

24.7.1 Konstruktion

998

24.7.2 Zugriff

999

24.7.3 Iteratoren

1000

24.7.4 Manipulation

1002

24.7.5 Speichermanagement

1014

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.12.1 Konstruktion

1026

24.12.2 Zugriff

1027

24.12.3 Manipulation

1029

24.13 Relationen (map und multimap)

1030

24.13.1 Konstruktion

1030

24.13.2 Zugriff

1031

24.13.3 Manipulation

1032

24.14 Algorithmen der Standardbibliothek

1032

24.14.1 Vererbung und virtuelle Funktionen in Containern

1037

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