[알고리즘] 하노이의 탑

//--------

// Stack

//--------

typedef struct {

int top;

int num; // filled number

int size;

int *val;

} int_stack_ctx_t;

void int_stack_push(int_stack_ctx_t *ctx, int val)

{

if (-1 == val)

goto exit;

if (ctx->top >= ctx->size) {

goto exit;

}

ctx->val[++ctx->top] = val;

ctx->num++;

exit:

return;

}

int int_stack_pop(int_stack_ctx_t *ctx)

{

int ret = -1;

if (ctx->top == -1) {

goto exit;

}

ret = ctx->val[ctx->top--];

ctx->num--;

exit:

return ret;

}

int_stack_ctx_t *int_stack_init(int size)

{

int_stack_ctx_t *ctx = (int_stack_ctx_t *)malloc(sizeof(int_stack_ctx_t));

if (!ctx) {

goto exit;

}

ctx->top  = -1;

ctx->size = size - 1; // index starts from 0

ctx->num  = 0;

ctx->val = (int *)malloc(sizeof(int)*size);

if (ctx->val) {

goto exit;

}

free(ctx);

exit:

return ctx;

}

void int_stack_deinit(int_stack_ctx_t *ctx)

{

if (!ctx) {

return;

}

if (ctx->val) {

free(ctx->val);

}

free(ctx);

}

int int_stack_empty(int_stack_ctx_t *ctx)

{

int ret = ctx->num == 0 ? 1 : -1;

return ret;

}

void hannoi_print_all(int_stack_ctx_t *ctx1, int_stack_ctx_t *ctx2, int_stack_ctx_t *ctx3)

{

int l, i;

int_stack_ctx_t *cur_ctx[3];

cur_ctx[0] = ctx1;

cur_ctx[1] = ctx2;

cur_ctx[2] = ctx3;

printf("--------------------------------------\r\n", __FUNCTION__);

for (l = 0; l < 3; l++) {

for (i = 0; i < cur_ctx[l]->num; i++) {

printf("%d ", cur_ctx[l]->val[i]);

}

printf(" : ");

}

printf("\r\n--------------------------------------\r\n", __FUNCTION__);

}

void hanoi_move(int from, int to, int_stack_ctx_t **poles)

{

int val = int_stack_pop(poles[from]);

int_stack_push(poles[to], val);

}

void hanoi(int n, int from, int by, int to, 

int_stack_ctx_t **poles)

{

if (n == 1)

hanoi_move(from, to, poles);

else {

hanoi(n - 1, from, to, by, poles);

hanoi_move(from, to, poles);

hanoi(n - 1, by, from, to, poles);

}

}

int hannoi_int_ver(int size)

{

int i, val;

int_stack_ctx_t *pole1 = int_stack_init(size);

int_stack_ctx_t *pole2 = int_stack_init(size);

int_stack_ctx_t *pole3 = int_stack_init(size);

int_stack_ctx_t *poles[3] = {

pole1, pole2, pole3

};

printf("+%s: size = %d\r\n", __FUNCTION__, size);

for (i = size; i > 0; i--) {

int_stack_push(pole1, i);

}

hanoi(size, 0, 1, 2, poles);

for (i = 0; i < size; i++) {

printf("stack: pop %d\r\n", int_stack_pop(pole3));

}

int_stack_deinit(pole1);

int_stack_deinit(pole2);

int_stack_deinit(pole3);

printf("-%s:\r\n", __FUNCTION__);

}

void test_hannoi(void)

{

// stack test

#if 0

int size = 5, i;

int_stack_ctx_t *stack1 = int_stack_init(size);

for (i = 0; i < size + 3; i++) {

printf("stack: push %d\r\n", i);

int_stack_push(stack1, i);

}

for (i = 0; i < size + 3; i++) {

printf("stack: pop %d\r\n", int_stack_pop(stack1));

}

#endif

hannoi_int_ver(5);

hannoi_int_ver(3);

hannoi_int_ver(7);

}