Instructions
Requirements and Specifications
Source Code
#include
#include
#include
#define NUM_BUCKETS 10
#define TRUE 1
#define FALSE 0
/* Used for building linked-list */
typedef struct _ListNode
{
int data;
struct _ListNode *next;
} ListNode;
/* Function prototypes */
ListNode *newList(void);
ListNode *removeNode(ListNode *prev);
ListNode *insertNode(ListNode *prev, int data);
void deleteList(ListNode *current);
int length(ListNode *head);
void printList(ListNode *head);
/* Entry point of the program */
int main(int argc, char *argv[])
{
ListNode *headNodes[NUM_BUCKETS], *tailNodes[NUM_BUCKETS];
ListNode *listHead, *listTail, *current;
int i, flag, divisor, index, iteration;
int seed;
int numValues;
int minValue, maxValue, value;
/* Validate the arguments */
if (argc != 5)
{
printf("Usage: %s \n", argv[0]);
return 0;
}
if (sscanf(argv[1], "%d", &seed) != 1)
{
printf("The seed should be an integer\n");
return 0;
}
if (sscanf(argv[2], "%d", &numValues) != 1 || numValues <= 0)
{
printf("The number of values should be a positive integer\n");
return 0;
}
if (sscanf(argv[3], "%d", &minValue) != 1)
{
printf("The minimum value should be a positive value\n");
return 0;
}
if (sscanf(argv[4], "%d", &maxValue) != 1 || maxValue <= minValue)
{
printf("The maximum value should be a positive value higher than the minimum value\n");
return 0;
}
/* Seed the random number generator */
srand(seed);
/* Reset the buckets with empty list */
listHead = NULL;
listTail = NULL;
for (i = 0; i < NUM_BUCKETS; i++)
{
headNodes[i] = NULL;
tailNodes[i] = NULL;
}
/* Generate random values and put them in an unsorted list */
for (i = 0; i < numValues; i++)
{
value = (rand() % (maxValue - minValue)) + minValue;
if (listHead == NULL)
{
listHead = newList();
listHead->data = value;
listTail = listHead;
}
else
{
listTail = insertNode(listTail, value);
}
}
/* Print out the unsorted list */
iteration = 0;
printf("Iteration %d: ", iteration);
printList(listHead);
/* Now do the radix sort */
flag = TRUE;
divisor = 1;
while (flag)
/* Flag identifies if we're done iterating */
flag = FALSE;
/* Re-distrbute the list values to the buckets */
current = listHead;
while (current != NULL)
{
index = (current->data / divisor) % 10;
if (index > 0)
flag = TRUE;
if (headNodes[index] == NULL)
{
headNodes[index] = newList();
headNodes[index]->data = current->data;
tailNodes[index] = headNodes[index];
}
else
{
tailNodes[index] = insertNode(tailNodes[index], current->data);
}
current = current->next;
}
/* Merge back the elements from buckets to the main list in-order */
deleteList(listHead);
listHead = NULL;
listTail = NULL;
for (i = 0; i < NUM_BUCKETS; i++)
{
current = headNodes[i];
while (current != NULL)
{
if (listHead == NULL)
{
listHead = newList();
listHead->data = current->data;
listTail = listHead;
}
else
{
listTail = insertNode(listTail, current->data);
}
current = current->next;
}
deleteList(headNodes[i]);
headNodes[i] = NULL;
tailNodes[i] = NULL;
}
/* Check out our new list */
iteration++;
printf("Iteration %d: ", iteration);
printList(listHead);
/* Move to the next digit .. (e.g. ones, tens, hundreds... ) */
divisor *= 10;
}
/* Clean up */
deleteList(listHead);
return 0;
}
/* Create a new empty list */
ListNode *newList(void)
{
ListNode *node;
node = malloc(sizeof(ListNode));
node->data = 0;
node->next = NULL;
return node;
}
/* Remove the node after the previous node */
ListNode *removeNode(ListNode *prev)
{
ListNode *removedNode;
if (prev == NULL || prev->next == NULL)
return NULL;
removedNode = prev->next;
prev->next = removedNode->next;
return removedNode;
}
/* Insert a new value after the previous node*/
ListNode *insertNode(ListNode *prev, int data)
{
ListNode *insertedNode;
if (prev == NULL)
return NULL;
insertedNode = newList();
insertedNode->data = data;
insertedNode->next = prev->next;
prev->next = insertedNode;
return insertedNode;
}
/* Deallocate the nodes */
void deleteList(ListNode *current)
{
ListNode *next;
if (current == NULL)
return;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
}
/* Return the number of elements */
int length(ListNode *head)
{
int count;
ListNode *current;
ount = 0;
current = head;
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
/* Print the entire list contents */
void printList(ListNode *head)
{
ListNode *current;
current = head;
while (current != NULL)
{
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}