- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
数据结构实验报告三
——简易计算器(二叉树)
姓名:任子龙学号:1120140167班级
一、需求分析
(1)问题描述
由键盘输入一算术表达式,以中缀形式输入,试编写程序将
中缀表达式转换成一棵二叉表达式树,通过对该二叉树的后序遍
历求出计算表达式的值。
(2)基本要求
a.要求对输入的表达式能判断出是否合法,不合法要有错误提
示信息。
b.将中缀表达式转换成二叉表达式树。
c.后序遍历求出表达式的值。
(3)数据结构与算法分析
一棵表达式树,它的树叶是操作数,如常量或变量名字,而
其他的结点为操作符。
a.建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。
当要创建二叉树时,先从表达式尾部向前有哪些信誉好的足球投注网站,找到第一个优先级最
低的运算符,建立以这个运算符为数据元素的根结点。注意到表达式
中此运算符的左边部分对应的二叉绔为根结点的左子树,右边部分对
应的是二叉绔为根结点的右子树,根据地这一点,可用递归调用自己
来完成对左右子树的构造。
b.求表达式的值。求值时同样可以采用递归的思想,对表达式进行
后序遍历。先递归调用自己计算左子树所代表的表达式的值,再递归
调用自己计算右子树代表的表达式的值,最后读取根结点中的运算
符,以刚才得到的左右子树的结果作为操作数加以计算,得到最终结
果。
(4)测试
a.加减运算
输入:6+9-5输出:10
b.乘除运算
输入:5.6*2.7/2输出:7.56
c.四则混合运算
输入:(2+3)*8-3/2输出:23.5
d.非法输入
输入:(5+6(*5输出:括号不匹配!
1.2问题分析
与之前利用栈实现计算器功能不同,本实验采取的方法是:将中
缀表达式转换成一棵二叉表达式树,通过对该树的后序遍历求出计算
表达式的值。所以,实验的重点是如何“将中缀表达式转换成一棵二
叉表达式树”;
如上图所示,该二叉表达式树表示的是计算式(5+2)*3。可以
看出,操作数均为叶子结点,其它结点为操作符;构建二叉树的整体
思路是:(1)将中缀表达式转化为后缀表达式;(2)利用(1)中
的后缀表达式,在此基础上构建二叉表达式树。
最后的求值,可以通过递归调用函数,后序遍历二叉树来完成。
二、概要设计
2.1抽象数据类型定义
本程序主要用到的数据结构是二叉链表,所以先行定义链表结点,
其中每一个节点包含两个数据域和两个指针域,数据域分别存放char
型变量和float型变量,相对应是运算符和操作数;指针域分别指向
两个左右孩子。
structnode{
chardata;
floatnumber;
structnode*left;
structnode*right;
};
另外,考虑到程序还需转换后缀表达式,所以又建立了另一种结点类
型变量,并定义其类型的数组array[20]:
structoprtnumber{
charsign;//存放符号型变量
floatnumber;//存放浮点数
}array[20];
2.2主程序流程
主函数流程如下:
intmain()
{
char*b,a[100],*t;
b=convert();//中缀表达式转为反序后缀表达式
do
{完成反序后缀式的逆向;
}
T=create(T,a);//create()函数创建二叉链表
postordertraverse(T);//后序遍历进行计算
输出结果;
}//main
2.3程序模块调用关系
具体关系如下图所示:
三、详细设计
3.1主函数的具体过程
intmain()
{structnode*T
您可能关注的文档
- 初中美术基于学科核心素养的课堂教学策略.pdf
- 初中生文明出行演讲稿(精选13篇).pdf
- 材料模拟软件:LIGGGHTS二次开发_LIGGGHTS中的流体力学模拟.docx
- 材料模拟软件:ANSYS二次开发_ANSYSWorkbench与二次开发集成.docx
- 材料科学软件:Materials Studio二次开发_高级用户界面设计与开发.docx
- 材料模拟软件:LIGGGHTS二次开发_LIGGGHTS的案例分析与应用实例.docx
- 材料设计软件:Materials Studio二次开发_使用Python进行二次开发.docx
- 材料设计软件:Materials Studio二次开发_高级图形与可视化技术.docx
- 材料科学软件:VASP二次开发_晶体结构与输入文件构建.docx
- 材料科学软件:Materials Studio二次开发_项目实战案例分析.docx
- 材料设计软件:Materials Explorer二次开发_必威体育精装版研究进展与应用.docx
- 材料设计软件:Materials Explorer二次开发_优化与性能提升.docx
- 材料科学软件:VASP二次开发_电子结构与性质计算.docx
- 材料模拟软件:COMSOL二次开发_API接口的使用与开发.docx
- 材料模拟软件:LIGGGHTS二次开发all.docx
- 材料科学软件:Materials Studio二次开发_常见问题与解决方案.docx
- 材料科学软件:Materials Studio二次开发all.docx
- 材料设计软件:Materials Studio二次开发_MaterialsStudio二次开发概述.docx
- 材料设计软件:Materials Explorer二次开发_二次开发项目实战.docx
- 材料模拟软件:OOF二次开发_案例分析与实践.docx
最近下载
- GB 19593-2015 烟花爆竹 组合烟花.pdf
- 工会十八大精神知识竞赛复习试题含答案.doc VIP
- 第一单元第1课《多样的美术门类》+课件+++++2024—2025学年赣美版初中美术七年级上册.pptx VIP
- 花卉鉴赏--草本花卉之球根花卉 唐菖蒲.pptx VIP
- 指南与共识:中国老年心肺复苏急诊专家共识(2024)解读PPT课件.pptx VIP
- 创意动漫教学ppt:日系动漫课件.pptx VIP
- 第四节 肉类的营养特点.docx
- 苏州市2023-2024学年高二上学期期中调研生物试题(原卷版).pdf VIP
- 2022工业视觉系统运维员实操.docx VIP
- GBT19017-2020 质量管理 技术状态管理指南.pdf
文档评论(0)