Programmierübungen
Algorithmen und Datenstrukturen

Sortieren

1. C++ mit wxWidgets-GUI: Verschiedene Sortierverfahren.
   Programm zum Vervollständigen: gra-sort-angabe.cpp
   Musterlösung: gra-sort.cpp.
   (siehe Programmierübungen C für GUI-lose Sortier-Übungen!)

Listen

2. C++: Stack als Liste.
   Musterlösung: list-stack.cpp.
3. C: Sortierte, einfach verkettete Liste.
   Musterlösung: liste.c.
4. C++, letzte Teilaufgabe mit Templates:
   Einfügen & Löschen in sortierter Liste (einfach & doppelt verkettet).
   Musterlösungen:
   Grundlösung: sorted-list.cpp,
   Implementierung mit **: sorted-list-dblptr.cpp,
   Doppelt verkettete Liste: sorted-dbl-list.cpp,
   Implementierung als Template-Klasse: sorted-list-templ.cpp.
5. C++: Radix-Sort mit Listen.
   Musterlösung: radixsort.cpp.
6. C: Radix-Sort mit Listen.
   Musterlösung: radix.c.
7. C: Listen von Arrays: Textfiles seitenweise verkehrtherum ausgeben.
   Musterlösung: pagerev.c.
8. C: Arrays von Listen: Textfiles nach Zeilenlänge sortiert ausgeben.
   Musterlösung: lensort.c.

Bäume & Hashtables

9. C++, letzte Teilaufgabe mit STL: Wort-Vorkommen zählen.
   Musterlösungen:
   Grundlösung: baum.cpp,
   Mit grafischer Ausgabe & Statistik: baum-stat.cpp,
   Mit getFirst & getNext: baum-first+next.cpp,
   Mit Löschen (konventionell): baum-delete.cpp,
   Mit Löschen (Pointer-auf-Pointer): baum-delete-pp.cpp,
   Mit Löschen (rekursiv): baum-delete-rec.cpp,
   Unter Verwendung von STL map: baum-map.cpp.
10. C: Hashtable: Wortindex.
    Zu komplettierendes Programm: xref-hash-ang.c.
    Musterlösung: xref-hash.c.
11. C: Unbalancierter Baum: Wortindex.
    Musterlösung: xref-tree.c.
12. C, schwierig: Balancierter Baum: Wortindex.
    Musterlösung: xref-tree-bal.c.
13. C, schwierig: Trie: Wortindex.
    Musterlösung: xref-trie.c.
14. C: Decodierung von Morse-Zeichen.
    Musterlösung: morse.c.
15. C++ und/oder C: Unbalancierter Baum mit Löschen und getNext.
    Musterlösung: baum.cpp (in C: baum-c.c).
16. C: Priority Queue (heap).
    Musterlösung: priqueue.c.

Backtracking

17. C mit SDL-Grafik: Backtracking: 8-Damen-Problem.
    Musterlösung: queens.c, queens-stepbystep.c.
18. C mit SDL-Grafik: Backtracking: Travelling Salesman.
    Vorgegebenes Programm zum Weiterschreiben: travel-angabe.c.
    Musterlösung: travel.c.
19. C: Backtracking, Strukturen, qsort, File-I/O formatiert: Rucksack packen.
    Meine Gegenstands-Liste: rucksack.txt.
    Musterlösung: rucksack.c, rucksack-opt.c, rucksack-file.c.
20. C: Backtracking: Graph färben.
    Musterlösung: colors.c.
21. C: Backtracking: Buchstabensumme.
    Programm zum Vervollständigen: textsumme-ang.c
    Musterlösung: textsumme.c, textsumme-tricky.c.
22. C++ mit wxWidgets-GUI: Backtracking: Sudoku
    Übungsaufgabe ist nur der Lösungs-Code:
    Gesucht ist der .cpp-File mit der Implementierung der folgenden Klasse: Solver.h
    Zur Ein- und Ausgabe soll der Lösungs-Code Methoden der folgenden GUI-Klasse aufrufen: Sudoku.h
    Die Implementierung dieser Klasse kommt von mir, sie ist nicht Übungsaufgabe: sudoku.cpp, sudoku-main.cpp
    Musterlösung: solver.cpp.

Graphen

23. C mit SDL-Grafik: Graphen: Kruskal's Algorithmus.
    Musterlösung: kruskal.c.
    Für Interessierte: Algorithmus von Prim: prim.c.
24. C: Graphen: Breadth-First-Durchlauf (zählen, verketten, Tiefe eintragen).
    Hauptprogramm zum Weiterschreiben: bfs-main.c
    Test-Graph mit 9 Knoten: bfs-data
    Erwartete Ausgabe bei ./bfs 9 0 < bfs-data : bfs-out
    Musterlösung: bfs.c.
25. C: Graphen: Depth-First-Durchlauf (durchnummerieren, Anzahl In-Edges eintragen).
    Hauptprogramm zum Weiterschreiben: dfs-main.c
    Test-Graph mit 9 Knoten: bfs-data
    Erwartete Ausgabe bei ./dfs 9 0 < bfs-data : dfs-out
    Musterlösung: dfs.c.
26. C mit SDL-Grafik: Graphen: Topologisches Sortieren.
    Programm zum Vervollständigen: topsort-angabe.c
    Musterlösung: topsort.c, topsort-tail.c.