数据结构课程设计课程设计报告.docx

上 海 电 机 学 院 课 程 设 计 报 告课设课题： 数 据 结 构 交通咨询系统 学 院： 电 子 信 息 学 院 1专 业： 网络工程 1姓 名： 唐章武 1班 级： BX1213 指导老师： 张艳 1报告日期： 2013年12月11日 年 月 制目 录一、需求分析：1二、总体结构设计：1三、各子模块设计：2四、编程实现：3五、测试结果：6六、总结：9七、参考文献：9九、附录源代码：109一、需求分析：设计一程序，完成交通咨询系统的设计。旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。可用实例来验证迪杰斯特拉算法。要求“建立交通网络图的存储结构；解决单源最短路径问题；实现两个城市顶点之间的最短路径问题。要求：根据以上功能说明，设计程序完成功能。二、总体结构设计：输入不同数字,来控制程序执行不同的子模块并实现相应功能。图2.1主菜单总体设计结构三、各子模块设计：3.1子模块 新建城市网,按要求输入城市名字、边数以及各边权值图3.1新建城市网流程图3.2 子模块 输入出发地和目的地，咨询权值分别为路程、时间、费用的最短路径图3.2求最短路径流程图四、编程实现：鉴于实际生活中交通网络的双向性，特建立无向网来说明各城市间的交通关系。#include#include#include#define MAXLEN 100 #define INFINITY 99999 /定义一个很大的数,邻接矩阵边的初始权值/图的邻接矩阵存储结构如下：typedef structchar vexsMAXLENMAXLEN;float edges_pathMAXLENMAXLEN; /以路径为边的权值float edges_moneyMAXLENMAXLEN; /以费用为边的权值float edges_timeMAXLENMAXLEN; /以时间为边的权值int n,e;MGraph;/建立一个无向图的邻接矩阵存储的算法简略如下：MGraph *CreateMGraph()int i,j,k;float weight_path,weight_money,weight_time; char ch1MAXLEN,ch2MAXLEN;MGraph *G;G=(MGraph *)malloc(sizeof(MGraph);/ 邻接矩阵初始化for (i=0; in; i+)for (j=0; jn; j+)G-edges_pathij=INFINITY;G-edges_moneyij=INFINITY;G-edges_timeij=INFINITY;/给无向图的边赋初值for(i=0;strcmp(ch1,G-vexsi)!=0; i+);for(j=0;strcmp(ch2,G-vexsj)!=0; j+);G-edges_pathij=weight_path; G-edges_pathji=weight_path;G-edges_moneyij=weight_money;G-edges_moneyji=weight_money;G-edges_timeij=weight_time;G-edges_timeji=weight_time;/函数功能，找到城市名字在邻接矩阵中对应的下标int Tranform_Name_int(MGraph *G,char v0_Name,char vl_Name,int &v0,int &vl)/v0为起始顶点在邻接矩阵顶点数组中的下标。/P为二维的布尔矩阵类型，矩阵P用来存储当前已经求得的所有最短路径；/若Pvw为true,则w是当前求得的从v0到v最短路径上的顶点/D为浮点型型数组类型，数组D用来存储从v0到所有顶点的带权路径长度/用Dijkstra算法求无向网G的v0顶点到其余顶点v的最短路径pv及其带权路径长度Dvvoid Shortest(MGraph *G, int v0, bool PMAXLENMAXLEN, float DMAXLEN,float *piMAXLEN)*piMAXLEN)/主函数，菜单界面printf(ntt);printf(ntt 交通咨询系统 );printf(ntt*);printf(ntt* 1-新建城市网 *);printf(ntt* 2-咨询城市间的最短路程 *);printf(ntt* 3-咨询城市间的最低费用 *);printf(ntt* 4-咨询城市间的最少时间 *);printf(ntt* 0-退出 *);五、测试结果：城市网及各边权值如图所示：5.1一交通无向网图5.1一交通无向网5.2各边权值图5.2各边权值5.3 输入1，新建城市网图5.3新建城市网5.4 输入2，咨询城市间最短路程图5.4 根据路程寻找最短路径5.5输入3，咨询城市间最低费用图5.5根据费用寻找最短路径5.6 输入4，咨询城市间最少时间图5.6根据时间寻找最短路径六、总结：本次我数据结构课程设计的课题是交通咨询系统的设计，我与同组成员黄浩一起完成，拿到课题后，先分析课题要求，然后构思，课题题目是：设计一程序，完成交通咨询系统的设计。旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。用实例来验证迪杰斯特拉算法。要求是：建立交通网络图的存储结构；解决单源最短路径问题；实现两个城市顶点之间的最短路径问题。1. 对于交通网络图的存储结构，我们采用无向图的邻接矩阵存储方式，课题要求中城市间有三个权值，分别是路程，时间，费用，我们有一个结构体中定义三个邻接矩阵方式，对于选择功能不一样，每次向迪杰斯特拉算法中传的邻接矩阵参数也不一样，实现迪杰斯特拉算法中每次单邻接矩阵。2. 对于单源最短路径，采用迪杰斯特拉算法实现，向迪杰斯特拉函数中传入起点参数，邻接矩阵参数，保存路径数组参数（用bool型实现），及最短路径总长 度参数。利用迪杰斯特拉算法实现对最短路径的寻找。本次课程设计，我们遇到我问题也是很多的，首先我们查阅资料和课本知识，设计到很多都是用C+语言写的迪杰斯特拉算法程序，由于C+和C语言之间的差异，要在理解基础上与以修改及反复调试才能保证程序最终的正常运行。在开发过程当中，我学到很多，明白了做任何事情都要有始有终，要敢于同困难作斗争，要养成独立思考的习惯。在以后的工作和生活当中，我将继续发扬这些好的作风。在同学和老师的帮助下，基本完成本次课程设计，基本达到了工资管理系统的要求。通过学习和练习C程序的设计基础，了解了一些关于C的知识。在设计过程中，好多处困惑、疑问，有是会很烦，甚至不想再做，但必须做好，所以耐着性子做好了。此时感觉有一点点成就感，也学到了一些知识。通过本次课程设计，我对图的典型的应用最短路径问题有了更深的了解，也会用迪杰斯特拉算法查找最短路径问题。小组成员分工黄浩 负责 对整个交通网络信息的存储，输入城市名得到下标，程序的整体调试。唐章武 负责 流程图的绘制，求最短路径的实现。参考文献：1 严蔚敏 吴伟民编著 数据结构 清华大学出版社，20002 黄国瑜 叶乃菁编著 数据结构 清华大学出版社，2001 3 胡学钢编著 数据结构算法设计指导 清华大学出版社，19994 王士元编著 数据结构与数据库系统 南开大学出版社，20005 李强根主编 数据结构（C+ 描述） 中国水利水电出版社， 20016 杨正宏编著 数据结构 中国铁道出版社，20027 胡学钢编著 数据结构算法设计指导 清华大学出版社，19998 殷人昆 徐孝凯编著 数据结构习题解析 清华大学出版社，20029 李春葆编著 数据结构习题与解析 清华大学出版社，200110 咨讯教育小组编著 数据结构数据结构版 中国铁道出版社，200211 陈元春等 实用数据结构基础(第二版) 中国铁道出版社.12 谭浩强 C程序设计 清华大学出版社.附录源代码：#include#include#include#define MAXLEN 100 #define INFINITY 99999 /定义一个很大的数,邻接矩阵边的初始权值/图的邻接矩阵存储的描述如下：typedef structchar vexsMAXLENMAXLEN;float edges_pathMAXLENMAXLEN; /以路径为边的权值float edges_moneyMAXLENMAXLEN; /以费用为边的权值float edges_timeMAXLENMAXLEN; /以时间为边的权值int n,e;MGraph;/建立一个无向图的邻接矩阵存储的算法如下：MGraph *CreateMGraph()int i,j,k;float weight_path,weight_money,weight_time; char ch1MAXLEN,ch2MAXLEN;MGraph *G;G=(MGraph *)malloc(sizeof(MGraph);printf(请输入城市个数和边数(输入格式为:城市个数,边数):);scanf(%d,%d,&(G-n),&(G-e);getchar();printf(请输入顶点信息(顶点标志)每个顶点以回车作为结束:n);for (i=0;in;i+) printf(请输入第%d个城市的名称:,i+1);gets(G-vexsi);for (i=0; in; i+)for (j=0; jn; j+)G-edges_pathij=INFINITY;/ 邻接矩阵初始化G-edges_moneyij=INFINITY;G-edges_timeij=INFINITY;printf (请输入每条边所对应的两个城市名称及两城市间的路程(公里)，费用(元)，时间(小时)!n);for(k=0; ke; k+) printf(请输入第%d条边的两个城市名称及两城市间的路程，费用，时间(用空格分隔)：n,k+1);scanf(%s%s%f%f%f,ch1,ch2,&weight_path,&weight_money,&weight_time);getchar();for(i=0;strcmp(ch1,G-vexsi)!=0; i+);for(j=0;strcmp(ch2,G-vexsj)!=0; j+);G-edges_pathij=weight_path; /给无向图的边赋初值G-edges_pathji=weight_path;G-edges_moneyij=weight_money;G-edges_moneyji=weight_money;G-edges_timeij=weight_time;G-edges_timeji=weight_time;return G;/函数功能，找到城市名字在邻接矩阵中对应的下标int Tranform_Name_int(MGraph *G,char v0_Name,char vl_Name,int &v0,int &vl)int i;for(i=0;in;i+)if(strcmp(v0_Name,G-vexsi)=0)v0=i;if(strcmp(vl_Name,G-vexsi)=0)vl=i;return v0;/v0为起始顶点在邻接矩阵顶点数组中的下标。/P为二维的布尔矩阵类型，矩阵P用来存储当前已经求得的所有最短路径；/若Pvw为true,则w是当前求得的从v0到v最短路径上的顶点/D为浮点型数组类型，数组D用来存储从v0到所有顶点的带权路径长度/用Dijkstra算法求无向网G的v0顶点到其余顶点v的最短路径pv及其带权路径长度Dvvoid Shortest(MGraph *G, int v0, bool PMAXLENMAXLEN, float DMAXLEN,float *piMAXLEN) int v,w,i,j;float min;bool finalMAXLEN; /finalv为true，当前仅当v属于S，即已经求得从v0到v的最短路径for(v=0; vn; v+) finalv=false;/ 初始化S集合为空for(w=0; wn; w+)/ 初始化最短路径矩阵PPvw=false; / 没有存储任何最短路径，所以全部元素均为FalseDv=piv0v;/ 初始的最短路径长度设置为v0到相应顶点弧的权值if (DvINFINITY) / 若v0到顶点v的弧存在，则在P中设置好相应路径 Pvv0=true; / 设置v0到自身的最短路径为0Pvv=true; Dv0=0; finalv0=true;/ 将顶点v0加入到已选取顶点集合S中 for (i=1;in;i+)min=INFINITY;for(w=0;wn;w+) / 查找尚未加入到集合S中，并且带权路径长度最小的最短路径终点，该终点的下标保存在v中 if (!finalw & Dwmin) / 更新v的值 v=w; min=Dw; finalv=true; / 将顶点v加入到已选取顶点集合S中for(w=0;wn;w+) / 更新当前最短带权路径长度 if (!finalw&min+pivwDw) Dw=min+pivw; / 向量D及路径矩阵Pfor(j=0;jn;j+)if(Pvj=true)Pwj=Pvj;Pww=true;/主函数，菜单界面void main()MGraph *G=NULL;float *piMAXLEN;int m=1,i,j;char v0_NameMAXLEN,vl_NameMAXLEN;int v0,vl; /v0为起始点的下标,vl为终点的下标char choice,ch;bool PMAXLENMAXLEN;float DMAXLEN;while(m)printf(ntt);printf(ntt 交通咨询系统 );printf(ntt*);printf(ntt* 1-新建城市网 *);printf(ntt* 2-咨询城市间的最短路程 *);printf(ntt* 3-咨询城市间的最低费用 *);printf(ntt* 4-咨询城市间的最少时间 *);printf(ntt* 0-退出 *);printf(ntt 请输入你的选择(0-4):);scanf(%c,&choice);getchar();switch(choice)case 1:G=CreateMGraph();break;case 2:if(G=NULL)printf(城市网不存在，请先建立一个城市网!);elseprintf(n请输入你要查询的(出发地，目的地)两个城市名称(以空格分隔):);scanf(%s%s,v0_Name,vl_Name);getchar();v0=INFINITY;vl=INFINITY;Tranform_Name_int(G,v0_Name,vl_Name,v0,vl);if(v0=INFINITY|vl=INFINITY)printf(n对不起！您输入出发地或者目的地不在地图中，请重新输入);break;for(i=0;in;i+)pii=G-edges_pathi;Shortest(G,v0,P,D,pi);printf(n您从出发地(%s)到目的地(%s)的最短路程长度为:%.2f公里,v0_Name,vl_Name,Dvl);if(Dvl=INFINITY)printf(%s与%s间无路径,G-vexsv0,G-vexsvl);elseprintf(n最短路径为:);printf(%s,G-vexsv0);for(j=0;jn;j+)for(j=0;jn;j+)if(Pvlj=true&vl!=j&v0!=j)printf(-%s,G-vexsj);printf(-%s,G-vexsvl);printf(nn);break;case 3:if(G=NULL)printf(城市网不存在，请先建立一个城市网!);elseprintf(n请输入你要查询的(出发地，目的地)两个城市名称(以空格分隔):);scanf(%s%s,v0_Name,vl_Name);getchar();v0=INFINITY;vl=INFINITY;Tranform_Name_int(G,v0_Name,vl_Name,v0,vl);if(v0=INFINITY|vl=INFINITY)printf(n对不起！您输入出发地或者目的地不在地图中，请重新输入);break;for(i=0;in;i+)pii=G-edges_moneyi;Shortest(G,v0,P,D,pi);printf(n您从出发地(%s)到目的地(%s)的最低费用为:%.2f元,v0_Name,vl_Name,Dvl);if(Dvl=INFINITY)printf(%s与%s间无路径,G-vexsv0,G-vexsvl);printf(n最短路径为:);printf(%s,G-vexsv0);for(j=0;jn;j+)for(j=0;jn;j+)if(Pvlj=true&vl