「BUAA SE Pair Programming Work」软工结对编程博客

Part 1 前言

• 教学班级 ： 周四班

• 项目地址 ： https://github.com/Mmmusel/WordChain

• GUI项目地址 ： https://github.com/saltyfishyjk/WordChainGUI

Part 2 PSP预估耗时表格

PSP(Personal Software Process Stages)是一种结构化的软件开发过程，旨在帮助软件工程师更好地理解和改进自己的工作表现，通过对软件开发过程进行规范和跟踪，比较预测和实际的代码开发情况

Part 3 接口设计

版本一

3.1 Information Hiding（信息隐藏）

Information Hiding（信息隐藏）是指将程序中最有可能发生变化的设计决策隔离起来，从而保护其他部分免受修改的影响。

在我们的设计中，我们将Edge（边类）和Graph（图类）的内部属性和细节隐藏起来，通过get方法等约定接口暴露出必要的信息；我们将计算模块、运算模块、输出模块等进行封装，分别对外提供必要的函数接口，隐藏实现细节，以避免输入输出模块对计算模块内部细节的干扰或误操作等，方便后续在不影响程序功能的情况下修改和优化计算模块。

3.2 Interface Design（接口设计）

Interface Design（接口设计）是指定义程序中各个组件之间如何交互和通信的规范。接口设计应该清晰，简洁，一致和易于使用。

在我们的设计中，使用图形化界面（GUI）使得用户可以方便地进行文本框输入和文件输入并查看结果，同时提供了丰富的提示信息和错误处理机制来应对各种可能的情况，提高用户的体验；同时，我们将关联性强的函数等放在一起，并使之接口约束规范清晰，方便通信和理解。

3.3 Loose Coupling（松耦合）

Loose Coupling（松耦合）是指程序中各个组件之间的关联程度很低，也就是说改变一个组件对另一个组件的影响很小。松耦合可以提高程序的可维护性和可扩展性。

在我们的设计中，我们事先通过清晰的接口约束规定了输入模块、运算模块、输出模块等之间的交互，实现了松耦合，这样使得两个模块之间更加独立和灵活，同时方便我们进行单元测试或在遵守接口约束的前提下更换其中的某个模块而不影响其他的模块。同时，便于后期和其他队伍交换模块。

Part 4 计算模块接口的设计与实现

4.0 存储与类的设计

4.0.1 单词

• 使用string来保存单词

4.0.2 结点

• 使用整数0-25分别表示26个英文字母作为图的结点

4.0.3 Edge边类

• 一个Edge对象表示一个单词

• int start, end：单词的首、尾字母结点

• int weight：边的权重
• string word：边代表的单词

4.0.4 Graph图类

• int pointNum：图中点的数量
• int inDegree[]：图中点的入度
• vector <Edge*> edges[][]：邻接矩阵，其中edges[i][j]为一个vector<Edge*>，记录从点i到点j的边的集合
• vector <Edge*> selfEdge[], edgesIn[], edgesOut[]：分别表示每个点的自环边集合、入边集合和出边集合

4.1 接口说明

4.1.1 CORE模块接口参数说明

1
2
3

int gen_chains_all(char* words[], int len, char* result[]);
int gen_chain_char(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);
int gen_chain_word(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);

为了使CORE模块便于与其他小组进行模块互换，我们按照课程组接口针对计算CORE模块封装以上三个接口，

• char* words[]和len为从输入文本中提取出的单词数组
• char* result[]为计算模块返回的输出文本，对于-w和-c指令计算最长单词链时result[]为单词链的单词数组，对于-n指令计算单词链总数时result[]为单词链数组。
• char head, tail, reject 为 -h, -t, -j指令的约束字母，约定的规范输入为大小写字母代表存在对应指令的约束字母，当不存在此类指令的约束字母时传入0即为NULL。传入其他符号时按照传入参数异常处理。
• bool enable_loop 对应是否使用-r指令允许输入文本成环。

4.1.2 CORE模块接口实现

• 在第一阶段开发过程中，我们将计算单词链的功能分为五种：-n, -w, -w -r, -c, -c -r , 每种计算模式对应一个计算函数。在API接口函数中，只需要根据传入的bool enable_loop 参数实现分发功能即可。

• 第二阶段封装过程遇到的主要问题：第一阶段编码时对于计算功能函数有注意提前独立成子模块，在封装时对于第一阶段计算模块的改动较小。但前期对于封装没有考虑全面的地方主要在input部分，第一阶段在input阶段就实现了去除-j单词包括建图等功能，导致输入模块和计算模块产生了一定程度的耦合，在封装时对于input部分的改动较大。

• 在第三阶段异常机制实现时，对于封装的主要改动是将原本的一种异常类拆分成了coreException和inputException。coreException属于CORE计算模块抛出的异常，包括成环及无解的情况；inputException属于命令行程序解析输入命令及文件时抛出的异常，包括命令格式错误及输入非法等更多异常情况。

4.2 流程图与函数

首先介绍设计和实现思路：

• 首先设计和实现基本需求1：计算单词文本中可以构成多少个单词链（-n），该参数对应的正确情况一定不存在环，且和后续对“最长”的需求有所差别，并且不能与其他参数共同使用，故单独设计函数与接口实现流程。
• 然后分析和设计基本需求4：指定单词链开头或结尾字母（-h-t）和基本需求5：指定单词链中所有单词均不允许出现的首字母（-j），这些参数对其他两个功能型参数（-w-c）都有整体影响，作为参数传入-w-c的函数实现中，在建图前或动态规划前后对输入或输出进行filter实现此类参数功能。
• 然后分析和设计基本需求6：允许单词文本隐含单词环（-r），这一参数会较大影响其他两个功能型参数（-w-c）的设计思路。所以将-w、-c与是否使用-r两两组合成四种计算函数来实现。
• 然后分别分析基本需求2：计算最多单词数量的单词链（-w）和基本需求3：计算字母最多的单词链（-c），这两个需求整体框架是相似的，仅在是否带边权计算和部分细节有所区别。

4.2.1 基本需求1：计算单词文本中可以构成多少个单词链（-n）

首先建图后判断是否成环，首先判断每个字母的自环是否会形成单词环，然后对于不存在自环单词环的图进行拓扑排序，即可通过拓扑结果判断是否存在环路。

由于题目要求输出包含嵌套单词链的所有单词链，所以选择从每个起点进行dfs遍历过程中输出所有单词链。

4.2.2 基本需求4：指定单词链开头或结尾字母（-h-t）和基本需求5：指定单词链中所有单词均不允许出现的首字母（-j）

在建图前或动态规划前后对输入或输出进行filter实现此类参数功能。

-j只需要在建图时过滤掉以-j指定忽略的字母开头的单词即可。需要注意的细节是当不包含-r参数时，需要先对原图进行环路判断之后，再进行-j的过滤。

-h相当于指定动态规划的起点。对于不存在-h的情况，所有字母均可以作为起点，所以动态规划开始前将所有起点按其是否包含自环或者自环字母数初始化即可。对于-h指定起点时，只对起点初始化，其余点的初始值设为-1。然后依据拓扑排序的顺序依次进行动态规划，跳过dp值小于0的点即可。

-t指定单词链终点。动态规划的状态设计dp[i]为以字母i结尾的最长链长，所以不包含-t时动态规划结束后比较最大dp值为最长链长；使用-t指定单词链结尾字母end时只需要在动态规划结束后找到dp[end]作为最长链长，如果dp[end]<1为不存在合法单词链。

4.2.3 基本需求6：允许单词文本隐含单词环（-r）

对于不包含-r参数时，先建图并判断是否包含自环形成的环路，再做拓扑排序判断是否成环。如果成环抛出CoreException。

对于包含-r参数时计算最长链长的算法如下：

• 首先去除环路：首先使用tarjan算法求解强连通分量，然后对每个强连通分类建子图。再将每个代表强连通分量的子图视为一个节点，建立去除强连通分量后的有向无环图。遍历原图的每一条边， 依据起点和终点是否在一个强连通分量内，将边划分入强连通分量子图或者有向无环图。
• 然后在每个强连通分量子图中使用dfs计算图内节点两两之间包括自环的最大链长，记为sccInnerDp[i][j]。
• 然后对去除强连通分量后的DAG图再做拓扑排序得到动态规划的顺序。
• 动态规划更新到每个强连通分量时，由DAG图当前动态规划更新的所有前序节点dp值sccOuterDp[i]和子图内内节点两两之间的最长链长sccInnerDp[i][j]更新强连通分量子图内所有点作为节点的新dp值： dp[j]=sccOuterDp[i]+sccInnerDp[i][j]。遍历结束后将sccOuterDp[i]更新为dp[i]。
• 最后再遍历DAG图中所有起点为此强连通分量内部节点的桥边，结合权值更新终点的sccOuterDp[end]值。
• 最后获得最长链长的终点，再根据动态规划过程中记录的前向节点倒序遍历输出最长链。输出时需要输出自环边，以及需要使用dfs遍历输出强连通分量内部两个节点间的所有边。

4.2.4 基本需求2：计算最多单词数量的单词链（-w）

对于不包含-r的情况，由拓扑排序排除成环情况后得到拓扑序，按传入的-h参数设定动态规划初始值为0(-h未指定首字母且此字母无自环)或1(-h未指定首字母且此字母有自环)或-1(不是-h指定的首字母)拓扑序进行动态规划，记录以当前字母为终点时的最大链长与前向节点。

结合-t的指定终点字母的情况与所有字母的dp值，确定符合约束条件下的最长链的终点，然后逆序获得单词链中所有单词，遍历过程中遇到自环需要输出自环。

对于包含-r的情况，对于环路的具体动态规划思路与方程可见4.2.3 -r的算法描述部分。大体思路为使用tarjan算法计算强连通分量，为所有强连通分量建立子图，然后将强连通分量视为一个节点分别建立无环DAG图，分别将强连通分量内部边与连接两个强连通分量的桥边分别划入强连通分量子图或去环后的DAG图。然后在强连通分量子图进行dfs计算图内节点两两之间的最大链长。然后对DAG图进行拓扑排序，按拓扑序依次更新DAG图内此强连通分量的所有节点的dp值。然后再更新此强连通分量的所有节点与其他强连通分量的连接桥边的后继节点的dp值。最后结合-t的指定终点字母的情况与所有字母的dp值，确定符合约束条件下的最长链的终点，然后逆序获得组成此单词链中所有单词，需要对强连通分量内部进行带长dfs以输出强连通分量内部组成的最长单词链。遍历过程中遇到自环需要输出自环。

4.2.5 基本需求3：计算字母最多的单词链（-c）

-c与-w的处理流程基本相同。以下仅说明-c相较-w的区别：

首先在计算最大链长时，对于一个单词（一条边）-w处理时简单+1即可，意味着对于首位相同的单词任选其一即可。对于-c处理时对于首位相同的单词还需要考虑优先选择更长单词长度的单词纳入计算并打印输出。-w处理自环时只需要计入自环条数即可，-c处理自环时需要计入所有自环的字母数之和。

其次-w只需要在动态规划结束后判断链长>=2即可满足单词链的定义。但是由于-c在动态规划过程中的状态量为字母数，因此如果与-w完全一致的处理会出现动态规划最大值可能只有一个单词不符合单词链定义的情况。所以为了处理的简便，对于-c处理时在建图时删除所有孤立边（单词首尾均不存在自环且起点入度为0终点出度为0的单词），即可避免发生-c动态规划时结果不符合单词链长度>=2的定义约束。

4.3 关键算法与独到之处

4.3.1 Tarjan算法计算强连通分量

我们选择tarjan算法将计算带环图的强连通分量优化到O(n)时间复杂度。

Tarjan算法是一种用于求解有向图中强连通分量的算法，它使用深度优先搜索（DFS）来遍历图，并使用一个栈来记录每个顶点的搜索顺序。当一个顶点被发现并加入栈中时，Tarjan算法会尝试找到一个强连通分量，它会在遍历过程中将强连通分量中的所有顶点都从栈中移除。

Tarjan算法的优点是可以在线性时间内求出有向图的所有强连通分量，而且不需要额外的空间。Tarjan算法的简要思路如下：

1. 对每个未访问过的顶点u，执行DFS，并给u赋予一个编号dfn[u]和一个最小能回溯到的编号low[u]，初始时都等于u的访问次序。
2. 在DFS过程中，每访问到一个顶点u，就把它压入栈中，并继续访问它的邻接顶点v。
3. 如果v已经在栈中，说明v和u在同一个强连通分量中，则更新low[u]=min(low[u],dfn[v])。
4. 如果v未被访问过，则递归地对v进行DFS，并更新low[u]=min(low[u],low[v])。
5. 如果low[u]==dfn[u]，说明u是当前强连通分量的根节点，则依次从栈中弹出该强连通分量中的所有顶点，并标记为已访问。
6. 重复以上步骤直到所有顶点都被访问过。

使用tarjan算法$O(n)$时间复杂度计算强连通分量后，为所有强连通分量建立子图，然后将强连通分量视为一个节点分别建立无环DAG图，分别将强连通分量内部边与连接两个强连通分量的桥边分别划入强连通分量子图或去环后的DAG图。

4.3.2 -c提前去除孤立边

由于-c在动态规划过程中的状态量为字母数，因此如果不做任何处理时动态规划最大值可能只有一个单词不符合单词链定义的情况。所以为了处理的简便，对于-c处理时在建图时删除所有孤立边（单词首尾均不存在自环且起点入度为0终点出度为0的单词），即可避免发生-c动态规划时结果不符合单词链长度>=2的定义约束。

4.3.3 强连通分量的动态规划

对于包含强连通分量的动态规划，首先需要依据去除环路后DAG图的拓扑顺序，然后还需要将动态规划过程细化到每个强连通分量内部的所有节点。所以将动态规划过程分为两个阶段，首先是第一阶段借助子图内内节点两两之间的最长链长sccInnerDp[i][j]更新强连通分量子图内所有点的sccOuterDp[j]。然后第二阶段再遍历DAG图中所有起点为此强连通分量内部节点的桥边，结合权值更新连通分量外桥边终点的sccOuterDp[end]值。因此我们需要在动态规划前计算好强连通分量子图内内节点两两之间的最长链长sccInnerDp[i][j]。

4.3.4 强连通分量内dfs使用贪心算法求解最长路径

在每个强连通分量子图中使用dfs计算图内节点两两之间包括自环的最大链长时，这一部分的时间复杂度较高，我们在优化性能时采用了贪心算法进行剪枝优化，将dfs过程中对边的遍历改为对出度点的遍历。-w时对每个不同的出度点只需要选择任意一条边即可，优化掉首位相同的其他单词的遍历，dfs实现了剪枝。-c时也可以使用贪心算法，预先对相同出度点的边做按单词长度的排序，每次优先选最长的边作为本层dfs时标记的边进行下一层搜索即可，回溯时只对不同出度点进行回溯，不再进行相同出度点的其他边的深搜，也实现了和-w一样的剪枝优化。

Part 5 编译器编译通过无警告

Part 6 UML图

存储类包括 Edge边类和 Graph图类。 Edge边类和 Graph图类是聚合关系，图由边组成。计算功能封装在API接口中，可以分为CountChains, charCountMax, wordCountMax三个功能实现模块，与图类是依赖关系，计算接口会访问图类（被依赖类）中的一些public方法来获取特定信息。

Part 7 计算模块接口部分的性能改进

7.1 性能改进花费的时间

起初的计算强连通分量与求解强连通分量内部的算法性能较差，我们在第一阶段大概花费半天时间在性能改进上，主要工作包括查找性能较差的函数与分析原因、学习时间复杂度更低的算法、优化算法并进行迭代开发、回归测试。

7.2 程序中消耗最大的函数

我们使用VS插件对程序进行分析，发现关于带环图计算强连通分量、强连通分量内部dfs寻找最长路径部分的时间复杂度最高。

7.3 算法分析与改进

在计算强连通分量时，我们选择tarjan算法实现O(V+E)的时间复杂度。

在每个强连通分量子图中使用dfs计算图内节点两两之间包括自环的最大链长时，优化前的算法对边遍历，后来优化的时候发现存在可以剪枝的dfs过程，即改为对点的遍历。在每个强连通分量子图中使用dfs计算图内节点两两之间包括自环的最大链长时，这一部分的时间复杂度较高，我们在优化性能时采用了贪心算法进行剪枝优化，将dfs过程中对边的遍历改为对出度点的遍历。-w时对每个不同的出度点只需要选择任意一条边即可，优化掉首位相同的其他单词的遍历，dfs实现了剪枝。-c时也可以使用贪心算法，预先对相同出度点的边做按单词长度的排序，每次优先选最长的边作为本层dfs时标记的边进行下一层搜索即可，回溯时只对不同出度点进行回溯，不再进行相同出度点的其他边的深搜，也实现了和-w一样的剪枝优化。

Part 8 Design by Contract与Code Contract

8.1 Design by Contract (DbC)

• Design by Contract (DbC) 或契约式设计是一种设计软件的方法，它要求软件设计者为软件组件定义正式、精确和可验证的接口规范，这些规范扩展了抽象数据类型的普通定义，增加了前置条件、后置条件和不变量。
• 优点：获得更加优秀的设计，不会盲目、更清楚、更简单，更容易阅读、理解、找错，减少犯错，可靠性更高。
• 缺点：对于程序语言有一定的要求，契约式编程需要一种机制来表达和检查契约。

8.2 Code Contract

• Code Contract 或代码契约是一种实现 DbC 的工具。
• 优点：提高了软件工程的效率和质量，保证了调用者和被调用者之间的协作和责任分明3。支持编译时或运行时的契约检查，可以发现潜在的错误或异常。
• 缺点：增加了代码的复杂度和冗余，可能影响性能和可读性。需要花费额外的时间和精力来编写和维护契约。

8.3 在结对作业中的应用

• 在设计阶段确定好各个模块和函数的接口规范，如Edge和Graph类，各种对外服务的函数的输入输出、前置条件、后置条件、不变量和一致性等。
• 在编码阶段使用Code Contract工具（如.Net框架）来具体实现上述接口规范，并进行单元测试来验证契约是否被满足。
• 在代码评审和审阅阶段检查代码是否符合接口规范，并及时修改代码或完善契约。

Part 9 计算模块部分单元测试

我们使用Visual Studio中的单元测试框架对项目进行测试，并使用OpenCppCoverage扩展插件进行分支覆盖率的分析。

9.1 单元测试代码

我们的单元测试主要分为以下五类共47个测试点：

9.1.1 针对CORE计算核心API接口的测试

输入单词数组char* words[]，在测试代码里给出答案数组char* ans[]，通过调用接口gen_chain_char()获取程序输出char *result[]，然后使用单元测试框架下的Assert::AreEqual函数进行比对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

TEST_METHOD(example_c_r_1) {
    char* words[] = { "append", "deny", "yahoo", "oops", "strange", "eat", "tuna", "banana", "pig", "graph", "news", "silence"};
    char* ans[] = {"news", "silence", "eat", "tuna", "append", "deny", "yahoo", "oops", "strange"};
    test_arg_c(words, 12, ans, 9, 0, 0, 0, true);
}

void test_arg_c(char* words[], int len, char* ans[], int ans_len, char head, char tail, char reject, bool enable_loop) {
    char** result = (char**)malloc(10000);
    int out_len = gen_chain_char(words, len, result, head, tail, reject, enable_loop);
    Assert::AreEqual(ans_len, out_len);
    for (int i = 0; i < ans_len; i++) {
        if (result != nullptr) Assert::AreEqual(strcmp(ans[i], result[i]), 0);
    }
}

9.1.2 针对面向Vuetify-GUI的API接口的测试

1
2
3
4
5
6
7
8
9
10

TEST_METHOD(example_api_2) {
    const char* input = "de,ef,eff";
    char* ans = "de\neff\n";
    test_vuetify_api(input, ans, 1, 0, 0, 0, false);
}

void test_vuetify_api(const char* input, char* ans, int type, char head, char tail, char reject, bool weighted) {
    const char* result = vuetifyAPI(input, type, head, tail, reject, weighted);
    Assert::AreEqual(strcmp(ans, result), 0);
}

9.1.3 针对命令行程序命令解析模块与文件读入模块的测试

1
2
3
4
5

TEST_METHOD(example_main_5) {
    char* args[] = { "", "-w", "D:\PROJECTS\WordChain\input.txt" };
    int ret = parseCmd(3, args);
    Assert::AreEqual(0, ret);
}

9.1.4 InPutException异常测试：针对命令行程序命令解析模块与文件读入模块

在测试代码中使用``try {} catch {}并比对异常信息。

1
2
3
4
5
6
7
8
9
10
11

TEST_METHOD(exception_7_undefined_cmd) {
    try {
        char* args[] = { "WordChain.exe", "-q", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(3, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: undefined cmd.", e.GetInfo().data()));
        return;
    }
    Assert::Fail();
}

9.1.5 CoreException异常测试：针对计算模块

1
2
3
4
5
6
7
8
9
10
11

TEST_METHOD(core_exception_2_no_solution) {
    try {
        char* words[] = { "ab", "cd", "ef" };
        char* ans[] = { "" };
        test_arg_w(words, 3, ans, 0, 0, 0, 0, false);
    }
    catch (CoreException const& e) {
        Assert::AreEqual(0, strcmp("CoreError: No Chain", e.GetInfo().data()));
        return;
    }
}

9.2 单元测试函数

结合9.1部分展示的几类单元测试代码，我们主要测试了以下几类函数：

9.2.1 CORE计算核心API

1
2
3

int gen_chains_all(char* words[], int len, char* result[]);
int gen_chain_char(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);
int gen_chain_word(char* words[], int len, char* result[], char head, char tail, char reject, bool enable_loop);

9.2.2 面向Vuetify-GUI的API

1

const char* vuetifyAPI(const char* input, int type, char head, char tail, char reject, bool weighted) ;

9.2.3 命令行程序的命令解析、输入模块

1
2
3

int parseCmd(int argc, char *argv[]);
int splitWord(char *words[],const char *fileName, int reject);
void checkBuf(string& wordBuf);

9.3 构造测试数据的思路

• 分支覆盖率：首先最基本的是通过OpenCppCoverage插件查看单元测试中未覆盖全面的语句，保证单元测试的基本样例可以覆盖所有分支。这部分主要针对的是计算模块以外的部分，包括命令行程序的命令解析、输入模块测试、接口的函数分发、多种异常是否完全覆盖等。

• 针对计算模块的功能正确性测试：这部分测试主要考虑：

  • 指令间的叠加组合，主要是-c -w与-r -h -t -j之间的多种组合
  • 输入图无自环、自环数量为1、自环数量>1、头部自环、尾部自环
  • 输入图为DAG图、没有复杂强连通分量的简单环路、包含一个复杂强连通分量、多个复杂强连通分量由桥边链接
  • 相同输入在-c和-w得到不同输出

• 压力测试：完全图、两节点间存在多条不同边等

• 鲁棒性测试：空文件、不存在的文件、参数非法等
• 边界数据测试：单字母单词、重复单词、全部为自环、全部为孤立边等

9.4 测试覆盖率

Part 10 计算模块部分异常处理说明

我们一共实现了14种输入模块异常InPutException，主要包括命令解析和文件读入出现的问题。

计算模块一共实现3种异常CoreException ，主要包括输入单词成环、没有符合约束的单词链、输入参数非法。

异常的设计目标和对应场景跟在下述每个测试点前用注释的形式说明。

10.1 输入模块异常InPutException 共14种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

//InPutException 1：输入字符串格式非法，不能被解析为已知命令
TEST_METHOD(exception_1_cmd_format_error) {
    try {
        char* args[] = { "WordChain.exe", "-", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(3, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: cmd format error", e.GetInfo().data()));
        return;
    }
}

//InPutException 2：-n -w -c 不能重复使用
TEST_METHOD(exception_2_too_many_cmd) {
    try {
        char* args[] = { "WordChain.exe", "-w", "-c", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(4, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: to many cmd. -n -w -c can only choose one and use once", e.GetInfo().data()));
        return;
    }
}

//InPutException 3：-h -t -j 后只能输入单个英文字符
TEST_METHOD(exception_3_missing_char) {
    try {
        char* args[] = { "WordChain.exe", "-j", "ttt", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(4, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: -j must followed by one char", e.GetInfo().data()));
        return;
    }
}

//InPutException 4：-h/-t/-j 最多使用一次
TEST_METHOD(exception_4_redeclaration) {
    try {
        char* args[] = { "WordChain.exe", "-w", "-h", "c", "-h", "c", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(7, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp( "Cmd Input Error: redeclaration of-h\0", e.GetInfo().data()));
        return;
    }
}

//InPutException 5：-h -t -j 后只能输入英文字符
TEST_METHOD(exception_5_error_char) {
    try {
        char* args[] = { "WordChain.exe", "-j", ".", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(4, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: -j must followed by a char", e.GetInfo().data()));
        return;
    }
}

//InPutException 6：-h -t -j 后必须输入一个英文字符
TEST_METHOD(exception_6_missing_char) {
    try {
        char* args[] = { "WordChain.exe", "-w", "-j", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(4, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: -j must followed by one char", e.GetInfo().data()));
        return;
    }
}

//InPutException 7：未定义的命令参数
TEST_METHOD(exception_7_undefined_cmd) {
    try {
        char* args[] = { "WordChain.exe", "-q", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(3, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: undefined cmd.", e.GetInfo().data()));
        return;
    }
}

//InPutException 8：输入文件不是txt
TEST_METHOD(exception_8_txt) {
    try {
        char* args[] = { "WordChain.exe", "-n", "D:\PROJECTS\WordChain\input" };
        parseCmd(3, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("File Input Error: filename must be *.txt", e.GetInfo().data()));
        return;
    }
}

//InPutException 9：命令字符串格式错误，遗漏'-'
TEST_METHOD(exception_9_cmd_format_error) {
    try {
        char* args[] = { "WordChain.exe", "n", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(3, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: cmd format error", e.GetInfo().data()));
        return;
    }
}

//InPutException 10：没有输入文件
TEST_METHOD(exception_10_missing_input_file) {
    try {
        char* args[] = { "WordChain.exe", "-n" };
        parseCmd(2, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("File Input Error: please enter a filename", e.GetInfo().data()));
        return;
    }
}

//InPutException 11：输入多个文件
TEST_METHOD(exception_11_too_many_files) {
    try {
        char* args[] = { "WordChain.exe", "-n", "D:\PROJECTS\WordChain\input.txt","D:\PROJECTS\WordChain\input.txt" };
        parseCmd(4, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("File Input Error: you can only input one file", e.GetInfo().data()));
        return;
    }
}

//InPutException 12：-n和-r使用
TEST_METHOD(exception_12_cmd_format_error) {
    try {
        char* args[] = { "WordChain.exe", "-n", "-r", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(4, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: -n should use seperately without -r", e.GetInfo().data()));
        return;
    }
}

//InPutException 13：-n和-h/-t/-j使用
TEST_METHOD(exception_13_cmd_format_error) {
    try {
        char* args[] = { "WordChain.exe", "-n", "-h", "a", "D:\PROJECTS\WordChain\input.txt" };
        parseCmd(5, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("Cmd Input Error: -n should use seperately without -h -t -j", e.GetInfo().data()));
        return;
    }
}

//InPutException 14：输入文件路径不存在
TEST_METHOD(exception_14_file_not_exist) {
    try {
        char* args[] = { "WordChain.exe", "-n", "D:\PROJECTS\WordChain\input_not_exist.txt"};
        parseCmd(3, args);
    }
    catch (InPutException const& e) {
        Assert::AreEqual(0, strcmp("File Input Error: file not exist", e.GetInfo().data()));
        return;
    }
}

10.2 计算模块异常CoreException 共3种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

//CoreException 1：-h/-t/-j必须是英文字符
TEST_METHOD(core_exception_1_input_char_error) {
    try {
        char* words[] = { "ab", "bc", "cd" };
        char* ans[] = { "" };
        test_arg_w(words, 3, ans, 0, '4', 0, 0, false);
    }
    catch (CoreException const& e) {
        Assert::AreEqual(0, strcmp("CoreError: -h -j -t must be a char", e.GetInfo().data()));
        return;
    }
}

//CoreException 2：没有合法单词链
TEST_METHOD(core_exception_2_no_solution) {
    try {
        char* words[] = { "ab", "cd", "ef"};
        char* ans[] = { "" };
        test_arg_w(words, 3, ans, 0, 0, 0, 0, false);
    }
    catch (CoreException const& e) {
        Assert::AreEqual(0, strcmp("CoreError: No Chain", e.GetInfo().data()));
        return;
    }
}

//CoreException 3：未指定-r时或-n时输入单词存在环路
TEST_METHOD(core_exception_3_loop) {
    try {
        char* words[] = { "ab", "bb", "bcb" };
        char* ans[] = { "" };
        test_arg_w(words, 3, ans, 0, 0, 0, 0, false);
    }
    catch (CoreException const& e) {
        Assert::AreEqual(0, strcmp("CoreError: LOOP!", e.GetInfo().data()));
        return;
    }
}

Part 11 界面模块的详细设计

11.1 技术栈介绍

我们搭建的GUI应用使用了包括如下技术：

• Vuetify 2.6.0
• Vue 2.6.14
• Electron 13.0.0
• node-ffi-napi 4.0.3
• Lodash 4.0.0
• Moment.js 2.29.2

打包所用的插件是 vue-cli-plugin-electron-builder，其使用的打包引擎是 electron-builder。

11.2 设计风格

使用Vuetify提供的Material Design风格界面，效果类似于OO课程网站。

具体地，左上板块为参数说明板块，左下板块为控制板块，右上板块为输入板块，右下板块为输出板块。

11.3 界面构建

我们使用基于Vue编写的Material Design框架Vuetify提供的组件进行搭建，以下说明具体实现方法。

11.3.1 参数说明板块（左上）

我们使用Vuetify的v-card卡片组件和v-tabs选项卡组件来在固定区域展示各参数的含义和详细介绍信息，包括n,w,c,h,t,j,r七个参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

<template>
  <v-card>
    <v-tabs v-model="tab" background-color="primary" dark show-arrows>
      <v-tab v-for="item in items" :key="item.tab">
        {{ item.tab }}
      </v-tab>
    </v-tabs>
    <v-tabs-items v-model="tab">
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">计算单词文本中可以构成多少个单词链（能够构成所有单词链的数目）</v-card-title>
          <v-card-text>
            <p>
              -n参数统计该单词文本中共有多少条单词链，包含嵌套单词链
            </p>
            <p>
              参数-n不要求和其他参数联合使用
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">计算最多单词数量的单词链</v-card-title>
          <v-card-text>
            <p>
              -w参数加文件名的形式计算最多单词数量的英语单词链
            </p>
            <p>
              需要保证单词的输出顺序满足其单词链顺序，即首尾相连
            </p>
            <p>
              假如可能有多组最长的相连英语单词串，选取其中任意一组作为结果即可
            </p>
            <p>
              参数-w与-n -c 等功能性参数不兼容
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">计算字母最多的单词链</v-card-title>
          <v-card-text>
            <p>
              -c参数计算字母最多的英语单词链
            </p>
            <p>
              需要保证单词的输出顺序满足其单词链顺序，即首尾相连
            </p>
            <p>
              假如可能有多组字母数最多的单词链，选取其中任意一组作为结果即可
            </p>
            <p>
              参数-c与-n -w这一类功能型参数不兼容，同时出现属于异常
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">指定单词链开头字母</v-card-title>
          <v-card-text>
            <p>
              -c参数指定单词链的首字母
            </p>
            <p>
              参数-h属于附加型参数，单独出现属于异常
            </p>
            <p>
              假参数-h与-t兼容，允许复合使用，此时需要同时满足首字母和尾字母条件
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">指定单词链开头字母</v-card-title>
          <v-card-text>
            <p>
              -h参数指定单词链的首字母
            </p>
            <p>
              参数-h属于附加型参数，单独出现属于异常
            </p>
            <p>
              参数-h与-t兼容，允许复合使用，此时需要同时满足首字母和尾字母条件
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">指定单词链结尾字母</v-card-title>
          <v-card-text>
            <p>
              -t参数指定单词链的尾字母
            </p>
            <p>
              参数-t属于附加型参数，单独出现属于异常
            </p>
            <p>
              参数-h与-t兼容，允许复合使用，此时需要同时满足首字母和尾字母条件
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">指定单词链中所有单词均不允许出现的首字母</v-card-title>
          <v-card-text>
            <p>
              -j参数指定不允许出现的首字母
            </p>
            <p>
              参数-j属于附加型参数，单独出现属于异常
            </p>
            <p>
              参数-j与参数-h -t兼容，若-h与-j指定字母一致则以“不存在符合条件的单词链”处理
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
      <v-tab-item>
        <v-card flat>
          <v-card-title class="headline">允许单词文本隐含单词环</v-card-title>
          <v-card-text>
            <p>
              -r参数表示允许单词文本隐含单词环
            </p>
            <p>
              参数-r属于附加型参数，单独出现属于异常
            </p>
            <p>
              参数-r与参数-h及-t兼容，允许复合使用，此时需要同时满足首字母和尾字母条件
            </p>
            <p>
              特别指出，-r参数可能与-j参数复合使用，同时可能存在-h以及-t参数。这四个参数作为附加型参数，若出现逻辑上的冲突，以“不存在符合条件的单词链”处理。
            </p>
          </v-card-text>
        </v-card>
      </v-tab-item>
    </v-tabs-items>
  </v-card>
</v-card>
</template>

效果（以n,w参数为例）：

11.3.2 控制板块（左下）

我们使用Vuetify的v-card卡片组件和v-list列表组件来支持切换不同功能性参数（n,w,c），并通过右列给出功能性参数允许的附加型参数（h,t,r,j）。

template如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

<template>
  <v-card class="elevation-6 overflow-y-auto" style="height: 100%">
    <v-container fluid class="fill-height py-0">
      <v-row class="align-center justify-center" style="height: 100%">
        <v-col class="pa-0" cols="4" style="height: 100%">
          <v-list dark class="rounded-l pa-0 primary" style="height: 100%">
            <v-list-item-group mandatory active-class="indicator" v-model="selectedMode" style="height: 100%">
              <v-list-item v-for="(item, i) in modes" :key="i" style="height: 33%">
                <v-list-item-content>
                  <v-list-item-title class="text-center">
                    {{ item }}
                  </v-list-item-title>
                </v-list-item-content>
              </v-list-item>
            </v-list-item-group>
          </v-list>
        </v-col>
        <v-col cols="8" style="height: 100%; display: flex" class="justify-center">
          <v-card-title v-if="noAvailableOptions" class="justify-center text--secondary">
            无可用选项： <br />
            -n参数不能和其他参数一起使用
          </v-card-title>
          <v-col v-if="!noAvailableOptions" style="height: 100%" class="mode-options py-0 px-2">

            <v-text-field label="首字母限制 -h" class="my-0" v-model="head" :rules="[rules.singleLetter]" />
            <v-text-field label="尾字母限制 -t" class="my-0" v-model="tail" :rules="[rules.singleLetter]" />
            <v-text-field label="不允许出现的首字母 -j" class="my-0" v-model="reject" :rules="[rules.singleLetter]" />
            <v-checkbox label="允许单词环 -r" class="mt-0" v-model="allowRing"></v-checkbox>

          </v-col>
        </v-col>
      </v-row>
    </v-container>
  </v-card>
</template>

效果：

11.3.3 输入板块（右上）

我们使用v-btn按钮组件和v-card-text卡片输入框组件来组合实现文本输入部分，支持直接输入单词、从本地选择并导入文本文件、清空文本输入框以及求解四个功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

<template>
  <v-card class="elevation-6" style="height: 100%; display: flex; flex-direction: column">

    <v-toolbar class="elevation-0 py-1" style="flex-grow: 0">
      <v-btn dark class="primary" @click="importText"> 导入文本文件 <v-icon right light> mdi-file-import </v-icon>
      </v-btn>
      <v-spacer />
      <v-btn dark class="primary" @click="clearInputText"> 清空 <v-icon right light> mdi-cached </v-icon>
      </v-btn>
      <v-spacer />
      <v-btn class="primary" @click="solve" :loading="calculating" :dark="!calculating" :disabled="calculating">
        求解
        <v-icon right light> mdi-send </v-icon>
      </v-btn>
    </v-toolbar>

    <v-card-text style="flex-grow: 1" class="pt-3">
      <v-textarea filled no-resize height="86%" placeholder="在此处输入单词文本" style="height: 100%" v-model="inputText" />
    </v-card-text>
  </v-card>
</template>

效果：

11.3.4 输出板块（右下）

我们使用v-btn按钮组件、v-card-text文本框组件和v-chip纸片组件来完成输出板块，支持将输出导出为文本文件，清空输出框以及展示计算用时的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

<template>
  <v-card class="elevation-6" style="height: 100%; display: flex; flex-direction: column">

    <v-toolbar class="elevation-0 py-1" style="flex-grow: 0">
      <v-btn dark class="primary" @click="importText"> 导入文本文件 <v-icon right light> mdi-file-import </v-icon>
      </v-btn>
      <v-spacer />
      <v-btn dark class="primary" @click="clearInputText"> 清空 <v-icon right light> mdi-cached </v-icon>
      </v-btn>
      <v-spacer />
      <v-btn class="primary" @click="solve" :loading="calculating" :dark="!calculating" :disabled="calculating">
        求解
        <v-icon right light> mdi-send </v-icon>
      </v-btn>
    </v-toolbar>

    <v-card-text style="flex-grow: 1" class="pt-3">
      <v-textarea filled no-resize height="86%" placeholder="在此处输入单词文本" style="height: 100%" v-model="inputText" />
    </v-card-text>
  </v-card>
</template>

效果：

11.4 异常处理

为了增强软件的鲁棒性，提高用户体验，我们在GUI部分设计了许多可以直接判断的特殊情况并给出反馈。

11.4.1 h,t,j参数输入异常

• 首先，在左上角的说明板块中明确说明h,t,j须为单个的英文字符（大小写均可）

• 在左下角的控制板块中，当输入框中检测到了长度大于1的字符串或非英文字符时，给出反馈，如下图：

  

  

• 如果用户不理睬控制板块输入框的错误提示并执意点击”求解“按钮，则直接进行错误反馈：

  

11.4.2 单词环异常处理

当没有勾选-r且输入隐含单词环时，会给出错误提示，且不进行计算：

11.4.3 无解

当在用户给定的参数和输入下没有可行解时，会给出错误提示：

Part 12 界面模块与计算模块的对接

我们使用node-ffi-napi库完成Node.js环境与dll的对接。

12.1 动态库声明

dll源码声明如下：

1
2
3

const char* vuetifyAPI(const char* input, int type, char head, char tail, char reject,  bool weighted) {
    /* code details */
}

GUI模块实现方法如下：

1
2
3
4
5
6

<script>
const path = window.require('path')
const ffi = window.require('ffi-napi')
const corePtr = ffi.DynamicLibrary(path.resolve('./COREDLL_031619.dll')).get('vuetifyAPI')
const core = ffi.ForeignFunction(corePtr, 'string', ['string', 'int', 'char', 'char', 'char', 'bool'])
const moment = window.require('moment')

12.2 异步调用

我们在 Vue 中为”求解”按钮的 onclick 事件绑定了以下的 handler：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

solve() {
  this.calculating = true
  this.outputText = ''
  this.runMessage = ''
  let start = moment()
  if (this.head.length > 1) { // 判断各种异常
    this.reportError("-h参数须为长度为1的英文字母，当前输入长度大于1")
    this.calculating = false
  } else if (this.tail.length > 1) {
    this.reportError("-t参数须为长度为1的英文字母，当前输入长度大于1")
    this.calculating = false
  } else if (this.reject.length > 1) {
    this.reportError("-j参数须为长度为1的英文字母，当前输入长度大于1")
    this.calculating = false
  } else if (!(this.head.length == 0 || (this.head.charCodeAt(0) >= "a".charCodeAt(0) && this.head.charCodeAt(0) <= "z".charCodeAt(0))
    || (this.head.charCodeAt(0) >= "A".charCodeAt(0) && this.head.charCodeAt(0) <= "Z".charCodeAt(0)))) {
    this.reportError("-h参数须为长度为1的英文字母，当前输入非英文字母")
    this.calculating = false
  } else if (!(this.tail.length == 0 || (this.tail.charCodeAt(0) >= "a".charCodeAt(0) && this.tail.charCodeAt(0) <= "z".charCodeAt(0))
    || (this.tail.charCodeAt(0) >= "A".charCodeAt(0) && this.tail.charCodeAt(0) <= "Z".charCodeAt(0)))) {
    this.reportError("-t参数须为长度为1的英文字母，当前输入非英文字母")
    this.calculating = false
  } else if (!(this.reject.length == 0 || (this.reject.charCodeAt(0) >= "a".charCodeAt(0) && this.reject.charCodeAt(0) <= "z".charCodeAt(0))
    || (this.reject.charCodeAt(0) >= "A".charCodeAt(0) && this.reject.charCodeAt(0) <= "Z".charCodeAt(0)))) {
    this.reportError("-j参数须为长度为1的英文字母，当前输入非英文字母")
    this.calculating = false
  } else {
    core.async( // 异步运算
      this.inputText,
      [0, this.allowRing ? 3 : 1, this.allowRing ? 3 : 1, this.allowRing ? 3 : 1][this.selectedMode],
      this.noAvailableOptions || !this.head ? 0 : this.head.charCodeAt(0),
      this.noAvailableOptions || !this.tail ? 0 : this.tail.charCodeAt(0),
      this.noAvailableOptions || !this.reject ? 0 : this.reject.charCodeAt(0),
      this.selectedMode === 1,
      (e, d) => {
        if (e) this.reportError(e)
        if (/^WordList-GUI: /.test(d)) {
          this.reportError(d.substring(14))
        } else {
          this.outputText = d
          this.runMessage = '' + moment().diff(start) + ''
        }
        this.calculating = false
      }
    )
  }

}

12.3 实现效果

1

const char* vuetifyAPI(const char* input, int type, char head, char tail, char reject,  bool weighted);

1
2
3

int gen_chains_all(const char* words[], int len, char* result[]);
int gen_chain_word(const char* words[], int len, char* result[], char head, char tail, char n_head, bool enable_loop);
int gen_chain_char(const char* words[], int len, char* result[], char head, char tail, char n_head, bool enable_loop);