数据结构课程设计2.docx
《数据结构课程设计2.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计2.docx（8页珍藏版）》请在冰点文库上搜索。
数据结构课程设计2
课程设计说明书
课程名称：
数据结构
设计题目：
表达式求值
院系：
学生姓名：
学号：
专业班级：
指导教师：
2011年6月25日
课程设计任务书
设计题目
表达式求值
学生姓名
所在院系
计科学院
专业、年级、班
设计要求：
1.计算表达式手工录入，计算结果必须正确
2.支持两位以上的整数和浮点数的运算
3.运算符优先级表可在程序中直接通过代码初始化
4.能够检查表达式是否合法，对于错误的表达式要能够给出错误原因。
学生应完成的工作：
设计一个能够计算表达式的程序，要求能够对包含加、减、乘、除、括号运算符的表达式进行计算，并能显示出一定的错误及错误分析。
参考文献阅读：
严蔚敏吴伟民编著《数据结构》（C语言版）清华大学出版社2010年10月
（美）克林伯格编著《算法设计》清华大学出版社2007年6月
王晓东 编著《算法设计与分析》（第三版）电子工业出版社2007年5月
工作计划：
1、第一周的第一天：
小组布置设计题目；说明进度安排。
2、第一周的第二天：
小组审题，查阅资料，进行设计前的必要资料准备。
3、第一周的第三天、第四天、第五天：
程序编写、上机调试
4、第二周的第一天至第三天：
上机调试程序、结果分析。
5、第二周的第四天：
撰写设计报告。
6、第二周的第五天：
设计答辩及成绩评定。
任务下达日期：
2011年6月13日
任务完成日期：
2011年6月25日
指导教师（签名）：
学生（签名）：
表达式求值
摘要：
表达式求值是程序设计语言编译中的一个最基本的问题。
它的实现是栈应用的一个典型例子。
我们使用的是一种简单直观，广为使用的算法—“算符优先法”。
要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。
要知道算法四则运算即
（1）先乘除，后加减；
（2）从左到右；（3）先括号内，后括号外。
算法优先级法就是根据这个运算优先级的规定来实现对表达式的编译或解释执行的。
任何一个表达式都是由操作数，运算符和界限符组成的，我们称之它们为单词。
一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符，关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。
关键词：
表达式栈（出战，入栈）括号匹配符号优先级运算
目录
一.设计背景………………………………………………………………3
1.1．目的……………………………………………………………3
1.2．背景……………………………………………………………3
二.设计方案………………………………………………………………3
3.方案实施……………………………………………………………4
3.1运算………………………………………………………………4
4.结果与结论…………………………………………………………6
4.1.运算结果…………………………………………………………6
4.2.结论………………………………………………………………7
5.收获与致谢……………………………………………………………7
5.1.收获………………………………………………………………7
5.2.致谢………………………………………………………………7
六．参考文献……………………………………………………………8
八．指导教师评语………………………………………………………9
一.设计背景
1.1．目的
通过课程设计，巩固和加深对栈的理论知识的理解；掌握现实复杂问题的分析和解决方法；提高利用计算机分析解决综合性实际问题的基本能力。
1.2．背景
“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理科专业的热门选修课。
栈是重要的线性结构，从数据结构角度看，栈也是线性表，其特点在于栈的基本操作是线性表操作的子集，它的操作受限的线性表，因此，可称为限定性的数据结构。
但从数据类型角度看，它是和线性表大不相同的一类重要的抽象数据类型。
由于栈广泛应用在各种软件系统中，因此在面向对象的程序设计中，它是多型数据类型。
表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。
2.设计方案
我负责的部分是求值的过程，使OPTR和OPND分别为运算符栈和运算数栈，算法的基本思想是：
（1）首先置操作数栈为栈，表达式起始符“=”为运算符栈的栈底元素。
（2）依次读入表达式中的每一个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和读入的字符均为“=”）。
三.方案实施
3.1.运算
SElemTypeEvaluateExpression（）
{SqStackOPTR,OPND;
SElemTypea,b,x,theta;
charc;//存放由键盘接收的字符串
charz[6];//存放整数字符串
inti;
floatf;
InitStack（OPTR）;//构造一个运算符栈
Push（OPTR,'='）;//将“=”号压入栈底
InitStack（OPND）;//构造一个运算数栈
c=getchar（）;
while（c!
='='||GetTop（OPTR）!
='='）//栈顶不是“=”号且输入不是“=”号
{
if（In（c））//输入的字符为运算符
switch（Precede（GetTop（OPTR）,c））
{
case'<':
//栈顶元素优先权低
Push（OPTR,c）;
c=getchar（）;
break;
case'=':
//脱括号并接下一个字符
Pop（OPTR,x）;
c=getchar（）;
break;
case'>':
退栈并将运算结果入栈
Pop（OPTR,theta）;
Pop（OPND,b）;
Pop（OPND,a）;
Push（OPND,Operate（a,theta,b））;
}
elseif（c>='0'&&c<='9'||c=='.'）{
if（c>='0'&&c<='9'）
i=0;
do
{
z[i]=c;
i++;
c=getchar（）;
}while（c>='0'&&c<='9'）;
intd=z[i-1]-48;
inte1=1;
for（intj=i-2;j>=0;j--）
{
e1=e1*10;
d=d+（z[j]-48）*e1;
}
if（c=='.'）
c=getchar（）;
floatdigit=0.0,e=0.1;
while（c>='0'&&c<='9'）
{
digit=digit+（c-48）*e;
e=e*0.1;
c=getchar（）;
}
f=（float）d+digit;
Push（OPND,f）;
}
else//不能出现除了“+”，“-”，“*”，“/”以及小数点“.”，“=”和操作数以外的非法字符
{
printf（"******************************\n"）;
printf（"*出现了非法字符或没有以=结尾!
*\n"）;
printf（"******************************\n"）;
exit（0）;
}
}
returnGetTop（OPND）;
returnOK;
}
四.结果与结论
4.1．运算结果
1.当出现非法字符或者是没有以“=”结尾时：
图.1
图.1表示运算表达式中不能出现非法字符
2.没有以“=”号结尾时
图.2
图.2表示运算表达式要以“=”号结尾
结论：
在本次课程设计的程序所支持的表达式进行运算时不能出现非法字符，表达式必须要以“=”号结尾。
五.收获与致谢
5.1.收获
通过这次课程设计，不仅仅让我知道自己的只是还远远不够，复习了我的Ｃ语
言的相关知识、还巩固了数据结构关于栈的算法的知识，更锻炼了我的意志。
5.2.致谢
通过这次的课程设计让我知道了老师说的很对，上课认真听下课多多的动手操作很重要，在这里非常感谢孙老师这半年来交给我们的知识，雅瑶感谢我的组员们特别是组长，让我了解到团结真的很重要。
六.参考文献
[1]严蔚敏，吴伟民．《数据结构》（C语言版）清华大学出版社2010年10月
[2]（美）克林伯格．《算法设计》清华大学出版社2007年6月
［３］王晓东．《算法设计与分析》（第三版）电子工业出版社2007年5月
指导教师评语：
1、课程设计报告：
a、内容：
不完整□完整□详细□
b、方案设计：
较差□合理□非常合理□
c、实现：
未实现□部分实现□全部实现□
d、文档格式：
不规范□基本规范□规范□
2、出勤：
全勤□缺勤次
3、答辩：
a、未能完全理解题目，答辩情况较差□
b、部分理解题目，部分问题回答正确□
c、理解题目较清楚，问题回答基本正确□
d、理解题目透彻，问题回答流利□
课程设计报告成绩：
，占总成绩比例：
50%
课程设计其它环节成绩：
环节名称：
出勤，成绩：
，占总成绩比例：
20%
环节名称：
答辩，成绩：
，占总成绩比例：
30%
总成绩：
指导教师签字：
年月日
升级会员 