山东大学《数据结构》讲义01绪论.docx

第一章绪论
内容概述
数据结构研究非数值数据之间的逻辑关系，合理组织它们，存储到计算机内, 并依此实现操作数据的算法。本章首先从数据结构的实例入手，分析了数据结构 研究内容；然后介绍数据、数据元素、数据对象、数据结构、数据类型等数据结 构所涉及的基本概念，并以抽象数据类型为工具结合实例描述了数据结构的表示 与实现；最后介绍算法和算法的评价。
本章难点和重点数据结而的理解、抽象数据类型的表示与实现、算法的评价。
思考.你对数据结构的概念是如何理解？
1 .数据逻辑结构包括哪些类型？
2 .为什么采用抽象数据类型描述数据结构？
3 .算法分析的目的是什么？
案例分析<!"[if!supportLists]->l. v!--[endif]-->物流活动中货车的抽象数据类型表示 与实现。
第一节数据结构实例为了更好地理解数据结构，本节从飞机订票系统、物料清单、邮递员送信等三个 实际应用入手分析了数据结构研究的内容。
v!supportLists]-->L v线性结构中数据元素之间的关系例1-1飞机订票系统。应用本系统进行飞机订票的过程中，客户首先通过查询航 班信息表，并根据自己的情况按照起始城市和起降时间查找具体航班，然后，根 据票价和座位情况，确定航班号，进而进行订票操作。订票操作中，客户输入姓 名、证件号等信息后，选择航班、订票数，即可完成订票。在此类系统中，计算 机处理的对象之间通常存在着一种最简单的线性关系，如图1-1所示，即各个数 据元素按照一定的顺序线性排列，我们把这类结构称为线性数据结构。
该类线性数据结构还可应用于其他各种订票系统、学籍管理、选课系统、网上 购物、仓库账目管理等。
2 .树”结构中数据元素之间的关系例1-2物料清单(BOM)。物料清单BOM (BillofMaterial)是一种描述配套件结 构的零件表，其中包括所有子件、零件、原材料的清单，以及制造一个配件所需 要的所有物料的数量。BOM是制造业信息系统的一个核心部件。如果我们将产 品的配件按照线性数据结构罗列表示，如图L2 (a)所示，将不利于产品的设 计和改进；当把产品的配件按照一定的层次进行表示时，如图1.2 (b)所示， 形成的结构图像一棵倒长的树，''树根〃是该产品，而所有的''叶子〃就是产品对应 的零配件。这时的产品配件结构鲜明，易于分析和应用。我们把此类存储产品配 件资料的数据结构称为''树〃结构。
该产品结构图不仅可以应用于产品的设计和改进，还可应用到生产管理中。当 接收到客户订单时，查询每个结点即配件是否有货，即进行''遍历〃操作。如果无 货，对于本厂生产的配件，制订出生产作业计划；对于外购的配件，向供货商发 出订单。如果把图L2 (b)的''树〃结构转换成图1.2 (c)的结构，即每个结点只 成。
(2)确定性：算法中的每一步都必须有确切的含义，没有二义性，对于相同的 输入只能得出相同的输出。
(3)可行性:算法中的每一步都能够通过有限次的基本运算在有限时间内实现。
(4)输入：一个算法可以有零个或多个取自于某个特定对象集合的输入量。
(5)输出：一个算法执行结束后至少有一个输出量。
v!・-[if!supportLists]-->2. v!--[endif]-->时间复杂性及其计算
时间复杂度(Timecomplexity)。指一个算法运行时间的相对量度。一个算法 在计算机上从开始运行到运行结束花费的时间约等于计算机执行一种简单操作 的时间和算法中进行简单操作的次数的乘积。其中计算机执行一种简单操作的时 间由计算机本身的硬、软件环境决定，所以通常把算法中包含简单操作的次数作 为算法的时间复杂度，用来衡量一个算法的运行时间。算法中基本操作重复执行 的次数一般是问题规模n的一个函数f(n)o我们在本书中不要求对时间复杂度进 行精确计算，只要大致计算出相应的数量级即可。所以我们把算法的时间复杂度 记作T(n)=O(f(n))。多数情况下最深层次循环内的语句中的原操作，其重复执行 的次数和算法的执行时间成正比，和包含它的语句的频度相同。语句的频度
(Frequencycount)是指该语句重复执行的次数。例如，在以下程序段中：
a){a=0;b=l;s=a+b;}
b)for(i=0;i<N;
c)for(i=0;i<N;for0=O;j<N;c[i][j]=na[i][j]+b[i][j]; <br"j++)> 三个例子都包含求
和这个基本操作。其中，第一个例子含基本操作、's=a+b〃的语句的频度是1；第 二个例子含基本操作％+=b[i]〃的语句的频度是n；第三个例子含基本操作的语句的频度是n2。以上三个例子的时间复杂度分别是
0(1), 0(n), 0(n2)o其中，0(1)是常量阶，表示算法的运行时间不随数据量n 的改变而改变；0(n)是线性阶，表示算法的运行时间与n成正比；0(n2)是平方 阶，当n加倍时算法的运行时间将增长4倍。常见的算法的时间复杂度有0(1), 0(n), 0(n2), O(lnn), O(log2n), 0(2n)等形式。
对于一个算法而言，最好情况的时间复杂度最容易求出，但通常实际意义不大; 最坏情况下的时间复杂度是估算算法执行时间的一个上界，通过它可以估计算法 运行所需要的最长时间，并使用户尽量防止出现这种情况；一般计算平均情况下 的时间复杂度，需要概率统计和推导，但最具实际意义，可以确切的反映出运行 一个算法的平均快慢程度。
有不多于两个分叉，转换后的结构可称为''二叉树〃，该''树〃的结点的增加、删除、 修改、遍历等操作的相应算法将比非''二叉树〃的算法更加简单和成熟。
3 . v!—[endif]—>算法和算法的评价例L3邮递员送信问题。如图1.3（a）所示，现在邮递员从邮局出发，向以下几 个地点2、3、4送信。要求选择一条路线，从邮局出发，经过每个地点，最终 回到邮局，并且路线长度最短。
该问题描述的是经典的''中国邮路〃问题，通常这类邮件发送问题的数学模型是 一种称为''图〃的数据结构。在此例中，如图1,3 （b）所示，可以通过一个顶点表 示一个地点，通过两点之间的连线表示两地之间的通路。
此外，在诸如城市物斫 ''图〃数据结构。
AT-
/ /-
/ \ //
«TR/
叫
酒已送、建筑网络布线、城市道路规划等问题中，均会用到
4 11 /^\
v、>«
r/
10J
-—• / \
Ax

图1.3邮递员送信问题
第二节基本概念和术语数据、数据对象、数据元素是更深入理解数据结构的基础概念。数据逻辑结构、 数据存储结构是计算机处理非数值问题中算法设计与实现的依据。抽象数据类型 是数据结构的描述框架，抽象数据类型的表示与实现也是本节需要解决的问题。 <>-[if!supportLists]->l. v数据、数据元素、数据对象
数据（Data）是人们利用各种符号对客观事物及其活动进行的抽象描述。从计 算机程序设计的角度来讲，数据那么是计算机程序加工和处理的''原料〃和对象。例 如，一个简单的数值计算程序所使用的数据是一些整数和实数；一个编译程序所 加工、处理的数据那么是用某种高级语言编写的源程序。就我们本教材所讨论的内 容而言，我们可做如下定义：数据是描述客观事物用到的数、字符以及所有能输 入到计算机中并能被计算机处理的符号的集合，它是计算机程序使用、加工的原 料和输出的结果。一般把数据分为数值性数据和非数值数据两类。数值性数据常 用于科学计算和商业事务处理等，包括整数、实数、复数、双精度数；非数值数 据一般是指字符、声音、图像、文字等数据。
数据元素（Data日ement）是数据整体中相对独立的基本单位，通常作为一个 整体在计算机程序中进行处理。针对处理具体问题的不同，数据元素可以是从简 单的数、字符到复杂的对象（例如C语言中的结构体类型），只要它们能被计算 机接受并处理，包括图形、声音等。一个数据元素可以由假设干个数据项组成，数据项是数据的最小单位，例如银行储蓄业务管理系统中处理的数据元素可包括如 下数据项：
账号，姓名，存入，支出，余额，利息；
学生档案管理系统中的数据项常常是:
学号，姓名，性别，年龄，籍贯，学习成绩。
数据对象(DataObject)是性质相同的数据元素的集合，是数据的一个子集。
例如，整数数据对象是集合N=｛0, ±1, ±2,字母字符数据对象是集合C=｛'A。…，Z｝。
<!-[if!supportLists]->2,，数据结构、数据逻辑结构、数据存
储结构
数据结构
现实世界中，客观事物都是相互联系的，所以数据之间也必然存在着联系。数 据结构(DataStructure)就是指数据元素及其相互之间的关系。
数据元素之间的相互联系称为数据的逻辑结构。根据数据元素之间关系的不同 特性，数据结构可以分为集合、线性结构、树型结构、图结构4类基本结构，见 图1.4。(1)集合：数据元素间的关系同属一个集合，除此之外，别无其它关 系。(2)线性结构：结构中的元素间存在一对一的关系。(3)树型结构：结构 中的元素间存在一对多的关系。(4)图(网状)结构：结构中的元素间存在多 对多的关系。在上节中，我们已经看到了分别为线性结构、树结构和图结构的三 个例子。
(a)集合
(d)
(b)式性(c)W
图数据结构的分类
为了更确切地描述数据的逻辑结构，通常采用二元组表示数据结构：
Data_Structu re=(D,S)其中：D是双据元素的有限集合，S是D上关系的有限集合。
下面结合上节中的具体例子进行说明。
例1-4在例的飞机订票系统中，定义一种数据结构为：
Linearity=(Name,Relation),其中
Name=｛丁琳，张伟，李明，王强｝
Relation=｛<李明，王强〉，〈王强，丁琳〉，〈丁琳，张伟〉｝这是按照航班号的大小顺序排列的线性关系。对应的图形如图L5所示。
<!--[if!supportLineBreakNewLine]->lI<!-[endif]->
例1・5在例1-2的物料清单结构中，定义一种数据结构为:
Tree=(Accessory,Relation),其中
Accessory={a,d,f,h}
Relation={<A,d>,<A<span>, f>,<A<span>, h>}对应的图形如图1,6所示。
(a) A (£>(£> <S><!-[if!supportLineBreakNewLine]--> 图】6 数据的树结构
数据逻辑结构和数据存储结构
我们利用计算机解决问题，就需要在计算机内部组织存放数据。数据在计算机 内组织存放的方式就称为数据的存储结构或物理结构。在计算机中存储数据时, 不仅要存储数据本身，还要存储数据之间的关系（即逻辑结构）。我们应当根据 具体问题，对于某一给定的抽象数据结构，选择一种恰当的与其对应的数据存储 结构，这一过程称为抽象数据结构到具体存储结构的映象。在计算机中，表示信 息的最小单位是二进制数的一位，称为位（bit）。一个由假设干位组合而成的位 串称为元素（Element）或结点（Node）,用它来表示数据元素，它是数据元素 在计算机中的映像。
存储结构可以分为顺序存储结构和链式存储结构两类。顺序存储结构是利用连 续的存储单元来依次存放逻辑上相邻的数据元素，这样通过元素在存储器中的相 对位置反映数据元素之间的关系。如图1.7（a）,某个姓名集合（李帅、张伟、马 亮、刘源），''李帅''和',张伟〃在逻辑上的关系是相邻的，这两个元素的存储位置 也是相邻的。链式存储结构对应的存储空间不必是连续的存储单元或不必按数据 元素的逻辑关系依次存储它们，它是通过指示出数据元素存储地址的指针反映元 素之间的关系。如图1.7（b）,数据元素''马亮〃的指针指向数据元素''刘源〃的存储 位置，这意味着，在逻辑关系上''马亮〃和''刘源''是相邻的。

图1.7存偌结构例如
<!~[endif]~>
数据的逻辑结构和物理结构密切相关，任何一个算法的设计取决于选定的逻辑 结构，算法的实现那么取决于采用的存储结构。
< !-[if !supportLists]-> 1.v抽象数据类型
数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称， 它描述了数据的取值范围、每一数据的结构及允许施加的操作。数据类型可以分 为简单类型和结构类型两类。简单类型的值是不可分解的，通常只作为整体使用， 如一个整数、实数、字符等。结构类型由假设干简单类型数据或结构类型数据按照 一定的规那么构造而成，是可以分解的，它的成分可以是非结构的，也可以是结构 的。
抽象数据类型（ADT, AbstractDataType）由具有一定关系的一组数据和定义 在该组数据上的操作组成。抽象数据类型的定义一般包括数据定义和操作定义两 个局部。一个含抽象数据类型的模块通常包含定义、表示和实现3个局部。 抽象数据类型为我们提供了一个描述数据结构的架构，在本书以后各章的内容中, 我们均采用抽象数据类型对各种数据结构进行描述。
抽象数据类型不仅包含一般数据类型的概念，还包括用户自定义的数据类型。 正如近代程序设计方法学中指出的，为了提高软件的复用率，一个软件系统的框 架应建立在数据之上，而不是建立在操作之上。也就是说，在构成软件系统的每 个相对独立的模块上，定义一组数据和在该组数据上的操作，并在模块内部给出 这些数据的表示及其操作的细节，同时在模块外部使用的只是抽象的数据和抽象 的操作。定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复 用程度也就越高。
和数据结构的形式定义相对应，抽象数据类型的形式表示为：
（D,S,O）其中：D是数据对象，S是D上的关系集合，。是D上的基本操作集合。
在本书中我们一般按如下格式定义抽象数据类型：
ADT抽象数据类型名{
数据对象：〈数据对象的定义,
数据关系：〈数据关系的定义,
基本操作：〈基本操作的定义》
}ADT抽象数据类型名其中，用伪码（Pseudocode,它是用介于自然语言和计算机语言之间的文字或 符号来描述算法）描述数据对象和数据关系的定义，用以下格式定义基本操作： 基本操作名（参数表）
初始条件：〈初始条件描述》
操作结果：〈操作结果描述》基本操作的参数有赋值参数和引用参数这两种参数。其中，赋值参数为操作提供 输入值；引用参数以&开头，除提供输入值之外，还将返回操作结果J'初始条件〃 描述了操作执行前数据结构和参数应满足的条件，假设不能满足初始条件，那么操作 失败，返回相应的出错信息。''操作结果〃说明了操作正常完成后数据结构的变化 情况和应返回的结果。
<!-[if!supportLists]->2. v!--[endif]--> 抽象数据类型的表示与实现抽象数据类型的表示与实现
我们可以通过固有数据类型表示和实现抽象数据类型，即利用处理器中已存在 的数据类型来说明新的结构，用已经实现的操作来组合新的操作。由于我们是在 高级程序设计语言的层次上来讨论抽象数据类型的表示和实现，所以采用介于C 语言和伪码之间的类C语言作为数据结构的描述工具，或用伪码来描述一些只含 抽象操作的抽象算法。这样可以使数据结构和算法的描述相对简单和清晰，不必 严格按照C语言的语法细节来描述，但易于转换成C或C++程序。
本书所采用的类C语言是在精选C语言的核心集的基础上作了修改和扩充而成 的，它增强了语言的描述功能。以下对其作简要说明。
（1）预定义常量和类型
〃函数结果状态代码
#defineTRUEl
#defineFALSEO
#defineOKl
#defineERRORO
#defineINFEASIBLE-l
#defineOVERFLOW-2
“Status是函数的类型，其值是函数结果状态代码
typedefintStatus;
（2）数据结构的表示（存储结构）用类型定义（typedef）描述。数据元素类 型约定为日emType,由用户在使用该数据类型时自行定义。（3）基本操作的 算法都用以下形式的函数描述：
函数类型函数名（函数参数表）{
〃算法说明
语句序列
} 〃函数名除了函数的参数需要说明类型，算法中使用的辅助变量可以不作变量说明，必要 时对其作用给予注释。一般而言，用a, b, c等表示数据元素，i, j, k等表示 整型变量，p, q等表示指针变量。当函数返回值为函数结果状态代码时，函数 定义为Status类型。除值调用方式以外，增加了 C++语言的引用调用的参数传 递方式，以便于算法的描述。注意在形式参数表中，以&打头的参数即为引用参 数。
（4）赋值语句简单赋值变量名=表达式；
串联赋值变量名1=变量名2=...=变量名1<=表达式；成组赋值（变量名1,…,变量名k）=（表达式1,…,表达式k）；
结构名=结构名；结构名=（值1,…，值k）；
变量名口二表达式；变量名［起始下标.,终止下标］=变量名［起始下标.,终止下标］;
交换赋值变量名^—变量名条件赋值变量名=条件表达式？表达式1：表达式2；
（5）选择语句条件语句lif （表达式）语句；
条件语句2if （表达式）语句1；else语句2；
开关语句lswitch （表达式）{case < 1 ：语句序列 1； break；
■ ■ ■case值n：语句序列n； break；
default：语句序列n+1；）
开关语句2switch{case条件1：语句序列1； break；
■ ■ ■case条件n：语句序列n； break；
default：语句序列n+1；）
（6）循环语句for语句fo「（赋初值表达式；条件表达式；修改表达式）语句；
while语句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在物流活动中，经常应用到货车进行运输。一般货车每次运输不止一 种货物，每种货物都有对应的数量。在进行装货、卸货等操作的时候，需要根据 各种货物的变化情况修改其种类和数量。因此，我们可以把货车定义为一种抽象 数据类型，其数据局部包括货车车厢里的货物种类和数量，操作局部包括初始化 货车、装货、卸货等。
假设给定一个三厢货车用SET表示，车厢用gl, g2和g3表示，每个车厢只能 装载一种货物，货物种类由小写字母a, b, c标记，并注明每种货物的数量，如 图L8所示。
抽象数据类型ADTTruck的定义ADTTruck{
数据对象：D={gl,g2,g3|gl,g2,g3eSET)
数据关系：R={<Gl,g2>,<G2,g3>}
基本操作：
InitT ruck(&T,vl,v2,v3)
操作结果：创立货车T,车厢gl、g2和g3分别装上数据为vl、v2和v3的 货物。
DestroyTruck(&T)
操作结果：货车T被销毁。
GoodsGet(T,i,&e)
初始条件：货车T存在，14区3。
操作结果：用e返回第i个车厢的货物数据。
GoodsChange(&T,i,e,&f)
初始条件：货车T存在，14区3。
操作结果：卸下货车T中第i个车厢的货物，用f返回，并装上数据为e的货 物。
GoodsSort(&T)
初始条件：货车T存在。
操作结果:货车T中货物放入车厢gl〜g3的顺序按货物种类的字母顺序排列。
Max(T,&e)
初始条件：货车T存在。
操作结果：用e返回货车T的3个车厢中数量最大的货物数据。
Min(T,&e)
初始条件：货车T存在。
操作结果：用e返回货车T的3个车厢中数量最小的货物数据。
}ADTTruck
〃抽象数据类型ADTTruck的表示和实现typedefstruct{〃货物数据，作为Truck的数据元素
charkind;//声品种类
intnum; 〃产品数量}ElemType;
typedefElemT ype*T ruck;StatusInitTruck(Truck&TzElemTypevlzElemTypev2,ElemTypev3){
〃创立货车T,依次设置T的三个车厢的初值为vl,v2和v3o
T二(日 emType*)malloc(3*sizeof(日 emType));
if(!T)exit(OVERFLOW);
T[0]=vl;T[l]=v2;T[2]=v3;〃为每个元素赋值，即为每个车厢装货
returnOK;}//InitTruck
StatusDestroyT ruck(T ruck&T){
〃销毁货车
free(T);T=NULL;
returnOK;}//DestroyTruck
StatusGoodsGet(TruckTzinti,ElemType&e){
〃得到第i个车厢的货物数据
if(i<l||i>3)returnERR0R;
e=T[i-l];
returnOK;}//GoodsGet
StatusGoodsChange(Truck&T,inti,ElemTypee,ElemType&f){
〃卸下货车T中第i个车厢的货物并返回其数据，装上数据为e的货物。
if(i<l||i>3)returnERROR;
f=T[i-l]；
T[i-l]=e;
returnOK;}//GoodsChange
StatusGoodsSort(T ruck&T){
〃货车T中货物放入车厢gl〜g3的顺序按货物种类由a到c排列
if(T[O].kind>T[l].kind)
T ⑼一T[l];
if(T[0].kind>T[2].kind)
T 血一T[2];
if(T[l].kind>T[2].kind)
T[l]-T[2];
returnOK;}//GoodsSort
StatusMax(TruckT,ElemType&e){
〃用e返回货车T的3个车厢中数量最大的货物数据。
e=(T[0].num>=T[l].num)?((T[0].num>=T[2].num)?T[0]:T[2])
:((T[l].num>=T ⑵,num)?T[l]:T[2]);
returnOK;}//Max
StatusMin(TruckT,ElemType&e){
〃用e返回货车T的3个车厢中数量最小的货物数据。
e=(T[0].num<=T[l].num)?((T[0].num<=T[2].num)?T[0]:T[2])
:((T[l].num<=T[2].num)?T[l]:T[2]);
returnOK;}//Min
第三节算法和算法的评价算法是解决特定问题的有限运算序列。本节介绍算法具有的特性以及算法设计的 优劣评价指标。
<!-[if!supportLists]->l. <!--[endif]-->算法的特性
算法(Algorithm)是指完成一个任务所需要的具体步骤和方法的描述。一个算 法可以采用文字表达，或用传统的流程图、N-S图等描述。
一个算法应具备以下五个特性：
(1)有穷性：一个算法必须在执行有穷步之后结束，每一步都在有穷时间内完