数据结构课程设计报告十进制二叉树四则运算计算器设计与实现.doc
《数据结构课程设计报告十进制二叉树四则运算计算器设计与实现.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计报告十进制二叉树四则运算计算器设计与实现.doc(18页珍藏版)》请在三一文库上搜索。
1、成绩 中国农业大学课程设计报告书(2010-2011学年夏季学期)设计题目:十进制四则运算计算器设计与实现 课程名称: 数据结构 任课教师: 彭 波 班级: 试验092 学号: 0958020205 姓名: 曹 津 课程设计报告书格式要求(封皮的背面):1. 课程设计报告书采用统一封面,以左侧为准装订成册。2. 课程设计报告书一律使用标准A4复印纸打印或使用标准A4复印纸手写稿形式上交。3. 课程设计报告书打印的格式要求:课程设计标题(使用隶书二号字体加黑;一级标题、二级标题分别使用黑体三号、四号字体加黑)正文(使用宋体小四号,行距20磅)算法代码及源程序代码(使用Times New Roma
2、n五号)十进制四则运算计算器设计与实现1. 问题描述(1) 题目要求:利用二叉树表示算术表达式的基础上,设计实现一个十进制的四则运算计算器。(2) 基本要求:由用户输入中缀四则运算表达式,由程序计算所输入四则运算表达式的结果并输出。(3) 测试数据:12 - ( - 4 ) * ( ( 20 + 3 / 5 ) * 8 / 5 ) * ( - 4 ) #- ( 22.7 - 4208.3 ) / ( ( 2.4 + 1.6 ) * 12 ) + 4.4 - 2.9 #10 - ( - 3 ) * ( ( 21 + 3 / 5 ) * 8 / 3 ) * ( - 2 ) # 运行结果:-515.
3、36 88.7 -335.62. 需求分析(1) 本程序用于求出用户输入的任意合法四则运算表达式的值。(2) 程序运行后显示提示信息,由用户输入任意四则运算表达式,倘若所输入的表达式不合法程序将报错。(3) 用户输入四则运算表达式完毕,程序将输出运算结果。(4) 测试用的表达式须是由+、-、*、/运算符,括号“(”、“)”与相应的运算数组成。运算数可以是无符号浮点型或整型,范围在065535。3. 概要设计为了实现上述程序功能,应以字符串表示用户输入的表达式,进而将用户输入的表达式转化为二叉树形式存储供计算的类型。期间还须用到堆栈数据类型。(1) 二叉树的抽象数据类型定义ADT BinaryT
4、ree 数据对象:表达式运算数 num | 0 num 65535 表达式运算符 opr | + , - , * , / 数据关系:由一个根结点和两棵互不相交的左右子树构成,且树中结点具有层次关系。根结点必须为运算符,叶子结点必须为运算数。基本操作: InitBiTree(&T , &S) 初始条件:存在一四则运算前缀表达式S。 操作结果:根据前缀表达式S构造相应的二叉树T。 DestroyBiTree(&T) 初始条件:二叉树T已经存在。 操作结果:销毁T。 Value(&T) 初始条件:二叉树T已经存在。 操作结果:计算出T所表示的四则运算表达式的值并返回。ADT BineryTree(2
5、) 顺序栈的抽象数据类型定义ADT Stack 数据对象:具有相同类型及后进先出特性的数据元素集合。 数据关系:相邻数据元素具有前去和后继关系。 基本操作: InitStack(&S) 初始条件:无 操作结果:构造一个空栈S。 DestroyStack(&S) 初始条件:栈S已经存在。 操作结果:销毁S。 StackLength(&S) 初始条件:栈S已经存在。 操作结果:返回S中元素个数。 GetTop(S , &e) 初始条件:栈S已经存在且非空。 操作结果:用e返回S的栈顶元素。 Push(&S , e) 初始条件:栈S已经存在。 操作结果:插入元素e为S的新栈顶元素。 Pop(&S ,
6、 e) 初始条件:栈S已经存在且非空。 操作结果:删除S的栈顶元素,并用e返回其值。ADT Stack(3) 字符串的抽象数据类型定义ADT String 数据对象:具有字符类型的数据元素集合。 数据关系:相邻数据元素具有前驱和后继关系。 基本操作: StrLength(S) 初始条件:串S已经存在。 操作结果:返回S的元素个数。 StrNeg(S , F) 初始条件:串S已经存在且非空。 操作结果:求S的逆序并将结果保存在串F中。ADT String(4) 本程序包含四个模块:主程序模块;二叉树单元模块(实现二叉树的抽象数据类型,包括结点和指针的定义);顺序栈单元模块(实现顺序栈的抽象数据类
7、型,包含结点和指针的定义);字符串单元模块(实现字符串的抽象数据类型)。四个模块之间调用关系如下: 4. 详细设计(1) 顺序栈类型。#define Stack_Size 100typedef struct char elemStack_Size; int top;SqStack 基本操作实现的伪代码算法如下: void InitStack (SqStack &S) /初始化顺序栈 S.elem=new ElemTypeStack_Size; if(!S.elem) Error(Overflow!); S.top=-1; viod Push (SqStack &S,char c) /顺序栈压栈
8、 if(S.top=(Stack_Size-1) Error(Stack Overflow!); S.elem+S.top=c; ElemType Pop (SqStack &S) /顺序栈出栈 if(S.top=-1) Error(Stack Empty!); return S.elemS.top-; int StackLength(SqStack &S) /求顺序栈长度 return (S.top+1); GetTop(SqStack &S ,char e) /取栈顶元素 e=S.elemtop; (2) 字符串类型typedef struct /动态顺序串 char *ch; int l
9、ength;String基本操作实现的伪代码算法如下:int StrLength(&S) /求串长 return S.length; void StrNeg(&S , &F) /求逆序串if(!S.length) error(“String Empty!”); for(i=0 ; i=0 ; i-) /对输入串逆序扫描 if(Str.chi=48&Str.chi=Precedence( GetTop(S) ) ) Push( S , Str.chi ); break; else Pop(S , e); Output.chi=e; Output.length+; if( Str.chi=( )
10、/假如是左括号,栈中运算符逐个出栈并输出,直到遇到右括号。右括号出栈并丢弃。 while( GetTop(S)!=) ) Output.chi=Pop(S); Output.length+; while(S.top!=-1) /假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。 Output.ch=Output.ch-; Output.ch=Pop(S); return output;void CreatBiTree(&T , &S) /由中缀表达式生成表达式二叉树 String F; SqStack Sq; /用以存放生成的二叉树结点 InitStack(Sq); F=Convert(S
11、); /求得S的前缀表达式 for(i=F.length-1 ; i=0 ; i-) If( !IsOperator(F.chi) ) T=new TNode; T-data=F.chi; T-lchild=NULL; T-rchild=NULL; Push(Sq , T) else T=new TNode; T-data=F.chi; T-lchild=Pop( Sq ); T-rchild=Pop( Sq ); Push(Sq , T); int Calc(int a, char opr, int b) /计算 switch (opr) case +: return a + b; case
12、 -: return a - b; case *: return a * b; case /: return a / b; int Value(TNode *T) if (T-lchild = NULL &T-rchild = NULL) return T-data; else return Calc( Value(T-lchild) , T-data , Value(T-rchild) );(4) 主函数伪码算法。void main() Face(); /输出界面及相关信息 do cout”Please input an expression:”Str; JudgeExp(S); /判断输入
13、的表达式是否合法。 T=CreatBiTree(S);N=Value(T); cout”The value of this expression is”Nendl;coute; if(e=y) flag=1;else flag=0; while(flag) /main(5) 函数调用关系图。5. 调试分析(1) 程序中使用的字符串类型可直接引用C+自带的类型库,没必要自行定义。(2) 算法时间复杂度分析。对于由表达式字符串生成二叉树的操作,由于是对字符串顺序扫描根据扫描到当前字符的情况决定操作,以n代表输入的表达式字符串长度,则此算法时间复杂度为0(n)。对于二叉树求值操作,由结点数量决定时间
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 十进制 二叉 四则运算 计算器 设计 实现
链接地址:https://www.31doc.com/p-9957065.html