重庆科技学院《数据结构》课程设计报告学院:_电气与信息工程学院_ 专业班级: 计科2学生姓名: 学号:设计地点（单位）__ _ 计算机基础自主学习中心__ _ _设计题目:________ 交通咨询系统设计__ ___ _ _完成日期：2012年7 月6 日指导教师评语: ______________________ _________________________________________________________________________________________________________________ _________________________________________________________________________________________________________ __________ _成绩（五级记分制）:______ __________指导教师（签字）:________ ________重庆科技学院课程设计任务书设计题目：交通咨询系统的设计系主任：雷亮指导教师：黄永文/王双明/熊茜/彭军/王成敏2012年6月20日摘要在交通网络非常发达，人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。
对于这样一个人们关心的问题，可以用一个图结构来表示交通网络，利用计算机建立一个交通咨询系统。
图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。
比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。
本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。
关键词：数字结构C语言交通咨询最短路径目录1 设计内容和要求 (1)1.1 问题描述 (1)1.2需求分析 (1)2 课程需求分析 (2)2.1 算法思路 (2)2.2 数据结构体 (2)2.3 基本操作 (4)2.4 算法应用 (4)2.5 程序设计流程图 (5)3 功能模块详细设计 (6)3.1 测试数据 (6)3.2 程序调试 (7)4 课程总结与体会 (24)5参考文献 (26)6 致谢 (27)1 设计内容和要求1.1 问题描述：设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）里程最少。
1.2需求分析：该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。
此程序规定：（1）在程序中输入城市名称时，需输入20个字符以内的字符串；输入费用时需输入一个实型数据；输入时间时需输入一个整型数据；在选择功能时，应输入与所选功能对应的一个整型数据。
（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或两城市间需要走过的最短路程，并详细说明如何坐车才能最省。
（3）程序的功能包括：提供对城市信息的编辑，对两城市间时间、花费、还有路程的编辑，提供三种最优决策：最快到达、最省钱到达、最少路程到达。
2 课程需求分析2.1 算法思路(1) 数据存储。
城市信息、交通信息(城市间的里程、旅费和时间)存储于磁盘文件。
建议把城市信息、交通信息还有城市和交通信息数目分开存于三个文件中，用fread和fwrite函数操作。
(2) 数据的逻辑结构。
根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间、旅费、里程。
(3) 数据的存储结构。
采用邻接矩阵作为数据的存储结构，提高空间的存储效率。
(4) 用不同的功能模块对城市信息和交通信息进行编辑，可用菜单方式或命令提示方式。
只要能方便的对城市信息和交通信息进行管理即可。
(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。
2.2 数据结构体typedef struct lu /* 交通信息数据类型*/{int distance; /*城市间里程*/int cost; /*城市间旅费*/int time; /*城市间时间*/}lu,lujin[max][max];typedef struct city /*城市数据类型*/ {char name[20];/*城市名称*/}citys[max];typedef struct /*网络图的数据类型*/ {citys clist; /*城市信息*/lujin arcs; /*边的信息*/int c_n,l_n; /*边和顶点数目*/}Graph;typedef struct /*最短路径*/{char adjvex;int mincost;/*最少旅费*/int mindistance;/*最短里程*/int mintime;/*最少时间*/}closedge;2.3 基本操作void zairu(Graph *G);/*导入文件中的信息，能否是程序运行*/void Administer(Graph G);/*管理员操作界面，由主函数调用*/void show(Graph G);/*显示系统中的全部城市信息和交通信息*/int insertcity(Graph *G); /*增加城市信息*/int insertlu(Graph *G); /*增加交通信息*/int Located(Graph *G, char *p);/* 返回邻接矩阵的位置下标，系统中的关键*/ void baocun(Graph G);/*将城市信息、交通信息保存在文件中*/int serchlu(Graph *G);/*搜索交通信息*/void mindistance(Graph *G, int v0, int v1);/*最少里程计算，迪杰斯特拉算法*/ void mincost(Graph *G, int v0, int v1);/*最少旅费计算，迪杰斯特拉算法*/void mintime(Graph *G, int v0, int v1);/*最少时间计算，迪杰斯特拉算法*/ 2.4 算法应用在判断源点到其余各点的最短路径时运用迪杰斯特拉算法：一般情况下，假设S为以求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为x）或者是弧(v,k)，或者是中奖只经过S中的顶点而最后到达顶点x的路径。
这可用反证法来证明，假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比此路径短的路径。
但是，这是不可能的。
因为我们是按照路径长度递增的次序来产生各最短路径的，故长度比此路径段的所有路径均已产生，它们的终点必定在S中，即假设不成立。
因此，在一般情况下，下一条长度次短的最短路径的长度必是i v i D Min j |][{][D =}S V -∈其中，D[i]或者是弧()i v v ,上的权值，或者是D[k])(S v k ∈和弧()i k v v ,上的权值之和。
（1）假设用带权的邻接矩阵arcs 来表示带权有向图，arcs[i][j]表示弧v <vi,vj>上的权值。
若<vi,vj>存在，则置arcs[i][j]为∞(在计算机上可用允许的最大值代替)。
S 为已找到从v 出发的最短路径的终点的集合，他的初始状态为空集。
那么，从v 出发到图上其余个顶点(终点)vi 可能达到的最短路径长度的初值为：V v i v G Vex Locatearc i D i ∈=])[,([][（2）选择j v ，使得}S |][D {][-∈=V v i Min i D ij v 就是当前求得的一条从v 出发的最短路径的终点。
令}{j S S ⋃=(3)修改从v 出发到集合V-S 上任一顶点k v 可达的最短路径长度。
如果][]][[][k D k j arcs i D <+则修改][k D 为]][[][][k j arcs j D k D +=(4)重复操作(2)、(3)共n-1次。
由此求得从v 到图上其余各点的最短路径是依路径长度递增的序列。
2.5 程序设计流程图：图2.1程序设计流程图3 功能模块详细设计 3.1 测试数据表3.2交通信息表交通咨询系统管理员用户 添加城市查询最少花费路线 查询最短时间路线 查询最短里程路线 退出添加交通路线 返回上一级菜单 返回上一级菜单显示所有交通路线1.主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理；选项二：用户咨询界面，选择该项可进行最少费用、最少时间、最短里程的决策咨询；选项三：显示城市交通系统，选择该项可显示城市交通系统的所有信息，包括城市、交通路线信息；选项四：退出程序，选择该项将退出程序。
图3.1程序主界面在该系统运行的开始会从文件读取交通信息，如果文件不存在会导致程序运行错误！出现下图情况：图3.2文件不存在该函数代码如下：void zairu(Graph *G)//读取文本中的信息{FILE *fpout, *fpin;int cnum, lnum;char Fromc[20], Toc[20];int t, i, j;for(i = 0; i < max; i++)for(j = 0; j < max; j++){G->arcs[i][j].distance = G->arcs[j][i].distance = zuida;G->arcs[i][j].cost = G->arcs[j][i].cost = zuida;G->arcs[i][j].time = G->arcs[j][i].time = zuida;}fpout = fopen("number.txt", "r");assert(fpout);if(fscanf(fpout, "%d %d", &cnum,&lnum)== 2){G->c_n = cnum;G->l_n = lnum;fclose(fpout);//读取城市顶点信息fpout = fopen("city.txt", "r");for(t = 0; t < G->c_n; t++)fscanf(fpout, "%s", G->clist[t].name);fclose(fpout);//读取边的信息.(起点、终点、距离(千米)、花费(元)、时间(分钟))fpout = fopen("lu.txt", "r");for(t = 0; t < G->l_n; t++){fscanf(fpout, "%s %s", Fromc, Toc);i = Located(G, Fromc);j = Located(G, Toc);fscanf(fpout, "%d %d %d", &G->arcs[i][j].distance, &G->arcs[i][j].cost, &G->arcs[i][j].time);G->arcs[j][i].distance = G->arcs[i][j].distance;G->arcs[j][i].cost = G->arcs[i][j].cost;G->arcs[j][i].time = G->arcs[i][j].time;}fclose(fpout);}else{fpin = fopen("number.txt", "w");assert(fpin);fprintf(fpin, "0 0");G->l_n = 0;G->c_n = 0;fclose(fpin);}}2．管理员管理界面首先出现登陆界面，采用加密技术，初始密码为admin，菜单项包括5 个选项：选项一：增加城市信息；选项二：增加交通路线信息；选项三：保存新增信息，返回上一级菜单，可返回主界面。