generated from freudenreichan/info2Praktikum-DobleSpiel
151 lines
15 KiB
HTML
151 lines
15 KiB
HTML
<html>
|
|
<head>
|
|
<title>numbers.c</title>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
|
|
<style type="text/css">
|
|
.s0 { color: #b3ae60;}
|
|
.s1 { color: #bcbec4;}
|
|
.s2 { color: #6aab73;}
|
|
.s3 { color: #7a7e85;}
|
|
.s4 { color: #cf8e6d;}
|
|
.s5 { color: #bcbec4;}
|
|
.s6 { color: #2aacb8;}
|
|
</style>
|
|
</head>
|
|
<body bgcolor="#1e1f22">
|
|
<table CELLSPACING=0 CELLPADDING=5 COLS=1 WIDTH="100%" BGCOLOR="#606060" >
|
|
<tr><td><center>
|
|
<font face="Arial, Helvetica" color="#000000">
|
|
numbers.c</font>
|
|
</center></td></tr></table>
|
|
<pre><span class="s0">#include </span><span class="s2"><stdlib.h></span>
|
|
<span class="s0">#include </span><span class="s2"><stdio.h></span>
|
|
<span class="s0">#include </span><span class="s2"><time.h></span>
|
|
<span class="s0">#include </span><span class="s2"><string.h></span>
|
|
<span class="s0">#include </span><span class="s2">"numbers.h"</span>
|
|
<span class="s0">#include </span><span class="s2">"bintree.h"</span>
|
|
|
|
<span class="s3">//TODO: getDuplicate und createNumbers implementieren</span>
|
|
<span class="s3">/* * * Erzeugen eines Arrays mit der vom Nutzer eingegebenen Anzahl an Zufallszahlen.
|
|
* Sicherstellen, dass beim Befüllen keine Duplikate entstehen.
|
|
* Duplizieren eines zufälligen Eintrags im Array.
|
|
* in `getDuplicate()`: Sortieren des Arrays und Erkennen der doppelten Zahl durch Vergleich benachbarter Elemente. */</span>
|
|
|
|
<span class="s3">// Returns len random numbers between 1 and 2x len in random order which are all different, except for two entries.</span>
|
|
<span class="s3">// Returns NULL on errors. Use your implementation of the binary search tree to check for possible duplicates while</span>
|
|
<span class="s3">// creating random numbers.</span>
|
|
<span class="s3">// Vergleichsfunktion für qsort</span>
|
|
<span class="s4">static int </span><span class="s1">compareUnsignedInt</span><span class="s5">(</span><span class="s4">const void </span><span class="s5">*</span><span class="s1">a</span><span class="s5">, </span><span class="s4">const void </span><span class="s5">*</span><span class="s1">b</span><span class="s5">)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s4">const unsigned int </span><span class="s5">*</span><span class="s1">x </span><span class="s5">= (</span><span class="s4">const unsigned int </span><span class="s5">*)</span><span class="s1">a</span><span class="s5">;</span>
|
|
<span class="s4">const unsigned int </span><span class="s5">*</span><span class="s1">y </span><span class="s5">= (</span><span class="s4">const unsigned int </span><span class="s5">*)</span><span class="s1">b</span><span class="s5">;</span>
|
|
|
|
<span class="s4">if </span><span class="s5">(*</span><span class="s1">x </span><span class="s5">< *</span><span class="s1">y</span><span class="s5">) </span><span class="s4">return </span><span class="s5">-</span><span class="s6">1</span><span class="s5">;</span>
|
|
<span class="s4">if </span><span class="s5">(*</span><span class="s1">x </span><span class="s5">> *</span><span class="s1">y</span><span class="s5">) </span><span class="s4">return </span><span class="s6">1</span><span class="s5">;</span>
|
|
<span class="s4">return </span><span class="s6">0</span><span class="s5">;</span>
|
|
<span class="s5">}</span>
|
|
|
|
<span class="s3">// Fisher-Yates Shuffle Algorithmus zum Mischen des Arrays</span>
|
|
<span class="s4">static void </span><span class="s1">shuffleArray</span><span class="s5">(</span><span class="s4">unsigned int </span><span class="s5">*</span><span class="s1">array</span><span class="s5">, </span><span class="s4">unsigned int </span><span class="s1">n</span><span class="s5">)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s4">if </span><span class="s5">(</span><span class="s1">n </span><span class="s5">> </span><span class="s6">1</span><span class="s5">)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s4">for </span><span class="s5">(</span><span class="s4">unsigned int </span><span class="s1">i </span><span class="s5">= </span><span class="s1">n </span><span class="s5">- </span><span class="s6">1</span><span class="s5">; </span><span class="s1">i </span><span class="s5">> </span><span class="s6">0</span><span class="s5">; </span><span class="s1">i</span><span class="s5">--)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s4">unsigned int </span><span class="s1">j </span><span class="s5">= </span><span class="s1">rand</span><span class="s5">() % (</span><span class="s1">i </span><span class="s5">+ </span><span class="s6">1</span><span class="s5">);</span>
|
|
<span class="s4">unsigned int </span><span class="s1">temp </span><span class="s5">= </span><span class="s1">array</span><span class="s5">[</span><span class="s1">i</span><span class="s5">];</span>
|
|
<span class="s1">array</span><span class="s5">[</span><span class="s1">i</span><span class="s5">] = </span><span class="s1">array</span><span class="s5">[</span><span class="s1">j</span><span class="s5">];</span>
|
|
<span class="s1">array</span><span class="s5">[</span><span class="s1">j</span><span class="s5">] = </span><span class="s1">temp</span><span class="s5">;</span>
|
|
<span class="s5">}</span>
|
|
<span class="s5">}</span>
|
|
<span class="s5">}</span>
|
|
|
|
<span class="s4">unsigned int </span><span class="s5">*</span><span class="s1">createNumbers</span><span class="s5">(</span><span class="s4">unsigned int </span><span class="s1">len</span><span class="s5">)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s4">if </span><span class="s5">(</span><span class="s1">len </span><span class="s5">< </span><span class="s6">2</span><span class="s5">) </span><span class="s4">return </span><span class="s1">NULL</span><span class="s5">;</span>
|
|
|
|
<span class="s3">// 1. Array reservieren</span>
|
|
<span class="s4">unsigned int </span><span class="s5">*</span><span class="s1">numbers </span><span class="s5">= </span><span class="s1">malloc</span><span class="s5">(</span><span class="s1">len </span><span class="s5">* </span><span class="s4">sizeof</span><span class="s5">(</span><span class="s4">unsigned int</span><span class="s5">));</span>
|
|
<span class="s4">if </span><span class="s5">(</span><span class="s1">numbers </span><span class="s5">== </span><span class="s1">NULL</span><span class="s5">) </span><span class="s4">return </span><span class="s1">NULL</span><span class="s5">;</span>
|
|
|
|
<span class="s3">// Hilfsvariablen für den Baum</span>
|
|
<span class="s1">TreeNode </span><span class="s5">*</span><span class="s1">root </span><span class="s5">= </span><span class="s1">NULL</span><span class="s5">;</span>
|
|
<span class="s4">int </span><span class="s1">isDuplicate </span><span class="s5">= </span><span class="s6">0</span><span class="s5">;</span>
|
|
<span class="s4">unsigned int </span><span class="s1">count </span><span class="s5">= </span><span class="s6">0</span><span class="s5">;</span>
|
|
|
|
<span class="s3">// 2. PHASE 1: Erzeuge (len - 1) EINZIGARTIGE Zahlen mit Hilfe des Baums</span>
|
|
<span class="s3">// Wir nutzen den Baum als "Türsteher"</span>
|
|
<span class="s4">while </span><span class="s5">(</span><span class="s1">count </span><span class="s5">< </span><span class="s1">len </span><span class="s5">- </span><span class="s6">1</span><span class="s5">)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s3">// Zufallszahl generieren (1 bis 2*len)</span>
|
|
<span class="s4">unsigned int </span><span class="s1">value </span><span class="s5">= (</span><span class="s1">rand</span><span class="s5">() % (</span><span class="s6">2 </span><span class="s5">* </span><span class="s1">len</span><span class="s5">)) + </span><span class="s6">1</span><span class="s5">;</span>
|
|
|
|
<span class="s3">// Versuchen, in den Baum einzufügen</span>
|
|
<span class="s3">// Wir übergeben &isDuplicate, damit der Baum Duplikate ABLEHNT.</span>
|
|
<span class="s1">root </span><span class="s5">= </span><span class="s1">addToTree</span><span class="s5">(</span><span class="s1">root</span><span class="s5">, &</span><span class="s1">value</span><span class="s5">, </span><span class="s4">sizeof</span><span class="s5">(</span><span class="s4">unsigned int</span><span class="s5">), </span><span class="s1">compareUnsignedInt</span><span class="s5">, &</span><span class="s1">isDuplicate</span><span class="s5">);</span>
|
|
|
|
<span class="s3">// Prüfen: War es ein Duplikat?</span>
|
|
<span class="s4">if </span><span class="s5">(</span><span class="s1">isDuplicate </span><span class="s5">== </span><span class="s6">0</span><span class="s5">)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s3">// Nein, es war neu! -> Ins Array schreiben</span>
|
|
<span class="s1">numbers</span><span class="s5">[</span><span class="s1">count</span><span class="s5">] = </span><span class="s1">value</span><span class="s5">;</span>
|
|
<span class="s1">count</span><span class="s5">++;</span>
|
|
<span class="s5">}</span>
|
|
<span class="s3">// Falls isDuplicate == 1, machen wir einfach weiter (while-Schleife läuft weiter)</span>
|
|
<span class="s5">}</span>
|
|
|
|
<span class="s3">// 3. PHASE 2: Das garantierte Duplikat erzeugen</span>
|
|
<span class="s3">// Wir wählen zufällig eine der bereits existierenden Zahlen aus</span>
|
|
<span class="s4">unsigned int </span><span class="s1">randomIndex </span><span class="s5">= </span><span class="s1">rand</span><span class="s5">() % (</span><span class="s1">len </span><span class="s5">- </span><span class="s6">1</span><span class="s5">);</span>
|
|
<span class="s4">unsigned int </span><span class="s1">duplicateValue </span><span class="s5">= </span><span class="s1">numbers</span><span class="s5">[</span><span class="s1">randomIndex</span><span class="s5">];</span>
|
|
|
|
<span class="s3">// Wir schreiben das Duplikat an die allerletzte Stelle</span>
|
|
<span class="s1">numbers</span><span class="s5">[</span><span class="s1">len </span><span class="s5">- </span><span class="s6">1</span><span class="s5">] = </span><span class="s1">duplicateValue</span><span class="s5">;</span>
|
|
|
|
<span class="s3">// Optional: Duplikat auch in den Baum einfügen (Modus: Akzeptieren / isDuplicate = NULL)</span>
|
|
<span class="s3">// Damit der Baum konsistent zum Array ist (falls man ihn später noch braucht).</span>
|
|
<span class="s1">root </span><span class="s5">= </span><span class="s1">addToTree</span><span class="s5">(</span><span class="s1">root</span><span class="s5">, &</span><span class="s1">duplicateValue</span><span class="s5">, </span><span class="s4">sizeof</span><span class="s5">(</span><span class="s4">unsigned int</span><span class="s5">), </span><span class="s1">compareUnsignedInt</span><span class="s5">, </span><span class="s1">NULL</span><span class="s5">);</span>
|
|
|
|
<span class="s3">// 4. Mischen</span>
|
|
<span class="s3">// Da das Duplikat jetzt immer ganz am Ende steht, müssen wir mischen.</span>
|
|
<span class="s1">shuffleArray</span><span class="s5">(</span><span class="s1">numbers</span><span class="s5">, </span><span class="s1">len</span><span class="s5">);</span>
|
|
|
|
<span class="s3">// 5. Aufräumen</span>
|
|
<span class="s3">// Der Baum war nur ein Hilfsmittel zur Überprüfung. Er wird jetzt gelöscht.</span>
|
|
<span class="s3">// WICHTIG: Damit verhindern wir Memory Leaks [cite: 12]</span>
|
|
<span class="s1">clearTree</span><span class="s5">(</span><span class="s1">root</span><span class="s5">);</span>
|
|
|
|
<span class="s4">return </span><span class="s1">numbers</span><span class="s5">;</span>
|
|
<span class="s5">}</span>
|
|
|
|
<span class="s3">// ... Hierunter bleibt die getDuplicate Funktion deines Kollegen unverändert ...</span>
|
|
<span class="s3">// Sie ist korrekt implementiert laut Aufgabenstellung (mit qsort)[cite: 11, 43].</span>
|
|
<span class="s4">unsigned int </span><span class="s1">getDuplicate</span><span class="s5">(</span><span class="s4">const unsigned int </span><span class="s1">numbers</span><span class="s5">[], </span><span class="s4">unsigned int </span><span class="s1">len</span><span class="s5">)</span>
|
|
<span class="s5">{</span>
|
|
<span class="s4">if </span><span class="s5">(</span><span class="s1">numbers </span><span class="s5">== </span><span class="s1">NULL </span><span class="s5">|| </span><span class="s1">len </span><span class="s5">< </span><span class="s6">2</span><span class="s5">) {</span>
|
|
<span class="s4">return </span><span class="s6">0</span><span class="s5">;</span>
|
|
<span class="s5">}</span>
|
|
|
|
<span class="s4">unsigned int </span><span class="s5">*</span><span class="s1">copy </span><span class="s5">= </span><span class="s1">malloc</span><span class="s5">(</span><span class="s1">len </span><span class="s5">* </span><span class="s4">sizeof</span><span class="s5">(</span><span class="s4">unsigned int</span><span class="s5">));</span>
|
|
<span class="s4">if </span><span class="s5">(</span><span class="s1">copy </span><span class="s5">== </span><span class="s1">NULL</span><span class="s5">) {</span>
|
|
<span class="s4">return </span><span class="s6">0</span><span class="s5">;</span>
|
|
<span class="s5">}</span>
|
|
|
|
<span class="s1">memcpy</span><span class="s5">(</span><span class="s1">copy</span><span class="s5">, </span><span class="s1">numbers</span><span class="s5">, </span><span class="s1">len </span><span class="s5">* </span><span class="s4">sizeof</span><span class="s5">(</span><span class="s4">unsigned int</span><span class="s5">));</span>
|
|
|
|
<span class="s1">qsort</span><span class="s5">(</span><span class="s1">copy</span><span class="s5">, </span><span class="s1">len</span><span class="s5">, </span><span class="s4">sizeof</span><span class="s5">(</span><span class="s4">unsigned int</span><span class="s5">), </span><span class="s1">compareUnsignedInt</span><span class="s5">);</span>
|
|
|
|
<span class="s4">unsigned int </span><span class="s1">duplicate </span><span class="s5">= </span><span class="s6">0</span><span class="s5">;</span>
|
|
|
|
<span class="s4">for </span><span class="s5">(</span><span class="s4">unsigned int </span><span class="s1">i </span><span class="s5">= </span><span class="s6">0</span><span class="s5">; </span><span class="s1">i </span><span class="s5">+ </span><span class="s6">1 </span><span class="s5">< </span><span class="s1">len</span><span class="s5">; ++</span><span class="s1">i</span><span class="s5">) {</span>
|
|
<span class="s4">if </span><span class="s5">(</span><span class="s1">copy</span><span class="s5">[</span><span class="s1">i</span><span class="s5">] == </span><span class="s1">copy</span><span class="s5">[</span><span class="s1">i </span><span class="s5">+ </span><span class="s6">1</span><span class="s5">]) {</span>
|
|
<span class="s1">duplicate </span><span class="s5">= </span><span class="s1">copy</span><span class="s5">[</span><span class="s1">i</span><span class="s5">];</span>
|
|
<span class="s4">break</span><span class="s5">;</span>
|
|
<span class="s5">}</span>
|
|
<span class="s5">}</span>
|
|
|
|
<span class="s1">free</span><span class="s5">(</span><span class="s1">copy</span><span class="s5">);</span>
|
|
<span class="s4">return </span><span class="s1">duplicate</span><span class="s5">;</span>
|
|
<span class="s5">}</span></pre>
|
|
</body>
|
|
</html> |