算法与数据结构设计.doc

《算法与数据结构设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构设计报告（2011/2012学年第二学期）题目：算术表达式的求解专业学生姓名班级学号指导教师指导单位日期年月日评分细则评分项优秀良好中等差遵守机房规章制度上机时的表现学习态度程序准备情况程序设计能力团队合作精神课题功能实现情况算法设计合理性用户界面设计报告书写认真程度内容详实程度文字表达熟练程度回答问题准确度简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格一、课题名称算术表达式的求解二、课题内容和要求设计要求：给定一个算术表达式，通过程序求出最后的结果。（1）从键盘输入要求解的算术表达式；（2）采用栈结构进行算术表达式的求解过程；（3）能够判断算

2、术表达式正确与否；（4）对于错误表达式给出提示；（5）对于正确的表达式给出最后的结果。三、需求分析首先通过键盘输入表达式并将字符串入栈,然后按从左到右的循环判断表达式的格式正确与否，当表达式的+，-，×，/,ˆ，()等运算符号间有两个小数点时，表达式为错误，给出错误提示并转到起始环节，然后根据给定运算顺序来做运算，有括号要先算括号里面的，计算的结果赋值到浮点型数据并输出结果。四、概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和成员函数原型声明）。1.栈的建立先

3、建立两个不同的栈分别存放运算符号和数字，然后初始化栈。当从键盘输入符号时，首先判断输入的是否是括号，若是，则在括号标志位置1，再判断是否是负号，若为负，则再输入一位，并将负号标志位置1；输入字符不满足要求时，提示错误，重新输入；（1）、定义栈的抽象数据类型定义：ADTStack{数据对象：D={ai

4、ai∈DateType,i=1,2,……，n，n>=0}数据关系：R1={

5、ai-1,ai∈D,i=2,……,n}基本操作：InitStack(&S)（2）、栈类型思想：本程序中栈采用的链式存储结构，因为存放操作符和操作数的结点类型不一样，所以设计了两个结点。栈的基本操作采用了重

6、载的方法，使两种结点类型都能使用。（1）、存放操作符的结点：structnode2{chardata2;//存放操作符node2*next2;};（2）、存放操作数的结点：structnode{doubledata;//存放操作数node*next;};2.数字输入当字符是数字时，若紧接该字符之后的仍然是数字，则说明输入的为多位数，按十进制算法*10相加得到实数a入栈。3.符号输入输入符号时，根据不同的标志位，有不同的处理方法：若两运算符相连，提示错误，重新输入；当有左括号时，根据标志位判断，若未找到右括号，则提示输入错误，重新输入。4.运算符号栈中运算符号op出栈，数字栈中的数字出栈并赋值给

7、a，b，根据给定的运算优先级（括号，*，/,+，-，ˆ），在除数b不为0的条件下，调用Execute(floata,charop,floatb)函数，得出结果v，压入栈中，若之前有负号（负号标志位位为1），则求其相反数v=-v，并将结果压入数字栈中，然后不断循环，直到遇到“=”停止，然后从数字栈输出结果。5、本程序包含的三个模块（1）、主程序模块；(2)、栈模块——实现栈抽象数据类型；（3）、表达式求解模块——求解表达式值的抽象数据类型；主程序模块表达式求解模块栈模块三个模块之间的调用关系如上图所示。6、函数的调用关系图：主程序s.Output()s.Put()s.Help()退出程序五、详细

8、设计各个算法实现的源程序（可以是一组源程序，每个功能模块采用不同的函数实现），源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。源程序代码：#includeusingnamespacestd;#defineStack_Size1000#defineStack_Float1000#defineTRUE1#defineFALSE0typedefstruct//建立数字栈{floatelem[Stack_Float];inttop;}Stack_float;voidInitStack(Stack_float*S)//初始化栈{S->

9、top=-1;}intPush(Stack_float*S,floate)//进栈{if(S->top==Stack_Float-1)return(FALSE);else{S->top++;S->elem[S->top]=e;return(TRUE);}}intPop(Stack_float*S,float*x)//出栈{if(S->top==-1)return(FALSE);else{*x=S-