pietro-pelizon/projeto-02-EDII

# 仓库结构 ``` . ├── docs # Arquivos (.pdf) com as especificações do projeto ├── include # Arquivos de cabeçalho (.h) ├── src # Implementação do projeto (.c) ├── testes # Arquivos de comando (.geo, .qry e .via) ├── unit_test # Testes unitários feitos utilizando o Framework Unity (test_*.c) ├── unity # Framework Unity para testes em C └── README.md # Documentação do repositório ``` ## 关于本项目 本项目开发了一个针对 Bitnópolis 市的模拟地理信息系统 (SIG)，重点在于高级数据结构（Graph、List、Hashmap 和 Priority Queue）的实现与使用，旨在优化并分析其复杂的道路交通流。 系统处理基于街区的地图，构建道路网络并解决路径规划问题（最短路径和最快路径），同时生成详细的文本输出和动态的 `.svg` 可视化渲染。 ## 主要功能 * **泛型数据结构：** 模块化实现的数据结构，用于处理城市数据，确保了灵活性和代码复用性。 * **Hashmap：** 通过字母数字格式的 CEP 快速映射和搜索街区。 * **Graph（Adjacency List）：** 道路地图的表示（路口作为顶点，街道作为带有距离和速度权重的边）。 * **Priority Queue (PQueue)：** 用于优化搜索算法的基础结构。 * **路径规划与分析算法：** * **Dijkstra 算法：** 高效计算最佳路线（距离最短或时间最快）。 * **Minimum Spanning Tree (MST)：** 识别需要扩建以改善城市互联的路段。 * **Connected Components：** 分析道路交通流中的“孤岛”。 * **图形输出与动画：** 生成交互式的 `.svg` 文件，显示城市地图、bounding boxes、高亮显示的路段以及所找到路径的动画（使用 ``）。 ## 输入文件 系统主要处理三种类型的输入文件： - `.geo` 文件：描述城市的几何结构（矩形街区、CEP、颜色）。 - `.via` 文件：描述道路系统（代表路口的顶点和代表街道的有向边，包含平均速度和长度等属性）。 - `.qry` 文件：包含将修改地图或请求数据的地理和路径规划查询。 ### (`.geo`) 文件 定义城市街区的外观、大小和位置。 | **命令** | **参数** | **描述** | |-------------|-------------------------|----------------------------------------------------------------------------------------------------| | `q` | `cep x y w h` | 插入一个具有指定属性的街区。 | | `cq` | `sw cor_fill cor_borda` | 定义此命令之后街区的填充颜色、边框粗细和颜色。 | ### (`.via`) 文件 定义城市的整个道路系统（街道和路口） | **命令** | **参数** | **描述** | |--------------|-----------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------| | `nv` | `n` | 文件的第一行预先定义了道路 Graph 中存在的顶点数量。 | | `v` | `id x y` | 创建标识符为 `id` 的顶点，并将其放置在坐标 (`x, y`) 处。 | | | `e` | `i j ldir lesq cmp vm nome` | 创建边 (`i, j`) 并将其他信息关联到该边。如果边在其某一侧没有街区，则使用 '`#`' 表示缺失。 | ### 查询命令 (.qry) | **命令** | **参数** | **描述** | |-------------|--------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------| | `@o?` | `reg cep face num` | 将地址的地理位置存储在寄存器 `reg` 中。在 `.svg` 中标记该点并在 `.txt` 中报告。 | | `mvm` | `v x y w h` | 将定义区域内边（街道）的平均速度更新为 `v`。 | | `regs` | `v` | 识别交通流岛屿的 connected components（速度 $\ge$ `v1` 的街道）。在 (`.svg`) 中绘制半透明的 bounding boxes。 | | `exp` | `v1` | 计算慢速道路（< `v1`）的 Minimum Spanning Tree (MST)，将这些道路的速度提高 50%。在 `.svg` 中以红色高亮显示。 | | `p?` | `reg1 reg2 cc cr` | 计算起点 (`reg1`) 和终点 (`reg2`) 之间的最佳路线。在 `.svg` 中绘制并生成最短路径（颜色为 `cc`）和最快路径（颜色为 `cr`）的动画。 | ## 前置条件 请确保您的环境中已安装以下工具： * **GCC** 编译器（支持 C99 标准） * **Make**（用于自动化 build） * **Linux** 或 **WSL** (Windows Subsystem for Linux) 环境 ## 编译与执行 项目在 `src` 文件夹中包含一个 Makefile，以方便主可执行文件和测试套件的编译。 - 要编译主项目，请执行： ``` cd src && make ``` ## 单元测试 (Unity Framework) 为了确保每个 **TAD**（Tipo Abstrato de Dado，抽象数据类型）和功能模块的完整性，本项目使用了 **Unity** 框架。 测试文件位于 `unit_test/` 文件夹中，带有 `test_*.c` 前缀。`Makefile` 已配置为独立编译并执行每个测试套件。 - 要运行特定测试，请在 `src/` 文件夹中使用 `test_` 前缀加上模块名称。例如： ``` make test_grafo make test_pqueue make test_hashmap ``` - 要清理编译和测试生成的二进制文件： ``` make clean ``` ## 执行参数 程序最多支持五个命令行参数： ``` ./ted -e [path] -f [arq.geo] -q [consulta.qry] -v [arqvias.via] -o [dir_saida] ``` | **参数** | **必填** | **描述** | |---------------|-----------------|--------------------------------------------------------------------------------| | `-e path` | 否 | 输入基础目录 (`BED`)。如果省略，则使用当前目录。 | | `-f arq.geo` | 是 | 包含城市描述的主文件。 | | `-v arq.via` | 否 | 用于构建交通 Graph 的道路文件。 | | `-q arq.qry` | 否 | 包含查询和命令的文件。 | | `-o path` | 是 | 输出基础目录 (`BSD`)，`.svg` 和 `.txt` 文件将保存在此。 | **执行自动化：** 您可以使用仓库中提供的 `(.sh)` 脚本一次性执行所有测试。 编译完成后，应执行以下命令： ``` chmod +x run.sh && ./run.sh ``` 这省去了逐个正确引用文件的麻烦。唯一的前提是 `testes` 文件夹必须存在于项目根目录下，并且包含所有 `(.geo), (.qry) e (.via)` 文件。 ## 代码结构（模块） * **`main`**: 程序入口，协调执行过程和参数。 * **`geo_handler`**: 读取 `.geo` 文件并初始化城市几何结构（街区）。 * **`via_handler`**: 读取 `.via` 文件并构建道路系统 Graph。 * **`qry_handler`**: 处理 `.qry` 中的查询（路径规划、扩展、bounding boxes）。 * **`svg_handler`**: 负责生成和格式化可视化 `.svg` 文件。 * **`grafo`**: 使用 adjacency list 实现有向 Graph。 * **`exhash`**: 可扩展 Hash 表，用于 CEP 的超快速索引和搜索。 * **`priority_queue`**: 针对 Dijkstra 算法优化的 Priority Queue (Min-Heap)。 * **`lista`**: 泛型动态 List，是 Hash 表和 Graph 顶点的基础。 * **`quadra`**: 城市街区数据的结构与处理。 * **`rua`**: 街道及其属性的表示（Graph 的边）。 * **`ponto`**: 用于地理坐标 (x, y) 的辅助结构。 * **`utils`**: 通用实用函数（字符串处理等）。

标签：交通流优化, 图算法, 地理信息系统, 客户端加密, 教学项目, 数据结构, 最短路径