数据结构课程设计利用线性表进行算式计算.doc
《数据结构课程设计利用线性表进行算式计算.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计利用线性表进行算式计算.doc(41页珍藏版)》请在沃文网上搜索。
1、数据结构试验报告 利用线性表进行算式计算一:问题描述:在计算机中,算术表达式由常量、变量、运算符号和括号组成,由于不同的运算符具有不同的优先级,又要考虑到括号,因此,算术表达式的求值不可能严格地从左往右进行,因而在程序设计时,借助栈实现。算法要点:设置运算符栈和运算数队列辅助分析算符优先关系,在读入表达式的字符序列的同时,完成运算符和运算数的识别处理,以及相应运算。二:需求分析1、输入的形式和输入值的范围一个算术表达式,由常量、变量、运算符和括号组成(以字符串的形式输入)。为简化,规定操作数只能为整数,操作符为“+”、“-”、“*”、“/”、“%”,用“#”开始且用“#”结束,优先级为:括号-
2、%-*,/-+,-。2、输出的形式即输出表达式运算结果,本算法中输出的形式为The end is:.3、程序所能达到的功能 界面上出现一个文本框,输入一个表达式(以“#”开始并以“#”结束,此表达式包括“+”、“-”、“*”、“/”、“%”、括号以及整数),点击回车,显示结果。4、测试结果 正确的输入一个表达式是指输入一个正确的表达式即不能连续输入两个运算符(括号除外),切以“#”开始以“#”结束,点击回车界面上出现The end is:即此表达式的结果。输入表达式错误有两种形式:(1)、所输入的表达式未以“#”开始则点击回车,系统会提示“RROE!Please begin with #“,“
3、且下面输出”Continue?(y/n):“,若输入Y或者y,则再次进入主界面输入表达式,若输入N或者n,则跳出系统。(2)、所输入的表达式错误,即连续输入两个运算符,此时系统会提示“ERROE!Please input another time!“,三:概要设计 主程序的流程图为 YNNY开始输入表达式输出结果结束输入表达式有误是否继续四:详细设计1、本系统中所用到的抽象数据类型有栈的抽象数据类型以及队列的抽象数据类型。栈的抽象数据类型定义:ADT Stack 数据对象:D=ai| ai ElemSet,i=1,2,3n,n0 数据关系:R1= ai-1, ai D,i=2,3n基本操作:
4、InitStack(&S)操作结果:构造一个空栈DestoryStack(&S)初始条件:栈S已存在。操作结果:栈S被销毁。ClearStack(&S)初始条件:栈S已存在。操作结果:将S清为空栈。 StackEmpty(&S)初始条件:栈S已存在。操作结果:若栈S为空栈,则返回TRUE,否则返回FALSE。StackLength(&S)初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。GetTop(S,&e)初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。Push(S,&e)初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。Pop(S,&e)初始条件:栈S已存
5、在且非空。操作结果:删除S的栈顶元素,并用e返回其值。StackTraverse(S,visit())初始条件:栈S已存在且非空。操作结果:从栈底到栈顶一次对S的每个元素调用函数visit()。一旦visit()失败,则操作失败。ADT stack队列的抽象数据类型定义:ADT Queue 数据对象:D=ai| ai ElemSet,i=1,2,3n,n0 数据关系:R1= -*(=%#=3、各模块间的层次调用(1).算法思路 a.若导入的是操作数,则直接输出到队列。 b.若当前运算符的优先级高于栈顶运算符的优先级,则入栈。 c.若当前运算符的优先级低于栈顶运算符的优先级,则栈顶运算符退栈,并
6、输出到队列,当前运算符再与新的栈顶运算符比较。 d.若当前运算符的优先级等于栈顶运算符的优先级,且栈顶运算符为左括号,当前运算符为右括号,则栈顶运算符退栈,继续读下一个符号。 e.若当前运算符的优先级等于栈顶运算符的优先级,且栈顶运算符为“#“,当前运算符也为”#“,则栈顶运算符退栈,输出队列中的数值即可。 (2).各个函数的含义 头函数结束以后用typedef struct snode 定义栈的结构体,void initiatels(slnode *h) 此函数是对栈的初始化,即构造一个空栈,void pushls( slnode *h,char *x) 、char *popls( slno
7、de *h,char *x) ,分别是进栈出栈函数的实现。typedef struct qnode 队列的结构体定义,typedef struct 此函数是对队列的初始化,即构造一个空队列,void initiatelq(lqtype *q) 、void enterlq(lqtype *q,char *x) ,分别是入队列以及出队列的实现。这就是函数模块的实现,除此之外在主函数main()函数中利用函数while(c!=“#“) 即可获取屏幕上输入的字符,数据和运算符并分别将其存放在结点中,利用函数while(x【0】!=35) 来判断x进入符号栈还是队列,enterlq(operand,x)
8、;说明x是数据则进入队列,利用函数if(a=b) 判断如果x的优先级大于当前栈顶元素的优先级,则进栈。利用函数if(y【0】=40) 判断如果x是”)“,则依次输出符号栈的元素,放进队列中,直到遇到”(“为止,否则else函数表示mid为空后,一次输出符号栈的元素至队列中,直到遇到”#“为止。五:调试分析本实验要调试成功在此之前肯定遇到很多困难经常会出现一些说明语法错误以及出现一些语法错误等各种各样的问题,此时要检查自己的代码,找到自己代码的问题所在,不折不挠多次调试即可。本实验的时间复杂度是O(n),空间复杂度为O(n)。此实验是利用一个栈和一个队列,可以改进为两个栈的运算,一个栈存放运算符
9、,另外一个栈存放运算数据。本实验算法采用了链式存储结构,以开辟新空间为代价,有效降低了算法时间复杂度和空间复杂度,并且对表达式的长度没有要求。六:测试结果 调试成功后进入的页面为输入正确的表达式后点击y重新进入主页面若输入错误的表达式后七:附录源程序#include#include #include#include#include#include#define null 0typedef struct snode /定义结构体 char data11;struct snode *next;slnode;void initiatels(slnode *h) /初始化 h-next = null;
10、 void pushls( slnode *h,char *x) /压栈 slnode *p; p = (slnode *)malloc(sizeof(slnode); strcpy(p-data,x); p-next = h-next; h-next = p; char *popls( slnode *h,char *x) /出栈 slnode *p; p = h-next; if(p!=null) h-next = p-next; return(p-data); return(x); typedef struct qnode /定义链队列结构体 char data11;struct qno
11、de *next;qlnode;typedef struct qlnode *h; qlnode *rear; lqtype;void initiatelq(lqtype *q) /初始化 q-rear = q-h; q-h-next = null;void enterlq(lqtype *q,char *x) /入队qlnode *p; p = (qlnode *)malloc(sizeof(qlnode);/申请新结点strcpy(p-data,x); /新结点数据域赋值 p-next = null;if(q-h=null)q-h = p;q-rear-next = p;q-rear =
12、p; /修改尾指针char *deletelq(lqtype *q,char *x) /出队 qlnode *p; p = q-h-next; / 暂存原队头指针 if(q-h-next!=null) /队非空 q-h-next=p-next; /删除队头元素 if(q-h-next=null) q-rear-next=null; return(p-data); return(x); void main() char ch8=#,+,-,*,/,%,(,); char c,cc, x11,y11,z11; int i,j,a,b,n; int t; slnode *operater,*pp;
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 利用 线性 进行 算式 计算