搜索
数据结构课程实践设计报告专业：计算机科学与技术班级名称：08统招本科组别：第6组组长：温冬飞姓名：温冬飞学号：23指导教师：王沛礼地点：实训基地·实验楼南昌理工学院计算机系2010年1月8日一、实训题目:表达式的处理与实现二、实训目的加深对栈的理解，掌握栈的数据结构，栈的基本操作,。通过课程设计，学生在下述各方面的能力应该得到锻炼：（1）进一步巩固、加深学生所学专业课程《C/C++程序设计》、《数据结构》的基本理论知识，理论联系实际，进一步培养学生综合分析问题，解决问题的能力。（2）全面考核学生所掌握的基本理论知识及其实际业务能力，从而达到提高学生素质的最终目的。（3）利用所学知识，开发应用课题，掌握运用C/C++语言编写调试应用系统程序，训练独立开发应用系统，进行数据处理的综合能力。（4）对于给定的设计题目，如何进行分析，理清思路，并给出相应的数学模型。（5）掌握自顶而下的设计方法，将大问题进行模块化，领会结构化程序设计的方法。三、实训要求⑴实训编程环境为VisualC++6.0。要求学生熟悉C/C++语言环境，掌握C/C++语言程序的书写格式和C/C++语言程序的结构。⑵熟练应用C/C++语言函数参数传递的规则，熟悉指针变量作函数参数的基本用法，以及如何把一个数据结构的算法转变成C/C++语言的源程序。⑶完成简单算术表达式转换成后缀表达式（逆波兰表达式）程序，并在机器上调试、运行，计算出结果。四、实训步骤1、问题分析这个课程设计题目是表达式处理与实现。要把一个表达式翻译成正确求值的一个机器指令序列。或者直接对表达式求值，首先要能够正确解释表达式。例如，要对下面的算术表达式求值：8+(5-3)*4/2首先要了解算术四则运算的规则。即：（1）先乘除，后加减；（2）从左算到右；（3）先括号内，后括号外。2、数据结构与算法设计⑴数据结构：这个程序涉及到的数据结构是栈。⑵概要设计：此程序分为十七个模块：(1)structSqOpnd定义运算符栈(2)Init_SqOpnd(SqOpnd*L)初始化运算符栈(3)PushPushOpnd(SqOpnd*L,ElemTypeOpnde)入运算符栈(4)PopOpnd(SqOpnd*L)出运算符栈(5)GetOpndTop(SqOpndL)取栈（运算符栈）顶元素(6)structSqOplnd定义存放运算对象栈(7)Init_SqOplnd(SqOplnd*L)初始化运算对象栈(8)PushOplnd(SqOplnd*L,ElemTypeOptre)入运算对象栈(9)PopOplnd(SqOplnd*L)出运算对象栈(10)GetOplndTop(SqOplndL)取栈（运算符对象栈）顶元素(11)Precede(chara,charb)比较运算符优先级(12)cal(charexp[])运算对象、运算符，入队、进栈的相关操作(13)transform(charsuffix[],charx[])后缀表达式队计算结果操作过程函数(14)main(intargc,char*argv[])主函数我负责主控模块：transform(charsuffix[],charx[])功能：后缀表达式队计算结果操作过程函数main(intargc,char*argv[])功能：主函数⑶处理模式：输入中缀表达式－→转换为后缀表达式（逆波兰表达式）－→计算出结果①中缀表达式到后缀表达式的转换如何将一个中缀表达式转换成后缀表达式呢？先假定在算术表达式中只含有四种基本运算符，操作数是在10以内的整数，没有括号。假定一个中缀表达式4+2*3,它的后缀表达式为423*+。在扫描中缀表达式中的后2后，不能立即输出“+”运算，因为“*”具有较高的优先级，必须先运算，因此先要保存“+”。也就是说，新扫描到的运算符，其优先级必须与前一个运算符的优先级做比较，如果新的运算符优先级高，就要像前一个运算符那样保存它，直到扫描到第二个操作数并将它输出才能将该运算输出。因此，在转让中必须保存两个运算符，后保存的运算先输出。用计算机来实现这一转化过程，，就需要到后进先出的概念。如果在中缀表达式中含有小括号，那么由于括号隔离了优先级规则，它在整个表达式的内部产生了完全的独立的表达式，因此，前面的算法就需要有所改变。当扫描到一个左括号时，需要将其压入栈中，使其在栈中产生了一个“伪栈底”。这样，算法就可以像前面一样进行。但当扫描到一个右括号时，就需要将从栈顶到这个“伪栈底”中的所有运算符全部弹出，然后再将这个“伪栈底”删除。综上分析，可得到通过栈将中缀表达式转换为后缀表达式（逆波兰表达式）的算法如下：顺序扫描中中缀算术表达式，当读到运算时，将栈中所有优先级高于或等于该运算符的运算符弹出，将当前运算符入栈；当读入左括号时，即入栈；当读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，再删除栈中的左括号。②算法设计在有了上述分析之后，实现其转换的算法就不难给出。为了简化算法，我们把括号也作为运算看待，并规定它的优先级为最低，另外将表达式中的操作娄规定为1位数字字符，运算符也只包括+、－、*、/四种。读者可根据需要对算法的功能加以扩充。为了方便边界条件的判断，提高算法的运行效率，在扫描读入中缀表达式之前，在空栈预先压入一个“#”字符，作为栈底元素，另外，在表达式的最后增加一个“#”字符。作为中缀表达式的结束标志，该结束符与栈底元素“#”配对。本算法不包括输入表达式的语法检查，但可以过虑掉输入符号之间的空格。③算法的具体实现如果要执行上述算法，还必须给出相关的栈的定义、操作以及调用该算法的主函数。根据实训要求，输入中缀表达式字符串：8+(9-6/2)*5，输出结果为：8962/-5*+.其中运算符栈存放后缀表达式的变化过程如表所示：中缀表达式到后缀表达式（逆波兰表达式）的转换过程示例转换步骤中缀表达式的读入运算符栈后缀表达式初始8+(9-6/2)*5##空1+(9-6/2)*5##82(9-6/2)*5##+839-6/2)*5##+(84-6/2)*5##+(8956/2)*5##+(-896/2)*5##+(-89672)*5##+(-/8968)*5##+(-/89629*5##+(-8962/10*5##+(8962/-11*5##+8962/-125##+*8962/-13##+*8962/514##+8962/-5*15##8962/-5*+④后缀表达式（逆波兰表达式）的计算在后缀表达式中，不仅不需要括号，而且还完全免除了算符优先规则。对于后缀表达式来说，仅仅用一个自然规则，即从左到右顺序完成计算，这个规则对于计算而言，是很容易实现的。下面将讨论如何用计算机后缀表达式的算法。如果在表达式中仅仅只有一个运算符，如像53*这样的表达式，显然计算过程非常简单，可立即进行。但后缀表达式在多数情况下都是多于一个运算符，因此，必须要像保存输入数字一样保存其中间的结果。在计算后缀表达式时，最后保存的值是最先取出参与运算，所以要用到栈。利用前面生成的后缀表达式，可以写出计算后缀表达式的算法。由于在生成的后缀表达式中存放的是字符序列，因此，在算法中要有一个数字符到数值的转换。这个算法在这里就不详细解析了，只要将此算法与前一个中缀表达式到后缀表达式转换算法连在一起，进行相应修改即可。下面以后缀表达式9547*+5/-3为例，使用上述已有的中缀表达式队列进行计算，计算过程如表：后缀表达式（逆波兰表达式）的计算过程示例转换步骤后缀表达式结果栈初始8962/-5*+空1962/-5*+8262/-5*+9832/-5*+6984/-5*+26985-5*+39865*+687*+5688+3089383、主控模块运行框图cal(charexp[])函数运行框图（运算对象、运算符、入栈、进栈的相关操作）运算符栈地址=＞s指针↓初始化运算符栈（调用函数）↓表达式的左“#”入栈↓取中缀表达式字符=＞C↓是C是数字？入运算对象栈↓是C是“(”？入栈↓是C是“”或左“#”？进入处理程序（1）↓是C是“＋、－、*、/”？进入处理程序（2）↓输出当前运算符栈的情况↓输出当前后缀表达式的情况是↓C≠“#”（右“#”号）?↓处理结果处理程序（1）取栈顶元素（运算符）（既取又退）=＞t↓是t≠‘（’&&t≠“#”?t=＞运算对象栈是↓t≠‘（’&&（未到栈底）?↓结束处理程序（2）当前所取运算符C的优先级数=＞i↓栈顶运算符优先级数=＞j↓i=j?是↓栈顶运算符出栈=＞入栈↓再取栈顶运算符优先级=＞j↓当前运算符C入栈↓结束main(intargc,char*argv[])主函数运行框图建立后缀表达式栈Queue的指针*Q↓后缀表达式栈首地址=＞Q↓初始化栈↓进行中缀转后缀的处理（调用cal(charexp[])函数）↓进行后缀表达式计算结果的处理（调用cal(charexp[])函数）↓结束4、编码实现把详细设计的结果用C/C++语言表示（主控模块程序代码）：doublecal(charexp[]){char*p=exp;SqOpndS;Init_SqOpnd(&S);doublea,b;while(*p!='\0'){if(!In(*p)&&*p!=''){doublea=strtod(p,NULL);PushOpnd(&S,a);while(*p++!='');}if(*p==''){p++;}if(In(*p)){b=GetOpndTop(S);PopOpnd(&S);a=GetOpndTop(S);PopOpnd(&S);if(*p=='+')a=a+b;if(*p=='-')a=a-b;if(*p=='*')a=a*b;if(*p=='/')a=a/b;p++;PushOpnd(&S,a);}printf(\n[%s]\n,p);}a=GetOpndTop(S);DestoryOpnd(&S);returna;}voidtransform(charsuffix[],charx[]){charexp[80]=;strncat(exp,x,strlen(x));strncat(exp,#,1);printf(%s\n,exp);SqOplndS;Init_SqOplnd(&S);PushOplnd(&S,'#');char*p;charq;p=exp;while(*p!='\0'){printf(\n[%s]\n,suffix);if(!In(*p)){strncat(suffix,p,1);p++;}else{char*m=suffix;while(*m++!='\0');*m--;if(*p!='('&&!In(*m))strncat(suffix,,1);switch(*p){case'#':while(GetOplndTop(S)!='#'){q=GetOplndTop(S);strncat(suffix,&q,1);PopOplnd(&S);}PopOplnd(&S);break;case'(':PushOplnd(&S,*p);break;case')':while(GetOplndTop(S)!='('){q=GetOplndTop(S);strncat(suffix,&q,1);PopOplnd(&S);}PopOplnd(&S);break;case'*':case'/':case'+':case'-':printf(运算符栈:\t%c\n,*p);while(!Precede(*p,GetOplndTop(S))){q=GetOplndTop(S);PopOplnd(&S);strncat(suffix,&q,1);}PushOplnd(&S,*p);break;default:break;}p++;}}DestoryOplnd(&S);}intmain(intargc,char*argv[]){charinput[81];begin:printf(\n\n(1)*******************输入表达式(加减乘除四则运