数据结构-C语言描述(第三版)第13章实习指导和实习题.ppt

　　5．测试和调试　　采用黑盒测试法的等价类划分法产生测试用例。测试分两阶段进行：模块测试和集成测试。　　1) 模块测试　　(1) 模块InfixtoPostfix测试。模块InfixtoPostfix中的函数InfixtoPostfix接收以字符串形式输入的中缀表达式，将其转换成后缀表达式。输出的后缀表达式中每一项之间以空格分隔。 　　测试用例可分成合法和不合法两个等价类，其中符合中缀表达式语法规则的表达式列为有效等价类，否则为无效等价类。合法和不合法的中缀表达式可进一步根据不同的情况分别细分成若干种情况。例如，混合数据类型、单层括号、括号嵌套、分母为零、括号非法嵌套、非允许的运算符、非法操作数(操作数不是合法的数)等。表13－1为函数InfixtoPostfix的测试用例和测试结果。 (2) 模块Eval测试。模块Eval中的函数Eval接收来自模块Calculator输出的后缀表达式。函数Eval的测试用例同样可分为合法和非法两个等价类。由于本模块通常接收合法后缀表达式，因此可以重点测试输入为合法的后缀表达式时的情形。表13－2显示函数Eval的测试用例和测试结果，运行结果取两位小数。 2) 集成测试　　集成测试是测试模块Calculator中的main函数，它调用函数InfixtoPostfix和Eval实现输入和计算中缀表达式的值。其测试用例和测试结果见表13－3。 3) 结果分析　　上述测试结果表明程序的如下情况：　　(1) 当输入允许的正确的中缀表达式时，程序能输出正确的后缀表达式，并得到正确的运算结果。　　(2) 在输入不合法的情况下，程序只提供了简单的查错功能。例如，程序未考虑负数，一旦输入负数，将显示“Missing Operand!”。在缺少右括号时，程序也能给出某个输出，但并不能正确提示。如果缺少左括号，程序在遇到右括号时将不断弹出栈中元素，因栈中无左括号，程序在栈空的情况下仍执行出栈操作，程序将进入无限循环。如果输入不允许的运算符或操作数，程序会非法终止。测试结果表明，这一程序健壮性差，需进一步改进。 　　6．实习小结　　(1) 对教材介绍的算法加以改进使之可以计算操作数是双精度数的中缀表达式，此时需要解决在输入的字符串中提取双精度操作数的问题，对转换而成的后缀表达式可以在表达式的各项(操作数和运算符)之间添加空格作为项与项之间的分隔符。还需将字符串形式的双精度数转换成double类型的数。　　(2) 一个可靠的程序要求在合法输入时，产生预期的输出，还应当考虑当输入不合法时，如何作适当处理，使之不会导致系统异常。本程序对健壮性考虑较少。　　(3) 理解了科学和合理选择测试用例对开发可靠软件的重要性。熟练使用调试环境能较快诊断程序存在的语法和逻辑错误。 　　2．实习内容和要求　　事先创建磁盘文本文件original.txt，实现对该文本文件的查找、删除和替换。　　(1) 设字符串采用如下定义的结构存储，在此存储结构上实现字符串ADT上定义的所有运算。　　typedef struct string{　　 char chs[MaxSise];　　 int Length,MaxSise,Current;　　}String; 　　(2) 编写主函数，以菜单方式选择执行如下操作：　　① 读入磁盘文件。　　② 查找：输入待查找的子串，从主串的当前位置开始查找子串第一次出现的位置；若存在，则显示该子串出现的位置，否则显示“未发现所查子串”。　　③ 删除：输入待查找的子串，从主串的当前位置开始查找子串第一次出现的位置；若存在，则删除该子串，并显示结果文本，否则显示“未发现所查子串”。　　④ 替换：输入待查找的子串和一个替换串，从主串的当前位置开始查找子串第一次出现的位置；若存在，则以替换串替换之，并显示结果文本，否则显示“未发现所查子串”。　　⑤ 全部替换：输入待查找的子串和一个替换串，在主串中查找子串；对子串的每次出现都以替换串替换之，并显示全部替换后的结果文本。 实习11 二叉树的基本运算和应用　　1．实习目的　　(1) 理解二叉树的数据结构。　　(2) 掌握二叉链表上实现二叉树基本运算的方法。　　(3) 学会设计基于遍历的、求解二叉树应用问题的算法。 　　2．实习内容和要求　　(1) 实现二叉树ADT的各基本运算。　　(2) 设计递归算法：　　① 删除一棵二叉树。　　② 求一棵二叉树的高度。　　③ 求一棵二叉树中叶子结点数。　　④ 复制一棵二叉树。　　⑤ 交换一棵二叉树的左右子树。　　(3) 设计算法，按自上而下、自左向右的次序，按层次遍历一棵二叉树。