《 数据结构与算法》实验报告要求

《 数据结构与算法 》实验报告要求

实验报告首先要求有一个清晰醒目的报告标题，例如：《数据结构课程设计实验一：xxxxxxxxxx》。报告至少要求具备以下四部分内容：

一、简介 这一部分需简单介绍题目内容，即该实验到底要做什么。如果涉及明确 的算法，最好再简单介绍一下算法产生的背景。 基本要求：实验内容必须覆盖完备。 二、算法说明 这一部分需详细描述解决问题所需要用到的算法和重要的数据结构，即 该实验到底应该怎么做。 基本要求：所有处理问题中所用到的关键算法都要描述清楚，而不是仅 描述主函数。算法和数据结构用伪码和图示描述，千万不要只写源代码加注 释。 这一部分的目的是让读者在短时间内对作者解决问题的整体思路有个 清楚的了解，表达方式必须比源代码通俗易懂。如果读者感觉还不如直接读

源代码来得明白，这一部分就失去了意义。 三、测试结果 这一部分需根据题目类型设计提供相应的测试方法和结果。 对于需要比较不同算法性能优劣的题目，应设计并填写一张性能比较表格，列出不同算法在同一指标下的性能表现。但仅仅罗列出一堆数据是不够的，还应将数字转化为图象、曲线等，帮助读者更直观地理解测试结果。 对于需要利用某算法解决某问题的题目，应设计并填写一张测试用例表。每个测试用例至少应包括下列内容： ? 测试输入：设计一组输入数据； ? 测试目的：设计该输入的目的在于测试程序在哪方面可能存在的漏洞； ? 正确输出：对应该输入，若程序正确，应该输出的内容； ? 实际输出：该数据输入后，实际测试得到的输出内容； ? 错误原因：如果实际输出与正确输出不符，需分析产生错误的可能原因； ? 当前状态：分为“通过”（实际输出与正确输出相符）、“已改正”（实际输出与正确输出不符，但现在已修改正确）、“待修改”（实际输出与正确输出不符，且尚未改正）三种状态。 四、分析与探讨 这一部分应是整篇报告中最令读者感兴趣的部分，分为两块内容： ? 测试结果分析。需详细解释测试策略，对得到的数据进行分析，总结出算法的时空复杂度，得出自己对算法性能等方面分析的结论。 ? 不局限于题目要求使用的算法，探讨更多解决问题的途径，或者提出自己的见解，给出改进算法以得到更好结果的建议。 附录：源代码 源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行少于30%的代码将不能得分。 本课程的考核实验报告可以选择以下任一实验，也可以自己选择其他实验。 1、第1个可选题目

设计一个模拟简单整数计算器的程序。该程序可以接受整数数据，运算符可以接受包含(, ), +, -, *, /, %, 和 ^ (求幂运算符, a^b = ab )的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。

输入要求：

程序从“input.txt”.文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。

输出要求：

对于每一个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值（精确到小数点后两位），也可能是错误信息“ERROR IN INFIX NOTATION”

输入例子： 499+599+699*1 (3*5*(4+8)%2) 2^2^3 1+2( 2/0 (2-4)^3 2%2 2%5

输出例子： 1797 0 256

ERROR IN INFIX NOTATION ERROR IN INFIX NOTATION -8 0 2

2、第2个可选题目

完成字符串模式匹配的KMP算法即完整程序。对给定的文本文件，查找所有给定的子串。

具体的要求可以自主确定。 3、第3个可选题目

设计并实现一种快速排序（quicksort）的最优化的版本，并且比较在下列组合情况下的算法的性能表现：

(1) Cutoff值从0~20 Cutoff值的作用是只有当数组的长度小于等于这个值时，才使用另一种排序方法对其排序，否则继续使用quicksort算法排序。 (2) 选定pivot（支点）的方法分别是“第一个元素”，“三个元素的中值”，“五个

元素的中值”。

对上述的测试分别要采用如下三种类型的input文件： (1) 顺序的input (2) 逆序的input (3) 随机的input

输入文件中测试数组的大小可以从1000个数到10000个数不等。程序输入input.txt文件，输出output文件。例如： input.txt内容如下

5 //数字的个数

5 4 3 2 1 //数字用空格分开

//两组测试数据中间空一行 10

4 6 8 7 5 1 3 9 2 0

相应的output.txt内容如下

Case number: 1

Number of elements: 5 1 2 3 4 5

Case number: 2

Number of elements: 10 0 1 2 3 4 5 6 7 8 9

程序的重点在于对每种组合情况下算法性能的比较。不同的运行时间（run time）要用图表表示出来，在图表中要区分由于文件大小的不同而产生的差别。

实验成绩的评分依据：

一：程序设计（50分）其中：

1、完成程序的设计，程序能够正常运行（20分）；

2、输入测试数据，能够得到正确的结果，并且能够能对输入内容进行数据合法性检测并进行相应的异常处理（20分）；

3、程序结构合理，有充足的（30%以上）注释（10分）；

4、数据结构、算法设计巧妙，在正确的基础上提高效率或者增加创新的一些功能，提供友好的输入、输出界面，可相应加分。 二、程序测试（20分）其中：

5、设计充足合理的测试用例（15分）； 6、完成测试结果分析（5分）；

7、测试用例没有涵盖各种情况的，相应扣3－6分；测试用例考虑全面、测试结果分析透彻，可相应加分。 三、实验报告（30分）其中：

8、完成实验报告，第一章中描述程序所解决的问题以及算法背景等（5分）； 9、第二章中使用伪代码等手段对算法做出详细的分析设计（15分）； 10、第四章分析与探讨（8分）；文档风格统一（2分）；

11、实验题目分析透彻，算法、数据结构描述恰当，可相应加分。

本文来源：https://www.bwwdw.com/article/zuj6.html