数据结构课程设计任务书.doc

数据结构课程设计系别： 专业： 年级： 班级： 姓名（学号）： 指导教师 年 月 日一、项目总体设计1.1 需求分析设计一个程序，计算含有如下标识符的表达式的值。1、 数值：包括整数和实数，数值可带正、负号。2、 一般运算符：正号、负号、加、减、乘、除、求模和乘方，其中可以包括括号。3、 单词（即运算函数）：abs、sqrt、exp、ln、log10、sin、cos和tanh。其中运行时函数abs用a代替，sqrt用r，exp用e，ln用n，log10用l，cos用c，tanh用t表示。1.2系统功能模块设计： 后缀表达式运算的思想为依次读入表达式中的每一个字符，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行，并将运算结果入对象栈，继续处理当前字符，直到遇到结束符。 后缀表达式的结果计算主要涉及的数据结构为栈结构，包括下面一些操作，如进栈、出栈、判断栈是否为空 、及栈是否为满、读栈顶元素等操作，同时也涉及了文件的读取及输出等操作。设计如下几个函数模块：typedef struct /定义存放符号的堆栈 OPtypedef struct /定义存放需要计算数字的堆栈 NUMint InitstackOP(SqStackOP &s)/初始化符号堆栈int PushOP(SqStackOP &s,char e)/符号堆入栈操作char GetTopOP(SqStackOP &s)/获取符号堆栈栈顶int PopOP(SqStackOP &s, char &e)/弹出符号堆栈栈顶int StackEmptyOP(SqStackOP s)/判断符号堆栈是否为空void ShowOP(SqStackOP s)/显示符号堆栈内容int InitstackNUM(SqStackNUM &s)/初始化数字堆栈int PushNUM(SqStackNUM &s,double e)/数字堆栈入栈操作double GetTopNUM(SqStackNUM &s)/获取数字堆栈栈顶int PopNUM(SqStackNUM &s,double &e)/弹出数字堆栈栈顶int StackEmptyNUM(SqStackNUM s)/判断数字堆栈是否为空void ShowNUM(SqStackNUM s)/显示数字堆栈内容char Precede(char a, char b)/判断a,b两符号的优先关系(#用#代替)double operate(double a,char theta,double b)/做简单运算int IsOP(char c)/判断输入的字符是否是计算符号int ExpEvaluation()/做复杂运算二、数据结构的设计 两个栈包括在一个数据结构里面，通过对读取的字符类型进行判断来决定它该入哪个栈。typedef struct /*算符栈*/char dataSTACKSIZE ;int top; SqStackOP;typedef struct /*对象栈*/double dataSTACKSIZE ;int top;SqStackNUM;2.1 程序已实现的功能：1、使用栈的数据结构表示数据的存储。2、设计算法将中缀表达式转换成后缀表达式，用栈的数据结构实现表 达式的运算。3、把中缀表达式转换为后缀 表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。2.2 核心功能的实现过程。1、首先实现表达式的求值： 要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则：(1)先乘除,后加减;(2)从左算到右;(3)先括号内,后括号外2、再根据这个运算优先的规定来实现对表达式的编译或解释执行. 任何一个表达式都是由操作数和操作符组成的，根据四则运算基本法则，在运算的每一步中，任意两个相继出现的操作符a和b之间的优先关系最多有以下3种：（1)a的优先级低于b（2)a的优先级等于b（3)a的优先级小于b3、为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果；操作栈op，用于存放操作符。算法思想：（1)首先将中缀表达式转换成后缀表达式： 从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和“.” ，则直接将它们写入后缀表达式中。 如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”弹出，表明这一层括号内的操作处理完毕。 如果遇到的是操作符，则将该操作符和操作符栈顶元素比较： a.当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级； b.当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。 重复上述步骤直到遇到中缀表达式的结束0，弹出栈中的所有元素并放入后缀表达式中，算法结束。(2)对后缀表达式求值： 将遇到的操作数暂存在一个操作数栈中，凡是遇到操作符，便从栈中弹出两个操作数执行相应的操作，并将结果存于操作数栈中，直到表达式处理完毕，最后压入栈中的数就是表达式的结果。2.3 调试：在设计过程中出现程序不能运行，发现不能找到标识符，因此在设计的时候需要人为动态添加标识符#，顺利运行。算法时间和空间分析： 算法的运行时间主要花在while循环上，它从头到尾扫描表达式中的每一个数据（每个操作数或运算符均为一个数据），若表达式由n个数据组成，则 此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个 数与运算符（假定把#也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。三、 项目总结本次实验熟悉了栈数据结构的表示与实现方法，以及考虑到表达式必须是后缀表达式文法，则在模块设计中必须有能够对表达式中的非终结符进行分析的模块，从而能够将中缀表达式转换成后缀表达式，最后进行表达式的求值运算。表达式要进行加减乘除运算，在分析的过程中还有一个出错处理模块，用来提示输入的文法的错误，有利于进行改进。 在进行表达时计算求值的时候，输入的表达式分各种情况，有单个的表达式、表达式中含有项、项中含有因子等情况，不同的情况下