[C언어 알고리즘] 6.1.4 순열 알고리즘 소스 코드

[C언어 알고리즘] 6.1.4 순열 알고리즘 소스 코드

---

//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;

}