数据结构课设 表达式求值

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=

4、0; while(i<limit-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语言版） 严蔚敏 清华大学出版社数据结构课程设计 苏仕华 机械工业出版社数据结构实验与实训教程 邓文华 清华大学出版社

5、 C程序设计（第二版） 谭浩强 清华大学出版社交通咨询系统设计课程设计报告1.设计要求设计一个交通咨询系统能让旅客咨询从任意一个城市顶点到另一城市顶点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需费用。2.题目分析（设计思想、主要数据结构、主要代码结构、主要代码段分析）设计共分为三个部分， 1. 一是用有向图的邻接矩阵建立交通网络图的存储结构；首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。一个图的邻接矩阵表示是唯一的。除了用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要用一个具有n个元素的一维数组来存储顶点信息。2.

6、二是是用迪杰斯特拉（Dijkstra）算法解决源点到所有点的最短路径问题； 单源最短路径问题：即有向图（带权），我们希望找出从某个源点SV到G中其余个顶点的最短路径。用迪杰斯特拉算法（按路径长度递增产生诸顶点的最短路径算法）可以求得有向图的单源最短路径。3三是用费罗伊德（Floyd）算法算出任意两点之间的最短路径最短路径的解决方法：我们可以一次吧有向网络中德没打个顶点作为源点，重复执行前面讨论的底特斯特拉算法n次，即可求出每对顶点之间的最短路径。主要数据结构：1.建立有向图的存储结构 2.迪杰斯特拉算法 3.费罗伊德算法 4.主框架函数的实现3.流程图4.全局变量与子程序功能说明主要代码结构：

7、(1) void CreateMGraph(MGraph *G,int n,int e)建立有向图的存储结构void CreateMGraph(MGraph *G,int n,int e)/采用邻接矩阵表示法构造有向图G，n,e表示图的当前结点数和边数 int i,j,k,w; for(i=1;i<=n;i+)/输入顶点信息 G->vexsi=(char)i; for(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=Maxint;/初始化邻接矩阵，权值为无限大 printf("输入%d条边的i,j及w: n",e

8、); for(k=1;k<=e;k+)/读入e条边，建立邻接矩阵 scanf("%d %d %d",&i,&j,&w);/顶点i到顶点j的权值w G->arcsij=w;/将i和j两点之间的权值赋给arcsij printf("有向图的存储结构建立完毕!n");（2）void Dijkstra(MGraph*G,int v1,int n) 迪杰斯特拉算法 /用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径Pv及其权Dv /设G是有向图的邻接矩阵，若边<i,j>不存在，则Gij=Maxint、

9、*菡枫* /Sv为真，当且仅当vs,即已求得从v1到v的最短路径 int D2MVNum,P2MVNum; int v,i,w,min; enum boolean SMVNum; for (v=1;v<=n;v+)/初始化S和D Sv=FALSE;/置空最短路径终点集 D2v=G->arcsv1v;/置初始的最短路径值 if(D2v<Maxint) P2v=v1;/v1是v的前趋（双亲） else P2v=0;/v无前趋 D2v1=0; Sv1=TRUE;/S集初始只有源点，源点到源点的距离为0 /开始循环，每次球得v1到某个v顶点的最短路径，并加v到S集中 for(i=2;

10、i<n;i+)/其余n-1个顶点*菡枫* min=Maxint; for(w=1;w<=n;w+) if(!Sw&&D2w<min) v=w; min=D2w; /更新当前最短路径及距离 Sv=TRUE; for(w=1;w<=n;w+) if(!Sw&&(D2v+G->arcsvw<D2w) D2w=D2v+G->arcsvw; P2w=v; printf("路径长度: 路径n"); for(i=1;i<=n;i+) printf("",D2i); printf("

11、;",i); v=P2i; while(v!=0) printf("<-%d",v); v=P2v; printf("n"); （3）void Floyd(MGraph*G,int n)费罗伊德算法 int i,j,k,v,w; for(i=1;i<=n;i+)/设置路径长度D和路径path初值*菡枫* for(j=1;j<=n;j+) if(G->arcsij!=Maxint) Pij=j; else Pij=0; Dij=G->arcsij; for(k=1;k<=n;k+)/做k次迭代，每次均试图将顶点

12、K扩充到点钱球得的从i到j的最短路径Pij上 for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj;/修改长度 Pij=Pik;/printf("dij=%d,pij=%dn",Dij,Pij); 5.源程序（附）6.测试调试过程（测试数据设计与测试结果分析）1.输入源程序 编译并链接 2.执行（1）按要求输入图中的定点个数和边数n,e:4,5 （2）i,j是图中边的顶点编号，w是边的权值（3）按要求输入: 按enter键选择1，求单源路径，输入1（求顶点1到其它点的最短路径）（4）此为

13、源点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语言版） 严蔚敏 清华大学出版社数据结构课程设计 苏仕华 机械工业出版社数据结构实验与实

14、训教程 邓文华 清华大学出版社 C程序设计（第二版） 谭浩强 清华大学出版社（附：交通咨询系统设计源程序）#include<stdio.h>#include<stdlib.h>#define MVNum 100/定义最大的定点数#define Maxint 32767/初始定义两点之间的权值无限大enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef struct VertexType vexsMVNum;/顶点数组，类型假定为char型 Adjmatrix arcsMVN

15、umMVNum;/链接矩阵，假定为int型MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;/定义三个函数void CreateMGraph(MGraph *G,int n,int e);/建立有向图的存储结构void Dijkstra(MGraph *G,int v1,int n);/迪杰斯特拉算法void Floyd(MGraph *G,int n);/弗洛伊德算法/主函数/void main() MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGr

16、aph);/创建一个新的结点 printf("输入图中顶点个数(n)和边数(e): "); scanf("%d %d",&n,&e); CreateMGraph(G,n,e);/建立有向图的存储结构 while(xz!=0) printf("*求城市之间的最短路径*n"); printf("=n"); printf("1.求一个城市到所有城市的最短路径n"); printf("2.求任意的两个城市之间的最短路径n"); printf("=n"

17、;); printf("请选择: 1 或 2,选择 0 退出: "); scanf("%d",&xz); if(xz=2) Floyd(G,n);/调用佛洛依德算法 printf("输入源点(或称起点)和终点：v,w: "); scanf("%d,%d",&v,&w); k=Pvw;/k为起点v的后继顶点 if(k=0) printf("顶点%d 到 %d 无路径!n",v,w); else printf("从顶点%d到%d的最短路径是: %d",v,

18、w,v); while(k!=w) printf("->%d",k);/输出终点 k=Pkw;/继续找下一个后继顶点 printf("->%d",w);/输出终点w printf("路径长度: %dn",Dvw); else if(xz=1) printf("求单源路径,输入源点 v: "); scanf("%d",&v); Dijkstra(G,v,n);/调用迪杰斯特拉算法 printf("结束求最短路径,再见! n");/创建有向图的存储结构/voi

19、d CreateMGraph(MGraph *G,int n,int e)/采用邻接矩阵表示法构造有向图G，n,e表示图的当前结点数和边数 int i,j,k,w; for(i=1;i<=n;i+)/输入顶点信息 G->vexsi=(char)i; for(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=Maxint;/初始化邻接矩阵，权值为无限大 printf("输入%d条边的i,j及w: n",e); for(k=1;k<=e;k+)/读入e条边，建立邻接矩阵 scanf("%d %d %d&

20、quot;,&i,&j,&w);/顶点i到顶点j的权值w G->arcsij=w;/将i和j两点之间的权值赋给arcsij printf("有向图的存储结构建立完毕!n");/迪杰斯特拉算法/void Dijkstra(MGraph *G,int v1,int n) /用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径Pv及其权Dv /设G是有向图的邻接矩阵，若边<i,j>不存在，则Gij=Maxint、*菡枫* /Sv为真，当且仅当vs,即已求得从v1到v的最短路径 int D2MVNum,P2MVNum; int

21、v,i,w,min; enum boolean SMVNum; for (v=1;v<=n;v+)/初始化S和D Sv=FALSE;/置空最短路径终点集 D2v=G->arcsv1v;/置初始的最短路径值 if(D2v<Maxint) P2v=v1;/v1是v的前趋（双亲） else P2v=0;/v无前趋 D2v1=0; Sv1=TRUE;/S集初始只有源点，源点到源点的距离为0 /开始循环，每次球得v1到某个v顶点的最短路径，并加v到S集中 for(i=2;i<n;i+)/其余n-1个顶点*菡枫* min=Maxint; for(w=1;w<=n;w+) if

22、(!Sw&&D2w<min) v=w; min=D2w; /更新当前最短路径及距离 Sv=TRUE; for(w=1;w<=n;w+) if(!Sw&&(D2v+G->arcsvw<D2w) D2w=D2v+G->arcsvw; P2w=v; printf("路径长度: 路径n"); for(i=1;i<=n;i+) printf("",D2i); printf("",i); v=P2i; while(v!=0) printf("<-%d",

23、v); v=P2v; printf("n"); /佛洛依德算法/void Floyd(MGraph *G,int n) int i,j,k,v,w; for(i=1;i<=n;i+)/设置路径长度D和路径path初值*菡枫* for(j=1;j<=n;j+) if(G->arcsij!=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

24、;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj;/修改长度 Pij=Pik;/printf("dij=%d,pij=%dn",Dij,Pij); （附：表达式求值源程序）#include<stdio.h>#include<stdlib.h>#include<string.h>#define TRUE 1#define FALSE 0#define MAXNUM 1000typedef int DataType;struct BinTreeNode;typedef struct BinTreeNode*PBinTre

25、eNode;struct BinTreeNode DataType info; PBinTreeNode llink; PBinTreeNode rlink;typedef struct BinTreeNode*BinTree;typedef BinTree*PBinTree;int extoBinTree(PBinTree pbtree,const char *ex,int n)/*从中缀表达式ex(长度为n)创建二叉树。若是一个合法的表达式，则返回TRUE，且算法结束时*pbtree存放二叉树的根节点的地址；否则返回FALSE*/ char c; int index,i,bracket;

26、int have_bracket=FALSE; /*记录表达式中是否包含括号*/ int num,state_int,nint; int tag1,tag2; if(ex0=' '|ex0='t'|ex0='n') return extoBinTree(pbtree,ex+1,n-1);/*忽略掉左边的若干空字符*/ if(exn-1=' '|ex0='t'|ex0='n') return extoBinTree(pbtree,ex,n-1);/*忽略掉右边的若干空字符*/ if(ex0='

27、('&&exn-1=')') return extoBinTree(pbtree,ex+1,n-2);/*忽略掉左右的成对括号*/ bracket=0; index=n; for(i=n-1;i>=0;i-)/*从后向前搜索，寻找到第一个不在括号中的优先级最低的运算符*/ c=exi; if(c=')')/*进入一层括号*/ have_bracket=TRUE; bracket+; if(c='(') bracket-;/*出一层括号*/ if(bracket<0)/*左右括号不相匹配，表达式非法*/ *pbt

28、ree=NULL; return FALSE; if(bracket>0) continue;/*若当前位置在某层括号中，直接搜索下个位置*/ if(c='+'|c='-') if(index=n|exindex='*'|exindex='/') index=i; if(c='*'|c='/') if(index=n) index=i; if(bracket!=0) return FALSE;/*左右括号不相匹配，表达式非法*/ if(index=n)/*说明这是一个只含一个数字和若干空字符的

29、表达式，相应地创建一棵只含一个根节点的二叉树*/ if(have_bracket=TRUE) *pbtree=NULL; return FALSE; /*不应含有括号*/ nint=0;/*nint记录表达式中含有的整数个数*/ state_int=FALSE;/*state_int记录当前读入的字符是否是数字字符*/ num=0; for(i=0;i<n;i+) c=exi; switch(c) case'0':case'1':case'2':case'3':case'4': case'5'

30、:case'6':case'7':case'8':case'9': if(state_int=FALSE) num=c-'0' state_int=TRUE; nint+; else num=num*10+c-'0' break; case' ':case't':case'n': state_int=FALSE; break; default: /*出现了非法字符*/ *pbtree=NULL; return FALSE; if(nint!=1) *p

31、btree=NULL; return FALSE; *pbtree=(BinTree)malloc(sizeof(struct BinTreeNode); (*pbtree)->info=num; (*pbtree)->llink=NULL; (*pbtree)->rlink=NULL; return TRUE; /*成功创建了一棵只含一个根节点的二叉树*/ *pbtree=(BinTree)malloc(sizeof(struct BinTreeNode); (*pbtree)->info=exindex; tag1 =extoBinTree(&(*pbtre

32、e)->llink,ex,index);/*递归调用本算法创建左子数*/ tag2 =extoBinTree(&(*pbtree)->rlink,ex+index+1,n-index-1);/*递归调用本算法创建右子数*/ if(tag1=TRUE&&tag2=TRUE) return TRUE; return FALSE;int cal(BinTree btree,int*presult)/*计算二叉树btree所代表的表达式的值。若是一个合法的表达式，则返回TRUE，且算法结束时*presult中存放计算结果；否则，返回FALSE.*/ int resu

33、lt1,result2; if(btree=NULL) return FALSE; /*空树，无法计算*/ if(btree->llink=NULL&&btree->rlink=NULL) /*只有一个节点，直接计算*/ *presult=btree->info; return TRUE; if(btree->llink=NULL|btree->rlink=NULL) /*只有左子树或只有右子树，无法计算*/ return FALSE; switch(btree->info) case'+': if(cal(btree->

34、;llink,&result1)=FALSE) return FALSE; if(cal(btree->rlink,&result2)=FALSE) return FALSE; *presult=result1+result2; return TRUE; case'-': if(cal(btree->llink,&result1)=FALSE) return FALSE; if(cal(btree->rlink,&result2)=FALSE) return FALSE; *presult=result1-result2; return TRUE; case'*': if(cal(btree->llink,&result1)=FALSE) return FALSE; if(cal(btree->rlink,&result2)=FALSE) return FALSE; *presult=result1*result2; return TRUE; case'/': if(cal(btree->llink,&result1)=FALSE) return FALSE; if(cal(btree->rlink,&result2)=F