[C] 연결리스트 큐 이용한 기수정렬

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define TRUE 1
#define FALSE 0

typedef struct _QUEUE_NODE_ {
	int data;
	struct _QUEUE_NODE_* link;
}QUEUE_NODE;

typedef struct _Q_TYPE_ {
	QUEUE_NODE* front;
	QUEUE_NODE* rear;
}Q_TYPE;

int MaxDigit(int* arr, int size) {
	int i;
	int max = arr[0];
	for (i = 0; i < size; i++) {
		if (max < arr[i]) {
			max = arr[i];
		}
	}
	int cnt = 0;
	while (max != 0) {
		cnt++;
		max /= 10;
	}
	return cnt;
}

int isEmpty(Q_TYPE* queue, int idx) {
	if (queue[idx].front == NULL) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

int radix(int item, int div) {
	//1이면 item%10
	//2이면 (item/10)%10;
	//3이면 (item/100)%10;

	int i;
	for (i = 1; i <= div - 1; i++) {
		item /= 10;
	}

	return item % 10;
}

//radix : 특정번째의 숫자
void Enqueue(Q_TYPE* queue, int item, int radix) {
	QUEUE_NODE* newNode = NULL;
	newNode = (QUEUE_NODE*)calloc(1, sizeof(QUEUE_NODE));
	assert(newNode != NULL);
	newNode->data = item;
	newNode->link = NULL;

	if (isEmpty(queue, radix)) {
		queue[radix].front = newNode;
		queue[radix].rear = newNode;
	}
	else {
		queue[radix].rear->link = newNode;
		queue[radix].rear = newNode;
	}
}


int Dequeue(Q_TYPE* queue, int radix) {
	if (isEmpty(queue, radix)) {
		return;
	}
	int dequeuedata = queue[radix].front->data;
	QUEUE_NODE* delNode = NULL;
	delNode = queue[radix].front;
	queue[radix].front = queue[radix].front->link;
	free(delNode);
	delNode = NULL;
	return dequeuedata;
}

void init(Q_TYPE* QUEUE) {
	int i;
	for (i = 0; i < 10; i++) {
		QUEUE[i].front = NULL;
		QUEUE[i].rear = NULL;
	}
}

int main() {
	int arr[] = { 13,212,14,7141,10987,6,15 };
	int size = sizeof(arr) / sizeof(int);
	int maxdigit = MaxDigit(arr, size);
	int radixnum; //n번째 자리의 숫자 
	int k = 0;
	Q_TYPE* QUEUE = (Q_TYPE*)calloc(10, sizeof(Q_TYPE));
	assert(QUEUE != NULL);

	int i,j;

	for (i = 1; i <= maxdigit; i++) {
		for (j = 0; j < size; j++) {
			radixnum = radix(arr[j], i);
			Enqueue(QUEUE, arr[j], radixnum);
		}
		for (j = 0; j < 10; j++) {
			while (!isEmpty(QUEUE, j)) {
				arr[k++] = Dequeue(QUEUE, j);
			}
		}
		init(QUEUE);
		k = 0;
	}
	for (i = 0; i < size; i++) {
		printf("%d ", arr[i]);
	}
	getchar();
	return 0;
}