0. 주저리

아래 소스코드는 대학생 시절때 자료구조 과제로 진행하였던 소스코드이구요.
그 당시의 코드를 그대로 올려서 공유드립니다.
Heap Sort가 궁금하시다면 Wikipedia 페이지를 공유드리니 참고해주세요.

1. Heap Sort

#include <stdio.h>
#include <iostream>
using namespace std;

void out(int *a)
{
    printf("%d\n", a[0]);
    for(int i = 0; i < 10;i++){
        for(int j = 0; j < 10; j++){
            if((2*j+1) == i){
                printf("%d, %d\n", a[i], i); /*왼쪽 출력*/
            }
            else if((2*j+2) == i){
                printf("%d, %d\n\n", a[i], i); /*오른쪽 출력*/
            } 
        }
    }
}

void insert(int *a, int data)

{
    /*
    1. 마지막(현재) 인덱스에 data를 넣는다.
    2. 부모와 비교하면서 자식이 크면 자리를 바꾼다.
    */

    int current =10;
    int parent = 0;
    int tmp = 0;

    a[current] = data;

    parent = (current -1)/2;



    while( (current != 0) && (a[current] > a[parent]) ){
        tmp = a[parent];
        a[parent] = a[current];
        a[current] = tmp;
        current = parent; /*부모인덱스 변경*/
        parent = (current -1) / 2; /*자식으로 설정*/
    }
}

void downheap(int *a, int current)

{

    int child = 0;
    int tmp = 0;

    if(current == 10) return;
    else{
        child = 2 * current + 1;
        if(child+1 != 0){
            if(a[child+1] > a[child]) child = child +1;
        }   

        if(a[current] < a[child]){

            tmp = a[current];
            a[current] = a[child];
            a[child] = a[current];

            downheap(a, child);
        }
    }
}

void remove(int *a)

{

    int cnt = 10;
    int data = a[0]; /*root값 return*/

    a[0] = a[cnt - 1]; /*마지막값 root로 이동*/
    cnt --;

    downheap(a, 0);
}

int main(void)
{
    int a[10] = {24, 19, 12, 17, 10, 5, 4, 9, 7};

    insert(a, 26);
    out(a);

    remove(a);
    out(a);

    return 0;
}

setjmp()와 longjmp()는 C언어의 goto문과 유사하지만 다소 차이가 있습니다.

goto문 같은 경우는 실행중의 EIP(또는 Program Count)만 변경되지만, setjmp()/longjmp()의 특징은 아래와 같습니다.

int setjmp( jmp_buf env )

• 함수가 호출되는 순간 스택값들은 env에 저장됩니다.

• setjmp()호출, longjmp할 곳을 지정합니다.

void longjmp( jmp_buf env, int val )

• longjmp를 호출하면 setjmp()를 한 곳으로 돌아갑니다.

#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
#include <signal.h>
void p1();
void intHandler();
jmp_buf env;

int main()
{
    signal( SIGINT, intHandler );
    if( setjmp( env ) != 0 ){
        printf( "오류로 인해 복귀\n" );
        exit( 0 );
    }
    else
        printf( "처음 통과\n" );

    p1();
}

void p1()
{
    while( 1 ){
        printf( "루프\n" );
        sleep( 1 );
    }
}

void intHandler()
{
    printf( "인터럽트\n" );
    longjmp( env, 1 );
}

출처 : http://growingdever.tistory.com/164

초보자를 위한 A* 알고리즘 (기초개념 설명 및 소스)

참고 - http://egloos.zum.com/cozycoz/v/9748811

8-puzzle에서의 F, G, H값과 열린노드, 닫힌노드 간략한 설명

1) F = G + H, 열린 노드중에서 F값이 최소인 경우를 선택하여 이동한다.
2) G = 현재까지 이동한 횟수

- H = 목표 노드와 현재노드를 비교하여 맞지 않는 노드의 개수
- 열린 노드 : 현재 빈 공간에서 상, 하, 좌, 우 중 갈 수있는 방향을 설정(이때 부모 노드의 위치도 함께저장한다.)
- 닫힌 노드 : 이동하기 전의 현재 위치를 저장( 이동한 이후에 월래자리로 돌아가지 않게하기 위함이다.)

8 puzzle 결과

8 puzzle 소스코드

/****************************************/
/*  name : jihwan-yoon(blackcon)         */
/*  email  : 131ackcon@gmail.com       */
/*  date   : 2015. 04. 04                       */
/****************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define swap( a, b ) temp = a; a = b; b = temp;
#define TILE_NUM    9

typedef struct node{
    int parent;
    int child;
    struct node *next;
}NODE;
typedef struct list{
    int cnt;
    NODE* head;
}LIST;

char start[ TILE_NUM ] = { 2, 8, 3, 1, 6, 4, 7, -1, 5 }; 
char goal[ TILE_NUM ]  = { 1, 2, 3, 8, -1, 4, 7, 6, 5};  
char close = 0;     // 왔던 길은 close노드에 추가한다.
int  dist = 0;

void o_c_node_init( LIST *list );
void add_o_node( LIST *list, int parent, int child );
void del_node( LIST *list );
void func();
int  find_empty();
int  heruistic( LIST *list );
void draw( char *node );

void o_c_node_init( LIST *list )
{
    list->cnt = 0;
    list->head = NULL;
}

void add_o_node( LIST *list, int parent, int child )
{
    int i = 0;
    NODE *p = (NODE *)malloc( sizeof( NODE ) );
    p->parent = parent;
    p->child = child;
    NODE *tmp = list->head;
    // 다음 이동할 경로가 직전에 있었던 위치라면 return
    if( close == child )
        return;
    if( list->cnt == 0 ){
        list->head = p;
        p->next = list->head;
        list->cnt = 1;
    }
    else{
        tmp = list->head;
        for( i = 0; i < list->cnt; i++)
            tmp = tmp->next;
        p->next = tmp->next;
        tmp->next = p;
        list->cnt++;
    }
}

void del_node( LIST *list )
{
    NODE *tmp = list->head;
    while( list->cnt != 0 ){
        free( list->head );
        list->head = tmp->next;
        tmp->next = (tmp->next)->next;
        list->cnt--;
    }
}
int find_empty()
{
    int i = 0;
    int j = 0;
    int cnt = 0;
    /* 비어있는 타일을 찾는다.  */
    for( i = 0; i < TILE_NUM ; i++){
        if( start[i] == -1 ){
            return i;
        }
    }
    return -1;  // 비어있는 타일을 못찾았을 경우 -1반환.
}
void func()
{
    int i = 0;
    int cnt = 0;
    int empty = 0;
    int select[2] = {0x0, };    // [0] = parent, [1] = child

    LIST list;
    NODE *tmp;
    o_c_node_init( &list );   // 오픈 노드, 클로즈 노드  초기화
    empty = find_empty();   // 빈 타일 찾기

    /* 인접한 타일을 open노드에 추가한다. */
    if( empty != -1 ){
        if( empty > 2 ){                // UP
            add_o_node( &list, empty, empty-3 );
        }
        if( empty < 6 ){           // DOWN
            add_o_node( &list, empty, empty+3 );
        }
        if( (empty % 3) != 2 ){    // RIGHT
            add_o_node( &list, empty, empty +1 );
        }
        if( (empty % 3) != 0){     // LEFT
            add_o_node( &list, empty, empty -1);
        }

        /* 이동비용이 최소인 값을 찾는다. */
        dist++;
        close = empty;
        select[1] = heruistic( &list );
        tmp = list.head;
        while( 1 ){
            if( select[1] == tmp->child ){
                select[0] = tmp->parent;
                break;
            }
            tmp = tmp->next;
        }
        /* 공백(-1)과 이동할 위치에 있는 타일을 바꾼다. */
        start[ select[0] ] = start[ select[1] ];
        start[ select[1] ] = -1;
    }
    del_node( &list );
}
int heruistic( LIST *list )
{
    char node[ TILE_NUM ] = {0x0,};
    int misplaced = 0;
    int totalHerst = 0;
    int i = 0;
    int j = 0;
    int _short = -1;
    int select_node = 0;
    NODE *tmp = list->head;

    while( 1 ){
        if( i == list->cnt )
            break;
        else{
            misplaced = 0;
            memcpy( node, start, 9 );
            node[ tmp->child ]  = node[ tmp->parent ];
            node[ tmp->parent ] = -1;

            /* 목표 타일과 이동했을 때의 타일을 비교하여, 맞지 않는 타일의 개수를 확인한다. */
            for( j = 0; j < TILE_NUM ; j++){
                if( node[j] != goal[j] )
                    misplaced += 1;
            }
            totalHerst = dist + misplaced;

            /* 열린 노드중에서 F값이 가장 작은 노드를 찾는다. */
            if( (_short == -1) || (_short > totalHerst ) ){
                _short = totalHerst;
                select_node = tmp->child;
            }
            tmp = tmp->next;
            i++;
        }
    }
    printf( "close : %d, dist : %d, short path : %d, select tile: %d\n", close, dist, _short, select_node );
    return select_node;
}

void draw( char *node )
{
    int i = 0;
    for( i = 0; i < TILE_NUM; i++ ){
        if( i % 3 == 0 )    printf("\n" );
        if( node[i] == -1 )
            printf("  ");
        else
            printf("%d ", node[i] );
    }
    printf("\n");
}
int main( void )
{
    draw( start );
    while( 1 ){
        printf("=================\n");
        if( memcmp( start, goal, 9 ) == 0)  break;
        func();
        draw( start );
    }
    return 0;
}