山大《数据结构》讲义01绪论

1、第一章绪论内容概述数据结构研究非数值数据之间的逻辑关系，合理组织它们，存储到计算机内，并依此实现操作数据的算法。本章首先从数据结构的实例入手，分析了数据结构研究内容；然后介绍数据、数据元素、数据对象、数据结构、数据类型等数据结构所涉及的基本概念，并以抽象数据类型为工具结合实例描述了数据结构的表示与实现；最后介绍算法和算法的评价。本章难点和重点数据结构的理解、抽象数据类型的表示与实现、算法的评价。思考1你对数据结构的概念是如何理解？2数据逻辑结构包括哪些类型？3为什么采用抽象数据类型描述数据结构？4算法分析的目的是什么？案例分析1物流活动中货车的抽象数据类型表示与实现。第一节数据结构实例为了更好

2、地理解数据结构，本节从飞机订票系统、物料清单、邮递员送信等三个实际应用入手分析了数据结构研究的内容。1.线性结构中数据元素之间的关系例1-1飞机订票系统。应用本系统进行飞机订票的过程中，客户首先通过查询航班信息表，并根据自己的情况按照起始城市和起降时间查找具体航班，然后，根据票价和座位情况，确定航班号，进而进行订票操作。订票操作中，客户输入姓名、证件号等信息后，选择航班、订票数，即可完成订票。在此类系统中，计算机处理的对象之间通常存在着一种最简单的线性关系，如图1-1所示，即各个数据元素按照一定的顺序线性排列，我们把这类结构称为线性数据结构。该类线性数据结构还可应用于其他各种订票系统、学籍管理

3、、选课系统、网上购物、仓库账目管理等。2.树结构中数据元素之间的关系例1-2物料清单（BOM）。物料清单BOM（BillofMaterial）是一种描述配套件结构的零件表，其中包括所有子件、零件、原材料的清单，以及制造一个配件所需要的所有物料的数量。BOM是制造业信息系统的一个核心部件。如果我们将产品的配件按照线性数据结构罗列表示，如图1.2（a）所示，将不利于产品的设计和改进；当把产品的配件按照一定的层次进行表示时，如图1.2（b）所示，形成的结构图像一棵倒长的树，“树根”是该产品，而所有的“叶子”就是产品对应的零配件。这时的产品配件结构鲜明，易于分析和应用。我们把此类存储产品配件资料的数据

4、结构称为“树”结构。该产品结构图不仅可以应用于产品的设计和改进，还可应用到生产管理中。当接收到客户订单时，查询每个结点即配件是否有货，即进行“遍历”操作。如果无货，对于本厂生产的配件，制订出生产作业计划；对于外购的配件，向供货商发出订单。如果把图1.2（b）的“树”结构转换成图1.2（c）的结构，即每个结点只有不多于两个分叉，转换后的结构可称为“二叉树”，该“树”的结点的增加、删除、修改、遍历等操作的相应算法将比非“二叉树”的算法更加简单和成熟。3.算法和算法的评价例1-3邮递员送信问题。如图1.3（a）所示，现在邮递员从邮局出发，向以下几个地点2、3、4送信。要求选择一条路线，从邮局出发，经

5、过每个地点，最终回到邮局，并且路线长度最短。该问题描述的是经典的“中国邮路”问题，通常这类邮件发送问题的数学模型是一种称为“图”的数据结构。在此例中，如图1.3（b）所示，可以通过一个顶点表示一个地点，通过两点之间的连线表示两地之间的通路。此外，在诸如城市物流配送、建筑网络布线、城市道路规划等问题中，均会用到“图”数据结构。第二节基本概念和术语数据、数据对象、数据元素是更深入理解数据结构的基础概念。数据逻辑结构、数据存储结构是计算机处理非数值问题中算法设计与实现的依据。抽象数据类型是数据结构的描述框架，抽象数据类型的表示与实现也是本节需要解决的问题。1.数据、数据元素、数据对象数据（Data）

6、是人们利用各种符号对客观事物及其活动进行的抽象描述。从计算机程序设计的角度来讲，数据则是计算机程序加工和处理的“原料”和对象。例如，一个简单的数值计算程序所使用的数据是一些整数和实数；一个编译程序所加工、处理的数据则是用某种高级语言编写的源程序。就我们本教材所讨论的内容而言，我们可做如下定义：数据是描述客观事物用到的数、字符以及所有能输入到计算机中并能被计算机处理的符号的集合，它是计算机程序使用、加工的原料和输出的结果。一般把数据分为数值性数据和非数值数据两类。数值性数据常用于科学计算和商业事务处理等，包括整数、实数、复数、双精度数；非数值数据一般是指字符、声音、图像、文字等数据。数据元素（D

7、ataElement）是数据整体中相对独立的基本单位，通常作为一个整体在计算机程序中进行处理。针对处理具体问题的不同，数据元素可以是从简单的数、字符到复杂的对象（例如C语言中的结构体类型），只要它们能被计算机接受并处理，包括图形、声音等。一个数据元素可以由若干个数据项组成，数据项是数据的最小单位，例如银行储蓄业务管理系统中处理的数据元素可包括如下数据项：账号，姓名，存入，支出，余额，利息；学生档案管理系统中的数据项常常是：学号，姓名，性别，年龄，籍贯，学习成绩。数据对象（DataObject）是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，1，2，字母字符数据对象

8、是集合C=A，B，Z。2.数据结构、数据逻辑结构、数据存储结构数据结构现实世界中，客观事物都是相互联系的，所以数据之间也必然存在着联系。数据结构（DataStructure）就是指数据元素及其相互之间的关系。数据元素之间的相互联系称为数据的逻辑结构。根据数据元素之间关系的不同特性，数据结构可以分为集合、线性结构、树型结构、图结构4类基本结构，见图1.4。（1）集合：数据元素间的关系同属一个集合，除此之外，别无其它关系。（2）线性结构：结构中的元素间存在一对一的关系。（3）树型结构：结构中的元素间存在一对多的关系。（4）图（网状）结构：结构中的元素间存在多对多的关系。在上节中，我们已经看到了分别

9、为线性结构、树结构和图结构的三个例子。为了更确切地描述数据的逻辑结构，通常采用二元组表示数据结构：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,

10、hRelation=,A，f,A，h对应的图形如图1.6所示。数据逻辑结构和数据存储结构我们利用计算机解决问题，就需要在计算机内部组织存放数据。数据在计算机内组织存放的方式就称为数据的存储结构或物理结构。在计算机中存储数据时，不仅要存储数据本身，还要存储数据之间的关系（即逻辑结构）。我们应当根据具体问题，对于某一给定的抽象数据结构，选择一种恰当的与其对应的数据存储结构，这一过程称为抽象数据结构到具体存储结构的映象。在计算机中，表示信息的最小单位是二进制数的一位，称为位（bit）。一个由若干位组合而成的位串称为元素（Element）或结点（Node），用它来表示数据元素，它是数据元素在计算机中的

11、映像。存储结构可以分为顺序存储结构和链式存储结构两类。顺序存储结构是利用连续的存储单元来依次存放逻辑上相邻的数据元素，这样通过元素在存储器中的相对位置反映数据元素之间的关系。如图1.7(a)，某个姓名集合（李帅、张伟、马亮、刘源），“李帅”和“张伟”在逻辑上的关系是相邻的，这两个元素的存储位置也是相邻的。链式存储结构对应的存储空间不必是连续的存储单元或不必按数据元素的逻辑关系依次存储它们，它是通过指示出数据元素存储地址的指针反映元素之间的关系。如图1.7(b)，数据元素“马亮”的指针指向数据元素“刘源”的存储位置，这意味着，在逻辑关系上“马亮”和“刘源”是相邻的。数据的逻辑结构和物理结构密切相

12、关，任何一个算法的设计取决于选定的逻辑结构，算法的实现则取决于采用的存储结构。1.抽象数据类型数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称，它描述了数据的取值范围、每一数据的结构及允许施加的操作。数据类型可以分为简单类型和结构类型两类。简单类型的值是不可分解的，通常只作为整体使用，如一个整数、实数、字符等。结构类型由若干简单类型数据或结构类型数据按照一定的规则构造而成，是可以分解的，它的成分可以是非结构的，也可以是结构的。抽象数据类型（ADT，AbstractDataType）由具有一定关系的一组数据和定义在该组数据上的操作组成。抽象数据类型的定义一般包括数据定

13、义和操作定义两个部分。一个含抽象数据类型的模块通常包含定义、表示和实现3个部分。抽象数据类型为我们提供了一个描述数据结构的架构，在本书以后各章的内容中，我们均采用抽象数据类型对各种数据结构进行描述。抽象数据类型不仅包含一般数据类型的概念，还包括用户自定义的数据类型。正如近代程序设计方法学中指出的，为了提高软件的复用率，一个软件系统的框架应建立在数据之上，而不是建立在操作之上。也就是说，在构成软件系统的每个相对独立的模块上，定义一组数据和在该组数据上的操作，并在模块内部给出这些数据的表示及其操作的细节，同时在模块外部使用的只是抽象的数据和抽象的操作。定义的数据类型的抽象层次越高，含有该抽象数据类

14、型的软件模块的复用程度也就越高。和数据结构的形式定义相对应，抽象数据类型的形式表示为：（D,S,O）其中：D是数据对象，S是D上的关系集合，O是D上的基本操作集合。在本书中我们一般按如下格式定义抽象数据类型：ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名其中，用伪码（PseudoCode，它是用介于自然语言和计算机语言之间的文字或符号来描述算法）描述数据对象和数据关系的定义，用下列格式定义基本操作：基本操作名（参数表）初始条件：操作结果：基本操作的参数有赋值参数和引用参数这两种参数。其中，赋值参数为操作提供输入值；引用参数以&开头，除提供输入值之外，还将返回操作结果。“

15、初始条件”描述了操作执行前数据结构和参数应满足的条件，若不能满足初始条件，则操作失败，返回相应的出错信息。“操作结果”说明了操作正常完成后数据结构的变化情况和应返回的结果。2.抽象数据类型的表示与实现抽象数据类型的表示与实现我们可以通过固有数据类型表示和实现抽象数据类型，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。由于我们是在高级程序设计语言的层次上来讨论抽象数据类型的表示和实现，所以采用介于C语言和伪码之间的类C语言作为数据结构的描述工具，或用伪码来描述一些只含抽象操作的抽象算法。这样可以使数据结构和算法的描述相对简单和清晰，不必严格按照C语言的语法细节来描

16、述，但易于转换成C或C+程序。本书所采用的类C语言是在精选C语言的核心集的基础上作了修改和扩充而成的，它增强了语言的描述功能。以下对其作简要说明。（1）预定义常量和类型/函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE1#defineOVERFLOW2/Status是函数的类型，其值是函数结果状态代码typedefintStatus;（2）数据结构的表示（存储结构）用类型定义（typedef）描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。（3）基本操作的算法都用以下形

17、式的函数描述：函数类型函数名（函数参数表）/算法说明语句序列/函数名除了函数的参数需要说明类型，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。一般而言，用a，b，c等表示数据元素，i，j，k等表示整型变量，p，q等表示指针变量。当函数返回值为函数结果状态代码时，函数定义为Status类型。除值调用方式以外，增加了C+语言的引用调用的参数传递方式，以便于算法的描述。注意在形式参数表中，以&打头的参数即为引用参数。（4）赋值语句简单赋值变量名=表达式；串联赋值变量名1=变量名2=变量名k=表达式；成组赋值（变量名1,变量名k）=（表达式1,表达式k）；结构名=结构名；结构名=（值1

18、，值k）；变量名=表达式；变量名起始下标.终止下标=变量名起始下标.终止下标；交换赋值变量名变量名条件赋值变量名=条件表达式？表达式1：表达式2；（5）选择语句条件语句1if（表达式）语句；条件语句2if（表达式）语句1；else语句2；开关语句1switch（表达式）case值1：语句序列1；break；case值n：语句序列n；break；default：语句序列n+1；开关语句2switchcase条件1：语句序列1；break；case条件n：语句序列n；break；default：语句序列n+1；（6）循环语句for语句for（赋初值表达式；条件表达式；修改表达式）语句；while语

19、句while（条件表达式）语句；do-while语句do语句序列；while（条件表达式）；（7）结束语句函数结束语句return表达式；return；case结束语句break；异常结束语句exit（异常代码）；（8）输入和输出语句输入语句scanf（格式串，变量1，变量n）；输出语句printf（格式串，表达式1，表达式n）；通常省略格式串。（9）注释单行注释/文字序列（10）逻辑运算约定与运算&：对于A&B，当A的值为零时，不再对B求值。或运算|：对于A|B，当A的值为非零时，不再对B求值。下面看一个简单的例子。例1-6在物流活动中，经常应用到货车进行运输。一般货车每次运输不止一种货物，

20、每种货物都有对应的数量。在进行装货、卸货等操作的时候，需要根据各种货物的变化情况修改其种类和数量。因此，我们可以把货车定义为一种抽象数据类型，其数据部分包括货车车厢里的货物种类和数量，操作部分包括初始化货车、装货、卸货等。假设给定一个三厢货车用SET表示，车厢用g1，g2和g3表示，每个车厢只能装载一种货物，货物种类由小写字母a，b，c标记，并注明每种货物的数量，如图1.8所示。抽象数据类型ADTTruck的定义ADTTruck数据对象：D=g1,g2,g3|g1,g2,g3SET数据关系：R=,基本操作：InitTruck(&T,v1,v2,v3)操作结果：创建货车T，车厢g1、g2和g3分

21、别装上数据为v1、v2和v3的货物。DestroyTruck(&T)操作结果：货车T被销毁。GoodsGet(T,i,&e)初始条件：货车T存在，1i3。操作结果：用e返回第i个车厢的货物数据。GoodsChange(&T,i,e,&f)初始条件：货车T存在，1i3。操作结果：卸下货车T中第i个车厢的货物，用f返回，并装上数据为e的货物。GoodsSort(&T)初始条件：货车T存在。操作结果：货车T中货物放入车厢g1g3的顺序按货物种类的字母顺序排列。Max(T,&e)初始条件：货车T存在。操作结果：用e返回货车T的3个车厢中数量最大的货物数据。Min(T,&e)初始条件：货车T存在。操作结

22、果：用e返回货车T的3个车厢中数量最小的货物数据。ADTTruck/抽象数据类型ADTTruck的表示和实现typedefstruct/货物数据，作为Truck的数据元素charkind;/产品种类intnum;/产品数量ElemType;typedefElemType*Truck;StatusInitTruck(Truck&T,ElemTypev1,ElemTypev2,ElemTypev3)/创建货车T，依次设置T的三个车厢的初值为v1,v2和v3。T=(ElemType*)malloc(3*sizeof(ElemType);if(!T)exit(OVERFLOW);T0=v1;T1=v2

23、;T2=v3;/为每个元素赋值，即为每个车厢装货returnOK;/InitTruckStatusDestroyTruck(Truck&T)/销毁货车free(T);T=NULL;returnOK;/DestroyTruckStatusGoodsGet(TruckT,inti,ElemType&e)/得到第i个车厢的货物数据if(i3)returnERROR;e=Ti1;returnOK;/GoodsGetStatusGoodsChange(Truck&T,inti,ElemTypee,ElemType&f)/卸下货车T中第i个车厢的货物并返回其数据，装上数据为e的货物。if(i3)retur

24、nERROR;f=Ti1;Ti1=e;returnOK;/GoodsChangeStatusGoodsSort(Truck&T)/货车T中货物放入车厢g1g3的顺序按货物种类由a到c排列if(T0.kindT1.kind)T0T1;if(T0.kindT2.kind)T0T2;if(T1.kindT2.kind)T1T2;returnOK;/GoodsSortStatusMax(TruckT,ElemType&e)/用e返回货车T的3个车厢中数量最大的货物数据。e=(T0.num=T1.num)?(T0.num=T2.num)?T0:T2):(T1.num=T2.num)?T1:T2);ret

25、urnOK;/MaxStatusMin(TruckT,ElemType&e)/用e返回货车T的3个车厢中数量最小的货物数据。e=(T0.num=T1.num)?(T0.num=T2.num)?T0:T2):(T1.num=T2.num)?T1:T2);returnOK;/Min第三节算法和算法的评价算法是解决特定问题的有限运算序列。本节介绍算法具有的特性以及算法设计的优劣评价指标。1.算法的特性算法（Algorithm）是指完成一个任务所需要的具体步骤和方法的描述。一个算法可以采用文字叙述，或用传统的流程图、NS图等描述。一个算法应具备以下五个特性：（1）有穷性：一个算法必须在执行有穷步之后结束，每一步都在有穷时间内完成。（2）确定性：算法中的每一步都必须有确切的含义，没有二义性，对于相同的输入只能得出相同的输出。（3）可行性：算法中的每一步都能够通过有限次的基本运算在有限时间内实现。（4）输入：一个算法可以有零个或多个取自于某个特定对象集合的输入量。（5）输出：一个算法执行结束后至少有一个输出量。2.时间复杂性及其计算时间复