7.1.4 순열 알고리즘 소스 코드

다음은 C언어로 바구니에서 공을 꺼내는 순열 문제를 작성한 소스 코드입니다.

//common.h
#pragma once //헤더 파일을 한 번만 포함해서 컴파일
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <memory.h>
#include <time.h>
#pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제

//Array.h
#pragma once
typedef void * Element;
typedef struct _Array Array;
struct _Array
{
	Element *base;
	int capacity;
	int usage;
};
typedef Element *Iterator;

Array *New_Array();
void Delete_Array(Array *arr);
void Array_SetSize(Array *arr,int capacity,Element data);
void Array_PushBack(Array *arr,Element data);
void Array_Insert(Array *arr,Iterator pos,Element data);
void Array_SetAt(Array *arr,int index,Element data);
Element Array_GetAt(Array *arr,int index);
Iterator Array_Begin(Array *arr);
Iterator Array_End(Array *arr);
void Array_Erase(Array *arr,Iterator pos);

//Array.c
#include "Array.h"
#include <malloc.h>
#include <memory.h>
Array *New_Array()
{
	Array *arr = 0;
	arr = (Array *)malloc(sizeof(Array));
	arr->base = 0;
	arr->capacity = arr->usage = 0;
	return arr;
}
void Delete_Array(Array *arr)
{
	if(arr->base)
	{
		free(arr->base);
	}
	free(arr);
}
void Array_SetSize(Array *arr,int capacity,Element data)
{		
	arr->capacity = capacity;
	arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
	for(    ;arr->usage<arr->capacity; arr->usage++)
	{
		arr->base[arr->usage] = data;
	}
}
void Array_PushBack(Array *arr,Element data)
{
	Iterator at = Array_End(arr);
	Array_Insert(arr,at,data);
}
void Array_Insert(Array *arr,Iterator pos,Element data)
{
	int index = pos - arr->base;
	int mcount = arr->usage - index;
	if(arr->capacity == arr->usage)
	{
		if(arr->capacity)
		{
			arr->capacity*=2;
		}
		else
		{
			arr->capacity = 1;
		}
		arr->base = (Element *)realloc(arr->base,sizeof(Element)*arr->capacity);
	}
	memcpy(arr->base+index+1,arr->base+index,sizeof(Element)*mcount);
	arr->base[index] = data;
	arr->usage++;
}
void Array_SetAt(Array *arr,int index,Element data)
{
	if((index>=0)&&(index<arr->usage))
	{
		arr->base[index] = data;
	}
}
Element Array_GetAt(Array *arr,int index)
{
	if((index>=0)&&(index<arr->usage))
	{
		return arr->base[index];
	}
	return 0;
}
Iterator Array_Begin(Array *arr)
{
	return arr->base;
}
Iterator Array_End(Array *arr)
{
	return arr->base+arr->usage;
}
void Array_Erase(Array *arr,Iterator pos)
{
	int index = pos - arr->base;
	int mcount = arr->usage - index -1;
	memcpy(pos,pos+1,sizeof(Element)*mcount);
	arr->usage--;
}

//LinkedList.h
#pragma once
typedef void * Element;
typedef struct _Node Node;
typedef Node *Link;
struct _Node
{
	Link next;
	Link prev;
	Element data;
};

typedef struct _LinkedList LinkedList;
struct _LinkedList
{
	Link head;
	Link tail;
	int usage;
};


LinkedList *New_LinkedList();
void Delete_LinkedList(LinkedList *linkedlist);
void LinkedList_PushBack(LinkedList *linkedlist,Element data);
void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data);
Link LinkedList_Begin(LinkedList *linkedlist);
Link LinkedList_End(LinkedList *linkedlist);
void LinkedList_Erase(LinkedList *linkedlist,Link pos);

//LinkedList.c
#include "LinkedList.h"
#include <malloc.h>
#include <memory.h>
Link New_Node(Element data)
{
	Link link = (Link)malloc(sizeof(Node));
	link->data = data;
	link->next = link->prev = 0;
	return link;
}
void HangNode(Link link,Link pos)
{
	link->prev = pos->prev;
	link->next = pos;
	pos->prev->next = link;
	pos->prev = link;
}
void DisconnectNode(Link pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
}
LinkedList *New_LinkedList()
{
	LinkedList *linkedlist = 0;
	linkedlist = (LinkedList *)malloc(sizeof(LinkedList));
	linkedlist->head = New_Node(0);
	linkedlist->tail = New_Node(0);
	linkedlist->head->next = linkedlist->tail;
	linkedlist->tail->prev = linkedlist->head;
	linkedlist->usage = 0;
	return linkedlist;
}
void Delete_LinkedList(LinkedList *linkedlist)
{
	Link seek = linkedlist->head;
	
	while( seek != linkedlist->tail)
	{
		seek = seek->next;
		free(seek->prev);
	}
	free(linkedlist->tail);
	free(linkedlist);
}
void LinkedList_PushBack(LinkedList *linkedlist,Element data)
{
	LinkedList_Insert(linkedlist,linkedlist->tail,data);
}
void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data)
{
	Link link = New_Node(data);
	HangNode(link,pos);
	linkedlist->usage++;
}
Link LinkedList_Begin(LinkedList *linkedlist)
{
	return linkedlist->head->next;
}
Link LinkedList_End(LinkedList *linkedlist)
{
	return linkedlist->tail;
}
void LinkedList_Erase(LinkedList *linkedlist,Link pos)
{
	DisconnectNode(pos);
	linkedlist->usage--;
}

//EHStack.h
#pragma once
#include "LinkedList.h"

typedef LinkedList EHStack;

EHStack *New_EHStack();
void Delete_EHStack(EHStack *ehs);
void EHStack_Push(EHStack *ehs, Element data);
Element EHStack_Pop(EHStack *ehs);
int EHStack_IsEmpty(EHStack *ehs);

//EHStack.c
#include "EHStack.h"
#include <malloc.h>
#include <memory.h>
EHStack *New_EHStack()
{
	return New_LinkedList();	
}
void Delete_EHStack(EHStack *ehs)
{
	Delete_LinkedList(ehs);	
}
void EHStack_Push(EHStack *ehs, Element data)
{
	LinkedList_PushBack(ehs,data);
}
Element EHStack_Pop(EHStack *ehs)
{
	Element element = 0;
	if( ! EHStack_IsEmpty(ehs))
	{
		Link last = LinkedList_End(ehs);
		last = last->prev;
		element = last->data;
		LinkedList_Erase(ehs,last);
	}
	return element;
}
int EHStack_IsEmpty(EHStack *ehs)
{
	return ehs->usage == 0;
}

// Heuristic.h
#pragma once
#include "Array.h"

typedef struct _Heuristic Heuristic;
struct _Heuristic
{
    Array *ori_bucket;
    Array *out_bucket;
};

Heuristic *MakeInitHeuristic(Array *bucket);
void DeleteHeuristic(Heuristic *now);
void FindNextHeuristics(Heuristic *now, Array *next_heus);
int GetOutCount(Heuristic *now);
void ViewHeuristic(Heuristic *now);

//Heuristic.c
#include "Heuristic.h"
#include <malloc.h>
#include <stdio.h>

Heuristic *MakeNextHeu(Heuristic *now,int ball)
{
    Heuristic *heu = 0;
    Iterator seek=0, end=0;
    
    heu = (Heuristic *)malloc(sizeof(Heuristic));
    heu->ori_bucket = New_Array();
    heu->out_bucket = New_Array();
    
    seek = Array_Begin(now->out_bucket);
    end = Array_End(now->out_bucket);
    for(seek = seek; seek != end; ++seek)
    {
        Array_PushBack(heu->out_bucket, *seek);
    }
    
    seek = Array_Begin(now->ori_bucket);
    end = Array_End(now->ori_bucket);
    for(seek = seek; seek != end; ++seek)
    {
        if((int)(*seek) == ball)
        {
            Array_PushBack(heu->out_bucket,*seek);
        }
        else
        {
            Array_PushBack(heu->ori_bucket,*seek);
        }
    }
    return heu;
}
Heuristic *MakeInitHeuristic(Array *bucket)
{
    Heuristic *heu = 0;
    Iterator seek=0, end=0;
    heu = (Heuristic *)malloc(sizeof(Heuristic));
    heu->ori_bucket = New_Array();
    heu->out_bucket = New_Array();
    
    seek = Array_Begin(bucket);
    end = Array_End(bucket);
    for(seek = seek; seek != end; ++seek)
    {
        Array_PushBack(heu->ori_bucket, *seek);
    }
    return heu;
}

void DeleteHeuristic(Heuristic *now)
{
    Delete_Array(now->ori_bucket);
    Delete_Array(now->out_bucket);
    free(now);
}
void FindNextHeuristics(Heuristic *now, Array *next_heus)
{
    Iterator seek=0, end=0;
    Heuristic *next = 0;
    
    seek = Array_Begin(now->ori_bucket);
    end = Array_End(now->ori_bucket);
    for(seek = seek; seek != end; ++seek)
    {
        next = MakeNextHeu(now,(int)*seek);
        Array_PushBack(next_heus,next);
    }
}
int GetOutCount(Heuristic *now)
{
    return now->out_bucket->usage;
}
void ViewHeuristic(Heuristic *now)
{
    Iterator seek=0, end=0;
    seek = Array_Begin(now->out_bucket);
    end = Array_End(now->out_bucket);
    for(seek = seek; seek != end; ++seek)
    {
        printf("%d ",(int)*seek);
    }	
    printf("\n");
}

//Program.c
#include "EHStack.h"
#include "Heuristic.h"
Array * InitSimulation()
{
    int ball = 0;
    Array *bucket = 0;
    
    bucket = New_Array();
    for(ball = 0; ball<=9; ++ball)
    {
        Array_PushBack(bucket,(Element)ball);
    }
    return bucket;
}
int main()
{
    EHStack *ehs = 0;
    Heuristic *heu = 0;
    Array *bucket = 0;
    Array *next_heus = 0;
    Iterator seek=0, end=0;
    
    bucket = InitSimulation();
    ehs = New_EHStack();
    heu = MakeInitHeuristic(bucket);
    EHStack_Push(ehs,heu);
    while( ! EHStack_IsEmpty(ehs) )
    {
        heu = (Heuristic *)EHStack_Pop(ehs);
        next_heus = New_Array();
        FindNextHeuristics(heu,next_heus);
        seek = Array_Begin(next_heus);
        end = Array_End(next_heus);
        for(seek=seek; seek != end; ++seek)
        {
            heu = (Heuristic *)(*seek);
            if(GetOutCount(heu) == 3)
            {
                ViewHeuristic(heu);
                DeleteHeuristic(heu);
            }
            else
            {
                EHStack_Push(ehs,heu);
            }
        }
        Delete_Array(next_heus);
    }
    Delete_Array(bucket);	
    Delete_EHStack(ehs);
    return 0;
}