第三章算法与数据结构

1、第三章第三章 算法与数据结构算法与数据结构l 用计算机解决实际问题时，首先要进行程序用计算机解决实际问题时，首先要进行程序 设计；而程序设计主要包括两个方设计；而程序设计主要包括两个方 面的面的内内 容：容： -行为特性的设计行为特性的设计- - 将解决实际问题的每个细节准确地加以定义，并且还应当将全部解题过程完整地描述出来。这就是算法的设计 -结构特性的设计结构特性的设计- - 确定合适的数据结构l 程序设计的步骤：程序设计的步骤： 1了解和研究需要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤 2模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来 3用计算机语言将步骤转化

2、为计算机可以“读懂”的计算机程序，即所谓的“编程” 4进行测试和修改l 本章着重讨论解决问题的核心本章着重讨论解决问题的核心-算法算法以及以及 算法的处理对象算法的处理对象-数据的结构数据的结构3.1 3.1 算法算法l通常，把解题过程的准确而完整的描述称作通常，把解题过程的准确而完整的描述称作解该问题的算法解该问题的算法 程序的目的是加工数据，而如何加工数据是算法的问题。程序是数据结构与算法的统一lNiklaus WirthNiklaus Wirth教授进一步提出了如下有名公教授进一步提出了如下有名公式：式： 程序算法数据结构 程序就是在数据的某些特定的表示方式和结构基础上对抽象算法的计算机

3、语言具体表述l从算法的角度，可将程序定义为从算法的角度，可将程序定义为: 为解决给定为解决给定问题的计算机语言有穷操作规则的有序集合问题的计算机语言有穷操作规则的有序集合一算法的两要素一算法的两要素l一个算法由一些操作组成，而这些操作又是一个算法由一些操作组成，而这些操作又是按一定的控制结构所规定的次序执行的按一定的控制结构所规定的次序执行的 操作操作 (1) 逻辑运算： “与”、“或”、“非” (2) 算术运算： 加、减、乘、除 (3) 数据比较： 大于、小于、等于、不等于 (4) 数据传送： 输入、输出、赋值 算法的控制结构（三种基本控制结构）算法的控制结构（三种基本控制结构） (1)顺序

4、 (a.顺序结构） (2)选择 (b.选择结构） (3)循环 (c.直到型循环 d.当型循环) 三种基本控制结构的一般形式三种基本控制结构的一般形式S1S2BS1S2BS(a)(b)(c)S3FTBFT(d)Sl 算法结构化算法结构化1966 Bohm Jacopini顺序顺序选择选择循环直到循环直到循环当循环当二算法的特征二算法的特征l算法具有以下几个特征：算法具有以下几个特征： 有效性 确定性，可行性 足够的信息:一个或多个输出;0个或多个输入 有穷性:执行是可终止的l算法是一个过程，这个过程由一套明确的规算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，则组成，

5、这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答以便用有限的步骤提供特定类型问题的解答三算法的表示三算法的表示l 自然语言自然语言l 专用工具专用工具l 算法描述语言算法描述语言自然语言自然语言l 用自然语言描述算法通俗易懂，但它用自然语言描述算法通俗易懂，但它 存在着难以克服的缺陷存在着难以克服的缺陷: : 易产生歧义性 语句比较繁琐冗长，并且很难清楚地表达算法的逻辑流程。如果算法中包含判断、循环处理，尤其是这些处理的嵌套层数增多，自然语言描述其流程既不直观又很难表达清楚 当今的计算机尚不能处理用自然语言表示的算法专用工具专用工具l为了形象地描述算法，人们创造了许多专用为

6、了形象地描述算法，人们创造了许多专用工具来描述算法。常用的有流程图、工具来描述算法。常用的有流程图、PADPAD图图和和N-SN-S图等。除图形工具之外，人们可使用图等。除图形工具之外，人们可使用代码符号代码符号( (如伪代码如伪代码) )描述算法描述算法lPADPAD是问题分析图（是问题分析图（Problem Analysis Problem Analysis DiagramDiagram）的英文缩写，自）的英文缩写，自19731973年由日本日年由日本日立公司发明以来，已经得到一定程度的推广。立公司发明以来，已经得到一定程度的推广。它用二维数形结构的图表示程序的控制流，它用二维数形结构的图

7、表示程序的控制流，将这种图转换为程序代码比较容易将这种图转换为程序代码比较容易 常用流程图符号常用流程图符号开始结束(a) 起止框、连接框(b) 输入输出框AA输入a,bN10(c) 判断框truefalse(d) 处理框i+1i(e) 注释框(f) 流向线N为正整数流程图简明直观、便于交流N-S图图l Nassi和和Shneiderman提出了一种符合结构化程序设提出了一种符合结构化程序设计原则的图形描述工具，叫做盒图，也叫做计原则的图形描述工具，叫做盒图，也叫做N-S图图 N-S图的五种基本控制结构PAD图图l PAD是是Problem Analysis Diagram 的缩写，它是日的缩

8、写，它是日本日立公司提出，由程序流程图演化来的，用结构本日立公司提出，由程序流程图演化来的，用结构化程序设计思想表现程序逻辑结构的图形工具。现化程序设计思想表现程序逻辑结构的图形工具。现在已为在已为ISO认可认可 PAD图的五种基本控制结构算法描述语言算法描述语言l为了便于转换成某种编程语言，一般采为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。如用准程序设计语言作算法描述语言。如pascal_likepascal_like，c_likec_like等类等类_xxx_xxx语言。本语言。本书约定一种算法描述语言，这种语言是书约定一种算法描述语言，这种语言是VBVB语言的变体，

9、称为类语言的变体，称为类VBVB语言语言类类VBVB语言一览表语言一览表种种 类类名名 称称表示形式表示形式备备 注注注释行以 “ ”开始的一段文字在本行内有效标识符由字母开头的字母数字构成不区分大小写算术运算符，关系运算符，运算符逻辑运算符AND ， OR ， NOT ，赋值语句变量 = 表达式a b，其中，a是变量或数组元素，b是表示式或常数。复合语句 中内容表示可以迭代输入语句INPUT 输出语句PRINT 错误显示语句ERROR ( 错误信息)简单语句变量声明语句变量名：数据类型(接下页)种种 类类名名 称称表示形式表示形式备备 注注过程定义PROC过程名 () ENDVB 中是Sub

10、过程名（ ）过程调用CALL 过程名 ()函数定义FUNC 函数名 ()：类型 RETURN (函数的返回值)ENDVB 中是Function 函数名()AS类型函数名=返回值Exit FunctionEnd Function 算法形式函数调用变量名 = 函数名 ()类类VBVB语言一览表语言一览表条 件 语 句I F T H E N E L S E E N D I F对 于 复 合 语 句 ， 可 用 如 下 形 式 ：I F T H E N 语 句 块1 E L S E I F T H E N 语 句 块2 E L S E I F T H E N 语 句 块n - 1 E L S E 语

11、句 块n E N D I F分支语句分 情 形 语 句C A S E 变 量 名 O F 常 量 表1 ： 常 量 表2 ： E N D C A S E指 针 类 型变 量 名 ： 类 型V B 语 言 中 没 有 指 针 类 型类型定义结 构 类 型T Y P E 类 型 标 识 符 域 名1 ： 类 型1 域 名2 ： 类 型2 E N D T Y P EF O R 语 句F O R 循环控制变量= 初值 T O 终值 S T E P 增 量 N E X T 循 环 控 制 变 量终 值 大 于 或 等 于 初 值F O R 语 句F O R 循 环 控 制 变 量 = 初 值 D O W

12、 N T O 终值 S T E P 增 量 N E X T 循 环 控 制 变 量终 值 小 于 或 等 于 初 值W H I L E 语 句W H I L E D O E N D W H I L E重复语句L O O P 语 句D O E X I T D O L O O P W H I L E 四四. . 常用算法常用算法l 枚举法枚举法 ( (穷举法）穷举法）l 迭代法迭代法l 递归法递归法l 递推法递推法l 分治法分治法l 回溯法回溯法枚举法枚举法l 枚举法亦称穷举法，它的基本思想是：首先依据题目枚举法亦称穷举法，它的基本思想是：首先依据题目的部分条件确定答案的大致范围，然后在此范围内对

13、的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到全部情况验证完。若所有可能的情况逐一验证，直到全部情况验证完。若某个情况使验证符合题目的条件，则为本题的一个答某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则本案；若全部情况验证完后均不符合题目的条件，则本题无答案题无答案l 枚举法的实质是枚举所有可能的解，用检验条件判断枚举法的实质是枚举所有可能的解，用检验条件判断定哪些是有用的，哪些是无用的，而题目往往就是检定哪些是有用的，哪些是无用的，而题目往往就是检验条件。枚举法的特点是验条件。枚举法的特点是算法简单，但有时运算量大算法简

14、单，但有时运算量大，对于可确定解的取值范围且又一时找不到其他更好的对于可确定解的取值范围且又一时找不到其他更好的算法时，就可以用它算法时，就可以用它枚举法例题枚举法例题l 百鸡问题：百元买百鸡百鸡问题：百元买百鸡 公鸡公鸡5元元 母鸡母鸡3元元 小鸡小鸡1/3元元 x+y+z=100 5x+3y+z/3=100 三层循环嵌套三层循环嵌套迭代法迭代法l 重复同样步骤，可以逐次求得更精确的值。这一重复同样步骤，可以逐次求得更精确的值。这一过程即为迭代过程过程即为迭代过程l 使用迭代法构造算法的基本方法是：首先确定一使用迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解

15、个合适的迭代公式，选取一个初始近似值以及解的误差，然后用循环处理实现迭代过程，终止循的误差，然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差。并认为最后一对值小于或等于预先给定的误差。并认为最后一次迭代得到的近似值为问题的解。这种迭代方法次迭代得到的近似值为问题的解。这种迭代方法称为逼近迭代称为逼近迭代013 xx在在x1.5附近的一个根附近的一个根31xx25721. 115 . 13x33086. 1135721. 13x13 xx递归法递归法l递归是构造计算机算法的一种基本方递归是构造计算机

16、算法的一种基本方法。如果一个过程直接或间接地调用法。如果一个过程直接或间接地调用它自身，则称该过程是递归的，它自身，则称该过程是递归的， 递归递归过程必须有一个递归终止条件，即存过程必须有一个递归终止条件，即存在在“递归出口递归出口”。无条件的递归是毫。无条件的递归是毫无意义的无意义的l f(n)=n!=n*(n-1)!=n*f(n-1)llong fac(int i)l if (i = 1) fac = 1; return fac; else fac = i * fac(i - 1);l递归算法汉诺塔递归算法汉诺塔lPROC MoveTower( N, 1, 2)l call MoveTow

17、er( N-1, 1, 3)l call MoveDisk( 1, 2)l call MoveTower( N-1, 3, 2)lEND123NN-1递归法递归法（汉诺塔移动问题）（汉诺塔移动问题）l Please input the number of disks : n= 3 Please input the number of disks : n= 3l move disk 1 from peg 1 to peg 2 move disk 1 from peg 1 to peg 2l move disk 2 from peg 1 to peg 3 move disk 2 from peg

18、1 to peg 3l move disk 1 from peg 2 to peg 3 move disk 1 from peg 2 to peg 3l move disk 3 from peg 1 to peg 2 move disk 3 from peg 1 to peg 2l move disk 1 from peg 3 to peg 1 move disk 1 from peg 3 to peg 1l move disk 2 from peg 3 to peg 2 move disk 2 from peg 3 to peg 2l move disk 1 from peg 1 to pe

19、g 2 move disk 1 from peg 1 to peg 2l Press any key to continue Press any key to continue递推法递推法l所谓递推法，它的数学公式也是递归的所谓递推法，它的数学公式也是递归的（如：（如：f(n)=n!=n*(n-1)!=n*f(n-1) ）。只是）。只是在实现计算时迭代方向相反。从给定边界在实现计算时迭代方向相反。从给定边界出发逐步迭代到达指定计算参数。它不需出发逐步迭代到达指定计算参数。它不需反复调用自己（节省了很多调用参数匹配反复调用自己（节省了很多调用参数匹配开销），效率较高开销），效率较高l递推操作是提

20、高递归函数执行效率最有效递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见的方法，科技计算中最常见递归与递推递归与递推l 递推是从已知的初始条件出发，逐次递推出最后所递推是从已知的初始条件出发，逐次递推出最后所求的值求的值l 递归则是从需求的函数本身出发，逐次上溯调用其递归则是从需求的函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值倒推回来，得到最终的值l 一般说来，一个递推算法总可以转换为一个递归算一般说来，一个递推算法总可以转换为一个递归算法。尽管递归算法往往比非递归算法要付出更多的法。尽管

21、递归算法往往比非递归算法要付出更多的执行时间，由于递归算法编程序非常容易，用递归执行时间，由于递归算法编程序非常容易，用递归过程来描述算法非常自然，而且证明算法的正确性过程来描述算法非常自然，而且证明算法的正确性也比相应的非递归形式容易很多，因此，递归是算也比相应的非递归形式容易很多，因此，递归是算法设计的基本技术法设计的基本技术lF(0) = 0! = 1lF(1) = 1! = 1*f(0) = 1lF(2) = 2! = 2*f(1) = 2lF(3) = 3! = 3* f(2) = 6l.lF(n) = n* (n-1)! = n*f(n-1)分治法分治法l解一个复杂的问题时，尽可能

22、地把这个问解一个复杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这再把各部分的解组合成整个问题的解，这就是所谓的分治法就是所谓的分治法l分治法在设计检索、快速分类选择等问题分治法在设计检索、快速分类选择等问题的算法中是很有效的，并得到广泛应用的算法中是很有效的，并得到广泛应用分治法（分治法（Divide and Conquer) “分分”而治之而治之一般方法一般方法l 对大规模问题的求解对大规模问题的求解 l 利用分治法求解大规模问题利用分治法求解大规模问题 分治策略基本思想 当问题的规模较大而无法直接求解

23、时，将整个问题分成若干个小问题，然后分而治之。 可用递归过程描述。一般情况下，子问题与原始问题“同质”回溯法回溯法l回溯法是设计算法中的一种基本策略。回溯法是设计算法中的一种基本策略。在那些涉及到寻找一组解的问题或者满在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有足某些约束条件的最优解的问题中，有许多可以用回溯法来求解许多可以用回溯法来求解l例：迷宫游戏l例：8皇后问题l在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。l8皇后问题可以表示为8-元组(x1,x8) ，其中xi是放置皇后i所在的列号。

24、l显式约束条件是si=1,2,3,4,5,6,7,8, 1i8l隐式约束条件是，没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。QQQQQQQQ 1 2 3 4 5 6 7 812345678由于解向量之间不能相同，所以解空间的大小由由于解向量之间不能相同，所以解空间的大小由88个个元组减少到元组减少到8!个元组。上图中的解表示为一个个元组。上图中的解表示为一个8-元组元组即即（4，6，8，2，7，1，3，5）。算法分析算法分析l评价算法是否完善，我们主要关心以下三个评价算法是否完善，我们主要关心以下三个问题问题: :算法的复杂度算法的复杂度l时间复杂度-算法的时间代价l空间复杂度-执

25、行算法所需的内存空间算法的最优性算法的最优性-衡量算法的好坏主要依据算法的复杂度，特别是时间复杂度l最优算法是指在解决一个问题时，如果在被研究的算法类中，没有一个算法比现有算法执行更少的基本运基本运算算，则称此算法是最优的快速算法的设计快速算法的设计-与工程上常用的算法相比，其时间复杂度较小l快速算法不一定是最优算法背包问题背包问题假设有一个能装入总体积为假设有一个能装入总体积为T的背包和的背包和n件体积分别为件体积分别为w1 , w2 , , wn 的物品，能否从的物品，能否从n件物品中挑选若干件恰好装满背包件物品中挑选若干件恰好装满背包，即使，即使w1 +w2 + + wn=T，要求找出所

26、有满足上述条件的，要求找出所有满足上述条件的解。例如：当解。例如：当T=10，各件物品的体积，各件物品的体积1，8，4，3，5，2时时，可找到下列，可找到下列4组解：（组解：（1，4，3，2） （1，4，5） （8，2） （3，5，2）。）。 提示：可利用回溯法的设计思想来解决背包问题。首先将物提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品，若该件物品件物品“太大太大”不能装入，则弃

27、之而继续选取下一件，直至不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明填满背包，则说明“刚刚刚刚”装入背包的那件物品装入背包的那件物品“不合适不合适”，应将它取出，应将它取出“弃之一边弃之一边”，继续再从，继续再从“它之后它之后”的物品中的物品中选取，如此重复，直至求得满足条件的解，或者无解。选取，如此重复，直至求得满足条件的解，或者无解。举例：顺序搜索法举例：顺序搜索法输入：一维数组 L（1：n），搜索项 x输出：第一次使L（j）=x的j，若x不在数组L中，则输出为0j=1Whil

28、e (j= n) and (L(j)x) Do j=j+1If jn Then j=0Output jReturn设x在数组L中的概率为q。当输入的x为L(i)时，算法所做的比较次数为i,1=i=nT(L(i)=n,i=n+1l 假设输入x出现在数组每个位置上的可能性相等：q/n,1=i=n p(L(i)=1-q,i=n+1l 于是：A(n)=(n+1)q/2+(1-q)nl 当已知x在数组L中时，q=1,则A(n)=(n+1)/2，平均要检查一半的元素l 当已知有一半的机会不在此数组中时，q=1/2,则A(n)约为3n/4，即大约要检查数组中3/4的元素l 最坏的情况是检查n次3.2 3.2

29、 数据结构数据结构l 任何程序都要处理数据任何程序都要处理数据l 在计算机诞生后的一段时期，它主要作为高速的在计算机诞生后的一段时期，它主要作为高速的科学计算工具。程序关心的是计算机速度、精确科学计算工具。程序关心的是计算机速度、精确性、可靠性，用到的数据相对简单：各种类型的性、可靠性，用到的数据相对简单：各种类型的变量，一维或多维数组、简单的表变量，一维或多维数组、简单的表l 随着计算机商业应用的发展，程序关心的数据组随着计算机商业应用的发展，程序关心的数据组织和快速存取织和快速存取l 计算机系统更是大量处理数据计算机系统更是大量处理数据l 计算机科学的各个领域及有关的应用软件都要用计算机科

30、学的各个领域及有关的应用软件都要用到数据结构到数据结构 一数据结构概述一数据结构概述l 数据的基本单位称为数据元素。有时一个数据元素由若干个数据项组成，在这种情况下，称数据元素为记录。数据项是数据的最小单位l 最简单的数据元素是一个数据项（有时也叫元素），复杂的数据项间存在着某些联系。这种联系称为结构。当然，数据元素之间还可以构成结构关系，所以数据结构就是指数据之间的结构关系(或是带有结构特性的数据元素的集合)数据结构的研究内容数据结构的研究内容l数据结构作为一个学科分支主要是研究程序数据结构作为一个学科分支主要是研究程序设计中计算机所操作的对象以及它们之间的设计中计算机所操作的对象以及它们之

31、间的关系和运算，概括地说是三个方面：关系和运算，概括地说是三个方面： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算数据的运算数据的逻辑结构数据的逻辑结构l数据的逻辑结构是数据元素之间的逻辑关数据的逻辑结构是数据元素之间的逻辑关系。它只抽象地反映数据元素集合的结构，系。它只抽象地反映数据元素集合的结构，而不管其存储方式，它可以用一个二元组而不管其存储方式，它可以用一个二元组给出如下形式的定义：给出如下形式的定义： Data-Structure Data-Structure (D,R)(D,R) 其中，其中，D D是数据元素的集合，是数据元素的集合，R R是是D D上关系

32、的集合上关系的集合数据的存储结构数据的存储结构l数据的逻辑结构在计算机内存中的映数据的逻辑结构在计算机内存中的映象称为数据的物理结构。数据的存储象称为数据的物理结构。数据的存储结构是数据在计算机内存中的结构是数据在计算机内存中的实际存实际存放方式放方式。只能是首地址后跟一长串数。只能是首地址后跟一长串数据，或按地址寻值别无它法据，或按地址寻值别无它法数据的运算数据的运算l 程序中的数据运算是定义在数据的逻辑结构上的，程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有结构都有一个运

33、算集合。常用的运算有检索、插入、检索、插入、删除、更新、排序删除、更新、排序等。简单的逻辑结构和物理结构等。简单的逻辑结构和物理结构完全一致，如数组和表处理，所以学好简单数据结完全一致，如数组和表处理，所以学好简单数据结构就可以打下实现复杂数据结构的基础。而复杂数构就可以打下实现复杂数据结构的基础。而复杂数据结构能提高我们解决问题的能力。在以下的讲述据结构能提高我们解决问题的能力。在以下的讲述中数据元素用中数据元素用“结点结点”画出，关系用结点间弧线或画出，关系用结点间弧线或箭头表示箭头表示数据结构的分类数据结构的分类l从结构的观点，一般将数据结构分为两大类：从结构的观点，一般将数据结构分为两

34、大类： 线性数据结构l 线性表、栈、队列、串、数组和文件 非线性数据结构l 树和图二线性表二线性表l 线性表是最简单、最常用也是最基本的一种数据结线性表是最简单、最常用也是最基本的一种数据结构。线性表的逻辑结构是构。线性表的逻辑结构是n n个数据元素的有限序列个数据元素的有限序列: : (a1, a2 ,a3,an) 表中元素的个数表中元素的个数n n定义为线性表的长度定义为线性表的长度(n0)(n0)，n=0n=0的表称为空表的表称为空表l 线性表的结构特征是：数据元素呈线性关系线性表的结构特征是：数据元素呈线性关系在线性表中必存在唯一被称为在线性表中必存在唯一被称为“第一个第一个”的数据元

35、素的数据元素必存在唯一的一个被称为必存在唯一的一个被称为“最后一个最后一个”的数据元素的数据元素除第一个元素外，每个元素都有且只有一个前驱元素除第一个元素外，每个元素都有且只有一个前驱元素除最后一个元素外，每个元素都有且只有一个后继元素除最后一个元素外，每个元素都有且只有一个后继元素所有数据元素所有数据元素aiai在同一个线性表中必须是相同的数据类型在同一个线性表中必须是相同的数据类型线性表线性表（续）（续）l 线性表按其存储结构可分为线性表按其存储结构可分为顺序表顺序表和和链表链表 用顺序存储结构存储的线性表称为顺序表 用链式存储结构存储的线性表称为链表l线性表的基本运算主要有线性表的基本运

36、算主要有： 在两个确定的元素之间插入一个新的元素 删除线性表中某个元素 按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新顺序表和一维数组顺序表和一维数组 l 计算机中表示线性表最简单的办法是用一组地址连续的存储单元依次存放线性表的数据元素。这种顺序分配的存储方式的表，称为顺序表 逻辑上的相邻元素存储地址也相邻 线性表的逻辑关系隐含在存储单元的邻接关系中 数据元素的数据类型相同，每个元素占用同样大小的存储单元l 高级语言里的一维数组就是用顺序方式存储的线性表l 线性表的示意图如下图所示a3a2a1a4a5an顺序表插入算法顺序表插入算法l 在线性表(a1, a2,，ai，ai+

37、1，an)的第i个位置插入元素x，使之成为(a1, a2,，ai，x，ai+1，an)，其算法描述如下： PROC INSERT (VAR A,VAR n,i,x)PROC INSERT (VAR A,VAR n,i,x) 注释：在一维数组A(1n)中第i个元素之前插入一个新元素x If(in+1) Then ERROR(“位置不存在！”) 注释：插入的位置不合法 Else For j=n Down To i+1For j=n Down To i+1 A(j+1)=A(j) 注释：元素后移 Next jNext j Endif A(i)=x 注释：进行插入 n=n+1 注释：线性表的长度加1

38、End顺序表删除算法顺序表删除算法l 通常，在表长为n的线性表(a1, a2 ,，ai-1,ai，ai+1，an)中删除第i个数据元素，还需将第i+1个至第n个元素向前推动一个位置，即(a1, a2 ,，ai-1,ai+1，an)，其算法描述如下： PROC DELETE (VAR A,VAR n,i) 注释：一维数组A(1:n)中的第i个元素处删除该元素x If (in) Then ERROR (位置不存在！) 注释：删除的位置不合法 ELSE FOR j=i TO n-1 A(j)=A(j+1) 注释：元素前移 Next j n=n-1 注释：表长减1 Endif End链表链表l 在顺序

39、表中插入或删除元素时，都不可避免地在顺序表中插入或删除元素时，都不可避免地要作要作元素的移动元素的移动，每进行一次插入或删除，都，每进行一次插入或删除，都要移动近乎一半的元素。又由于顺序表是一组要移动近乎一半的元素。又由于顺序表是一组地址连续的存储单元，对于长度可变的线性表，地址连续的存储单元，对于长度可变的线性表，必须按其可能达到的最大长度必须按其可能达到的最大长度预先分配空间预先分配空间，这可能由于估计不足造成一部分空间太长而得这可能由于估计不足造成一部分空间太长而得不到充分利用，也可能因空间过短而造成溢出。不到充分利用，也可能因空间过短而造成溢出。链表恰能有效地克服这些缺点。链表恰能有效

40、地克服这些缺点。链表一般有单链表一般有单链表、双向链表和循环链表链表、双向链表和循环链表单链表单链表( (线性链表线性链表) )l 单链表就是链式存储的线性表，其结点除信息域外单链表就是链式存储的线性表，其结点除信息域外还含有一个还含有一个指针域指针域，用来，用来指出其后继结点的位置指出其后继结点的位置。单链表的最后一个结点没有后继结点，它的指针域单链表的最后一个结点没有后继结点，它的指针域为空为空( (记为记为NULL NULL 或或)。另外还需要设置一个指针。另外还需要设置一个指针headhead，指向单链表的第一个结点，指向单链表的第一个结点l 链表的一个重要特点是插入、删除运算灵活方便

41、，链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可不需移动结点，只要改变结点中指针域的值即可单链表的相关操作单链表的相关操作infonext信息域指针域李研刘丰陈宏英HeadabHeadabHeadx acHeadb 单链表节点结构单链表逻辑示意图单链表的插入单链表的删除循环链表循环链表l循环链表是表结构形式上和单循表稍有不同的一种链表。循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NULL”，而是指向头一个结点，整个链表成为一个由链指针相链结的环，故称之为循环链表。其插入、删除算法和单链表没有多大区别双向链表双向链表l 对于线性表来说，除了

42、设有指向后继结点的指针对于线性表来说，除了设有指向后继结点的指针外，还可设一个指向前驱结点的指针。我们称这外，还可设一个指向前驱结点的指针。我们称这种含有种含有两个指针域两个指针域的结点构成的链表为双向链表。的结点构成的链表为双向链表。由于每个结点中都设有两个指针，则不仅可直接由于每个结点中都设有两个指针，则不仅可直接得到后继结点的信息，也容易得到前驱结点的信得到后继结点的信息，也容易得到前驱结点的信息。但在作插入、删除运算时，需要同时修改两息。但在作插入、删除运算时，需要同时修改两个方向上的指针。一般情况下，我们称结点含有个方向上的指针。一般情况下，我们称结点含有多个指针域的链表为多重链表，

43、上述表示线性表多个指针域的链表为多重链表，上述表示线性表的双向链表是多重链表的双向链表是多重链表循环链表与双向链表结构对比循环链表与双向链表结构对比栈栈l栈栈(STACK)(STACK)也是一种特殊的线性表，是一也是一种特殊的线性表，是一种种“后进先出后进先出”的结构，也是使用最为广的结构，也是使用最为广泛的数据结构之一泛的数据结构之一l栈的结构特点货栈栈的结构特点货栈 货栈 穿衣服的顺序 子弹压入子弹夹 摞盘子栈栈（续）（续）l 栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom) ；栈的操作是按先进后出的原则进行，故栈又称为LIFO (Last

44、In First Out)表，如右上图所示l 栈的物理存储可以用顺序存储结构，也可以用链式存储结构，如右下图所示ana3a2a1进栈出栈栈顶 top栈底栈底栈顶top栈栈（续）（续）l 栈的运算：栈的运算： 通常对栈进行的运算有：设置一个空栈、判定某个栈是否为空栈、进栈操作、退栈操作以及读取栈顶元素等。下面分别给出顺序存储结构栈的进栈和退栈的算法进栈进栈l PROC PUSHSTACK (VAR STACKPROC PUSHSTACK (VAR STACK，m m，VAR topVAR top，x)x) 注释：在栈STACK(1:m)的栈顶top之上插入元素x BEGIN IF top=m T

45、HEN ERROR (“栈满！”) ELSE top=top+1 注释：栈顶上移 STACK(top)=x 注释：将x放入栈顶 ENDIF END退栈退栈l PROC POPSTACK (VAR STACK，VAR top，VAR y)：VAR 注释：当栈空时返回函数值FALSE，反之 退出栈顶元素赋给变量y并返回函数值TRUE BEGIN IF top=0 THEN RETURN (FALSE) ELSE y=STACK(top) 注释：将栈顶元素赋给变量y top=top-1 注释：栈顶下移 RETURN (TRUE) ENDIF END队列队列l 队列也是一种特殊的线性表，与生活中的队列

46、也是一种特殊的线性表，与生活中的“排队排队”极为相极为相似，也是按似，也是按“先来到先解决先来到先解决”的原则行事的，的原则行事的，既不允许既不允许“加塞儿加塞儿”，也不允许，也不允许“中途离队中途离队”，“先入先出先入先出”l 队列队列(Queue)(Queue)是限定所有的是限定所有的插入只能在表的一端进行，而所插入只能在表的一端进行，而所有的删除都在表的另一端进行有的删除都在表的另一端进行的线性表。表中允许插入的的线性表。表中允许插入的一端称为队尾一端称为队尾(Rear)(Rear)，允许删除的一端称为队头，允许删除的一端称为队头(Front)(Front)，队列的物理存储可以用顺序存储

47、结构，也可以用链式存储队列的物理存储可以用顺序存储结构，也可以用链式存储结构结构a1 a2 a3 an入队列出队列头尾队列的运算队列的运算l 通常对队列进行的运算有：设通常对队列进行的运算有：设置一个空队列；判定某个队列置一个空队列；判定某个队列是否是空队列；插入一个新的是否是空队列；插入一个新的队尾元素，简称入队列；删除队尾元素，简称入队列；删除队头元素，简称出队列；以及队头元素，简称出队列；以及读取队头元素等读取队头元素等l 如果进入队列的元素个数事先如果进入队列的元素个数事先可以估计得到，则队列可以按可以估计得到，则队列可以按顺序存储方式进行组织。当队顺序存储方式进行组织。当队列的容量无

48、法预先估计时，可列的容量无法预先估计时，可以采用以采用右图所示的链表存储结右图所示的链表存储结构构队尾队头FrontRear队列的运算队列的运算（续）（续）l “假溢出假溢出”问题问题：若采取每插入一个元素，队尾指：若采取每插入一个元素，队尾指针变量针变量R R的值加的值加1 1，每删除一个元素，队头指示变量，每删除一个元素，队头指示变量F F的值加的值加1 1的方法，则经过若干次插入、删除运算后，的方法，则经过若干次插入、删除运算后，尽管队列中的元素个数小于存储空间的容量，但由尽管队列中的元素个数小于存储空间的容量，但由于此时于此时R R可能已指向存储空间的末端，而无法再进行可能已指向存储空

49、间的末端，而无法再进行插入了。解决办法是把队列的存储空间逻辑上看成插入了。解决办法是把队列的存储空间逻辑上看成一个环，当一个环，当R R指向存储空间的末端后，就把它重新置指向存储空间的末端后，就把它重新置成指向存储空间的始端，如下图所示成指向存储空间的始端，如下图所示AABBBCBCDCDECD初态插入A插入B删除A插入C插入D删除B插入EFRFRFRFRFRRFRFFR循环队列循环队列l 将队列存储空间的最后一个位置绕到第一个位置，将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。采用循形成逻辑上的环状空间，供队列循环使用。采用循环队列结构后，有效地解决了环队

50、列结构后，有效地解决了“假溢出假溢出”的问题，的问题，避免了数据元素的移动避免了数据元素的移动l 插入一个新元素rear = mod(rear,m)+1l 删除一个元素front = mod(front,m)+1l front = rear 队列空或满， 增加一个标志变量S循环队列循环队列（续）（续）l 假设标志为S，其状态定义为 0，队列空l S 1，队列不空设初始状态 F=R， S0，插入一个元素后置 S1， 插入操作 If ( F = R ) and ( S = 1 ) ThenERROR (“ 队满！”)；Return;ElseR = mod ( R,m ) + 1;Q(R) = x;

51、S = 1;Endif 删除操作If S = 0 ThenERROR (“ 队空！”)；Return;ElseF mod ( F,m ) + 1;If F = R Then S = 0;Endif三串三串l 串(String)：由零个或多个字符组成的有限序列，一般记作 s=“S0 S1 S2. Sn”l 可以看作一维字符数组，但其长度不恒定，可以作删除、插入操作，在这点上其结构和链表类似。串也可以用链表表示l 子串(Substring)是串的一部分，具有串的一切特征l 字符串在数据处理中是最常用到的数据结构，为了连接、删除、插入操作，用子串有时很方便值为空格字符串的空格串“ ”不等同空串l 值

52、为单个字符的字符串不等同单个字符，如字符串“a”不等同字符a串串(String)(String)的操作的操作l 赋值：s=“student”l 求长度：Len (s)=7l 判等：Equal (s,“stud”)=falsel 联接：Concat(s,“ number”)=“student number”l 定位：Index(s,“d”)=4l 求子串：Substr(s,2,4)=“tud”l 置换l 插入l 删除四树和二叉树四树和二叉树l 树型结构是一类重要的非线性数据结构。在此类树型结构是一类重要的非线性数据结构。在此类结构中，元素之间存在着明显的分层或嵌套关系，结构中，元素之间存在着明显

53、的分层或嵌套关系，它们通常以各种形式的链表作存储结构，树和二它们通常以各种形式的链表作存储结构，树和二叉树是最常用的树型结构叉树是最常用的树型结构l 基本术语基本术语 结点、结点度、根、支、叶结点 子结点、父结点、兄弟结点 树的度、路径、长度、高度、深度 森林、有序、无序 树树l 树结构类似一棵树结构类似一棵倒长的树倒长的树，结构中含有一个类，结构中含有一个类似似“树根树根”的结点和若干类似的结点和若干类似“树叶树叶”的结点的结点以及若干分支结点。树的逻辑结构如图所示以及若干分支结点。树的逻辑结构如图所示树的形式化定义树的形式化定义l 树(Tree)是由一个或多个结点组成的有限集合Tl 其中有

54、一个特定的称为根(Root)的结点l 其余结点可分为m(m0)个互不相交的有限集T1,T2,T3 ,Tml 其中每一个集合本身又是一棵树，且称为根的子树(Subtree）树树l 树的表示，每进一层次加一个括号，同层次用逗号分开。例如： (A(B(E,F),C(G),D(H,I,J)l 一个结点的子树个数称为该结点的度（degree）；树中各结点的度的最大值被定义为该树的度；0棵或多棵不相交的树的集合(通常是有序集)称为森林树结构举例树结构举例 树的存储结构树的存储结构l 数组实现方式（双亲表示法）数组实现方式（双亲表示法）l 链表实现方式（孩子表示法）链表实现方式（孩子表示法） l 二叉链表实

55、现方式（孩子兄弟表示法）二叉链表实现方式（孩子兄弟表示法） 数组实现方式数组实现方式l 用数组存储树的结点信息，在每个结点中附设一用数组存储树的结点信息，在每个结点中附设一个指示器指示其双亲结点在数组中的位置。个指示器指示其双亲结点在数组中的位置。结构结构描述：描述： #define MAXSIZE 100#define MAXSIZE 100 typedef struct PTNode typedef struct PTNode TElemType data TElemType data； int parent int parent ； PTNode PTNode； typedef stru

56、c typedef struc PTNode nodesMAXSIZE PTNode nodesMAXSIZE； int nint n； Ptree Ptree； 数组实现方式数组实现方式链表实现方式链表实现方式l 把每个结点的孩子结点排列起来，组成一个线性把每个结点的孩子结点排列起来，组成一个线性表，且以单链表作为存储结构，则表，且以单链表作为存储结构，则n n个结点有个结点有n n个个孩子链表。孩子链表。结构描述：结构描述： typedef struct CTNode typedef struct typedef struct CTNode typedef struct int child

57、 int child； CTBox nodesMAXSIZECTBox nodesMAXSIZE； struct CTNode struct CTNode * *nextnext： int nint n，r r； * *ChildptrChildptr； Ctree Ctree； typedef struct typedef struct TElemType data TElemType data； Childptr firstchildChildptr firstchild； CTBox CTBox； 链表实现方式链表实现方式二叉链表实现方式二叉链表实现方式l 以二叉链表作为树的存储结构。链

58、表中结点的两以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。个兄弟结点。结构描述：结构描述： typedefstruct CSNode ElemType data； struct CSNode *firstchild ， *netsibling； CSNode，* CSTree； 二叉链表实现方式二叉链表实现方式二叉树二叉树l 二叉树是另一种重要的树形结构，其结构定义为：二叉树(Binary Tree)是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不

59、相交的二叉树组成，如右下图所示AGDCBIHEF二叉树的五种基本形态二叉树的五种基本形态二叉树的性质二叉树的性质l 性质一性质一 二叉树的第二叉树的第i i层上至多有层上至多有2i-1 2i-1 个结点个结点（1=i1=i）利用归纳法证明：利用归纳法证明：只有一个结点，对的；只有一个结点，对的；假设对所有的假设对所有的j j，i=j=1i=j=1，命题成立，即在第，命题成立，即在第j j层上，至多层上，至多有有2j-1 2j-1 个结点。个结点。由归纳假设，第由归纳假设，第i-1i-1层上至多有层上至多有2i-2 2i-2 个结点。由于二叉树的个结点。由于二叉树的每个结点的度至多为每个结点的度

60、至多为2 2，故第，故第i i层上的最大结点数为第层上的最大结点数为第i-1i-1层层上的最大上的最大 结点数的结点数的2 2倍，即倍，即 2X2i-2 = 2i-12X2i-2 = 2i-1。由性质一可见，深度为由性质一可见，深度为k k的二叉树的最大结点数为：的二叉树的最大结点数为：2k-1 2k-1 l 性质二性质二 深度为深度为k k的二叉树上最多含有的二叉树上最多含有2k-12k-1个结点个结点（k = 1k = 1） 二叉树的存储结构二叉树的存储结构 l 顺序存储（一维数组）顺序存储（一维数组） l 记录数组结构记录数组结构 l 链式存储链式存储 二叉链表 三叉链表 顺序存储（一维