数据结构与算法课程设计 城市公共交通最短线路

《算法与数据结构》课程设计报告题目：公交线路专业：软件工程班级： 1003学号： 41姓名：简指导教师：魏完成日期：2012 年 06月 17 日一、课程设计目的本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。

设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。

通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

二、课程设计内容建立某城市（如福州）主要公交线路图查询站点路线三、课程设计过程[基本要求]输入任意两站点，给出最佳的乘车线路和转车地点。

如：该城市共有n条公交线路，m个公交站点。

其中，公交线路1经过编号为1，2，4，7的站点，公交线路2经过编号为3，5，7，8，的站点，则从站点2到站点8的最佳乘车线路是：乘坐公交线路1从站点2到站点7再乘坐公交线路2到站点8。

[测试数据]该城市共有3条公交线路，6个公交站点，其中：第1条公交线路经过站点：1，2第2条公交线路经过站点：2，3，4第3条公交线路经过站点：4，5用图的最短路径算法实现（转乘次数最少）2．概要设计1）为了实现上述程序功能，需要定义图数据类型：typedef struct // 图的定义{ char name[MAX_VERTEX_NUM];int vexs[MAX_VERTEX_NUM];int vexnum,arcnum; // 顶点信息弧的信息int ln,l,n; //ln是路线数，l是路线,n是站点数,d是站点,nu路径数int vexno[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //顶点: 路线，路线中的站点数int arclin[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 弧: 站点-站点，，存的是权值} mgraph;基本操作：void create(mgraph &g)输入路线，站点信息，站点间关系操作结果：创建公交线路图，void floyd (mgraph g,int v,int w)计算最少换乘路径。

数据结构课程设计报告题目交通旅游图的最短路径问题学生姓名*****指导教师*****学院******专业班级******完成时间********摘要数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的关系和操作等的学科。

数据结构在计算机科学与技术中是一门综合性的专业基础课，其研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系。

不论是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配问题。

在计算机科学与技术中，数据结构不仅是一般程序性的基础，而且也是其他系统程序和大型程序的重要基础。

在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。

对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。

图中顶点表示站点之间的交通关系。

这个交通系统可以回答旅客提出的各种问题。

比如任意一个站点到其他站点的最短路径，任意两个站点之间的最短路径问题。

本次设计的交通咨询系统主要是运用C语言来完成交通图的存储、图中顶点的最短路径和任意一对顶点间的最短路径问题。

关键字：数据结构课程设计交通咨询系统目录前言 (1)第一章设计要求 (2)1.1设计内容 (2)1.2设计目的 (3)1.3设计分析 (4)第二章系统功能模块的设计 (5)2.1 系统功能分析与设计 (5)2.1.1系统简介 (5)2.1.2 系统流程图 (5)2.2 各功能模块简介 (6)2.2.1结构体的建立 (6)2.2.2 图的建立与初始化 (6)2.2.3 邻接矩阵的输出 (8)2.2.4 显示函数 (8)2.2.5 最短路径算法 (9)2.2.6主函数 (10)第三章实践结果与调试 (12)3.1运行结果 (12)3.1.1主界面 (12)3.1.2查询站点编号模块 (12)3.1.3邻接矩阵查询模块 (12)3.1.4最短路径查询模块 (13)3.2运行调试及发现问题 (15)3.2.1调试过程 (15)3.2.2发现问题 (15)第四章设计总结与心得 (16)附录：程序源代码 (18)前言乘汽车旅行的人总希望找出到目的地的尽可能短的行程。

目录交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。

在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。

这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。

对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。

针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。

并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

三、概要设计可以将该系统大致分为三个部分：① 建立交通网络图的存储结构；② 解决单源最短路径问题；③ 实现两个城市顶点之间的最短路径问题。

四、详细设计建立图的存储结构定义交通图的存储结构。

邻接矩阵是表示图形中顶点之间相邻关系的矩阵。

设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点V的信息）。

i邻接矩阵的存储结构：附录#include<>#include<>#defineMVNum100#defineMaxint32767enumboolean{FALSE,TRUE}; typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum];}MGraph;intD1[MVNum],p1[MVNum];intD[MVNum][MVNum],p[MVNum][MVNum]; voidCreateMGraph(MGraph*G,intn,inte){inti,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint;printf("输入%d条边的及w:\n",e);for(k=1;k<=e;k++){scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf("有向图的存储结构建立完毕！\n"); }voidDijkstra(MGraph*G,intv1,intn){intD2[MVNum],p2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){S[v]=FALSE;D2[v]=G->arcs[v1][v];if(D2[v]<Maxint)p2[v]=v1;elsep2[v]=0;}D2[v1]=0;S[v1]=TRUE;for(i=2;i<n;i++){min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}S[v]=TRUE;for(w=1;w<=n;w++)if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];p2[w]=v;}}printf("路径长度路径\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=p2[i];while(v!=0){printf("<-%d",v);v=p2[v];}printf("\n");}}voidFloyd(MGraph*G,intn){inti,j,k,v,w;for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)p[i][j]=j;elsep[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];p[i][j]=p[i][k];}}}}voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf("输入图中顶点个数和边数n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0){printf("************求城市之间最短路径************\n");printf("=========================================\n");printf("1.求一个城市到所有城市的最短路径\n");printf("2.求任意的两个城市之间的最短路径\n");printf("=========================================\n");printf("请选择:1或2，选择0退出:\n");scanf("%d",&xz);if(xz==2){Floyd(G,n);printf("输入源点（或起点）和终点:v,w:");scanf("%d,%d",&v,&w);k=p[v][w];if(k==0)printf("顶点%d到%d无路径!\n",v,w);else{printf("从顶点%d到%d最短路径路径是:%d",v,w,v);while(k!=w){printf("--%d",k);k=p[k][w];}printf("--%d",w);printf("径路长度:%d\n",D[v][w]);}}elseif(xz==1)printf("求单源路径，输入源点v:");scanf("%d",&v);Dijkstra(G,v,n);}printf("结束求最短路径，再见!\n"); }。

数据结构最短路径课程设计一、课程目标知识目标：1. 理解图的基本概念，掌握图的表示方法及其特性；2. 掌握最短路径的两种经典算法：Dijkstra算法和Floyd算法；3. 能够运用所学算法解决实际生活中的最短路径问题。

技能目标：1. 能够运用数据结构中的图，进行实际问题的建模；2. 能够编写并实现Dijkstra算法和Floyd算法，解决最短路径问题；3. 能够通过分析、比较两种算法，选择合适的算法解决特定问题。

情感态度价值观目标：1. 培养学生面对复杂数据结构问题时，保持积极探究、解决问题的态度；2. 培养学生的团队协作能力，学会在团队中分享、交流、互助；3. 通过解决实际生活中的问题，培养学生将所学知识应用于实践的意识。

课程性质分析：本课程为数据结构中的图部分，以最短路径为具体实例，帮助学生理解图的概念及其在实际中的应用。

学生特点分析：学生已具备一定的编程能力和数据结构基础知识，但对图的相关概念和算法掌握不足，需要通过具体案例和实际操作，提高理解和应用能力。

教学要求：1. 以实际问题引入，激发学生的学习兴趣；2. 采用任务驱动法，引导学生自主探究、实践；3. 结合课堂讲解和实际操作，使学生在实践中掌握知识；4. 注重团队合作，培养学生的沟通与协作能力。

二、教学内容1. 图的基本概念：图的定义、图的表示方法（邻接矩阵、邻接表）、图的遍历（深度优先搜索、广度优先搜索）。

2. 最短路径问题：最短路径的定义、最短路径算法的应用场景。

3. Dijkstra算法：算法原理、算法步骤、实例分析、编程实现。

4. Floyd算法：算法原理、算法步骤、实例分析、编程实现。

5. 算法比较与分析：Dijkstra算法与Floyd算法的优缺点比较、适用场景分析。

6. 实践项目：设计一个实际场景的最短路径问题，要求学生运用所学算法进行解决。

教学内容安排与进度：第一课时：图的基本概念、图的表示方法、图的遍历。

第二课时：最短路径问题、Dijkstra算法原理与实例分析。

问题描述：若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。

试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。

基本要求：（1）从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。

（2）以用户指定的起点和终点，输出从起点到终点的花费。

一、需求分析：1、本程序需要用矩阵来存储图的各种信息。

2、测试数据输入（文件）5－1 10 3 20 －1－1 －1 －1 5 －1－1 2 －1 －1 15－1 －1 －1 －1 11－1 －1 －1 －1 －1（用户）起点 0终点 4输出18实现提示：（1）设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。

（2）此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。

（3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。

因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。

（4）考虑没有路径时的输出。

二、概要设计：抽象数据类型：为实现上述功能需建立一个二维数组和图类。

算法的基本思想：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（>>途中各点之间的距离）。

2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。

如果l1<l2，则用l1的距离替换l2。

重复上述操作n-1（n为结点数）次。

得到的即为第一个结点到其他结点的最短距离。

程序的流程程序由三个模块组成：输入模块：读入图的信息（用矩阵进行存储）。

处理模块：Dijkstra算法。

数据结构课程设计最短路径一、课程目标知识目标：1. 理解图的基本概念，掌握图的表示方法，如图的邻接矩阵和邻接表；2. 掌握最短路径问题的定义，了解其应用场景；3. 学会运用Dijkstra算法和Floyd算法解决最短路径问题；4. 了解最短路径算法的时间复杂度，并能够分析其优缺点。

技能目标：1. 能够运用所学知识，编写程序实现最短路径算法；2. 能够分析实际问题，选择合适的数据结构和算法解决最短路径问题；3. 学会使用调试工具，调试并优化最短路径算法程序。

情感态度价值观目标：1. 培养学生对数据结构课程的兴趣，激发学习热情；2. 培养学生的团队合作精神，学会在团队中分工合作，共同解决问题；3. 培养学生面对问题时的耐心和毅力，勇于克服困难，寻求解决方案；4. 通过解决实际问题，增强学生的应用意识和创新意识。

课程性质：本课程为计算机科学专业选修课程，旨在帮助学生掌握图论中的最短路径问题及其算法实现。

学生特点：学生已经具备一定的编程基础，熟悉C/C++等编程语言，了解基本的数据结构，如数组、链表、栈和队列等。

教学要求：结合学生特点和课程性质，注重理论与实践相结合，通过实例分析、算法实现和调试优化，使学生掌握最短路径问题的解决方法，并培养其分析问题和解决问题的能力。

在教学过程中，关注学生的情感态度价值观的培养，提高学生的综合素质。

二、教学内容1. 图的基本概念：图的定义、图的分类、图的表示方法（邻接矩阵、邻接表）。

2. 最短路径问题：最短路径的定义、应用场景、最短路径算法的分类。

3. Dijkstra算法：算法原理、算法步骤、实例分析、编程实现。

4. Floyd算法：算法原理、算法步骤、实例分析、编程实现。

5. 最短路径算法时间复杂度分析：比较Dijkstra算法和Floyd算法的时间复杂度，分析其适用场景。

6. 实践环节：设计实际案例，让学生动手编写程序实现最短路径算法，并进行调试优化。

7. 算法优化：探讨最短路径算法的优化方法，如优先队列、动态规划等。

内容和要求广东省主要大城市之间的交通图如下所示，每条边上的权值代表从城市A到城市B的路途长度，使用数据结构图的相关理论编程给出广州到各个城市的最短路径，并且输出经过的路径。

进一步了解数据结构中对图的各种操作，以及求最短路径的算法。

解决方案和关键代码解决方案：思路：首先把图用带权邻接矩阵g表示出来（每个城市看做一个顶点，广州是v0），然后用c语言实现书上的迪杰斯特拉算法，求有向网g的v0顶点到其余顶点v 的最短路径保存到D[v]，以及途经的一个最近新的路径保存Path[v]。

最后输出D[v]以及Path[v]。

其中：（v0是广州；v1是佛山；v2是肇庆；v3是珠海；v4是深圳；v5是南宁；v6是香港）关键代码#include <iostream>#pragma warning (disable:4996)using namespace std;//定义我们需要的变量char cityName[7][256];//用于表示城市之间的关系,依次是广州,佛山,肇庆,珠海,深圳,南宁,香港int dis[7][7] = {{ -1, 100, 200, 200, -1, -1, -1 },{ -1, -1, -1, 50, 150, -1, -1 },{ -1, -1, -1, 100, -1, 150, -1 },{ -1, -1, -1, -1, 80, 350, -1 },{ -1, -1, -1, -1, -1, -1, 150 },{ -1, -1, -1, -1, 360, -1, 450 },{ -1, -1, -1, -1, -1, -1, -1 } };int from[7];int disSum[7];int current, current1;int nextNoList[7];int nextNoList1[7];char path[7][256];char temp[256];int main(){//将广州等字符串复制给cityName数组中strcpy(cityName[0], "广州");strcpy(cityName[1], "佛山");strcpy(cityName[2], "肇庆");strcpy(cityName[3], "珠海");strcpy(cityName[4], "深圳");strcpy(cityName[5], "南宁");strcpy(cityName[6], "香港");int i, j;for (i = 0; i < 7; i++){disSum[i] = -1;from[i] = -1;}current = 1;nextNoList[0] = 0;disSum[0] = 0;strcpy(path[0], cityName[0]);//用Dijkstra算法计算图的最短路径while (current){current1 = 0;for (j = 0; j < current; j++){for (i = 1; i < 7; i++){if (dis[nextNoList[j]][i] != -1){if (disSum[i] == -1 || disSum[i] > disSum[nextNoList[j]] +dis[nextNoList[j]][i]){disSum[i] = disSum[nextNoList[j]] +dis[nextNoList[j]][i];nextNoList1[current1++] = i;from[i] = nextNoList[j];strcpy(temp, path[nextNoList[j]]);strcat(temp, " -> ");strcat(temp, cityName[i]);strcpy(path[i], temp);}}}}current = current1;for (j = 0; j < current1; j++){nextNoList[j] = nextNoList1[j];}}//显示各个效果for (i = 1; i < 7; i++){printf("从%s到%s : %d : %s\n", cityName[0], cityName[i], disSum[i], path[i]);}return 0;}数据测试与结果总结：本次主要运用了Dijkstra算法（迪杰斯特拉算法）来求得两个点之间的最短路径，理论是还是很好明白的，但在本次的实验中，最难的就是上机实现这个算法问题。