西安交通大学数据结构

西安交通大学数据结构（共6篇）

篇1：西安交通大学数据结构

广东海洋大学

2013 ——

2014 学年第 1 学期

《数据结构与算法》课程试题

一、选择题（6小题，每题3分）

1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（A)存储方法最节省时间 A 顺序表

B单链表

C 双链表

D单循环链表 2.一个栈的入栈序列是1,2,3,4,5，则不可能的出栈序列是(C)A 5,4,3,2,1

B 4,5,3,2,1

C 4,3,5,1,2

D 1,2,3,4,5 3.深度为k的完全二叉树至多有（C）个结点 A 2k2

1B 2k1

C

D 2k11

k4.G是一个非连通无向图，共28条边，则该图至少有（D）个顶点2A 6

B 7

C 8

D 9

1

5.在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（C）型调整以使其平衡 A LL

B LR

C RL

D RR 6.下述排序方法中，时间性能和待排序记录的初始状态无关的是（C）A 插入排序和快速排序

B 归并排序和快速排序 C 选择排序和归并排序

D 插入排序和归并排序

二、填空题

1.数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素位置，计算队列中元素个数的公式为______（rear-front+n）%n______________。

2.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有__12_________个叶子结点。

3.已知无向图的顶点数为n，边数为e，其邻接表表示的空间复杂度为____________O(n+e)____。4.假定一个数列{25,43,62,31,48,56}，采用散列函数为H(k)=k mod 7，则元素48的同义词是____62_______。5.利用简单选择排序对n个记录进行排序，最坏情况下，记录交换次数为_____n-1_______。

三、（15分）已知一棵二叉树的中序遍历序列为DBKEHJAFCIG，后序遍历序列为DKJHEBFIGCA，试画出该二叉树并给出其前序遍历序列

四、（15分）设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，它们在电文中出现的频度分别为{0.02,0.30,0.08,0.14,0.17,0.11,0.12, 0.06}，回答下面问题：（1）为这八个字符设计哈夫曼编码（2）对这八个字符进行等长编码需要几位二进制数，哈夫曼编码比等长编码电文总长压缩多少？

五、（20分）已知一个长度为11的线性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，试回答下面问题（1）将线性表元素依次插入一个空的平衡二叉树，画出所得平衡二叉树，如果假设每个元素查找概率相同，则平均查找长度为多少？

（2）如果对线性表元素排序后进行折半查找，画出折半查找判定树，假设每个元素查找概率相同，计算平均查找长度。

六、（12分）已知数据序列为（11,4,8,19,6,31,23），写出快速排序及堆排序每一趟的结果 解：

七、（11分）设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。

篇2：西安交通大学数据结构

学院（盖章）： 计算机与软件学院 专业： 模式识别与智能系统 考试科目：数据结构

一、考试基本要求

本考试大纲适用于报考深圳大学模式识别与智能系统专业的硕士研究生入学考试。《数据结构》是为招收模式识别与智能系统专业硕士生而设置的具有选拔功能的水平考试。它的主要目的是测试考生对数据结构各项内容的掌握程度。要求考生熟悉计算机处理数据的基本方法，掌握计算机加工的数据结构的特性，熟悉为实际应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并掌握算法的时间分析和空间分析技术。要求考生能够编写符合软件工程规范、结构清楚、正确易读的算法（程序）。

二、考试内容和考试要求

1、基本概念

逻辑结构、存储结构、算法及三者之间的关系

算法的特征及设计目标

了解算法时间、空间需求的大O表示法

2、向量、链表、栈、队

向量（顺序表）、链表（静态链表、单链表、双向链表、循环链表）及相关算法 栈、队，了解其应用，理解递归

串及C语言中串的表示

串的模式匹配算法

了解多维数组的行优先和列优先的顺序存储

了解特殊矩阵（如上、下三角矩阵）的一维数组存储

3、树和二叉树

树（森林）、二叉树及其性质；两者的对应关系

二叉树的llink-rlink和完全二叉树的顺序存储法

二叉树遍历

赫夫曼（Huffman）树的构造及应用

4、图

图（网）的概念及其邻接矩阵和邻接表存储法

图的遍历、最小生成树、最短路径、拓扑排序、关键路径等算法

5、查找

顺序查找、二分查找

二叉排序树、平衡二叉排序树及插入、删除时的平衡方法

B-树、B+树

哈希（Hash）表

了解查找成功及失败的平均查找长度

6、内部排序

排序的概念及相关术语

“希尔”、“快速”、“堆”、“归并”、“基数”等排序算法

了解上述排序算法的时间复杂度、空间复杂度、稳定性

了解上述部分排序算法的适用场合三、考试基本题型

主要题型可能有：判断题、选择题、填空题、应用题、算法设计题等。试卷满分为150分。

篇3：西安交通大学数据结构

1 大数据的现状

据权威数据显示, 大数据应用在我国还处在起步阶段。但在未来三年, 通信、金融领域将在大数据市场突破100亿元。市场规模在2012年有望达到4.7亿元, 到2013年增至11.2亿元, 增长率高达138%, 2014年, 保持了与2013年基本持平的增速, 增长率为114.38%, 市场规模达到24.1亿元, 未来三年内有望突破150亿元, 2016年有望达到180亿规模。自从2014年以来, 各界对大数据的诞生都备加关注, 已渗透到各个领域:交通行业、医疗行业、生物技术、零售行业、电商、农牧业、个人位置服务等行业, 由此也正在不断涌现大数据的新产品、新技术、新服务。

大数据行业“十三五”规划主要目标:在2020年, 将大数据打造成为国民经济新兴支柱产业并在社会各领域广泛应用, 推动我国大数据产业稳步快速发展, 基本健全大数据产业体系, 推动制定一批相关大数据的国标、行标和地方标准, 引进具备大数据条件的企业, 建设大数据产业孵化基地, 提高全国信息化总体水平, 以跻身世界先进水平。

2 大数据的概述

2.1 大数据定义

大数据即巨量数据集合, 目前还没有一个统一的定义。大数据的概念最早是由全球著名的管理咨询公司麦肯锡提出, 2011年Mckinsey发布研究称, 大数据通常是指信息爆炸时代产生的海量数据, 在各个行业和业务领域, 数据已经渗透到行业中并逐渐成为重要的要素, 人们能够从海量数据中挖掘出有用的数据并加以应用。对大数据定义的另一说法是利用常用软件工具捕获、管理和处理数据所耗时间超过可容忍时间的数据集。

随着信息时代的高速发展, 大数据已经成为社会生产力发展的又一推动力。大数据被称为是继云计算、物联网之后信息时代的又一大颠覆性的技术革命。大数据的数据量巨大, 一般10TB规模左右, 但在实际应用中, 多个数据集放在一起, 已经形成了PB级的数据量, 甚至EB、ZB、TB的数据量。

2.2 大数据的特点

2.2.1 数据量巨大

数据量级别从TB级别跃升到PB级别。随着可穿戴设备、物联网和云计算、云存储等技术的发展, 用户的每一个动作都可以被记录, 由此每天产生大量的数据信息。据有关人士估算:1986~2007年, 全球数据的存储能力每年提高23%, 双向通信能力每年提高28%, 通用计算能力每年提高58%;2007年, 人类大约存储了超过300EB的数据;到2013年, 世界上存储的数据能达到约1.2ZB。

2.2.2 数据类型多样化

即数据类型繁多, 产生了海量的新数据集, 新数据集可以是关系数据库和数据仓库数据这样的结构化数据到半结构化数据和无结构数据, 从静态的数据库到动态的数据流, 从简单的数据对象到时间数据、生物序列数据、传感器数据、空间数据、超文本数据、多媒体数据、软件程序代码、Web数据和社会网络数据[1]。各种数据集不仅产生于组织内部运作的各个环节, 也来自于组织外部。

2.2.3 数据的时效性高

所谓的数据时效性高指以实时数据处理、实时结果导向为特征的解决方案, 数据的传输速度、响应、反应的速度不断加快。数据时效性为了去伪存真, 采用非结构化数据剔除数据中无用的信息, 而当前未有真正的解决方法, 只能是人工承担其中的智能部分。有些专员负责数据分析问题并提出分析后的解决方案。

2.2.4 数据真实性低

即数据的质量。数据的高质量是大数据时代重要的关注点。但在生活中, “脏数据”无处不在, 例如, 一些低劣的伪冒产品被推上市场, 由于营销手段的成功, 加之其他因素的影响导致评分很高。但是这并不是真实的数据, 如果对数据不加分析和鉴别而直接使用, 即使计算的结果精度高, 结果都是无意义的, 因为数据本身就存在问题出现。

2.2.5 价值密度低

指随着物联网的广泛应用, 信息巨大, 信息感知存在于客观事物中, 有很多不相关的信息。由于数据采集的不及时, 数据样本不全面, 数据可能不连续等等, 数据可能会失真, 但当数据量达到一定规模, 可以通过更多的数据达到更真实全面的反馈。

2.3 大数据的应用

2.3.1 医疗大数据

利用大数据平台收集患者原先就医的病例和治疗方案, 根据患者的体征, 建立疾病数据库并对患者的病例分类数据库。一旦患者在哪个医院就医, 凭着医保卡或就诊卡, 医生就可以从疾病数据库中参考病人的疾病特征、所做的检查报告结果快速帮助患者确诊。同时拥有的数据也有利于医药行业开发出更符合治疗疾病的医疗器械和药物的研发。

2.3.2 传统农牧业大数据

因为传统农牧业主要依赖于天气、土壤、空气质量等客观因素, 因此利用大数据可以收集客观因素的数据以及作物成熟度, 甚至是设备和劳动力的成本及可用性方面的实时数据, 能够帮助农民选择正确的播种时间、施肥和收割作物的决策。当农民遇到技术市场问题可以请教专业人员, 专业人员根据实时数据做出科学的指导, 制定合理的优化决策, 降低农民的损失成本, 提高产品的产量, 从而为转向规模化经营打下良好基础。

2.3.3 舆情大数据

利用大数据技术收集民众诉求的数据, 降低社会群体事件, 有利管理犯罪行为。通过大数据收集在微博发布的寻找走失的亲人或提供可能被拐卖人口的信息, 来帮助别人。

3 智能交通的需求

随着城市一体化的快速发展, 新时代农民工涌入大城市, 促使城市人口的增大不断给城市交通带来问题。究其原因主要有:一是机动车的迅猛发展导致城市主次干道的流量趋于饱和, 大量机动车的通行和停放占据主干道路。二是城市交通的道路基础设施供给不平衡导致路网承担能力差。三是停车泊位数量不足导致机动车使用者不得不过多依赖道路停车。四是公共设施的公交车分担率不高导致交通运输效率降低。五是城市的土地开发利用与道路交通发展不均衡。六是行人和机动车主素质不文明导致道路通行效率降低。为此, 智能交通的出现是改善当前城市交通的必要需求, 能够在一定程度上有效的解决城市交通问题。

大数据是如何在智能交通的应用呢?可以从两个方面说明:一是对交通运行数据的收集。由于每天道路的通行机动车较多, 能够产生较大的数据, 数据的采集并发数高, 利用大数据使机动车主更好的了解公路上的通行密度, 有效合理对道路进行规划, 可规定个别道路为单行线。其二是可以利用大数据来实现主干道根据道路的运行状况即时调度信号灯, 提高已有线路运行能力, 可以保障交通参与者的生命和提高有关部门的工作效率, 降低成本。对于机动车主可以根据大数据随时的了解当前的交通状况和停车位数量。如果交通拥堵, 车主则可选择另一路线, 节约了车主的大量时间。

4 智能交通体系的建立

4.1 智能交通建立的框架

主要包括感知数据层、软件应用平台及分析预测和优化管理的应用。物理感知层主要是采集交通的运行状况和对交通数据的及时感知;软件应用平台主要整合每个感知终端的信息、将信息进行转换和处理, 达到支撑分析并做出及时的预警措施。比如:对主要交通干进行规划, 对频发交通事故进行监控。同时还应进行应用系统建设的优化管理。比如:对机动车进行智能诱导、智能停车。

智能交通系统需要在各道路主干道上安装高清摄像头, 采用先进的视频监控、智能识别和信息技术手段, 来增加可管理的维度, 从空间的广度、时间的深度、范围的精细度来管理。整个系统的组成包括信息综合应用平台、信号控制系统、视频监控系统、智能卡口系统、电子警察系统、信息采集系统、信息发布系统。每个城市建立智能交通并进行联网, 则会产生越来越多的视频监控数据、卡口电警数据、路况信息、管控信息、营运信息、GPS定位信息、射频识别信息等数据, 每天产生的数据量将可以达到PB级别, 并且呈现指数级的增长。

4.2 智能交通数据处理体系的构成

主要包括交通的数据输入、车辆信息、道路承载能力等的数据处理、数据存储、数据检索。其中交通数据输入可以是静态数据或者是动态数据。数据处理是针对实时数据的处理。数据主要存储的是每天采集的巨大数据量。为了从中获取有用的数据, 则需要进行数据查询和检索, 还要对数据进行规划。

5 大数据技术

5.1 数据采集与预处理

数据采集与预处理主要对交通领域全业态数据的立体采集与处理来支撑交通建设、管理、运行决策。采集的数据主要是车辆的实时通行数据, 以实现实时监控、事先预测、及时预警, 完成道路网流量的调配、控。这些数据获取可以采用安装的传感器、识别技术并完成对已接收数据的辨析、转换、抽取、清洗等操作。

5.2 数据存储与管理

大数据的存储与管理是把采集到的数据存放在存储器, 并建立相应的数据库, 如关系数据库、Not Only SQL即对关系型SQL数据系统的补充。利用数据库采用更简单的数据模型, 并将元数据与应用数据分离, 从而实现管理和调用。

5.3 数据分析与挖掘

数据分析及挖掘技术是大数据的核心技术。从海量数据中, 提取隐含在其中, 人们事先未知的, 但又可能有用的信息和知识的过程。从复杂数据类型中挖掘, 如文本、图片、视频、音频。该技术主要从数据中自动地抽取模式、关联、变化、异常和有意义的结构, 可以预测模型、机器学习、建模仿真。从而实现一些高级别数据分析的需求。

5.4 数据展现与应用

数据技术能够将每天所产生的大量数据从中挖掘出有用的数据, 应用到各个领域有需要的地方以提高运行效率。

6 结束语

大数据时代, 能对智能交通信息资源进行优化配置, 能够改善传统的交通问题。对非机动车主而言, 利用大数据可以更好的规划线路, 更好的了解交通状况, 在一定程度上可以对问题预先提出解决方案, 起到节省大量时间、额外的开支。同时对交管部门而言, 能够在限的警力情况下合理配置人员资源和交通设备, 主干道路在高峰期出现的问题能够合理利用大数据信息配置资源, 在刑事案件侦查中也能发挥更重要的作用。

全国要实现智能交通的联网, 依然有问题需要突破, 这都是大数据的数据技术应用所在。

参考文献

篇4：产业结构对交通运输结构影响分析

1、研究背景及意义

交通运输结构体现了地区交通运输的发展程度和规模，其中国民经济是影响区域交通运输结构的重要因素之一。2013年北京市生产总值达到了19500.56亿元。北京市经济的高速发展引起了区域内部交通运输结构的变化，本文从北京市产业结构规模变动现状出发，借助灰色关联理论分析方法，定量分析产业结构变化对交通运输结构变化的影响，从而为今后北京市交通运输结构发展策略提供理论支撑。

2、北京市产业结构与交通运输现状分析

北京市地区生产总值呈现稳步上升趋势，北京市地区生产总值从2006年8117亿元增长至2013年的19500亿元，平均每年约增长1626亿元，其中2013年第一、二、三產业生产总值所占比例分别约为0.83%、22.32%、76.85%，由此可见北京市社会经济保持高速增长的态势。

在货物运输方面，从2006年的33547万吨增长到了2013年的27180万吨。货物周转量从3376300万吨公里涨到了29996599万吨公里。公路运输仍然占据主导地位，铁路货物运输近10年都在2000万吨以上。

3、北京市产业结构与交通运输的灰色关联度分析

根据北京市统计信息网的2014年北京市统计年鉴提取数据，在交通运输方面的指标为货运量和货物周转量，可以细分为铁路、公路和民航。

4、计算结果

由表2可以看出，北京市铁路运输方式的货运量、货运周转量与第二、三产业关联度较高，由此可知，第二、三产业的发展可以进一步刺激铁路运输方式结构的增长；对于公路和航空而言，其货运量、货运周转量则与第一产业关联度较高，第一产业的发展可以进一步刺激公路和航空运输方式结构的增长。

5、结论

随着国民经济持续快速的协调发展，产业结构也呈现快速变化趋势，由于各个产业对交通的需求程度不同，因此，不同的产业结构比例对应着与其发展相协调的交通运输结构。由此可见，分析运输与产业结构的关系，对于把握产业结构的调整对交通运输需求的变化趋势有着重要的作用。

篇5：西安交通大学数据结构

—全国铁路咨询系统

目录

一．需求分析****************************************** 3

二．概要设计******************************************

三．储存结构设计**************************************

四．详细设计******************************************

五．用户手册******************************************

六．测试数据******************************************

七．心得体会****************************************** 8 11 17 18 26

一、需求分析

1、问题描述

由于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的时间尽可能短，出门旅游的游客则期望旅费尽可能省。编制一个全国城市间的交通咨询程 序，为旅客提供两种最优决策的交通咨询。

根据铁路的特征，数据的储存需要使用图的结构。每个城市之间有不同的车次，每个车次的始发站、路过车站和终点站都不一样，所以两个城市之间就有指向明确的边，是一个有向图；而由于车次的不一样，所以发车时间，到站时间，价格等也会不一样；所以每两个点之间不止两条边，可能存在不同的多条边。

2、功能需求

铁路咨询的对象是用户，所以，需要一个对用户友好的功能菜单，根据用户可能需要的实际需求，功能菜单中可能会包括以下要点：

1：显示所有车站信息

2: 显示所有车次信息（包括时刻表）

3: 查询车站信息

4: 查询两个城市之间的铁路信息

5: 增加或删除车站

6: 增加或删除铁路信息

7: 增加、删除或修改时刻表、距离和价格

8：寻找两城市间最省钱的一条路径

9：寻找两城市间最省时间的一条路径 10：寻找两城市间所有路径(按费用从低到高排序输出)

11：寻找两城市间所有路径(按所用时间从少到多排序输出)

12：退出咨询系统

图的初始数据从文本中读入，文本是老师给的标准数据。

3、输入及输出格式

(1):输入格式：

A：图的初始数据输入

数据的初始化是需要从文本中读入的，所以不需要有专门的文本输入函数，只需要给出读文本的函数input（）；使用input（）函数从测试数据的三个文本中读入数据，然后使用创建图的函数CreateGraph（）创建起整个图。初始数据的读入，分别是从station.txt中读入每个城市站点的名称的城市编号，从iinformation.txt中读入每个城市间的铁路信息，从railway.txt中读入所有铁路线的信息。

如：

以下从station.txt中节选部分

0 北京广州石家庄郑州武汉长沙

以下从information.txt中节选部分

出发城市编号 到达城市编号 车次 里程

费用

出发时刻

到达时刻

0

1000 287

62.5

0000

0246

0

1016 287

0060

0275

0

1001 137

23.5

0000

0117

0

1017 137

28.5

0060

0163

0

1002 1199 156.5 0000

1028

1008 1257 162.5 0000

1077

以下从railway.txt中节选部分

各条铁路线上城市编号（此行可去掉）

京广线 0 2 3 4 5 6 1

京九线 0 13 14 12

京沪线 0 8 9 10 11 7

陇海线 18 10 3 20 24 19

B：用户要求输入

用户在使用本程序时，会要求用户输入各种数据，如城市编号id、抉择选项y/n等；用户只需要按照程序菜单的要求输入即可。如城市编号id就是初始化数据（文本数据）中每个城市就有的编号，用户在不知道城市编号之前先查看一下城市信息就可以清楚明了的知道城市id了。

(2):输出格式

在系统的管理下，为了用户的查询方便，需要有多重输出方式。如每条铁路线上信息的输出。这里面就包括了，在每条铁路上所有车次信息，每个车次始发站信息、过站信息和终点站信息。

样例如下：

兰新线中有以下车次：

1005次列车运行情况：

出发城市

到达城市

车次

距离(km)出发时间

到达时间

费用(元)

兰州

酒泉

1005

748

0：0

10：41

酒泉

乌鲁木齐

1005

797

10：51 22：14

152.5

乌鲁木齐

阿拉山口

1005

477

22：24

5：13

64.5

1013次列车运行情况：

出发城市

到达城市

车次

距离(km)出发时间

到达时间

费用(元)

阿拉山口

乌鲁木齐

1013

477

0： 0

6：49

64.5

乌鲁木齐

酒泉

1013

797

6：59

18：22

152.5

酒泉

兰州

1013

748

18：32

5：13

对于每个城市信息的输出，只需要输出经过每个城市的铁路新路即可，当然必须得输出城市站点的id，方便用户的查询和管理

样例如下：

城市编号

城市名称

过站铁路线

0

北京

京广线

京九线

京沪线

广州

京广线

石家庄

京广线

郑州

京广线

陇海线

武汉

京广线

长沙

京广线

株洲

京广线

沪昆线

上海

京沪线

沪昆线

二、概要设计

1.数据特性分析

（1）：整体结构分析

铁路交通咨询模拟系统管理的是全国的各个城市间的铁路信息。对于整体的全

国铁路信息来说，每一个城市站点就是一个顶点节点，城市与城市之间的每一个车

次信息就是一条有向边。所有整个咨询系统应该是一个有向图结构。从A城市出发

到B城市，可能会有多个车次。

如下例：

出发城市

到达城市

车次

距离(km)出发时间

到达时间

费用(元)

北京

石家庄

1000

287

0： 0

4： 6

62.5

北京

石家庄

1016

287

1： 0

4：35

所以每两个城市顶点之间就可能会有多条有向边，所以这个图也不会是 一个有

向简单图了。为了城市节点能够动态的扩充和删除不受影响，我对于顶点的储存采

用链表结构不使用顺序表结构，定义一个顶点链表类VertexList。这样，虽然链表查

询和其节点的删除的时间复杂度受到了一定的影响，但这样设计出来的铁路网图才

更具有一般性个实用性。对于查找的时间复杂度问题的解决，我在后面也会给出方案。

（2）：城市顶点分析

对于每一城市来说，在全国的铁路网中，它就是一个火车站节点。每一个火车，它都应该会有自己的名字，过站的铁路线等。为了咨询系统管理和维护的方便，在 文本数据中，我们就人为的给每一个城市都编上序号id，每一个不同id对应了一

个不同的城市节点。由于每个城市的id都是唯一的，所以在顶点的链表结构里面，完全可以定义一个哈希表haxi[n]，对于haxi[i]来说，它存储的就是id为i的城市

在内存中地址。这样，顶点链表在哈希表的支持下，就能完美解决查找、添加、删除的时间复杂度问题了。

在整个铁路网中，每一个城市就是顶点，每一个顶点，就是应该有一个边链表

用于储存此城市能到达所有城市的各个不同车次的信息，也就是各个不同的边。如：

出发城市编号 到达城市编号 车次 里程

费用

出发时刻

到达时刻

0

1000 287

62.5

0000

0246

0

1016 287

0060

0275

从上例我们可以看出，对于每个顶点的不同边来说，每一个不同的边就有一个独有

的车次。所以这样，对于边的储存，我们也可以采用哈希表结构。经观察发现，每 一车次都大于1000，所以，哈希表的id=车次-1000；对于编号为a的城市节点haxi[k]

来说，它储存的是为城市a中车次为：1000+k的一条边，边里面就有到达城市、出发和到达时间、费用、距离等等。

（3）：边数据分析

对于图来讲，边就是一个逻辑结构，沟通顶点与顶点之间的关系。同时了，边还有其物理特性。他需要储存边的权值等，它需要开辟储存空间来存储数

据。在铁路网中，每两个城市之间不同的车次信息就是一条不同的边，所以，我需要把物理特性给单独列出来，成为一个类LineInformation，用于表示边

的物理信息。对于图中抽象的边，也需要定义一个类EdgeNode，用于沟通

图中原本孤立的顶点，使之变成一个完整的图

2.整体概要设计

前面，我提到了有顶点类station、顶点链表类VertexList、边的物理类LineInformation和边的逻辑类EdgeNode、火车线路类railway；对于整个完整的图类来说，还有两个主要的类没有提及，那就是图类RailwayNet和管理图类的类management。当然对于图中需要完成各个不同功能的时候，我还写了许多的辅助类。如查找两个车站之间所有路径时需要用到的LinStack，当然还有LinStack的类的基石StackNode类。整个咨询系统还有许多的结构体，这些结构体的功能我就不一一叙述了，详细可见源代码的注释。下面我就列出各个类的关系图

三．储存结构设计

1、存储结构的确定

数据结构的目的是有效组织和处理数据。为了有效组织和处理数据，先要分析多项式操作的特点和指针所占空间比例，然后确定最优的存储结构。

1.铁路网是由铁路和火车站构成，每个火车站相当于一个定点，每新建一条铁路就相当于新建定点之间的边

2.车站之间可以任意到达，可直接相连，也可以间接相连，且怎么连接是不固定的。3.综上所述，资源管理器的存储结构采用树形结构。

2、类的结构设计图：

management类图：

RailWay类图：

VertexList类图：

RailWay类图：

LineInformation类图：

EdgeNode结构图：

Station类图；

四、详细设计

1.管理类management

class management{ private:

vector m_city;vector m_edge;vector m_rail;RailwayNet m_graph;void input();void VertexDisplay();//边的输出函数，输出一条边的信息 void EdgeDisplay(EdgeNode *edge);//输出函数，被 RailwayDisplay（）调用

void NextDisplay(EdgeNode* edge, LinStack & UsedTrainNumber, int a);void RailwayDisplay();void SearchStation();void SearchRail();void EditStation();void EditRail();void EditInformation();void ShortestCost();void ShortestTime();void SearchAll(vector & AllPath);void PathDispaly(vector & path);void OrderOnCost();void OrderOnTime();public: 2.图类RailwayNet //全国铁路信息网类（邻接表图类）class RailwayNet{ private:

//私有的函数，以深度优先遍历的方式寻找两点之间的所有路径

void DepthFirstSearchPath(vector & pa, time_and_cost_path & p, VertexList vertex;//顶点链表 vector m_rail;EdgeNode *edge, int terminal, LinStack & UsedVertex);

//私有函数，以Dijkastra算法寻找最节省时间的路径

void ShortestCost(vector & OptimalPath, int origin, int terminal);// 获取起点origin到终点terminal的最少用时 void ShortestTime(int origin, int terminal);void ShortestTime2(vector & OptimalPath, int origin, int terminal);//快速排序

void QuickSort(vector & AllPath, int low, int high, int option);public:

};

VertexList & Vertex(){ return vertex;} vector & GetRail(){ return m_rail;} //插入顶点

void InsertVertex(station* s);//在顶点v1和v2之间插入一条边(边的起点为v1，终点为v2)void InsertEdge(int v1, int v2, EdgeNode* & ed);//删除编号为id的城市顶点 void DeleteVertex(int id);//删除边edge

void DeleteEdge(int v1, int v2);//创建一个邻接表图

void CreateGraph(RailwayNet & graph, vector & city, vector //输出图

void display(RailwayNet & graph);//返回顶点v1和v2的第一条边

EdgeNode* const GetFirstEdge(int v1, int v2);//获取起点origin到终点terminal的最少费用

float GetShortestCost(int origin, int terminal, LineInformation & edge);//获取边路径path中的用时

int GetPathTime(vector & path);//获取边路径path中的费用

float GetPathCost(vector & path);//对vector中的元素按照要求排序【option为 1 表示以最省钱方式，为 2 表示以最省时方式】 void Sort(vector & AllPath, int option);//求点origin到terminal的所有路径

void GetAllPath(vector & AllPath, int origin, int terminal);//求点origin到terminal的最短“路径”（路程最短或时间最省）【使用Dijkastra算法】 void BestOption(vector & OptimalPath, int option, int origin, int & edge, vector & rail);terminal);3.顶点链表类

//顶点链表类 class VertexList{ private:

station *head;//头指针

int size;//链表的大小（元素的个数）

station* haxi[1000];//哈希表，内存有节点的地址(哈希表中的下标与对应城市节点的ID相等)public:

};VertexList();~VertexList();station* & GetHead(){ return head;} int & GetSize(){ return size;} //按照id从小到大的顺序将city插入链表中 void insert(station* city);//删除城市编号为id的节点 void Delete(int id);//根据城市的id获取城市节点 station* GetVertex(int id);station** GetVertexHaxi(){ return haxi;} int IsVertexExist(int id);

4.顶点类

class station{ private:

int m_size;//边链表的大小

EdgeNode* haxi[100];//以此车站为始发站的边的哈希表(下标为：车次-1000)vector ha2;//以此车站为终点的边在其哈希表中的下标 station();//默认构造函数

station(string na, int i);//构造函数 station(const station & sta);//复制构造函数 void Delete();//删除函数 //接口函数 station* prior;//指向上一个车站 station *next;//指向下一个车站 EdgeNode *head;//指向第一条边节点 string m_name;int m_id;vector m_rail;public:

};string & GetName(){ return m_name;} int & GetId(){ return m_id;} vector & GetRail(){ return m_rail;} station* & GetPrior(){ return prior;} station* & GetNext(){ return next;} EdgeNode* & GetHead(){ return head;} int & GetSize(){ return m_size;} EdgeNode** GetHaxi(){ return haxi;} vector & GetHa(){ return ha2;} 5.边节点类EdgeNode //边结点结构体 struct EdgeNode{

LineInformation information;EdgeNode *next;//下一个边结点 EdgeNode *prior;//上一个边节点

};

6.边物理类LineInformation

class LineInformation{ private:

int m_DepartId;//出发城市编号 int m_ArriveId;//到达城市编号 int m_TrainNumber;//车次 int m_distance;//车程 float m_cost;//费用 int m_DepartTime;//出发时间 int m_ArriveTime;//到达时间

//默认构造函数 int DepartId=0, int ArriveId=0，LineInformation(int DepartId = 0, int ArriveId = 0, int Train = 0, int distance =-1, //复制构造函数

LineInformation(const LineInformation & l);~LineInformation(){};LineInformation operator=(const LineInformation& e);//接口函数

int & GetDepartTime(){ return m_DepartTime;} int & GetArriveTime(){ return m_ArriveTime;} int & GetTrainNumber(){ return m_TrainNumber;} public: float cost = 0, int DepartTime =-1, int ArriveTime =-1);

};int & GetDepartId(){ return m_DepartId;} int & GetArriveId(){ return m_ArriveId;} int & GetDistance(){ return m_distance;} float & GetCost(){ return m_cost;}

7.火车线路类railway

class railway{ private:

};string m_name;//火车线名

vector m_station;//线路进过的火车站的id railway(string s = “ ”):m_name(s){} string & GetName();vector & GetStation();void Delete(int a);public:

8.自定义栈类

template class LinStack;template class StackNode{

};

template class LinStack{ private: friend class LinStack;T data;

//定义类LinStack为友元

//数据元素 private: StackNode *next;

//指针

//前视定义,否则友元无法定义

//模板类型为T

public: //构造函数1,用于构造头结点

StackNode(StackNode *ptrNext = NULL);//构造函数2,用于构造其他结点

StackNode(const T& item, StackNode *ptrNext = NULL);~StackNode(){};

};StackNode *head;int size;

//头指针 //数据元素个数 //构造函数 public: LinStack(void);~LinStack(void);T Pop(void);

//析构函数 //入栈 //出栈 //取栈顶元素 //堆栈非空否 void Push(const T& item);T GetTop(void)const;

int NotEmpty(void)const;

bool IsInStack(T a);//判断元素a是否在栈中 void Empty();//清空栈

int GetSize();//获取栈中元素的个数 void display();//输出栈中元素

五、用户手册

1.本程序运行在Windows操作系统下，VS2013，按F7编译，F5运行。

2.在程序运行前有预设函数，最好选择预设函数，然后进行测试。

3.在菜单中选择你想进的功能，然后输入前面的数字即可。

用户菜单如下：

*****************************全国铁路交通咨询模拟**************************** 1: 显示所有车站信息

2: 显示所有车次信息（包括时刻表）

3: 查询车站信息“

4: 查询两个城市之间的铁路信息

5: 增加或删除车站

6: 增加或删除铁路信息

7: 增加、删除或修改时刻表、距离和价格

8: 寻找两城市间最省钱的一条路径

9: 寻找两城市间最省时间的一条路径

10:寻找两城市间所有路径(按费用从低到高排序输出)

11:寻找两城市间所有路径(按所用时间从少到多排序输出)

12: 退出咨询系统”

*****************************************************************************"

六、测试数据

1.用户菜单

在输入指令一栏输入你想要使用的功能的数字编号。如：输入1 功能为：显示所有车站信息

由于数据过多，这里只截取部分输出

输入指令：2 功能：查询所有车次信息

数据量太大，也只截取部分输出。

输入指令：3 功能：查询车站信息

车站信息有：

1.从此车站出发各个车次信息。2.从其他车站出发到达此车站的信息

输入指令：4 功能：查询两个车站之间的信息

查询的时候，是由先后顺序的，先输入的是出发城市，后输入的到达城市

输入指令：5 功能：增加或删除车站

样例1：增加成功

样例2：增加失败

错误原因：编号输入错误 编号id为12：九龙

所以此编号已有城市占用，输入错误

样例3：删除成功

现在可查询广州的信息

发现广州此时已不存在，删除成功

样例4：删除失败

错误原因：id为31 的城市不存在

输入指令：6 功能：增加或删除铁路信息

样例1：增加失败

失败原因：id为1的城市已删除，不能再城市1余城市6之间增加铁路

样例2：增加成功

此时新建铁路状态：还有铁路线，没有车次 注：想要铁路线有火车运行，必须补充车次信息

样例3：删除成功

样例4：删除失败

失败原因：不存在从城市9到城市13的铁路

输入指令：7 功能：增加、删除或修改时刻表、距离和价格

测试样例：

可查询修改后的价格 出发城市：6 株洲 到达城市：5 长沙

车次为：1022的信息中 价格：999 修改成功！

输入指令：8 功能：寻找两城市间最省钱的路劲

输入指令：9 功能：寻找两城市间最省时间的路劲

输入指令：10 功能：寻找两城市间所有路径(按费用从低到高排序输出)

数据过多，取前二十条显示，我也只截取前一部分数据

输入指令：11 功能：寻找两城市间所有路径(按所用时间从少到多排序输出)

数据过多，取前二十条显示，我也只截取前一部分数据

注：后面的测试时前面面修改后的结果，所以，计算的结果和初始化数据计算的结果可能会不一致，这是因为只是可能计算会用到我修改后的数据，所以存在不一致的问题。

篇6：西安交通大学数据结构

1.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

3.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

① front=11，rear=19;② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

4.试将下列递归过程改为非递归过程。

void test(int &sum){

int x;

Sanf(x);

if(x= =0)sum=0;

else {test(sum);sum+=x;}

printf(sum);

}

1.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；

队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是„„）

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。

2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。

采用循环队列是解决假溢出的途径。

另外，解决队满队空的办法有三：

① 设置一个布尔变量以区别队满还是队空；

② 浪费一个元素的空间，用于区别队满还是队空。

③ 使用一个计数器记录队列中元素个数（即队列长度）。

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。

判断循环队列队空标志是： f=rear队满标志是：f=(r+1)%N

3.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

① front=11，rear=19;② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

答：用队列长度计算公式：(N＋r－f)% N

① L=（40＋19－11）% 40=8② L=（40＋11－19）% 40=32

4.参考程序：

void test(int &sum){

Stack S;

int x;

Sanf(x);

InitStack(S);

While(x){

Push(S,x);

Scanf(x);

}

sum=0;

printf(sum);

while(Pop(S,x)){

sum+=x;

printf(sum);

}