111 lines
3.1 KiB
C
111 lines
3.1 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <time.h>
|
|
#include <string.h>
|
|
#include "numbers.h"
|
|
#include "bintree.h"
|
|
|
|
// helper comparator for unsigned int for bintree
|
|
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;
|
|
}
|
|
|
|
// comparator for qsort (unsigned int)
|
|
static int qsort_uint_cmp(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;
|
|
}
|
|
|
|
// 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)
|
|
return NULL;
|
|
|
|
unsigned int *numbers = (unsigned int *)malloc(sizeof(unsigned int) * len);
|
|
if(numbers == NULL)
|
|
return NULL;
|
|
|
|
// seed once
|
|
srand((unsigned int)time(NULL));
|
|
|
|
TreeNode *root = NULL;
|
|
unsigned int range = 2 * len;
|
|
// create len-1 unique numbers
|
|
for(unsigned int i = 0; i < len - 1; i++)
|
|
{
|
|
unsigned int val;
|
|
int isDup = 0;
|
|
// try until a unique number is inserted
|
|
do
|
|
{
|
|
val = (unsigned int)(rand() % range) + 1; // [1..2*len]
|
|
root = addToTree(root, &val, sizeof(val), compareUInt, &isDup);
|
|
// if addToTree returned NULL due to allocation failure, cleanup and return NULL
|
|
if(root == NULL && isDup == 0)
|
|
{
|
|
free(numbers);
|
|
clearTree(root);
|
|
return NULL;
|
|
}
|
|
} while(isDup);
|
|
numbers[i] = val;
|
|
}
|
|
|
|
// duplicate one existing random entry
|
|
unsigned int idx = (unsigned int)(rand() % (len - 1));
|
|
numbers[len - 1] = numbers[idx];
|
|
|
|
// shuffle array (Fisher-Yates)
|
|
for(unsigned int i = len - 1; i > 0; i--)
|
|
{
|
|
unsigned int j = (unsigned int)(rand() % (i + 1));
|
|
unsigned int tmp = numbers[i];
|
|
numbers[i] = numbers[j];
|
|
numbers[j] = tmp;
|
|
}
|
|
|
|
// free tree resources
|
|
clearTree(root);
|
|
return numbers;
|
|
}
|
|
|
|
// 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 == NULL || len < 2)
|
|
return 0;
|
|
|
|
// make a copy so original array order is not modified by caller expectation
|
|
unsigned int *copy = (unsigned int *)malloc(sizeof(unsigned int) * len);
|
|
if(copy == NULL)
|
|
return 0;
|
|
|
|
memcpy(copy, numbers, sizeof(unsigned int) * len);
|
|
|
|
qsort(copy, len, sizeof(unsigned int), qsort_uint_cmp);
|
|
|
|
unsigned int result = 0;
|
|
for(unsigned int i = 0; i + 1 < len; i++)
|
|
{
|
|
if(copy[i] == copy[i+1])
|
|
{
|
|
result = copy[i];
|
|
break;
|
|
}
|
|
}
|
|
|
|
free(copy);
|
|
return result;
|
|
} |