[데이터 구조] C 언어 실현: 단일 체인 테이블

#ifndef SLIST_H
#define SLIST_H

#include 
#include 

typedef struct SListNode_struct
{
	int m_Data;
	struct SListNode_struct * m_Next;
} SListNode_t;

typedef struct
{
	SListNode_t * m_Head;
	size_t m_Count;
} SList_t;

bool SList_Init(SList_t * list);
bool SList_Insert(SList_t * list, int index, int data);
bool SList_Delete(SList_t * list, int index);
bool SList_Update(SList_t * list, int index, int newData);
void SList_Reverse(SList_t * list);
void SList_Empty(SList_t * list);
bool SList_Sort(SList_t * list);

void SList_Print(const SList_t * list);

static inline size_t SList_Count(const SList_t * list)
{
    return list->m_Count;
}

static inline bool SList_IsEmpty(const SList_t * list)
{
	return list->m_Count == 0;
}

#endif

#include 
#include 
#include 
#include 
#include "SList.h"

void QuickSort(int array[], int firstIndex, int lastIndex)
{
	int i = 0;
	int j = 0;
	int key = 0;

	if(firstIndex >= lastIndex)
		return;
	
	i = firstIndex;
	j = lastIndex;
	key = array[firstIndex];

	while(i < j)
	{
		while(i < j && key <= array[j])
			j--;
		array[i] = array[j];

		while(i < j && array[i] <= key)
			i++;
		array[j] = array[i];
	}

	array[i] = key;
	QuickSort(array, firstIndex, i - 1);
	QuickSort(array, i + 1, lastIndex);
}

bool SList_Init(SList_t * list)
{
	if(!list)
		return false;
	
	SListNode_t * node = malloc(sizeof(SListNode_t));
	if(!node)
		return false;
	
	node->m_Data = 0;
	node->m_Next = NULL;
	
	list->m_Head = node;
	list->m_Count = 0;

	return true;
}

bool SList_Insert(SList_t * list, int index, int data)
{
	SListNode_t * p = NULL;

	if(!list)
		return false;
	if(index < 0)
		index = 0;
	if(index > list->m_Count)
		index = list->m_Count;
	
	SListNode_t * node = malloc(sizeof(SListNode_t));
	if(!node)
		return false;

	node->m_Data = data;

	p = list->m_Head;
	for(int i = 0; i < index; i++)
		p = p->m_Next;
	
	node->m_Next = p->m_Next;
	p->m_Next = node;

	list->m_Count++;

	return true;
}

bool SList_Delete(SList_t * list, int index)
{
	SListNode_t * p = NULL;
	SListNode_t * q = NULL;

	if(!list)
		return false;
	if(index < 0 || index >= list->m_Count)
		return false;

	p = list->m_Head;
	for(int i = 0; i < index; i++)
		p = p->m_Next;
	
	q = p->m_Next;
	p->m_Next = q->m_Next;
	free(q);

	list->m_Count--;

	return true;
}

bool SList_Update(SList_t * list, int index, int newData)
{
	SListNode_t * p = NULL;

	if(!list)
		return false;
	
	if(index < 0 || index >= list->m_Count)
		return false;
	
	p = list->m_Head->m_Next;
	for(int i = 0; i < index; i++)
		p = p->m_Next;
	
	p->m_Data = newData;

	return true;
}

void SList_Reverse(SList_t * list)
{
	SListNode_t * p = NULL;
	SListNode_t * q = NULL;
	SListNode_t * r = NULL;

	if(!list)
		return;
	
	if(list->m_Count < 2)
		return;
	
	p = list->m_Head->m_Next;
	q = p->m_Next;
	p->m_Next = NULL;
	while(q)
	{
		r = q->m_Next;

		q->m_Next = p;

		p = q;
		q = r;
	}
	list->m_Head->m_Next = p;
}

void SList_Empty(SList_t * list)
{
	SListNode_t * p = NULL;
	SListNode_t * q = NULL;

	p = list->m_Head->m_Next;
	while(p)
	{
		q = p->m_Next;
		free(p);
		p = q;
	}

	list->m_Head->m_Next = NULL;
	list->m_Count = 0;
}

bool SList_Sort(SList_t * list)
{
	int * array = NULL;
	SListNode_t * p = NULL;
	size_t count = 0;

	count = list->m_Count;
	array = malloc(sizeof(int) * count);
	if(!array)
		return false;
	
	p = list->m_Head->m_Next;
	for(int i = 0; i < count; i++, p = p->m_Next)
	{
		array[i] = p->m_Data;
	}

	//          array[]    
	QuickSort(array, 0, count - 1);

	SList_Empty(list);
	for(int i = 0; i < count; i++)
	{
		SList_Insert(list, list->m_Count, array[i]);
	}

	return true;
}

void SList_Print(const SList_t * list)
{
	SListNode_t * p = NULL;

	if(!list)
		return;

	printf("[ ");
	p = list->m_Head->m_Next;
	while(p)
	{
		printf("%d ", p->m_Data);
		p = p->m_Next;
	}
	printf("]
");
}