数据结构与算法及其航空航天应用（C语言版）（项目式微课版）

版权信息

书名：数据结构与算法及其航空航天应用（C语言版）（项目式微课版）

ISBN：978-7-115-66296-5

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版  权

主  编 赵学武 车 葵 赵 妍

副 主 编 李玲玲 赵雪专

责任编辑 贾鸿飞

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内容提要

本书系统地讲解数据结构与算法设计的相关知识，共分两部分。第1部分讲解数据结构的主要内容，包括数据结构概述、线性表、栈与队列、串、数组和广义表、树、图、查找与排序等，还包括航空航天应用实例的分析与实现。第2部分重点阐述典型的算法设计方法，包括算法概述、递归与分治、动态规划、贪心算法、回溯法、分支限界法等，并对这些算法的设计策略进行了比较，最后讲解航空航天应用案例分析与算法设计。

本书适合理工类相关专业的本科生和研究生阅读，也适合从事数据挖掘、机器学习研究、算法设计与分析等工作的相关人员阅读。

前  言

当前，以信息技术为核心的新一轮科技革命正深刻影响着人们生产、生活的方式。新业态和新需求呼唤新软件的出现。高效开发高质量的软件，需要遵循软件工程的原则。编写能高效运行的代码需要具备良好的编程技巧，更需要能设计合理有效的数据组织方式和高效实用的算法，这正是计算机领域数据结构与算法所研究的主要内容。

本书的编写思路是将数据结构/问题模型化、问题求解算法化，在介绍数据结构的基础上，讲解典型的算法设计策略的理论，分析算法的实际应用。本书特点如下。

（1）数据结构与算法设计有机融合。

（2）示例丰富，重视应用。

（3）强调动手能力和实践能力的培养。

（4）应用实例面向航空航天新兴战略领域。

本书采用C语言和类C语言作为数据结构和算法设计的描述工具。为了便于读者学习和掌握，本书安排了很多应用实例尤其是航空航天实例，并提供了丰富的习题。需要说明的是，为了节省篇幅，也为了让读者节约手动输入代码的时间，本书部分代码放在了电子文件中，读者可以扫描正文中相应位置的二维码进行下载。

本书由赵学武、车葵、赵妍主编，李玲玲和赵雪专副主编，赵学武负责全书的统稿工作。

本书在编写过程中参阅了大量的书籍、文献、网络等资料，特别是百度文库中的相关试题和课件等资源给予编者良好的启发，研究生李家乐和许景阳同学协助整理相关的图片。本书的编写和出版，得到了河南省战略性新兴领域“十四五”高等教育教材建设团队项目的资助。在此一并表示衷心的感谢。

本书是编写组多年教学经验的总结和体现，尽管编者不遗余力，但由于时间仓促和水平所限，难免存在不足和疏漏之处，恳请读者批评指正，以便使本书得以改进和完善。

本书是河南省战略性新兴领域“十四五”高等教育教材建设团队教材和河南省“十四五”普通高等教育规划教材。

本书受软件工程河南省新一轮重点学科、河南省高等教育教学改革研究与实践项目（项目编号：2024SJGLX0149）、河南省高等教育教学改革研究与实践项目（研究生教育类）（项目编号：2023SJGLX325Y）、河南省研究生教育改革与质量提升工程项目（项目号：YJS2024JD48）、河南省高等学校重点科研项目计划（25A0002，24A520052）、河南省通航技术重点实验室、中原创新领军人才项目（254000510017）、河南省重点研发专项（231111212000）、河南省杰出外籍科学家工作室项目（GZS2022011）、河南省本科高校产教融合示范学院（航空航天信息产业学院）、航空航天电子信息技术河南省协同创新中心、航空航天智能工程河南省特需急需特色骨干学科群、郑州航院研究生质量提升工程项目——研究生精品教材项目（项目编号：2024YJSJC06）、郑州航院教育教学改革研究与实践项目（项目编号：zhjy24——（68））、郑州航院研究生教育教学改革与发展研究项目（2025YJSJG49）资助。

编 者

2025年6月

第1部分 数据结构

第1章 数据结构概述

数据结构（data structure）是计算机科学与技术专业及相关专业的一门重要专业必修课，它主要研究各种数据类型的组织方式、操作方式和存储方式。学习数据结构知识有助于养成良好的程序设计能力和熟练的算法分析能力。

本章主要介绍了数据结构的基本概念、数据结构的内容、算法基础，以及如何学习和运用数据结构与算法。通过本章的学习，读者能对数据结构有初步的了解。

1.1　数据结构的基本概念

1.1.1　什么是数据结构

在计算机科学界，数据结构并没有标准的定义。根据个人理解的不同而有不同的表述方法。克利福德·A.谢弗（Clifford A.Shaffer）在《数据结构与算法分析》一书中的定义：数据结构是抽象数据类型（abstract data type，ADT）的物理实现。洛贝特·L. 克鲁泽（Lobert L.Kruse）在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的逻辑表示和在计算机内的存储细节以及运算的实现。

简而言之，数据结构就是相互之间存在一种或多种特定关系的数据元素的集合，其中包括数据对象以及定义在这组数据对象上的特定关系。

在计算机程序中，数据是以整数、浮点数、字符串、数组等各种不同类型存储的，而且不同类型的数据有不同的特点和操作方式。数据结构的目标就是将这些数据按照一定的方式进行组织，以方便程序操作。因此，要设计一个结构好﹑效率高的程序，必须研究数据的特性、数据间的相互关系以及对应的存储表示，并利用这些特性和关系设计相应的算法和程序。

1.1.2　基本概念与术语

1．数据、数据元素和数据项

数据是所有能输入计算机中并被计算机程序加工、处理的符号集合，在计算机科学中指计算机操作的对象。数据可以是整型、字符型等数值类型，也可以是音频、图片、视频等非数值类型。例如，机票预订网站上某个航空班次的乘客数量、价格可以是数值型数据，而该航班的图片、实时飞行动态是非数值型数据。

数据元素是数据的基本单位，在不同的数据结构中也称为记录、节点或顶点等。数据元素是一种抽象的概念，并没有具体的数值化标准。例如，在机票预订网站中可以把一个班次看作是一个数据元素，也可以把一个乘客看作是一个数据元素。在计算机程序中数据元素通常是作为一个整体进行分析和处理的。

数据元素由数据项组成，数据项是数据不可分割的最小单位，一个数据元素可由一个或多个数据项组成。例如，数据元素航空班次（航班号，航空公司，乘客数量，出发地，目的地，票价）由数据项“航班号”“航空公司”“乘客数量”“出发地”“目的地”“票价”组成。数据项也可以称为字段或域，是对元素的详细描述，所以，也可以说数据元素航空班次有“航班号”“航空公司”“乘客数量”“出发地”“目的地”“票价”6个字段。

2．数据对象

数据对象是具有相同性质的数据元素组成的集合，也是数据的子集。例如，每一个乘客都有姓名、年龄、性别、出生地址这些数据项。在具体问题中，性质相同的数据元素的值不一定相同，但都是数据对象集合中的成员。处理相同性质的数据元素时，默认将数据对象简称为数据。也就是说，“数据”在数据结构这一课题中默认代指数据对象。

数据项、数据元素、数据对象之间的关系是什么呢？一个数据元素是由若干相关的数据项构成的，一个数据对象是由相关的数据元素构成的。它们三者是被包含与包含的关系。数据项、数据元素、数据对象是数据逻辑结构的层次单位，也是数据存储结构的层次单位。

3．数据类型和抽象数据类型

数据类型是一个值的集合以及定义在这个值集上的一组操作。其含义包括以下两点：①值的集合，集合里的数据具有相同的类型；②一组操作的集合，这组操作是作用在值的集合上的。因此也可以说它（数据类型）包括数据对象以及在数据对象上的操作。在高级程序设计语言中，数据类型用来描述数据对象的特性，定义的常量、变量等都有不同的数据类型。

通常情况下，可以将数据类型按其“值”的特性划分成原子类型和结构类型。对于原子类型，顾名思义是指其值不可分解，原子类型也称为基本类型，例如整型、字符型、浮点型、布尔类型等。对于结构类型，其值由若干个用户自己定义的分量组成，例如数组、结构体等类型。

研究数据元素之间的逻辑关系就是研究数据的逻辑结构。ADT是指描述数据的逻辑结构以及在这些逻辑结构上的一组操作。抽象数据类型的定义取决于它的逻辑特性，与其在计算机内部的表示和实现无关。也就是说，只要抽象数据类型的数学特性不变，其内部的变化就不会影响外部的使用。

抽象数据类型的定义，可以采用三元组来(D,R,P)表示。其中D表示的是数据对象，R表示D上的关系集合，P表示对D的基本操作集合。其基本格式描述如下。

ADT Name{
    Data Object：数据对象的定义
    Data Relationship：数据关系的定义
    Basic Operation：基本操作的定义
}ADT NAME

基本操作的定义格式如下。

Basic Operation Name(Parameters)
    Initial Condition：初始条件描述
    Operation Results：操作结果描述

基本操作的参数有两种：一种是赋值参数，为操作提供输入值；另一种是引用参数，以符号&开头，可以提供输入值，同时还返回操作结果。

初始条件用于描述操作执行前数据结构和参数满足的条件，如果不满足，则操作失败并返回相应的出错信息；如果初始条件为空，则可以省略。

操作结果用于说明操作正常完成之后，数据结构的变化状况和应该返回的结果。

就实质而言，抽象数据类型和数据类型是一个概念，但是其含义比一般数据类型更广泛、更抽象。二者的区别在于数据类型是高级程序设计语言支持的基本数据类型，而抽象数据类型是用户自定义的数据类型。抽象数据类型只定义数据的逻辑结构和操作说明，不考虑存储结构和具体实现。

4．数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，可以使用一个公式形象地表示：数据结构=(D,R)，其中D={数据元素}，R={D上的关系}。例如，复数可被定义为一种数据结构Complex=(D,R)。其中，D={x|x是实数}，R={<x，y> | x，y∈D，x称为实部，y称为虚部}。可见，数据结构是计算机存储和组织数据的一种方式，因此，数据结构会影响数据的存储和检索效率。

1.2　数据结构的内容

数据结构的内容包含逻辑结构、存储结构和运算三个方面。

逻辑结构指的是数据元素之间的逻辑关系；存储结构指的是数据的逻辑结构如何在计算机的存储器里表示和实现，也称为物理结构；运算在选择了数据结构的存储结构之后就可以实现，不同存储结构的运算性能可能存在一定的差异。

运算在数据的逻辑结构上定义时，描述的是“做什么”；在数据的存储结构上实现时，描述的是“如何做”。运算的实现就是通常所说的算法。算法的设计取决于数据的逻辑结构，算法的实现依赖于指定的物理结构。

1.2.1　数据的逻辑结构

按照数据元素之间关系的不同特性，通常可以将数据的逻辑结构分为集合结构、线性结构、树形结构和图形结构四种类型。

1．集合结构

集合结构中的数据元素除了同属一个集合外，没有其他关系，各个元素是“平等”的，元素顺序是随意的，每个元素在集合中都是唯一的，该结构类似于数学中的集合，如图 1.1所示。

图1.1　集合结构

2．线性结构

线性结构中的每个数据元素都可以看作一个节点，数据元素之间是一对一的关系，即除了第一个元素外，每个元素有唯一的前驱；除了最后一个元素外，每个元素有唯一的后继。如图 1.2 所示。生活中的城市公交路线类是典型的线性结构，其中站点就是数据元素，每一条公交线路都有一个起点和终点，中间各站按先后次序排列。

图1.2　线性结构

逻辑上，具有这种线性的数据结构也称为线性表。表 1.1 航空客户信息表就是线性结构，每个数据元素由会员卡号、入会时间、第一次飞行日期、性别、年龄、观测窗口结束时间、窗口内的飞行次数、总基本积分等数据项组成。

表1.1　航空客户信息表

3．树形结构

树形结构中的数据元素之间存在一对多的层次关系，或是分支关系。一个节点可能包含子节点，也可能不包含。没有子节点的节点称为叶子节点。此外，树形结构有一个特殊的节点，称为根节点，它是整棵树的起点。从根节点出发，可以到达树中的任何其他节点，如图 1.3所示。

图1.3 树形结构

在实际应用中，一所学校的组织架构类似于树形结构，如图 1.4所示。树根为学校，学校的下一层对应各个学院，各学院下有各个系。因此，学校架构可被抽象成树形结构来进行数据管理。

图1.4　学校的树形架构

4．图形结构

图形结构中的数据元素之间存在着多对多的网络关系，数据元素也称为顶点，顶点与顶点之间存在着复杂的网络关系，所以图形结构也称为网状结构，如图1.5所示。

图1.5　图形结构

航空公司的飞行线路图类似于上述结构，如图1.6所示。每一个城市都是一个数据元素，飞行线路是元素之间的关系，一个城市机场可与多个城市通过飞行线路相连，多个城市连接成网状。

图1.6　航空线路图

1.2.2　数据的物理结构

从逻辑关系上来观察数据，它与数据的存储无关，是独立于计算机的。数据的物理结构则是逻辑结构在计算机存储器里的实现，是依赖于计算机的。

计算机的存储器由有限个存储单元组成，每个存储单元有唯一的地址，各地址是连续编码的。一片相邻的存储单元的整体称为存储区域。通常数据的存储结构有以下四种类型。

1．顺序存储结构

顺序存储结构按照给定数据元素的先后次序，逐一存放在连续的物理存储空间上。也就是把逻辑上相邻的节点存储在物理位置也相邻的存储单元中，如图 1.7所示。

图1.7 顺序存储结构

顺序存储结构是一种简单且易于实现的存储方式。因为在采用顺序存储结构存储数据元素时，只需要知道数据元素在物理存储空间的位置关系，就可以得到数据元素的逻辑关系。存储的过程中，不需要增加其他的存储单元来记录数据元素的逻辑关系。通常情况下，在高级程序设计语言中可以用数组来实现存储结构。当对数据元素进行访问时，可以通过数组下标直接访问相关数据元素，因此顺序存储结构是一种可以随机访问的存储方式。

顺序存储结构的缺点：一方面当处理数据量很大，即数据元素个数较多时，需要一大块连续的存储空间，有时计算机很难满足其要求；另一方面当数据元素需要进行插入和删除操作时，需要对其他的节点进行移动，这种操作会增加系统开销，增加算法的时间复杂度。

2．链式存储结构

在链式存储结构中，逻辑上相邻的数据元素可以存储在物理位置不相邻的存储单元上，如图 1.8 所示。也就是说不同的数据元素可以存储在连续的地址空间，也可以存储在不连续的地址空间。通常情况下，在高级程序设计语言中可以用指针类型来实现链式存储中对逻辑关系的描述。

图1.8 链式存储结构

链式存储结构中除了存储数据元素的这部分存储空间外，还有一部分存储空间用来存储数据元素之间的逻辑关系，即指针。由于逻辑关系相邻的元素物理位置不一定相邻，所以链式存储结构不能实现随机访问。链式存储结构的优点是容易修改，在插入、删除数据元素的操作时，只需要对相关指针进行修改，不需要像顺序存储结构一样对数据元素进行移动。

3．索引存储结构

索引存储结构通过索引表来确定数据元素的存储位置，如图1.9所示。索引表包括数据元素的关键字和存储地址，数据元素的关键字能够唯一标识数据元素，通过存储地址可以访问该存储地址上的数据元素。

图1.9　索引存储结构

索引存储结构结合了顺序存储结构和链式存储结构的优点。不但能够实现对数据元素的随机访问，而且当需要对数据进行插入、删除等操作时，只需要修改和移动索引表中的相关节点的存储地址信息，不需要移动存储空间上的数据元素。索引存储结构可以分为两种：一种是稀疏索引，一组数据元素对应一个索引项；另一种是稠密索引，每一个数据元素都对应一个索引项。

4．散列存储结构

散列存储结构将数据元素的关键字通过哈希函数转换成其存储地址，这种结构也称为哈希存储结构。这种结构适用于高速检索，效率近似于随机存取。它的基本设计思想是以数据元素的关键字K为自变量，确定一个函数关系f（称为散列函数），计算出对应的函数值f (K)，将这个值解释为数据元素的存储地址，最后将数据元素存入f (K)所指的存储位置。查找数据元素时，根据其关键字用同样的函数计算出存储地址即可。

1.2.3　数据的运算

数据和操纵数据的运算是研究数据结构不可分割的两个方面，所以我们在讨论数据结构时，不但要讨论数据的逻辑结构、存储结构，还要讨论在数据结构上执行的运算（operation）以及实现这些运算的算法（algorithm）。

数据运算就是施加于数据的操作。数据运算包括运算的定义和运算的实现，前者确定运算的功能，后者是在存储结构上确定运算的算法。

数据运算包括算术运算（加、减、乘、除）、关系运算（大于、小于、等于）、逻辑运算（与、或、非），以及指数、对数、三角函数等更复杂的运算，还包括特定数据结构的运算，如矩阵运算、集合运算等。此外，在计算机科学中，数据运算还涉及位运算、移位运算等。有时数据运算常常涉及算法问题，常见的有插入、删除、更新、查找和排序等。例如，在数组中插入新元素可能需要移动其他元素以腾出空间；在链表中插入元素则相对简单，只需要调整指针。与此相似，在数组中删除元素可能需要移动其他元素以填补空缺；在链表中删除元素通常涉及重新连接指针。在数组或链表执行更新操作中，可以通过索引或遍历找到元素后直接更新。查找运算中的线性查找需遍历整个数据结构；二分查找则适用于已排序的数组，通过不断缩小查找范围来提高效率。

解决这些问题时，需要综合考虑数据结构的特性、算法的时间复杂度和空间复杂度，以及具体的应用场景和需求。通过优化算法和数据结构，可以显著提高程序的性能和效率。

1.3　算法基础

1.3.1　算法的概念

算法这个词最早出现在波斯数学家阿勒·花刺子密（Al-Khwarizmi）在公元825年所写的《印度数字算术》中。那么，什么是算法？简单来说，算法就是针对特定问题的解决思路、方法和步骤。算法在计算机中表现为表示一个或多个操作的指令有限序列，一种算法就是将输入转换为输出的一系列计算步骤。

1.3.2　算法的特性

算法必须满足有穷性、确定性、可行性、存在输入及存在输出等5个重要特性。

1．有穷性

有穷性指算法在执行有限的步骤之后会自动结束，并且每一个步骤都在可接受的时间内完成。例如，C语言的一条语句 while(true){ }，该语句中循环条件为真，将一直执行循环体{ }。然而该循环体为空语句，如果没有break语句，语句将一直执行下去，这种情况称为死循环，在一般程序中是不允许出现的。但是，有穷性是个相对的概念，有时出现在网络服务器代码中是允许的，因为服务器通常需要处于连续工作当中。

2．确定性

确定性指算法的每一步必须有确切的定义，无二义性。算法在每种情况下的操作都有明确的规则，这避免了因操作的歧义性而使得计算机程序无法执行。

3．可行性

算法的每一步操作都是可行的，都能够通过基本运算执行有限次数完成。可行性意味着算法可以转换为计算机程序并得到正确的结果。不过，存在一些极其复杂的算法，理论上是可以实现的，但实际上受编程方法、工具等条件限制却不能实现。

4．输入

算法具有零个或多个取自特定数据对象集合的输入。有些算法看起来没有输入，但实际上已经有处理好的数据嵌入算法中或者已经存在于计算机中。

5．输出

一个算法具有零个或多个输出，这些输出与输入之间存在某种确定关系。输出是执行算法后，对数据进行加工处理得到的结果，这个结果可以是数据，也可以是操作过程执行结束后得到的对错/是否等信息。

算法与数据结构是相辅相成的。算法可以选择不同的数据结构，选择是否恰当直接影响算法效率的高低；数据结构的优劣由算法的执行来体现。

1.3.3　算法的评价

在算法设计中，针对同一个问题可以设计出多个不同的算法来解决它。如何评价这些算法并从中选择最优算法呢？

算法设计的要求通常包括以下5个方面。

（1）正确性。算法的正确性是指算法的输入/输出和加工处理无歧义，能够正确反映问题的需求，并且得到问题的正确答案。

算法的“正确性”大体分为4个层次：算法程序没有语法错误；合法的输入能够产生满足要求的结果；非法的输入数据能够得出满足规格说明的结果；对于特殊的输入数据也都有满足要求的结果。证明一个复杂算法在这4个层次上都是正确的，代价非常高。一般情况下，仅把第3层次作为一个算法是否“正确”的评判标准。

（2）可读性。算法的变量命名、格式符合行业规范，并在关键处给出注释，以提升算法的可理解性。

（3）稳健性。算法对于异常输入数据，或者出现错误操作后，能够给予错误提示信息，保证程序正常运行或者终止程序。

（4）时间高效性。时间效率指的是算法的执行时间，对于同一个问题可以有多个算法，执行时间短的算法效率高，执行时间长的效率低。这也就是算法的时间复杂度。

（5）低存储量。存储量通常包括算法在运行时所使用的变量、数据结构以及系统调用栈等所占用的内存空间。解决同一问题额外占用的临时存储空间越少，算法的空间效率就越高。算法存储量通常用空间复杂度来度量。

1.3.4　算法的复杂度

1．时间复杂度

事后统计法和事前分析估算法是衡量算法效率的两种方法。事后统计法需要先将算法实现，然后测算其时间和空间开销。这就要求：①必须把算法转换成可执行的程序；②测算结果依赖于计算机软硬件等环境因素，而这样做容易掩盖算法本身的优劣。因此，通常采用事前分析估算法，借助计算算法的渐进复杂度来衡量算法的效率。

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，执行的时间都可能不相同。一个算法的执行时间大致上等于它所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。由于语句的执行时间受编译器、硬件环境等因素影响，所以计算语句的真实执行时间是不可取的。这时尝试可采用算法中语句的执行次数之和来度量该算法的执行时间，即T(n) = f (n)。

【例1-1】 求两个n阶矩阵相加的算法。

  for (i=0; i<n; i++)                     // 语句频度为n+1
     for (j=0; j<n; j++)                  // 语句频度为n*(n+1)
        c[i][j]=a[i][j]+b[i][j];          // 语句频度为n*n

该算法所有语句的频度之和，是问题规模n的函数，且随着n的增大而增大。然而，对于上述较简单的算法，是相对比较复杂的。这给不同算法间时间效率的比较带来不便。从的表达式可以看到，随着n的增加，的大小主要是由最高阶项决定，它正好对应了基本运算（加法或赋值）的执行次数；同时中的最高阶也反映算法时间对问题规模的变化趋势（快慢）。所以，一般情况下并不用实际执行时间来衡量算法的效率，而是关注算法的时间开销对于问题规模变化的趋势。

设问题的规模为，即算法输入量的大小，算法的执行时间可用其基本操作的执行次数来度量。所谓的“基本操作”是指算法中执行次数最多的元操作，如加法、减法、乘法、除法、赋值、移位和逻辑运算等。为了进一步简单地反映算法时间的变化趋势，引入了渐进时间复杂性的理论。从数学意义上讲，算法时间的变化趋势集中体现的阶。

对于T(N)，如果存在Ť(N)，使得当N→∞时有：

称Ť(N)是T(N)当N→∞时的渐进复杂性。显然Ť(N)不是唯一的。我们可以尽可能选择简单的Ť(N)，然后使用Ť(N)来替代T(N)作为N→∞的复杂性度量。例如：

T(n)=3n²+4nlogn+7; Ť(n) =3n²

T(n)=4nlogn+7n; Ť(n) =4nlogn

进一步地，基于“O”给出渐进时间复杂性的定义。若T(n)和f (n)是定义在正整数集上的两个函数，则T(n) = O( f (n))表示存在正的常数c和n₀，使得当n≥n₀时都有0≤T(n)≤cf (n)。该定义说明T(n)的增长量阶不高于f (n)的增长量阶，而大多数情况下取与f (n)相同的增长量阶。表示随问题规模的增大，算法执行时间的增长量阶，称为算法的渐进时间复杂度，简称为时间复杂度。

【例1-2】 常量阶示例。

{a=a+i, i++;}

上面语句中，加法、赋值和自加操作均执行一次，相应的执行时间是一个与问题规模 n无关的常数。因此，该算法的时间复杂度T(n) = O(1)，称为常量阶。

【例1-3】 线性阶示例

 temp=0;
 for(i=0; i<n; i++)
     temp+=a[i];

上面的算法中，赋值和加法是基本操作，均执行 n 次。因此，该算法的时间复杂度T(n)=O(n)，称为线性阶。

【例1-4】 平均阶示例。

for(i=0;i<n-1;i++)
  for(j=i+1;j<n;j++)
     if (a[i]>a[j]) {
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
     }

上面算法中，a[i]>a[j]是基本操作，执行次数为：，则该算法的时间复杂度为T(n)=O(n²)，称为平方阶。

对某些具体问题，相应算法的基本操作不仅仅与问题的规模有关，也依赖于其他因素，如下例所示。

【例1-5】 在一维数组a中查找某个值等于e的元素，若存在则返回其所在位置。

for (i=0; i<n; i++)
  if (a[i]==e)  return i+1;
return 0;

容易发现，“a[i]==e”的执行次数不仅与问题规模n有关，而且与数组a中各元素的值及分布和元素e的值有关。假定数组a中存在等于e的值，则查找必定成功，同时“a[i]==e”的执行次数随着被查找到元素位置的不同而不同。最好的情况是a[1]等于e，此时仅需执行一次，即f (n)=1；最坏的情况是a[n−1]等于e，此时需执行n次。然而，对于一个算法来讲，需要考虑所有可能出现的情况，以及每种情况出现的概率。通常情况下，被查找元素在数组各个位置上出现的概率均相同（1/n），此时取查找到每个位置上“a[i]==e”执行次数的平均值，容易算出执行次数的平均值 f(n)=n/2。此例说明，算法的时间复杂度不仅问题的规模n有关，还可能与问题的其他因素有关，而这些因素影响着算法复杂度的试题。因此，有时人们会对算法有最好、最坏以及平均时间复杂度的评价。

算法在最好情况下的时间复杂度被称为最好时间复杂度，此时的计算量可能达到最小值。算法在最坏情况下的时间复杂度被称为最坏时间复杂度，这时的计算量可能达到最大值。算法的平均时间复杂度是指在考虑所有可能情况下，按照输入实例以等概率出现时算法计算量的加权平均值。

对于算法的时间复杂度，人们可能更关心其平均时间复杂度和最坏时间复杂度。在许多情况下，算法的平均时间复杂度很确定。在此背景下，人们在讨论算法时间复杂度时更多的是最坏时间复杂度，即最坏情况下，算法执行时间的上界。在本书后面讨论的时间复杂度，除非特别说明，均指最坏时间复杂度。

2．空间复杂度

一个算法在计算机存储器上所占的存储空间，包括存储算法本身所占用的存储空间、算法输入/输出数据所占用的存储空间，以及求解问题所需的辅助空间（也可以说是临时存储空间）。空间复杂度指的就是最后那部分临时存储空间，元素本身的大小不在空间复杂度的考虑范围之内。

3．时间复杂度与空间复杂度的关系

在实际算法中，时间效率和空间效率往往不可兼得。通常来说，一个算法如果在空间复杂度保持不变的情况下能够提高时间性能，该算法性能就得到了改进。随着硬件设备性能的提高及内存价格的降低，大多数情况下会牺牲空间来换取时间性能的提高。

1.4　如何学习和运用数据结构与算法

在学习数据结构与算法之前，需要先了解一下程序设计。程序设计是给出现实世界中解决特定问题程序的过程。一般来说，计算机解决具体问题的主要步骤如下。

① 现实世界中具体问题的抽象，即从具体问题抽象出一个合适的数学模型。

② 算法设计，即设计一个解决此数学模型的优秀算法。

③ 问题的解答，即程序的编写、测试以及调试。

其中，建立数学模型是一个从具体到抽象的过程，它一般包括两个步骤。

① 分析具体问题，选定操作对象。

② 发现对象间的关系，并用数学语言进行描述。

在处理实际问题之前，我们需要解决如下两个问题。

① 如何使用计算机能够理解的数据形式来描述现实世界的问题。例如，要设计一个购物平台，首先要解决的问题就是要设计一个合理的数据结构来存储每件商品的编号、名称、分类、价格等信息。

② 如何根据问题确定算法和实现程序开发。例如，一个购物平台需要对商品信息进行管理，需要解决数据的输入、删除、修改、插入、排序、查询等问题。采用合适的算法设计策略，如何设计出能解决问题的高效算法合理的算法。

学习数据结构，可以选择总结和概括的学习方法，内容脉络会非常清晰。数据结构内容可以大致概括为“三种数据结构+两种存储方法+三种重要算法”的一条学习线路——三种数据结构即线性结构、树结构、图结构，两种存储方法即顺序存储和链式存储，三种重要算法即查找、插入、删除。

学习算法设计，首先要掌握不同算法设计策略（分治算法、动态规划算法、贪心算法、回溯法和分支限界法）的基本思想和基本理论，然后总结出不同算法设计策略的异同和用之解决一些问题的基本步骤及主要思路。

1.5　习题

1．填空题

（1）　　　　是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

（2）　　　　指的是解决问题的有限运算序列。

（3）从逻辑关系上讲，数据结构主要分为　　　　、　　　　、　　　　和　　　　。

（4）数据的存储结构主要有　　　　和　　　　两种基本方法，不论哪种存储结构，都要存储两方面的内容：　　　　和　　　　。

（5）算法具有五个特性，分别是　　　　、　　　　、　　　　、　　　　、　　　　。

（6）算法的描述方法通常有　　　　、　　　　和　　　　、　　　　四种。

（7）在一般情况下，一个算法的时间复杂度是　　　　的函数。

（8）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为　　　　，若为nlog₂(5n)，则表示成数量级的形式为　　　　。

（9）算法在发生非法操作时可以作出处理的特性称为　　　　。

（10）数据结构是一门研究非数值计算的程序设计问题中计算机的　　　　以及它们之间的　　　　和运算等的学科。

2．选择题

（1）顺序存储结构中数据元素之间的逻辑关系是由（　　）表示的，链接存储结构中的数据元素之间的逻辑关系是由（　　）表示的。

A．线性结构　　

B．非线性结构　　

C．存储位置　　

D．指针

（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（　　）。

A．树　　

B．图　　

C．线性表　　

D．集合

（3）算法指的是（　　）。

A．对特定问题求解步骤的一种描述，是指令的有限序列

B．计算机程序

C．解决问题的计算方法

D．数据处理

（4）下面（　　）不是算法所必须具备的特性。

A．有穷性　　

B．确切性　　

C．高效性　　

D．可行性

（5）算法分析的目的是（　　），算法分析的两个主要方面是（　　）。

A．找出数据结构的合理性　　

B．研究算法中输入和输出的关系

C．分析算法的效率以求改进　　

D．分析算法的易读性和稳当性

E．空间性能和时间性能　　

F．正确性和简明性

G．可读性和文档性　　　　

H．数据复杂性和程序复杂性

（6）从逻辑上可以把数据结构分为（　　）两大类。

A．动态结构、静态结构　　

B．顺序结构、链式结构

C．线性结构、非线性结构　　

D．初等结构、构造型结构

（7）在下面的程序段中，对x的赋值语句的频度为（　　）。

for(k=1;k<=n;k++)
    for(j=1;j<=n;j++)
        x=x+1;

A．O(2n)　　

B．O(n)　　

C．O(n²)　　

D．O(log₂n)

（8）每个节点有且仅有一个直接前趋和多个（或无）直接后继（第一个节点除外）的数据结构称为（　　）。

A．树形结构　　

B．图形结构　　

C．线性结构　　

D．集合

（9）数据的（　　）包括查找、插入、删除、更新、排序等操作类型。

A．存储结构　　

B．逻辑结构　　

C．基本操作　　

D．算法描述

（10）在发生非法操作时，算法能够进行适当处理的特性称为（　　）。

A．正确性　　

B．健壮性　　

C．可读性　　

D．可移植性

3．判断题

（1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。　　（　　）

（2）每种数据结构都具备三个基本操作：插入、删除和查找。　　（　　）

（3）所谓数据的逻辑结构指的是数据之间的逻辑关系。　　（　　）

（4）逻辑结构与数据元素本身的内容和形式无关。　　（　　）

（5）基于某种逻辑结构之上的基本操作，其实现是唯一的。　　（　　）

（6）数据的逻辑结构是指数据的各数据项之间的逻辑关系。　　（　　）

（7）顺序存储方式的优点是存储密度大，且插入、删除运算效率高。　　（　　）

（8）数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。　　（　　）

（9）算法的高效性指算法要达到所需要的时间性能。　　（　　）

（10）算法必须有输出，但可以没有输入。　　（　　）

4．计算下题中的时间复杂度

（1）i=1;k=0 
    while (i < n - 1)
    {
        k=k+10*i;
        i++;
    }
（2）i=1;k=0;
    do
    {
        k=k+10*i;
        i++;
    }while(i <= n)
（3）i=1;j=0;
     while((i + j) <= n)
     if(i >j)  j++;
     else      i++;
（4）y=0;
    while((y + 1)*(y + 1) <=n)
        y=y+1;
（5）for(i=1;i<=n;i++)
         for(j = 1;j <= i; j ++)
            for(k= 1; k<=j; k++)
            x++;

5．简答题

（1）简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构。

（2）常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？

（3）简述算法和程序的区别。

6．操作题

（1）设计一个算法，求一维数组float a[n]中的所有元素之和，写出相应C程序。

（2）设计一个算法，依次输入三个数x、y和z，然后对其进行排序，并按从大到小的顺序输出。