“数据结构与算法课程设计”报告写作要求及示例

一、报告要求：

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 T>           //定义模板类SeqStack

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 <class T>

char *SeqStack<T>::Translate(char infix[],char postfix[])

{

SeqStack<char> cstk;

（这里不写代码，但要把代码的核心算法描述清楚）

     计算后缀表达式的值

功能：由后缀表达式计算表达式的值，返回计算结果

template <class T>

void SeqStack<T>::Value(char postfix[])

{

    SeqStack<double> dstk;

   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 <stdlib.h> 。 其功能是: 把字符串转换成浮点数。具体的函数说明是： atof()会扫描参数nptr字符串，跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，而再遇到非数字或字符串结束时('\0')才结束转换，并将结果返回。参数字符串可包含正负号、小数点或E(e)来表示指数部分。返回值是转换后的浮点型数。

还有一个知识点是清屏函数，它也是包含于<stdlib.h>头文件中的， 使用形式为system("CLS")。主要功能就是清空屏幕。

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<M;i++) { } cout<<bds(A,M,&a[0])<<endl; cout<<a[i].get()<<" ";

其中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<L) { if(A[i]=='(') //括号的处理 { int k=1; for(int j=i+2;j<L;j++) { if(k!=0) { } if(k==0) { int l=j-i-1; char *p=new char[l+1]; string B; if(A[j]=='(') k++; if(A[j]==')') k--; for(int m=0;m<l;m++) p[m]=A[i+1+m]; p[l]='\0'; B=p;

} } 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<N;j++) {if(A[i]==char(a[j].get1())) { } } Temp.input1(a[j].get()); if(i==0) ANS.input1(Temp.get()); Temp.input1(jisuan(A,i,L,N,&a[0])); ANS=ANS<Temp; i++; continue; i++; break; return ANS.get();

其中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<L;j++) { if(k!=0) { } if(k==0) { int l=j-i-1; char *p=new char[l+1]; string B; for(int m=0;m<l-1;m++) p[m]=A[i+2+m]; if(A[j]=='(') k++; if(A[j]==')') k--; p[l-1]='\0'; B=p; delete p; Temp.input1(bds(B,N,&a[0])); i=i+j; break;

} } } else { } return Temp.get(); int j=0; while(j<L) { } if(A[i+1]==char(a[j].get1())) { } j++; i++; Temp=a[j]; break;

主函数部分同时还完成命题变元及命题公式的输入与储存，最后调用函数void fuzhi(string A,int N,int M,Proposition a[])完成全部计算，其内容如下：

Proposition a[30]; char x='1'; int i=0,N; cout<<"请输入涉及的命题变元(输入‘0’按回车结束)"<<endl; while(int(x)!=48) { cin>>x;

if(i>19) } N=i; int M; M=N; string A; cout<<"请输入命题公式( 否定：！，合取：&，析取：|，蕴含> )"<<endl; cin>>A; cout<<A<<"的真值表为："<<endl; for(int j=0;j<M;j++) cout<<char(a[j].get1())<<" "; cout<<"真值"<<endl; fuzhi(A,N,M,&a[0]); system("pause"); return 0; {cout<<"命题变元个数超过30，无法处理"<<endl;break;} if(x!='0') { } a[i].input2(x); i++;

从实验结果还可以看出，本程序的基本识别全部四种运算及括号，这样在理论上是可以计算较为复杂的命题公式的真值表。 当然，由于计算机硬件及C++的递归深度的限制， 命题公式的复杂度超过一定限制也会无法计算，对于一般性的复杂命题公式的真值计算，本程序完全可以基本可实现。

4、编码与调试分析：

一般来讲，构想一个算法并不困难，难的是把设计的算法变成有效的代码。在代码的调试中，经常出现编译通过了，但运行时报错，而这类问题又很难查到，这就需要花时间和精力，没有足够的耐心是不行的。当遇到这类问题时，我常常不知所措。一般采取请教同学或老师的方法 请求帮忙解决。

5．使用说明：（程序使用简单说明。）

1）运行程序

2）按要求输入变量 一般输入 2—4个英文字母，输入结束后输入0回车进入下一步。

3)按提示输入表达式命题公式。输入结束并确认输入无误后回车 进入程序运算。

4）程序自动给出真值表。

5）按任意键结束。

6、测试结果：

经验证 程序运行正常 结果正确。

7．课程设计心得体会

在大学过去的一年半里，我学习了《C++面向对象程序设计》和《算法与数据结构》。对这些课学的很吃力，因为自己动手时总是困难重重，很多时候是处于理论的学习而没有上机的实践操作，在有限的上机操作时，经常是看看老师提供的代码就算了。平时遇到问题，总是到网上找代码，几乎没有自己原创的程序，也没认真下功夫去写过代码。但是，这次课程设计从选题开始，就给自己定了一个较高的要求。选的题是自己觉得可供选择的题中最难得一个，同时也力求独立

自主完成。在做这次课程设计的过程中，有遇到问题而一时又无法解决时的无奈，也有写代码调程序到深夜的艰辛，更有解决某个问题和最后成功的喜悦。

一般来讲，构想一个算法并不困难，难的是把设计的算法变成有效的代码。在代码的调试中，经常出现编译通过了，但运行时报错，而这类问题又很难查到，这就需要花时间和精力，没有足够的耐心是不行的。当遇到这类问题时，我常常不知所措。每每想要放弃时，都会想到我的程序员梦想，想到数模竞赛时的那股干劲和精神，这样又有了动力，重新开始调试。虽然有时一连几个小时都毫无进展，但我坚持下来了。最后写的程序基本上达到了预定目标，功能上完全达到了，只是没有容错能力，稳定性还不够强。

同时，经过这次的课程时机，我有了许多收获，意志得到了锻炼，获得了很多编程的经验。每每调试错误，我都会有新的发现，新的收获。能更好的利用现有的资源为我服务，当遇到错误时，往往能够找到我想要的。

在日后的学习中我会继续努力。好好学习天天向上。为社会主义代码事业尽一己薄力。