数据结构课程设计.docx
- 文档编号:9490184
- 上传时间:2023-05-19
- 格式:DOCX
- 页数:17
- 大小:103.78KB
数据结构课程设计.docx
《数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计.docx(17页珍藏版)》请在冰点文库上搜索。
数据结构课程设计
信息科学与工程学院课程设计任务书
题目:
表达式求值
姓名:
学号:
专业:
课程:
数据结构
指导教师:
完成时间:
2011年11月----2011年12月
信息科学与工程学院制
课程设计任务书及成绩评定
课程设计的任务和具体要求
通过课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基本能力。
指导教师签字:
日期:
指导教师评语
成绩:
指导教师签字:
日期:
课程设计所需软件、硬件等
Pc机、WIN-T
课程设计进度计划
起至日期
工作内容
备注
11月28日-11月30日
12月1日-12月4日
12月5日-12月13日
分析课程设计任务要求并合理安排工作
进行设备配置及测设验证
编写课程设计任务书及排版
认真仔细的分析搜索的资料
参考文献、资料索引
序号
文献、资料名称
编著者
出版单位
1、《数据结构》蒋秀英中国石油大学出版社
2、《数据结构(C语言版)》严蔚敏清华大学出版社
3、《C语言程序设计》丁峻岭中国铁道出版社
4、《C程序设计》谭浩强清华大学出版社
表达式求值
一目的
通过课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基本能力。
二需求分析
此次课程设计的目标是能够设计一个程序,演示算术表达式求值的过程。
①输入的形式和输入值的范围:
以字符串的形式输入表达式,以换行符结束;
②输出的形式:
在计算过程中遇到的问题或最终的答案将回显到屏幕上,同时所计算的表达式和最终的显示也将保存至文件中;
③程序所能达到的功能:
能够处理以字符序列的形式输入的不含变量的实数表达式,正确处理负数与小数,判断表达式是否语法正确(包含分母不能为零的情况),正确实现对算术四则混合运算表达式的求值,能够将计算中遇到的问题和结果以文件的形式予以存储;
④初步的测试计划:
当输入正确表达式时,以换行符结束,能得到最终的正确结果;当输入含有非正常符号的错误表达式时,以换行符结束,能得到最终的提示语句;当遇到分数为0的轻快是,能得到提示语句。
三概要设计
1、本程序中用到的数据类型
该设计主要运用的是栈的知识。
为实现表达式求值的功能,需分别定义数字栈与符号栈。
其结构体定义如下:
typedefstructtagstack1{/*数据栈*/
double*base;/*栈底指针*/
inttop;/*栈顶*/
intlen;/*栈的容量*/
}STACK1;
typedefstructtagstack2{/*符号栈*/
char*base;/*栈底指针*/
inttop;/*栈顶*/
intlen;/*栈的容量*/
}STACK2;
为了便于标记程序运行的正确与否,为了便于文件指针的应用,该程序定义了两个全局变量,如下:
intwr=0;/*wr用于标记是否出错*/
FILE*fp;/*指向文件的指针*/
2、程序的简单流程与主要函数
该设计主要在主函数中通过while循环来多次调用对一个表达式的处理函数ss();函数ss()调用了多个函数来实现对一个表达式的处理功能,其中,主要的函数如下:
charDealNbr(STACK1*S,chara,char**pstr,int*i)
/*若字符a是数字字符,则从字符串*pstr中继续读取字符,将数字整体的读出后,进行处理,并将最后的数字如数字栈S*/
charCompare(chara,charb)
/*比较两字符的优先级,若a较高则返回字符>,相同则返回=,较低则返回<*/
doublecalculate(doublea,doubleb,charc)
/*计算数字a与数字b经运算符c计算后的结果,并返回*/
intchange(charc)/*获得符号c的优先级*/
voidInit1(STACK1*S)/*初始化数据栈S*/
voidFull1(STACK1*S)/*判断栈是否已满若满则追加空间*/
intEmpty1(STACK1S)/*判断栈是否为空若为空则返回真值*/
voidPush1(STACK1*S,doublee)/*数据e入栈*/
voidPop1(STACK1*S,double*e)/*数据出栈用e返回*/
doubleGetTop1(STACK1S)/*返回栈顶数据*/
符号栈的有关符号与数字栈相似,不重复记录。
3、函数之间的调用关系
main()->ss();
ss()->DealNbr();Compare();calculate();change();
Init1();Push1();Empty1();Pop1();GetTop1();等一系列栈的函数
四详细设计
1、Init1(STACK1*S):
voidInit1(STACK1*S){/*初始化数据栈*/
(*S).len=StackSize;
(*S).base=(double*)malloc(sizeof(double)*StackSize);
if(!
(*S).base){
wr=1;
printf("\n\nSpace!
!
");
fprintf(fp,"Space!
!
\n\n");
return;
}(*S).top=-1;
}
令栈初始容量为StackSize,并为栈底指针分配相应空间。
若未分配成功,则标记出错,否则,令栈顶为-1,此时,栈内没有元素;
2、Push1(STACK1*S,doublee):
voidPush1(STACK1*S,doublee){/*数据e入栈*/
Full1(S);
(*S).top++;
*((*S).base+(*S).top)=e;
}
先判断栈是否已满,若满则增加空间。
令栈顶自加,并将元素入栈。
3、Pop1(STACK1*S,double*e):
voidPop1(STACK1*S,double*e){/*数据出栈用e返回*/
if((*S).top==-1){
wr=1;
printf("\n\nArithmeticexpressionwrong!
!
");
fprintf(fp,"Arithmeticexpressionwrong!
!
\n\n");
return;
}
*e=*((*S).base+(*S).top);
(*S).top--;
}
若栈为空,则提示出错,否则,用e返回栈顶元素,并令top自减。
数字栈的相关函数与符号栈相似,在此,符号栈相关函数的定义将不再重复。
4、DealNbr(STACK1*S,chara,char**pstr,int*i):
charDealNbr(STACK1*S,chara,char**pstr,int*i){
/*数字字符则进行处理并入栈*/
doubled1=0,d2=1;
while(a>='0'&&a<='9'){a-='0';d1=d1*10+a;a=(*pstr)[(*i)++];}
if(a=='.')
{a=(*pstr)[(*i)++];
while(a>='0'&&a<='9'){
d2/=10;
a-='0';
d1+=d2*a;
a=(*pstr)[(*i)++];
}/*while*/
}/*if*/
Push1(S,d1);
returna;
}
若字符a是数字字符,则继续从字符串中读取字符,直到不再是数字字符,处理后保存在d1中;若紧接着是小数点字符,则说明此数为实数;继续读取字符,若是数字字符则继续处理,直到不再是数字字符。
最终将字符串中的一串数字字符转化为实数,并将此数入数字栈。
5、change(charc):
intchange(charc){/*获得符号c的优先级*/
if(c=='\x0')return1;
if(c=='+'||c=='-')return2;
if(c=='*'||c=='/')return3;
if(c=='('||c==')')return4;
return0;
}
因字符串的最后一个字符为’\x0’,所以令其的优先级最低;令’+’和’-’为2,比乘除和括号要低;令’*’和’/’的优先级为3,比括号低;令括号的优先级最高。
6、Compare(chara,charb):
charCompare(chara,charb){/*比较两字符的优先级*/
if(a=='('&&b==')')return'=';
if(a==')'&&b=='('){
wr=1;
printf("\n\nArithmeticexpressionwrong!
!
");
fprintf(fp,"Arithmeticexpressionwrong!
!
\n\n");
return0;
}
if(a=='('||b=='(')return'<';
if(a==')'||b==')')return'>';
if(change(a)>=change(b))return'>';
elsereturn'<';
}
左右括号的级别相同;若右括号紧接左括号,则表达式出错;若左括号紧接左括号,则后面的括号优先级较高;若右括号紧接右括号,则前面的括号优先级较高;其他情况下,则是change值较大的或位置比较靠前的字符优先级高;
7、calculate(doublea,doubleb,charc):
doublecalculate(doublea,doubleb,charc){/*计算数字a与数字b经运算符c计算后的结果,并返回*/
switch(c){
case'+':
returna+b;
case'-':
returna-b;
case'*':
returna*b;
case'/':
if(!
b){
wr=1;
printf("\n\nDivisoriszero!
!
");
fprintf(fp,"Divisoriszero!
!
\n\n");
returnFALSE;
}returna/b;
default:
wr=1;
printf("\n\nArithmeticexpressionwrong!
!
");
fprintf(fp,"Arithmeticexpressionwrong!
!
\n\n");
returnFALSE;
}/*switch*/
}/*calculate*/
运用switch语句,不同的运算符则进行不同的运算;进行除法时,若分母为0,则将标志标记成错误,并退出这个函数;若不是运算符,则同样标志错误,退出函数。
8、ss(double*a,char**pstr):
intss(double*a,char**pstr){/*对表达式的处理*/
STACK1OPND;
STACK2OPTR;
doublenbr1=0,nbr2=0;
charc=0,d=0,e=0;
inti=0;
Init1(&OPND);
Init2(&OPTR);/*初始化*/
if(wr)returnFALSE;/*空间分配不成功*/
Push1(&OPND,0);/*默认数据栈中的初始化元素为0*/
Push2(&OPTR,'0');/*将符号零入符号栈作为标记*/
c=(*pstr)[i++];/*取得输入字符串的第一个字符*/
if(c=='(')
Pop1(&OPND,&nbr1);/*若第一个字符为左括号则将0出栈*/
if(c>='0'&&c<='9'){
Pop1(&OPND,&nbr1);
c=DealNbr(&OPND,c,pstr,&i);
}/*若为数字字符则0出栈并将数字处理后入数字栈*/
while(c!
='\0'||GetTop2(OPTR)!
='0'){
/*循环条件为字符均已处理或符号栈中的字符均已计算*/
if(c>='0'&&c<='9'){
if(GetTop2(OPTR)=='(')Pop1(&OPND,&nbr1);
/*若前一个字符为左括号则将0出栈*/
c=DealNbr(&OPND,c,pstr,&i);/*处理数字并入数字栈*/
if(e=='='){/*若前一个符号为右括号则出错*/
wr=1;
printf("\n\nArithmeticexpressionwrong!
!
");
fprintf(fp,"Arithmeticexpressionwrong!
!
\n\n");
}
if(wr)returnFALSE;/*空间分配不成功*/
}/*if*/
if(!
change(c)){/*未知符号存在*/
wr=1;
printf("\n\nWrongcharacterexist!
!
");
fprintf(fp,"Wrongcharacterexist!
!
\n\n");
returnFALSE;
}
if(c=='('){/*若收到左括号则将0入数字栈便于处理负数*/
Push1(&OPND,0);
if(wr)returnFALSE;/*空间分配不成功*/
}
e=Compare(GetTop2(OPTR),c);/*比较栈顶符号与当前符号的优先级*/
switch(e){
case'<':
Push2(&OPTR,c);/*若当前符号优先级高则入栈*/
if(wr)returnFALSE;/*空间分配不成功*/
c=(*pstr)[i++];/*读取下一个字符*/
break;
case'=':
Pop2(&OPTR,&d);/*若两符号优先级相同则为左右括号出栈*/
c=(*pstr)[i++];
break;
case'>':
Pop2(&OPTR,&d);
/*若栈顶符号的优先级高则出栈并计算将结果入数字栈*/
Pop1(&OPND,&nbr1);
Pop1(&OPND,&nbr2);
if(wr)returnFALSE;/*栈空*/
nbr1=calculate(nbr2,nbr1,d);
if(wr)returnFALSE;/*除数为零*/
Push1(&OPND,nbr1);if(wr)returnFALSE;/*空间分配不成功*/
break;
}/*switch*/
/*else*/
}/*while*/
Pop1(&OPND,a);/*将数字栈栈顶数据出栈放入a*/
if(Empty1(OPND)&&GetTop2(OPTR)=='0')returnTRUE;
/*若两栈中都没有多余字符则说明成功计算了表达式*/
printf("\n\nArithmeticexpressionwrong!
!
");/*否则提示出错*/
fprintf(fp,"Arithmeticexpressionwrong!
!
\n\n");returnFALSE;
}
此函数为该课程设计的核心部分。
为便于处理负数,采用了模仿常见的计算器的方法,开始值默认为0。
当处理负数时,括号里也默认存在一个数字0。
如此,负数就转变成了0减去一个数的计算。
当从字符串中读取字符时,若是数字则进行处理,若是非正常字符则提示出错并停止运算,若是运算符或括号等正常符号,则将其与符号栈的栈顶元素比较优先级的大小。
若栈顶符号的优先级较高,则先进行栈顶符号相对应的运算;若两符号的优先级大小相同,则说明正好组成一对括号,且括号内无其他的数字、字符或运算,此时令栈顶符号出栈即可;若栈顶符号的优先级不如所读取字符的优先级高,则将此字符入栈,等待下次的运算。
最终,当符号栈中不含有字符时,即没有运算时,将数字栈的栈顶元素出栈。
若数字栈中此时不再含有其他的数字,则说明表达式已经完全正确的计算,用a返回最终结果,并返回TRUE以说明表达式运算的正确;若数字栈中还有其他数字或符号栈中不是只剩字符’0’,则说明表达式未能够正确的处理,返回FALSE,不输出运算的结果。
五调试分析
当用户输入正确表达式时,能够输出最终计算的结果。
如:
输入3.6-7.5+4.9-(-6)回车输出:
7.0000
提示是否循环,输入y
当用户输入中还有非正常符号式,能够输出提示错误的语句。
如:
输入4*9-5a+6回车输出:
Wrongcharacterexist!
!
提示是否循环,输入y
当用户输入的表达式中分母为0,能够输出提示错误的语句。
如:
输入7+8/(6-2*3)回车输出:
Divisoriszero!
!
提示是否循环,输入n
六测试结果
当常规输入简单表达式时,能够得到正确结果:
当输入含有小数和负数的表达式时,能够得到正确结果:
当分母为零时,能够得到相应的提示语句:
当含有多重括号时,能够得到提示错误的语句:
当括号不匹配时,能够得到提示错误的语句:
当出现右括号左括号情况时,能够得到提示错误的语句:
(见下页)
当)后跟数字时,能够得到提示错误的语句:
当第一个字符为右括号时,能够得到提示错误的语句:
当含有非正常字符时,能够得到提示错误的语句:
同时,当以上步骤运行完后,D盘下的文件a.txt生成,如图所示:
(见下页)
七用户使用说明
运行后直接输入表达式,以换行符结束。
当一个表达式处理后,输入y或n来选择是否继续输入表达式来运算。
结束应用时,可打开文件来查看记录。
八课程设计总结
我通过此次的课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基本能力。
在细节问题的分析上,较以往有了很大的提高。
在寻求最优解的问题上,也能够找到多种解决方案来使自己的程序收放自如。
如,在处理实数的问题上,我采用的是每取得一个字符,就立刻对此字符进行处理的方法。
其实,我们可以用一个字符数组,来存储连接着的一系列数字字符,然后再通过atof函数,直接得到字符数组中所存储的数字。
再如,对负数问题的处理上,我最初的想法是通过一个标志mark来记录前面的字符是否是负号(或减号),再在后面取到除符号外的数字时,选择是否添加负号。
然而在做这个课程设计的过程中的一天,我用到计算器时意识到,计算器的初始0使得很多的计算变得简单。
于是,模仿常用计算器的计算顺序,将程序改为初始为0,括号中初始也为0,从而不需要再对负数进行处理。
另外,与其他人不同的是,在我的课程设计中,Compare()函数与其他有着很大的区别。
通常情况下,同学们参照课本,都会采用占用7*7=49个空间的数组来分别存储对应两个字符的优先级符号,并对两个字符进行预算之后得到数组中的位置。
虽然7*7的数组所占的空间并不是非常大,但在我看来这也是一种浪费,并且空间的浪费并没有换回时间一定的节省。
因此,我采用了一种常规的思路。
将各种运算符按照数学逻辑上的优先顺序进行排序,并得到两个字符之间的优先级关系。
这样一来,我们将不再需要那7*7的数组,且时间复杂度并不大幅增涨。
在这个课程设计中,运用到的数据结构的知识主要是栈的知识。
栈在各种软件系统中,应用非常广泛。
栈的的存储特性(LIFO先进后出),使得在用栈来编程时,思路清晰明了。
在使用递归算法时,栈也是一种很好的选择。
此外,这次的课程设计进一步加强了我们运用C语言进行编程,调试,处理问题的能力,加深了我们对算法及数据结构的认识。
同时我也意识到,开发程序的早期计划要做的充分,以免出现程序完成后发现不足而带来的修改麻烦。
虽然这只是一个小小的软件,但对我们之后的影响确实很大的。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计