书名：动手学数据结构与算法
ISBN：978-7-115-64780-1
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 俞 勇 翁惠玉 傅凌玥 周 聪
责任编辑 刘雅思
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书系统介绍了数据结构与算法的基本概念和相关知识，既注重理论，又注重算法设计，更突出代码实现，是一本着眼于数据结构与基本算法的教学实践的教材。
本书介绍了线性表、队列与栈、树与优先级队列、集合与静态查找表、动态查找表、排序、外部查找与排序、图、最小生成树与最短路径、算法设计思想等内容，将数据结构的理论与真实应用的实践紧密结合，从各种数据结构的代码实现到火车票管理系统的代码实现，手把手地指导读者学习数据结构与算法，帮助读者轻松掌握数据结构与算法的基本知识及基本技能，为后续进行更多专业课程的学习打下扎实基础。
本书可以作为高等院校计算机和人工智能相关专业学生的教材，也可以作为广大计算机科学与工程领域从业人员的参考书。
天施地生，其益无方。凡益之道，与时偕行。
——《周易•益卦•彖传》
自20世纪90年代互联网进入商用并迅速兴起，到21世纪20年代大数据、人工智能技术的快速迭代，直至近几年大语言模型的迅猛崛起，这短短的30多年，科技有了极大的进步，社会有了极大的发展，不仅改变了世界的格局，也改变了人们的生活。
为了顺应时代的变化，专业教育何为？专业人才何所？2021年我们开始筹划一套可以“动手学”的人工智能系列教材——新一代人工智能实战型人才培养系列教程，这套教材将分期出版，第一期包括《动手学强化学习》《动手学机器学习》《动手学自然语言理解》《动手学计算机视觉》《动手学博弈论》《动手学数据结构与算法》等6册，稍后还会推出第二期，甚至第三期。
十年磨一剑，廿年亮一剑。自2002年上海交通大学ACM班创办至今已有20多年，这个以培养计算机科学家及行业领袖为宗旨的班级，已在国内外的学术界和工业界小有名气，其“秘籍”到底是什么？或许可以通过阅读和学习这套教材得知真相。
这套教材将满足高等院校的计算机专业、人工智能专业及新工科专业的学生，从事科研工作的高校教师、科研院所人员，转行到IT行业的从业人员及自学人群等对人工智能进行系统的理论学习，学后能够直接上手实战的需要。这是目前国内第一套可以“动手学”的人工智能系列教材，希望能为我国的人工智能实战型人才培养及人工智能落地做些有益的探索与实践。欢迎高等院校的教师与学生、科研院所及企业的研究人员与工程师、社会人士使用这套教材。
任何事物都有从无到有、从无序到有序的发展过程，人类社会的进化也是如此。有序就是循规蹈矩，有了规和矩才能画出圆和方。于是，世界万物也就有了各自的“形状”。
所谓数据结构与算法，则是用一定的“规则”和“方法”对大千世界的“重塑”。这里的规则，既不是抽象的数学，也不是具象的物理，它既要符合数学、物理等学科的思维，又要符合生活常理，更不同的是，它是一种计算机能表示，甚至能理解的方法。使用这些规则和方法，我们就可以方便地利用计算机重塑现实世界，为我们创作未来世界打下良好的基础。
计算机学科已经渗透到各个领域及行业，因此几乎所有专业（包括人工智能专业）都无法完全脱离计算机专业，数据结构是计算机类专业最基础，也是最重要的核心课程之一，它为其他后继课程的学习奠定了基础，很多学校在新工科平台的培养计划中也将其列为必修课程，数据结构的重要性不言而喻。同时，数据结构与算法又是一门实践性非常强的课程，这门课的难点不是理解不了知识点，而是想不出算法，更是写不出代码。但是，已有的教材主要注重知识点的描述方式与形式，例如用生活场景和动画展现，无法在教学过程中解决其实践性特点所带来的学习上的真正困难。那么，如何在教学过程中将理论讲解与代码实践无缝衔接，让学生真正做到边学边练呢？本书试图给出答案。
本书以动手练平台与电子资料仓库的形式为读者提供课程辅助材料和代码。书中将每一章的原理讲解部分与其代码实践部分耦合，读者在学完一个知识点原理后能立即以代码实践的形式学习其实现方式。更重要的是，可以直接对代码进行在线运行和修改，完成对一种数据结构的原理学习和代码实践。这样的学习方式能帮助读者更好地将理论知识点与实践能力点对应，也能帮助老师更高效地授课、布置作业和批改作业。
通过长期的程序设计及数据结构的教学探索与实践经验总结，我们特编写了本书，旨在分享上海交通大学ACM班的培养模式及教学方法，使读者不再畏惧代码，让每一个普通人都能上手“拿捏”代码，成为人工智能时代的弄潮儿，为我国乃至世界人工智能的发展贡献一份力量。
本书的编写遵循“问题先导，应用贯穿；描述简洁，代码其中”的原则。全书共包含11章，以火车票管理系统大型应用为主线，介绍涉及的基本概念、实现及应用。除了第1章和第11章，每章结构的安排基本按照问题引入、定义与实现、简单应用、大型应用实现、小结与习题的框架。
第1章由火车票管理系统这个大型应用引入数据结构的基本概念（逻辑结构、存储结构、操作定义和操作实现等）、算法分析（时间复杂度、空间复杂度等）及优化，并介绍火车票管理系统的需求分析、系统构成及涉及的数据管理类。
第2章介绍线性表的基本概念（定义、实现与简单应用），并介绍大型应用中列车运行计划管理类的实现。
第3章介绍队列与栈的基本概念（定义、实现与简单应用），并介绍大型应用中排队交易类的实现。
第4章介绍树的定义、二叉树与优先级队列的基本概念（定义、实现与简单应用）、哈夫曼树与哈夫曼编码，并介绍大型应用中带优先级的排队交易类的实现。
第5章介绍集合的定义、静态查找表及并查集，并介绍大型应用中列车运行图类及旅途中的站点可达性查询的实现。
第6章介绍二叉查找树、AVL树、红黑树、哈希表的基本概念（定义、实现），并介绍大型应用中旅客管理类的实现。
第7章介绍排序的定义、插入排序、选择排序、交换排序、归并排序和基数排序。
第8章介绍外部查找表的定义、B树、B+树、外排序，并介绍大型应用中余票管理类与行程管理类的实现。
第9章介绍图的定义、实现、遍历（深度优先搜索、广度优先搜索）及图的遍历的简单应用（连通性、欧拉回路、拓扑排序及关键路径），并介绍大型应用中列车运行图类的线路途经站点查询的实现。
第10章介绍最小生成树（定义、克鲁斯卡尔算法及普里姆算法）、单源最短路径（非加权图、加权图、带有负权值图及无环图的最短路径）、所有顶点对的最短路径，并介绍大型应用中列车运行图类的最优路线查询的实现。
第11章介绍枚举法、贪婪算法、分治法、回溯法、动态规划、随机算法，并通过一个外卖配送任务实例进行算法综合分析。
本书的11章内容皆为数据结构与算法的主干知识，所有希望系统掌握数据结构基本知识及基本算法的读者都应该学习这些内容。
本书包括纸质图书与电子资源两部分。纸质图书包括相关数据结构的定义、实现、简单应用、大型应用的实现代码。电子资源包括三部分——理论解读视频、动手练平台与电子资料仓库，均可通过http://hds.boyuai.com访问，动手练平台与电子资料仓库的具体使用方法参见附录B。纸质图书的正文中还将提供对应视频课程的二维码，供读者使用手机扫描学习。本书提供的代码都是基于C++编写的，读者需要具有一定的C++编程基础。
读者可以根据自己的需求自行选择感兴趣的纸质内容或电子资源进行学习实践。例如，只想学习各种数据结构的基本概念而不关注具体实现细节的读者，可以只阅读代码以外的文字部分；已经了解了算法的实现，只想动手进行代码实践的读者，可以只关注代码的具体实现部分，直接使用动手练平台与电子资料仓库。
本书具有如下特色：
● 以大型应用中的实际场景作为问题引入，使读者在学习知识点前体验“有用”；
● 为各类数据结构配备完整的代码实现，使读者能将理论与实践相联系，更真切地感受“好用”；
● 完整地实现数据结构中公认最烦琐的B+树，使读者消除恐惧，领略“可用”；
● 以大型应用的实现贯穿本书所有章节，使读者在了解知识点的同时亲历“实用”。
本书是数据结构与算法的入门读物，也可以作为高校数据结构与算法课程的教材或者辅助教材。本书面向的读者主要是对数据结构与算法感兴趣的高校学生（包括本科生和研究生）、教师、企业及研究院所的研究人员及工程师。在阅读本书之前，读者需要掌握一些C++程序设计语言的基本语法和编程技能。由于编写时间有限，书中难免会有一些不足之处，恳请读者批评指正，以便再版时修改、完善。希望每一位读者在学习完本书之后都能有所收获，为本系列后续教材的学习以及投身人工智能事业打下良好的基础。
学而时习之，不亦乐乎。
——《论语》
同学们，动起手来，快乐学习，轻松编程，共创未来！
由衷感谢上海交通大学ACM班的历届助教及学生长期以来的积累，他们为本书做出了卓越贡献。
感谢ACM班21级的冯跃洋、杨晋晟同学完成本书中大型应用实现及火车票管理系统的完整代码及调试，为本书的代码实现做出了重要贡献。
感谢ACM班22级的王鲲鹏、王冠杰、张世奇、陈瑞茗、李紫燕为本书绘制插图。
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
本书提供如下资源：
● 配套源代码；
● 教学课件；
● 习题答案；
● 理论解读视频。
要获得以上配套资源，您可以扫描下方二维码，根据指引领取；
您也可以在异步社区本书页面中点击
，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。
如果您是教师，希望获得教学配套资源，请在社区本书页面中直接联系本书的责任编辑。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“发表勘误”，输入勘误信息，点击“提交勘误”按钮即可（见下图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
本书责任编辑的联系邮箱是liuyasi@ptpress.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书技术审校等工作，可以发邮件给我们。
如果您来自学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接通过邮件发给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”（www.epubit.com）是由人民邮电出版社创办的IT专业图书社区。异步社区于2015年8月上线运营，致力于优质学习内容的出版和分享，为读者提供优质学习内容，为作译者提供优质出版服务，实现作者与读者在线交流互动，实现传统出版与数字出版的融合发展。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社30余年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
数据结构用于描述数据的存储方式，算法用于描述数据的处理过程。数据结构和算法是相互关联的。数据结构的选择会影响算法的选择，反之，算法的选择也会影响数据结构的选择。
本书将基于从火车票管理系统这一应用，引入数据结构及算法的基本概念，详细讨论各类数据结构，并用相应的数据结构实现火车票管理系统中的相应模块（功能），还将介绍一些经典和常用的算法。
1.1 问题引入火车票管理系统
很多人坐火车出行时，会选择通过“中国铁路12306”网站或“铁路12306”App（即火车票管理系统）购买车票。本章以一个简化的火车票管理系统为例，从需求分析、功能划分、系统设计等层面分析火车票管理系统的实现，直至“破茧”底层的数据结构。
火车票管理系统是一种典型的高性能大数据应用，主要用于解决旅客查票、购票，以及管理员制订列车运行计划、票务管理等问题。通过对火车票管理系统的功能调研，进行火车票管理系统的需求分析，如图1-1所示。本系统考虑两类用户：管理员与旅客，使用人形图标表示。
图1-1展示了火车票管理系统中用户功能和数据之间的关系。下面简单梳理一下系统功能。
对管理员来说，首先需要添加列车运行计划，这是整个系统最基础的信息。简单起见，列车运行计划只包括车次号、日期、额定乘员、途经站点、时长与票价等信息，车次对应该列车途经站点的序列。管理员还需要查询列车运行计划。
管理员还需要负责车票的发售与停售。在列车开行前若干天发售车票，而列车发车前停止售票，因此管理员需要频繁地进行票池的维护与管理。
对旅客来说，可以按照其行程需要查询相应线路。例如，旅客只知道自己的出发站和到达站，并不知道相应的路线，通过路线查询可以得知从出发站到到达站是否可达（直达或转车）。旅客可能还想知道从出发站到到达站可以选择哪些路线，分别经过哪些站点，并按照票价最低、历时最短等偏好筛选最优路线及车次，系统将根据列车运行计划回复旅客。获知路线后，旅客还可以进行余票查询、购票、退票、已购车票查询等操作。
图1-1 火车票管理系统的需求分析图
旅客信息的管理是两类用户共同涉及的功能。旅客可以注册、修改、查询自己的信息。在实际的火车票管理系统中，军人和老弱病孕残通常可以优先购票或退票，所以每个旅客都对应一个优先级。旅客的优先级不能自己指定，只能由管理员核实并修改。
用户与各系统功能在交互过程中产生的各类数据在图1-1中单独列出，如列车运行图、列车运行计划、旅客行程、余票信息、旅客信息等。这些数据与功能之间通过有向箭头连接。从数据指向功能的数据流代表此功能需要从系统中查询此类数据；从功能指向数据的数据流代表此功能产生新的数据或修改已有数据，需要写入系统。
上文简要介绍了火车票管理系统，可以看出，它涉及的数据种类较多（如旅客信息、行程、车次、车票、站点等），数据与数据之间（如某车次所途经的站点之间、列车运行图中站点之间等）、数据与功能之间（车票与购票、行程与查询、车次与发售等）的交互也颇为紧密。由此，可将火车票管理系统划分为5个子系统：列车运行计划管理子系统（列车运行计划添加和列车运行计划查询）、票务管理子系统（车票发售和车票停售）、车票交易子系统（查询已购车票、余票查询、购票、退票）、路线查询子系统（路线查询）、旅客管理子系统（旅客信息添加、修改和查询），如图1-2所示。其中，许多旅客可能会同时使用车票交易子系统，则该子系统将旅客的购票与退票交易请求按照先后顺序形成交易请求队列，并按顺序完成相应交易；也可以将旅客的购票与退票交易请求按照优先级顺序排列，高优先级的先交易，低优先级的后交易。
在实现火车票管理系统的过程中，如何管理好各子系统的数据并高效地使用这些数据，就是数据结构要解决的基本问题。
图1-2 火车票管理系统的构成
1.2 什么是数据结构数据结构是一组具有特定关系的同类数据元素的集合，其主要研究数据的逻辑结构、数据的存储结构，以及数据的操作定义和操作实现。
什么是数据结构
在现实生活中，数据元素之间的关系复杂而多样，但数据元素之间的逻辑关系仅可以分为4种：无关系、一对一关系、一对多关系、多对多关系，这4种逻辑关系统称数据的逻辑结构。
根据数据元素之间逻辑关系的不同，数据的逻辑结构可分为以下4类，如图1-3所示。
● 集合。集合包含的所有数据元素之间无关系，即数据元素的次序是任意的。集合中各个数据元素均是“平等”的，它们属于同一个集合，如图1-3（a）所示。例如，在操场上玩耍的学生，快递车上运输的快递包裹，在展览馆参观的游客等。又如，火车票管理系统中的每个旅客都是“平等”的，旅客之间没有关系。
● 线性结构。线性结构包含的数据元素之间存在一对一的关系，即数据元素构成一个有序序列。若存在多个数据元素，则第一个数据元素之前没有数据元素，最后一个数据元素之后也没有数据元素。除了第一个数据元素和最后一个数据元素，其余数据元素前面都有唯一的一个数据元素（称为前驱），后面也都有唯一的一个数据元素（称为后继），如图1-3（b）所示。例如，《水浒传》中的108条好汉形成了一个数据集合，他们的排列是有次序的，宋江排第一，卢俊义排第二，以此类推。又如，在火车票管理系统中，列车运行计划里每个车次所途经的站点是一个接一个的，形成了一个有序序列。
● 树形结构。树形结构包含的数据元素之间存在一对多的关系，即数据元素之间形成层次关系。除了根元素，每个数据元素有且仅有一个前驱，后继数目不限，根元素没有前驱，如图1-3（c）所示。例如，一个家族的家谱就可以表示为树形结构，老祖宗是树根，老祖宗的儿子是老祖宗的后继，每个人可以有多个儿子，因此后继数目不限，但每个人只能有一个父亲，因此只有一个前驱。
● 图形结构。图形结构包含的数据元素（顶点）之间存在多对多的关系，即每个数据元素的前驱和后继数目都不限。图形结构是最常见的数据逻辑结构，如图1-3（d）所示。例如，互联网的拓扑关系就是一个图形结构；朋友关系也是一个图形结构。又如，在火车票管理系统的列车运行图中，站点之间要么直接连接，要么不直接连接，构成图形结构。
图1-3 数据的逻辑结构示意图
数据的逻辑结构对应以下4类常见的操作（运算）：
● 构造和析构，包括数据结构的创建、初始化，以及必要的结构操作；
● 属性操作，包括读取数据结构各基本属性的值；
● 查找，包括特定搜索、访问和遍历数据元素的操作；
● 更新，包括插入、删除或修改数据元素的内容或更新数据元素之间的关系。
数据的存储结构（又称数据的物理结构）是数据的逻辑结构在计算机内的存储方式，共有以下4种。
● 顺序存储，指将所有数据元素存放在一段连续的存储空间中，数据元素的存储位置反映了它们之间的逻辑关系。例如，幼儿园小朋友按学号坐成一排就是一种顺序存储结构。线性结构中逻辑上相邻的数据元素，其对应的物理存储位置也是相邻的。顺序存储结构一般借助程序设计语言中的数组来实现。
● 链接存储，指逻辑上相邻的数据元素不需要在物理位置上也相邻，也就是说数据元素的存放位置可以是任意的。每个数据元素所对应的存储表示由两部分组成，一部分是数据元素，另一部分是指针，指针表示有逻辑关系的数据元素的存储地址。以快递运输为例，快递公司按照快递的目的地地址把快递一站一站地进行转运，即取件→起始地分运站→起始地总运站→目的地总运站→目的地分运站→送件，这样的转运过程就是一种链接存储。
● 索引存储，指分别存放数据元素和数据元素之间的关系。数据元素之间关系的存储称为索引。例如，去银行办理业务时通常需要排队，但人们并不需要真正站在窗口前排队，而是随意坐在大厅中等待叫号，大厅中排队的人就是数据元素，叫号系统中的编号就是索引。
● 哈希存储（又称散列存储），指将数据元素存放在一个连续的区域，每一个数据元素的具体存放位置是使用哈希（散列）函数根据其键值计算出来的。例如，邮政编码由6位数字组成，其中前两位代表省（自治区、直辖市），第三位代表邮区，第四位代表县（市）邮政局，最后两位代表投递局（乡镇支局所或城区的某一投递区域），这样就很容易根据邮政编码将信件投入相应的运输车。
这4种存储方式及其组合可以实现数据的灵活存储。注意，数据的逻辑结构表示的是数据元素之间的逻辑关系，与数据的存储结构无关，它是独立于计算机的。而数据的存储结构包括数据元素在计算机中的存储表示及数据元素的逻辑关系在计算机中的存储表示，它完全依赖于计算机。
数据结构的实现
数据的操作（也称运算或算法）包括操作定义和操作实现。操作定义是对现实问题的抽象，它独立于计算机，例如火车票管理系统中，管理员添加列车运行计划、旅客购票等。而操作实现的方式取决于数据的存储结构，它依赖于计算机和具体的程序设计语言。例如，旅客购票的实现方式取决于车票数据是如何存储的，假设车票是顺序存储的，并按起点的字母顺序排列，则可以通过二分法快速找到相应的车次完成购票，即车票（数据）的操作实现。
本书将采用C++语言实现所有数据结构的基本操作，以及火车票管理系统中主要数据管理模块的实现。
1.3 算法分析算法分析
设计算法时，常常需要在各种指标之间进行权衡和选择。有时候，一种算法可能会在某些特定情境下表现得非常出色，但在其他情境下可能效率低下。因此，算法的优化往往需要考虑问题的实际情况、数据的特征及算法的适用范围。本节将探讨算法分析的相关知识，帮助读者更好地理解和应用各种算法。
算法是为了求解问题而给出的有限的指令序列。对同一个问题采用不同的算法，虽然结果一样，但算法所消耗的时间资源和空间资源有很大的区别。那么，应该如何衡量不同算法的优劣呢？一般考虑以下几个指标。
● 正确性：能够按照预定功能产生正确的输出。
● 易读性：逻辑清楚、结构清晰，算法易于阅读、理解、维护。
● 鲁棒性：对于边界条件输入、不频繁出现的输入，算法能够产生正确的输出；对于非法输入，算法能够输出相应提示，不会发生崩溃。
● 高效率：时间和空间利用效率高，需要较少的运行时间和存储空间。
这些指标通常是互相冲突的。例如，算法考虑的情况越多，虽然的确会增加鲁棒性，但往往易读性会受到影响。本书将着重讨论算法的时间性能和空间性能，其他方面不在本书讨论范围内。
所谓算法分析，就是确定算法的时间性能和空间性能，即算法的时间复杂度和空间复杂度。前者是算法的运行时间度量，后者则是算法需要的额外存储空间的度量（即除算法本身和输入/输出数据所占用的空间之外的空间）。时间性能和空间性能一般不可兼得，需要选择一个平衡点。
影响程序运行时间的因素有：
● 程序采用的算法；
● 计算机软硬件系统的性能；
● 编译器生成的目标代码的质量；
● 问题规模；
● 数据的分布情况。
同一个问题往往可以采用不同的算法求解，例如去书店购买某本文学小说，有两种方式：第一种，在书店里挨个书柜寻找；第二种，直接去文学小说书柜寻找。显然，第一种方式的寻找时间长，而第二种方式的寻找时间要短很多。因此，程序采用的算法不同，其运行时间也大相径庭。
当在运算速度不同的硬件上运行同一个程序时，即便输入同样的数据，其所需的运行时间也会不同。即使硬件环境一样，程序运行在不同编译器的软件环境中，生成的可执行代码是不同的，运行时间也不一样。因此，运行时间不能说明程序采用的算法的优劣。
算法的时间性能应该与运行算法的计算机的软硬件系统无关，在算法分析中通常用运算量衡量。算法所需的运算量与所处理问题的规模之间的关系称为算法的时间复杂度。优化算法的时间复杂度的关键是降低所需的运算量。
算法的运算量除了与问题规模有关，还与被处理的数据的分布情况有关。在实际应用中，很难用单一指标描述算法的时间性能。算法分析中，通常用最好情况、最坏情况及平均情况时间复杂度描述不同的数据分布情况下的时间复杂度。例如，火车票管理系统中有n个车次存储于数组中，现要查找是否存在某个车次。假设算法从第一个车次开始依次往后查找，直到找到了该车次或找遍了整个数组也没有找到该车次。如果被查找的车次出现在第一个位置，则比较一次就找到了。在这种情况下，算法所需的时间最短，这就是最好情况的时间复杂度。如果被查找的车次出现在最后或根本没有出现，则需要比较所有车次，即比较n次。在这种情况下，算法所需的运行时间最长，这就是最坏情况的时间复杂度。如果每个车次被查找的概率相等，则经过多次查找后，平均需要查找n/2次，这就是平均情况的时间复杂度。
假设有一组存储在数组array中的正整数，要求设计一个算法，求数组中的最大值与正整数d的乘积。代码清单1-1展示了这一问题的两个算法实现。函数max1(int array[], int size, int d)先对数组元素逐一乘d，再求数组中的最大元素；而函数max2 (int array[], int size, int d) 先求数组中的最大值，再将其乘d。对于任意的输入，函数max1()的运算量显然比max2()大，因为max1()多运行了第一个for循环，即多做了n−1次乘法和n次赋值。因此，在软硬件环境、问题规模、数据分布均相同的情况下，max1()的运行时间一定比max2()长，也就是说max2()的时间性能更好一些。
代码清单1-1 函数max1()与max2()的实现
int max1(int array[], int size, int d) {
int max = 0, i;
for (i = 0; i < size; ++i) array[i] *= d;
for (i = 0; i < size; ++i)
if (array[i] > max) max = array[i];
return max;
}
int max2(int array[], int size, int d) {
int max = 0, i;
for (i = 0; i < size; ++i)
if (array[i] > max) max = array[i];
return max * d;
} 从上述讨论明显看出，评价算法的性能时并不需要计算精确的运算时间，只要能反映求解相同问题的不同算法的运算量之间的差异即可。通常的做法如下：
（1）选择一种或几种简单语句作为标准操作，将标准操作作为一个运算单位；
（2）确定每个算法在给定的输入下共执行了多少次标准操作，将该数值作为算法的运算量。
对于代码清单1-1中的例子，如果选择乘法、赋值和条件判断作为标准操作，则当输入的数组值为1,3,5，且d=10时，max1()执行了3次乘法（第一个for循环体）、14次赋值（第一个for循环的循环控制行中的i = 0、++i分别执行了1次、3次赋值，循环体也执行了3次赋值；第二个for循环也一样）、11次比较（第一个和第二个for循环体的循环控制行中的i < size均执行了4次；for循环体执行了3次），共28次标准操作。同样，max2()执行了1次乘法、7次赋值、7次比较，共15次标准操作。显然，max2()的时间性能优于max1()。
如何计算一个算法随问题规模变化的运算量？先来分析一下max1()在最坏情况下的运算量。假设数据规模为n，首先看第一个for循环。在循环控制行中，i = 0执行1次，i < size执行n+1次，++i执行n次。循环体执行n次，在每个循环周期中执行1次乘法、1次赋值。因此第一个for循环体总的运算量为1+(n+1)+n+n×2 = 4n+2。再来看第二个for循环体。在循环控制行中，i = 0执行了1次，i < size执行了n+1次，++i执行了n次，循环体执行1次比较，在最坏情况下，还要执行1次赋值。因此，第二个for循环体的总运算量为1+(n+1)+n+n×2 = 4n+2。max1()在最坏情况下的总运算量是8n+4。同理，可找出最好情况下运算量与问题规模之间的关系。
一般来说，算法的运行时间函数是一个很复杂的函数，而且求解同一问题的算法也不止一种，自然相应的运行时间函数也不一样。那么，如何比较不同算法的运行时间函数，并选择一个好的算法解决特定问题呢？这项工作不是那么简单。
运行时间与数据规模有关，例如对于两个算法f1和f2，其运行时间函数分别为T1(n) = n2+ 225和T2(n) = 2n2。当n<15时，T1(n)>T2(n)，即算法f1的运行时间函数值比f2大；当n>15时，T1(n)<T2(n)，即算法f1的运行时间函数值比f2小，那么到底是算法f1好还是算法f2好？
当问题规模很小时，运行时间不会影响算法的时间性能。算法的时间性能主要考虑问题规模很大时，运行时间随问题规模的变化趋势。因此，问题规模较小时，运行时间可以忽略不计，只考虑问题规模大到一定程度后的情况。例如上述算法f1和f2，我们认为算法f1的时间性能优于f2的时间性能。因为当n>15时，算法f2的运行时间函数值总是大于算法f1的运行时间函数值。
当问题规模很大时，算法的运行时间函数也会出现很多形式，此时又如何衡量算法的优劣呢？这个问题比上一个问题更复杂，这里略做简化，不考虑具体的运行时间函数，只考虑运行时间函数的数量级。这种方法称为渐近表示法。最常用的渐近表示法是大O表示法。
定义1-1 （大O表示法）如果存在两个正常数c和N0，使得当n≥N0时有T(n)≤cF(n)，则记为T(n)=O(F(n))。
例1-1 设T(n)=(n+1)2。当N0=1及c=4时，T(n)≤cn2成立。因此，T(n)=O(n2)。
例1-2 设T(n)=2n3+3n2。当N0=0及c=5时，T(n)≤cn3成立。因此，T(n)=O(n3)。
大O表示法给出了算法运行时间随数据规模增长的上界，亦称渐近时间复杂度，简称时间复杂度。大O表示法不需要计算运行时间的精确值，只需要给出一个数量级，表示当问题规模很大时，对算法运行时间的增长影响最大的函数项（主项），忽略对问题的时间复杂度产生较小影响的低阶项。因此，在选择F(n)时，通常选择运行时间函数的最高次项，忽略低次项及系数。表1-1给出了常用的时间复杂度函数及其名称。
表1-1 常用的时间复杂度函数及其名称
| 函数 |
大O表示法 |
名称 |
|---|---|---|
| F(n)= 1 |
O(1) |
常数级 |
| F(n)= logn |
O(logn)[1] |
对数级 |
| F(n)= n |
O(n) |
线性级 |
| F(n)= nlogn |
O(nlogn) |
对数线性级 |
| F(n)= n2 |
O(n2) |
平方级 |
| F(n)= n3 |
O(n3) |
立方级 |
| F(n)= 2n |
O(2n) |
指数级 |
| F(n)= n! |
O(n!) |
指数级 |
| F(n)= nn |
O(nn) |
指数级 |
[1] 若无特殊说明，本书中的log均表示以2为底数的对数。
表1-1中的常数级时间复杂度表示算法的运行时间与问题规模无关，无论问题规模怎样，算法总是执行有限个标准操作。
时间复杂度为多项式的算法称为多项式时间算法，时间复杂度为指数函数的算法称为指数时间算法。最常见的多项式时间算法的时间复杂度之间的关系为O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)，即时间复杂度为O(1)的算法是最好的算法，其次是时间复杂度为O(logn)的算法。指数时间算法的时间复杂度之间的关系为O(2n) < O(n!) < O(nn)。多项式时间算法要比指数时间算法好。
从大O表示法的定义（定义1-1）可以看出，大O表示法只是表示算法运行时间函数的上界，并没有考虑这个函数与上界的接近程度。在实际计算时，应选择算法运行时间函数的最小上界。
为了更精确地表示算法的时间性能，算法分析领域还定义了其他3种与大O表示法相关的时间复杂度的渐进表示法，而且本书后续章节偶尔会用到这几种方法。
定义1-2 （大Ω表示法）如果存在两个正常数c和N0，使得当n≥N0时有T(n)≥cF(n)，则记为T(n)=Ω(F(n))。
定义1-3 （大Ө表示法）当且仅当T(n)=O(F(n))，且T(n)=Ω(F(n))，则记为T(n)=Ө(F(n))。
定义1-4 （小o表示法）当且仅当T(n)=O(F(n))，且T(n)≠Ө(F(n))，则记为T(n)=o(F(n))。
大O表示法说明T(n)的增长率小于或等于F(n)的增长率，即F(n)为T(n)的上界。大Ω表示法说明T(n)的增长率大于或等于F(n)的增长率，即F(n)为T(n)的下界。大Ө表示法说明T(n)的增长率等于F(n)的增长率，即T(n)的上界与下界相等。小o表示法说明T(n)的增长率严格小于F(n)的增长率，即T(n)的上界与下界不等。
算法的时间复杂度的计算可以按照代码清单1-1的分析方法，首先定义算法的标准操作，然后计算算法的标准操作次数，这样就可以得到一个随问题规模变化的标准操作次数的函数。最后取出函数的主项，作为其时间复杂度的大O表示。但这种计算方法比较烦琐，下面将介绍一些时间复杂度的简化计算方法。我们先引入两个常用定理。
定理1-1 求和定理：假定T1(n)、T2(n)分别是程序P1、P2的运行时间函数，且T1(n)属于O(f(n))，而T2(n)属于O(g(n))。那么，先运行P1，再运行P2的总运行时间是T1(n)+T2(n)=O(MAX(f(n), g(n)))。
证明：根据定义1-1，对于某些正常数c1、n1及c2、n2，根据已知条件，可得：
当n≥n1时，T1(n)≤c1f(n)成立；
当n≥n2时，T2(n)≤c2g(n)成立。
设n1和n2之间的最大值为n0，即n0=MAX(n1, n2)。
那么，当n≥n0时，T1(n)+T2(n)≤c1f(n)+c2g(n)成立。因此，T1(n)+T2(n)≤(c1+c2)MAX(f(n), g(n))。于是，定理得证。
定理1-2 求积定理：如果T1(n)和T2(n)分别属于O(f(n))和O(g(n))，那么T1(n)×T2(n)属于O(f(n)×g(n))。
证明：根据已知条件，当n≥n1时，T1(n)≤c1f(n)成立。当n≥n2时，T2(n)≤c2g(n)成立。其中c1、n1及c2、n2都是正常数。因此，当n≥MAX(n1,n2)时，T1(n)×T2(n)≤c1c2f(n)g(n)，说明T1(n)×T2(n)属于O(f(n)×g(n))。
定理1-1和定理1-2为时间复杂度的计算提供了很大便利。由这两个定理可以得到以下5条简化的计算规则。
规则1。每个简单语句，如赋值语句、输入/输出语句，它们的运行时间与问题规模无关，在每个计算机系统中的运行时间都是一个常量，因此时间复杂度为O(1)。
规则2。对于条件语句，if <条件> then <语句> else <语句>的运行时间为进行条件判断的代价，时间复杂度一般为O(1)，再加上运行then后面的语句的代价（若条件为真），或运行else后面的语句的代价（若条件为假），时间复杂度为MAX(O(then子句), O(else子句))。
规则3。对于循环语句，运行时间是循环控制行和循环体运行时间的总和。循环控制行的作用一般是进行一个简单的条件判断，不会占用大量的时间，因此时间复杂度为O(循环次数×O(循环体))。
规则4。对于嵌套循环语句，在外层循环的每个循环周期，内层循环都要运行它的所有循环周期，因此，可用求积定理计算整个嵌套循环语句的时间复杂度，即时间复杂度为O(O(内层循环体)×外层循环的循环次数)。例如，以下程序
for (i=0; i<n; i++)
for (j=0; j<n; j++)
for (k=0; k<n; k++) s++;的时间复杂度为O(n3)。
规则5。连续语句的时间复杂度是利用求和定理把这些连续语句的时间复杂度相加而得到的。例如，以下程序
for (i=0; i<n; i++) a[i]=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++) a[i]= i+j;由两个连续的循环组成。第一个循环的时间复杂度为O(n)，第二个循环的时间复杂度为O(n2)。根据求和定理，整个程序的时间复杂度为O(n2)。
有了这些简化的计算规则后，计算算法的时间复杂度就简单了。没有必要像分析max1()的时间性能那样统计所有标准操作的次数，而只需要找出最复杂、运行时间最长的程序段。在max1()中，最复杂的程序段是两个循环，这两个循环的时间复杂度都为O(n)，因此整个程序的时间复杂度是O(n)。
与时间复杂度类似，算法的空间复杂度也常用大O表示法计算。一个算法在运行过程中需要占用大小不等的存储空间，包括算法本身占用的存储空间、输入/输出数据占用的存储空间和辅助空间（算法实现所需的额外存储空间）。空间复杂度仅对算法运行过程中所占用的辅助空间进行度量，即算法所需的辅助空间和问题规模之间的关系函数，记为S(n)，然后得到其数量级。空间复杂度通常也是按最坏情况计算的。
1.4 算法优化本节通过一个实例详细介绍算法优化的过程。
例1-3 最大连续子序列和的问题：给定（可能是负的）整数序列{A1,A2,…,AN}，寻找（并标识）使
的值最大的连续子序列。如果所有整数都是负的，那么最大连续子序列的和是0。
例如，假设输入是{−1,12,−5,13,−6,3}，则最大连续子序列的和是20，最大连续子序列包含第2项到第4项（如粗体字部分所示）。又如，对于输入{1,−3,4,−2,−1,6}，则最大连续子序列的和是7，最大连续子序列包含最后4项（如粗体字部分所示）。
选用最大连续子序列和的问题作为本节实例，是因为有很多种算法可以解决这个问题，而且这些算法的时间复杂度相差很大。本节将讨论4个算法。第一个算法是时间复杂度为O(n3)的算法，采用枚举法，效率很低。第二个算法是时间复杂度为O(n2)的算法，它对第一个算法做了改进。第三个算法是时间复杂度为O(n log n)的算法，它采用分治法。最后一个算法是时间复杂度为O(n)的算法，效率很高，但不易想到，也不易理解。
最大连续子序列和：枚举算法O(n3)
最简单、最暴力的算法是枚举法，即一一罗列所有可能的连续子序列，从中找出和值最大的连续子序列，如代码清单1-2所示。maxSubsequenceSum(int a[], int size, int &start, int &end)函数的输入参数为一个待查找的数组a、数组的大小size，输出参数是最大连续子序列的起始位置start、最大连续子序列的终止位置end，返回值为最大连续子序列的和maxSum。程序的主体是一对用来遍历所有可能的连续子序列的循环。循环变量i控制连续子序列的起始位置，循环变量j控制连续子序列的终止位置。对于每个可能的连续子序列，用一个循环变量为k的计数循环计算其和。如果当前连续子序列之和大于目前所遇到的最大连续子序列之和，则更新maxSum、start和end的值。结束循环后，返回maxSum。
代码清单1-2 最大连续子序列和的枚举算法
int maxSubsequenceSum(int a[], int size, int &start, int &end) {
int maxSum = 0; // 当前的最大连续子序列之和
for (int i = 0; i < size; i++) // 子序列的起始位置
for (int j = i; j < size; j++) { // 子序列的终止位置
int thisSum = 0;
for (int k = i; k <= j; k++) // 求从i开始到j结束的序列之和
thisSum += a[k];
if (thisSum > maxSum) { // 找到一个更好的序列
maxSum = thisSum;
start = i;
end = j;
}
}
return maxSum;
} 这个算法的实现原理非常简单。一个算法越简单，被正确编程的可能性就越大。然而，枚举法通常效率不够高，这个算法的时间复杂度是O(n3)。
根据求积定理可以看出，这个算法的运行时间完全由循环变量为i的for循环确定。如果输入的序列长度为n，则该循环的循环体被运行n次。该循环的内层循环体也是一个for循环（循环变量为j的循环），被运行n−i次。循环变量为j的for循环是一个复合语句，它由一个赋值语句、一个循环变量为k的循环语句和一个条件语句组成。根据求和定理，该循环体的时间复杂度为循环变量为k的循环语句的时间复杂度。根据规则4，可得代码清单1-2的时间复杂度为
，属于O(n3)。
一个有3层嵌套循环的程序，每个循环的运行都有可能处理大部分数组元素，则该程序的时间复杂度为O(n3)。正是嵌套导致了组合爆炸，为了改进这个算法，需要删除一层循环。
最大连续子序列和：改进算法O(n2)
从嵌套循环算法中删除一层循环，通常可以减少算法的运行时间。那么，怎样删除一层循环呢？答案是，不一定总能删除。例如，代码清单1-2中的算法有一些不必要的计算。在计算第i到第j+1个元素的和时，算法用了一个循环。事实上，在上一次循环计算从第i到第j个元素的和时，已经得到了第i到第j个元素的连续子序列和。而
，因此，只需要再做一次加法即可。利用这一结果，将代码清单1-2中最内层的循环用一个加法替代，就得到了代码清单1-3所示的改进算法。
代码清单1-3 最大连续子序列和的O(n2)两重循环算法
int maxSubsequenceSum(int a[], int size, int &start, int &end) {
int maxSum = 0; // 已知的最大连续子序列之和
for (int i = 0; i < size; i++) { // 连续子序列的起始位置
int thisSum = 0; // 从i开始的连续子序列之和
for (int j = i; j < size; j++) { // 连续子序列的终止位置
thisSum += a[j]; // 计算从第i到第j个元素的连续子序列之和
if (thisSum > maxSum) {
maxSum = thisSum;
start = i;
end = j;
}
}
}
return maxSum;
} 代码清单1-3所示的O(n2)算法有一个两重循环而不是三重循环，时间复杂度是O(n2)。
最大连续子序列和：改进算法O(nlogn)
最大连续子序列和的问题还可以用分治法解决。假设输入的整数序列是{4,−3,5,−2,−1,2,6,−2}，这个输入可以被划分成两部分，即前4个元素和后4个元素。这样使和值最大的连续子序列可能出现在下面3种情况中。
情况1：使和值最大的连续子序列位于前半部分。
情况2：使和值最大的连续子序列位于后半部分。
情况3：使和值最大的连续子序列从前半部分开始但在后半部分结束。
这3种情况中，使和值最大的连续子序列就是本问题的解。
前两种情况下，只需要在前半部分或后半部分找最大连续子序列，这通过递归调用就可以解决。问题是第三种情况下怎么办？可以从前后两部分的边界开始，通过从右到左的扫描找到左半段的最大连续子序列；类似地，通过从左到右的扫描找到右半段的最大连续子序列。把这两个连续子序列组合起来，形成跨越中点的最大连续子序列。在上述输入的整数序列中，通过从右到左扫描得到左半段的最大连续子序列和是4，包括前半部分的所有元素。从左到右扫描得到的右半段的最大连续子序列和是7，包括−1、2和6这3个元素。因此，从前半部分开始但在后半部分结束的最大连续子序列和为4+7=11，使和值最大的连续子序列是{4,−3,5,−2,−1,2,6}。
总结一下，用分治法解决最大连续子序列和问题的算法包括4个步骤。
（1）递归地计算位于前半部分的最大连续子序列。
（2）递归地计算位于后半部分的最大连续子序列。
（3）通过循环查找以左半段某处为起点，以中点为终点的连续子序列和的最大值，以及以中点为起点，以右半段某个位置为终点的连续子序列和的最大值，计算从前半部分开始但在后半部分结束的最大连续子序列的和。
（4）选择上述3个步骤中得出的使和值最大的连续子序列，作为整个问题的解。
根据此算法，可编写代码清单1-4所示的程序。由于此方案采用了递归算法，所以函数包含控制递归的参数left和right。这个函数原型与前文所用的原型不同，在实际应用时并不需要传入left和right的值，所以需要定义一个包裹函数。
代码清单1-4 最大连续子序列和的O(n log n)递归算法
// 递归解决方案
int maxSum(int a[], int left, int right, int &start, int &end) {
int maxLeft, maxRight, center;
// maxLeft和maxRight分别为前半部分、后半部分的最大连续子序列和
int leftSum = 0, rightSum = 0; // 情况3中，左、右半段的连续子序列和
int maxLeftTmp = 0,
maxRightTmp = 0; // 情况3中，左、右半段的最大连续子序列和
int startL, startR, endL,
endR; // 前半部分、后半部分的最大连续子序列的起点和终点
if (left == right) { // 仅有一个元素，递归终止
start = end = left;
return a[left] > 0 ? a[left] : 0;
}
center = (left + right) / 2;
// 找前半部分的最大连续子序列和
maxLeft = maxSum(a, left, center, startL, endL);
// 找后半部分的最大连续子序列和
maxRight = maxSum(a, center + 1, right, startR, endR);
// 找从前半部分开始但在后半部分结束的最大连续子序列
start = center;
for (int i = center; i >= left; --i) {
leftSum += a[i];
if (leftSum > maxLeftTmp) {
maxLeftTmp = leftSum;
start = i;
}
}
end = center + 1;
for (int i = center + 1; i <= right; ++i) {
rightSum += a[i];
if (rightSum > maxRightTmp) {
maxRightTmp = rightSum;
end = i;
}
}
// 找3种情况中的最大连续子序列和
if (maxLeft > maxRight)
if (maxLeft > maxLeftTmp + maxRightTmp) {
start = startL;
end = endL;
return maxLeft;
} else
return maxLeftTmp + maxRightTmp;
else if (maxRight > maxLeftTmp + maxRightTmp) {
start = startR;
end = endR;
return maxRight;
} else
return maxLeftTmp + maxRightTmp;
}
// 包裹函数
int maxSubsequenceSum(int a[], int size, int &start, int &end) {
return maxSum(a, 0, size - 1, start, end);
} 代码清单1-4的时间复杂度是O(n log n)。递归函数的时间复杂度的计算较为复杂，本书将在7.5.2节和7.6节介绍递归函数时间复杂度的计算。
最大连续子序列和：改进算法O(n)
最大连续子序列和问题的算法还可以继续优化。进一步观察代码清单1-3所示的两重循环算法，如果能再删除一个循环，就可以得到一个线性算法。然而，从代码清单1-2到代码清单1-3删除循环很简单，但要再删除另一个循环就不那么容易了。这个问题的关键在于平方级算法仍然是一种枚举法，也就是说，还是尝试了所有可能的子序列。平方级算法和立方级算法唯一的不同就是计算每个最大连续子序列和的时间复杂度是常量O(1)而不是线性的O(n)。因为序列具有平方数目的连续子序列数，所以得到一个线性算法的唯一方法就是找出一个聪明的方法排除对很多连续子序列的考虑，而不用真正计算所有连续子序列的和值。
我们可以通过分析来排除很多可能的连续子序列。如果一个连续子序列的和是负的，则它不可能是最大连续子序列的开始部分，因为可以通过不包含它得到一个连续子序列和值更大的连续子序列。例如，{−2,11,−4,13,−5,2}的最大连续子序列不可能从−2开始，{1,−3,4,−2,−1,6}的最大连续子序列不可能包含{1,−3}。所有与最大连续子序列毗邻的连续子序列一定有负的和值或0和值。因此，在代码清单1-5中，当检测出一个负的连续子序列和时，不但可以从内层循环中跳出来，还可以让i直接增加到j+1。例如，对于{1,−3,4,−2,−1,6}，当检测序列{1,−3}后，发现连续子序列和是负值，则该子序列不可能包含在最大连续子序列中，接下来i就可以从4开始检测。使用这种方法，只需要顺序检查一遍序列中的元素。根据该思想实现的算法如代码清单1-5所示。
代码清单1-5 最大连续子序列和的线性算法
int maxSubsequenceSum(int a[], int size, int &start, int &end) {
int maxSum, starttmp, thisSum;
start = end = maxSum = starttmp = thisSum = 0;
for (int j = 0; j < size; ++j) {
thisSum += a[j];
if (thisSum <= 0) { // 排除前面的连续子序列
thisSum = 0;
starttmp = j + 1;
} else if (thisSum > maxSum) { // 找到一个连续子序列和更大的连续子序列
maxSum = thisSum;
start = starttmp;
end = j;
}
}
return maxSum;
} 代码清单1-5只使用了一个最多重复n次的循环，显然这个算法的运行时间是线性的。这个循环体最多重复运行n次，而循环体中语句的运行次数是常数级的，与问题规模无关。因此时间复杂度是O(n)。但与前面几个算法相比，这个算法读起来不那么方便，也就是说，牺牲了易读性换取了时间！
1.5 大型应用实现：火车票管理系统总览大型应用实现：总览
本书将以1.1节介绍的火车票管理系统作为大型应用，贯穿全书所有章节，每章首先介绍数据结构的基本概念，然后讲解该大型应用中与该章数据结构内容相关的具体实现。
针对火车票管理系统的数据特点及管理要求，为每一类数据选择合适的数据结构，并采用面向对象的程序设计方法，把对每一类数据的管理封装成一个类，供应用系统使用。
根据1.1节火车票管理系统的需求分析（如图1-1所示）与系统构成（如图1-2所示），下面将以数据为中心描述火车票管理系统的类及其对应的数据结构与所属章节，按照数据的生成、使用与消亡过程依次介绍其管理类。
列车运行图类RailwayGraph管理整个列车运行计划所包含的运行线路图，提供站点可达性查询、途经站点查询和最优路线查询功能，这3种查询统称路线查询。列车运行图信息与列车运行计划的添加有关，如图1-4所示。该类涉及的并查集、图的存储与搜索、最短路径等内容将分别在第5章、第9章、第10章中介绍。
图1-4 列车运行图类RailwayGraph
列车运行计划管理类TrainScheduler管理所有列车的运行计划，包括车次号、额定乘员、途经站点、历时、票价等车次基本信息，提供列车运行计划的添加与查询功能。列车运行计划信息也与车票的发售与停售有关，如图1-5所示。该类涉及的线性表等内容将在第2章中介绍。
图1-5 列车运行计划管理类TrainScheduler
余票管理类TicketManager管理每一段线路的余票信息，提供车票发售与停售、购票、退票、余票查询功能，如图1-6所示。该类涉及的B+树等内容将在第8章中介绍。
行程管理类TripManager管理所有旅客的行程，行程信息受到旅客购票和退票交易的影响。该类为每个旅客提供已购车票查询功能，如图1-7所示。该类涉及的B+树等内容也将在第8章中介绍。
图1-6 余票管理类TicketManager
排队交易类WaitingList与PrioritizedWaitingList管理所有待交易车票的信息，处理普通或特殊旅客的排队购票及退票请求，如图1-8所示。该类涉及的队列与优先级队列等内容将分别在第3章、第4章中介绍。
图1-7 行程管理类TripManager
图1-8 排队交易类WaitingList与PrioritizedWaitingList
旅客管理类UserManager管理所有旅客的信息，提供旅客信息的查询、添加与修改功能，该类在旅客的购票和退票交易时将被用到，如图1-9所示。该类涉及的红黑树等内容将在第6章中介绍。
图1-9 旅客管理类UserManager
本节概述了火车票管理系统中列车运行图、列车运行计划管理、余票管理、行程管理、排队交易、旅客管理等6个类，后续章节将逐一详细讲解并用C++语言实现。在学习过程中，读者可以尝试编译和运行书中的示例代码，以进一步探索和练习。有关环境配置和项目构建的更多信息详见附录B。
1.6 小结本章主要介绍了数据结构及算法分析两个重要概念。
数据结构是一组具有特定关系的同类数据元素的集合，其主要研究数据的逻辑结构、数据的存储结构，以及数据的操作定义和操作实现。数据的逻辑结构包括集合、线性结构、树形结构和图形结构。数据的存储结构包括顺序存储、链接存储、索引存储及哈希存储。数据的操作包括操作定义和操作实现。
算法分析是对一个算法的时间复杂度和空间复杂度进行定量分析，从而衡量算法的优劣。算法分析时，通常采用渐近表示法分析算法的时间复杂度的增长趋势。
本书将火车票管理系统作为大型应用贯穿全书，并在相关章节叙述其实现。
1.7 习题（1）什么是算法的时间复杂度和空间复杂度？
（2）什么是数据结构？
（3）数据结构在火车票管理系统中起到什么作用？
（4）算法的优劣可以用哪几个指标衡量？
（5）在递归实现分治法时，为什么要定义包裹函数？
（6）设计一个函数，计算S=1−2+3−4+5−6+…+(−1)n−1×n的值，要求时间复杂度为O(1)。
（7）给出下列代码时间复杂度的大O表示。
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
sum++; （8）在面向对象的数据结构中，用类来封装一种数据结构有什么好处？
（9）请设计一个算法，判断整数N是否是素数，并分析其时间复杂度的大O表示。
（10）试说明下列数据集合中数据元素的逻辑关系。
1）列车站点中排队等候上车的乘客。
2）公园里的游客。
3）某人通讯录中的人员。
（11）下列与计算机相关的技术中，数据元素的逻辑结构分别是什么？
1）面向对象程序设计中，通过单继承形成的所有类。
2）面向对象程序设计中，通过多继承形成的所有类。
3）计算机中的文件和文件夹。
