# dsa_gamify

**Repository Path**: senzhanggit/dsa_gamify

## Basic Information

- **Project Name**: dsa_gamify
- **Description**: No description available
- **Primary Language**: C
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-02-16
- **Last Updated**: 2026-03-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 🚂 火车数据结构之旅 (Train Data Structure RPG)

一款基于火车场景的数据结构学习RPG游戏，通过实现各种数据结构和算法来完成你的火车旅程！

## 📖 项目简介

这是一个教育性质的RPG游戏，玩家扮演一位火车乘客，需要通过实现8个实验（涵盖经典数据结构和算法）来推进游戏进程。游戏将抽象的数据结构概念与具体的火车场景相结合，让学习变得更加有趣和直观。

## 🎮 游戏特色

- **场景化学习**: 每个数据结构都与火车场景紧密结合
- **实战编程**: 使用C99语言实现数据结构，真正的代码实践
- **即时反馈**: 自动编译测试，立即知道代码是否正确
- **版本控制**: 集成Git，自动保存和提交代码（必需）
- **编辑器支持**: 必须使用CLion编辑器，提供良好的编程体验（必需）

## 🗺️ 实验关卡设计

| 实验 | 场景 | 数据结构/算法 | 核心概念 |
|------|------|---------------|----------|
| 1 | 🚃 车厢座位管理 | **线性表的顺序表实现** | 随机访问 O(1) |
| 2 | 🎟️ 检票口乘客队列 | **线性表的链表实现** | 指针操作、动态插入删除 |
| 3 | 🍽️ 餐车盘子管理 | **栈的实现** | 后进先出 LIFO |
| 4 | 🎫 购票大厅排队 | **队列的实现** | 先进先出 FIFO |
| 5 | 🚃 车厢座位层级 | **二叉树操作** | 递归遍历、树形结构 |
| 6 | 🛤️ 列车调度网络 | **图的遍历操作** | 最短路径、Dijkstra算法 |
| 7 | 📍 站点信息查找 | **查找算法的实现** | 顺序查找、二分查找 |
| 8 | 📍 站点信息排序 | **排序算法的实现** | 冒泡排序、快速排序 |

## 🚀 快速开始

### 环境要求（所有条件必须满足）

- **Python 3.6+**
- **GCC编译器**
- **Git（必需）** - 必须安装并配置到PATH
- **CLion编辑器（必需）** - 必须安装并配置到PATH

**重要**: 必须确保 `clion` 或 `clion64` 以及 `git` 命令在PATH环境变量中可用。

### 安装步骤

1. **克隆或下载项目**
```bash
cd train_datastructure_rpg
```

2. **准备Git远程仓库（必需）**

游戏需要Git进行版本控制：
- 在 [Gitee](https://gitee.com) 或 [GitHub](https://github.com) 创建空仓库
- 确保本地已安装Git并配置到PATH
- 游戏启动时会自动检测并配置Git

3. **运行启动脚本**
```bash
python3 start_game.py
```

3. **开始游戏**
- 选择菜单选项1开始游戏
- 输入玩家名称
- 配置Git仓库信息（必需）
- **配置Git用户名和邮箱**（如果未设置，会自动提示）
- 开始你的数据结构之旅！

## 📁 项目结构

```
train_datastructure_rpg/
├── game/                   # 游戏引擎模块
│   ├── __init__.py
│   ├── engine.py          # 游戏主引擎
│   └── feedback_system.py # 细粒度反馈系统
├── templates/             # C语言代码模板（8个实验）
│   ├── lab1/              # 实验1: 车厢座位管理 - 顺序表
│   │   ├── main.c
│   │   └── CMakeLists.txt
│   ├── lab2/              # 实验2: 票口乘客队列 - 链表
│   │   ├── main.c
│   │   └── CMakeLists.txt
│   ├── lab3/              # 实验3: 车盘子管理 - 栈
│   │   ├── main.c
│   │   └── CMakeLists.txt
│   ├── lab4/              # 实验4: 购票大厅排队 - 队列
│   │   ├── main.c
│   │   └── CMakeLists.txt
│   ├── lab5/              # 实验5: 车厢座位层级 - 二叉树
│   │   ├── main.c
│   │   └── CMakeLists.txt
│   ├── lab6/              # 实验6: 车调度网络 - 图
│   │   ├── main.c
│   │   └── CMakeLists.txt
│   ├── lab7/              # 实验7: 站点信息查找 - 查找算法
│   │   ├── main.c
│   │   └── CMakeLists.txt
│   └── lab8/              # 实验8: 站点信息排序 - 排序算法
│       ├── main.c
│       └── CMakeLists.txt
├── lab1/ ~ lab8/          # 实验工作目录（运行时自动创建，不提交Git）
├── config/                # 配置文件
│   └── game_config.json
├── start_game.py          # 游戏启动脚本
├── demo.py                # 演示脚本
├── Makefile               # 构建脚本
└── README.md              # 项目说明
```

## 🎯 游戏玩法

### 1. 选择实验
在游戏主菜单中选择"查看关卡地图"，查看所有实验的状态：
- 🔒 锁定状态
- 🔄 可玩状态
- ✅ 已完成状态

### 2. 编写代码
选择实验后：
1. 游戏会自动创建代码模板文件
2. 选择"打开CLion编辑器"编写代码
3. 根据任务描述实现所需的数据结构

### 3. 测试代码
完成代码后：
1. 选择"编译并测试代码"
2. 游戏会自动编译并运行测试用例
3. 查看测试结果，根据反馈修改代码

### 4. 完成实验
测试通过后：
1. 选择"完成关卡"
2. 代码自动提交到Git仓库
3. 解锁下一实验

### 5. 获取帮助
遇到困难时：
- 选择"查看提示"获取实现思路
- 查看代码模板中的注释和示例
- 参考测试用例了解预期输出

## 💡 数据结构实现要点

### 实验1: 车厢座位管理 - 顺序表 (Sequential List)
```c
// 火车场景: 进入车厢，每个座位都有固定编号。通过顺序表管理这些座位的占用情况。
// 核心操作
void ListInitiate(SeqList *L);
int ListLength(SeqList L);
int ListInsert(SeqList *L, int i, DataType x);
int ListDelete(SeqList *L, int i, DataType *x);
int ListGet(SeqList L, int i, DataType *x);
```

### 实验2: 票口乘客队列 - 链表 (Linked List)
```c
// 火车场景: 列车即将到站，乘客们正在检票口排队检票。使用链表管理这个动态的乘客队列。
// 核心操作
int ListInitiate(LNode **head);
int ListLength(LNode *head);
int ListInsert(LNode *head, int i, DataType x);
int ListDelete(LNode *head, int i, DataType *x);
int ListGet(LNode *head, int i, DataType *x);
```

### 实验3: 车盘子管理 - 栈 (Stack)
```c
// 火车场景: 你来到餐车，看到一叠干净的盘子整齐地叠放着。服务员管理盘子的叠放和取用。
// 核心操作
int init_stack(Stack *s);
int push(Stack *s, int value);
int pop(Stack *s, int *value);
int peek(Stack *s, int *value);
int is_empty(Stack *s);
```

### 实验4: 购票大厅排队 - 队列 (Queue)
```c
// 火车场景: 你来到了繁忙的火车站购票大厅，人们正在排队等待购票。
// 核心操作
int init_queue(Queue **q);
int enqueue(Queue *q, int value);
int dequeue(Queue *q, int *value);
int queue_is_empty(Queue *q);
int queue_size(Queue *q);
```

### 实验5: 车厢座位层级 - 二叉树 (Binary Tree)
```c
// 火车场景: 车厢座位呈层级结构排列（如卧铺车厢的上中下铺），你需要理解这种层次关系。
// 核心操作
BiTreeNode* create_tree(char* pre_order_seq);
void preorder_traversal(BiTreeNode* root);
void inorder_traversal(BiTreeNode* root);
void postorder_traversal(BiTreeNode* root);
void levelorder_traversal(BiTreeNode* root);
int tree_depth(BiTreeNode* root);
int tree_node_count(BiTreeNode* root);
```

### 实验6: 车调度网络 - 图 (Graph)
```c
// 火车场景: 列车需要在复杂的铁路网络中找到最优路线。铁路网络可以用图来表示。
// 核心操作
void graph_init(MGraph *g);
int locate_vertex(MGraph g, VerTexType v);
int add_vertex(MGraph *g, VerTexType v);
int add_edge(MGraph *g, VerTexType v1, VerTexType v2, ArcType weight);
void DFS(MGraph g, int v);
void BFS(MGraph g, int v);
void dijkstra(MGraph g, int start, int dist[], int path[]);
```

### 实验7: 站点信息查找 - 查找算法 (Search)
```c
// 火车场景: 列车即将到站，你需要在站点列表中找到目的地。
// 核心操作
int sequential_search(int arr[], int n, int target);
int binary_search(int arr[], int n, int target);
int binary_search_recursive(int arr[], int low, int high, int target);
```

### 实验8: 站点信息排序 - 排序算法 (Sort)
```c
// 火车场景: 车站需要按照某种规则对站点信息进行排序。
// 核心操作
void swap(int *a, int *b);
void bubble_sort(int arr[], int n);
void quick_sort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void insertion_sort(int arr[], int n);
```

### 额外内容（可选）

项目还包含以下额外模板供参考学习：
- `templates/string_template.c` - 字符串处理
- `templates/hashtable_template.c` - 哈希表实现
- `templates/generallist_template.c` - 广义表实现
- `templates/searchsort_template.c` - 查找排序综合

## 🔧 高级功能

### Git自动检测与初始化

游戏启动时会**自动检测**当前目录的Git状态：

#### 场景1: 已是Git仓库
```
🔍 正在检测Git仓库状态...
✅ 检测到Git仓库
📡 远程仓库: https://gitee.com/username/repo.git
```

#### 场景2: 不是Git仓库
```
🔍 正在检测Git仓库状态...
ℹ️  当前目录不是Git仓库

📦 Git仓库初始化
============================================================

当前目录不是一个Git仓库。
你需要提供一个远程代码仓库地址来初始化。

支持的平台:
  • GitHub: https://github.com/username/repo.git
  • Gitee:  https://gitee.com/username/repo.git
  • GitLab: https://gitlab.com/username/repo.git
  • 或其他Git服务器...

请输入远程仓库地址: https://gitee.com/username/trainrpg.git
Git用户名: your_name
Git密码/Token: your_token

🔄 正在初始化Git仓库...
✅ Git仓库初始化成功
✅ 远程仓库origin已设置
✅ 初始提交创建成功
🔄 正在推送到远程仓库...
✅ 代码已推送到远程仓库

🎉 Git仓库配置完成！
```

#### 场景3: 跳过Git配置
```
请输入远程仓库地址 (或输入'skip'跳过): skip

⚠️ 已跳过Git功能，游戏将以本地模式运行
   你可以稍后通过菜单重新配置
```

### Git工作流程

1. **自动提交**: 完成关卡时自动提交代码
2. **自动推送**: 自动推送到远程仓库
3. **版本历史**: 每个关卡都有独立的提交记录
4. **重新配置**: 可通过主菜单随时重新配置Git

### 支持的Git平台

- **Gitee** (推荐国内用户): https://gitee.com
- **GitHub**: https://github.com
- **GitLab**: https://gitlab.com
- **自建Git服务器**: 支持任何标准Git服务器

### 细粒度反馈系统

游戏提供**多层级、实时**的代码反馈，帮助学生快速定位问题：

#### 反馈层级

| 层级 | 功能 | 响应时间 | 用途 |
|------|------|----------|------|
| **1. 语法检查** | 使用 `gcc -fsyntax-only` 快速检查语法 | < 1秒 | 快速发现语法错误 |
| **2. 函数级测试** | 逐个函数验证正确性 | < 5秒 | 定位具体函数问题 |
| **3. 逻辑检查** | 检查常见逻辑错误模式 | < 1秒 | 发现潜在逻辑问题 |
| **4. 完整测试** | 编译并运行完整测试 | < 30秒 | 最终验证 |

#### 使用示例

```
请选择操作:
  1. 📝 打开CLion编辑器编写代码
  2. 🔍 快速语法检查（秒级反馈）      ← 边写边查
  3. 🧩 函数级测试（逐个函数验证）     ← 逐个验证
  4. 📊 完整反馈报告                   ← 全面分析
  5. 🧪 编译并运行完整测试             ← 最终测试
  6. 💡 查看提示
  ...
```

#### 反馈示例

**语法检查反馈：**
```
🔍 正在进行快速语法检查...
❌ 语法错误: expected ';' before '}' token
   📍 第25行
   💡 建议: 检查语法结构，确保所有括号、分号都正确闭合

✅ 语法检查通过！没有发现语法错误。
```

**函数级测试反馈：**
```
🧩 正在进行函数级测试...
✅ queue_init: 函数测试通过！
❌ queue_enqueue: 函数测试失败
   💡 提示: 入队时将元素放入rear位置，然后rear后移
✅ queue_dequeue: 函数测试通过！

📊 测试结果: 2/3 通过
```

**完整反馈报告：**
```
📋 代码反馈报告
============================================================

【1. 语法检查】
✅ 语法检查通过！没有发现语法错误。

【2. 函数级测试】
✅ queue_init: 函数测试通过！
✅ queue_enqueue: 函数测试通过！
✅ queue_dequeue: 函数测试通过！

【3. 逻辑检查】
✅ 检测到循环队列实现

【4. 数据结构可视化】
📊 队列可视化
═══════════════════════════════════════
队列状态: [数据] front → ... → rear
入队: 元素从 rear 进入
出队: 元素从 front 离开
═══════════════════════════════════════
```

### CMake构建系统

每个实验模板都包含 **CMakeLists.txt** 文件：

```cmake
cmake_minimum_required(VERSION 3.10)
project(lab1 C)

set(CMAKE_C_STANDARD 99)
set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -Wall -Wextra")

add_executable(lab1 main.c)
```

#### 编译方式

游戏支持两种编译方式：

1. **CMake (优先)** - 如果系统安装了CMake
   ```bash
   cd lab1
   mkdir -p build
   cd build
   cmake ..
   cmake --build .
   ./lab1
   ```

2. **GCC (备选)** - 直接使用gcc编译
   ```bash
   cd lab1
   gcc -std=c99 -Wall -o lab1 main.c
   ./lab1
   ```

#### 使用CLion打开

CMakeLists.txt文件可以直接被CLion识别：
1. 选择实验菜单中的"打开CLion编辑器"
2. CLion会自动加载CMakeLists.txt
3. 可以直接在CLion中编译运行

### 编辑器集成
游戏支持多种方式打开代码：
- **CLion**: 如果已安装，直接调用CLion打开
- **系统默认编辑器**: 使用xdg-open调用默认编辑器
- **手动打开**: 显示文件路径，手动打开编辑

## 📝 开发计划

- [x] 游戏引擎核心功能
- [x] 8个实验模板
- [x] Git集成
- [x] CLion支持
- [ ] 更多测试用例
- [ ] 图形界面版本
- [ ] 在线排行榜
- [ ] 社区关卡分享

## 🤝 贡献指南

欢迎提交Issue和Pull Request！

1. Fork项目
2. 创建特性分支 (`git checkout -b feature/AmazingFeature`)
3. 提交更改 (`git commit -m 'Add some AmazingFeature'`)
4. 推送到分支 (`git push origin feature/AmazingFeature`)
5. 打开Pull Request

## 📄 许可证

本项目采用 MIT 许可证 - 详见 [LICENSE](LICENSE) 文件

## 🙏 致谢

感谢所有数据结构教材和在线资源，让学习变得更加有趣！

## 📧 联系方式

如有问题或建议，欢迎通过以下方式联系：
- 提交GitHub Issue
- 发送邮件至: your.email@example.com

---

🚂 **开始你的数据结构火车之旅吧！**