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

上海电机学院课程设计报告课设课题：数 据 结 构 ━━ 交通咨询系统学 院：电 子 信 息 学 院 1专业：网络工程 1姓 名：唐章武1班 级： BX1213指导老师：张艳 1报告日期：2013年12月11日 年月制一、需求分析：?设计一程序，完成交通咨询系统的设计。旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。可用实例来验证迪杰斯特拉算法。要求“建立交通网络图的存储结构；解决单源最短路径问题；实现两个城市顶点之间的最短路径问题。　　要求：　　根据以上功能说明，设计程序完成功能。二、总体结构设计：输入不同数字,来控制程序执行不同的子模块并实现相应功能。图2.1主菜单总体设计结构三、各子模块设计：3.1子模块新建城市网,按要求输入城市名字、边数以及各边权值图3.1新建城市网流程图3.2子模块输入出发地和目的地，咨询权值分别为路程、时间、费用的最短路径图3.2求最短路径流程图四、编程实现：鉴于实际生活中交通网络的双向性，特建立无向网来说明各城市间的交通关系。#includestdio.h#includestring.h#includestdlib.h#define MAXLEN 100 #define INFINITY 99999 //定义一个很大的数,邻接矩阵边的初始权值//图的邻接矩阵存储结构如下：typedefstruct{charvexs[MAXLEN][MAXLEN];float edges_path[MAXLEN][MAXLEN]; //以路径为边的权值float edges_money[MAXLEN][MAXLEN]; //以费用为边的权值float edges_time[MAXLEN][MAXLEN]; //以时间为边的权值intn,e;}MGraph;//建立一个无向图的邻接矩阵存储的算法简略如下：MGraph *CreateMGraph(){inti,j,k;floatweight_path,weight_money,weight_time; char ch1[MAXLEN],ch2[MAXLEN];MGraph *G;G=(MGraph *)malloc(sizeof(MGraph));// 邻接矩阵初始化for (i=0; iG-n; i++)for (j=0; jG-n; j++){G-edges_path[i][j]=INFINITY;G-edges_money[i][j]=INFINITY;G-edges_time[i][j]=INFINITY;}//给无向图的边赋初值for(i=0;strcmp(ch1,G-vexs[i])!=0; i++);for(j=0;strcmp(ch2,G-vexs[j])!=0; j++);{G-edges_path[i][j]=weight_path; G-edges_path[j][i]=weight_path;G-edges_money[i][j]=weight_money;G-edges_money[j][i]=weight_money;G-edges_time[i][j]=weight_time;G-edges_time[j][i]=weight_time;}}//函数功能，找到城市名字在邻接矩阵中对应的下标intTranform_Name_int(MGraph *G,char v0_Name[],char vl_Name[],int v0,int vl)//v0为起始顶点在邻接矩阵顶点数组中的下标。//P为二维的布尔矩阵类型，矩阵P用来存储当前已经求得的所有最短路径；//若P[v][w]为true,则w是当前求得的从v0到v最短路径上的顶点//D为浮点型型数组类型，数组D用来存储从v0到所有顶点的带权路径长度//用Dijkstra算法求无向网G的v0顶点到其余顶点v的最短路径p[v]及其带权路径长度D[v]void Shortest(MGraph *G, int v0, bool P[MAXLEN][MAXLEN], float D[MAXLEN],float *pi[MAXLEN])*pi[MAXLEN])//主函数，菜单界面printf(\n\t\t);printf(\n\t\t 交通咨询系统 );printf(\n\t\t********************************************);printf(\n\