不用递归实现汉诺塔,堆栈模拟递归

plaodj

不用递归实现汉诺塔,堆栈模拟递归

[mw_shl_code=cpp,true]#include <stdio.h>
#include <math.h>
#include <malloc.h>

typedef struct MyStruct
{
        int i;
        char A;
        char B;
        char C;
}cs, *Pcs;

void mov(int i, char A, char B, char C);
void mov_stack(int i, char A, char B, char C);

int main()
{
        int cou = 0;
        printf_s("Please Input a number:");
        scanf_s("%d", &cou);
        printf_s("递归:\n");
        mov(cou, 'A', 'B', 'C');
        printf_s("stack:\n");
        mov_stack(cou, 'A', 'B', 'C');
        return 0;
}

void mov(int i, char A, char B, char C)
{
        if (i == 1)
                printf_s("%c->%c\n", A, C);
        else
        {
                mov(i - 1, A, C, B);
                printf_s("%c->%c\n", A, C);
                mov(i - 1, B, A, C);
        }
}

void mov_stack(int n, char A, char B, char C)
{
        int sum = (int)pow(2.0, (double)n);
        // 计算次数 (-1没减)
        Pcs stack = (Pcs)malloc(sizeof(cs) * sum);
        //分配堆栈空间
        int index = 0;
        //堆栈初始化
        stack[index].i = n;
        stack[index].A = A;
        stack[index].B = B;
        stack[index].C = C;
        index++;
        //push
        while (index)
        {
                if (stack[index - 1].i > 1)
                {
                        stack[index].i = stack[index - 1].i - 1;
                        stack[index].A = stack[index - 1].A;
                        stack[index].B = stack[index - 1].C;
                        stack[index].C = stack[index - 1].B;
                        index++;
                        //if(i>1) push
                }
                else
                {
                        printf_s("%c->%c\n", stack[index - 1].A, stack[index - 1].C);
                        //if(i==1) show
                        index--;
                        //pop
                        if (!index)
                                break;
                        if (stack[index - 1].i == stack[index - 2].i)// 是否为第二个
                        {
                                while (index && stack[index - 1].i == stack[index - 2].i)//pop
                                        index -= 2;
                                if (!index)
                                        break;
                        }

                        printf_s("%c->%c\n", stack[index - 1].A, stack[index - 1].C);
                        //show  两个函数之间的那句
                        
                        stack[index].i = stack[index - 1].i;
                        stack[index].A = stack[index - 1].B;
                        stack[index].B = stack[index - 1].C;
                        stack[index].C = stack[index - 1].A;
                        index++;
                        /*
                        push
                        因为
                        A B C
                        B A C
                        所以
                        A C B
                        B C A
                        */
                }
        }}[/mw_shl_code]