c_snake_game

第 9 课：链表 🔗

链表是贪吃蛇游戏的核心数据结构！蛇的身体就是一个链表。

---

9.1 什么是链表？

链表是由节点组成的数据结构，每个节点包含：

1. 数据 - 存储的信息
2. 指针 - 指向下一个节点

┌─────────┐    ┌─────────┐    ┌─────────┐
│ 数据: A │───>│ 数据: B │───>│ 数据: C │───> NULL
│  next: ─┼───>│  next: ─┼───>│  next: ─┘
└─────────┘    └─────────┘    └─────────┘
   ↑
  head

---

9.2 链表 vs 数组

特性	数组	链表
大小	固定	动态
访问	随机访问 O(1)	顺序访问 O(n)
插入/删除	慢（需要移动）	快（修改指针）
内存	连续	不连续

数组示例

int arr[5] = {1, 2, 3, 4, 5};  // 固定大小
arr[2] = 30;                    // 随机访问，快

链表示例

// 可以动态增长
Node* head = create_node(1);
add_node(&head, 2);
add_node(&head, 3);
// ... 可以一直添加

---

9.3 链表节点定义

typedef struct Node {
    int data;               // 数据
    struct Node* next;      // 指向下一个节点
} Node;

---

9.4 基本操作

创建节点

Node* create_node(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

在头部插入

void insert_at_head(Node** head, int data) {
    Node* new_node = create_node(data);
    new_node->next = *head;  // 新节点指向原头部
    *head = new_node;        // 更新头部
}

// 使用
Node* head = NULL;
insert_at_head(&head, 3);  // 3
insert_at_head(&head, 2);  // 2 -> 3
insert_at_head(&head, 1);  // 1 -> 2 -> 3

遍历链表

void print_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

删除节点

void delete_node(Node** head, int data) {
    Node* current = *head;
    Node* prev = NULL;
    
    // 找到要删除的节点
    while (current && current->data != data) {
        prev = current;
        current = current->next;
    }
    
    if (!current) return;  // 没找到
    
    // 删除
    if (!prev) {
        // 删除的是头节点
        *head = current->next;
    } else {
        prev->next = current->next;
    }
    
    free(current);
}

释放整个链表

void free_list(Node* head) {
    Node* current = head;
    while (current) {
        Node* next = current->next;
        free(current);
        current = next;
    }
}

---

9.5 贪吃蛇中的链表

蛇的身体天然就是一个链表！

// 蛇身段
typedef struct Segment {
    int x;                  // X 坐标
    int y;                  // Y 坐标
    struct Segment* next;   // 指向下一段
} Segment;

// 蛇
typedef struct {
    Segment* head;          // 头部
    Segment* tail;          // 尾部
    int length;             // 长度
    int direction;          // 方向
} Snake;

创建蛇

Snake* snake_create(int start_x, int start_y) {
    Snake* snake = malloc(sizeof(Snake));
    
    // 创建头部
    Segment* head = malloc(sizeof(Segment));
    head->x = start_x;
    head->y = start_y;
    head->next = NULL;
    
    snake->head = head;
    snake->tail = head;
    snake->length = 1;
    snake->direction = DIR_RIGHT;
    
    return snake;
}

移动蛇（关键！）

void snake_move(Snake* snake) {
    // 1. 计算新头部位置
    int new_x = snake->head->x;
    int new_y = snake->head->y;
    
    switch (snake->direction) {
        case DIR_UP:    new_y -= 1; break;
        case DIR_DOWN:  new_y += 1; break;
        case DIR_LEFT:  new_x -= 1; break;
        case DIR_RIGHT: new_x += 1; break;
    }
    
    // 2. 创建新头部
    Segment* new_head = malloc(sizeof(Segment));
    new_head->x = new_x;
    new_head->y = new_y;
    new_head->next = snake->head;
    
    snake->head = new_head;
    snake->length++;
    
    // 3. 移除尾部（除非在生长）
    if (!snake->growing) {
        // 找到倒数第二个节点
        Segment* current = snake->head;
        while (current->next->next) {
            current = current->next;
        }
        
        // 删除最后一个节点
        free(current->next);
        current->next = NULL;
        snake->tail = current;
        snake->length--;
    } else {
        snake->growing = false;  // 重置生长标志
    }
}

绘制蛇

void snake_render(Snake* snake) {
    Segment* current = snake->head;
    int is_head = 1;
    
    while (current) {
        char symbol = is_head ? 'O' : '#';
        
        // 使用 ncurses 或 printf 绘制
        mvaddch(current->y, current->x, symbol);
        
        current = current->next;
        is_head = 0;
    }
}

碰撞检测

bool snake_check_collision(Snake* snake, int width, int height) {
    // 检查墙壁碰撞
    if (snake->head->x <= 0 || snake->head->x >= width - 1 ||
        snake->head->y <= 0 || snake->head->y >= height - 1) {
        return true;
    }
    
    // 检查自身碰撞（从第二个节点开始）
    Segment* current = snake->head->next;
    while (current) {
        if (current->x == snake->head->x &&
            current->y == snake->head->y) {
            return true;
        }
        current = current->next;
    }
    
    return false;
}

销毁蛇

void snake_destroy(Snake* snake) {
    Segment* current = snake->head;
    
    while (current) {
        Segment* next = current->next;
        free(current);
        current = next;
    }
    
    free(snake);
}

---

9.6 完整示例

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef enum { DIR_UP, DIR_DOWN, DIR_LEFT, DIR_RIGHT } Direction;

typedef struct Segment {
    int x, y;
    struct Segment* next;
} Segment;

typedef struct {
    Segment* head;
    Segment* tail;
    int length;
    Direction dir;
    bool growing;
} Snake;

Snake* snake_create(int x, int y) {
    Snake* s = malloc(sizeof(Snake));
    Segment* seg = malloc(sizeof(Segment));
    seg->x = x; seg->y = y; seg->next = NULL;
    s->head = s->tail = seg;
    s->length = 1;
    s->dir = DIR_RIGHT;
    s->growing = false;
    return s;
}

void snake_move(Snake* s) {
    int nx = s->head->x, ny = s->head->y;
    if (s->dir == DIR_UP) ny--;
    else if (s->dir == DIR_DOWN) ny++;
    else if (s->dir == DIR_LEFT) nx--;
    else if (s->dir == DIR_RIGHT) nx++;
    
    Segment* new_head = malloc(sizeof(Segment));
    new_head->x = nx; new_head->y = ny;
    new_head->next = s->head;
    s->head = new_head;
    s->length++;
    
    if (!s->growing) {
        Segment* cur = s->head;
        while (cur->next->next) cur = cur->next;
        free(cur->next);
        cur->next = NULL;
        s->tail = cur;
        s->length--;
    } else {
        s->growing = false;
    }
}

void snake_destroy(Snake* s) {
    Segment* cur = s->head;
    while (cur) {
        Segment* next = cur->next;
        free(cur);
        cur = next;
    }
    free(s);
}

int main(void) {
    Snake* snake = snake_create(10, 10);
    
    printf("蛇创建成功，长度：%d\n", snake->length);
    
    snake_destroy(snake);
    return 0;
}

---

✅ 本课检查清单

• 理解链表的概念
• 会创建和遍历链表
• 理解链表在贪吃蛇中的应用
• 会动态添加和删除节点
• 知道如何释放链表

---

📝 作业

1. 实现链表的基本操作：插入、删除、查找

2. 实现双向链表（每个节点有 prev 和 next 指针）

3. 完善贪吃蛇的链表实现，添加吃食物生长的功能

---

下一课：模块化编程