第一章绪论内容概述数据结构研究非数值数据之间的逻辑关系，合理组织它们，存储到计算机内，并依此实现操作数据的算法。本章首先从数据结构的实例入手，分析了数据结构研究内容；然后介绍数据、数据元素、数据对象、数据结构、数据类型等数据结构所涉及的基本概念，并以抽象数据类型为工具结合实例描述了数据结构的表示与实现；最后介绍算法和算法的评价。本章难点和重点数据结构的理解、抽象数据类型的表示与实现、算法的评价。思考1你对数据结构的概念是如何理解？2数据逻辑结构包括哪些类型？3为什么采用抽象数据类型描述数据结构？4算法分析的目的是什么？案例分析1物流活动中货车的抽象数据类型表示与实现。第一节数据结构实例为了更好地理解数据结构，本节从飞机订票系统、物料清单、邮递员送信等三个实际应用入手分析了数据结构研究的内容。1.线性结构中数据元素之间的关系例1-1飞机订票系统。应用本系统进行飞机订票的过程中，客户首先通过查询航班信息表，并根据自己的情况按照起始城市和起降时间查找具体航班，然后，根据票价和座位情况，确定航班号，进而进行订票操作。订票操作中，客户输入姓名、证件号等信息后，选择航班、订票数，即可完成订票。在此类系统中，计算机处理的对象之间通常存在着一种最简单的线性关系，如图1-1所示，即各个数据元素按照一定的顺序线性排列，我们把这类结构称为线性数据结构。该类线性数据结构还可应用于其他各种订票系统、学籍管理、选课系统、网上购物、仓库账目管理等。2.树结构中数据元素之间的关系例1-2物料清单（BOM）。物料清单BOM（BillofMaterial）是一种描述配套件结构的零件表，其中包括所有子件、零件、原材料的清单，以及制造一个配件所需要的所有物料的数量。BOM是制造业信息系统的一个核心部件。如果我们将产品的配件按照线性数据结构罗列表示，如图1.2（a）所示，将不利于产品的设计和改进；当把产品的配件按照一定的层次进行表示时，如图1.2（b）所示，形成的结构图像一棵倒长的树，“树根”是该产品，而所有的“叶子”就是产品对应的零配件。这时的产品配件结构鲜明，易于分析和应用。我们把此类存储产品配件资料的数据结构称为“树”结构。该产品结构图不仅可以应用于产品的设计和改进，还可应用到生产管理中。当接收到客户订单时，查询每个结点即配件是否有货，即进行“遍历”操作。如果无货，对于本厂生产的配件，制订出生产作业计划；对于外购的配件，向供货商发出订单。如果把图1.2（b）的“树”结构转换成图1.2（c）的结构，即每个结点只有不多于两个分叉，转换后的结构可称为“二叉树”，该“树”的结点的增加、删除、修改、遍历等操作的相应算法将比非“二叉树”的算法更加简单和成熟。3.算法和算法的评价例1-3邮递员送信问题。如图1.3（a）所示，现在邮递员从邮局出发，向以下几个地点2、3、4送信。要求选择一条路线，从邮局出发，经过每个地点，最终回到邮局，并且路线长度最短。该问题描述的是经典的“中国邮路”问题，通常这类邮件发送问题的数学模型是一种称为“图”的数据结构。在此例中，如图1.3（b）所示，可以通过一个顶点表示一个地点，通过两点之间的连线表示两地之间的通路。此外，在诸如城市物流配送、建筑网络布线、城市道路规划等问题中，均会用到“图”数据结构。第二节基本概念和术语数据、数据对象、数据元素是更深入理解数据结构的基础概念。数据逻辑结构、数据存储结构是计算机处理非数值问题中算法设计与实现的依据。抽象数据类型是数据结构的描述框架，抽象数据类型的表示与实现也是本节需要解决的问题。1.数据、数据元素、数据对象数据（Data）是人们利用各种符号对客观事物及其活动进行的抽象描述。从计算机程序设计的角度来讲，数据则是计算机程序加工和处理的“原料”和对象。例如，一个简单的数值计算程序所使用的数据是一些整数和实数；一个编译程序所加工、处理的数据则是用某种高级语言编写的源程序。就我们本教材所讨论的内容而言，我们可做如下定义：数据是描述客观事物用到的数、字符以及所有能输入到计算机中并能被计算机处理的符号的集合，它是计算机程序使用、加工的原料和输出的结果。一般把数据分为数值性数据和非数值数据两类。数值性数据常用于科学计算和商业事务处理等，包括整数、实数、复数、双精度数；非数值数据一般是指字符、声音、图像、文字等数据。数据元素（DataElement）是数据整体中相对独立的基本单位，通常作为一个整体在计算机程序中进行处理。针对处理具体问题的不同，数据元素可以是从简单的数、字符到复杂的对象（例如C语言中的结构体类型），只要它们能被计算机接受并处理，包括图形、声音等。一个数据元素可以由若干个数据项组成，数据项是数据的最小单位，例如银行储蓄业务管理系统中处理的数据元素可包括如下数据项：账号，姓名，存入，支出，余额，利息；学生档案管理系统中的数据项常常是：学号，姓名，性别，年龄，籍贯，学习成绩。数据对象（DataObject）是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，1，2，字母字符数据对象是集合C=A，B，Z。2.数据结构、数据逻辑结构、数据存储结构数据结构现实世界中，客观事物都是相互联系的，所以数据之间也必然存在着联系。数据结构（DataStructure）就是指数据元素及其相互之间的关系。数据元素之间的相互联系称为数据的逻辑结构。根据数据元素之间关系的不同特性，数据结构可以分为集合、线性结构、树型结构、图结构4类基本结构，见图1.4。（1）集合：数据元素间的关系同属一个集合，除此之外，别无其它关系。（2）线性结构：结构中的元素间存在一对一的关系。（3）树型结构：结构中的元素间存在一对多的关系。（4）图（网状）结构：结构中的元素间存在多对多的关系。在上节中，我们已经看到了分别为线性结构、树结构和图结构的三个例子。为了更确切地描述数据的逻辑结构，通常采用二元组表示数据结构：Data_Structure=(D,S)其中：D是数据元素的有限集合，S是D上关系的有限集合。下面结合上节中的具体例子进行说明。例1-4在例1-1的飞机订票系统中，定义一种数据结构为：Linearity=(Name,Relation)，其中Name=丁琳,张伟,李明,王强Relation=，这是按照航班号的大小顺序排列的线性关系。对应的图形如图1.5所示。例1-5在例1-2的物料清单结构中，定义一种数据结构为：Tree=(Accessory,Relation)，其中Accessory=a,d,f,hRelation=,A，f,A，h对应的图形如图1.6所示。数据逻辑结构和数据存储结构我们利用计算机解决问题，就需要在计算机内部组织存放数据。数据在计算机内组织存放的方式就称为数据的存储结构或物理结构。在计算机中存储数据时，不仅要存储数据本身，还要存储数据之间的关系（即逻辑结构）。我们应当根据具体问题，对于某一给定的抽象数据结构，选择一种恰当的与其对应的数据存储结构，这一过程称为抽象数据结构到具体存储结构的映象。在计算机中，表示信息的最小单位是二进制数的一位，称为位（bit）。一个由若干位组合而成的位串称为元素（Element）或结点（Node），用它来表示数据元素，它是数据元素在计算机中的映像。存储结构可以分为顺序存储结构和链式存储结构两类。顺序存储结构是利用连续的存储单元来依次存放逻辑上相邻的数据元素，这样通过元素在存储器中的相对位置反映数据元素之间的关系。如图1.7(a)，某个姓名集合（李帅、张伟、马亮、刘源），“李帅”和“张伟”在逻辑上的关系是相邻的，这两个元素的存储位置也是相邻的。链式存储结构对应的存储空间不必是连续的存储单元或不必按数据元素的逻辑关系依次存储它们，它是通过指示出数据元素存储地址的指针反映元素之间的关系。如图1.7(b)，数据元素“马亮”的指针指向数据元素“刘源”的存储位置，这意味着，在逻辑关系上“马亮”和“刘源”是相邻的。数据的逻辑结构和物理结构密切相关，任何一个算法的设计取决于选定的逻辑结构，算法的实现则取决于采用的存储结构。1.抽象数据类型数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称，它描述了数据的取值范围、每一数据的结构及允许施加的操作。数据类型可以分为简单类型和结构类型两类。简单类型的值是不可分解的，通常只作为整体使用，如一个整数、实数、字符等。结构类型由若干简单类型数据或结构类型数据按照一定的规则构造而成，是可以分解的，它的成分可以是非结构的，也可以是结构的。抽象数据类型（ADT，AbstractDataType）由具有一定关系的一组数据和定义在该组数据上的操作组成。抽象数据类型的定义一般包括数据定义和操作定义两个部分。一个含抽象数据类型的模块通常包含定义、表示和实现3个部分。抽象数据类型为我们提供了一个描述数据结构的架构，在本书以后各章的内容中，我们均采用抽象数据类型对各种数据结构进行描述。抽象数据类型不仅包含一般数据类型的概念，还包括用户自定义的数据类型。正如近代程序设计方法学中指出的，为了提高软件的复用率，一个软件系统的框架应建立在数据之上，而不是建立在操作之上。也就是说，在构成软件系统的每个相对独立的模块上，定义一组数据和在该组数据上的操作，并在模块内部给出这些数据的表示及其操作的细节，同时在模块外部使用的只是抽象的数据和抽象的操作。定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。和数据结构的形式定义相对应，抽象数据类型的形式表示为：（D,S,O）其中：D是数据对象，S是D上的关系集合，O是D上的基本操作集合。在本书中我们一般按如下格式定义抽象数据类型：ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名其中，用伪码（PseudoCode，它是用介于自然语言和计算机语言之间的文字或符号来描述算法）描述数据对象和数据关系的定义，用下列格式定义基本操作：基本操作名（参数表）初始条件：操作结果：基本操作的参数有赋值参数和引用参数这两种参数。其中，赋值参数为操作提供输入值；引用参数以&开头，除提供输入值之外，还将返回操作结果。“初始条