还剩7页未读,继续阅读
文本内容:
表达式求值目的利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目,利用C/C++语言进行程序设计,并规范地完成课程设计报告通过课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基本能力设计一个程序,演示以字符序列的形式输入不含变量的实数表达式求值的计算结果二需求分析设计一个程序,演示以字符序列的形式输入不含变量的实数表达式求值的计算结果对于这个程序我们从输入,输出,和功能三方面来分析
1.程序输入从键盘上输入表达式,一个算术表达式,由常量、运算符和括号组成(以字符串形式输入,不含变量)为了简化,操作数只能为浮点数,操作符为“+”、、“*”、“/、“(”、“)”,用#表示结束
2.程序输出表达式运算结果,运算符栈、运算数栈、输入字符和主要操作变化过程,如运算符栈、运算数栈的出入记录,字符出入栈的过程,打印出完整的过程功能要求及说明从犍盘上输入表达式分析该表达式是否合法(包含分母不能为零的情况)
(1)是数字,则判断该数字的合法性
(2)是规定的运算符,则根据规则进行处理在处理过程中,将计算该表达式的值
(3)若是其它字符,则返回错误信息若上述处理过程中没有发现错误,则认为该表达式合法,并打印处理结果三概要设计数据结构的选择任何一个表达式都是由操作符,运算符和界限符组成的我们分别用顺序栈来寄存表达式的操作数和运算符栈是限定于紧仅在表尾进行插入或者删除操作的线性表为了实现算符优先算法,可以使用两个工作栈一个称做,用以寄存运算符;另一个称做,用以寄存操作数或者运算结果首先置操作以上调试结果是正确的能够实现各个符号优先级先后顺序的运算,根据符号优先级(、)、+、-、*、/,如此顺序进行运算,实现了基本表达式运算的功能但是需要注意的是,这个程序功能并非那末完善,具体能实现的功能如下由于中英文字符的不同,加之本程序没有对中文字符加以处理,当从键盘输入的表达式中包含中文括号时程序无法正确的计算出结果,而是会报错!同样表达式中只能包含英文的运算符,输入中文的运算符时会报错!同样,从键盘输入的表达式必须要运算符匹配,例如括号要匹配,要成对浮现,由于本程序没有加以处理,遇到这种情况,程序会报错!七用户使用说明
1.使用环境:Visual C++
6.
0.
2.操作要求程序运行后,用户根据提示输入0—9之间的数字或者是字符以进入相应的功能处理函数程序调用建表功能函数后,用户将按照规定的方式输入你所要计算的表达式,最后可以计算出结果
3.用户需要从键盘输入正确的表达式,表达式中不可浮现中文符号,运算符要匹配
4.该程序支持整数,小数的运算,四则混合运算八课程设计总结数据结构的研究不仅涉及到计算机硬件的研究,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据元素在存储器中的分配问题在研究信息检索时也必须考虑如何组织数据,以便使查找和存取数据元素更为方便在课程设计中,应该力求算法简明易懂,而易于转换为上机程序;如果程序反复多次使用,则应该尽可能选用快速的算法;如果待解决的问题数据量极大,机器的存储空间较小,则在编写算法时应该考虑如何节省空间以后在编写程序时就应该注意到所编写程序的时间复杂度,以及是否运用了良好的算法,而不能只是像以前编写程序时单纯使用C语言的知识,要充分考虑程序的性能,争取编写出更优良的程序来经过两个星期的实际操作和搜索相关资料,终于让我完成为了任务让我对《数据结构》C语言有了更进一步的认识和了解,也让我知道,要想学好它要重在实践,理论与实际应用相结合,提高了自己组织数据及编写大型程序的能力,培养了基本的、良好的程序设计技能以及合作能力通过实际操作,我也发现我的好多不足之处1用栈的结构来解决表达式的求值,首先要解决的问题是如何将人们习惯书写的表达式转换成计算机容易处理的表达式开始有些茫然,后来通过结合课本和同学的匡助完成为了该课题2对一些看似简单的东西掌握不够熟练,比如由于函数的调用参数问题不熟而造成为了调试的艰难对于语法的掌握也欠缺成熟,需要进一步掌握栈的结构理解不够清晰,造成为了设计程序时理不清头绪,需要对数据结构有更深层次的3理解数栈为空栈,表达式起始符#作为运算符栈的栈底元素,然后挨次读入表达式的每一个字符,若是操作数则进入栈,若是运算符则和栈的栈顶运算符比较优先权后做相应操作,直至整个表达式求值完毕两个栈运算符栈运算数栈相关功能函数声明运算符栈建立函数声明运算数栈建立函数主要的确定如何入栈的函数声明入栈函数声明入栈函数声明取栈顶元素函数声明取栈顶元素函数声明出栈函数声明出栈函数声明比较函数通过这个函数我们来实现运算符运算的先后顺序判断运算符优先权,返回优先权高的算符间的优先关系如下+*/#+*/■#最后的计算函数:声明运算函数为了使运算的过程更加直观的反应出来,我们再绘制一个表格,绘制表格的相关函数如下从栈底到栈顶挨次输出各元素从栈底到栈顶挨次输出各元素函数模块之间的调用关系:主程序模块U栈的建立及初始化模块判断输入是否结束模块四详细设计首先本程序定义两个顺序栈运算符栈()和运算数栈();运算符栈运算数栈然后是主要功能函数的详细设计:运算符栈函数构造一个空栈存储分配失败!存储分配失败确定如何入栈的函数实现如下入栈如果栈满,追加存储空间存储分配失败!将元素压入栈中,指针上移实现提取栈顶元素的函数实现取栈顶元素运算符栈已空以及设计的一个在结果显示过程的栈中清单打印函数从栈底到栈顶挨次输出各元素核心的算法确定如何入栈函数的实现如下将入栈,作为低级运算符请输入不含变量的表达式(以结束)・•对表达式求值的操作过程如下:步骤运算符栈运算数栈输入字符主要操作输入的字符如果不是运算符号,则继续输入直到输入的是运算符为止,将非运算符转换成浮点数输入的是运算符非运算型数据计数器清零比较运算符的优先级栈顶元素优先级低,则入栈且继续输入栈顶元素优先级相等,脱括号并接收下一字符栈顶元素优先级高,则退栈并将运算结果入栈显示表达式最终结果表达式的结果为・表达式出错运算符的优先级比较函数实现如下运算符的优先级比较输入符号为、栈顶元素为、此时栈顶符号优先级低,返回否则,栈顶符号优先级高返回输入的符号为、栈顶元素为、、此时栈顶符号优先级高,返回否则,栈顶符号优先级低返回输入的符号为则直接返回输入的符号为栈顶元素为此时优先级同,返回否则,栈顶符号优先级高返回输入符号为其他栈顶元素为此时优先级同,返回否则,栈顶符号优先级高返回以及最后的计算函数运算函数从运算符栈取出的符号为,则运算数栈的两元素相加,并返回从运算符栈取出的符号为,则运算数栈的两元素相减,并返回从运算符栈取出的符号为,则运算数栈的两元素相乘,并返回从运算符栈取出的符号为,则运算数栈的两元素相除,并返回表达式出错除数不能为五调试分析.结构分析1栈中的数据节点是通过数组来存储的因为在C语言中数组是用下标从零开始的,因此我们在调用他们的数据是要特殊注意指针变量的值要末为空NULL,不指向任何结点;要末其值为非空,即它的值是一个结点的存储地址注意,当P为空值时,则它不指向任何结点,此时不能通过P来访问结点,否则会引起程序错误如果输入的数字不符合题目要求,则会产生错误结果算法的时空分析
2.时间和空间性能分析时间上,对于含个字符的表达式,无论是对其进行合法性检测还是对其进行入栈出栈操作次,因此其时间复杂度为空间上,由于是用数组来存储输入的表达式,用栈来存储运算中的数据和运算符,而栈的本质也用到的数组,数组在定义时必须确定其大小在不知表达式长度的情况下确定数组的长度确非易事,此时极易造成空间的浪费,因此空间性能不是很好六测试结果、实数混合运算。