数据结构课设表达式求值

1、计算表达式 课程设计报告标 题：计算表达式单 位：报 告 人： 指导教师： 编程环境： VC6时间： 2011 年 12 月 20 日一、设计要求 对于输入的一个中缀表达式，判断表达式是否合法。如果合法， 把中缀表达式转换成一棵二叉树，然后通过后根遍历计算表达式的 值，输出运算结果。 合法表达式不能为空，可以出现在表达式中的字符有：*运算符“ +”、“-”、“*”、“”；* 左右括号“ （”、“）”；* 整数 （可以是多位的 ）；*空格符和制表符。例如：表达式为“ 20+（3*（4+46）-6） 2-134”将得到结果 -42。 数据结构采用二叉树的链接表示。二、题目分析 由设计要求可以确定程

2、序的几大模块，读入源程序 （ 1）读入中缀表达式（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所

3、代表的表达式的值。若是一个合法的表 达式，则返回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 lim

4、it)char c;int i=0;while(ilimit-1&(c=getchar()!=EOF&c!=n)linei+=c;linei=0;从标准输入中读入一行，作为字符串line,作用为程序执行的第一步将所输入的表达式读入五源程序(附)六测试1)输入，编译，链接程序(2)执行程序C : DocuMent s and Se incsAent s and Sett ingsAdinist rat or桌面ID*Please input tlw expression：20+3*-6/2-134Result：-42Continue?(y/n)yPlease input the expressi

5、on(5) 输入N结束运算程序MC:Docuents and SettingsAdinistrator桌面 blease input the expression:20+3*-6)/2-134 Result:42Continue?(y/nnPress any key to continue七参考文献说明数据结构(C语言版)严蔚敏清华大学出版社数据结构课程设计苏仕华机械工业出版社数据结构实验与实训教程邓文华清华大学出版社C程序设计(第二版)谭浩强清华大学出版社交通咨询系统设计 课程设计报告1. 设计要求设计一个交通咨询系统能让旅客咨询从任意一个城市顶点到另 一城市顶点之间的最短路径或最低花费或最

6、少时间等问题。 对于不同 的咨询要求，可输入城市间的路程或所需费用。2. 题目分析(设计思想、主要数据结构、主要代码结构、主要代码段分析)设计共分为三个部分，1. 一是用有向图的邻接矩阵建立交通网络图的存储结构；首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点 之间相邻关系的矩阵。一个图的邻接矩阵表示是唯一的。除了用 一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要 用一个具有 n 个元素的一维数组来存储顶点信息。2. 二是是用迪杰斯特拉( Dijkstra )算法解决源点到所有点的最短 路径问题；单源最短路径问题：即有向图（带权），我们希望找出从某个 源点S V到G中其余个顶点的

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

8、raph *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 两点之间的权值赋给arcsijprintf(有向图的存储结构建立完毕 !n);( 2)void Dijkstra(MGraph*G,int v1,int n) 迪杰斯特拉算法/用Dijkstra 算

9、法求有向图 G的v1顶点到其他顶点 v的最短路径Pv及其权Dv/设G是有向图的邻接矩阵，若边 不存在，则Gij=Maxint、*菡枫*Sv为真，当且仅当 v s,即已求得从v1到v的最短路径int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for (v=1;varcsv1v;/置初始的最短路径值if(D2vMaxint)P2v=v1;/v1 是v的前趋(双亲)elseP2v=0;/v 无前趋D2v1=0;Sv1=TRUE;/S 集初始只有源点，源点到源点的距离为 0/ 开始循环，每次球得 v1 到某个 v 顶点的最短路径，并加 v 到

10、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 i,

11、j,k,v,w;for(i=1;i=n;i+)设置路径长度 D和路径path初值*菡枫*for(j=1;jarcsij!=Maxint)Pij=j;elsePij=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+Dkj tinrludr flrirfjnr MH4i lilwi iiip Mm Lili nyrtfz.enum typrdeFUrrtrKlfv*;typrdrF lt 的jnatE厮ly卩h

12、iIpV 1 rucljUrt*xlffd 口叶可”顶原抉且慧舉收屯为盅2碍 ddJiwtrfiH jrcs Hwhl | HU Hur /P 阀NCiaphLnt DiHmi.FiWitai =Lnl. D WHanl I HUHiihJHVHwiJ :M疋艾三F禹強uald Cr*ti-jphHCraHi iCPlnt町:“建立有商图的存世皓柚void DljfcrtrjCMlKaph talnt ullBt 时詔/世千刪丹壮/出 void F1H惱Fdph HCilirt nppM扁韬护需暮征主函it”*”理密打void mH利料Wraph *4?int ,.Lhl, KdT1 ；C-1

13、 hCra#* SiKillac(Ladf4HCm陞)J:创建一1、剽的池自 HH1X mi A -apn fcfr J-h A4 i- s - k 2. 执行頁D:C+lSDev98据结构实耋肛输人图中顶点个薮和边数:(1)按要求输入图中的定点个数和边数n ,e:4,5菊7罔中顶点个数和边教n , ：4巧 输入誇边的i j及卅=(2) i,j是图中边的顶点编号，w是边的权值(3)按要求输入按enter键选择1,求单源路径，输入1 (求顶点1到其它点的最短路径)(4)此为源点1到其它点的最短路径然后选择2后，程序调用Floyd算法点（或称起点和终点=V * W ：输入源点和终点v, w: 2,

14、3顶点2到顶点3无路径，选择0退出总结1、设计中遇到的问题及解决过程在输入i,j,w 的值时对数据的输入规则不够清楚， 悉，多看几遍实验程序了解输入数据的有向单一性。2、设计中产生的错误及原因分析在Floyd算法中v，w是无效引用的局部变量，将有向图的认识不熟i=1错输为i=i让程序在求最短路径是发生错误3、设计体会和收获对于图的认识更深入了解， 了解迪杰斯特拉算法和费罗伊德算法的数 据结构。7. 参考文献说明数据结构（ C 语言版）严蔚敏清华大学出版社数据结构课程设计苏仕华机械工业出版社数据结构实验与实训教程邓文华清华大学出版社C 程序设计（第二版）谭浩强清华大学出版社(附：交通咨询系统设计

15、源程序)#include#include#define MVNum 100/ 定义最大的定点数#define Maxint 32767/初始定义两点之间的权值无限大enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;/ 顶点数组，类型假定为 char 型Adjmatrix arcsMVNumMVNum;/ 链接矩阵，假定为 int 型 MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNu

16、m;/ 定义三个函数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(MGraph);/ 创建一个新的结点 printf( 输入图中顶点个数 (n) 和边数 (e): );scanf(%d %d,&n,&e);CreateMG

17、raph(G,n,e);/ 建立有向图的存储结构 while(xz!=0)printf(* 求城市之间的最短路径 *n); printf(=n); printf(1.求一个城市到所有城市的最短路径 n);printf(2.求任意的两个城市之间的最短路径 n);printf(=n); 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)pr

18、intf( 顶点 %d 到 %d 无路径 !n,v,w);elseprintf(”从顶点4到d的最短路径是：d,v,w,v);while(k!=w)printf(-%d,k);/输出终点k=Pkw;/继续找下一个后继顶点printf(-%d,w);/输出终点 wprintf( 路径长度 ： %dn,Dvw);elseif(xz=1)printf( 求单源路径 , 输入源点 v： );scanf(%d,&v);Dijkstra(G,v,n);/调用迪杰斯特拉算法printf( 结束求最短路径 , 再见 ! n);/ 创建有向图的存储结构 /void CreateMGraph(MGraph *G,

19、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 两点之间的权值赋给arcsijprintf(有向图的存储结构建立完毕 !n);/ / 迪杰斯特拉算法 / / void Dijkstra(MGraph *G,int v1,int n) /用Dijkstra算法求有向

20、图 G的v1顶点到其他顶点 v的最短路径Pv及其权Dv/设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint 、*菡枫*Sv为真，当且仅当 v s,即已求得从v1到v的最短路径int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for (v=1;varcsv1v;/置初始的最短路径值if(D2vMaxint)P2v=v1;/v1 是 v 的前趋(双亲)elseP2v=0;/v无前趋D2v1=0;Sv1=TRUE;/S 集初始只有源点，源点到源点的距离为 0/开始循环，每次球得v1到某个v顶点的最短路径，并加v到S集中for(i=2;

21、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);/ 佛洛依德算法 /void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=

22、n;i+)设置路径长度 D和路径path初值*菡枫*for(j=1;jarcsij!=Maxint)Pij=j;elsePij=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);(附：表达式求值源程序)#include#include#include#define TRUE 1#defi

23、ne FALSE 0#define MAXNUM 1000typedef int DataType;struct BinTreeNode;typedef struct BinTreeNode*PBinTreeNode; struct BinTreeNodeDataType info;PBinTreeNode llink;PBinTreeNode rlink;typedef struct BinTreeNode*BinTree; typedef BinTree*PBinTree;int extoBinTree(PBinTree pbtree,const char *ex,int n)/*从中缀表

24、达式ex(长度为n)创建二叉树。若是一个合法的表达式，则返回 TRUE ，且算法结束时 *pbtree 存放二叉树的根节点的 地址；否则返回 FALSE*/char c;int index,i,bracket;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

25、,ex,n-1);/* 忽略掉右边的若干空 字符 */if(ex0=(&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(bracket0) continue;/* 若当前位置在某层括号中，直接搜索下个位置 */if(c=+|c

26、=-)if(index=n|exindex=*|exindex=/) index=i;if(c=*|c=/)if(index=n)index=i;if(bracket!=0) return FALSE;/* 左右括号不相匹配，表达式非 法*/if(index=n)/* 说明这是一个只含一个数字和若干空字符的 表达式，相应地创建一棵只含一个根节点的二叉树 */if(have_bracket=TRUE)*pbtree=NULL;return FALSE;/* 不应含有括号 */nint=0;/*nint 记录表达式中含有的整数个数 */ state_int=FALSE;/*state_int 记录

27、当前读入的字符是 否是数字字符 */num=0;for(i=0;iinfo=num;(*pbtree)-llink=NULL;(*pbtree)-rlink=NULL;return TRUE; /* 成功创建了一棵只含一个根节 点的二叉树 */*pbtree=(BinTree)malloc(sizeof(struct BinTreeNode); (*pbtree)-info=exindex;tag1 =extoBinTree(&(*pbtree)-llink,ex,index);/* 递归调用本 算法创建左子数 */tag2 =extoBinTree(&(*pbtree)-rlink,ex+i

28、ndex+1,n-index-1);/* 递归调用本算法创建右子数 */if(tag1=TRUE&tag2=TRUE) return TRUE;int cal(BinTree btree,int*presult)/* 计算二叉树 btree 所代表的表达 式的值。若是一个合法的表达式，则返回 TRUE ，且算法结束时 *presult 中存放计算结果；否则，返回 FALSE.*/int result1,result2;if(btree=NULL) return FALSE; /* 空树，无法计 算*/if(btree-llink=NULL&btree-rlink=NULL) /* 只 有一个节

29、点，直接计算 */*presult=btree-info;return TRUE;if(btree-llink=NULL|btree-rlink=NULL) /* 只有左 子树或只有右子树，无法计算 */return FALSE;switch(btree-info)case+:return FALSE;return FALSE;return FALSE;return FALSE;return FALSE;return FALSE;if(cal(btree-rlink,&result2)=FALSE)*presult=result1+result2;return TRUE;case-:if(cal(btree-llink,&result1)=FALSE)if(cal(btree-rlink,&result2)=FALSE)*presult=result1-result2;return TRUE;case*:if(cal(btree-llink,&result1)=FALSE)if(cal(btree-rlink,&re