# data-structure-c

**Repository Path**: jiao-jingzhe/data-structure-c

## Basic Information

- **Project Name**: data-structure-c
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 5
- **Created**: 2025-06-14
- **Last Updated**: 2025-06-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#include <conio.h>

// ================== 常量与类型定义区 ==================
#define MAP_ROWS 21
#define MAP_COLS 20
#define DOT '.'
#define WALL '#'
#define EMPTY ' '
#define PACMAN 'P'
#define GHOST 'G'
#define NAME_LEN 16
#define GHOST_COUNT 4

/** * 表示地图上的一个坐标点。 * r 表示行号（row），c 表示列号（column）。 */
typedef struct {
    int r, c; // r: 行号，c: 列号
} Point;

// --- 排行榜结构体 ---
/** * 表示排行榜中的一条记录。 * name 为玩家姓名，score 为玩家得分。 */
typedef struct {
    char name[NAME_LEN]; // 玩家姓名
    int score;           // 玩家得分
} LeaderboardEntry;

// ================== 数据结构层 ==================
// --- 队列（用于BFS，循环队列实现） ---
// QUEUE_MAX 定义循环队列的最大容量，等于地图的最大点数
#define QUEUE_MAX (MAP_ROWS * MAP_COLS)

/** * 循环队列结构体，用于BFS等场景。 * data 存储队列中的点（Point），front 为队头索引，rear 为队尾索引。 */
typedef struct {
    Point data[QUEUE_MAX]; // 队列数据数组
    int front, rear;       // 队头和队尾索引
} Queue;

void queue_init(Queue* q) {
    q->front = q->rear = 0;
}

int queue_empty(Queue* q) {
    return q->front == q->rear;
}

int queue_full(Queue* q) {
    return (q->rear + 1) % QUEUE_MAX == q->front;
}

void queue_push(Queue* q, Point p) {
    if (queue_full(q)) return;
    q->data[q->rear] = p;
    q->rear = (q->rear + 1) % QUEUE_MAX;
}

Point queue_pop(Queue* q) {
    if (queue_empty(q)) {
        Point dummy = {-1, -1};
        return dummy;
    }
    Point p = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_MAX;
    return p;
}

// --- 排序（通用） ---
/** * 对排行榜数组按分数从高到低进行排序。 * @param arr 排行榜数组。 * @param n 数组长度。 */
void sort(LeaderboardEntry* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int max_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j].score > arr[max_idx].score) {
                max_idx = j;
            }
        }
        if (max_idx != i) {
            LeaderboardEntry temp = arr[i];
            arr[i] = arr[max_idx];
            arr[max_idx] = temp;
        }
    }
}

// --- 链表（通用）结构体定义 ---
typedef struct {
    int r, c;
} Dot; // 豆子或坐标结构体

typedef struct ListNode {
    Dot pos;               // 节点存储的豆子位置
    struct ListNode* next; // 指向下一个节点
} ListNode;

typedef struct {
    ListNode* head; // 链表头指针
    int count;      // 链表节点数量
} LinkedList;

// --- 链表（通用） ---
/** * 初始化链表。 * @param list 指向链表的指针。 */
void LinkedList_init(LinkedList* list) {
    list->head = NULL;
    list->count = 0;
}

/** * 向链表头部插入一个节点。 * @param list 指向链表的指针。 * @param pos 要插入的Dot结构体（豆子位置）。 */
void LinkedList_insert(LinkedList* list, Dot pos) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->pos = pos;
    newNode->next = list->head;
    list->head = newNode;
    list->count++;
}

/** * 从链表中移除指定位置的节点。 * @param list 指向链表的指针。 * @param pos 要移除的Dot结构体（豆子位置）。 * @return 如果移除成功返回1，否则返回0。 */
int LinkedList_remove(LinkedList* list, Dot pos) {
    ListNode* current = list->head;
    ListNode* prev = NULL;

    while (current != NULL) {
        if (current->pos.r == pos.r && current->pos.c == pos.c) {
            if (prev == NULL) {
                list->head = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            list->count--;
            return 1;
        }
        prev = current;
        current = current->next;
    }
    return 0;
}

/** * 释放链表所有节点，重置链表。 * @param list 指向链表的指针。 */
void LinkedList_free(LinkedList* list) {
    ListNode* current = list->head;
    while (current != NULL) {
        ListNode* next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
    list->count = 0;
}

// 自定义比较函数类型
typedef int (*CompareFunc)(void* a, void* b);

// --- 二叉树相关函数（通用） ---
// --- 二叉树结构体（通用） ---
/** * 二叉树节点结构体。 * name 表示节点名称，left/right 分别为左、右子节点指针。 */
typedef struct BinaryTreeNode {
    char name[16];             // 节点名称，此处用来保存技能名称
    struct BinaryTreeNode* left;  // 左子节点
    struct BinaryTreeNode* right; // 右子节点
} BinaryTreeNode;

/** * 创建一个二叉树节点。 * @param name 节点名称。 * @return 新创建的二叉树节点指针。 */
BinaryTreeNode* BinaryTree_create(const char* name) {
    BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    strcpy(node->name, name);
    node->left = node->right = NULL;
    return node;
}

/** * 将child节点插入到parent的左子树。 * @param parent 父节点。 * @param child 子节点。 */
void BinaryTree_insert_left(BinaryTreeNode* parent, BinaryTreeNode* child) {
    if (parent) parent->left = child;
}

/** * 将child节点插入到parent的右子树。 * @param parent 父节点。 * @param child 子节点。 */
void BinaryTree_insert_right(BinaryTreeNode* parent, BinaryTreeNode* child) {
    if (parent) parent->right = child;
}

/** * 递归释放二叉树所有节点。 * @param root 根节点指针。 */
void BinaryTree_free(BinaryTreeNode* root) {
    if (!root) return;
    BinaryTree_free(root->left);
    BinaryTree_free(root->right);
    free(root);
}

/** * 二叉树先序遍历（递归实现）。 * @param root 根节点指针。 */
void BinaryTree_preorder(BinaryTreeNode* root) {
    if (root == NULL) return;
    printf("%s ", root->name);
    BinaryTree_preorder(root->left);
    BinaryTree_preorder(root->right);
}

/** * 计算二叉树的最大深度。 * @param root 根节点指针。 * @return 最大深度。 */
int BinaryTree_depth(BinaryTreeNode* root) {
    if (root == NULL) return 0;
    int left_depth = BinaryTree_depth(root->left);
    int right_depth = BinaryTree_depth(root->right);
    return (left_depth > right_depth ? left_depth : right_depth) + 1;
}

/** * 计算二叉树节点总数。 * @param root 根节点指针。 * @return 节点总数。 */
int BinaryTree_count(BinaryTreeNode* root) {
    if (root == NULL) return 0;
    return 1 + BinaryTree_count(root->left) + BinaryTree_count(root->right);
}

/** * 计算二叉树叶子节点数量。 * @param root 根节点指针。 * @return 叶子节点数量。 */
int BinaryTree_leaf_count(BinaryTreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return BinaryTree_leaf_count(root->left) + BinaryTree_leaf_count(root->right);
}

// --- 二叉树构造（技能树示例） ---
BinaryTreeNode* BinaryTree_sample() {
    BinaryTreeNode* root = BinaryTree_create("RootSkill");
    BinaryTreeNode* left = BinaryTree_create("Attack");
    BinaryTreeNode* right = BinaryTree_create("Defense");
    BinaryTreeNode* leftleft = BinaryTree_create("Accelerate");
    BinaryTreeNode* leftright = BinaryTree_create("More One Life");
    BinaryTreeNode* rightleft = BinaryTree_create("Cross Wall");
    BinaryTreeNode* rightright = BinaryTree_create("Unbeatable");

    BinaryTree_insert_left(root, left);
    BinaryTree_insert_right(root, right);
    BinaryTree_insert_left(left, leftleft);
    BinaryTree_insert_right(left, leftright);
    BinaryTree_insert_left(right, rightleft);
    BinaryTree_insert_right(right, rightright);

    return root;
}

// --- 图结构体与BFS ---
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
} Graph;

void graph_init(Graph* g, char grid[MAP_ROWS][MAP_COLS]) {
    for (int i = 0; i < MAP_ROWS; i++)
        for (int j = 0; j < MAP_COLS; j++)
            g->grid[i][j] = grid[i][j];
}

/** * 初始化前驱数组 */
void init_pre(Point pre[MAP_ROWS][MAP_COLS]) {
    for (int i = 0; i < MAP_ROWS; i++)
        for (int j = 0; j < MAP_COLS; j++)
            pre[i][j].r = pre[i][j].c = -1;
}

/** * BFS主循环，负责遍历地图、判断终点、记录前驱。 * @param g 指向图结构体。 * @param start 起点坐标。 * @param target 终点坐标。 * @param vis 访问标记数组。 * @param pre 前驱数组，用于路径回溯。 * @return 若找到终点返回1，否则返回0。 */
int bfs_core(Graph* g, Point start, Point target, int vis[MAP_ROWS][MAP_COLS], Point pre[MAP_ROWS][MAP_COLS]) {
    Queue q;
    queue_init(&q);
    vis[start.r][start.c] = 1;
    queue_push(&q, start);

    int dr[] = {-1, 1, 0, 0}; // 上、下、左、右
    int dc[] = {0, 0, -1, 1};

    while (!queue_empty(&q)) {
        Point p = queue_pop(&q);

        if (p.r == target.r && p.c == target.c) {
            return 1; // 找到终点
        }

        for (int i = 0; i < 4; i++) {
            int nr = p.r + dr[i];
            int nc = p.c + dc[i];

            // 检查新点是否有效
            if (nr >= 0 && nr < MAP_ROWS && nc >= 0 && nc < MAP_COLS && 
                !vis[nr][nc] && g->grid[nr][nc] != WALL) {
                vis[nr][nc] = 1;
                pre[nr][nc] = p;
                queue_push(&q, (Point){nr, nc});
            }
        }
    }
    return 0; // 未找到终点
}

/** * 路径回溯，根据前驱数组回溯最短路径。 * @param start 起点坐标。 * @param target 终点坐标。 * @param pre 前驱数组。 * @param path 用于存储回溯得到的路径。 * @return 路径长度。 */
int backtrack_path(Point start, Point target, Point pre[MAP_ROWS][MAP_COLS], Point* path) {
    int len = 0;
    Point cur = target;
    Point tmp_path[MAP_ROWS * MAP_COLS];

    while (!(cur.r == start.r && cur.c == start.c)) {
        tmp_path[len++] = cur;
        cur = pre[cur.r][cur.c];
    }
    tmp_path[len++] = start;

    for (int i = 0; i < len; i++) {
        path[i] = tmp_path[len-1-i];
    }
    return len;
}

/** * BFS查找最短路径，主函数。 * 负责调用BFS主循环和路径回溯，返回最短路径长度。 * @param g 指向图结构体。 * @param start 起点坐标。 * @param target 终点坐标。 * @param path 用于存储最短路径的数组（可为NULL）。 * @param path_len 用于存储路径长度的指针（可为NULL）。 * @return 路径长度（若不可达返回0）。 */
int graph_bfs(Graph* g, Point start, Point target, Point* path, int* path_len) {
    if (start.r == target.r && start.c == target.c) {
        if (path) path[0] = start;
        if (path_len) *path_len = 1;
        return 1;
    }

    int vis[MAP_ROWS][MAP_COLS] = {0};
    Point pre[MAP_ROWS][MAP_COLS];
    init_pre(pre);

    int found = bfs_core(g, start, target, vis, pre);
    if (!found) { 
        if (path_len) *path_len = 0; 
        return 0; 
    }

    int len = backtrack_path(start, target, pre, path);
    if (path_len) *path_len = len;
    return len;
}

// ================== 逻辑层 ==================
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
    LinkedList dots;
} Map;

typedef struct {
    int row, col;
    int score;
    int lives;
} Pacman;

typedef struct {
    int row, col;
} Ghost;

static char map_data[MAP_ROWS][MAP_COLS+1] = {
    "####################",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#.................#",
    "#..##..####..##...#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "######.#.##.#.######",
    "#      #.##.#      #",
    "######.#.##.#.######",
    "#.................#",
    "######.#.##.#.######",
    "#      #.##.#      #",
    "######.#.##.#.######",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#..##..####..##...#",
    "#.................#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "####################"
};

void map_init(Map* map) {
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map_data[i][j];
            map->grid[i][j] = c;
        }
    }
    LinkedList_init(&map->dots);
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            if (map->grid[i][j] == DOT) {
                Dot pos = {i, j};
                LinkedList_insert(&map->dots, pos);
            }
        }
    }
}

int map_eat_dot(Map* map, int row, int col) {
    if (map->grid[row][col] != DOT) return 0;
    Dot pos = {row, col};
    int removed = LinkedList_remove(&map->dots, pos);
    if (removed) {
        map->grid[row][col] = EMPTY;
        return 1;
    }
    return 0;
}

void pacman_init(Pacman* p, int row, int col) {
    p->row = row; p->col = col; p->score = 0; p->lives = 3;
}

void ghost_init(Ghost* g, int row, int col) {
    g->row = row; g->col = col;
}

void pacman_draw(Pacman* p, Map* map) {
    map->grid[p->row][p->col] = PACMAN;
}

void ghost_draw(Ghost* g, Map* map) {
    map->grid[g->row][g->col] = GHOST;
}

void ghost_move(Map* map, Ghost* ghost, Pacman* pacman) {
    Graph g;
    graph_init(&g, map->grid);
    Point path[MAP_ROWS * MAP_COLS];
    int path_len;
    if (graph_bfs(&g, (Point){ghost->row, ghost->col}, 
                (Point){pacman->row, pacman->col}, path, &path_len)) {
        if (path_len > 1) {
            ghost->row = path[1].r;
            ghost->col = path[1].c;
        }
    }
}

// ================== UI层 ==================
// Windows控制台设置函数
void setup_console() {
    // 获取控制台句柄
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    // 设置控制台字体
    CONSOLE_FONT_INFOEX fontInfo;
    fontInfo.cbSize = sizeof(fontInfo);
    GetCurrentConsoleFontEx(hConsole, FALSE, &fontInfo);
    wcscpy(fontInfo.FaceName, L"Consolas");
    fontInfo.dwFontSize.Y = 16;
    SetCurrentConsoleFontEx(hConsole, FALSE, &fontInfo);
}

// 使用ASCII字符定义墙体
const char* WALL_CHARS[] = {
    "+", // 十字
    "-", // 横线
    "|", // 竖线
    "+", // 左上
    "+", // 右上
    "+", // 左下
    "+", // 右下
    "+", // 左中
    "+", // 右中
    "+", // 上中
    "+"  // 下中
};

void map_draw(Map* map) {
    int ghost_color_idx = 0;
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    const WORD ghost_colors[] = {
        FOREGROUND_RED | FOREGROUND_INTENSITY, // 红色
        FOREGROUND_BLUE | FOREGROUND_INTENSITY, // 蓝色
        FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY, // 黄色
        FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY // 白色
    };

    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map->grid[i][j];
            if (c == WALL) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
                int up = (i > 0 && map->grid[i-1][j] == WALL);
                int down = (i < MAP_ROWS-1 && map->grid[i+1][j] == WALL);
                int left = (j > 0 && map->grid[i][j-1] == WALL);
                int right = (j < MAP_COLS-1 && map->grid[i][j+1] == WALL);
                
                if (up && down && left && right) printf("+");
                else if (up && down) printf("|");
                else if (left && right) printf("-");
                else printf("+");
            } else if (c == DOT) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
                printf(".");
            } else if (c == PACMAN) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
                printf("C"); // 使用C代表Pacman
            } else if (c == GHOST) {
                SetConsoleTextAttribute(hConsole, ghost_colors[ghost_color_idx]);
                printf("G"); // 使用G代表Ghost
                ghost_color_idx = (ghost_color_idx + 1) % 4;
            } else {
                printf(" ");
            }
        }
        printf("\n");
        ghost_color_idx = 0;
    }
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
    printf("\nDots left: %d\n", map->dots.count);
}

void leaderboard_ui(LeaderboardEntry* lb, int n) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    sort(lb, n);
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("\n+======== Leaderboard ========+\n");
    
    for (int i = 0; i < n; i++) {
        printf("| ");
        if (i == 0) {
            SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
        } else {
            SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
        }
        printf("%-10s | %4d", lb[i].name, lb[i].score);
        
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf(" |\n");
    }
    printf("+===========================+\n");
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
}

void binarytree_print_with_color(BinaryTreeNode* node, int depth, int isLast, int isRoot) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    
    for (int i = 0; i < depth; i++) {
        printf("|   "); // 改为竖线表示层级
    }
    
    if (depth > 0) {
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf("|-- "); // 统一使用|--连接
    }
    
    if (isRoot) {
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
        printf("%s\n", node->name);
    } else {
        SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf("%s\n", node->name);
    }
    
    if (node->left && node->right) {
        binarytree_print_with_color(node->left, depth+1, 0, 0);
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    } else if (node->left) {
        binarytree_print_with_color(node->left, depth+1, 1, 0);
    } else if (node->right) {
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    }
}

void binarytree_ui(BinaryTreeNode* root) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("\n+====== Skill Tree ======+\n");
    
    if (root)
        binarytree_print_with_color(root, 0, 1, 1);
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("+=======================+\n");
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Total Skills: ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_count(root));
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Skills Level(Tree Depth): ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_depth(root));
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Real Powerful Skills(Leaf count): ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_leaf_count(root));
}

// Windows版本的键盘输入检测
int kbhit() {
    return _kbhit();
}

// ================== 主函数 ==================
int main() {
    // 设置控制台
    setup_console();
    
    Map map;
    Pacman pacman;
    Ghost ghosts[GHOST_COUNT];
    LeaderboardEntry lb[5] = { {"Alice", 120}, {"Bob", 200}, 
                              {"Carol", 150}, {"You", 0}, {"Test", 0} };
    char playerName[NAME_LEN] = "You";
    
    srand(time(NULL));
    map_init(&map);
    pacman_init(&pacman, 10, 10);
    ghost_init(&ghosts[0], 1, 2);
    ghost_init(&ghosts[1], 1, 17);
    ghost_init(&ghosts[2], 19, 2);
    ghost_init(&ghosts[3], 19, 17);
    
    int frame = 0;
    int running = 1;
    
    while (running) {
        system("cls"); // Windows清屏命令
        
        // 清除上一帧的Pacman和Ghost
        for (int i = 0; i < MAP_ROWS; i++)
            for (int j = 0; j < MAP_COLS; j++)
                if (map.grid[i][j] == PACMAN || map.grid[i][j] == GHOST)
                    map.grid[i][j] = EMPTY;
        
        // 绘制当前帧
        pacman_draw(&pacman, &map);
        for (int i = 0; i < GHOST_COUNT; i++)
            ghost_draw(&ghosts[i], &map);
        
        map_draw(&map);
        
        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
        printf("\nName: %s Score: %d Lives: %d\n", playerName, pacman.score, pacman.lives);
        
        // 处理键盘输入
        if (kbhit()) {
            char key = _getch();
            int dr = 0, dc = 0;
            if (key == 'w' || key == 'W') dr = -1;
            if (key == 's' || key == 'S') dr = 1;
            if (key == 'a' || key == 'A') dc = -1;
            if (key == 'd' || key == 'D') dc = 1;
            
            int nr = pacman.row + dr, nc = pacman.col + dc;
            if (nr >= 0 && nr < MAP_ROWS && nc >= 0 && nc < MAP_COLS && map.grid[nr][nc] != WALL) {
                pacman.row = nr; pacman.col = nc;
                if (map_eat_dot(&map, nr, nc)) pacman.score += 10;
            }
        }
        
        // 幽灵移动（每2帧移动一次）
        if (frame % 2 == 0) {
            for (int i = 0; i < GHOST_COUNT; i++) {
                ghost_move(&map, &ghosts[i], &pacman);
                // 检查是否碰到幽灵
                if (ghosts[i].row == pacman.row && ghosts[i].col == pacman.col) {
                    pacman.lives--;
                    if (pacman.lives <= 0) running = 0;
                }
            }
        }
        
        // 检查游戏结束条件
        if (map.dots.count == 0) {
            running = 0; // 吃光所有豆子获胜
        }
        
        Sleep(120); // Windows睡眠函数，单位为毫秒
        frame++;
    }
    
    printf("\nGame Over!\n");
    lb[3].score = pacman.score;
    leaderboard_ui(lb, 5);
    
    BinaryTreeNode* skillroot = BinaryTree_sample();
    binarytree_ui(skillroot);
    BinaryTree_free(skillroot);
    
    LinkedList_free(&map.dots);
    
    // 恢复默认颜色
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
    return 0;
}