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