100 lines
3.3 KiB
C
100 lines
3.3 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <time.h> // für Zufallszahlen
|
|
#include <string.h>
|
|
#include "numbers.h"
|
|
#include "bintree.h"
|
|
|
|
//TODO: getDuplicate und createNumbers implementieren
|
|
/* * * 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. */
|
|
// Vergleichsfunktion für unsigned int
|
|
|
|
static int compareUInt(const void *a, const void *b)
|
|
{
|
|
unsigned int x = *(unsigned int *)a; // beide void Zeiger in unsigned int
|
|
unsigned int y = *(unsigned int *)b;
|
|
|
|
// Vergleich wie beim Binärbaum
|
|
if (x < y) return -1; // links
|
|
if (x > y) return 1; // rechts
|
|
return 0; // gleich
|
|
}
|
|
|
|
// Returns len random numbers between 1 and 2x len in random order which are all different, except for two entries.
|
|
// Returns NULL on errors. Use your implementation of the binary search tree to check for possible duplicates while
|
|
// creating random numbers.
|
|
unsigned int *createNumbers(unsigned int len)
|
|
{
|
|
if (len < 2) // min 2 Zahlen sind notwendig
|
|
return NULL;
|
|
|
|
// Erzeugen eines Arrays (unsigned int)
|
|
unsigned int *arr = malloc(sizeof(unsigned int) * len);
|
|
if (!arr)
|
|
return NULL; // kein Speicher -> Fehler
|
|
|
|
srand((unsigned int)time(NULL)); // Initialisieren Zufallszahl
|
|
|
|
TreeNode *root = NULL;
|
|
int isDup; // zeigt ob Duplikat
|
|
|
|
unsigned int count = 0;
|
|
|
|
// Erzeugen der Zufallszahlen
|
|
while (count < len - 1) // ERST len-1 verschiedene Zahlen (ein Platz übrig für Duplikat)
|
|
{
|
|
unsigned int value = (rand() % (2 * len)) + 1; // Bereich 1 bis 2len (wahrscheinlich wenig Duplikate)
|
|
|
|
root = addToTree(root, &value, sizeof(unsigned int), compareUInt, &isDup);
|
|
// Einfügen der Zahl in Binärbaum (isDup==0 neue Zahl ) (isDup==1 Zahl war schon)
|
|
|
|
if (!isDup) // nur hinzufügen, wenn kein Duplikat
|
|
{
|
|
arr[count] = value; //Neuer Wert gespeichert (Duplikate ignoriert)
|
|
count++;
|
|
}
|
|
}
|
|
|
|
// EIN zufälliges Duplikat hinzufügen
|
|
unsigned int idx = rand() % (len - 1);
|
|
arr[len - 1] = arr[idx];
|
|
|
|
clearTree(root); // Freigeben des Baumes
|
|
return arr; // Zurückgeben des Array
|
|
}
|
|
|
|
// Returns only the only number in numbers which is present twice. Returns zero on errors.
|
|
unsigned int getDuplicate(const unsigned int numbers[], unsigned int len)
|
|
{
|
|
if (!numbers || len < 2) // Prüfen ob Array leer oder zu kurz
|
|
return 0;
|
|
|
|
// Kopie erstellen zum Sortieren
|
|
unsigned int *tmp = malloc(sizeof(unsigned int) * len);
|
|
if (!tmp)
|
|
return 0;
|
|
|
|
for (unsigned int i = 0; i < len; i++) // Werte kopieren
|
|
tmp[i] = numbers[i];
|
|
|
|
// Sortieren (qsort - Vergleichsfunktion)
|
|
qsort(tmp, len, sizeof(unsigned int), compareUInt);
|
|
|
|
// benachbarte Duplikate finden
|
|
unsigned int duplicate = 0;
|
|
|
|
for (unsigned int i = 0; i < len - 1; i++) // Durchlaufen des Arrays
|
|
{
|
|
if (tmp[i] == tmp[i + 1]) // wenn 2 aufeinanderfolgende Werte gleich -> Duplikat
|
|
{
|
|
duplicate = tmp[i];
|
|
break;
|
|
}
|
|
}
|
|
|
|
free(tmp); // Kopie freigeben
|
|
return duplicate; //gefundene Zahl zurückgeben
|
|
} |