【软件工程】结对编程
本作业属于课程
作业要求
第一部分
Github项目地址：
第二部分：PSP表
| Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|
| 计划 | 60 | |
| · 估计这个任务需要多少时间 | 60 | |
| 开发 | ||
| · 需求分析 (包括学习新技术) | 300 | |
| · 生成设计文档 | 60 | |
| · 设计复审 (和同事审核设计文档) | 30 | |
| · 代码规范 (为目前的开发制定合适的规范) | 30 | |
| · 具体设计 | 100 | |
| · 具体编码 | 720 | |
| · 代码复审 | 60 | |
| · 测试（自我测试，修改代码，提交修改） | 300 | |
| 报告 | ||
| · 测试报告 | 100 | |
| · 计算工作量 | 30 | |
| · 事后总结, 并提出过程改进计划 | 30 | |
| 合计 | 1880 |
第三部分：接口设计方法
信息隐藏：结对编程中我们主要通过面向对象的编程方法，将类的所有属性和部分方法私有设为私有，对相应的数据进行封装，尽可能避免使用全局变量，只对外开放必要的接口。
接口设计：在编程之前的设计阶段对接口的参数和返回值、异常处理进行规范，各个接口之间分工明确。参数处理、文件读入、单词链计算等模块之间都是独立的，只提供必要的接口用于对接。
松耦合：我们的各个模块之间都是相对独立的，核心的计算模块可以单独调用，可以与其他合作组交换核心模块，并顺利通过了相应的测试。
第四部分：计算模块接口的设计与实现过程
算法设计
对于计算模块，首先要做的就是将读入的单词列表构建为一个图，比较基本的两种思路分别是
- 以单词作为顶点、首尾字母作为边；
- 以首尾字母作为顶点、单词作为边。
因为我们需要分别计算最多单词数和最多字母数的最长单词链，采用第二种方法时，对于求最多字母数的最长单词链，可以直接将单词的字母数作为图中边的权重；对于计算最多单词数的最长单词链，可以将各个边的权重都初始化为1。这样就可以将两个函数后续的求解过程统一起来，将求解最长单词链的问题转化为求一个有向带权图的最长路径问题，明显要比第一种方法便捷，所以我首先们采用第二种方法来构建一个带权有向图。
对图进行初始化以后，第二步需要判断构造的图是有环图还是无环图，然后分别采取不同的算法。这里我们采用的判断方法为进行拓扑排序，如果所有顶点能构成一个拓扑序列，说明图中无环，否则有环。
对于有向无环图（DAG）的最长路径问题，可以将权值取负，然后就转化为求一个不带负权环的最短路径问题，或者直接用Floyd等算法来求最长路径，但是因为已经进行了拓扑排序，所以最简便的方法还是直接采用动态规划方法按排序结果求解最长路径。对于以邻接表存储的图，拓扑排序的时间复杂度是O(V+E)，求出拓扑顺序后动态规划算法的时间复杂度也为O(V+E)，因此算法总的时间复杂度为O(V+E)。
对于带环图，求其最长路径属于NP-Hard问题，并没有比较高效的算法。我们采用的方法主要是按照以每个顶点作为起始点或根据所求的起始顶点，采用深度优先搜索找出所有的路径，然后从中选择最长的路径。
算法的独到之处主要在于通过在构建有向图时，通过赋不同的权值将求解最多单词和最多字母的问题统一起来，便于后续的求解，并增加了代码的复用性。使用的拓扑排序策略不仅可以判断图中是否有环，更为无环图的求解奠定了基础。
计算模块实现
计算模块主要包括一个WordInfo类型和WordGraph，Compute两个类，另外还有gen_chain_word，gen_chain_char两个接口函数，类中的成员和函数的详细信息见下面的类图。
WordInfo类型记录了单个单词的各项信息，如起始字母、终止字母，权重，在单词列表中的位置等。
WordGraph类将根据输入的单词列表构建一个有向加权图，并对图进行拓扑排序，判断是否有环。
Compute类中含有一个WordGraph成员，根据图的类型采用不同的算法进行最长单词链的计算。
计算时gen_chain_word，gen_chain_char两个接口函数初始化对顶的WordGraph类和Compute类并调用对应的方法进行初始化、拓扑排序，求最长单词链。
第五部分：UML图显示计算模块部分各个实体
点击菜单栏“工具”→“获取工具和功能” 获取组件类设计器，然后可用通过对应文件的右键菜单中的“查看类图选项”直接生成类图。
第六部分：计算模块接口部分的性能改进
在改进计算模块接口部分的性能上大概花费了2天的时间。
改进思路
计算模块在求最长路径时，对于有环图和无环图，首先采用的方法为以字母为顶点，单词为边构造邻接表，然后以每个顶点作为起始点采用深度优先搜索，找出所有的路径，从中选择符合要求的最长路径的基本算法，确保首先能够实现基本的生成功能，避免出现“过早优化”。性能的改进主要在以下几个方面：
- 采用拓扑排序对生成的图进行排序，判断图中是否有环；
- 在根据输入单词初始化图时，将首尾字母分别相等（但首字母与尾字母不同）的多个单词合成一条边，权值取单词中长度最长的一个，简化生成的图，便于后续的拓扑排序（如果排序后发现为有环图，则说明两个顶点之间的多条同向边不能合并，在使用dfs搜索之前再重新初始化图）。
- 对于无环图，采用动态规划算法依次求出以每个顶点为尾节点的最长路径，不必搜索所有路径；
- 对于指定首字母或尾字母的有环图，只搜索所有以该字母开始或结束的路径，而不是搜索所有路径。
- 对于较为复杂的有环图，有想过用一些启发式算法来求解，但是这类算法在很多时候求得的都是局部最优解，并不能保证一定能求得全局最优解，与我们题目的要求不符，因而最终没有采用这类算法。
性能分析
以下是读入一个不带单词环文本时的性能分析图，可以看出除main函数外，花费最多的函数为File_handle类中的deal_file函数，时间主要花费在文本读入和单词处理过程中。
以下是读入一个带单词环文本时的性能分析图，可以看出程序中消耗最大的函数为Core模块的dfs函数，主要时间都花费在了路径搜索上，花费了99%以上的时间。
第七部分：契约式设计
契约式设计（英语：Design by Contract，缩写为 DbC），一种设计计算机软件的方法。这种方法要求软件设计者为软件组件定义正式的，精确的并且可验证的接口，这样，为传统的抽象数据类型又增加了先验条件、后验条件和不变式。这种方法的名字里用到的“契约”或者说“契约”是一种比喻，因为它和商业契约的情况有点类似。
优点
- 接口的定义比较规范，方便实现者和调用者的相互对接，不同模块之间的相互对接
- 代码结构清新，易于理解和维护，易于定位bug出现的地方，可以有效地保证程序的正确性
- 对于多人合作、规模比较大的工程，事先定义严格的规范十分有必要
缺点
- 需要实现者和调用者严格遵守这些规范和约定
- 可能事先定义的规范不符合实际，给编码和实践阶段带来一定的困难
在我们的编程中，代码实现之前的设计阶段会对程序的整体架构和即将实现的接口指定规范，比如函数如何定义、在哪里抛出异常等，从而方便交换编程时一人从上一人结束的地方继续进行时，能快速上手，及时了解项目进度，减少沟通成本，同时也避免因为沟通不畅出现对一个问题进行多次检查，避免重复的代码。
第八部分：计算模块部分单元测试展示
部分单元测试代码
对于计算模块接口的测试主要分为两大类，正常情况和异常情况处理，本部分主要介绍正常输入下的单元测试，异常处理将在下一部分介绍。
1.简单测试
TEST_METHOD(TestMethod1) { char* input[4] = { "END", "OF", "THE", "WORLD" }; char* result[4] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_word(input, 4, result, 0, 0, false); Assert::AreEqual(len, 2); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0 } 2.最多单词测试
TEST_METHOD(TestMethod2) { char* input[11] = { "Algebra", "Apple", "Zoo", "Elephant", "Under", "Fox", "Dog", "Moon", "Leaf", "Trick", "Pseudopseudohypoparathyroidism" }; char* result[11] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_word(input, 11, result, 0, 0, false); Assert::AreEqual(len, 4); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 3.最多字母测试
TEST_METHOD(TestMethod3) { char* input[11] = { "Algebra", "Apple", "Zoo", "Elephant", "Under", "Fox", "Dog", "Moon", "Leaf", "Trick", "Pseudopseudohypoparathyroidism" }; char* result[11] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_char(input, 11, result, 0, 0, false); Assert::AreEqual(len, 2); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 4.最多单词带环测试
TEST_METHOD(TestMethod6) { char* input[5] = { "Algebra", "Applea", "Zooa", "Elephant", "Under" }; char* result[5] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_word(input, 5, result, 0, 0, true); Assert::AreEqual(len, 3); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 5.最多字母带环测试
TEST_METHOD(TestMethod7) { char* input[5] = { "Algebra", "Applea", "Zooa", "Elephant", "Under" }; char* result[5] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_char(input, 5, result, 0, 0, true); Assert::AreEqual(len, 3); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 6.最多单词特殊测试
TEST_METHOD(TestMethod10) { char* input[5] = { "aa", "aaa", "aaaa", "aaaaa", "a" }; char* result[5] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_word(input, 5, result, 0, 0, true); Assert::AreEqual(len, 5); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 7.最多字母特殊测试
TEST_METHOD(TestMethod11) { char* input[5] = { "aa", "aaa", "aaaa", "aaaaa", "a" }; char* result[5] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_char(input, 5, result, 0, 0, true); Assert::AreEqual(len, 5); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 8.最多单词指定首字母测试
TEST_METHOD(TestMethod12) { char* input[11] = { "Algebra", "Apple", "Zoo", "Elephant", "Under", "Fox", "Dog", "Moon", "Leaf", "Trick", "Pseudopseudohypoparathyroidism" }; char* result[11] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_word(input, 11, result, 'a', 0, false); Assert::AreEqual(len, 4); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 9.最多字母指定首字母测试
TEST_METHOD(TestMethod13) { char* input[11] = { "Algebra", "Apple", "Zoo", "Elephant", "Under", "Fox", "Dog", "Moon", "Leaf", "Trick", "Pseudopseudohypoparathyroidism" }; char* result[11] = { 0 }; /* 调用Core中封装好的函数 */ int len = gen_chain_char(input, 11, result, 'a', 0, false); Assert::AreEqual(len, 4); for (int i = 0; i < len - 1; i++) Assert::AreEqual(tolower(result[i][strlen(result[i]) - 1]), tolower(result[i + 1][0])); } 此外还包括指定尾字母测试，指定首尾字母测试等，就不一一列举了。
测试覆盖率截图
测试覆盖路达到了92%(由于vs自带的单元测试功能无法查看覆盖率，所以只好新建了一个test工程，把计算模块的代码复制到test.cpp文件中，将测试用例放在main函数中进行测试和查看覆盖率)：
第九部分：计算模块部分异常处理说明
计算模块部分的异常主要包括传入的参数不合法（words指针、result指针为空，参数len为负数，首尾字母约束不合法）、单词中包含环但没有-r参数、输入的单词无法构成单词链等。
1.最多单词测试，包含环但没有-r参数
TEST_METHOD(TestMethod8) { char* input[5] = { "Algebra", "Applea", "Zooa", "Elephant", "Under" }; char* result[5] = { 0 }; /* 调用Core中封装好的函数 */ try { int len = gen_chain_char(input, 5, result, 0, 0, false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Error: word text implies word rings"); } } 2.最多字母测试，包含环但没有-r参数
TEST_METHOD(TestMethod9) { char* input[5] = { "Algebra", "Applea", "Zooa", "Elephant", "Under" }; char* result[5] = { 0 }; /* 调用Core中封装好的函数 */ try { int len = gen_chain_char(input, 5, result, 0, 0, false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Error: word text implies word rings"); } } 3.最多单词测试，无单词链
TEST_METHOD(TestMethod4) { char* input[7] = { "Algebra", "Zoo", "Under", "Dog", "Moon", "Leaf", "Trick" }; char* result[7] = { 0 }; /* 调用Core中封装好的函数 */ try { int len = gen_chain_word(input, 7, result, 0, 0, false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Error: no word chain meets the requirements"); } } 4.最多字母测试，无单词链
TEST_METHOD(TestMethod5) { char* input[7] = { "Algebra", "Zoo", "Under", "Dog", "Moon", "Leaf", "Trick" }; char* result[7] = { 0 }; /* 调用Core中封装好的函数 */ try { int len = gen_chain_char(input, 7, result, 0, 0, false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Error: no word chain meets the requirements"); } } 5.不存在指定首尾字母的单词链测试
TEST_METHOD(TestMethod17) { char* input[11] = { "Algebra", "Apple", "Zoo", "Elephant", "Under", "Fox", "Dog", "Moon", "Leaf", "Trick", "Pseudopseudohypoparathyroidism" }; char* result[11] = { 0 }; /* 调用Core中封装好的函数 */ try { int len = gen_chain_char(input, 11, result, 'a', 'm', false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Error: no word chain meets the requirements"); } } 6.参数不合法：words指针为空
TEST_METHOD(TestMethod22) { char* result[11] = { 0 }; try { int len = gen_chain_word(NULL, 11, result, 0, 'm', false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Invalid parameter: 'words' or 'result' is null."); } } 7.参数不合法：len长度为负
TEST_METHOD(TestMethod25) { char* input[11] = { "Algebra", "Apple", "Zop", "Elephant", "Under", "Fox", "Dog", "Moon", "Leaf", "Trick", "Pseudopseudohypoparathyroidism" }; char* result[11] = { 0 }; try { int len = gen_chain_word(input, -1, result, 0, 'm', false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Invalid parameter: 'len' is less than 0."); } } 8.参数不合法：首尾字母约束不合法
TEST_METHOD(TestMethod28) { char* input[11] = { "Algebra", "Apple", "Zop", "Elephant", "Under", "Fox", "Dog", "Moon", "Leaf", "Trick", "Pseudopseudohypoparathyroidism" }; char* result[11] = { 0 }; try { int len = gen_chain_char(input, 11, result, 'a', '0', false); Assert::AreEqual(0, 1); } catch (const char *error_message) { Assert::AreEqual(error_message, "Invlid parameter: 'head' or 'tail' is not a letter or 0."); } } 第十部分：界面模块设计的详细设计
设计
我们的图形用户界面采用了github上开源的图形界面库。图形界面可以分为以下四部分：
- 输入：包括通过Select File按钮导入文本以及文本框输入文本两种输入方式，导入文件后文件的内容会出现在输入框中；
- 参数选择：通过参数选择框选择对应的参数，选择的参数发生缺少、冲突 、错误时会实时给出提示信息；
- 运行：当选择的参数无误后会显示Run按钮，用户点击Run按钮后调用核心模块计算；
- 输出：点击Run按钮计算完成之后运行结果以及Export按钮显示在按钮下方，点击Export按钮将跳出路径选择窗口，用户选择路径后将结果保存到用户指定的位置。
实现
用imgui开发图形用户界面比较便捷，先从库中选择对应的模版，然后在main函数的对应位置设置组件即可，部分组件的实现过程如下：
//显示提示信息 ImGui::Begin("Word_chain"); ImGui::Text("Please input words or select file:"); //显示文本选择按钮 ImGui::Button("Select File") //参数选择框 ImGui::Text("Please select parameters:"); ImGui::Checkbox("-w", &par_w) ImGui::Checkbox("-h", &par_h) ImGui::InputText(label_head, head, 2, 0, NULL, NULL) //产生计算结果后将结果显示在屏幕上并实现按钮导出功能 if (par_right && show_result) { ImGui::Text("Result:\n%s", answer.c_str()); if (ImGui::Button("Export")) { if (get_save_file_name(save_file_name)) { outf.open(save_file_name); if (outf) { outf << answer; } outf.close(); } } } 第十一部分：界面模块与计算模块对接
对接过程
当参数选对时才会显示Run按钮，用户点击Run按钮后会进行与计算模块的对接，先对输入框中的单词进行分割，然后调用gen_chain_word、gen_chain_char函数进行计算
计算出结果后会将结果显示在在屏幕上并显示导出按钮。
//用户点击Run按钮后执行if语句中的内容调用计算模块的接口进行计算 if (par_right && ImGui::Button("Run")) { char h, t; answer.clear(); get_words(buf, len, words); h = par_h ? head[0] : 0; t = par_t ? tail[0] : 0; int cnt = 0; if (par_w) { cnt = gen_chain_word(pwords, wordnum, result, h, t, par_r); } else if (par_c) { cnt = gen_chain_char(pwords, wordnum, result, h, t, par_r); } for (int i = 0; i < cnt; i++) { answer += result[i]; answer += "\n"; } show_result = true; } //产生计算结果后将结果显示在屏幕上并实现按钮导出功能 if (par_right && show_result) { ImGui::Text("Result:\n%s", answer.c_str()); if (ImGui::Button("Export")) { if (get_save_file_name(save_file_name)) { outf.open(save_file_name); if (outf) { outf << answer; } outf.close(); } } } 图形界面截图
第十二部分：结对过程
我们的结对编程主要按照领航员与驾驶员的模式，两人轮流编程，不断交替，一人编程时另一人负责监督和检查，由于是舍友，所以有条件在同一个地方编程，针对程序的设计和实现有不同的意见也会及时沟通，十分方便。
第十三部分：结对编程优缺点
结对编程优点
将代码复审的机制发挥到极致，有助于提高代码质量。
- 方便交流，能够有效锻炼和提升与人沟通协作的能力，同时在交流中提升自己。
二人轮流作业，互相监督，能在一定程度上避免其中一人划水的情况发生。
结对编程缺点
- 结对二人不在同一个地方时沟通成本较高，会对效率产生影响。
- 结对二人如果沟通不畅，容易产生分歧和矛盾。
- 结对二人交换编程时，可能需要花费一定的时间来熟悉上一个人的思路，容易花费额外的时间。
- 结对二人容易因为其他无关的事情开始闲聊，降低效率。
队友优点
- 能尽早开始任务，做事不拖延
- 能积极与人沟通
- 善于学习新工具、新技术的使用
队友缺点
- 代码风格不太规范
个人的优点
- 做事之前能先制定比较详细的计划
- 心态比较平和
- 乐于学习新知识
个人缺点
- 不善于沟通
- 做事比较拖延
第十四部分：PSP表
| Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|
| 计划 | 60 | 30 |
| · 估计这个任务需要多少时间 | 60 | 30 |
| 开发 | ||
| · 需求分析 (包括学习新技术) | 300 | 200 |
| · 生成设计文档 | 60 | 60 |
| · 设计复审 (和同事审核设计文档) | 30 | 30 |
| · 代码规范 (为目前的开发制定合适的规范) | 30 | 60 |
| · 具体设计 | 100 | 300 |
| · 具体编码 | 720 | 900 |
| · 代码复审 | 60 | 60 |
| · 测试（自我测试，修改代码，提交修改） | 300 | 300 |
| 报告 | ||
| · 测试报告 | 100 | 200 |
| · 计算工作量 | 30 | 30 |
| · 事后总结, 并提出过程改进计划 | 30 | 30 |
| 合计 | 1880 | 2230 |
附加题
1.GUI部分见博客第十、第十一部分。
使用说明(界面见第十一部分)：
1.可以使用select file按钮选择文件，也可以直接在input words文本框输入。 2.提供了参数选择框，参数错误时会给予提示；仅当参数正确时才会弹出run按钮。 3.run的结果直接显示在GUI上，并可以使用Export按钮导出。2.松耦合测试：（16061175 16061156）GUI AND（16061170 16061167） Core
耦合测试我们两个组的dll模块可以直接互相调用，不需要任何其他操作，但是运行时发现了不同的运行结果，如下图：
使用对方Core.dll模块的运行结果（20个单词）：
使用我们自己的Core.dll模块的运行结果（22个单词）：
经查证交换的合作小组的Core部分算法有问题并告知合作小组同学修正了，目前双方执行结果一致。