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

上海电机学院课程设计报告课设课题:数据结构━━交通咨询系统学院:电子信息学院1专业:网络工程1姓名:唐章武1班级:BX1213指导老师:张艳1报告日期:2013年12月11日年月制目录一、需求分析: 1二、总体结构设计: 1三、各子模块设计: 2四、编程实现: 3五、测试结果: 6六、总结: 9七、参考文献: 9九、附录源代码: 10一、需求分析: 设计一程序,完成交通咨询系统的设计。旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求,可以输入城市间的路程或所需要时间或所需费用。可用实例来验证迪杰斯特拉算法。要求“建立交通网络图的存储结构;解决单源最短路径问题;实现两个城市顶点之间的最短路径问题。要求: 根据以上功能说明,设计程序完成功能。二、总体结构设计:输入不同数字,来控制程序执行不同的子模块并实现相应功能。、各子模块设计:,按要求输入城市名字、,咨询权值分别为路程、时间、、编程实现:鉴于实际生活中交通网络的双向性,特建立无向网来说明各城市间的交通关系。#include<>#include<>#include<>#defineMAXLEN100#defineINFINITY99999//定义一个很大的数,邻接矩阵边的初始权值//图的邻接矩阵存储结构如下:typedefstruct{ charvexs[MAXLEN][MAXLEN]; floatedges_path[MAXLEN][MAXLEN];//以路径为边的权值 floatedges_money[MAXLEN][MAXLEN];//以费用为边的权值 floatedges_time[MAXLEN][MAXLEN];//以时间为边的权值 intn,e;}MGraph;//建立一个无向图的邻接矩阵存储的算法简略如下:MGraph*CreateMGraph(){ inti,j,k; floatweight_path,weight_money,weight_time; charch1[MAXLEN],ch2[MAXLEN]; MGraph*G; G=(MGraph*)malloc(sizeof(MGraph)); //邻接矩阵初始化 for(i=0;i<G->n;i++) for(j=0;j<G->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,charv0_Name[],charvl_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]voidShortest(MGraph*G,intv0,boolP[MAXLEN][MAXLEN],floatD[MAXLEN],float*pi[MAXLEN])*pi[MAXLEN])//主函数,菜单界面 printf("\n\t\t"); printf("\n\t\t交通咨询系统"); printf("\n\t\t********************************************"); printf("\n\t\t*1--新建城市网*"); printf("\n\t\t*2--