基于C语言实现的人机交互软件

任务综述

在数据结构理论课的基础上，进复杂、功能全、有友好交互界的程序设计，分别完成算法实现题以及综合应题。

内容实现概述

使 C++ Qt 框架完成算法实现题中对相关图算法的图形演。

使声明式 UI 框架 SwiftUI 完成综合应题：地铁换乘系统。

算法实现设计说明

题目

• 邻接矩阵的式确定个图，完成：
• 建并显出它的邻接链表；
• 以递归和递归的式进深度优先遍历，显遍历结果，并随时显栈的出、情况；
• 对该图进度优先遍历，显遍历结果，并随时显队列的出、情况。

软件功能

软件功能分为两部分，交互与算法功能。交互体现了使该软件时能进的操作；算法功能则体现了该软件的实价值。交互采用

C++ Qt 框架，算法功能采 C++14，使量 C++ 特性。

用户交互

先，软件有灵活的界，画上的乎所有显的元素都可由户标拖动，使户根据需求改变画。

其次，该软件有菜单项供户操作，切操作都在菜单项中，没有更多多余的选项，使户乎不需要任何学习成本。

最后，菜单中有丰富的快捷键，使软件的操作简化。（放与缩的操作还能使 Ctrl/Command + 滚轮进，体验然。）

算法功能

该软件在功能实现上完成了题要求，实时显个有向图对应的邻接链表，并完成了深度（递归与递归）、度优先遍历的结果显，同时显结

果以及栈、队列信息。显过程中包含动画效果，对所显的图进实时渲染。

设计思想

该程序的设计体分为三个块。先是算法本的设计实现，包括题所有要求的内部算法实现，以及内部的数据结构，不包含任何图形界；其次是图形显的设计，它代表了图形显，不包含任何算法；最后是者的整

合，实现图形与内部数据结构的同步。该设计思路遵循了种设计模式

（Design Pattern）： MVC（Model View Controller）[1]。

Model

数据结构与算法模型采 C++ 编写，量使 C++ 特性如模板

（template），auto，范围 for 循环、C++11 引的智能指针，基本标准库数据结构如 std::vector，级标准库数据结构如 std::deque、 std::unordered_set。

图的定义，它是个顶点存放 Value 类型值的模板：

template<typename Value> struct Graph;

代码简单易懂、有详细注释，思路较为清晰，切 C++ 相关的知识均参

• 考《C++ Primer》[2] 以及官[3]。算法的设计参考《算法导论》[4]。整个模型分为两个件：
• Graph.h：图的数据结构，
• GraphAlgorithms.h：深度优先遍历等图算法。

图的数据结构中包含了所有的图操作，例如添加顶点等操作。图算法通过图操作返回遍历结果、栈或队列的每次更新后的结果，供视图显。结果类型为 SearchResult，是定义类型，能够表达所有视图所需要的信息：

struct SearchResult {
    // 记录了某种遍历时的下标顺序。
    std::vector<int> indexOrder;    // 记录了栈、队列的实时信息。
    std::vector<std::deque<int>> containerCondition;
};

通过下标顺序以及栈、队列的实时信息，返回给视图层进渲染就分容易。

View

视图层使 Qt 作为开发框架，主要运了 Qt 的 Graphics View

Framework[5]，该框架能够做到对组件的组合。程序中，图形显的思路就是组合。邻接表是由上到下关于每个顶点的链接显，这样就可以将整个视图作为许多个顶点的链的组合，达到了从到搭建视图的效果。

同样对于栈以及队列，可以看成许多个顶点的组合，并添加外框。

整个程序采组合思路的好处在于组件的重复利，该程序中的顶点在 4 个模块中达到复：图的显、邻接表的显、遍历结果、栈或队列的实时更新。如此来，的图形就可以拆分为个个的部分，降低思维与编写代码的负担。

Controller

控制器是协调视图和模型的枢纽，有了控制器即能达到视图与模型的分离和同步。它的主要任务有两点。先是使 Qt 中的类对模型进再封装，组织接提供给视图层显。其次是对模型与视图的同步，例如户选择清空顶点后，控制器要负责将视图层的顶点清除，同时将模型层的顶点清除。

void clearGraph() {
    if (isAnimating) {
        QMessageBox::warning(this, "操作失败", "请等待动画结束后操作");
        return;
    }
    model.reset();
    graphObject.reset();
    adjointListGraph.resetFromRaw({});
}

当户点击清空顶点时上述代码触发。代码中进了 3 处 reset，model.reset() 将模型中的顶点全部删除，

graphObject.reset() 将显图中的顶点删除，更新视图，最后代码则清空邻接表视图。如此达到模型与视图同步。

逻辑结构与物理结构

下将讨论 Model 中图模型的数据结构，关于 View 和 Controller 的结果表可参考源代码。

顶点

template<typename Value> struct Graph<Value>::Vertex {
private:
    friend struct Graph<Value>;
    Value value;
    // 邻接表，不会产生循环引用，用智能指针自动销毁，
    // `std::unordered_set<int>`代表顶点在图中所处的下标而非值    std::shared_ptr<std::unordered_set<int>> adjointList;
    // ...
}

每个顶点包含了它所需存储的值，这将它定义为模板类型Value。同时，由于整个图采了邻接矩阵的式来存储，每个顶点都会有衍出去的邻接表，在这将邻接表定义为指向序集合的智能指针。

智能指针的作是根据引计数动销毁堆中创建的变量[2]，避免内存泄漏。序集合采了散列存储的式使元素唯且插删除达到 O(1)。（可参考 cppreference 中对 std::unordered_set 的介绍[2]）该集合的作是存储所邻接顶点在图结构中顶点的下标。（见下）

图

/// Value should be hashable template<typename Value>
struct Graph {
private:
    // `Graph<Value>::Vertex`，定义在下方。
    struct Vertex;
    std::vector<Vertex> vertices;
    // 每个顶点值到其所在下标的映射。
    std::unordered_map<Value, int> valueToIndex;
    // ...
}

图是个模板类型，它可以任何类型 hashable 的顶点值来实例化。其中存储了两个部分。先是顶点的 vector[2]，是个顺序存储的线性表，可以动态插删除元素。其次是个序映射，它从给定的顶点值映射到它在 vector 中的下标，以优化直接通过值（下标）来对图进操作的情况（该应的操作全部基于下标）。

通过顶点形成的动态数组以及每个顶点链接出去的邻接表，个向图的数据结构可以完整表。

开发平台

概述

操作系统：macOS Mojave 10.14.6

编程语：C++14

开发框架：Qt 5.13.0

编译器：clang-1001.0.46.4

IDE：CLion 2019.2（Build with CMake) 运环境上述环境可以直接运可执件。若上述环境则或需重新编译整个项目，需要装有 Qt 环境以及持 C++14 且能够编译 Qt 库的编译器如 MinGW、Clang。系统的运结果分析说明开发具起初我使 Qt Creator 作为开发具，它的好处在于环境已配置，打开即可使，且整合了 Qt Designer 便制作界。然它的代码提以及界友好度都不如 Jetbrains 开发的 CLion。CLion 的代码提功能使我可以根据提目猜测代码功能，在开发过程中减少了阅读档的频率。

配置 CLion 也只需 CMake 代码连接 Qt 类库，分便。唯的不在于对外部具 Qt Designer 等的使会较为烦，但总体体验分良好。

调试

调试段有两种，种是通过设置断点查看变量信息，第种是通过 std::cout、qDebug 语句在 CLion 集成的控制台输出结果。

版本控制系统

本次开发中使了版本控制系统 Git[6] 来保存代码的历史记录。同时使代码托管平台 GitHub 将整个 Git 仓库存储到该络平台中，使代码“有迹可循”。

Git 的使有两，最传统的式是通过 Mac 带的 Terminal，同时CLion 也集成了 Git 和控制台可以便使。