数据结构课设 表达式求值.docVIP

《计算表达式》课程设计报告 标 题：计算表达式 单 位： 报 告 人： 指导教师： 编程环境：VC6 时 间：2011年 12月 20日 一、设计要求 对于输入的一个中缀表达式，判断表达式是否合法。如果合法，把中缀表达式转换成一棵二叉树，然后通过后根遍历计算表达式的值，输出运算结果。 合法表达式不能为空，可以出现在表达式中的字符有： *运算符“+”、“-”、“*”、“／”； *左右括号“(”、“)”； *整数(可以是多位的)； *空格符和制表符。 例如：表达式为“20+(3*(4+46)-6)／2-134”将得到结果-42。 数据结构采用二叉树的链接表示。 二、题目分析 由设计要求可以确定程序的几大模块，读入源程序 （1）读入中缀表达式从中缀表达式ex(长度为n)创建二叉树 四．全局变量与子程序功能说明 （1） int extoBinTree (PBinTree pbtree,const char *ex,int n) 从中缀表达式ex(长度为n)创建二叉树。若是一个合法的表达式，则返回TRUE，且算法结束时*pbtree存放二叉树的根节点的地址；否则返回FALSE （2）int cal(BinTree btree,int*presult) 计算二叉树btree所代表的表达式的值。若是一个合法的表达式，则返回TRUE，且算法结束时*presult中存放计算结果；否则，返回FALSE. （3）void delete_BTree(PBinTree ptree) { BinTree temp=(*ptree); if(temp==NULL) return; delete_BTree((temp-llink)); delete_BTree((temp-rlink)); free(temp); } 作用为，当输入的程序有误时，或者一段表达式已经运算结束时清除储存空间，为下一段表达式的计算作准备。 （4）void getline(char *line,int limit) { char c; int i=0; while(ilimit-1(c=getchar())!=EOFc!=\n) line[i++]=c; line[i]=\0; } 从标准输入中读入一行，作为字符串line，作用为程序执行的第一步将所输入的表达式读入 五．源程序（附） 六．测试 （1）输入，编译，链接程序 （2）执行程序 （3）输入表达式 20+(3*(4+46)-6)／2-134 （4）输入Y继续执行运算表达式 （5）输入N结束运算程序 七．参考文献说明 数据结构（C语言版） 严蔚敏 清华大学出版社 数据结构课程设计 苏仕华 机械工业出版社 数据结构实验与实训教程 邓文华 清华大学出版社 C程序设计（第二版） 谭浩强 清华大学出版社 《交通咨询系统设计》课程设计报告 1.设计要求 设计一个交通咨询系统能让旅客咨询从任意一个城市顶点到另一城市顶点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需费用。 2.题目分析 （设计思想、主要数据结构、主要代码结构、主要代码段分析） 设计共分为三个部分， 一是用有向图的邻接矩阵建立交通网络图的存储结构； 首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。一个图的邻接矩阵表示是唯一的。除了用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要用一个具有n个元素的一维数组来存储顶点信息。 二是是用迪杰斯特拉（Dijkstra）算法解决源点到所有点的最短路径问题； 单源最短路径问题：即有向图（带权），我们希望找出从某个源点S∈V到G中其余个顶点的最短路径。用迪杰斯特拉算法（按路径长度递增产生诸顶点的最短路径算法）可以求得有向图的单源最短路径。 3．三是用费罗伊德（Floyd） 最短路径的解决方法：我们可以一次吧有向网络中德没打个顶点作为源点，重复执行前面讨论的底特斯特拉算法n次，即可求出每对顶点之间的最短路径。 主要数据结构：1.建立有向图的存储结构 2.迪杰斯特拉算法 3.费罗伊德算法 4.主框架函数的实现 3.流程图 4.全局变量与子程序功能说明 主要代码结构： void CreateMGraph(MGraph *G,int n,int e) 建立有向图的存储结构 void CreateMGraph(MGraph *G,int n,int e) {//采用邻接矩阵表示法构造