数据结构课程设计报告书.doc

数据结构课程设计 PAGE9 / NUMPAGES19 PAGE \* MERGEFORMAT 1 南通大学计算机学院 《数据结构课程设计报告书》 题目： 表达式求值问题 专业： 计算机科学与技术 班级: 学号: 姓名: 指导教师: 开始日期： 2013.1.14 完成日期： 2013.1.16 1.问题的描述和分析 1.1问题描述 表达式有中缀、后缀、前缀三种表示方式，中缀式的计算按运算符的优先级及括号优先原则，相同级别从左到右进行运算。而前缀式和后缀式没有括号给运算带来方便。本设计的主要任务是进行表达式的转换及不同表达式的计算。 1.2 问题分析 表达式是字符型数据，在程序中涉及表达上的转换，可用数组和栈来存储表达式。程序中关键要处理好在不同形式表达中字符的顺序，对操作符优先级的比较以及在中转前、中转后过程中对括号的处理。 2.概要设计 2.1系统模块划分 要求：描述整个系统的模块划分，最后以图的形式展现，并简单介绍每个模块的功能。例如： 进入主菜单 进入主菜单 中缀表达式求值 输出各种形式的表达式 退出程序 前缀表达式求值 后缀表达式求值 中缀式转后缀式 中缀式转前缀式 图2-1 系统模块图 2.2 ADT（抽象数据类型）描述 本程序要用到栈，对栈的操作包含在头文件“SqStack.h”中。 ADT Stack { 数据对象：D={ai|ai∈ElementSet,i=1,2…,n,n≥0} 数据关系：R={ai-1,ai|ai-1,ai∈D,i=2,…n} 基本操作： SqStack 创建一个空栈 Push 将一个元素压入栈中 Pop 将栈顶元素出栈 StackEmpty 判断栈是否为空要求} 3.详细设计 3.1 ADT基本操作算法设计 3.1.1 A 中缀表达式求值 SqStackchar OP(20);//操作符栈 SqStackdoubleOD(20);//操作数栈 读入表达式操作数或操作符C，如果C是操作数，OP.Push(C),如果C是操作符，把它与栈顶元素的优先级比较case:OP.Push(c)；case=:x=OP.Pop();如果是大于，从操作符栈里退出两个元素进行运算。 重复上述过程直到把表达式扫描完，操作数栈的栈顶元素为计算结果 3.1.2 中缀转后缀 SqStackchar OP(20) 从左向右读取表达式，读到操作数把它输出，读到操作符，把它与栈顶元素的优先级比较case:OP.Push(c); case=:x=OP.Pop();case:postexp[i++]=OP.Pop(); 3.1.3 ADT操作3 中缀转前缀 SqStackcharST(20); SqStackcharSP(20); SqStackcharOP(20); 将中缀式入栈再依次从栈中读取元素，如果是操作数把它加入一个数组中if(C==)’)OP.Push(C);如果是运算符，则：如果栈空或栈顶是闭括号或此元素的优先级大于等于栈顶元素此操作符入栈，否则，栈顶运算符出栈并加入数组中；如果是开括号，栈中元素逐个出栈加入数组中，直到遇到闭括号。最后数组中的元素序列为中缀式的逆序，将数组中的元素入栈再出栈就得到中缀式。 3.1.4 ADT操作 4 后缀求值 SqStackdouble OD(20);//操作数栈 c=*postexp++; while(c!=\0) { if((c=0c=9)||c==.)//为操作数 { i=0; do { z[i++]=c; c=*postexp++; }while(c=0c=9||c==.); z[i]=\0; d=atof(z); // 将字符串数组转为符点型存于d OD.Push(d); } if(In(c))//遇到运算符从栈中退出两个元素进行运算 { b=OD.Pop (); a=OD.Pop (); OD.Push (Operate(a,c,b)); c=*postexp++; } c=*postexp++; } v=OD.Pop ()//计算结果 3.1.5 ADT操作 5 前缀式求值 SqStackcharST(20); SqStackdoubleOD(20); while(*preexp!=\0) { ST.Push(*preexp+