1、数据结构与算法课程设计报告格式要求与模板级适用“数据结构与算法课程设计”报告写作要求及示例一、报告要求:1. 各位同学要严格按照要求写报告,A4 纸打印,用学校统一印发的课程设计报告封面封装(报告封皮各班班长到学院办公室领取)。2. 报告中不要求附全部的程序代码,但主要代码在详细设计中说明。3. 报告上的课程设计名称和指导教师按照数据结构与算法课程设计计划书中指定的填写。4. 报告字体及字号说明:中文使用宋体,西文使用Times New Roman。一级标题使用四号加黑,其它次级标题使用小四加黑,正文使用小四不加黑(注:不要附代码)。5. 刻盘说明:统一刻录光盘保存文档和源码,每班一张(班长负
2、责),卷标:数据结构与算法课程设计(*2012-*班),如:数据结构与算法课程设计(软件2012-1班)。根目录中每个同学一个文件夹,文件夹中保存源代码及报告电子文档,目录名为学号加姓名如:09083301-刘德华。6. 报告提交:课程设计报告由各班长或学习委员收齐后,交给各班的课程设计指导教师。报告提交时间:3月24日(周一)。具体提交地点和方式,由各班指导教师确定。二、报告格式1问题描述题目内容、基本要求、提高要求。2需求分析软件的基本功能、输入/输出形式、测试数据要求。3概要设计抽象数据类型、主程序流程及模块调用关系。4详细设计实现概要设计的数据类型、主程序以及其它模块的算法描述。5编码
3、与调试分析编码与调试过程中遇到的问题及解决的办法,还存在哪些没有解决的问题?6使用说明简要说明程序运行操作步骤。7测试结果8自学知识 自主学习了哪些新知识及主要知识点描述9课程设计心得体会三、示例题目:计算表达式的值1、问题描述对于给定的一个表达式,表达式中可以包括常数、算术运行符(“+”、“-”、“*”、“/”)和括号,编写程序计算表达式的值。基本要求:从键盘输入一个正确的中缀表达式,将中缀表达式转换为对应的后缀表达式,计算后缀表达式的值。提高要求:(1)对于表达式中的简单错误,能够给出提示;(2)不仅提示错误,也能给出错误信息(3)表达式中可以包括单个字母表示的变量(4)能够处理多种操作符
4、(5)实现包含简单运算的计算器(6)实现一个包含简单运算和函数运算的计算器。 2需求分析软件的基本功能:由键盘输入中缀表达式,程序可以将输入的中缀表达式转换成对应的后缀表达式,并计算后缀表达式的值。对于在输入时发生的简单错误,程序可以给出提示。本程序支持含负数、小数、多位数等多种操作数的处理,可以计算含加、减、乘、除、求余、求幂等多种运算符的表达式,并能判断表达式括号是否匹配。输入/输出形式:用户可以通过控制台,根据输入提示。输入形式:正确的不含字母变量的中缀表达式;含有简单错误的中缀表达式。输出形式:对于正确的中缀表达式,可以输出其转化后的后缀表达式及表达式的计算结果;对于含有简单错误的中缀
5、表达式,程序将自动输出错误提示,并给出错误信息。测试数据要求:用户可以输入一个符合要求的中缀表达式,也可以输入一个包含简单错误的表达式。表达式中可以包括各种类型的常数以及负数等,操作符包括(+、-、*、/、%、)等,同时表达式还可以包括各种括号。3概要设计(1)抽象数据类型:根据题目的要求,考虑用栈类型比较适合。ADT SeqStackData栈中元素具有相同类型及后进先出特性,相邻元素具有前驱和后继关系Operation SeqStack前置条件:栈不存在 输入:无 功能:栈的初始化 输出:无后置条件:构造一个空栈 SeqStack 前置条件:栈已存在 输入:无功能:销毁栈输出:无后置条件:
6、释放栈所占用的存储空间 Push 前置条件:栈已存在 输入:元素值x 功能:在栈顶插入一个元素x 输出:如果插入不成功,抛出异常 后置条件:如果插入成功,栈顶增加了一个元素 Pop 前置条件:栈已存在 输入:无 功能:删除栈顶元素 输出:如果删除成功,返回被删元素值,否则,抛出异常 后置条件:如果删除成功,栈顶减少了一个元素 GetTop 前置条件:栈已存在 输入:无 功能:读取当前的栈顶元素输出:若栈不空,返回当前的栈顶元素值后置条件:栈不变 Empty 前置条件:栈已存在 输入:无 功能:判断栈是否为空 输出:如果栈为空,返回1;否则,返回0 后置条件:栈不变End ADT(2)主程序流程
7、:(3)模块调用关系:本程序中函数包括:main函数,栈操作相关函数,Translate函数,Value函数,Calculate函数,OpPriority函数,Match函数(这里要求对每个函数的功能做简单介绍)其函数调用关系如下:4详细设计(1)实现概要设计的数据类型:采用顺序栈const int StackSize = 50;template /定义模板类SeqStackclass SeqStackpublic: SeqStack(); /构造函数,栈的初始化 SeqStack(); /析构函数 void Push(T x); /将元素x入栈 T Pop(); /将栈顶元素弹出 T Get
8、Top(); /取栈顶元素(并不删除) bool Empty(); /判断栈是否为空private: T dataStackSize; /存放栈元素的数组 int top; /栈顶元素;(2)主程序以及其它模块的算法描述:主函数具体代码:int main () char op; Mune(); /调用菜单函数 cin op; /输入选择字符 getchar(); / 吃掉回车,不然getline输入会有错,甚至导致系统崩溃。 cout op; getchar(); cout endl; return 0;这个函数主要调用了实现功能的各个函数。其步骤为:在用户没有选择退出时,先调用输入函数,输入
9、中缀表达式;然后调用判断表达式,如果中缀表达式错误,则根据返回的值来输出错误提示,不再往下运算;如果中缀表达式正确,则将中缀表达式转换为后缀表达式,然后输出中缀表达式和转换后的后缀表达式;接着,再调用计算函数,计算后缀表达式的结果输出。最后是清屏函数。直至用户选择退出。(3)其它模块的算法描述 表达式转换函数功能:将中缀表达式转换为后缀表达式,其中infix是输入的中缀表达式, postfix是转换后的后缀表达式。输入中缀表达式返回后缀表达式。template char *SeqStack:Translate(char infix,char postfix) SeqStack cstk;(这里
10、不写代码,但要把代码的核心算法描述清楚) 计算后缀表达式的值功能:由后缀表达式计算表达式的值,返回计算结果template void SeqStack:Value(char postfix) SeqStack dstk; dstk.Push(#); /将#压栈判断表达式结束 int j = 0;double a, b, result = 0; /左右操作数和计算结果(这里不写代码,但要把代码的核心算法描述清楚).其它函数的详细描述, 算法的效率与特点也在此描述5、编码与调试分析编码与调试过程中遇到的问题及解决办法:【问题一】程序无法计算负数。解决办法:分析得知,出现负数有两种情况:一是在表达式
11、首端直接出现负数,则将全部字符后移一位,在字符数组首插入-;二是在表达式中(后面跟着负数,则将(后出现的字符都向后移动一位,在(后插入一个0,再进行计算。解决此问题的核心代码:int n1 = strlen(infix); if(infix0 = -) /处理首字符是-的情况,在-前添加一个0 for(i = n1; i = 0; i-) infixi+1 = infixi; infix0 = 0; for(j = 0; j j; i-) infixi+1 = infixi; infixj+1 = 0; 【问题二】程序在判断表达式输入形式有误时,考虑情况不周全。解决办法:尽可能多的将表达式有误
12、的情况考虑在内。以下为现已考虑到并解决的问题:表达式中出现非数字或非运算符的其他字符;表达式中括号不匹配。【问题三】给变量赋值时出现重定义问题。解决办法:在定义暂存栈顶元素的变量t时,应该在函数外面定义,在函数里面给变量赋值时不能定义。【问题四】无法处理多位数和小数。解决办法:在连续的操作数结束之后插入空格到后缀表达式中,以分隔操作数。解决此问题的核心代码:if(op = 0 & op = 0 & op = 9)|(op = .) postfixj = op; j+; op = infix+i; postfixj = ; /插入空格为了以后好分隔操作数 j+; 2.待解决问题:由于使用了类模板
13、,所以在VC编译器中不能把类和实现函数分开;表达式中出现多个运算符同时连续出现的情况;不能计算含单个字母表示变量的表达式。 6、使用说明进入菜单,根据提示进行选择:(a).若要输入中缀表达式并求值,选择1;(b).若要退出程序,选择2;(c).若输入出现错误,则返回主菜单,重新输入。7、测试结果(1)含小数、多位数、负数及括号的表达式显示结果:(2)含求余、求幂的表达式的显示结果:(3)除法、求余时对于除数为零的错误提示: (4)括号不匹配时的错误提示: (5)输入错误选择时的错误提示: 8、自学知识在课程设计过程中,特别是在代码编写和调试的过程中,自学了很多新的知识。例如atof()函数,包
14、含于表头文件 #include 。 其功能是: 把字符串转换成浮点数。具体的函数说明是: atof()会扫描参数nptr字符串,跳过前面的空格字符,直到遇上数字或正负符号才开始做转换,而再遇到非数字或字符串结束时(0)才结束转换,并将结果返回。参数字符串可包含正负号、小数点或E(e)来表示指数部分。返回值是转换后的浮点型数。还有一个知识点是清屏函数,它也是包含于头文件中的, 使用形式为system(CLS)。主要功能就是清空屏幕。9、课程设计心得体会通过这次课程设计,增强了我的自信心。因为在这次课程设计中,我遇到了一些问题,但是都逐个得解决了,虽然有些问题请教了同学,但是从中学了很多东西,也学
15、到了一些处理问题的方法。在能力上得到了一些提升。同时也养成了独立思考问题,以及和同学一起探索问题的良好习惯。当然,在课程设计过程中,有些细节的处理还是不够完美,需要完善的地方还有很多,还需要继续努力,尽量将程序完善。 在编写程序过程中,得到了部分同学的帮助,如:数据间的分隔问题,得到了*同学的帮助(这里列出你的哪问题,得到了谁的帮助),将中缀表达式转换为后缀表达式的算法思想参考了数据结构课程设计(机械工业出版社),然后根据自己的理解,完成基本算法和细节处理,最后完成了转换函数的代码编写。 在将字符串转换为浮点型数字进行运算的思想主要参考了程序设计引导及在线实践这本书里面的一道程序,然后加以灵活运用,转换为自己的代码。当然,为此也掌握了一些新的知识。 清屏函数是在XX百科上获取的知识,也属于自学的新知识。 参考书:(列出你阅读的主要参考书或资料) 1c+面向对象程序设计 清华大学出版社 谭浩强著 2数据结构(C+版)清华大学出版社 王红梅、胡明、王涛著