交通咨询系统设计报告

重庆科技学院

《数据结构》课程设计

报告

学 院:_电气与信息工程学院_ 专业班级: 计科2 学生姓名: 学 号:

设计地点（单位）__ _ 计算机基础自主学习中心 __ _ _ 设计题目:________ 交通咨询系统设计__ ___ _ _ 完成日期：2012年 7 月 6 日

指导教师评语: ______________________ _________________

_________________________________________________________________________________________________________________________________________________________________________________________________________ __________ _

成绩（五级记分制）:______ __________

指导教师（签字）:________ ________

重庆科技学院 课程设计任务书

设计题目：交通咨询系统的设计 学生姓名 课程名称 地 点 设计内容及要求 数据结构课程设计 专业班级 计 计算机基础自主学习中心 起止时间 2012.6.25-2012.7.6 人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。可以用一个图结构来表示交通网络，图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。设计一个交通咨询系统，能让旅客咨询从任一个城市到另一个城市之间的最短路径（里程）、最少交通费用或最少时间等问题。 该设计的内容主要分两部分：一是建立交通网络图的存储结构；二是实现求两个城市顶点之间的最短路径算法。 要求表示城市之间的交通关系的边的信息中包括里程、费用、时间三个值。程序可实现求任两个城市之间的最短里程、最少时间或最少费用的路线。建立图的存储结构时要求从文本文件中读入顶点和边的信息。 设 测试数据要求： 计 交通图中顶点数不少于16个，边数不少于20，每条边有三个权值（里程、交通参费用、时间）。 数 2012.6.25 完成任务的讲解、并接受课程设计任务，选定课程设计的题目 2012.6.26 了解任务的算法、并画出算法的程序流程图，对任务的关键技术进行验证、并确定解决办法 进2012.6.27-2012.6.29 程序设计及编码，上机调试 度 2012.7.02 对程序进行调试，设计测试用例进行测试 要2012.7.03 整理课程设计的过程、并进行总结，完善程序功能 求 2012.7.04 编写课程设计报告初稿 2012.7.05 完善课程设计报告、并准备答辨 2012.7.06 提交课程设计报告和程序，进行答辨 参1．严蔚敏 吴伟民， 数据结构，清华大学出版社，2007.3 考资2．程杰 ，大话数据结构，清华大学出版社，2011.6 （美）Stephen Prata, C Primer Plus中文版（第五版），人民邮电出版社，2005.2 料 3．其它 说1.本表应在每次实施前一周由负责教师填写二份，学院审批后交学院教务办备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计明 内容、参数、要求等方面应有所区别。 系主任：雷亮 指导教师：黄永文/王双明/熊茜/彭军/王成敏 2012年 6月 20日

摘要

在交通网络非常发达，人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。对于这样一个人们关心的问题，可以用一个图结构来表示交通网络，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通情况，其权值可代表里程、交通费用或时间。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。

本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。 关键词：数字结构 C语言 交通咨询 最短路径

目录

1 设计内容和要求 .......................................................... 1

1.1 问题描述 ....................................................... 1

1.2需求分析 ........................................................ 1

2 课程需求分析 ............................................................ 2

2.1 算法思路 ....................................................... 2

2.2 数据结构体 ..................................................... 2

2.3 基本操作 ....................................................... 3

2.4 算法应用 ....................................................... 3

2.5 程序设计流程图 ................................................. 4

3 功能模块详细设计 ........................................................ 5

3.1 测试数据 ....................................................... 5

3.2 程序调试 ....................................................... 6

4 课程总结与体会 ........................................................ 19

5参考文献 ............................................................... 20

6 致谢 ................................................................... 21

重庆科技学院《数据结构》课程设计报告

1 设计内容和要求

1.1 问题描述：

设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方 案：（1）时间最短（2）费用最小（3）里程最少。

1.2需求分析：

该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交 通咨询。此程序规定：

（1） 在程序中输入城市名称时，需输入20个字符以内的字符串；输入费用时需输入一个实型数据；输入时间时需输入一个整型数据；在选择功能时，应输入与所选功能对应的一个整型数据。

（2） 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少 旅费才能到达，或两城市间需要走过的最短路程，并详细说明如何坐车才能最省。 （3） 程序的功能包括：提供对城市信息的编辑，对两城市间时间、花费、还有路程的编辑，提供三种最优决策：最快到达、最省钱到达、最少路程到达。

1

重庆科技学院《数据结构》课程设计报告

该函数代码如下：

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(\ assert(fpout);

if(fscanf(fpout, \ { G->c_n = cnum; G->l_n = lnum; fclose(fpout); //读取城市顶点信息

fpout = fopen(\ for(t = 0; t < G->c_n; t++)

fscanf(fpout, \

fclose(fpout);

//读取边的信息.(起点、终点、距离(千米)、花费(元)、时间(分钟)) fpout = fopen(\ for(t = 0; t < G->l_n; t++)

{

7

重庆科技学院《数据结构》课程设计报告

fscanf(fpout, \i = Located(G, Fromc); j = Located(G, Toc); fscanf(fpout,

\

%d

%d\

&G->arcs[i][j].distance,

&G->arcs[i][j].cost, &G->arcs[i][j].time);

} else { } }

2．管理员管理

界面首先出现登陆界面，采用加密技术，初始密码为 admin， 菜单项包括 5 个选项： 选项一：增加城市信息；选项 二：增加交通路线信息；选项三：保存新增信息，返回上一级菜单，可返回主界面。

8

}

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);

fpin = fopen(\assert(fpin); fprintf(fpin, \G->l_n = 0; G->c_n = 0; fclose(fpin);

重庆科技学院《数据结构》课程设计报告

图3.3管理员界面 在该界面中调用了三个重要函数，对城市、交通信息进行编辑和保存。 int insertcity(Graph *G)//增加城市 { char name[20]; printf(\输入要增加的城市: \ scanf(\ getchar(); if(G->c_n == 0) { } else {

strcpy(G->clist[0].name, name); G->c_n++; for(int i = 0; i < G->c_n; i++) if(strcmp(G->clist[i].name, name) == 0) 9

重庆科技学院《数据结构》课程设计报告

} return -1; else strcpy(G->clist[G->c_n].name, name); G->c_n++; return 1; } 图3.4增加城市 int insertlu(Graph *G)//增加城市交通信息 { char Fromc[20], Toc[20]; int i, j; int d, c, t; printf(\输入增加路径的出发城市、目的城市、距离(公里)、花费(元)、时间(小时): \\n\ scanf(\ getchar();

10

重庆科技学院《数据结构》课程设计报告

i = Located(G, Fromc); j = Located(G, Toc); if(i == -1 || j == -1) return -1; else { } return 1; } 图3.5增加交通信息

G->arcs[i][j].distance = G->arcs[j][i].distance = d; G->arcs[i][j].cost = G->arcs[j][i].cost = c; G->arcs[i][j].time = G->arcs[j][i].time = t; G->l_n++; void baocun(Graph G)//保存新增信息于文件中 { FILE *fpin; int i,m,k;

11

重庆科技学院《数据结构》课程设计报告

system(\ printf(\目前交通系统中含有%d个城市，%d条旅游路径\\n\\n\\n\G.c_n, G.l_n); printf(\各大城市: \\n\ for(i = 0; i < G.c_n; i++) { } printf(\if((i+1)==0) printf(\printf(\***\\n\\n\ printf(\城市\\t\\t城市\\t\\t距离(公里)\\t花费(元)\\t时间(小时) \\n\ for(i = 0; i < G.c_n; i++) for(k = i + 1; k < G.c_n; k++) if(G.arcs[i][k].distance != zuida) printf(\%d\\t\\t %d\\t\\t%d\\n\G.clist[i].name, G.clist[k].name, G.arcs[i][k].distance, G.arcs[i][k].cost, G.arcs[i][k].time); } 该短代码中主要是读取三个文件，然后分别将信息输出在屏幕上！ 5.在该系统中还有一段代码，是该程序的核心内容，用于返回网络图结构中位置下标；代码如下：

17

system(\重庆科技学院《数据结构》课程设计报告

int Located(Graph *G, char *p)//返回数据位置 { int i; for(i = 0; i < G->c_n; i++) if(strcmp(G->clist[i].name, p) == 0) return i; return -1; }

18

重庆科技学院《数据结构》课程设计报告

4 课程总结与体会 该系统虽然已满足此次任务要求，但是还有许多需要修改增加的地方：

1. 2. 3.

在系统运行时，如无文件就不能运行。可以让系统自行创建文件。 在对城市和交通信息进行编辑时不能对其进行删除和修改 在对信息编辑时可同时进行保存

在这次数据结构课程设计中，自己的 C 语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：

1.必须牢固掌握基础知识。由于 C 语言知识，有所遗忘，且未掌握好这学期所学的《数据结构》这门课，所以在实习开始不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地C语言和数据结构知识有所熟悉。这时才逐渐有了思路。

2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号” 的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十 分严谨的事情，不能有一点的粗心

3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。

总之，在这次实习中，自己的 C 语言以及数据结构知识得到提高，编程能力 也得到了提高。

19

重庆科技学院《数据结构》课程设计报告

5参考文献

【1】严蔚敏，吴伟民，《数据结构（C语言版）》，清华大学出版社，1997.4； 【2】周学毛，《新编C语言程序设计教程》，西安电子科技大学出版社，2005.7； 【3】苏仕华，《数据结构课程设计》，机械工业出版社，2005 【4】滕国文，《数据结构课程设计》，清华大学出版社，2010年

【5】Mark Allen Weiss，《数据结构与算法分析：C语言描述》，机械工业出版社，2004年

20

重庆科技学院《数据结构》课程设计报告

6 致谢

通过此次的课程设计，我不仅学会了很多有关数据结构的算法思路。 此次课程设计要细心指导，以师所授的数据结构知识，还有一些同学和学长的帮助，由于他们的指导与帮助才完成了课程设计。谢谢！

21

本文来源：https://www.bwwdw.com/article/ldsf.html