C語言漢諾塔圖形化演示：棧模擬與遞歸算法完整實現

漢諾塔是遞歸與棧數據結構的經典教學案例。本文提供基於 VC++6.0 的完整圖形化演示程式，包含棧封裝、漢諾塔邏輯、控制台繪圖，生動展示移動過程。

專案結構

• stack.h / stack.c — 通用棧封裝
• main.c — 漢諾塔邏輯、繪圖、主流程

stack.h — 棧介面

#define NULL 0
typedef int ElementType;

typedef struct {
    ElementType *pbuffer;
    int max;
    int top;
} Stack;

Stack *InitStack(int n);
int Push(Stack *sp, ElementType *pdata);
int Pop(Stack *sp, ElementType *pdata);
int DestroyStack(Stack *sp);
int IsEmpty(Stack *sp);
int IsFull(Stack *sp);
int TravereStack(Stack *sp, int (*pfn)(ElementType*,int,int), int x, int y);

stack.c — 關鍵實現

Stack *InitStack(int n) {
    Stack *sp = (Stack*)malloc(sizeof(Stack));
    if(!sp) return NULL;
    sp->pbuffer = (ElementType*)malloc(sizeof(ElementType)*n);
    if(!sp->pbuffer) { free(sp); return NULL; }
    sp->max = n;
    sp->top = -1;
    return sp;
}

int Push(Stack *sp, ElementType *pdata) {
    if(IsFull(sp)) return 0;
    sp->top++;
    memcpy(sp->pbuffer + sp->top, pdata, sizeof(ElementType));
    return 1;
}

int TravereStack(Stack *sp, int (*pfn)(ElementType*,int,int), int x, int y) {
    for(int i=0; itop+1; i++) {
        pfn(sp->pbuffer+i, x, y);
        y--;
    }
    return 1;
}

main.c — 核心邏輯

資料結構

typedef struct {
    Stack *sp[3];   // 三根柱子
    int x[3];       // 三柱 X 座標
    int y;          // 起始 Y 座標
    int total;      // 盤子總數
} Hannuota;

控制台繪圖

void gotoxy(int x, int y) {
    COORD C = {x, y};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), C);
}

int ShowElement(ElementType *pdata, int x, int y) {
    gotoxy(x, y);
    printf("%d", *pdata);
    return 1;
}

遞歸移動算法

void Mov(Hannuota *han, int num, int a, int b, int c) {
    if(num < 1) return;
    Mov(han, num-1, a, c, b);   // n-1 從 a 移到 b（借助 c）
    ChangeData(han, a, c);       // 第 n 個從 a 移到 c
    Mov(han, num-1, b, a, c);   // n-1 從 b 移到 c（借助 a）
}

int ChangeData(Hannuota *han, int a, int b) {
    ElementType data;
    Pop(han->sp[a], &data);
    Push(han->sp[b], &data);
    ShowHannuota(han);  // 每步刷新畫面
    return 1;
}

初始化與啟動

Hannuota *InitHannuota(int n) {
    Hannuota *han = (Hannuota*)malloc(sizeof(Hannuota));
    han->total = n; han->y = 10;
    for(int i=0; i<3; i++) {
        han->x[i] = 10*i + 10;
        han->sp[i] = InitStack(n);
    }
    return han;
}

int GameStart(Hannuota *han) {
    for(int i=han->total; i>0; i--) Push(han->sp[0], &i);  // 大在下
    ShowHannuota(han);
    Mov(han, han->total, 0, 1, 2);  // A→C，借助 B
    return 1;
}

執行效果

控制台顯示三根柱子（A/B/C），盤子用數字表示大小，每步移動暫停等待按鍵，步數計數器遞增。

Hanio  Game  Ver 0.1
----- ----- -----
A     B     C
3     |     |
2     |     |
1     |     |
Step is No. 1

算法複雜度

• 移動次數：2ⁿ - 1（最優解）
• 時間複雜度：O(2ⁿ)
• 空間複雜度：O(n) 遞歸深度 + O(n) 棧存儲

改進方向

• 非遞歸迭代實現（用顯式棧模擬）
• 圖形界面（Win32 API / SDL / OpenGL）
• 動畫平滑過渡而非逐步暫停
• 支援任意初始/目標柱配置
• 面向對象重構（C++ 類封裝）

編譯與運行

// VC++ 6.0
cl main.c stack.c /FeHanoi.exe
Hanoi.exe

// GCC (需替換 gotoxy 為 ANSI 轉義序列)
gcc main.c stack.c -o hanoi