| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 60 | 30 |
| · Estimate | · 估计这个任务需要多少时间 | 60 | 30 |
| Development | 开发 | 1680 | 2320 |
| · Analysis | · 需求分析 (包括学习新技术) | 120 | 100 |
| · Design Spec | · 生成设计文档 | 30 | 30 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 30 | 20 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 30 | 30 |
| · Design | · 具体设计 | 60 | 120 |
| · Coding | · 具体编码 | 1200 | 1680 |
| · Code Review | · 代码复审 | 30 | 40 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 180 | 300 |
| Reporting | 报告 | 390 | 510 |
| · Test Report | · 测试报告 | 180 | 200 |
| · Size Measurement | · 计算工作量 | 30 | 10 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 180 | 300 |
| 合计 | 2130 | 2860 |
In computing and systems design a loosely coupled system is one in which each of its components has, or makes use of, little or no knowledge of the definitions of other separate components. Subareas include the coupling of classes, interfaces, data, and services.[1] Loose coupling is the opposite of tight coupling.
——引用自维基百科
void InputHandler(int argc, char* argv[], bool &enable_loop, int &word_or_char, char &head, char &tail, string &Filename);
void ReadFile(string FileName, vector<string> &words);
void DFS_Length(Graph G, int v, vector<string> words, char tail);
以前做过类似的题，输入的所有单词能否全部首尾相连形成链。由于单词首尾相连有多种连接方式，故基本的数据结构为图。
建图有两种方式，一种是以单词为节点，如果单词间正好可以首尾连接，则添加一条边，该边即为连接的字母。另一种建图方式是以字母为节点，以单词为边，出现一个单词，即把首字母节点向尾字母节点添加一条边，边的值即为该单词。
对于这道题目而言，由于单词需要输出，加之对第二种建图方式掌握并不熟练，因此选择的是第一种建图方式。
模型确立后，问题就可以简化成“求图中的最长链”，即最长路径问题，显然问题是多源最长路径问题。
数据结构为图，存储方式为邻接矩阵，理由是能更契合floyd算法。
对于无环情况，由于为多源最长路径问题，联想到最短路径问题，可以确定为floyd算法。
而对于有环情况，由于出现了正值环，floyd算法不再适用。在找不到更有解决方法的情况下，只能适用DFS深度优先搜索求解。
ReadFile: 读取文件的模块，将文件中的单词提取进入容器vector中。
Graph: 图的定义。
InputHandler：处理输入的模块，读取命令行并处理参数。
FindLongestWordList: 计算模块，内含计算接口。计算出单词中的最长链。
首先需要判断有无环，对于没有-r参数的输入来说，如果有环需要报错。这里也是用到DFS的染色算法。每个点有三种状态：未遍历过，遍历过，当前序列正在遍历。如果一次DFS中一个点与正在遍历中的点相连了，说明DFS回到了之前的点，即图中有环。
另一问题是由于无环情况最多可有10000个单词，而floyd算法时间复杂度为O(n^3)，暴力的计算显然是不行的。考虑到对于无环的情况，有如下特性：对于单词element和elephant，由于无环，这两个单词最多只有一个会出现在链中。（否则会出现element, t..., ..., ....e, elephant / element，这样一定是有环的），而如果要满足字母最多，显然这时候需要选择elephant加入链中。因此我们可以对于所有首尾字母相同的单词，保留首尾字母组合中，最长的一个单词。这样的操作之后，最多的单词数目为351，即使是时间复杂度O(n^3)的算法也能很快得出结果。另外可以计算得，最长链的长度最大为51。
——优缺点引用自维基百科
TEST_METHOD(TestMethod3)
{
// TODO: normal_test3
char* words[101] = { "element", "heaven", "table", "teach", "talk"};
char* answer[101];
for (int i = 0; i < 101; i++)
{
answer[i] = (char*)malloc(sizeof(char) * 601);
}
int l = gen_chain_word(words, 5, answer, 0, 0, true);
Assert::AreEqual(l, 4);
Assert::AreEqual("table", answer[0]);
Assert::AreEqual("element", answer[1]);
Assert::AreEqual("teach", answer[2]);
Assert::AreEqual("heaven", answer[3]);
for (int i = 0; i < 101; i++)
{
free(answer[i]);
}
}
TEST_METHOD(TestMethod6)
{
// TODO: normal_test6
char* words[101] = { "apple", "banane", "cane", "a", "papa", "erase" };
char* answer[101];
for (int i = 0; i < 101; i++)
{
answer[i] = (char*)malloc(sizeof(char) * 601);
}
int l = gen_chain_char(words, 6, answer, 'a', 'e', false);
Assert::AreEqual(l, 3);
Assert::AreEqual("a", answer[0]);
Assert::AreEqual("apple", answer[1]);
Assert::AreEqual("erase", answer[2]);
for (int i = 0; i < 101; i++)
{
free(answer[i]);
}
}
TEST_METHOD(TestMethod2)
{
// 正确_2
int argc = 6;
char* argv[101] = { "Wordlist.exe", "-r", "-h", "a", "-c", "test_1.txt" };
char head;
char tail;
bool enable_loop;
int word_or_char = 0;
string Filename;
InputHandler(argc, argv, enable_loop, word_or_char, head, tail, Filename);
Assert::AreEqual(enable_loop, true);
Assert::AreEqual(word_or_char, 2);
Assert::AreEqual(head, 'a');
Assert::AreEqual(tail, char(0));
Assert::AreEqual(Filename, (string)"test_1.txt");
}
单元测试覆盖率截图（由于C++没有找到直接测试单元测试覆盖率的插件，这里用的方法是将单元测试代码移至main函数中用OpenCppCoverage插件得到的覆盖率，部分异常测试没有放进来，所以覆盖率没有达到100%）
TEST_METHOD(TestMethod3)
{
// 错误_1
int argc = 5;
char* argv[101] = { "Wordlist.exe", "-r", "-r", "-c", "test_1.txt" };
char head;
char tail;
bool enable_loop;
int word_or_char = 0;
string Filename;
try {
InputHandler(argc, argv, enable_loop, word_or_char, head, tail, Filename);
Assert::IsTrue(false);
}
catch (myexception1& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是‘-r’出现了两次，错误的参数组合。
TEST_METHOD(TestMethod7)
{
// 错误_5
int argc = 6;
char* argv[101] = { "Wordlist.exe", "-r", "-h", "1", "-c", "test_1.txt" };
char head;
char tail;
bool enable_loop;
int word_or_char = 0;
string Filename;
try {
InputHandler(argc, argv, enable_loop, word_or_char, head, tail, Filename);
Assert::IsTrue(false);
}
catch (myexception2& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是‘-h’指定首字母为‘1’，明显是错误的。
TEST_METHOD(TestMethod9)
{
// 错误_7
int argc = 5;
char* argv[101] = { "Wordlist.exe", "-b", "-r", "-c", "test_1.txt" };
char head;
char tail;
bool enable_loop;
int word_or_char = 0;
string Filename;
try {
InputHandler(argc, argv, enable_loop, word_or_char, head, tail, Filename);
Assert::IsTrue(false);
}
catch (myexception3& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是输入参数‘-b’显然是不符合规定的。
TEST_METHOD(TestMethod2)
{
// 错误
vector <string> words;
try {
ReadFile("normal_test3.txt", words); // 不存在的文件
Assert::IsTrue(false);
}
catch (myexception4& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是测试了一个在此路径下不存在的文件。
TEST_METHOD(TestMethod2)
{
// 错误
vector <string> words;
try {
ReadFile("long_word_test.txt", words);
Assert::IsTrue(false);
}
catch (myexception4& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是文件中存在长度超过600的单词。
TEST_METHOD(TestMethod2)
{
// 错误
vector <string> words;
try {
ReadFile("more_words_test.txt", words);
Assert::IsTrue(false);
}
catch (myexception4& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是所测试文件中单词数超过了10000。
TEST_METHOD(TestMethod10)
{
// wrong_test2
char* words[101] = { "alement", "oeaven", "tabla", "teaco", "talk" };
char* answer[101];
for (int i = 0; i < 101; i++)
{
answer[i] = (char*)malloc(sizeof(char) * 601);
}
try {
int l = gen_chain_char(words, 5, answer, 0, 'n', false);
Assert::IsTrue(false);
}
catch (myexception7& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是传入单词可以形成环，且用户没有传入参数‘-r’。
TEST_METHOD(TestMethod11)
{
// wrong_test3
char* words[101] = { "alement", "oeaven", "tabla", "teaco", "talk" };
char* answer[101];
for (int i = 0; i < 101; i++)
{
answer[i] = (char*)malloc(sizeof(char) * 601);
}
try {
int l = gen_chain_word(words, 5, answer, 'b', 'n', true);
Assert::IsTrue(false);
}
catch (myexception8& e) {
Assert::IsTrue(true);
}
catch (...) {
Assert::IsTrue(false);
}
}
这个单元测试是规定了首尾字母后，单词链中没有用户所要求的单词链。
原文：https://www.cnblogs.com/imageboom/p/10530410.html