算法与数据结构课程设计-表达式求解问题.doc

算法与数据结构课程设计任务书（09级）题目：表达式求解问题学生姓名： XX 学号： 09780015 班级： 计算机网络 题目类型：软件工程（R） 指导教师： XXX 一 题目简介该设计要求学生设计程序，实现任意算术表达式的求解问题。通过该题目的设计过程，可以加深理解线性表及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。二 主要任务1、查阅文献资料，一般在3篇以上；2、建立数据的逻辑结构和物理结构；3、完成相应算法的设计；4、完成测试工作；5、撰写设计说明书；6、做好答辩工作。三 主要内容、功能及技术指标（1）使用顺序栈存储算术表达式，主要功能有：输入并建立算术表达式、输出算术表达式、算术表达式的计算及显示输出等；（2）至少要用10个测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；（4）假设算术表达式中只含加减乘除等四种运算符，操作数是实数，界限符有括号有“（）”、“”、“ ”、表达式起始、结束符“#”等；（5）较高要求：实现图形化操作界面；表达式在输入出错时能够提示并尽心修正；显示栈的变化过程。四 提交的成果1. 设计说明书一份，内容包括：1) 中文摘要100字；关键词3-5个；2) 序言；3）采用类c语言定义相关的数据类型4）各模块的伪码算法5）函数的调用关系图6）调试分析a、调试中遇到的问题及对问题的解决方法；b、算法的时间复杂度和空间复杂度。7）测试结果8）源程序（带注释）9) 设计总结、参考文献、致谢等。2. 刻制光盘一张。五 主要参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.c语言程序设计. 清华大学出版社. 六各阶段时间安排（共2周）周次日期内容地点完成情况教师签字第1周星期一教师讲解设计要求，准备参考资料教室星期二分析设计要求，进行数据结构及算法设计教室星期三分析设计要求，进行数据结构及算法设计教室星期四算法设计，编程实现实验室星期五算法设计，编程实现实验室第2周星期一算法设计，编程实现实验室星期二编程上机实现、测试程序实验室星期三编程上机实现、测试程序实验室星期四编程上机实现、测试程序实验室星期五检查程序，答辩实验室2010年6月30日目 录一 设计分析31算法结构32 设计方案 4二 详细设计5 1 程序模块 5三 程序运行9 1 程序调试9 2 调试中遇到的问题9 3 心得体会11四 附件12 1 源程序代码12五 设计总结16六 参考文献17一 设计分析1算法框架数据结构+算法=程序2设计方案算法框架已经有了，现在的问题是数据结构的组织。输入：字符型，为了简便算法，只进行+-*/等简单运算，对算符的识别用简单的switchcase；所以运算符栈的数据类型可以为char输入：数值，eg：1+1中的如何处理？为了方便，只能和输入统一为字符型，那么问题变为了，数值只能为位整数（），因为程序目的是算法，所以可以简化为此。 但新问题来了，表达的运算中间结果或最终结果，不一定是位整数，eg：+*=？其中中间结果为，最终结果为。那么数据栈可以有以下种结构设计： 方案、数据栈元素类型为char，只保存字符即ASCII码为HH，对于输入不转化，直接入数据栈，但在数据出栈参与运算前，先将字符转为数字。且最终结果也要逆向再转换一次，且若（中间）结果位数位，那么新的问题又引发了，如何存储和识别数据的位数。由此可见数据栈类型为char会加大操作算法的难度。故放弃！ 方案、数据栈元素为int型，当然，操作算法也要加强，但相比方案的难度，会小得多！加强如下： 输入数据（只能为位数据，或加入位数识别函数），要先将字符转化为相应数字即ASCII减H（），这没什么难度。然后是（中间）结果，这里也没难度，只要结果在-65536+65535之间即可直接存入。因此选方案二。 二 详细设计 1程序模块* ConsoleMain.c*#defineDEBUG 0#include#include#include#includeEvaluateExp.hvoid main()charinput=1;intnShowInfo=1;/是否显示帮助信息doEvaluateexpression_r_r_r(nShowInfo);nShowInfo=0;printf(nagain? Y/Nnt);getchar();/接收多的一个回车键字符input=getchar();if(input=Y| input=y)input=1;elseinput=0;while(input);* EvaluateExp.h*#ifndefHEAD_LIST_SQ/头文件定义宏，避免重复定义#define HEAD_LIST_SQ#define STACK_INIT_SIZE 100#define STACK_INCREMENT_SIZE 10#defineTRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1/不可行的#define OVERFLOW-2typedef int Status;/函数状态返回码为int 型typedef char OptrElemType;/运算符栈元素类型，可以用所有基本类型以及结构体类型等，这里设为char 。typedef int OpndElemType;/数据栈元素类型typedefstructOptrElemType *base;OptrElemType *top;intstacksize;SqStackOptr;typedefstructOpndElemType *base;OpndElemType *top;intstacksize;SqStackOpnd;StatusInitStackOptr(SqStackOptr *p_optr);StatusInitStackOpnd(SqStackOpnd *p_opnd);Status PushOptr(SqStackOptr *p_optr,OptrElemType OptrE);Status PushOpnd(SqStackOpnd *p_opnd,OpndElemType OpndE);Status PopOptr(SqStackOptr *p_optr,OptrElemType *p_optrE);Status PopOpnd(SqStackOpnd *p_opnd,OpndElemType *p_opndE);OptrElemTypeGetStackOptrTop(SqStackOptr*p_optr);OpndElemTypeGetStackOpndTop(SqStackOpnd*p_opnd);StatusIsOptr(char ch);StatusIsOpnd(char ch);StatusTranslateNum(OpndElemType *p_data,OptrElemType *p_ch);charCompareOptr(OptrElemType optr_A,OptrElemType optr_B);StatusOpndCount(OpndElemType *p_opnd_X,OpndElemType *p_opnd_A,OptrElemType theta,OpndElemType *p_opnd_B);Status DestroyStackOptr(SqStackOptr *p);Status DestroyStackOpnd(SqStackOpnd *p);StatusEvaluateexpression_r_r_r(int nShowInfo);#endif 三 程序运行 1程序调试 2调试中遇到的问题1.书写标识符时，忽略了大小写字母的区别。main()int a=5;printf(%d,A);编译程序把a和A认为是两个不同的变量名，而显示出错信息。C认为大写字母和小写字母是两个不同的字符。习惯上，符号常量名用大写，变量名用小写表示，以增加可读性。2.忽略了变量的类型，进行了不合法的运算。main()float a,b;printf(%d,a%b);%是求余运算，得到a/b的整余数。整型变量a和b可以进行求余运算，而实型变量则不允许进行“求余”运算。3.将字符常量与字符串常量混淆。char c;c=a;在这里就混淆了字符常量与字符串常量，字符常量是由一对单引号括起来的单个字符，字符串常量是一对双引号括起来的字符序列。C规定以“”作字符串结束标志，它是由系统自动加上的，所以字符串“a”实际上包含两个字符：a和，而把它赋给一个字符变量是不行的。4.忽略了“=”与“=”的区别。在许多高级语言中，用“=”符号作为关系运算符“等于”。如在BASIC程序中可以写if (a=3) then 但C语言中，“=”是赋值运算符，“=”是关系运算符。如：if (a=3) a=b;前者是进行比较，a是否和3相等，后者表示如果a和3相等，把b值赋给a。由于习惯问题，初学者往往会犯这样的错误。5.忘记加分号。分号是C语句中不可缺少的一部分，语句末尾必须有分号。a=1b=2编译时，编译程序在“a=1”后面没发现分号，就把下一行“b=2”也作为上一行语句的一部分，这就会出现语法错误。改错时，有时在被指出有错的一行中未发现错误，就需要看一下上一行是否漏掉了分号。 z=x+y;t=z/100;printf(%f,t);对于复合语句来说，最后一个语句中最后的分号不能忽略不写(这是和PASCAL不同的)。6.多加分号。对于一个复合语句，如： z=x+y;t=z/100;printf(%f,t);复合语句的花括号后不应再加分号，否则将会画蛇添足。 3心得体会 转眼，为期两周的数据结构课程设计即将结束了。我的题目是:图遍历的演示,这两周课程设计中,通过该题目的设计过程, 自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高，我加深了对图数据结构及队列的逻辑结构,存储结构及图的深度优先和广度优先遍历过程的理解,对图数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。总结起来，自己主要有以下几点体会：1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的数据结构这门课，所以在实习之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，这次实习之后，我告诫自己：今后一定要牢固掌握好专业基础知识。2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。3.这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。两周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，两周中我收益很大，学到很多。四 附件 1源程序代码#include#include#define stack_init_size 40#define stackincrement 20#define OK 1#define FALSE 0 typedef struct int *base; int *top; int stacksize;s_stack;typedef struct char *base; char *top; int stacksize;f_stack;static char OP77= , , , , , ,= ;int in(char c) /*判断是否为运算符*/int i;char a=+-*/()#;for(i=0;ibase=(int *)malloc(stack_init_size*sizeof(int);if(!s-base) exit(0);s-top=s-base;s-stacksize=stack_init_size;return OK;int f_initial(f_stack *f) f-base=(char *)malloc(stack_init_size*sizeof(char);if(!f-base) exit(0);f-top=f-base;f-stacksize=stack_init_size;return OK;void s_push(s_stack *s,int e) if(s-top-s-base=s-stacksize) s-base=(int *)realloc(s-base,(s-stacksize+stackincrement)*sizeof(int); if(!s-base) exit(0); s-top=s-base+s-stacksize; s-stacksize+=stackincrement; *(s-top)=e; s-top+;void f_push(f_stack *f,char e) if(f-top-f-base=f-stacksize) f-base=(char *)realloc(f-base,(f-stacksize+stackincrement)*sizeof(char); if(!f-base) exit (0); f-top=f-base+f-stacksize; f-stacksize+=stackincrement; *(f-top)=e;f-top+;int f_pop(f_stack *f,char *e) if(f-base=f-top) return FALSE; *e=*(-f-top); return OK;int s_pop(s_stack *s,int *e)/*操作数出栈*/if(s-top=s-base) return FALSE; *e=*(-s-top); return OK;int s_gettop(s_stack *s) return *(s-top-1);char f_gettop(f_stack *f) return *(f-top-1);char Precede(char theta1,char theta2)/*比较运算符优先级*/ return OPin(theta1)-1in(theta2)-1;int operate(int p,char op,int q) /*计算*/ switch(op) case +: return q+p; case -: return q-p; case *: return q*p; case /: return q/p; int EvaluateExpression(s_stack *OPND,f_stack *OPTR)char c,op,x;int a,b;s_initial(OPND);f_initial(OPTR);f_push(OPTR,#);c=getchar();while(c!=# |f_gettop(OPTR)!=#) if(!in(c) /*为操作数*/ s_push(OPND,c-0); c=getchar(); else switch(Precede(f_gettop(OPTR),c) case : s_pop(OPND,&a); s_pop(OPND,&b); f_pop(OPTR,&op); s_push(OPND,operate(a,op,b);/*没有检查除0的错误*/ break; return s_gettop(OPND);int main() s_stack s; f_stack f;printf(%d n,EvaluateExpression(&s,&f);五 设计总结 这是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，李老师就为我们阐述了它的重要性。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。TC里检查错误都是用英文来显示出来的，经过了这次课程设计，