/************************************************************ * BLOCK 0 – Zweck der Datei * ---------------------------------------------------------- * Diese Datei liefert zwei Funktionen für das Spiel: * - createNumbers(len): erzeugt ein Array mit len Zufallszahlen, * in dem GENAU EINE Zahl doppelt vorkommt. * - getDuplicate(numbers, len): findet effizient die doppelte Zahl. * * Technik: * - Beim Erzeugen verhindert ein Binärsuchbaum (BST) Duplikate. * - Beim Finden sortieren wir eine Kopie und vergleichen Nachbarn. ************************************************************/ #include // malloc, free, rand #include // optional für Debug/printf #include // time() für einmaliges srand-Seed #include // memcpy #include "numbers.h" // Deklarationen: createNumbers, getDuplicate #include "bintree.h" // BST-API: addToTree, clearTree, CompareFctType /************************************************************ * BLOCK 1 – Gemeinsame Vergleichsfunktion * ---------------------------------------------------------- * compareUInt: * - Definiert die Ordnung für unsigned int (aufsteigend). * - Geeignet sowohl für den Binärbaum (addToTree) * als auch für qsort. * Rückgabewerte: * - < 0 : a < b → im BST nach LINKS * - = 0 : a == b → Duplikat * - > 0 : a > b → im BST nach RECHTS ************************************************************/ static int compareUInt(const void *a, const void *b) { unsigned int va = *(const unsigned int *)a; unsigned int vb = *(const unsigned int *)b; if (va < vb) return -1; if (va > vb) return 1; return 0; } /************************************************************ * BLOCK 2 – Zahlen erzeugen: createNumbers(len) * ---------------------------------------------------------- * Ziel: * - Ein Array mit len Zufallszahlen im Bereich [1 .. 2*len]. * - Zuerst ALLE eindeutig (via BST geprüft). * - Danach GENAU EINE Zahl absichtlich duplizieren. * - Zum Schluss das Array gleichverteilt mischen (Fisher–Yates). * * Rückgabe: * - Pointer auf dynamisch allokiertes Array (Caller muss free). * - NULL bei Fehlern (z. B. len < 2, malloc/Insert-Fehler). ************************************************************/ unsigned int *createNumbers(unsigned int len) { /*********************** * 2.1 Vorbedingungen & Speicher ***********************/ if (len < 2) // Ein Duplikat macht erst ab 2 Elementen Sinn return NULL; unsigned int *numbers = (unsigned int *)malloc(sizeof(unsigned int) * len); if (!numbers) // Speicherfehler return NULL; /*********************** * 2.2 Einmaliges Zufalls-Seed * (falls main() nicht seedet, sorgen wir einmalig dafür) ***********************/ static int seeded = 0; // Merker: srand nur einmal pro Prozess if (!seeded) { srand((unsigned int)time(NULL)); seeded = 1; } /*********************** * 2.3 BST-Setup & Wertebereich ***********************/ TreeNode *root = NULL; // Leerer Binärbaum zum Duplikat-Check unsigned int range = 2 * len; // Zahlenbereich: 1..2*len /*********************** * 2.4 len-1 EINDEUTIGE Zahlen erzeugen * – jede Zahl sofort gegen den BST prüfen ***********************/ for (unsigned int i = 0; i < len - 1; i++) { unsigned int val; int isDup; // Wiederholen, bis eine wirklich neue Zahl eingefügt wurde for (;;) { isDup = 0; // vor jedem Insert zurücksetzen val = (unsigned int)(rand() % range) + 1; // Kandidat in [1..2*len] // Versuch, val in den Baum einzufügen (Kopie wird im Knoten gespeichert) TreeNode *newRoot = addToTree(root, &val, sizeof(val), compareUInt, &isDup); // Fehlerfall: Es wäre ein neuer Knoten, aber newRoot ist NULL (z. B. malloc-Fehler) if (newRoot == NULL && isDup == 0) { free(numbers); // Array freigeben clearTree(root); // bisherige Baumknoten freigeben return NULL; // sauber abbrechen } // Wurzel ggf. aktualisieren (z. B. wenn Baum vorher leer war) if (newRoot) { root = newRoot; } if (!isDup) { // Wert war eindeutig → ins Array übernehmen und weiter zum nächsten i numbers[i] = val; break; } // sonst: Duplikat → neue Zufallszahl probieren } } /*********************** * 2.5 GENAU EIN Duplikat erzeugen * – eine der bestehenden Zahlen zufällig wählen und erneut eintragen ***********************/ unsigned int idx = (unsigned int)(rand() % (len - 1)); // Quelle in [0..len-2] numbers[len - 1] = numbers[idx]; // Duplikat absichtlich erzeugt /*********************** * 2.6 Gleichverteiltes Mischen (Fisher–Yates) ***********************/ for (unsigned int i = len - 1; i > 0; i--) { unsigned int j = (unsigned int)(rand() % (i + 1)); // j ∈ [0..i] unsigned int tmp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = tmp; } /*********************** * 2.7 Aufräumen & Rückgabe ***********************/ clearTree(root); // BST wird nicht mehr gebraucht return numbers; // Ownership des Arrays liegt beim Aufrufer (free(numbers)) } /************************************************************ * BLOCK 3 – Duplikat finden: getDuplicate(numbers, len) * ---------------------------------------------------------- * Idee: * - Original-Array unangetastet lassen → KOPIE erstellen. * - Kopie aufsteigend sortieren (qsort mit demselben Comparator). * - Ein linearer Durchlauf findet das erste Paar identischer Nachbarn. * * Rückgabe: * - die doppelte Zahl * - 0 bei Fehlern (z. B. ungültige Parameter, malloc-Fehler). ************************************************************/ unsigned int getDuplicate(const unsigned int numbers[], unsigned int len) { /*********************** * 3.1 Vorbedingungen & Kopie allokieren ***********************/ if (!numbers || len < 2) // ungültig oder zu kurz return 0; unsigned int *copy = (unsigned int *)malloc(sizeof(unsigned int) * len); if (!copy) // Speicherfehler return 0; memcpy(copy, numbers, sizeof(unsigned int) * len); // Original in Kopie übertragen /*********************** * 3.2 Kopie sortieren (qsort + compareUInt) ***********************/ qsort(copy, len, sizeof(unsigned int), compareUInt); /*********************** * 3.3 Nachbarvergleich: erstes Paar gleicher Werte = Duplikat ***********************/ unsigned int result = 0; for (unsigned int i = 0; i + 1 < len; i++) { if (copy[i] == copy[i + 1]) { result = copy[i]; break; // Duplikat gefunden → fertig } } /*********************** * 3.4 Aufräumen & Rückgabe ***********************/ free(copy); // Kopie freigeben return result; // 0, falls (unerwartet) kein Duplikat gefunden } /************************************************************ * BLOCK 4 – Hinweise für die Vorstellung * ---------------------------------------------------------- * Ownership: * - Das von createNumbers zurückgegebene Array muss vom Aufrufer * später mit free(numbers) freigegeben werden. * * Fehlerbehandlung: * - Bei jedem Fehlerpfad werden ALLLE angelegten Ressourcen sauber * freigegeben (Array/Kopie/Baum). * * Komplexität: * - Erzeugen: O(n log n) durch BST-Einfügen + O(n) fürs Shuffle. * - Finden: O(n log n) durch qsort + O(n) für den Nachbarvergleich. * * Zusammenarbeit: * - addToTree setzt bei Gleichheit isDuplicate=1 (Duplikat), * und liefert bei neuen Werten die (ggf. neue) Wurzel zurück. * - clearTree gibt ALLE Knoten inkl. Datenkopien frei. ************************************************************/