数据结构(表达式求值)课程设计.docx

课程设计报告课程名称：数据结构课程设计课程设计题目：表达式求值问题姓 名：系：计算机科学与技术专 业：计算机科学与技术年 级：2011级学 号：指导教师：职 称：讲师2011年 12月 31日目 录1.设计目的:12.设计要求:13.设计方案:14.设计内容:24.1．需求分析24.2．概要设计24.3.详细设计44.4.调试分析与结果74.5：使用说明115.总结：126.附录三：源代码12表达式求值问题1.设计目的:《数据结构课程设计》是计算机专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。其目的是： （1）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。 （2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。2.设计要求:以字符序列的形式从键盘输入语法正确的、不含变量的整数（或实数）表达式，实现对算术四则混合运算表达式的求值。当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号，对于异常表达式能给出错误提示。3.设计方案:任何一个表达式都是由操作符，运算符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素。为了实现算符优先算法。可以使用两个栈。一个称为OPF，用以寄存运算符，另一个称做OPS，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPS栈，若是运算符则和OPF栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPF栈的栈顶元素和当前读入的字符均为”#”）。4.设计内容:4.1．需求分析本程序所做的工作为：能直接求出四则表达式的值，并输出；本程序可用于小学教师对学生作业的快速批改以及对数值位数要求较大的科学运算。4.2．概要设计1.//用于存储操作数和运算结果（OPS）:ADT LinkStack{数据元素：此链栈中的所有元素类型为字符型的数字字符数据关系：栈中数据元素之间是线性关系。基本操作:（1）InitStack(LinkStack head)操作结果：构造一个空栈head（2）IsEmpty(LinkStack head)初始条件：栈head已存在操作结果：若栈为空栈，则返回TRUE,否则FALSE（3）Push(LinkStack head,ElementType element)初始条件：栈head已存在操作结果：插入元素element为新的栈顶元素（4）Pop(LinkStack head,ElementType element)初始条件：栈head已存在且非空操作结果：删除head的栈顶元素，并用e返回其值（5）GetTop(LinkStack head, ElementType element)初始条件：栈head已存在并且非空操作结果：用e返回head的栈顶元素（6）DestroyStack(LinkStack head)初始条件：栈head已存在操作结果：栈head 被销毁}ADT LinkStack2．//用于存储运算符(OPF)：ADT LinkCharStack{数据对象D：元素类型为字符型的符号字符数据关系R：基本操作：栈中数据元素之间是线性关系。（1）CInitStack(LinkCharStack head) 操作结果：构造一个空栈head（2）CIsEmpty(LinkCharStack head)初始条件：栈head已存在操作结果：若栈为空栈，则返回TRUE,否则FALSE（3）CPush(LinkCharStack head,ElementType element)初始条件：栈head已存在操作结果：插入元素element为新的栈顶元素（4）CPop(LinkCharStack head,ElementType element)初始条件：栈head已存在且非空操作结果：删除head的栈顶元素，并用e返回其值（5）CGetTop(LinkCharStack head, ElementType element)初始条件：栈head已存在并且非空操作结果：用e返回head的栈顶元素（6）CDestroyStack(LinkCharStack head)初始条件：栈head已存在操作结果：栈head 被销毁}ADT LinkCharStack3.系统中子程序及功能要求：Comop(char ch)：判断输入的字符是否为运算