《数据结构课设 表达式求值讲解》由会员分享，可在线阅读，更多相关《数据结构课设 表达式求值讲解（32页珍藏版）》请在金锄头文库上搜索。
1、计算表达式课程设计报告标 题：计算表达式单 位：报 告 人：指导教师：编程环境：VC6时 间：2011年 12月 20日一、设计要求对于输入的一个中缀表达式，判断表达式是否合法。如果合法，把中缀表达式转换成一棵二叉树，然后通过后根遍历计算表达式的值，输出运算结果。合法表达式不能为空，可以出现在表达式中的字符有： *运算符“+”、“-”、“*”、“”；*左右括号“(”、“)”；*整数(可以是多位的)；*空格符和制表符。例如：表达式为“20+(3*(4+46)-6)2-134”将得到结果-42。数据结构采用二叉树的链接表示。二、题目分析 由设计要求可以确定程序的几大模块，读入源程序 （1）读入中缀
2、表达式 （2）从中缀表达式ex(长度为n)创建二叉树 （3）后根遍历计算表达式的值 （4） 输出运算结果 进一步确定几个子程序及其相互之间的调用关系为： 三流程图四全局变量与子程序功能说明（1） int extoBinTree(PBinTree pbtree,const char *ex,int n)从中缀表达式ex(长度为n)创建二叉树。若是一个合法的表达式，则返回TRUE，且算法结束时*pbtree存放二叉树的根节点的地址；否则返回FALSE（2）int cal(BinTree btree,int*presult)计算二叉树btree所代表的表达式的值。若是一个合法的表达式，则返回TRUE
3、，且算法结束时*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-
4、1&(c=getchar()!=EOF&c!=n) linei+=c; linei=0;从标准输入中读入一行，作为字符串line，作用为程序执行的第一步将所输入的表达式读入五源程序（附）六测试（1）输入，编译，链接程序（2）执行程序（3）输入表达式20+(3*(4+46)-6)2-134（4）输入Y继续执行运算表达式（5）输入N结束运算程序七参考文献说明数据结构（C语言版） 严蔚敏 清华大学出版社数据结构课程设计 苏仕华 机械工业出版社数据结构实验与实训教程 邓文华 清华大学出版社 C程序设计（第二版） 谭浩强 清华大学出版社交通咨询系统设计课程设计报告1.设计要求设计一个交通咨询系统能让旅客
5、咨询从任意一个城市顶点到另一城市顶点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需费用。2.题目分析（设计思想、主要数据结构、主要代码结构、主要代码段分析）设计共分为三个部分， 1. 一是用有向图的邻接矩阵建立交通网络图的存储结构；首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。一个图的邻接矩阵表示是唯一的。除了用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要用一个具有n个元素的一维数组来存储顶点信息。2. 二是是用迪杰斯特拉（Dijkstra）算法解决源点到所有点的最短路径问题； 单源最短路径问题：即有向图（带权），我
6、们希望找出从某个源点SV到G中其余个顶点的最短路径。用迪杰斯特拉算法（按路径长度递增产生诸顶点的最短路径算法）可以求得有向图的单源最短路径。3三是用费罗伊德（Floyd）算法算出任意两点之间的最短路径最短路径的解决方法：我们可以一次吧有向网络中德没打个顶点作为源点，重复执行前面讨论的底特斯特拉算法n次，即可求出每对顶点之间的最短路径。主要数据结构：1.建立有向图的存储结构 2.迪杰斯特拉算法 3.费罗伊德算法 4.主框架函数的实现3.流程图4.全局变量与子程序功能说明主要代码结构：(1) void CreateMGraph(MGraph *G,int n,int e)建立有向图的存储结构voi
7、d CreateMGraph(MGraph *G,int n,int e)/采用邻接矩阵表示法构造有向图G，n,e表示图的当前结点数和边数 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint;/初始化邻接矩阵，权值为无限大 printf(输入%d条边的i,j及w: n,e); for(k=1;karcsij=w;/将i和j两点之间的权值赋给arcsij printf(有向图的存储结构建立完毕!n);（2）void Dijkstra(MGraph*G,int v1,int n) 迪杰斯特拉算法 /
8、用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径Pv及其权Dv /设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint、*菡枫* /Sv为真，当且仅当vs,即已求得从v1到v的最短路径 int D2MVNum,P2MVNum; int v,i,w,min; enum boolean SMVNum; for (v=1;varcsv1v;/置初始的最短路径值 if(D2vMaxint) P2v=v1;/v1是v的前趋（双亲） else P2v=0;/v无前趋 D2v1=0; Sv1=TRUE;/S集初始只有源点，源点到源点的距离为0 /开始循环，每次球得v1到某个v顶点的最短
9、路径，并加v到S集中 for(i=2;in;i+)/其余n-1个顶点*菡枫* min=Maxint; for(w=1;w=n;w+) if(!Sw&D2wmin) v=w; min=D2w; /更新当前最短路径及距离 Sv=TRUE; for(w=1;warcsvwarcsvw; P2w=v; printf(路径长度: 路径n); for(i=1;i=n;i+) printf(,D2i); printf(,i); v=P2i; while(v!=0) printf(-%d,v); v=P2v; printf(n); （3）void Floyd(MGraph*G,int n)费罗伊德算法 int
10、 i,j,k,v,w; for(i=1;i=n;i+)/设置路径长度D和路径path初值*菡枫* for(j=1;jarcsij!=Maxint) Pij=j; else Pij=0; Dij=G-arcsij; for(k=1;k=n;k+)/做k次迭代，每次均试图将顶点K扩充到点钱球得的从i到j的最短路径Pij上 for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+DkjDij) Dij=Dik+Dkj;/修改长度 Pij=Pik;/printf(dij=%d,pij=%dn,Dij,Pij); 5.源程序（附）6.测试调试过程（测试数据设计与测试结果分析）1.输
11、入源程序 编译并链接 2.执行（1）按要求输入图中的定点个数和边数n,e:4,5 （2）i,j是图中边的顶点编号，w是边的权值（3）按要求输入: 按enter键选择1，求单源路径，输入1（求顶点1到其它点的最短路径）（4）此为源点1到其它点的最短路径然后选择2后，程序调用Floyd算法输入源点和终点v，w：2,3顶点2到顶点3无路径，选择0退出。总结 1、设计中遇到的问题及解决过程 在输入i,j,w的值时对数据的输入规则不够清楚，有向图的认识不熟悉，多看几遍实验程序了解输入数据的有向单一性。2、设计中产生的错误及原因分析 在Floyd算法中v，w是无效引用的局部变量，将i=1错输为i=i让程序在求最短路径是发生错误3、设计体会和收获 对于图的认识更深入了解，了解迪杰斯特拉算法和费罗伊德算法的数据结构。7.参考文献说明数据结构（C语言版） 严蔚敏 清华大学出版社数据结构课程设计 苏仕华 机械工业出版社数据结构实验与实训教程 邓文华 清华大学出版社 C程序设计（第二版） 谭浩强 清华大学出版社（附：交通咨询系统设计源程序）#include#include#define MVNum 100/定义最大
