数据结构课程方案地铁建设问题

个人资料整理仅限学习使用软件学院课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名指导教师2018年 1 月目录1 设计时间12 设计目的13设计任务14 设计内容14.1需求分析14.2总体设计24.3详细设计44.4测试与分析11 4.4.1测试114.4.2分析134.5 附录145 总结与展望20参考文献22成绩评定22操作结果：构造一个无向图G；LocateDistri(Graph g,int u>操作结果：找出目标城市的位置；Min(Graph g,closedge closedge>操作结果：求出点与点之间的最短路径；Prim(G,G.distrinam[1]>操作结果：用普里姆算法找到连接各辖区的最短路；4.2.3主程序的流程主程序的流程如图1所示：图14.2.4各程序模块之间的层次<调用）关系各程序模块之间的层次<调用）关系如图2所示：图24.3详细设计4.3.1预处理#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>#define INFINITY 10000#define M 20typedef struct{ //创建图的结构体char V[M][10]。

//顶点数组，用来存储辖区的值即辖区的名称 int R[M][M]。

//邻接矩阵，邻接矩阵的元素值为辖区之间的距离{int i。

Graph g。

char a[10]。

i=creatgraph(&g>。

if(i>{printf("***********请输入起始地点为：************\n">。

scanf("%s",a>。

MiniSpanTree_PRIM(g,a>。

地铁线路设计规划模型一、摘要二、问题重述某城市中心城区（如图1所示）规划修建地铁，要求从该中心城区任意一点出发，到最近的地铁站的直线距离不超过800米，试通过建立模型解决下列问题：（1）最少要建多少个地铁站？（2）按最少数量的地铁站分布，设计出最佳图1：某城市中心城区的简化图，其中AGCB为梯形，DEFG为矩形，坐标A(0.5, 4.8), B(0, 2), BC=7.5, AG=3.5, DE=2.8, EF=7.3。

图中每单位长度表示实际距离3km。

三、名词和符号说明 四、模型假设 五、问题分析本题中规划的中心城区是一个不规则的图形，所以地铁分布时不能简单的按规律建立。

我们设想的是先建造一种拥有最佳有效面积的地铁站点。

首先，我们利用微分的思想，以地铁站为圆心，800m 为半径画圆再在圆内画内接多边形，希望最后能将两个圆内内接多边形重叠之后重叠的面积尽量少。

之后，我们又从化学原子排列规律中得到了另一种模型，从中我们再比较选出最佳的模型。

之后，我们利用CAD 按比例画出题目的图与地铁站点阵进行比较，为了获取地铁站间的距离，我们用C 语言编了一个程序计算出每个地铁站的距离矩阵，最后再利用Matlab 画出地铁站点图的最小生成树，从中得出最佳路线。

思路一：我们抛开这个城市的图形，以地铁站为圆心，800m 为半径画圆，如图5-1。

图 5-1然后，为了使所有两个地铁站能无缝地接在一起，我们把这个图尽可能多地划分成内接多边形。

如图（b ）~（e ）。

....图 5-2 图5-3 图 5-4 图 5-5这里，我们又出现一个新的问题，要使内接多边形能接在一起，内接多边形的角度必须能整除360，n 边形内角和为(2)180n -⨯，每个内角为(2)180n n -⨯÷。

满足整除360，只有n=3，4，6。

现在，我们先假设R=800圆心Cn=3（图5-3），则每个点有效面积2433r S a =； n=4（图5-4），则这个点有效面积22r S a = ； n=6（图5-5），则这个点有效面积2233r S a =。

数据结构课程设计报告学院：计算机科学与工程专业：计算机科学与技术班级：09级班学号：姓名：指导老师:时间: 2010年12月一、课程设计题目：1、哈夫曼编码的实现2、城市辖区地铁线路设计3、综合排序算法的比较二、小组成员：三、题目要求：1．哈夫曼编码的实现（1）打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一各字符出现的概率。

（2）针对上述统计结果，对各字符实现哈夫曼编码（3）对任意文章，用哈夫曼编码对其进行编码（4）对任意文章，对收到的电文进行解码2．某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线。

（1）从包含各辖区的地图文件中读取辖区的名称和各辖区的直接距离（2）根据上述读入的信息，给出一种铺设地铁线路的解决方案。

使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。

（3）输出应该建设的地铁路线及所需要建设的总里程信息。

3．综合排序算法的比较各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概的执行时间。

试通过随机的数据比较各算法的关键字比较次数和关键字移动的次数。

（1）对以下各种常用的内部排序算法进行比较：直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速排序简单选择排序，堆排序，归并排序，基数排序。

（2）待排序的表长不少于100，要求采用随机数。

（3）至少要用5组不同的输入数据做比较：比较的次数为有关键字参加的比较次数和关键字移动的次数（4）改变数据量的大小，观察统计数据的变化情况。

（5）对试验统计数据进行分析。

对各类排序算法进行综合评价。

四、项目安排：1、小组内分工合作分工：负责哈夫曼编码的实现，负责城市辖区地铁线路设计，负责综合排序算法的比较。

合作：组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并控制进度。

五、完成自己的任务：任务：城市辖区地铁线路设计1.实现方案创建城市辖区图表信息将信息写入文件从文件读取信息最优路径的选择输出最优路径的相关信息在整个编程中，我是通过手动输入的方式把数据写到文件中，而不是直接从文件中读取，这个不是题目要求的，但是我想当拿到数据之后都要对数据进行处理，干脆直接手动输入得出结果。

轨道交通系统的规划与建设方案随着城市化进程的加快，交通拥堵问题日益突出，轨道交通系统作为一种高效、环保的交通方式，受到越来越多城市的青睐。

本文将探讨轨道交通系统的规划与建设方案，以期为城市交通发展提供一些思路和借鉴。

一、轨道交通系统规划的重要性轨道交通系统规划是城市交通规划的重要组成部分，它关系到城市的可持续发展和居民的出行便利性。

首先，轨道交通系统能够大幅减少道路交通压力，改善城市交通拥堵状况。

其次，轨道交通系统具有较高的运力和运营效率，能够满足日益增长的出行需求。

此外，轨道交通系统还能减少汽车尾气排放，改善城市空气质量，实现低碳出行。

因此，科学规划轨道交通系统对城市的可持续发展至关重要。

二、轨道交通系统规划的原则1. 综合考虑城市发展需求和居民出行需求。

轨道交通系统规划应该与城市的总体规划相衔接，充分考虑城市发展的长远需求和居民的出行需求，以满足城市交通的可持续发展。

2. 确定轨道交通线网布局。

轨道交通线网布局应根据城市的地形、人口分布、交通流量等因素进行科学规划，确保线路覆盖面广，能够满足不同区域的出行需求，并与其他交通方式有机衔接。

3. 优化站点设置和换乘设计。

站点设置应根据人口密度、交通流量等因素进行科学布局，以方便居民出行和换乘。

同时，换乘设计应考虑到不同线路之间的换乘距离和时间，尽量减少换乘的不便。

4. 考虑轨道交通系统的可持续发展。

轨道交通系统规划应充分考虑环保因素，采用节能、低碳的技术和设备，减少能源消耗和环境污染，实现可持续发展。

三、轨道交通系统建设的步骤1. 前期调研和规划。

在轨道交通系统建设之前，需要进行前期调研和规划工作。

包括城市交通现状调研、人口分布和出行需求分析、线网布局和站点设置规划等。

2. 技术选型和设计。

根据城市的实际情况和需求，选择适合的轨道交通技术和设备，并进行线路设计、车站设计、信号系统设计等。

3. 建设和施工。

根据设计方案，进行轨道交通线路、车站和设备的建设和施工工作。

计算机科学与技术学院课程设计成绩单课程名称：数据结构指导教师：赵红武姓名谈腾性别男学号201113237022 班级计0904班综合成绩成绩等级程序运行情况（占总成绩20%）□能正确运行□基本能正确运行□能运行但结果不完善（20分）（15分）（10分）程序功能的完善程度（占总成绩10%）□完善□基本完善□不完善（10分）（8分）（5分）程序结构的合理性（占总成绩10%）□合理□基本合理□不太合理（10分）（8分）（5分）对问题的答辩情况（占总成绩40%）□概念正确有创新□能正确回答所有问题□基本能正确回答（40分）（35分）（30分）□部分问题回答概念不清晰（20分）学生的工作态度与独立工作能力（占总成绩10%）□工作态度认真能独立完成任务□工作态度认真但独立性较差（10分）（8分）□工作态度基本认真但缺乏独立性（5分）设计报告的规范性（占总成绩10%）□符合规范□基本符合规范□规范性较差（10分）（8分）（5分）优秀：90分~100分良好：80分~89分中等：70~79分及格：60~69分不及格0分~59分武汉科技大学计算机科学与技术学院制表计算机科学与技术学院课程设计报告课程名称：数据结构专业：计算机科学与技术班级：计0904班学号：201113237022 姓名：谈腾指导老师：赵红武实验一：火车票务系统的设计与实现一、需求分析火车票务管理系统具有以下需求：（1）列车信息录入：输入列车基本信息。

（2）列车信息删除：删除车次信息。

(列车线路停运)（3）列车信息修改：删除车次信息。

（列车时间、票价等信息有变动）（4）列车信息输出：根据格式对齐输出列车信息。

（5）列车信息查询：可根据车次号、始发站、终点站查询满足条件的列车信息。

（6）列车信息排序：可根据票价对列车信息进行排序并输出。

二、设计分析火车票务系统根据需求分为界面和6个模块，分别为火车票信息显示模块、输入模块、修改模块、删除模块、查询模块、排序模块。

c语言课程设计地铁一、教学目标本节课的教学目标是让学生掌握C语言的基本语法和编程技巧，通过编写程序模拟地铁运行系统，培养学生的逻辑思维能力和实际问题解决能力。

具体分为以下三个部分：1.知识目标：使学生了解C语言的基本数据类型、运算符、控制结构等语法知识，理解函数的定义和调用方法。

2.技能目标：培养学生具备运用C语言编写程序的能力，能够独立完成简单的程序设计任务。

3.情感态度价值观目标：激发学生对计算机科学的兴趣，培养他们勇于探索、创新的精神，提高学生团队协作和沟通的能力。

二、教学内容本节课的教学内容主要包括以下几个部分：1.C语言基本语法：数据类型、变量、运算符、控制结构等。

2.函数的定义和调用：函数的声明、定义、参数传递、返回值等。

3.地铁运行系统模拟：编写程序模拟地铁的运行，包括站点、列车、乘客等。

4.程序调试与优化：学会使用调试工具，分析程序运行过程中的问题，优化程序性能。

三、教学方法为了提高教学效果，本节课将采用以下几种教学方法：1.讲授法：讲解C语言的基本语法和编程技巧，让学生掌握必要的理论知识。

2.案例分析法：分析实际案例，让学生了解地铁运行系统的原理，引导学生运用所学知识解决实际问题。

3.实验法：让学生动手编写程序，模拟地铁运行，培养学生的实际操作能力和问题解决能力。

4.讨论法：学生进行小组讨论，分享学习心得和编程经验，提高学生的沟通能力和团队协作精神。

四、教学资源为了支持本节课的教学内容和教学方法，我们将准备以下教学资源：1.教材：《C程序设计语言》或《C语言入门教程》等。

2.参考书：《C语言编程实践》、《C语言深度探索》等。

3.多媒体资料：教学PPT、视频教程、在线编程练习平台等。

4.实验设备：计算机、编程软件（如Code::Blocks、Visual Studio等）、网络等。

通过以上教学资源，为学生提供丰富的学习渠道和实践机会，帮助他们更好地掌握C语言编程技能。

五、教学评估本节课的教学评估将采用多元化的评价方式，全面、客观地评价学生的学习成果。

轨道交通系统的规划与建设方案随着城市化进程的加快和人口的不断增长，交通问题已经成为城市发展中的一大瓶颈。

为了解决交通拥堵和环境污染等问题，越来越多的城市开始着手规划和建设轨道交通系统。

本文将探讨轨道交通系统的规划与建设方案，以期为城市发展提供可行的解决方案。

一、城市交通需求的分析在制定轨道交通系统规划和建设方案之前，首先需要对城市交通需求进行全面的分析。

这包括人口分布、交通流量、交通状况等方面的数据收集和分析。

通过对城市交通需求的深入了解，可以为轨道交通系统的规划和建设提供科学依据。

二、轨道交通系统的类型选择在制定规划和建设方案时，需要根据城市特点和需求选择合适的轨道交通系统类型。

常见的轨道交通系统包括地铁、轻轨、有轨电车等。

地铁适用于大城市的快速交通需求，轻轨适用于中小城市的城市交通需求，有轨电车则适用于城市内的短距离交通需求。

根据城市的实际情况，选择合适的轨道交通系统类型可以最大程度地满足城市的交通需求。

三、轨道交通线路的规划轨道交通系统的规划离不开线路的规划。

线路规划是轨道交通系统建设的核心环节，它直接关系到轨道交通系统的运营效果和覆盖范围。

在进行线路规划时，需要考虑城市的主要交通枢纽、人口密集区、商业中心等因素，以确保线路的合理性和便捷性。

此外，还应考虑到环境保护和文化遗产等因素，避免对城市的自然环境和历史建筑造成破坏。

四、轨道交通站点的布局轨道交通系统的站点布局直接关系到乘客的出行便利性。

在进行站点布局时，需要考虑到人口分布、交通流量、交通换乘等因素。

合理的站点布局可以最大程度地减少乘客的换乘时间和出行距离，提高轨道交通系统的运行效率。

五、轨道交通系统的建设与运营在制定轨道交通系统的规划和建设方案时，还需要考虑到建设和运营的问题。

建设轨道交通系统需要投入大量的资金和人力，因此需要制定合理的投资计划和建设进度。

同时，还需要考虑到轨道交通系统的运营管理和维护问题，确保轨道交通系统的安全和可靠性。

##大学数据结构课程设计报告题目：全国铁路运输网最佳经由问题院(系): 计算机工程学院学生姓名:班级：学号:起迄日期: 2011/6/20至2011/7/01指导教师:2010—2011年度第 2 学期一、需求分析1.问题描述：这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。

该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。

铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。

铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。

火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。

2.基本功能（1）查询某站所属的铁路线（2）要求具备新增铁路线的管理功能（3）要求具备新增车站的管理功能（4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。

并且要求能够显示出该最短路径的各个火车站的经由顺序3.输入输出初始数据是从views.txt、lines.txt、ways.txt三个文件中读入，在读入数据后，用户可以根据选项选择相应的功能，不同的功能有不同的数据输入/输出，比如：查询的功能是要求输入要查询的站的名称，然后输出是该站的相关信息；查询最短路径的功能则是输入起点站、终点站的名称，，输出则是该的路线距离和经由站等二、概要设计1.设计思路：核心问题:求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）:带权有向图 (权值计算: 距离*频度)2.数据结构设计：存储结构:本程序采用的是文件进行数据的存储，所以才用的是顺序存储结构，如要添加数据，直接在文件里面进行操作就行。

如下为抽象数据类型定义的模板及抽象数据类型线性表的定义如下：ADT List{数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,3,……，n}基本操作：void readviews()初始条件：views.txt已经存在。

城市轨道交通运营管理信息系统规划与建设方案一、引言随着城市化进程的推进，城市轨道交通系统的规模不断扩大，对运营管理信息系统的需求也越来越迫切。

为了提高城市轨道交通的运营效率和服务质量，本文将就城市轨道交通运营管理信息系统的规划与建设方案进行探讨。

二、系统规划城市轨道交通运营管理信息系统规划的目标是建立一个高效、智能化的管理平台，实现对轨道交通系统各个环节的全面监控和协调管理。

系统规划包括以下几个方面的内容：1. 系统需求分析在规划阶段，需要对城市轨道交通运营管理的需求进行充分的调研和分析，包括安全管理、运维管理、客流管理等各个方面的需求。

2. 功能模块划分根据系统需求的分析结果，将运营管理信息系统划分为不同的功能模块，包括车辆调度管理、乘客服务管理、安全监控管理等，以满足不同管理需求。

3. 数据流程设计对整个运营管理信息系统的数据流进行设计，确保数据的准确性和及时性。

包括数据采集、处理和传输等环节，保证信息的流畅和安全。

三、系统建设城市轨道交通运营管理信息系统的建设需要综合运用先进的信息技术手段，并结合实际运营管理需求，确保系统能够稳定、高效地运行。

1. 技术选型根据系统功能需求和实际情况，选择合适的技术方案和设备，包括硬件设备、网络设施和软件系统等。

确保系统的稳定性和可靠性。

2. 系统架构设计根据功能模块的划分和数据流程设计，设计系统的整体架构，包括前端界面、后台数据库和服务器等。

保证系统的可扩展性和性能优化。

3. 系统实施与测试在系统建设过程中，需要进行系统实施和测试，确保系统能够满足运营管理的需求。

包括数据迁移、接口联调和功能测试等环节。

四、系统应用与推广城市轨道交通运营管理信息系统的应用与推广是建设过程的重要环节，需要充分发挥系统的作用，提高城市轨道交通的管理水平和服务质量。

1. 系统培训与推广在系统建设完成后，组织相关人员进行系统培训，确保其能够熟练操作和运用系统。

同时，进行系统的推广和宣传，提高系统的使用率。

乘车数据结构课程设计一、课程目标知识目标：1. 理解并掌握乘车数据结构的基本概念，如队列、栈等；2. 学会使用乘车数据结构解决实际问题，如公交车的上下车问题；3. 了解乘车数据结构在实际应用中的优缺点及适用场景。

技能目标：1. 能够运用所学知识，设计并实现简单的乘车数据结构模型；2. 培养学生的逻辑思维能力和问题分析能力，使其具备解决实际问题的编程技能；3. 提高学生的团队协作能力，通过小组讨论和分享，共同优化乘车数据结构的设计。

情感态度价值观目标：1. 激发学生对计算机科学和数据结构的兴趣，培养其探索精神和求知欲；2. 培养学生严谨、踏实的学术态度，使其认识到数据结构在解决问题中的重要性；3. 引导学生关注乘车数据结构在生活中的应用，提高其对社会问题的关注度和责任感。

课程性质：本课程为计算机科学领域的一门专业基础课程，旨在让学生掌握乘车数据结构的基本知识，培养其编程能力和问题解决能力。

学生特点：学生为高中一年级学生，具备一定的计算机基础和编程能力，对数据结构有一定了解，但缺乏实际应用经验。

教学要求：结合学生特点，注重理论与实践相结合，强调在实际问题中发现、分析并解决问题。

通过小组讨论、案例分析和编程实践，提高学生的综合能力。

在教学过程中，关注学生的个体差异，因材施教，确保每位学生都能达到课程目标。

二、教学内容1. 队列的基本概念与应用- 队列的定义及特点- 队列的常见操作：入队、出队、查看队首元素- 乘车数据结构中队列的应用案例：公交车上下车问题2. 栈的基本概念与应用- 栈的定义及特点- 栈的常见操作：压栈、出栈、查看栈顶元素- 乘车数据结构中栈的应用案例：地铁站台的进出站问题3. 优先队列与循环队列- 优先队列的定义及实现方法- 循环队列的概念及优势- 优先队列和循环队列在实际乘车数据结构中的应用4. 乘车数据结构在实际问题中的应用与优化- 分析实际乘车场景，提出数据结构解决方案- 针对不同场景，选择合适的乘车数据结构- 优化乘车数据结构，提高系统运行效率5. 教学案例与实践- 设计具有实际意义的编程案例，引导学生运用所学知识解决问题- 组织小组讨论，分享编程经验和心得- 针对不同学生的特点，提供难易适度的实践任务，巩固所学知识教学内容依据教材章节安排，结合课程目标，注重理论与实践相结合。

地铁建设课程设计一、教学目标本课程旨在让学生了解地铁建设的基本概念、流程和技术要点，掌握地铁建设对社会经济和城市发展的影响，培养学生的实际问题分析和解决能力。

1.了解地铁的基本概念、类型和特点；2.掌握地铁建设的的主要流程和技术要点；3.了解地铁建设对社会经济和城市发展的影响。

4.能够运用所学知识分析和解决地铁建设相关问题；5.能够进行小组合作，进行项目式学习。

情感态度价值观目标：1.培养学生的创新意识，提高学生对科技改变生活的认识；2.培养学生热爱城市、关注城市发展的情感。

二、教学内容教学内容以《地铁建设技术与实践》教材为主，结合当地地铁建设实际情况进行调整。

1.地铁的基本概念、类型和特点；2.地铁建设的的主要流程和技术要点；3.地铁建设对社会经济和城市发展的影响；4.当地地铁建设的案例分析。

三、教学方法结合学生的认知特点和课程内容，采用讲授法、案例分析法、小组讨论法等多种教学方法。

1.讲授法：用于讲解地铁建设的基本概念、流程和技术要点；2.案例分析法：通过分析当地地铁建设案例，使学生更好地理解地铁建设对社会经济和城市发展的影响；3.小组讨论法：引导学生进行小组合作，共同探讨地铁建设相关问题，提高学生的实际问题解决能力。

四、教学资源1.教材：《地铁建设技术与实践》；2.参考书：相关城市地铁建设资料、论文；3.多媒体资料：地铁建设相关的视频、图片等；4.实验设备：地铁建设模拟沙盘、模型等。

教学资源的选择和准备应充分支持教学内容和教学方法的实施，丰富学生的学习体验。

五、教学评估为了全面、客观地评估学生的学习成果，本课程采用多元化评估方式，包括平时表现、作业、考试等。

1.平时表现：评估学生在课堂上的参与程度、提问回答等情况，以了解学生的学习状态；2.作业：布置相关地铁建设的案例分析、研究报告等，评估学生的理解和应用能力；3.考试：设置期中、期末考试，以检测学生对课程知识的掌握程度。

教学评估将严格按照评分标准进行，确保评估的客观性和公正性。

数据结构交通系统实验报告
本次实验是关于数据结构在交通系统中的应用，主要分为两部分，分别是地铁路线查
询和交通路网规划。

地铁路线查询
地铁路线查询是一种常见的需求，我们希望可以查询两个地铁站之间的最短路线。

在
本实验中，我们使用了 Dijkstra 算法来实现该功能。

该算法的时间复杂度为 O(n^2)，
其中 n 表示节点数目。

因此，当节点数过多时，该算法的效率会比较低。

在实际应用中，为了提高效率，可以采用其他的算法，如 A* 算法等。

交通路网规划
交通路网规划是指在一个城市中，规划一条新的路线，使得所有城市之间的距离最小。

在本实验中，我们使用了 Kruskal 算法来实现该功能。

Kruskal 算法的时间复杂度为
O(mlogn)，其中 n 表示节点数目，m 表示边数目。

该算法的优点是可以找到一条跨度最
小的连通图，且不需要事先知道联通情况，可以适用于不同的图形。

在实际应用中，可以
针对不同的问题，采用不同的算法来解决。

总结
本次实验基于数据结构的思想，实现了地铁路线查询和交通路网规划。

数据结构中的Dijkstra 算法和 Kruskal 算法都具有一定的时间复杂度优势，可以实现在可接受的时间
内完成任务。

在实际应用中，我们需要根据问题的特点选择合适的算法，并进行优化，以
提高效率。

数据结构课程设计_地铁建设问题地铁建设问题是一个涉及到城市交通规划和基础设施建设的重要议题。

在数据结构课程设计中，我们将探讨如何利用合适的数据结构和算法来解决地铁建设问题。

一、问题描述在城市规划中，地铁系统的建设是一个复杂而关键的任务。

我们需要设计一个程序，能够根据给定的城市地图和站点信息，实现以下功能：1. 添加地铁路线：能够添加新的地铁路线，并指定每一个站点的名称和位置。

2. 添加地铁站点：能够在已有的地铁路线上添加新的站点，并指定站点的名称和位置。

3. 查询地铁路线：能够根据路线名称查询该路线的所有站点信息。

4. 查询地铁站点：能够根据站点名称查询该站点所属的所有路线信息。

5. 查询两个站点之间的最短路径：能够根据给定的起点和终点站点，计算出两个站点之间的最短路径，并输出经过的所有站点。

二、数据结构设计为了实现上述功能，我们可以使用以下数据结构：1. 图(Graph)：用于表示整个地铁网络，每一个站点作为图的一个节点，站点之间的连接关系作为图的边。

2. 邻接表(Adjacency List)：用于表示每一个站点的邻接站点，方便查询某个站点的相邻站点。

3. 最短路径算法(Dijkstra算法)：用于计算两个站点之间的最短路径。

三、算法设计1. 添加地铁路线：根据输入的路线名称和站点信息，将新的路线添加到地铁网络中。

2. 添加地铁站点：根据输入的站点名称和位置，将新的站点添加到指定的地铁路线中，并更新相邻站点的连接关系。

3. 查询地铁路线：根据输入的路线名称，遍历地铁网络，找到该路线的所有站点信息，并输出。

4. 查询地铁站点：根据输入的站点名称，遍历地铁网络，找到该站点所属的所有路线信息，并输出。

5. 查询两个站点之间的最短路径：根据输入的起点和终点站点，利用Dijkstra 算法计算最短路径，并输出经过的所有站点。

四、实现步骤1. 定义图(Graph)数据结构，包括节点和边的定义，以及相关的操作方法。

软件学院
课程设计报告书
课程名称数据结构
设计题目地铁建设问题
专业班级
学号
姓名
指导教师
2014 年1月17日
目录
1 设计时间1
2 设计目的1
3设计任务1
4 设计容1
4.1总体设计1
4.2需求分析2
4.3详细设计3
4.4测试与分析5
4.4.1测试5
4.4.2分析6
4.5 附录7
5 总结与展望13
参考文献14
成绩评定15
图4-1算法图
4.2需求分析
（1）本程序设计计算城市各辖区间修建地铁的最短路程。

（2）运行时，输入辖区的名称，各辖区之间用空格键隔开，以#输入结束。

（3）输入各辖区间距离时，先输入两辖区名称，再输入距离。

图4-1正确测试结果
图4-2错误测试结果
4.4.2分析
调试时，在输入数据时，再输完数据后要再次按下空格键，再输入结束符号才会结束本次输入进入下一个输入。

且不能输入与本次输入无关的数据或者超出本次输入限制的数据，否则显示错误，将重新输入。

数据结构实验报告（二）学院自动化学院学号********姓名徐璐峰日期2017-12-18实验目的1)熟练掌握图的存储方式；2)了解图的特性，学习在实际问题背景下灵活运用图；3)掌握图的两种最短路径算法。

实验内容为简化问题，假设南京现有三条地铁线：1号线、2号线和3号线，线路都是双向的。

3条地铁线的站点名分别如下，地铁线交叉的换乘点用T1、T2等表示。

请根据3条地铁线的站点和换乘点构造图。

编写程序，任意输入两个站名名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。

地铁1号线（直线）经过车站：A1 A2 A3 T1 A4 A5 A6 A7 A8 T2 A9 A10 A11 A12 T3 A13 A14 A15 T4 A16地铁2号线（直线）经过车站：B1 T5 B2 B3 B4 B5 T2 B6 B7 B8 B9 B10 B11 T3 B12 B13 T6 B14 B15地铁3号线（环线）经过车站：C1 C2 C3 C4 C5 T1 C6 C7 C8 C9 C10 T5 C11 C12 C13 T6 C14 C15 T4 C16 C17 C18实验要求1)用户从键盘输入两个不同的站名，程序输出最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）；2)分别基于迪杰斯特拉算法和弗洛里德算法实现上述地铁换乘问题；3)程序功能模块的划分要适当，多使用流程图来描述算法结构。

1需求分析1）输入的形式和输入值的范围。

输入的形式需要是地铁站的名称，如“A1”、“B7”、“C14”。

所输入的的站点名不能是所要求的站点名之外的名称。

2）输出的形式。

所输出的是基于弗洛里德算法与迪杰斯特拉算法进行的最短路径长度求解的结果，以及最短路径的车站路径编号，并在输入错误的时候允许重复输入。

3）程序所能达到的功能。

用户输入车站起点与车站终点之后，通过迪杰斯特拉算法与弗洛伊德算法，输出从起点到终点的最短路径长度，以及最短路径所经过的车站编号。

数据结构与算法课程设计一、问题描述及设计目的城市公共交通最短线路，利用邻接矩阵来构建交通节点，邻接矩阵的行列编号即为交通中的节点，有行列决定的数据即为权值基本的输入信息和条件：1.输入总的节点个数，即为交通中的站点数目本程序中，站点的数目最大值为100。

2. 输入存在的通路，即为弧两个站点之间是联通的弧的数目是有限制的，数目小于站点数目[n*(n-1)]/23. 输入存在通路的两点，即为两站点站点编号要小于站点总数目二、应具备的功能1. 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。

2. 确定终点的最短路径问题，与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。

在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

3. 确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。

三、设计思想、主要算法的实现、基本操作、子程序调用关系1．Dijkstra算法的基本思想按路径长度递增顺序求最短路径算法。

2．Dijkstra 算法的基本步骤设V0是起始源点，S是已求得最短路径的终点集合。

V-S = 未确定最短路径的顶点的集合，初始时 S={V0}，长度最短的路径是边数为1且权值最小的路径。

下一条长度最短的路径：① V i V - S ，先求出V0到V i中间只经 S 中顶点的最短路径；②上述路径中长度最小者即为下一条长度最短的路径；②将所求最短路径的终点加入S 中；重复直到求出所有终点的最短路径。

3．存储结构设计本系统采用图结构类型（mgraph）存储抽象交通图的信息。

其中：各站点间的邻接关系用图的邻接矩阵类型存储；图的顶点个数及边的个数由分量n、e表示，它们是整型数据。

数据结构如下：typedef struct{ int no; //顶点编号InfoType info; //顶点其他信息，这里用于存放边的权值} VertexType; //顶点类型typedef struct //图的定义{ int edges[MAXV][MAXV]; //邻接矩阵int n,e; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息} MGraph; //图的邻接矩阵类型查询站点间的最短路程距离和路径该功能是查询站点的最短路径，包括距离和线路，有Floyd( )函数实现。