数据结构课设.doc

目录1 绪论12 需求分析2 3 概要设计34 详细设计45 调试分析56 课程体会8 7参考文献9附加源程序.101一.绪论 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。在数据结构的学习和课程设计过程中，我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。对于我们专业来说，虽然说对技术要求不是特别高，但是在实际操作过程中，没有足够的专业知识对于编程来说是远远不可以达到要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。在这次的课程设计中我选择的题目是表达式的求值演示。它的基本要求是：以字符序列的形式从终端输入语法正确的，不含变量的表达式。利用算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比较困难的，以我自身的能力，是不可能在规定的时间内完成任务的，所以我参考了很多书籍来帮助我完成我的程序设计。二、需求分析 这道题主要涉及到的知识点是栈的遍历和栈的运用。因为它要求是解决一个表达式的运算，然后我就想到了把一个完整的表达式可以通过字符来进行表示，并且可以构建成一个栈来进行处理，这样就能够很方便的实现多级的运算。当然其中这些肯定是要建立在实现优先分级的前提下的。在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因此，要求设计一个程序，利用栈演示运算符优先法对算术表达式求值的过程，利用算符有限关系，实现对算数混合四则运算表达式的求值。程序输入： 一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“+” “ -” “*” “/” “（” “）” 用“#”号结束程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程测试数据： （3*4+5-7）/2（用于正确性检测的合法输入数据）三、概要设计四、详细设计 在此课设中，我建立了两个数据栈，一个是用来存放算术符号的，另一个是用来存放操作数和结果的。他们分别被称为“栈1”和“栈2”我首先使栈为空栈，“#”为此栈的栈底元素。然后分别识别表达式的字符。求值过程：当前OPTR算符栈栈顶为f，下个读入的算符为gIf(fg)OPND数据栈连续pop()2个操作数 a,b;执行4则运算，result=afg，类似于a+b；将result进OPND，f出栈（2） 显示输入序列和栈的变化过程。五、调试分析这是简单的乘法运算，以#代表结束按下回车键会出现上面的情况 这幅图详细的说明了如何采用栈来运算算术表达式这个运算稍微复杂点，是两级运算。3*4+5 同样也以#结束。得到答案17这是最后的结果 这个算术表达式包括了“+” “ -” “*” “/” “（” “）” 几种符号。最后得到结果等于5六、课程体会通过本次课程设计,我巩固了栈的建立,入栈,出栈的操作,提高了发现问题进而解决问题的能力，深化了数据结构的基本知识，并进行了拓展实践。最终，加强了程序设计的能力,并且能够有条理的安排各个函数的功能和位置。 曾经存在的问题：1) 利用栈判断小数存在，并求解小数运算。2) 考虑各个运算符的优先顺序。解决方法：1) 利用小数点存在的判断，以及位数与数值的关系，除以十的倍数进行数值运算。优先顺序自己先罗列一遍，以免遗漏。将+-*/数字化，以此代表优先顺序。（）单独处理。七、参考文献1 谭浩强.C程序设计（第2版）.北京：清华大学出版社，20092 严蔚敏.吴伟民. 数据结构（C语言版）M. 北京: 清华大学出版社, 2007.3 腾国文.数据结构课程设计 北京：清华大学，2010. 4 张红霞.数据结构教程与实训附加源程序#include #include #include /判断是否为字符的函数的头文件#define MAXSIZE 100typedef int elmtype;typedef struct sqstack sqstack;/由于sqstack不是一个类型 而struct sqstack才是char ch7=+,-,*,/,(,),#;/把符号转换成一个字符数组int f17=3,3,5,5,1,6,0;/栈内元素优先级int f27=2,2,4,4,6,1,0;/栈外的元素优先级int n=0;struct sqstack elmtype stackMAXSIZE; int top;void Initstack(sqstack *s) s-top=0;Int StackEmpty(sqstack S ) /若S为空栈，则返回TRUE, 否则返回FALSE if( S.top = 0 ) return 1; else return 0; void Push(sqstack *s,elmtype x) if(s-top=MAXSIZE-1) printf(ERROR,Overflow!n); else s-top+; s-stacks-top=x; void Pop(sqstack *s,elmtype *x) if(s-top=0) printf(ERROR,Underflow!n); else *x=s-stacks-top; s-top-; elmtype Gettop(sqstack s) if(s.top=0) printf(ERROR,underflown); return 0; else return s.stacks.top;elmtype f(char c) switch(c) case +: return 0; case -: return 1; case *: return 2; case /: return 3; case (: return 4; case ): return 5; default: return 6; void visitoptr(sqstack c)/对栈进行遍历elmtype s;sqstack m;int i=0;Initstack(&m);if(StackEmpty(c)printf(0);while(!StackEmpty(c) Pop(&c,&s); Push(&m,s);while(!StackEmpty(m)i+;Pop(&m,&s);Push(&c,s); printf(%c,chs); printf(tt);void visitopnd(sqstack c)/对栈进行遍历elmtype s;sqstack m;int i=0;Initstack(&m);if(StackEmpty(c)printf(0);while(!StackEmpty(c) Pop(&c,&s); Push(&m,s);while(!StackEmpty(m)i+;Pop(&m,&s);Push(&c,s); printf(%d ,s); printf(tt);void printstep() n+; printf(%d,n); printf(tt);char Compare(char c1,char c2) int i1=f(c1); int i2=f(c2);/把字符变成数字 if(f1i1f2i2)/通过原来设定找到优先级 return ; else if(f1i1f2i2) return ; else return =;int Operate(elmtype a,elmtype t,elmtype b) int sum; switch(t) case 0: sum=a+b; break; case 1: sum=a-b; break; case 2: sum=a*b; break; default: sum=a/b; return sum;int EvaluateExpression() char c; int i=0,sum=0; int k=1,j=1;/设置开关变量 elmtype x,t,a,b; sqstack OPTR,OPND; Initstack(&OPTR); Push(&OPTR,f(#);/0压入栈 Initstack(&OPND); c=getchar(); printf(*n); printf(步骤); printf(tt); printf(栈1); printf(tt); printf(栈2); printf(tt); printf(操作n); printstep(); printf(Push(&OPTR,#)n); while(c!=#|chGettop(OPTR)!=#) if(isdigit(c) sum=0; while(isdigit(c) if(!j) sum=sum*10-(c-0);/实现了数字串前面有负号 else sum=sum*10+(c-0); c=getchar(); Push(&OPND,sum);/如果还是数字先不压栈，把数字串转化成十进制数字再压栈 j=1; else if(k) switch(Compare(chGettop(OPTR),c) case: Pop(&OPTR,&t); printstep(); visitoptr(OPTR); visitopnd(OPND); printf(Pop(&OPTR,%c)n,cht); Pop(&OPND,&b); printstep(); visitoptr(OPTR); visitopnd(OPND); printf(Pop(OPND,%d)n,b); Pop(&OPND,&a);/注意先出栈的元素 printstep(); visitoptr(OPTR); visitopnd(OPND); printf(Pop(&OPND,%d)n,a); Push(&OPND,Operate(a,t,b); printstep(); visitoptr(OPTR); vis