1、 算法与数据结构算法与数据结构课程设计报告课程设计报告 题目：题目： 公交线路公交线路 完成日期：完成日期：2012 2012 年年 0606 月月 17 日日 一、课程设计目的一、课程设计目的 本课程设计的目标就是要达到理论与实际应用相结合， 提高学生组织数据及编写 大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。 设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模 较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、 牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。 通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选
2、择和 应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序 设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 二、课程设计内容二、课程设计内容 建立某城市（如福州）主要公交线路图 查询站点路线 三、课程设计过程三、课程设计过程 基本要求 输入任意两站点，给出最佳的乘车线路和转车地点。如：该城市共有 n条公交线 路，m个公交站点。其中，公交线路 1 经过编号为 1，2，4，7 的站点，公交线 路 2 经过编号为 3，5，7，8，的站点，则从站点 2 到站点 8 的最佳乘车线路是： 乘坐公交线路 1 从站点 2 到站点 7 再乘坐公交线路 2 到站点 8。
3、测试数据 该城市共有 3 条公交线路，6 个公交站点，其中： 第 1 条公交线路经过站点：1，2 第 2 条公交线路经过站点：2，3，4 第 3 条公交线路经过站点：4，5 用图的最短路径算法实现（转乘次数最少） 2概要设计概要设计 1）为了实现上述程序功能，需要定义图数据类型：）为了实现上述程序功能，需要定义图数据类型： typedef struct / 图的定义 char nameMAX_VERTEX_NUM; int vexsMAX_VERTEX_NUM; int vexnum,arcnum; / 顶点信息 弧的信息 int ln,l,n; /ln 是路线数 ，l 是路线,n 是站点 数
4、,d 是站点,nu 路径数 int vexnoMAX_VERTEX_NUMMAX_VERTEX_NUM; /顶点: 路线，路线中的站 点数 int arclinMAX_VERTEX_NUMMAX_VERTEX_NUM; / 弧: 站点-站点， ，存的是 权值 mgraph; 基本操作基本操作： void create(mgraph int vexsMAX_VERTEX_NUM; int vexnum,arcnum; int ln,l,n; int vexnoMAX_VERTEX_NUMMAX_VERTEX_NUM; int arclinMAX_VERTEX_NUMMAX_VERTEX_NUM;
5、 mgraph; 2) 公交路线建设到查询的基本操作公交路线建设到查询的基本操作 建图： ：建图： ： void create(mgraph printf(“请输入公交站数和路径数：“); scanf(“%d,%d,“, printf(“请输入公交站点和其站名：“); for (d=1;d=g.vexnum;d+) scanf(“%d,%c“, for(i=1;i=g.vexnum;i+) for(j=1;j=g.vexnum;j+) g.arclinij=infi; printf(“请输入可达两站点的编号：n“); for(k=1;k=g.arcnum;k+) scanf(“%d,%d“,
6、g.arclinij=1; g.arclinji=1; printf(“请输入公交路线数：“); scanf(“%d“, for (k=1;k=g.ln;k+) printf(“请输入路线和所含站点数：“); scanf(“%d,%d“, printf(“请输入此路线的所含站点：“); for (e=1;e=g.n;e+) scanf(“%d“, if(jinfi) g.vexnog.lj=g.l; Floyd 算法：求最少换乘路径：算法：求最少换乘路径： void floyd (mgraph g,int v,int w)/floyd 算法算出各点间的最小路径 Int pathMAX_VERTEX_NUMMAX_VERTEX_NUM,aMAX_VERTEX_NUM,bMA
