← Zurück zur Übersicht

Zusammenfassung & Klausurvorbereitung

Fortgeschrittene Konzepte im Überblick

Fortgeschrittene Algorithmen und Programmierung in C

Vorlesung 13 | HTW Berlin | WiSe 2025/26

Semesterübersicht

VL 1-4

  • Einführung
  • Datentypen & Casting
  • Operatoren
  • Git

VL 5-7

  • Schleifen & Steuerung
  • Arrays & Strings
  • Zeiger (Pointers)

VL 8-9

  • Strukturen Teil 1
  • Strukturen Teil 2
  • Arrays & Funktionen

VL 10-12

  • Rekursion
  • Sortieralgorithmen
  • Binäre Suche & O()

1. Zeiger (Pointers)

int x = 42; int *ptr = &x; // ptr zeigt auf x printf("%d\n", x); // 42 printf("%p\n", ptr); // Adresse printf("%d\n", *ptr); // 42 (Dereferenzierung) *ptr = 100; // x wird zu 100! printf("%d\n", x); // 100

Wichtige Operatoren

&Adresse von ("Adress-of")
*Wert an Adresse ("Dereferenzierung")

Speicherbild:

x (0x1000): 42

ptr: 0x1000 → zeigt auf x

Klausurtipp: *ptr = Wert an der Adresse, &x = Adresse von x

2. Zeiger und Arrays

int arr[5] = {10, 20, 30, 40, 50}; int *ptr = arr; // arr ist schon Adresse! printf("%d\n", arr[0]); // 10 printf("%d\n", *ptr); // 10 printf("%d\n", *(ptr+2)); // 30 printf("%d\n", ptr[2]); // 30

arr[i] = *(arr + i)

Array-Name ist Zeiger auf erstes Element!

Zeiger-Arithmetik

ptr++ // Nächstes Element ptr + 3 // 3 Elemente weiter ptr - 1 // 1 Element zurück

Bei int-Array: ptr+1 springt 4 Bytes (sizeof(int))

3. Strukturen (struct)

struct Person { char name[50]; int alter; }; struct Person p1; strcpy(p1.name, "Anna"); p1.alter = 23; printf("%s, %d\n", p1.name, p1.alter);
p1

name: "Anna"

alter: 23

strcpy() für Strings!

Nicht: p1.name = "Anna";

4. Zeiger auf Strukturen & Pfeil-Operator

struct Person p1 = {"Anna", 23}; struct Person *ptr = &p1; // Mit Punkt (umständlich): (*ptr).alter = 25; // Mit Pfeil (elegant): ptr->alter = 25; printf("%s: %d\n", ptr->name, ptr->alter);

Regel

Variable:p1.alterPunkt
Zeiger:ptr->alterPfeil

ptr->x = (*ptr).x

Klausurtipp: Bei Funktionen mit struct Person *p immer Pfeil-Operator!

5. Call by Value vs. Call by Reference

Call by Value

void aendere(int x) { x = 100; // Nur Kopie! } int main() { int a = 5; aendere(a); printf("%d", a); // Immer noch 5! }

Original bleibt unverändert

Call by Reference

void aendere(int *x) { *x = 100; // Original ändern! } int main() { int a = 5; aendere(&a); // Adresse übergeben! printf("%d", a); // Jetzt 100! }

Original wird geändert

6. Rekursion

Fakultät

int fakultaet(int n) { // Basisfall if (n <= 1) { return 1; } // Rekursiver Aufruf return n * fakultaet(n - 1); } // fakultaet(5) = 5 * 4 * 3 * 2 * 1 = 120

Rekursion braucht:

  1. Basisfall - Abbruchbedingung
  2. Rekursiver Aufruf - ruft sich selbst auf
  3. Fortschritt - kommt näher zum Basisfall

Ohne Basisfall: Endlose Rekursion → Stack Overflow!

7. Sortieralgorithmen

Selection Sort

Finde kleinstes, tausche an Anfang

for (int i = 0; i < n-1; i++) { int min = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[min]) min = j; } swap(&arr[i], &arr[min]); }

Insertion Sort

Füge an richtiger Stelle ein

for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; }

Bubble Sort

Benachbarte vergleichen & tauschen

for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { swap(&arr[j], &arr[j+1]); } } }

Alle drei: O(n²) Zeitkomplexität - Langsam bei großen Arrays!

8. Binäre Suche

int binarySearch(int arr[], int n, int x) { int left = 0, right = n - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == x) return mid; // Gefunden! else if (arr[mid] < x) left = mid + 1; // Rechte Hälfte else right = mid - 1; // Linke Hälfte } return -1; // Nicht gefunden }

Voraussetzung

Array muss sortiert sein!

Vorteil

O(log n) - viel schneller als lineare Suche O(n)

Bei 1.000.000 Elementen: max. 20 Vergleiche!

9. Big-O Notation (Zeitkomplexität)

Notation Name Beispiel n=1000
O(1) Konstant Array-Zugriff arr[5] 1
O(log n) Logarithmisch Binäre Suche ~10
O(n) Linear Lineare Suche, Summe 1.000
O(n²) Quadratisch Bubble Sort, Selection Sort 1.000.000

Klausurtipp: Zählen Sie verschachtelte Schleifen! 1 Schleife = O(n), 2 verschachtelt = O(n²)

10. Häufige Fehler vermeiden

Häufige Fehler

  • Punkt statt Pfeil bei Zeiger: ptr.x
  • & vergessen bei Call by Reference
  • Kein Basisfall bei Rekursion
  • Binäre Suche auf unsortiertem Array
  • strcpy vergessen bei Strings
  • struct vergessen vor Typname
  • Array-Größe nicht übergeben

Richtig machen

  • Zeiger: ptr->x
  • aendere(&var);
  • if (n <= 1) return 1;
  • Erst sortieren, dann binär suchen
  • strcpy(p.name, "Text");
  • struct Person p;
  • void f(int arr[], int n)

Klausur-Checkliste

Das sollten Sie können:

  • Zeiger deklarieren und dereferenzieren
  • Call by Reference implementieren
  • Strukturen definieren und verwenden
  • Pfeil-Operator korrekt einsetzen
  • Arrays von Strukturen verwalten
  • Rekursive Funktionen schreiben
  • Sortieralgorithmen verstehen
  • Binäre Suche implementieren
  • Big-O Komplexität bestimmen

Klausurtipps

  • Bei Zeigern: Skizzieren Sie, wohin der Zeiger zeigt!
  • Rekursion: Basisfall zuerst schreiben
  • Strukturen: Immer struct davor
  • Komplexität: Schleifen zählen

Am Klausurtag

  • Code lesbar schreiben
  • Randfälle bedenken
  • Bei Rekursion: Basisfall prüfen

Schnellreferenz

// Zeiger int *ptr = &x; *ptr = 10; // Wert setzen int val = *ptr; // Wert lesen
// Struktur struct Person p; p.alter = 25; ptr->alter = 25;
// Rekursion int f(int n) { if (n <= 1) return 1; return n * f(n-1); }

Lineare Suche

O(n)

Binäre Suche

O(log n)

Bubble Sort

O(n²)

Zeiger: Detailwissen

Deklaration & Initialisierung

int x = 42; int *ptr = &x; // Zeiger auf x int *ptr2 = NULL; // Null-Zeiger // Zugriff int wert = *ptr; // Dereferenzierung *ptr = 100; // Wert ändern
Wichtig: Immer initialisieren! Uninitialisierte Zeiger führen zu Abstürzen.

Häufige Fehler

// ❌ FALSCH int *ptr; *ptr = 10; // Zeigt irgendwohin! // ✅ RICHTIG int x; int *ptr = &x; *ptr = 10; // Sicher
NULL-Check:
if (ptr != NULL) { *ptr = 10; }

Arrays und Zeiger

Array-Namen sind Zeiger!

int arr[] = {10, 20, 30, 40}; // Alle äquivalent: arr[0] // 10 *arr // 10 *(arr + 0) // 10 arr[2] // 30 *(arr + 2) // 30

Pointer Arithmetik

int *ptr = arr;
ptr++; // Zeigt auf arr[1]
ptr += 2; // Zeigt auf arr[3]

Array-Größe

int size = sizeof(arr) / sizeof(arr[0]);
// size = 4

Strukturen: Vertiefung

Verschachtelte Strukturen

struct Adresse { char stadt[50]; int plz; }; struct Person { char name[50]; struct Adresse wohnort; }; // Verwendung: struct Person p; strcpy(p.wohnort.stadt, "Berlin"); p.wohnort.plz = 10115;

Arrays in Strukturen

struct Klasse { char name[30]; int noten[10]; int anzahl_noten; }; // Noten hinzufügen: struct Klasse k; k.noten[0] = 95; k.noten[1] = 87; k.anzahl_noten = 2;
Tipp: Strukturen können auch Arrays enthalten - nützlich für variable Datenmengen pro Element!

Call by Reference: Praktische Beispiele

Wann Call by Reference?

✅ Anwendungsfälle

  • Wert ändern (swap, increment)
  • Große Strukturen (Performance)
  • Arrays modifizieren
  • Mehrere Rückgabewerte
// Mehrere Rückgabewerte void minMax(int arr[], int n, int *min, int *max) { *min = arr[0]; *max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] < *min) *min = arr[i]; if (arr[i] > *max) *max = arr[i]; } }

Aufruf & Nutzung

int zahlen[] = {5, 2, 9, 1, 7}; int minimum, maximum; minMax(zahlen, 5, &minimum, &maximum); printf("Min: %d\n", minimum); // 1 printf("Max: %d\n", maximum); // 9
Merke: & beim Aufruf, * in der Funktion!

Rekursion: Wichtige Muster

Linear Recursion

// Fakultät int fak(int n) { if (n <= 1) return 1; return n * fak(n - 1); } // Array-Summe int sum(int arr[], int n) { if (n == 0) return 0; return arr[n-1] + sum(arr, n-1); }

Rekursive Summe

// Summe der Zahlen 1 bis n int summe(int n) { if (n == 0) return 0; return n + summe(n-1); } // summe(3) = 3 + 2 + 1 + 0 = 6
Merke: Jeder rekursive Aufruf verkleinert das Problem bis zum Basisfall!

Rekursions-Checklist:

  • ✓ Basisfall definiert?
  • ✓ Problem wird kleiner?
  • ✓ Erreicht immer Basisfall?
  • ✓ Keine Endlosrekursion?

Selection Sort: Schritt für Schritt

Algorithmus

void selectionSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { // Finde Minimum im Rest int min_idx = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[min_idx]) { min_idx = j; } } // Tausche int temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; } }

Beispiel: [64, 25, 12, 22, 11]

i=0: [11, 25, 12, 22, 64]
i=1: [11, 12, 25, 22, 64]
i=2: [11, 12, 22, 25, 64]
i=3: [11, 12, 22, 25, 64]
Eigenschaften:
⏱ Zeitkomplexität: O(n²)
💾 Speicher: O(1) - in-place
⚠️ NICHT stabil

Insertion Sort: Schritt für Schritt

Algorithmus

void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // Verschiebe größere Elemente while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

Beispiel: [5, 2, 4, 6, 1, 3]

i=1: [2, 5, 4, 6, 1, 3]
i=2: [2, 4, 5, 6, 1, 3]
i=3: [2, 4, 5, 6, 1, 3]
i=4: [1, 2, 4, 5, 6, 3]
i=5: [1, 2, 3, 4, 5, 6]
Eigenschaften:
⏱ Best: O(n), Worst: O(n²)
💾 Speicher: O(1)
✅ Stabil!

Bubble Sort: Optimiert

Mit und ohne Optimierung

Ohne Flag (Naiv)

void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { // Tausche int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }

⚠️ Läuft immer O(n²), auch wenn sortiert!

Mit Flag (Optimiert)

void bubbleSortOpt(int arr[], int n) { for (int i = 0; i < n-1; i++) { int swapped = 0; for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = 1; } } if (!swapped) break; // ✅ Fertig! } }

✅ Best Case: O(n) bei sortiertem Array!

Binäre Suche: Visualisierung

Suche nach 23 in: [3, 7, 11, 18, 23, 31, 40, 55, 68]

Schritt 1: [3, 7, 11, 18, 📍23, 31, 40, 55, 68] - Mitte=23 → Gefunden!

Suche nach 18:

Schritt 1: [3, 7, 11, 18, 📍23, 31, 40, 55, 68] - 18 < 23 → Links
Schritt 2: [3, 7, 📍11, 18] - 18 > 11 → Rechts
Schritt 3: [📍18] - Gefunden!
int binaereSuche(int arr[], int n, int x) { int links = 0, rechts = n - 1; while (links <= rechts) { int mitte = links + (rechts - links) / 2; // Overflow vermeiden! if (arr[mitte] == x) return mitte; if (arr[mitte] < x) links = mitte + 1; else rechts = mitte - 1; } return -1; // Nicht gefunden }

Komplexität: Vollständiger Vergleich

Algorithmus Best Case Average Case Worst Case Speicher Stabil?
Selection Sort O(n²) O(n²) O(n²) O(1) ❌
Insertion Sort O(n) O(n²) O(n²) O(1) ✅
Bubble Sort O(n) O(n²) O(n²) O(1) ✅
Binäre Suche O(1) O(log n) O(log n) O(1) -
Lineare Suche O(1) O(n) O(n) O(1) -
Merksatz: Bubble Sort und Selection Sort haben beide O(n²) - einfach zu implementieren, aber langsam bei großen Arrays!

Häufige Code-Patterns

1. Swap-Pattern

// Zwei Werte tauschen void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // Aufruf: swap(&x, &y);

2. Akkumulator-Pattern

// Summe berechnen int summe(int arr[], int n) { int sum = 0; // Akkumulator for (int i = 0; i < n; i++) { sum += arr[i]; } return sum; }

3. Zähler-Pattern

// Gerade Zahlen zählen int countEven(int arr[], int n) { int count = 0; for (int i = 0; i < n; i++) { if (arr[i] % 2 == 0) { count++; } } return count; }

4. Flag-Pattern

// Element gefunden? int contains(int arr[], int n, int x) { int found = 0; // Flag for (int i = 0; i < n; i++) { if (arr[i] == x) { found = 1; break; } } return found; }

Debugging & Fehlersuche

Häufige Laufzeitfehler

Segmentation Fault
  • Uninitialisierte Zeiger
  • Array-Index außerhalb Grenzen
  • Dereferenzierung von NULL
  • Stack Overflow (zu tiefe Rekursion)
// ❌ FEHLER int *ptr; *ptr = 10; // Crash! // ✅ RICHTIG int x; int *ptr = &x; *ptr = 10; // OK

Debug-Strategien

1. Print-Debugging
printf("DEBUG: i=%d, arr[i]=%d\n", i, arr[i]);
2. Assertions
assert(ptr != NULL); assert(i >= 0 && i < n);
3. Schrittweise Testen
  • Kleine Testfälle
  • Edge Cases prüfen
  • Eine Funktion nach der anderen

Klausur-Strategie

Vor der Klausur

📚 Lernplan:
  • Woche 1: Theorie wiederholen
  • Woche 2: Code schreiben üben
  • 3 Tage vorher: Probeklausur
  • 1 Tag vorher: Nur durchsehen
✍️ Üben:
  • Code mit Hand schreiben!
  • Ohne IDE/Compiler
  • Zeitlimit setzen
  • Probeklausuren durcharbeiten

Während der Klausur

⏰ Zeitmanagement (90 Min):
  • Alle Aufgaben überfliegen (5 Min)
  • Einfache zuerst! (30 Min)
  • Schwierige Aufgaben (40 Min)
  • Durchsehen & Korrigieren (15 Min)
⚠️ Häufige Fehler vermeiden:
  • Semikolon vergessen
  • = statt ==
  • Array-Index off-by-one
  • Uninitialisierte Variablen
  • Rekursion ohne Basisfall

Must-Know: Diese Codes auswendig!

Swap

void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }

Min/Max finden

int findMax(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) max = arr[i]; } return max; }

Lineare Suche

int search(int arr[], int n, int x) { for (int i = 0; i < n; i++) { if (arr[i] == x) return i; } return -1; }

Fakultät (rekursiv)

int fak(int n) { if (n <= 1) return 1; return n * fak(n - 1); }

Array kopieren

void copy(int dest[], int src[], int n) { for (int i = 0; i < n; i++) { dest[i] = src[i]; } }

Primzahl prüfen

int isPrime(int n) { if (n <= 1) return 0; for (int i = 2; i*i <= n; i++) { if (n % i == 0) return 0; } return 1; }

Last-Minute Checklist

✅ Syntax-Checklist

  • □ Semikolon nach jeder Anweisung
  • □ Klammern: { } bei Blöcken
  • □ == für Vergleich, = für Zuweisung
  • □ Zeiger: * bei Deklaration & Dereferenzierung
  • □ Zeiger: & für Adresse
  • □ Struktur: . für Objekt, -> für Zeiger
  • □ Arrays: Index startet bei 0
  • □ Schleifen: i < n (nicht i <= n)
  • □ Rekursion: Basisfall ZUERST

💡 Konzepte wiederholen

Zeiger & Speicher:
  • Was ist ein Zeiger?
  • Call by Value vs. Reference
  • Array-Pointer-Beziehung
Algorithmen:
  • 3 Sortieralgorithmen
  • Binäre vs. Lineare Suche
  • Rekursion vs. Iteration
Komplexität:
  • O(1), O(log n), O(n), O(n²)
  • Best/Average/Worst Case
  • In-place vs. nicht in-place

Viel Erfolg bei der Klausur!

Sie haben dieses Semester viel gelernt!

Klausurtermin: 5. Februar 2026
Bei Fragen: Moodle oder Sprechstunde

Fortgeschrittene Algorithmen und Programmierung
HTW Berlin | WiSe 2025/26

1 / 15