第 4 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65

Presentation on theme: "第 4 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65"— Presentation transcript:

1 第 4 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65
第 4 章　 数据结构 65 10 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 865 A B C D E F G 参考书：数据结构 田鲁怀 电子工业出版社 姓名 学号 成绩 班级 李红 机97.6 08版

2 1.1 基本数据结构与算法----1.1.1数据结构的基本概念 （P27）
一.数据结构的定义 1. 数据： 信息载体，能够被计算机识别、存储和加工处理。可以是数值数据(整数、实数)，也可以是非数值数据(声音、图像等) 。 2. 数据项: 是数据的具有独立含义的不可分割的最小标识单位,如成绩表中学号,姓名。 3. 数据元素（ 又称结点、记录) 一个数据元素由若干数据项组成,是数据的基本单位，通常作为一个整体进行考虑和处理。

3 1个数据元素 5个数据项 1个数据项 学号 姓名 系别 住址 电话 981111 李洪 机械 六舍 982111 王刚 电子 四舍 983211 王将 计算机 五舍 983212 张强 六舎 4个数据元素

4 1. 数据对象: 具有相同性质的数据元素的集合。 是数据的一个子集。 例: 成绩表
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 数据对象-由4个记录组成,表中每行是一个记录,每个记录由5个数据项组成. 1. 数据对象: 具有相同性质的数据元素的集合。 是数据的一个子集。 例: 成绩表 学号 姓名 系别 住址 电话 981111 李洪 机械 六舍 982111 王刚 电子 四舍 983211 王将 计算机 五舍 983212 张强 六舎

5 1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 关键码：值唯一能区别不同的　 　　　　数据元素的数据项 学号 姓名 系别 住址 电话 981111 李洪 机械 六舍 982111 王刚 电子 四舍 983211 王将 计算机 五舍 983212 张强 六舎

6 各数据元素之间的逻辑关系 ②数据的存储结构： 各数据元素在计算机中的存储关系 ③对各种数据结构进行的运算： 添加，删除，排序等。
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5.数据结构: 相互之间存在着一种或多种关系的数据元素的集合。 ①数据的逻辑结构： 各数据元素之间的逻辑关系 ②数据的存储结构： 各数据元素在计算机中的存储关系 ③对各种数据结构进行的运算： 添加，删除，排序等。 这三个方面的关系为：( 考点 ) 数据的逻辑结构独立于计算机，是数据本身所固有的 存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。 1)研究 内容

7 二是尽量节省在数据处理过程中所占用的计算机存储空间.
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5.数据结构: 相互之间存在着一种或多种关系的数据元素的集合。 这三个方面的关系为：( 考点 ) 数据的逻辑结构独立于计算机，是数据本身所固有的 存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。 一是提高数据处理的速度. 二是尽量节省在数据处理过程中所占用的计算机存储空间. 2)研究 目的

8 集合——元素间为松散的关系 (属于关系) 线性结构——元素间为一对一关系 树形结构——元素间为一对多关系 图状结构——元素间为多对多关系
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5.数据结构: 相互之间存在着一种或多种关系的数据元素的集合。 集合——元素间为松散的关系 (属于关系) 线性结构——元素间为一对一关系 树形结构——元素间为一对多关系 图状结构——元素间为多对多关系 这三个方面的关系为：( 考点 ) 数据的逻辑结构独立于计算机，是数据本身所固有的 存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。 3)常见的数据结构类型

9 学号 姓名 语文 数学 C语言 1001 张三 85 54 92 1002 李四 84 64 1003 王五 87 74 73 ...

10 树型结构特点——结点间具有分层次的连接关系
线性结构 通迅录、成绩单、花名册 电子字典、家谱、目录 树型结构 树 计算机中的目录结构问题 图状结构 H G F E C D B A H B C D E F G A 树型结构特点——结点间具有分层次的连接关系

11 通迅录、成绩单、花名册 线性结构 树型结构 图形结构 交通线路、通信网络 图形结构特点——结点间的连结是任意的，
电子字典、家谱、目录、计算机中的目录结构问题 树型结构 图形结构 交通线路、通信网络 图形结构特点——结点间的连结是任意的， 数据元素之间存在多个对多个关系。 A E B C D

12 表示数据元素的信息 表示各数据元素之间的前后件关系 4)包含 信息 1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27）
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5.数据结构: 相互之间存在着一种或多种关系的数据元素的集合。 这三个方面的关系为：( 考点 ) 数据的逻辑结构独立于计算机，是数据本身所固有的 存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。 表示数据元素的信息 表示各数据元素之间的前后件关系 4)包含 信息

13 结点: 组成数据结构的数据元素称为一个结点。 前后件关系:
几种基本数据结构的节点图： 根结点 根结点 叶子结点 叶子结点 有关概念(补充): 结点: 组成数据结构的数据元素称为一个结点。 前后件关系: 数据元素之间的固有关系可以用前后件关系(前驱与后继关系)描述。举例：家庭成员辈分关系(父亲、儿子、女儿)，“父亲”是“儿子”和“女儿”的前件， “儿子”和“女儿”是 “父亲”后件。 根节点: 在数据结构中,没有前件的节点称为根结点. 叶子节点: 没有后件的结点称为终端结点或叶子结点

14 数据之间的相互关系，被称为数据的逻辑结构 逻辑结构分类： 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据逻辑结构分为:
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5. 数据 结构 二.数据结构的逻辑结构（P27-P28） 数据的逻辑结构： 数据之间的相互关系，被称为数据的逻辑结构 逻辑结构分类： 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据逻辑结构分为: 线性结构与非线性结构

15 1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5. 数据 结构 二.数据结构的逻辑结构（P27-P28） 线性结构：数据元素之间存在一个对一个的前后次序关系 特点: 有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件 非线性结构：一个数据结构如果不是线性结构，则称之为 非线性结构。 特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如集合、树型、图形结构属于非线性结构。 集合结构: 数据元素间的关系是属于同一个集合 树型结构：数据元素之间存在一个对多个的关系 图形结构：数据元素之间存在多个对多个的关系

16 数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5. 数据 结构 二.数据结构的逻辑结构（P27-P28） 三.数据结构的存储结构（P27-P28） 1.定义： 数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。 数据的逻辑结构是从解决问题的需要出发，为实现必要的功能所建立的数据结构。它属于用户视图，是面向问题的，例如，在选修可成绩系统中建立按成绩排列的有序表。数据的物理结构是指数据在计算机内如何存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图。

17 存储结构研究的是逻辑结构用计算机语言实现，依赖于计算机语言。
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 二.数据结构的逻辑结构（P27-P28） 三.数据结构的存储结构（P27-P28） 1.定义： 2. 特点： 存储结构研究的是逻辑结构用计算机语言实现，依赖于计算机语言。 一种数据结构可以根据需要采用多种不同的存储结构，常用的存储结构有顺序、链接与索引等存储方式。 数据的存储结构不同，解决问题的方法就有所不同，数据处理的效率也是不同的。

18 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为:
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 三.数据结构的存储结构（P27-P28） 1.定义： 2. 特点 线性结构：数据元素之间存在一个对一个的前后次序关系 特点: 有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件 非线性结构：一个数据结构如果不是线性结构，则称之为非线性结构。 特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如树型、图形结构属于非线性结构 3.实现方式： 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为: 线性结构与非线性结构 (1)顺序存储方式： 逻辑上相邻的元素存储在物理位置相邻的存储单元中。 主要用于线性结构。 通常借助于数组来实现。

19 线性表(a1, a2, a3, a4) 存储单元的地址即物理地址 顺序存储结构的线性表 逻辑上相邻的元素存储在物理位置相邻的存储单元中。

20 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为:
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 三.数据结构的存储结构（P27-P28） 1.定义： 2. 特点 线性结构：数据元素之间存在一个对一个的前后次序关系 特点: 有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件 非线性结构：一个数据结构如果不是线性结构，则称之为非线性结构。 特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如树型、图形结构属于非线性结构 3.实现方式： 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为: 线性结构与非线性结构 (1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。 (2)链式存储方式：对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。

21 每个结点由两部分组成：一部分存放数据，另一部 分存储指向前件或后件结点的指针域。 逻辑上相邻的结点物理上不必相连。
指针域：用于存放结点所在的存储单元的地址 线性表(a1, a2, a3, a4) a1,a2在逻辑上相邻,而在机内存储时,存储单元的地址(100,105)并不相邻. 存储单元的地址即物理地址 链式存储结构的线性表 链式存储结构的线性表 链式存储方式特点： 每个结点由两部分组成：一部分存放数据，另一部 分存储指向前件或后件结点的指针域。 逻辑上相邻的结点物理上不必相连。 数据运算(插入和删除等)灵活。

22 顺序存储结构 链式存储结构的线性表 逻辑结构为线性结构的线性表（a1,a2,a3,a4)存储方式比较：
顺序存储结构：逻辑上相邻的结点物理上必相连。 链式存储结构的线性表：逻辑上相邻的结点物理上不必相连。 顺序存储结构 链式存储结构的线性表

23 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为:
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 三.数据结构的存储结构（P27-P28） 1.定义： 2. 特点 线性结构：数据元素之间存在一个对一个的前后次序关系 特点: 有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件 非线性结构：一个数据结构如果不是线性结构，则称之为非线性结构。 特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如树型、图形结构属于非线性结构 3.实现方式： 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为: 线性结构与非线性结构 (1)顺序存储方式： (2)链式存储方式： (3)索引存储方法和散列存储方法： (3)索引存储方法和散列存储方法：(为了查找方便,不要求掌握) 索引存贮: 使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是:(关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。 散列存贮: 通过构造散列函数，用函数的值来确定元素存放的地址。

24 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为:
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一. 数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5. 数据 结构 二. 数据结构的逻辑结构：线性和非线性 三. 数据结构的存储结构：顺序、链式等 线性结构：数据元素之间存在一个对一个的前后次序关系 特点: 有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件 非线性结构：一个数据结构如果不是线性结构，则称之为非线性结构。 特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如树型、图形结构属于非线性结构 四. 数据的运算 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为: 线性结构与非线性结构 定义：在数据的逻辑结构上定义的操作算法 常见运算：插入、删除、查找、排序和更新等 分类： 加工型运算： 运算改变了数据结构的值 引用型运算：不改变值，只查询或求得结构值。 注意：数据的运算定义在逻辑结构上，而具体的实现都要在数据的存储结构上即计算机内进行。

25 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为:
1.1 基本数据结构与算法 1.1.1数据结构的基本概念 （P27） 一.数据结构的定义 1. 数据： 2. 数据项: 3. 数据元素： 1. 数据对象: 5. 数据 结构 二.数据结构的逻辑结构：线性和非线性 三.数据结构的存储结构：顺序、链式等 四.数据的运算:插入、删除、查找、排序等 线性结构：数据元素之间存在一个对一个的前后次序关系 特点: 有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件 非线性结构：一个数据结构如果不是线性结构，则称之为非线性结构。 特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如树型、图形结构属于非线性结构 五.数据类型及其分类 根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为: 线性结构与非线性结构 定义：数据类型是一个值的集合和定义在这个 值集上的一组操作的总称。 例：VB语言中的整型变量，其值为某个区间上整 数，定义在其上的操作为：加，减、乘、除和求余数等算术运算。 2. 分类：（1）非结构的原子类型 （2）结构类型

26 Public Type ID ‘类型名称为ID,包含两个数据项
（1）非结构的原子类型：原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。 （2）结构类型：结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。 VB结构类型举例： Public Type ID ‘类型名称为ID,包含两个数据项 Name As String * ‘存姓名 num as string * ‘存学号 sex as string * ‘存性别 End Type Dim person1 as ID ‘ 定义自定义类型的变量

27 具有特定关系的数据元素集合->数据结构
总结 数据->数据元素 具有特定关系的数据元素集合->数据结构 数据结构的逻辑表示与物理存储->逻辑结构与存储结构 人们不仅关心数据的逻辑结构、存储结构，还关心数据的处理方法（算法）与处理结果->数据类型 数据类型->分类 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

28 首先要从具体问题抽象出一个适当的数学模型； 然后设计一个解此数学模型的算法； 最后采用一种计算机语言编出程序，调试、修改 直至得到最终答案。
1.1 基本数据结构与算法 算法及算法分析 （P30） 一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。 用计算机解决一个具体问题时，大致需要经过下列几个步骤： 首先要从具体问题抽象出一个适当的数学模型； 然后设计一个解此数学模型的算法； 最后采用一种计算机语言编出程序，调试、修改 直至得到最终答案。

29 一. 算法的基本概念 1.1 基本数据结构与算法 1.1.2 算法及算法分析 （P30）
1.1 基本数据结构与算法 算法及算法分析 （P30） 一. 算法的基本概念 1.定义：为解决某个特定问题而采取的确定且有限的步骤。 2.算法特性： 有穷性： 一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。 确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。 可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

30 一. 算法的基本概念 二. 算法的基本要素及描述 1.1 基本数据结构与算法 1.1.2 算法及算法分析 （P30）
1.1 基本数据结构与算法 算法及算法分析 （P30） 一. 算法的基本概念 二. 算法的基本要素及描述 算术运算: 加、减、乘、除 逻辑运算：与、或、非等运算 关系运算：大于、小于、等于等 数据传输：赋值、输入、输出 对数据对象的运算和操作 1.算法基本要素构成 算法的控制结构 顺序 选择 循环（重复） 2. 算法的描述: 自然语言，伪代码，流程图, N-S图, 类C

31 一. 算法的基本概念 二. 算法的基本要素及描述 三. 算法设计要求（评价算法标准） 1.1 基本数据结构与算法
1.1 基本数据结构与算法 算法及算法分析 （P30） 一. 算法的基本概念 二. 算法的基本要素及描述 三. 算法设计要求（评价算法标准） 1.正确性：执行结果应满足预先的功能和性能要求 2.可读性：思路清晰、层次分明、简单明了、易读易懂。 3.健壮性：输入数据非法时，算法能作适当处理，不致于引 起严重后果 4 .效率： 有效使用存储空间和较高的时间效率。

32 四、算法设计的基本方法 1.1 基本数据结构与算法 1.1.2 算法及算法分析 （P30） 1. 列举法：
1.1 基本数据结构与算法 算法及算法分析 （P30） 四、算法设计的基本方法 1. 列举法： 列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的(如用循环解决百元买百鸡问题）。 2. 归纳法： 列举少量简单而又特殊的情况，分析归纳出一般结论。 3.递推法： 从已知初始条件出发，逐步推出各种中间结果和最后结果（如猴子吃桃）。 1. 递归法： 解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合（如求某数的阶乘）。

33 四、算法设计的基本方法P31 5.减半递推技术（分治法）：(补充） 减少：把问题规模减半，而性质不变 递推：重复减半的过程。
1.1 基本数据结构与算法 算法及算法分析 （P30） 四、算法设计的基本方法P31 5.减半递推技术（分治法）：(补充） 减少：把问题规模减半，而性质不变 递推：重复减半的过程。 6. 回溯法 （补充） 在工程上有些实际问题很难归纳出一组简单的递推公式或直关的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”，通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换其他路线再逐步试探。

34 一. 算法的基本概念 二. 算法的基本要素及描述 三. 算法设计要求（评价算法标准） 四. 算法设计的基本方法 五. 算法的分析
1.1 基本数据结构与算法 算法及算法分析 （P30） 一. 算法的基本概念 二. 算法的基本要素及描述 三. 算法设计要求（评价算法标准） 四. 算法设计的基本方法 五. 算法的分析

35 五.算法的分析 1.评价算法标准 算法所占用计算机资源，即时间代价(算法所需要的时间）和空间代价（算法所需要的存储空间）。 算法所需要的时间包括： 源程序进行编译所需要的时间； 计算机执行每条指令所需要的时间； 程序中指令重复执行的次数，而本条正是讨论算法中的重点内容

36 五.算法的分析 2.相关名词： (1)问题规模：不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于项数。 (2)算法运行时间：大致等于其所有语句执行时间 的总和。 (3)语句频度：该语句在算法中重复执行的次数。

37 五.算法的分析 3.算法的时间复杂度： 定义： 算法运行从开始到结束所需要的计算工作量. 说明:
同一个算法使用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同,这表明使用绝对的时间单位衡量算法的效率是不合适的,撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法 “运行工作量”的大小,只依赖于问题的规模(通常用整数n表示),它是问题的规模函数,即 算法的工作量=f(n)

38 单个语句的频度为1，则 程序段的时间复杂度为
五.算法的分析 3.算法的时间复杂度： 定义： 一个算法是由控制结构和原操作构成的，则算法时间取决于两者的的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题(或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。 2）表示： T (n)：算法中所有语句频度之和 n：问题规模。 T (n) 是n的某个函数。 O：数量级。 当问题规模趋向无穷时， T (n)的数量级称为时间复杂度。 T (n)=O( f (n) ) ********************************ghkhj <例1> x=X+5; 单个语句的频度为1，则 程序段的时间复杂度为 T(n)=O(1)

39 五.算法的分析 3.算法的时间复杂度： 定义： 一个算法是由控制结构和原操作构成的，则算法时间取决于两者的的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题(或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。 2）表示： T (n)：算法中所有语句频度之和 n：问题规模。 T (n) 是n的某个函数。 O：数量级。 当问题规模趋向无穷时， T (n)的数量级称为时间复杂度。 T (n)=O( f (n) ) <例2> … For i=0 TO n For j=0 to n a(i,j)=i*j next j next i 则：T(n)= O(n2) 最优算法：随n的增大， T (n)增长较慢的算法。

40 3）平均时间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 4）最坏时间复杂度：最坏情况下算法的时间复杂 度。
五.算法的分析 3.算法的时间复杂度： 定义： 2）表示： 3）平均时间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 4）最坏时间复杂度：最坏情况下算法的时间复杂　 　　　　　　　　　　度。

41 五.算法的分析 3.算法的时间复杂度： 1.算法的空间复杂度： 定义：算法运行从开始到结束所需的存储空间量,包括 固定部分和可变部分。 固定部分：此部分空间与所处理数据的大小和规模无关。通常用来保存本身所用的程序代码、常量、变量等。 可变部分：此部分空间与处理的数据的大小和规模有关，即执行算法时所需额外空间。

42 1.1 基本数据结构与算法思考题 研究数据结构的目的是什么？ 数据结构研究哪三方面的问题?关系如何?
1.1 基本数据结构与算法思考题 研究数据结构的目的是什么？ 数据结构研究哪三方面的问题?关系如何? 在数据结构中数据项、数据元素及数据对象的关系？ 数据的逻辑结构分为哪两大类？各有何特点？ 数据的存储结构中的顺序存储与链式存储各有什么特点？ 什么是算法？有何特点？ 算法设计的基本要求？ 算法设计的方法？ 如何评价算法？ 什么是时间复杂度？时间复杂度与哪些因素有关？ 什么是空间复杂度？包括哪两部分？

43 1.1数据结构与算法补充习题讲解 1.数据处理的最小单位是______。 A. 数据 B. 数据元素 C. 数据项 D. 数据结构 2. 数据结构中，与所使用的计算机无关的是数据的______。 A. 存储结构 B. 物理结构 C. 逻辑结构 D. 物理和存储结构 下面叙述正确的是______。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 1. 算法的时间复杂度是指______。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 5. 算法的空间复杂度是指______。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间 CCCCD

44 1.1数据结构与算法补充习题讲解 6. 算法一般都可以用哪几种控制结构组合而成______。 A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环 7.数据的存储结构是指______。 (05.4月） A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 8. 在下列选项中，哪个不是一个算法应该具有的基本特征______。 A. 确定性 B. 可行性 C. 无穷性 D. 健壮性 9. 在计算机中，算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 10. 算法分析的目的是______。 A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系 C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进 DDCCD

45 11.算法具有五个特性，以下选项中不属于算法特性的是______。(05.4月） A）有穷性 B）简洁性 C）可行性 D）确定性
1.1数据结构与算法补充习题讲解 11.算法具有五个特性，以下选项中不属于算法特性的是______。(05.4月） A）有穷性 B）简洁性 C）可行性 D）确定性 12. 下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 13. 算法复杂度主要包括时间复杂度和 【2】 复杂度。 （05.9月） 11. 问题处理方案的正确而完整的描述称为 【5】 。 (05.4月） A-1：（1.5学时） BD 空间复杂度、算法

46 1.2 线性表 L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 1.2.1 线性表的基本概念 (P32)
1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限 序列。是最简单、最常用的数据结构。 2) 表示: L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 表头 表尾 其中: n为线性表长度(n=0称为空表)，表中相邻元素之间存在着顺序关系。a1 ：表头元素；an ：表尾元素；ai-1称为ai的直接前驱；ai+1 称为ai的直接后继。

47 1.2 线性表 L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) (1)有且只有一个根结点a1，无前驱 。
1.2.1 线性表的基本概念 (P32) 1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 3) 线性结构特点: (1)有且只有一个根结点a1，无前驱 。 (2)有且只有一个终端结点an ，无后继 。 (3)其他结点有且只有一个直接前驱和一个直接后继。

48 1.2 线性表 L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 1.2.1 线性表的基本概念 (P32)
1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 3) 线性结构特点: 4) 线性表的分类 (1)简单线性表： 数据元素是简单项(数字、字母、季节名等)。 如:(12,34,4,67,8) (2)复杂线性表： 数据元素由若干个数据项组成，此时数据元素称为记录或节点, 如学生成绩表.

49 例2、学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20
例1、26个英文字母组成的字母表 （A，B，C、…、Z） 简单线性表 复杂线性表 例2、学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 21 张立立 790634 17 神经衰弱 …….. …….

50 1.2 线性表 顺序存储结构特点 表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放 1.顺序表基本概念 顺序表：
1.2.2 线性表的顺序存储结构 1.顺序表基本概念 1) 顺序存储结构： 用一组地址连续的存储空间依次存放线性表的各元素 。 顺序存储结构特点 表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放 顺序表： 采用顺序存储结构的线性表称为顺序表(一维数组)

51 1.2 线性表 1.顺序表基本概念 1.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2) 第i个元素地址 其中:
m：每个元素占m个存储单元 Loc(a1)第一个元素地址(基址) 对数组而言

52 对数组而言： 1 2 n m：每个元素占m个存储单元 存储地址 存储状态 数据元素在线性表中的位序 b an …….. ai a1 a0
从存取方式看,线性表的顺序存储结构是可以随机存储的存储结构. b+m b+i*m i-1 n b+n*m 空闲 m：每个元素占m个存储单元

53 注意：第6个元素，i=5 LOC（a5)=200+5×4=220 200 a0
例 .某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为 200,则第6个元素的存储地址是_______ A B. 224 C D. 216 204 208 212 216 220 分析：用数组实现，则按如下公式计算 注意：第6个元素，i=5 LOC（a5)=200+5×4=220

54 1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 1.2.2 线性表的顺序存储结构 1) 顺序存储结构：
存取: 访问线性表的第i个元素，使用或改变数据元素 的值。 查找: 在线性表中查找满足某种条件的数据元素。 插入: 在线性表的第i个元素之前，插入一个同类型的 元素。 (***) 删除: 删除线性表中第i个元素。 (***) 求表长: 求出线性表中元素的个数。 置空表: 建立一个空表。 清除表: 将已有线性表变为空表，即删除表中所有元素。 2) 第i个元素地址

55 1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 ….. … 先移动 后插入 ….. … … … 1.2.2 线性表的顺序存储结构
1) 顺序存储结构： 2.顺序表的基本运算 ——插入和删除 2) 第i个元素地址 1)顺序表的插入运算: 在线性表的第i个元素之前插入一个新的元素，先移动，后插入。 x ai-1 ….. a2 a1 an … ai+1 ai 先移动 后插入 ai-1 ….. a2 a1 ai … an ai x … ai+1 an …

56 (1)将ai ~ an顺序向后移动,为新元素让出位置 (2)将x置入空出的第i个位置
步骤： (1)将ai ~ an顺序向后移动,为新元素让出位置 (2)将x置入空出的第i个位置 举例：(在第4个和第5个元素之间插入元素91) 67 41 26 21 4 8 9 16 67 41 26 21 4 8 9 16 67 41 26 21 4 8 9 16 91

57 <例>在一线性表(a1,a2,a3)中插入任意一数i，求平 局移动元素次数:
插入运算时间性能分析： 插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，则平均移动元素次数(期望值)： <例>在一线性表(a1,a2,a3)中插入任意一数i，求平 局移动元素次数: pi：在第i个位置上作插入的概率。 在第i个位置上作插入x,则需将第i个至第n个元素移动，即共需移动(n-i+1)个元素。 (n-i+1) i 移动次数(n-i+1) 1(插入到第1个数a1前) 2 (插入到第2个数a2前) 3 (插入到第3个数a3前) (插入到第3个数a3后) 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 等差数列求和公式: ((首项+末项)×项数)/2 线性表(a1,a2,a3)平局移动元素个数: (¼)*( )=1.5

58 1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 2)顺序表删除运算： 定义：指将表中第i个元素从线性表中去掉。
1.2.2 线性表的顺序存储结构 1.顺序表基本概念 1) 顺序存储结构： 2.顺序表的基本运算 ——插入和删除 2) 第i个元素地址 2)顺序表删除运算： 定义：指将表中第i个元素从线性表中去掉。 原表长为n：( a1，a2，…ai-1，ai ，ai+1， … an ) 新表长为n-1：( a1，a2，…ai-1，ai+1， …， an ) 步骤： (1)删除ai (2)将ai+1 ~ an， 顺序向前移动

59 时间消耗与插入运算相同，平均移动元素次数：
举例：(删除第五个元素21) 67 41 26 21 4 8 9 16 67 41 26 4 8 9 16 时间性能分析： 时间消耗与插入运算相同，平均移动元素次数： qi:在第i个位置上作插入的概率。设qi=1/n 共需移动(n-i)个元素。

60 <例>在一线性表(a1,a2,a3)中删除任意一数i，求平局移动元素次数:
i 移动次数(n-i) 1(删除第1个数a1) 2 (删除第2个数a2) 3 (删除第3个数a3) 线性表(a1,a2,a3)平局移动元素个数: (1/3)*(2+1+0)=1

61 1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 3.顺序表优点和缺点 优点：
1.2.2 线性表的顺序存储结构 1.顺序表基本概念 2.顺序表的基本运算 3.顺序表优点和缺点 优点： 逻辑上相邻元素存储位置也相邻,无需增加额外存储空间可方便随机存取表中任一元素。 缺点： 插入和删除运算不方便,必须移动大量结点,效率较低不适合元素经常变动的大的线性表。

62 1.2 线性表 定义：线性表的链式存储结构称为线性链表 数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 定义：线性表的链式存储结构称为线性链表 存储空间可以不连续。 不要求逻辑上相邻的元素在物理位置上也相邻。 数据元素间逻辑关系由指针域确定。 线性链表中 结点组成： 数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的 前一个结点或后一个结点 分类：单链表、循环单链表、双向链表

63 例如：若头指针名是head，则把链表称为表head。
<例>有一线性表: (bat，cat，eat，fat，hat，jat，lat，mat) bat cat eat mat ^ … 其单链表示意图如下： 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 ……… …… hat 200 ……. cat 135 eat 170 …. mat Null bat 130 fat 110 jat 205 lat 160 …… 110 130 135 160 头指针 head 170 200 205 例如：若头指针名是head，则把链表称为表head。 165

64 1.2 线性表 3 .单链表: 例：线性单链表( A, B, C, D, E, F ) 1.2.3 线性表的链式存储结构 链式存储结构特点:
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 定义：由n个结点链接，且每个结点中只包含一个指针域的链表。 例：线性单链表( A, B, C, D, E, F ) 逻辑状态 A B C D E head F 其中: head称为单链表的头指针,指向表中的第一个节点

65 1.2 线性表 物理状态 1.2.3 线性表的链式存储结构 A B C D E F 头指针 存储地址 数据域 指针域 19 1 7 13
线性表的链式存储结构 head A B C D E F 物理状态 头指针 存储地址 数据域 指针域 19 1 7 13 19 25 31 E 7 F NULL B 25 A 13 C 31 D 1 单链表存取:必须从头指针开始进行，依次顺着指针向链尾方向扫描。找到各个元素,因此说线性表的链式存储结构是一种顺序存储的存储结构。

66 1.2 线性表 带头节点的单链表 1.2.3 线性表的链式存储结构 A B C D E F A B C D E F head head
线性表的链式存储结构 head A B C D E F head A B C D E F 带头节点的单链表 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

67 1.2 线性表 3 .单链表: 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表: (1)单链表插入：
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: (1)单链表插入： 不需要移动结点，只需要修改链接结点的指针域，从而实现插入。

68 例：在指针p所指结点之后插入一个指针s所指的结点 关键点：修改p和s所指结点的指针域的指针即可
插入步骤： 修改s指针域,使其指向p结点的后继结点:snext=pnext 修改p指针域, 使其指向新结点s: pnext＝s p A B C X s

69 1.2 线性表 3 .单链表: 删除结点 删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可 1.2.3 线性表的链式存储结构
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: (2)单链表删除：不需要移动结点,仅修改指针链接 删除结点 删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可

70 删除p结点，修改q结点指针域 qnext＝pnext
删除结点的步骤 先找到p的前驱结点q 删除p结点，修改q结点指针域 qnext＝pnext C p B A 删除前 free(p); p q C B A 删除后

71 1.2 线性表 3 .单链表: 1.循环链表 特点：表中最后一个结点的指针域指向头结点，整 个链表首尾相连形成一个环。
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 1.循环链表 特点：表中最后一个结点的指针域指向头结点，整 个链表首尾相连形成一个环。 带头节点的循环链表

72 优点：从表中任一结点出发均可找到表中其它结点。
对带头结点的单循环链表head为空的判定条件是 head->next=head 带头结点的空循环链表

73 1.2 线性表 3 .单链表: 1.循环链表 5.双向链表 定义：在双向链表中，每个结点有两个指针域，next
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 1.循环链表 5.双向链表 定义：在双向链表中，每个结点有两个指针域，next 指向后继结点，prior指向前趋结点。 data prior next 结点构成：

74 作用：可以方便地沿向前或向后两个方向查找。克服单链表中每个结点只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找的不足。
next head ... an a2 a1 prior

75 1.2 线性表 3 .单链表: 1.循环链表 5.双向链表 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表:
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 1.循环链表 5.双向链表 (1)插入结点：在p指针所指的结点后插入一个结点q，只需要修改p,q结点的prior和next域即可。 p 插入前 c b a x 待插入的结点:q

76 ①p结点作为q结点的前驱:q->prior=p；
a b c ④ ① ② ③ x q 确定新结点q的前驱和后继 ①p结点作为q结点的前驱:q->prior=p； ②p结点的后继作为q结点的后继:q ->next=p->next； ③q结点作为p 结点的后继结点的前驱结点:p->next->prior=q ④q结点作为p结点的后继:p->next=q； (p的后继指向新结点q)

77 1.2 线性表 3 .单链表: 1.循环链表 5.双向链表 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表:
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 1.循环链表 5.双向链表 (2)删除结点：删除P指针所指结点，只需修改P指针的前驱和后继结点的next，prior域即可。 p 删除前 c b a

78 p ① a b c ② ① p的后继结点作为p结点前驱结点的后继 (a c) p->prior->next = p->next； ② p的前驱结点作为p结点后继结点的前驱 ( a c) p->next->prior= p->prior； free(p)；

79 <例>一叠书或一叠盘子。 栈顶 …… 栈底 an an-1 ············ a2 a1 栈s=(a1,a2,…，an)
一种操作受限的线性表 ············ 只允许在表的一端进行插入和删除 a2 栈底 a1

80 1.3栈和队列 1.栈的定义 1.3.1 栈 定义：只允许在线性表的一端进行插入和删除的线性表。 假设栈：s=(a1,a2,…，an)
与栈有关的相关术语： 入栈 出栈 (1)栈顶： 允许插入与删除的一端称为栈顶 (2)栈底： 不允许插入与删除的一端称为栈底 (3)入栈：栈的插入操作(往栈中插入一个元素) (4)出栈：栈的删除操作(从栈中删除一个元素) (5) 栈顶指针：记录元素位置的变量(Top) (6) 栈顶元素：处于栈顶位置的数据元素 (7) 空栈：不含任何数据元素的栈(Top=0) (8) 栈满： Top=m(m为栈最大容量) 栈顶 a1 a2 …. an 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。 栈底

81 栈示意图： 栈顶元素总是最后入栈，而最先出栈的 栈底元素总是最先入栈，而最后出栈的 a1 a2 …. an 入栈 出栈 栈顶 栈底
修改栈的原则：(考点) 先进后出(FILO, First In Last Out)或后进先出(LIFO) 栈顶元素总是最后入栈，而最先出栈的 栈底元素总是最先入栈，而最后出栈的

82 堆栈操作 初始 A 进 B A 进 A 出 C A 进 A 出 D A 进 A 出 出 出栈元素顺序： B → C → D → A

83 1.3栈和队列 1.栈的定义 2.顺序栈及其运算 顺序栈：顺序存储结构的栈称为顺序栈。 链栈： 链式存储结构栈称为链栈。 1.3.1 栈
1)栈的两种存储结构 顺序存储结构：利用一组地址连续的存储单元依次存放自 栈底到栈顶的数据元素。 链式存储结构：用于收集计算机存储器中所有空闲存储空 间,来保存自栈底到栈顶的数据元素。 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top 顺序栈：顺序存储结构的栈称为顺序栈。 链栈：　链式存储结构栈称为链栈。

84 top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow)
顺序栈 实现：一维数组data[M] 注意：数组是倒过来图示的。故，top指向的是其箭头上面的存储空间 栈满 栈空 top top top=0 1 2 3 4 5 栈空 F 1 2 3 4 5 1 2 3 4 5 A B C D E F top top E top top D top top C top top B top top A top 顺序栈，即栈的顺序存储结构，利用一组地址连续的存储单元一次存放从栈顶到栈底之间的数据元素，同时利用一个变量记录当前栈顶的位置（下标或指针），成为栈顶指针， 栈顶指针并不一定是指针变量，也可以是下标变量。为了用C语言描述方便，在此约定，用下标变量记录栈顶的位置，栈顶指针始终指向栈顶元素的上一个位置！在初始化栈时，栈顶指针值为0，表示空栈， 进栈 出栈 设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow) 栈顶指针top,指向实际栈顶 后的空位置，初值为0

85 注意: 栈顶指针指向存储空间最后一个位置时，栈已满，不能再入栈。称为栈“上溢”错误.
1.3栈和队列 1.3.1 栈 1.栈的定义 2.顺序栈及其运算 1)栈的两种存储结构（顺序栈和链栈） 2)顺序栈的基本运算： 入栈、退栈与读栈顶元素 (1)入栈 栈顶指针top加1 新元素插入到栈顶指针指向位置 上溢是一种出错状态，应该设法避免之 步骤： 注意: 栈顶指针指向存储空间最后一个位置时，栈已满，不能再入栈。称为栈“上溢”错误.

86 栈顶指针为0时,栈空,不能再退栈。称为栈“下溢”错误
1.3栈和队列 1.3.1 栈 1.栈的定义 2.顺序栈及其运算 1)栈的两种存储结构 2)顺序栈的基本运算： 入栈、退栈与读栈顶元素 (2)出栈 栈顶元素赋给一个指定的变量 栈顶指针top减1 下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。 步骤： 栈顶指针为0时,栈空,不能再退栈。称为栈“下溢”错误

87 1.3栈和队列 1.栈的定义 2.顺序栈及其运算 1.3.1 栈 1)栈的两种存储结构 2)顺序栈的基本运算： 入栈、退栈与读栈顶元素
(3)读栈顶元素 概念：将栈顶元素赋给一个指定变量 注意：不删除栈顶元素，栈顶指针不会改变

88 1.3栈和队列 1.3.2 队列 定义：指允许在一端插入,而在另一端进行删除的线性表。 与队列有关的相关术语:
(1)队尾：允许插入的一端称为队尾。 rear队尾指针，指向队尾元素的下一个位置 (2)队头：允许进行删除的一端称为队头。 front队头指针，指向队头元素。 (3)入队列：队列插入操作(进队列) 首先将队尾指针进一（即rear=rear+1), 然后将新元素插入到队尾指向的位置。 (4)出队列：队列的删除操作(退队列) 首先将队头指针进一（即front=front+1), 然后将队头指向的元素赋给指定的变量。 (5)空队列：队列中无数据元素 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 　　例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 　　当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。

89 … 1.3栈和队列 1.3.2 队列 定义：指允许在一端插入,而在另一端进行删除的线性表。 a1 ai a2 an 队头 队尾
从对头出队 a1 ai a2 an … 从对尾入队 队头 队尾 队列结构示意图：队列Q=(a1，a2, …, an ) 队列修改原则：先进先出(FIFO)或后进后出(LILO) 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 　　例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 　　当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。 队头元素总是最先进队列的,也总是最先出队列 队尾元素总是最后进队列,也是最后出队列 新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。

90 队头指针front：指向单链表的第一个结点
1.3栈和队列 1.3.2 队列 定义：指允许在一端插入,而在另一端进行删除的线性表。 链队列: 用链表表示的队列。（或队列的链式存储结构） 队头指针front：指向单链表的第一个结点 队尾指针rear: 指向单链表的最后一个结点 a1 a2 ··· Q.front an ^ Q.rear 具有n个元素的队列

91 新元素入队时插在头结点之后,修改队尾rear指针
删除一个元素时,修改队头指针front指针。 Q.front a1 Q.front ^ Q.rear Q.rear a1入队列 空队列：头指针和尾指针均指向头结点

92 新元素入队时插在头结点之后,修改rear指针
删除一个元素时,修改front指针。 Q.front a1 a2 ^ Q.rear 队列中有两个数据元素 删除唯一元素时, front与rear 回缩到头结点，为空队列。 Q.front Q.rear

93 1.3栈和队列 1.3.2 队列 定义：指允许在一端插入,而在另一端进行删除的线性表。 2.链队列: 用链表表示的队列。 3.顺序队列
2.链队列: 用链表表示的队列。 3.顺序队列 定义：队列的顺序存储结构称为顺序队列，利用一组地址连续的存储单元依次存放队列中的数据元素。 约定：初始化队列令front=rear=0 ①入队时：将新元素插入rear所指的位置，然后将rear加1。 ②出队时：删去front所指的元素，然后将front加1。 在非空队列中 头指针front始终指向队列头元素 尾指针指向队尾元素的下一个位置

94 ①入队时：将新元素插入rear所指的位置，然后将rear加1。 ②出队时：删去front所指的元素，然后将front加1
举例：顺序队列头尾指针变化情况 5 4 3 2 1 5 4 3 2 1 Q.rear D Q.rear C Q.rear B Q.rear A Q.front→ Q.rear Q.front→ Q.rear 空对列 ABCD 相继入队 front=rear=0 ①入队时：将新元素插入rear所指的位置，然后将rear加1。 ②出队时：删去front所指的元素，然后将front加1

95 队未满,却不能再入队，假溢出 举例：顺序队列头尾指针变化情况 出队 空队列 入队 front=rear=0 Q.rear 5 4 3 2 1
5 4 3 2 1 F Q.rear E Q.rear D Q.front→ C Q.front→ B Q.front→ A Q.front→ Q.rear Q.front→ 出队 空队列 入队 front=rear=0 "假上溢"现象 　　由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。 "真上溢"现象     　当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

96 1.3栈和队列 顺序队列缺点： 1.3.2 队列 定义：指允许在一端插入,而在另一端进行删除的线性表。 2.链队列: 用链表表示的队列。
2.链队列: 用链表表示的队列。 3.顺序队列 顺序队列缺点： 有“假溢出”现象，为克服这点，引入循环队列。 1.循环队列 定义： 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环形空间。 队列简单应用：利用队列解决运行程序与键盘处理程序异步操作问题：设置循环的键盘缓冲区，键盘处理程序把从键盘上输入的字符依次存放到缓冲区中，若运行程序需要数据时，再按照先进先出的原则依次从缓冲区取出输入的字符。这样就可以使原形程序与键盘处理程序协调工作。显然，键盘缓冲区中所存储的数据就是一个循环队列。利用队列可以解决主机与打印机之间速度不匹配问题。

97 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环形空间。
Q.rear 入队 Q.rear 4 3 2 1 Q.front D 对应为： A 4 D C 3 Q.front→ 1 2 B Q.rear B Q.front→ A C Q.rear Q.front→ Q.rear Q.front 出队 Q.front Q.rear 循环队列： 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环形空间。

98 方法一： if Q.rear+1=5 Q.rear=0; else Q.rear=Q.rear+1
队尾指针指出数组外 Q.rear 入队 若用循环队列： Q.rear 4 3 2 1 E E Q.rear Q.rear D 对应为： 4 D C 3 Q.front→ 1 2 C Q.rear 方法一：     if Q.rear+1=5         Q.rear=0;     else         Q.rear=Q.rear+1 endif 出队 关键问题：是如何让rear（等于4）加1之后能够回退到0 Q.front 即 队未满,却不能再入队，假溢出 方法二：利用“求余运算"    Q.rear=(Q.rear+1)%5；

99 M: 数组存储空间的长度 队满：Q.rear=Q.front 但是 入队 对应为： F G G F 出队 继续入队 考虑出队情况
4 3 2 1 E E Q.rear Q.front D 对应为： 4 F D C 3 Q.front→ Q.rear 1 G Q.front 2 G Q.rear F C Q.rear Q.rear Q.front 出队 继续入队 考虑出队情况 因此，少用一个存储空间;约定以“队列头指针Q.front在队列尾指针Q.rear的下一位置上。 即队满条件就变为： (Q.rear+1)%M=Q.front Q.front Q.front Q.rear 队空：Q.rear=Q.front M: 数组存储空间的长度

100 E E F 4 4 F D 3 D 3 1 1 2 2 G C C Q.rear Q.front Q.front Q.rear 队满

101 队列简单应用： 利用队列解决运行程序与键盘处理程序异步操作问题： 设置循环的键盘缓冲区，键盘处理程序把从键盘上输入的字符依次存放到缓冲区中，若运行程序需要数据时，再按照先进先出的原则依次从缓冲区取出输入的字符。这样就可以使原形程序与键盘处理程序协调工作。显然，键盘缓冲区中所存储的数据就是一个循环队列。 利用队列可以解决主机与打印机之间速度不匹配问题。

102 总结 栈 队列 顺序栈 顺序队列 循环队列 指针 基本 运算 空与 满 上溢与 下溢 上溢:队满,不能入队 下溢:队空,不能退队 同左
m为存储空间长度 总结 栈 队列 顺序栈 顺序队列 循环队列 同左 top:指向栈顶 bottom:指向栈底 front:队头元素 rear: 队尾元素的下一个位置 指针 基本 运算 空与 满 上溢与 下溢 同左 可解决”假溢出” 入栈:top加1 出栈:top减1 入队: 队尾rear加1 出队:队头front加1 队空: front= rear 队满 (rear+1)%m=front 栈空:top=0 栈满:top=m 队空: front= rear=0 队满: rear=m 上溢:队满,不能入队 下溢:队空,不能退队 栈顶已满,不能入栈 栈空,不能退栈

103 1.2 线性表1.3 栈和队列补充习题讲解 1. 线性表的顺序存储结构和线性表的链式存储结构分别是______。
1.2 线性表1.3 栈和队列补充习题讲解 1. 线性表的顺序存储结构和线性表的链式存储结构分别是______。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构 2. 以下不是栈的基本运算的是_____ A) 删除栈顶元素 B) 删除栈底元素 C) 判断栈是否为空 D) 将栈置为空栈 3. 下列叙述中正确的是______。 A. 线性表是线性结构 B. 栈与队列是非线性结构 C. 线性链表是非线性结构 D. 二叉树是线性结构 1. 以下数据结构中不属于线性数据结构的是______。 A. 队列 B. 线性表 C. 二叉树 D. 栈 BBAC

104 1.2 线性表1.3 栈和队列补充习题讲解 下列关于栈的叙述中正确的是______。
1.2 线性表1.3 栈和队列补充习题讲解 下列关于栈的叙述中正确的是______。 A. 在栈中只能插入数据 B. 在栈中只能删除数据 C. 栈是先进先出的线性表 D. 栈是先进后出的线性表 6. 下列关于队列的叙述中正确的是______。 A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 7. 在长度为64的有序线性表中进行顺序查找，在最坏情况下所需要的比较次数为______。(06年9月) A B C D. 7 8. 栈和队列的共同点是______。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 DCBC

105 1.2 线性表1.3 栈和队列补充习题讲解 9 用链表表示线性表的优点是______。
1.2 线性表1.3 栈和队列补充习题讲解 9 用链表表示线性表的优点是______。 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取 10.某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为 200,则第12个元素的存储地址是_______. A B C D. 244 11.按照“后进先出”原则组织数据的数据结构是(06.4月) A)队列 B)栈 C)双向链表 D)二叉树 12.下列叙述中正确的是( 06.4月) A)线性链表是线性表的链式存储结构 B)栈与队列是非线性结构 C)双向链表是非线性结构 D)只有根结点的二叉树是线性结构 ADBA

106 1.2 线性表1.3 栈和队列补充习题讲解 13. 下列关于栈的描述中错误的是______。(05.4月） A） 栈是先进后出的线性表 B） 栈只能顺序存储C） 栈具有记忆作用 D） 对栈的插入与删除操作中，不需要改变栈底指针 11. 下列关于栈的描述正确的是______。(05.9月） A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除 元素 15. 下列对于线性链表的描述中正确的是______。(05.4月 ） A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 BCA

107 3.数据结构分为逻辑结构和存储结构，循环队列属于 ———— 结构。（05.9月）
1.2 线性表1.3 栈和队列补充习题讲解 填空题:(06.9月) 1.按 “先进后出”原则组织数据的数据结构是___.(06.9月) 2.数据结构分为线性结构和非线性结构,带链的队列属于_______. (06.9月) 3.数据结构分为逻辑结构和存储结构，循环队列属于 ———— 结构。（05.9月） 栈、线性结构、存储结构

108 1.4 树与二叉树 树的定义和基本术语 树型结构是一类重要的非线性数据结构，元素结点间存在明显的分支和层次关系。现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。 A D H I T3 J M B E L K T1 F C G T2 树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。

109 1.4 树与二叉树 1.1.1 树的定义和基本术语 1.树的定义 概念：树是n（n≥0）个结点构成的有限集合。
1.4 树与二叉树 树的定义和基本术语 1.树的定义 概念：树是n（n≥0）个结点构成的有限集合。 n=0为空树；n≠0时，树中结点应该满足两个条件 （1）有且仅有一个特定的根的结点。 （2）其余的n-1个结点可划分为m（m＞0）个互不相交的有限集T1，T2，…，Tm，其中Ti又是一棵树，称为根的子树。 示意图： T1＝{B，E，F，J，K} T2＝{C，G} T3＝{D，H，I，L} T3 T1 T2

110 1.4 树与二叉树-1.1.1 树的定义和基本术语 2.树的基本概念(相关术语) 4）叶子结点(终端结点): 没有子结点(后继)的结点。
1.4 树与二叉树 树的定义和基本术语 2.树的基本概念(相关术语) 1）根结点: 没有前驱的结点只有一个,称为根结点。 2）双亲（父）结点: 树中每个结点只有一个直接前驱,称为该结点 的双亲结点或父结点。 3）孩子（子）结点：一个结点的子树的根或者后继结点数称为该节 点的孩子结点或子结点。 4）叶子结点(终端结点): 没有子结点(后继)的结点。 A B C D E F G H I J K L A: 是根结点,同时是B、C、D结 点的父结点或双亲结点 B: 是E、F的父结点，E、F是B 的子结点或孩子结点 J、K、L、F、G、I：是叶子节点

111 1.4 树与二叉树-1.1.1 树的定义和基本术语 2.树的基本概念(相关术语) 5）兄弟：同一个双亲的孩子结点之间互称兄弟。
1.4 树与二叉树 树的定义和基本术语 2.树的基本概念(相关术语) 5）兄弟：同一个双亲的孩子结点之间互称兄弟。 6）堂兄弟：其双亲在同一层的结点互为堂兄弟。 7）结点的祖先：结点的祖先是从根到该结点所经分支的所有 结点。 8）结点的子孙：以某结点为根的子树中的任一结点都称为该 结点的子孙。 B的子孙为 E、F、J、K。 B,C,D互为兄弟 A B C D E F G H I J K L G与E、F、H、I互为堂兄弟结点 例：L的祖先为A、D、H。

112 1.4 树与二叉树-1.1.1 树的定义和基本术语 2.树的基本概念(相关术语)
1.4 树与二叉树 树的定义和基本术语 2.树的基本概念(相关术语) 9) 结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第k层，则其子树的根就在第k+1层。 10) 结点的度:一个结点的子树的个数(拥有后继的个数)。 11) 树的度: 所有结点度的最大值。 12）树的深度或高度：树中结点的最大层次称为树的深度。 A B C D E F G H I J K L 结点A的层次：1 结点L的层次：4 结点的度: A的度为3；C的度为1 F的度为0 树的度： 3 树的深度： 4 注意: 一棵树中,每个节点的度数之和=节点总数-1=数中边的条数

113 14）森林：是m（m≥0）棵互不相交的树的集合。对树中根结点而言，其子树的集合即为森林。由此，可用森林和树相互递归的定义来描述树。
1.4 树与二叉树 树的定义和基本术语 2.树的基本概念(相关术语) 13）有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树。否则为无序树。在有序树的最左边的根称为第一个孩子，最右边的称为最后一个孩子。 14）森林：是m（m≥0）棵互不相交的树的集合。对树中根结点而言，其子树的集合即为森林。由此，可用森林和树相互递归的定义来描述树。 因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂，所以引出二叉树的讨论。

114 1.4 树与二叉树- 1.1.2二叉树的定义和基本术语 1.二叉树的定义
1.4 树与二叉树 二叉树的定义和基本术语 1.二叉树的定义 定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 特点：每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 二叉树的五种基本形态（考点） 左右子树均非空 右子树为空 左子树为空 仅有 根结点 空二叉树

115 21-1 + 2 2-1+……+ 2 k-1 = 1*(1-2k)/(1-2)= 2 k-1 (k 1)
1.4 树与二叉树 4 2 3 1 5 6 7 8 9 10 11 12 13 14 15 二叉树 1.二叉树的定义 2.二叉树的性质 性质1：二叉树的第i层上至多有2 i-1（i 1）个结点。 性质2：深度为k的二叉树中至多2k-1个结点。 证明： 深度为k的二叉树最多有k层，根据性质1，只要将第1层到第k层的最大结点数相加，就可得到整个二叉树中结点的最大值。 ……+ 2 k-1 = 1*(1-2k)/(1-2)= 2 k-1 (k 1) 等比数列求和公式： Sn=a1(1-qn)/(1-q) : a1为首项 q:公比 n:项数

116 1.4 树与二叉树 1.1.2 二叉树 1.二叉树的定义 叶子结点：n0=3 度为2的结点： n2=2 2.二叉树的性质
1.4 树与二叉树 A B C D E F 二叉树 1.二叉树的定义 叶子结点：n0=3 度为2的结点： n2=2 2.二叉树的性质 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。 证明： (1)结点总数 n=n0+n1+n2 (n1是度为1的结点数) (2)进入分支总数m(每个结点唯一分支进入) n=m+1 (3)m个分支是由非叶子结点射出 m=n1+2n2 最后得:n0＝n2＋1

117 1.4 树与二叉树 1.1.2 二叉树 1.二叉树的定义 2.二叉树的性质 满二叉树
1.4 树与二叉树 二叉树 1.二叉树的定义 2.二叉树的性质 满二叉树 定义：如果一个二叉树深度为K，结点数为2k-1，则称为满 二叉树 特点：除最后一层外，每一层所有结点都有两个子结点。 4 2 3 1 5 6 7 8 9 10 11 12 13 14 15 满二叉树

118 注意:满二叉树必是完全二叉树；而完全二叉树未必是满二叉树。
二叉树 4 2 3 1 5 6 7 8 9 10 11 12 13 14 15 1.二叉树的定义 2.二叉树的性质 注意:满二叉树必是完全二叉树；而完全二叉树未必是满二叉树。 完全二叉树 定义: 指深度为k的，有n个结点的，且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。 特点: 叶子结点只可能在最下面两层上,且最下层叶子结点集中在树的左部。任一结点, 右分支下子孙结点最大层次为h，则左分支必为h或h+1。 4 2 3 1 5 6 7 8 9 10 4 2 3 1 5 6 7 非完全二叉树 完全二叉树

119 证明：根据完全二叉树的定义和性质2可知，当一棵 完全二叉树的深度为k，结点个数为n时，有
1.1.2 二叉树-二叉树性质证明 性质4：具有n个结点的完全二叉树的深度k为[log2n]+1 证明：根据完全二叉树的定义和性质2可知，当一棵 完全二叉树的深度为k，结点个数为n时，有 2k-1-1<n≤2k-1 即2k-1≤n<2k 对不等式取对数，有 k-1≤log2n<k 由于k是整数，所以有k=[log2n]+1。 深度为k的完全二叉树至少有 2k-1结点 1 1 2 3 2 3 4 5 6 7 4 深度为3的完全二叉树结点数最少情况是4, 即> 2k-1-1=3个 深度为3的完全二叉树结点数最多情况是2k-1= 7个

120 性质5：具有n个结点的完全二叉树，从上至下和从左到右的顺序对所有结点从1开始顺序编号，则对任意结点i有:
1.1.2二叉树-二叉树性质证明P46 性质5：具有n个结点的完全二叉树，从上至下和从左到右的顺序对所有结点从1开始顺序编号，则对任意结点i有: 1) i=1,该结点是根结点。否则(i>1),其双亲结点序号为i/2。 如果2i≤n,其左子结点的序号为2i。（如2、3、4、5节点） 如果 2i>n,则i结点，无左子结点,显然也没右节点。 (如图中6、7节点） 3）如果2i+1≤n，则序号为i的结点的右孩子结点的序号为 2i+1 (如2、3、4的右结点分别为5，7，9）； 如果2i+1>n，则序号为i的结点无右孩子结点。（如5、6、7） 1 作用：很容易确定每个结点的父结点、左子和右子结点的位置。 2 3 4 5 6 7 8 9 10 完全二叉树

121 1.4 树与二叉树 1.1.2 二叉树 1.二叉树的定义 2.二叉树的性质 3.二叉树的存储结构
1.4 树与二叉树 二叉树 1.二叉树的定义 2.二叉树的性质 3.二叉树的存储结构 (1)顺序存储结构: 用一组连续的存储单元存放二叉树中的结点 存储 结构

122 存储 结构 优点：适用于满二叉树和完全二叉树，按结点从上至下，从左到右顺序存放，结点序号唯一反映出结点间逻辑关系，又可用数组下标值确定结点位置。 缺点：对一般二叉树，需增加许多空结点将一棵二叉树改造成完全二叉树，浪费大量存储空间。(否则数组元素下标间不能反映各结点间逻辑关系)

123 1.4 树与二叉树 1.1.2 二叉树 1.二叉树的定义 2.二叉树的性质 3.二叉树的存储结构
1.4 树与二叉树 二叉树 1.二叉树的定义 2.二叉树的性质 3.二叉树的存储结构 (1)顺序存储结构: 用一组连续的存储单元存放二叉树中的结点 (2) 链式存储结构:每个结点由数据域、左指针域和右指针域组成。 lchild Data rchild

124 在n个结点的二叉链表中，有n+1个空指针域
lchild Data rchild A ^ A E C B D F B D ^ C ^ E ^ F 在n个结点的二叉链表中，有n+1个空指针域

125 1.4 树与二叉树 1.1.3 遍历二叉树 定义：按照一定规律对二叉树中的每个结点访问一次 目的：非线性结构线性化。
1.4 树与二叉树 遍历二叉树 定义：按照一定规律对二叉树中的每个结点访问一次 目的：非线性结构线性化。 二叉树是非线性结构，经过一次完整遍历，可将各结点的非线性排列变为某种意义的线性序列。 一棵二叉树的组成: 根结点 D(访问根结点) 左子树 L(遍历左子树) 右子树 R(遍历右子树) (1)前序遍历 (DLR) (2)中序遍历 (LDR) (3)后序遍历 (LRD) 在二叉树的一些应用中，常常要求在树中查找具有某 种特征的结点，或者对树中全部结点逐一进行某种处 理。这就引入了遍历二叉树的问题，即如何按某条搜 索路径巡访树中的每一个结点，使得每一个结点均被 访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的， 因而需要寻找一种规律，以便使二叉树上的结点能排 列在一个线性队列上，从而便于遍历。 3种遍历方式：

126 1.4 树与二叉树 1.1.3 遍历二叉树 定义：按照一定规律对二叉树中的每个结点访问一次
1.4 树与二叉树 遍历二叉树 定义：按照一定规律对二叉树中的每个结点访问一次 目的：非线性结构线性化。二叉树是非线性结构，经过一次完整遍历，可将各结点的非线性排列变为某种意义的线性序列。 访问根结点 按照前序遍历顺序访问根结点的左子树按照前序遍历顺序访问根结点的右子树 (1)前序遍历 (DLR) (2)中序遍历 (LDR) (3)后序遍历 (LRD) 按中序遍历顺序访问根结点的左子树 访问根结点 按中序遍历顺序访问根结点的右子树 在二叉树的一些应用中，常常要求在树中查找具有某 种特征的结点，或者对树中全部结点逐一进行某种处 理。这就引入了遍历二叉树的问题，即如何按某条搜 索路径巡访树中的每一个结点，使得每一个结点均被 访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的， 因而需要寻找一种规律，以便使二叉树上的结点能排 列在一个线性队列上，从而便于遍历。 按后序遍历顺序访问根结点的左子树 按后序遍历顺序访问根结点的右子树 访问根结点

127 以先序遍历D L R为例演示遍历过程 D L R A D L R A D L R C B T1 T3 B > D L R C > > D T2 D > > 先序遍历：D L R 中序遍历：L D R 后序遍历：L R D ABDC BDAC DBCA

128 1.4 树与二叉树 1.1.3 遍历二叉树 举例： a b d e g h c f 前序遍历(根左右)： 中序遍历(左根右) ：
1.4 树与二叉树 遍历二叉树 举例： 在二叉树的一些应用中，常常要求在树中查找具有某 种特征的结点，或者对树中全部结点逐一进行某种处 理。这就引入了遍历二叉树的问题，即如何按某条搜 索路径巡访树中的每一个结点，使得每一个结点均被 访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的， 因而需要寻找一种规律，以便使二叉树上的结点能排 列在一个线性队列上，从而便于遍历。 a b d e g h c f 前序遍历(根左右)： 中序遍历(左根右) ： d b g e h a c f 后序遍历(左右根) ： d g h e b f c a

129 1）在一棵二叉树上第4层的结点数最多是______。 A.4 B.8 C.32 D.12
习题 1）在一棵二叉树上第4层的结点数最多是______。 A.4 B.8 C.32 D.12 2) 在深度为5的满二叉树中，叶子结点的个数为______。 A B.31 C.16 D.15 3) 在深度为5的二叉树中，至多有______个结点。 A B.31 C.16 D.15 4）在具有10 个结点的树中，其边的树目为______。 A B.10 C.8 D.9 5）设一棵完全二叉树共有10个结点，则在该二叉树中的叶 子结点数为______。 A.9 B.5 C.2 D.4 4 2 3 1 5 6 7 8 9 10 = =16(性质1） =31(性质2） (根结点没有入边） 5.解： 由性质5， 如果2i≤n,其左子结点的序号为2i。 如果，2i>n,则i结点，无左子结点,显然也没右结点。 如果2i+1≤n，则序号为i的结点的右孩子结点的序号为 2i+1 如果2i+1>n，则序号为i的结点无右孩子结点。 当i=5,n=10时，2i<=n 且 2i+1>n, 说明i有左孩子、无右孩子，故，i是最后一个非叶子结点，那么结点从6～60均为叶子结点。 解答：BCBDB 1. 性质1： 2i 性质2 ：2k -1 根据性质5，可知最后叶子结点为10，其父结点是5，且该结点5是最后一个非叶子结点,那么从结点 6～10均为叶子结点。（10－6＋1）

130 解答：BBC =n0+n1+n2=3+8+(3-1) ( 性质3: n0=n2+1 ）
6 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数是______。 A.12 B.13 C.14 D.15 7.下面关于完全二叉树的叙述中，错误的是______。 A. 除了最后一层外，每一层上结点数均达到最大值 B. 可能缺少若干个左右叶子结点 C. 完全二叉数一般不是满二叉数 D. 具有n个结点的完全二叉树的深度为[log2n]+1 8.对于所示的二叉树，其后序遍历序列是______。 A. ABDECFG B. DEBAFCG C. DEBFGCA D. GFCEBDA D B C A E F G 解答：BBC =n0+n1+n2=3+8+(3-1) ( 性质3: n0=n2+1 ）

131 10.对如下二叉树，进行后序遍历的结果为______。（06.4月 ) A)ABCDEF B)DBEAFC
9. 在深度为7的满二叉树中， 叶子结点的个数为___。 (06.4月） A) B) C) D) 63 10.对如下二叉树，进行后序遍历的结果为______。（06.4月 ) A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 填空题： 某二叉树中度为2的结点有18个， 则该二叉树中有_____叶子结点。（ 05.4月 ） 10.共 2i-1个 解答：CD 19

132 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。 查找速度; 占用存储空间多少 算法本身复杂程度 1.5 查找 查找:
1.5 查找 查找: 查找——也叫检索，是根据给定的某个值，在表中确定 一个关键字等于给定值的记录或数据元素. 不同的数据结构采用不同的查找方法。 关键字——是数据元素中某个数据项的值，它可以标识 一个数据元素. 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。 查找的结果： 查找速度; 占用存储空间多少 算法本身复杂程度 查找方 法评价：

133 1.5 查找 顺序查找 基本思路： 从表中第一个元素开始，将给定的值与表中逐个元素的关键字比较。直到两者相等表示找到，查找成功。否则就是表中无要找的元素，查找失败。 表中第一个元素就是被查找元素，一次比较就成功。 表中最后一个元素是被查找元素(或不在表中)，与所有 元素比较。 平均情况，查找一个元素，大约与表中一半元素比较。 查找 次数 下列两种情况只能采用顺序查找：( 补充) 线性表是无序表(元素排列是无序的)，无论顺序存储还是链式 存储 有序线性表而采用链式存储结构，也只能用顺序查找 优点：对表中数据元素的存储没有要求。 缺点：线性表很大时，平均查找长度较长，效率低。

134 1.5 查找 1.5.2 二分法查找(折半查找) 思想：先确定待查找记录所在的范围，然后逐步缩小范围， 直到找到或确认找不到该记录为止。
1.5 查找 二分法查找(折半查找) 思想：先确定待查找记录所在的范围，然后逐步缩小范围， 直到找到或确认找不到该记录为止。 适用条件：必须在具有顺序存储结构的有序表(表中元素按关键值升序或降序存放)中进行。 算法实现 1) 确定区间的中间位置 mid =(low + high)/2 2) 用给定值与中间位置的关键字值比较；若相等，则查找成功； 若给定值大,新查找区为后半区； high=mid-1 若给定值小,新查找区为前半区。 low=mid+1 3) 对缩小的区域重复上述步,直至low>high时，查找失败

135 1.5 查找 1.5.1 二分法查找(折半查找) <例>在含有9个数的升序线性表中查找68的过程如下图 High=9 low=1
1.5 查找 二分法查找(折半查找) <例>在含有9个数的升序线性表中查找68的过程如下图 ( 08, , , , , , , , ) ( 08, , , , , , , , ) low=1 mid=5 High=9 ( 08, , , , , , , , ) low＝mid+1 high mid=(6+9)/2=7 mid=(1+9)/2=5 mid=7 mid=(low+high)/2 x<L[mid]: high=mid-1 x>L[mid]: low=mid+1 经过二次比较,查找成功

136 1.5.2 二分法查找(折半查找) 查找88的过程如下图： mid=(low+high)/2 Low high
二分法查找(折半查找) 查找88的过程如下图： mid=(low+high)/2 ( 08, , , , , , , , ) Low high mid (88>46,缩小到后部) ( 08, , , , , , , , ) low mid(88>68) high ( 08, , , , , , , , ) low high mid(88>79) ( 08, , , , , , , , ) low high mid(88<91) ( 08, , , , , , , , ) high low 二分法查找时间复杂度O(log2n) 失败:

137 二分查找(折半查找) 查找效率高 前提: 查找表中的数据元素必须有序。 算法:1) 确定区间的中间位置
二分查找(折半查找) 查找效率高 前提: 查找表中的数据元素必须有序。 算法:1) 确定区间的中间位置 mid =(left + right)/2 2) 用给定值与中间位置的关键字值比较； 若相等，则查找成功； 若给定值大,新查找区为后半区； 若给定值小,新查找区为前半区。 3)对缩小的区域重复上述步骤； 优点: 比较次数少,查找速度快 缺点：要求事先排序 二分法查找时间复杂度 ：O(log2n)

138 查找总结 顺序查找 二分查找 适用 情况 无序顺序表 链表 有序顺序表 优点 对表中数据元素的存储没有要求 比较次数少,查找速度快 缺点
线性表很大时，平均查找长度较长，效率低 要求事先排序 比较 次数 最坏情况下查找比较次数是n次 最坏情况下查找比较次数是log2n次

139 1.6 内部排序 排序又称分类，是计算机程序设计中一个重要运算，它的功能是将一组任意序列的数据元素，进行按由大到小的顺序（降序）排列或按由小到大的顺序（升序）排列。 这些数据元素可以是数值型，也可以为字符型。若为数值型，则按数值大小排列；若为字符型，则按其ASCII码的顺序排列。 在实际应用中，参加排序的数据元素有时不是单个数据项，而是由多个数据项组成的记录。此时排序应按照关键字的大小进行。所谓关键字是指记录中的某个数据项，用它可以标识一个记录。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字；反之，把用以识别若干记录的关键字称为次关键字。 学号 姓名 系别 住址 电话 981111 李洪 机械 六舍 982111 王刚 电子 四舍 983211 王将 计算机 五舍 983212 张强 六舎

140 1.6 内部排序 1.排序的功能：将一个数据元素（或记录）的任意序列，重 新排成一个按关键字有序的序列。 2.内部排序与外部排序
1.6 内部排序 1.排序的功能：将一个数据元素（或记录）的任意序列，重 新排成一个按关键字有序的序列。 2.内部排序与外部排序 根据排序时数据所占用存储器的不同,可将排序分为两类: 内部排序:整个排序过程完全在内存中进行. 外部排序:由于待排序记录数据量太大,内存无法容纳 全部数据,排序需要借助外部存储设备才能完成. 排序算法评价： 算法执行时间(最好、最差及平均情况) 需要附加空间大小

141 1.6 内部排序 1.6.1 插入排序 插入排序的基本思想： 插入排序三种方法
1.6 内部排序 插入排序 插入排序的基本思想： 插入排序三种方法 1. 直接排序: 认可第1个记录已排好序，然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。 2.折半插入排序: 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。 3.希尔排序: 将整个无序序列分割成若干个子序列分别进行直接插入排序. 将待排序文件中的记录，逐个按其排序码值的大小插入到已排好序的若干个记录组成的文件中的适当位置，保持新文件有序。

142 将Ri的排序码与前面已排好序的排序码从右向左依次比较，找到Ri应插入的位置；将该位置以后直到Ri-1各记录顺序后移,空出位置插入Ri。
1.6 内部排序 插入排序 1.直接插入排序: 思路：认可第1个记录已排好序，然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。 具体过程(第i个记录Ri插入到前面i-1个已排好序的记录中) 将Ri的排序码与前面已排好序的排序码从右向左依次比较，找到Ri应插入的位置；将该位置以后直到Ri-1各记录顺序后移,空出位置插入Ri。

143 对于有n个数据元素的待排序列，插入操作要进行n-1次
<例>直接插入排序: 待排元素序列：[53] 第一次排序： [ ] 第二次排序： [ ] 第三次排序： [ ] 第四次排序： [ ] 42 第五次排序： [ ] 直接插入排序示例 对于有n个数据元素的待排序列，插入操作要进行n-1次 该算法适合于n 较小的情况，时间复杂度为O(n2). 从上面看出,若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为i个.

144 1.6 内部排序 1.6.1 插入排序 1.直接插入排序: 时效分析 最好情况:初始排序码已经有序。共比较n-1次，移动0次。
1.6 内部排序 插入排序 1.直接插入排序: 时效分析 最好情况:初始排序码已经有序。共比较n-1次，移动0次。 最坏情况:待排序序列完全逆序。比较和移动均为n(n-1)/2次。 平均情况:比较和移动次数均为n2/4，时间复杂度为O(n2)。

145 若一个元素序列基本有序，则选用直接插入排序较快。
1.6 内部排序 1.直接插入排序: 若一个元素序列基本有序，则选用直接插入排序较快。 用直接插入排序方法对下列4个表由小到大进行排序，比较次数最少的是（）。 A. （94，32，40，90，80，46，21，69） B. （21，32，46，40，80，69，90，94） C. （32，40，21，46，69，94，90，80） D. （90，69，80，46，21，32，94，40） B

146 折半插入排序减少了关键字的比较次数，其时间复杂度与直接插入排序相同为O(n2)。
1.6 内部排序 插入排序 2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。 例：有6个记录，前5 个已排序的基础上，对第6个记录排序。 [ ]  low mid  high ( 42>36 ,后半) low  high mid ( 42<53 ,前半 ) [ ] 42 high low (high<low ， 查找结束，插入位置为low 或high+1 ) [ ] 折半插入排序减少了关键字的比较次数，其时间复杂度与直接插入排序相同为O(n2)。

147 1.6 内部排序 1.6.1 插入排序 3 .希尔排序 基本思想：将整个无序序列分割成若干个子序列分别进
1.6 内部排序 插入排序 3 .希尔排序 基本思想：将整个无序序列分割成若干个子序列分别进 行直接插入排序,待整个序列中的记录”基本 有序”时,再对全体记录进行一次直接插入排序。 子序列分割：选定两个元素之间距离h，将所有间隔为h的元素 分成一组(将相隔某个增量h的元素构成一个子系列)

148 1.6 内部排序 1.6.1 插入排序 具体实现: 3 .希尔排序 (1) 选择一个增量序列t1 ，t2，… ti ， tj … ，tk,
1.6 内部排序 插入排序 3 .希尔排序 具体实现: (1) 选择一个增量序列t1 ，t2，… ti ， tj … ，tk, 其中ti > tj, tk=1。 (2) 按增量序列个数k，对序列进行k趟排序。 (3) 每趟排序，根据对应的增量ti，将序列分割成若干长度为m的子序列，分别对各子表直接插入排序。增量ti逐次减小， tk=1时，再对全部元素进行一次直接插入排序即可完成。

149 举例: 有一个含有14个数的序列,使用希而排序进行升序排序
( 39,80,76,41,13,29,50,78,30,11,100,7,41,86 ) 取增量：t1=5，t2=3，t3= 趟排序 R1, R2, R3, R4, R5, R6, R7, R8, R9, R10 R11, R12, R13, R14 t1=5 (R1,R6, R11) (R2,R7, R12) (R3,R8, R13 ) (R4,R9, R14) (R5,R10 ) 则5个子序列： {39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}

150 R1, R2, R3, R4, R5, R6, R7, R8, R9, R10 R11, R12, R13, R14 t1=5 子序列： {39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11} 对每个序列进行直接插入排序: 对每个子序列进行直接插入排序 因此第一趟排序结果如下:

151 第一趟排序结果 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 t2=3 (R1,R4,R7,R10,R13) (R2,R5,R8,R11,R14) (R3,R6,R9,R12) 分别对以上3个子序列进行直接插入排序 {29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80} 第二趟最终结果：

152 第二趟最终结果： t3=1 序列基本有序，对其进行直接插入排序, 第三趟最终结果：

153 基本思路 冒泡排序 快速排序 1.6 内部排序 1.6.2 交换排序
1.6 内部排序 交换排序 基本思路 对待排序记录两两比较排序码，不满足排序顺序则交换。直到任何两个记录排序码满足排序要求。 冒泡排序 快速排序 交换排序种类:

154 1.6 内部排序 1.6.2 交换排序 1. 冒泡排序 基本思想：通过相邻元素的交换，逐步将线性表变成有序。 基本过程：
1.6 内部排序 交换排序 1. 冒泡排序 基本思想：通过相邻元素的交换，逐步将线性表变成有序。 基本过程： 第一趟冒泡排序：首先第一个元素与第二个元素比较，逆序则 交换；然后第二个元素与第三个元素比较；直到第n-1个元素与第n个元素比较为止。结果（关键字）最大的元素放在最后位置。 第二趟冒泡排序：对前面n-1个元素进行相同操作，结果 次大元素放在n-1位置上。 第i趟冒泡排序：对前面n-i+1个元素进行相同操作，结 果(n-i+1)中最大元素放在(n-i+1)位置上。 趟数： 最多n-1 结束条件： 在某一趟排序中没有进行交换元素操作。 在对n个元素进行冒泡排序的过程中，第一趟至多需要进行n-1 次相邻元素之间的比较。

155 交换排序-冒泡排序P53 举例:将数列 ( 8, 6, 5, 7, 1 ) 升序排序 思想：小的浮起， 大的沉底。 第一趟比较过程 6666 8555 5877 7781 1118 初始 8 6 5 7 1 第一趟 6 5 7 1 8 第二趟 5 6 1 7 8 第三趟 5 1 6 7 8 第四趟 1 5 6 7 8 时效分析: 初始已排好序(正序最好)，则只需进行一趟排序,比较次数n-1，移动次数为0。 逆序(最坏)，则需进行n-1趟排序, 比较次数为(1+2+3+…+n-1)=n(n-1)/2。 是稳定的排序,时间复杂度为O(n2 ),空间复杂度是O(1) .

156 1.6 内部排序 交换排序 2. 快速排序 基本思想： 通过一趟排序将待排记录分割成独立两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再对前、后两部分待排记录重复上述过程，直到所有子表表长不超过1为止。 [ ] [ ] [ ] 优点：通过两个不相邻元素交换，可以一次交换消除多个逆序，加快排序速度。 快速排序方法在要排序的数据已基本有序 情况下最不利于发挥其长处。

157 1.6 内部排序 交换排序 2. 快速排序 过程: 首先任选一个记录K(通常选第一个记录)作为枢轴(支点) 附设两个指针i和j分别指向第一个记录和最后一个记录。 (1) 指针j向前搜索逐个记录与K比较,直到发现小于K的记录为止，将其与枢轴记录互相交换。 (2)指针i向后搜索逐个记录与K比较,直到发现大于K的记录为止，将其与枢轴记录互相交换。 (3)重复(1) (2)直至i=j为止。完成一趟排序，完成一次分割(以K为分界线)，对前后两个子表按上述原则再分割，直到所有子表的表长不超过1(为空)为止。

158 j j i 举例: 将（49，39，66，96，76, 11，27，50）进行一趟快速排序
分析: (取第一个数49为枢轴,即K=49,空处是枢轴为49) 初始关键字 j i i 49 j 第1次交换(向前,小的与枢轴交换)即27与49交换. 49 j i 第2次交换:(向后,大的与枢轴交换)即66与49换, 49 j i 第3次交换:11与49换 49 第4次换:96与49换 完成一趟排序: j i j

159 快速排序的全过程 初始关键字 一次划分 之后 [ ] [ ] 分别进行快速排序 [11] [ 39] 结束 结束 [ ] [96] 结束 结束 有序序列 时效分析: 平均时间复杂度最佳为O(nlog2n)。 最坏情况时间效率为O(n2)。

160 1.6 内部排序 1.6.3 选择排序 选择排序种类: 直接选择排序和堆排序 1.直接选择排序( 以升序为例) 基本思想：
1.6 内部排序 选择排序 基本思想： 每次从待排序的记录中选出关键字最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。 选择排序种类: 直接选择排序和堆排序 1.直接选择排序( 以升序为例) 首先从所有n个待排序记录中选择关键字最小的记录，与第1个记录交换(第1遍进行n-1次比较)。 再从剩下的 n-1个记录中选出关键字最小的记录，与第2个记录交换(第2遍进行n-2次比较)。 重复操作进行n-1遍，直到待排序序列全部有序为止。

161 1.6 内部排序 1.6.3 选择排序 1. 直接选择排序 举例:将（89，21，56，48，85，16，19，47）直接选择排序
1.6 内部排序 选择排序 1. 直接选择排序 举例:将（89，21，56，48，85，16，19，47）直接选择排序 原序列 i= i= i= i= i= i= i= 时间复杂度O(n2) 最后结果 进行n-1=7次选择

162 1.6 内部排序 1.6.3 选择排序 2.堆排序 堆定义：n个元素的序列{K1，K2，…，Kn}，当且仅当满足下列关 系时，称为堆。
1.6 内部排序 选择排序 2.堆排序 堆定义：n个元素的序列{K1，K2，…，Kn}，当且仅当满足下列关 系时，称为堆。 ki≤k2i ki≤k2i+1 ki≥k2i　　　　　　 ki≥k2i+1 小根堆 或 大根堆 其中:（i=1，2，…，n/2） 在堆中,堆顶元素必为序列中n个元素的最小值(或最大值)。 25 15 56 10 30 70 25 56 30 70 15 10 大根堆 小根堆 堆结构(完全二叉树表示)：将序列对应的一维数组看成一个完全二叉树。

163 1.6 内部排序 1.6.3 选择排序 2.堆排序 排序过程: 两个问题:实现堆排序需解决
1.6 内部排序 选择排序 2.堆排序 排序过程: 两个问题:实现堆排序需解决 首先包括n个元素的序列建堆,输出堆顶最小值。得到n个 元素中最小元素。 然后再对剩下n-1个元素重建堆,输出堆顶元素。得到n个 元素中次小元素。 反复执行(直到剩下子序列为空)，便得到一个有序列。 (1)如何将n个元素的无序序列建成一个堆。 方法：将根结点与左、右子树根结点比较，若不满足堆条件，则较小值与根结点交换。 顺序：从完全二叉树最后一个非终端结点(第n/2个元素)开始，直到根结点(第一个元素)为止，对每一个结点，调整建堆。 (2)输出堆顶元素后，调整剩余元素成为一个新堆。 输出堆顶元素后，以堆中最后一个元素代替之。此时根结点左、右子树均为堆，仅需自上而下调整即可。

164 举例:一个无序序列(49,39,66,96,76,11,27,50)建小根堆的过程 无序序列 第4个结点96被筛选后状态
1. 从第一个非叶子结点(序号=n/2=8/2=4,即图中值为96的结点开始筛选,筛选 原则是保证父结点的值要小于或等于叶子节点 49 39 50 66 76 11 27 96 49 39 96 66 76 11 27 50 无序序列 第4个结点96被筛选后状态 49 39 50 11 76 66 27 96 49 39 50 11 76 66 27 96 第2个结点39被筛选后状态 第3个结点66被筛选后状态

165 目前的小根堆中,堆顶元素11为最小值,输出后,重新对n-1个元素重新建一个新堆, 新堆中的堆顶是剩余的n-1个元素中的最小值,n个元素中的次最小值.
49 39 50 11 76 66 27 96 第2个结点筛选完毕 该处理第1个结点 11 39 50 27 76 66 49 96 11 39 50 49 76 66 27 96 49 被筛选后建成的堆

166 输出堆顶元素之后,以堆中最后一个元素替代之,此时根结点的左、右子树均为堆,仅需自上至下进行调整即可。
举例:输出堆顶元素并建新堆过程 输出堆顶元素之后,以堆中最后一个元素替代之,此时根结点的左、右子树均为堆,仅需自上至下进行调整即可。 11 39 50 27 76 66 49 96 39 50 27 76 66 49 96 11 堆 11与96交换后情形 39 50 96 76 66 49 27 39 50 49 76 66 96 27 11 11 调整后新堆,27为新堆中的最小值 27与96交换后情形

167 调整后新堆,27为新堆中的最小值 输出27, 用96替代 96与50换 调整后新堆,39为新堆中的最小值 96与39换 39 50 49
76 66 96 27 39 50 49 76 66 96 11 11 27 调整后新堆,27为新堆中的最小值 输出27, 用96替代 50 96 49 76 66 39 96 50 49 76 66 39 11 27 11 27 96与50换 调整后新堆,39为新堆中的最小值 96与39换

168 输出堆顶元素（堆顶元素和树中最后一个结点对调） 重建堆（因为除了堆顶的根结点，左右子树已经是堆， 自上而下进行调整即可） 反复执行
50 96 49 76 66 39 50 96 49 76 66 39 11 27 11 27 调整后新堆,39为新堆中的最小值 继续此过程 输出堆顶元素（堆顶元素和树中最后一个结点对调） 重建堆（因为除了堆顶的根结点，左右子树已经是堆， 自上而下进行调整即可） 反复执行 直到剩下子序列为空（便得到一个有序列）

169 最坏情况下，时间复杂度为O (nlog2n)。适合规模较大的线性表。
堆排序的时效分析: 最坏情况下，时间复杂度为O (nlog2n)。适合规模较大的线性表。 若对n个元素进行堆排序，则在由初始堆进行每趟排序的过程中，共需要进行 n-1次筛选运算。

170 最坏情况下,比较次数n(n-1)/2时间复杂度O(n2) 最坏情况下,时间复杂度是O(n1.5) 最坏情况下,比较次数n(n-1)/2
排序小结 插入排序 交换排序 选择排序 直接插入排序 希尔 排序 冒泡排序 快速排序 直接选 择排序 堆排序 适用于n较小情况,或表中每个元素与其最终位置不远, 记录本身信息量较大时 若适用于数据元素初始状态基本有序 适用于n较大情况,是目前基于内部排序的方法中最好的 适用于n较小情况,且记录本身信息量较大时 适用于n较大情况, 最坏情况下,比较次数n(n-1)/2时间复杂度O(n2) 最坏情况下,时间复杂度是O(n1.5) 最坏情况下,比较次数n(n-1)/2 时间复杂度O(n2) 时间复杂度O(n log2n) 最坏情况下,比较次数n log2n 时间复杂度 O(n log2n) 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在 排序之前和经过排序之后，没有改变。 2. 快速排序和堆排序是不稳定的排序方法 希尔排序是不稳定的。

171 查找与排序补充习题讲解 ACB 1. 链表适用于_____查找. A . 顺序 B. 二分法 C. 顺序,也能二分法 D. 随机
2. 对长度为n的线性表进行顺序查找,在最坏情况下所需要 的比较次数为____. A. log2n B. n/ C. n D. n+1 （05年4月） 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的查找长度或次数为____. A B C D.6 解析：第一次：low=1, high=18, 则mid=(1+18)/2= 后半区 第二次：low=mid+1=10, high=18, 则mid=(10+18)/2=14 后半区 第三次：low=mid+1=15, high= 则mid=(15+18)/2=16 前半区 第四次：low=15, high=mid-1= 则mid=(15+15)/2=15 故查找次数为4次 ACB

172 查找与排序补充习题讲解 1. 在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更他们的相对位置，这就是__排序。
1. 在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更他们的相对位置，这就是__排序。 A. 希尔排序 B. 交换排序 C. 插入排序 D. 选择排序 5．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一段的方法，称为 A.希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 6．若一个元素序列基本有序，则选用（）排序较快。 A. 堆排序 B. 快速排序 C. 直接插入排序 D. 直接选择排序 7．快速排序方法在（）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 8. 希尔排序法属于哪一种类型的排序法______。 A. 交换类排序法 B. 插入类排序法 C. 选择类排序法 D. 建堆排序法 BDCCB

173 9. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序方法，以第一个纪录为基准得到的一次划分结果为（）。
A.（38，40，46，56，79，84） B.（40，38，46，79，56，84） C.（40，38，46，56，79，84） D.（40，38，46，84，56，79） 分析： 46， 79， 56， 38， 40， 84 40， 79， 56， 38， 46， 84 40， 46， 56， 38， 79， 84 40， 38， 56， 46， 79， 84 40， 38， 46， 56， 79， 84 C

174 11. 在对n个元素进行直接插入排序或冒泡排序的过程中，都需要进行（）趟。 A .n B.n+1 C . n-1 D.2n
C. 快速排序为n D.快速排序为n(n-1)/2 11. 在对n个元素进行直接插入排序或冒泡排序的过程中，都需要进行（）趟。 A .n B.n+1 C . n-1 D.2n 12．若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为（）。 A B.i-1 C.i D. i+1 DCC:在最坏情况下,冒泡排序和快速排序的比较次数都是n(n-1)/2

175 13．已知某二叉树的后序遍历序列是DACBE，中序序列是DEBAC，则它的前序遍历序列是（） A. ACBED B. DEABC
C. DECAB D. EDBAC E D B A C 分析：根据后序遍历序列是DACBE和中序序列是DEBAC，判定E为根节点，D为根节点的左子树，根节点的右子树由三个节点组成，又根据后序遍历序列DACBE中的给出的顺序ACB，中序序列DEBAC给出的序列BAC，判定节点B没有左子数，同理，节点A下无左子树，节点C在节点A的右子树。 D

176 11.在具有88个结点的二叉数,其深度至少为______.
分析:性质4 :深度=[log2n]+1=[ log288]+1=6+1=7

177 6．一个栈的输入序列是1，2，3，4，5，则下列序列中（）是栈的输出序列。 31245 B.41325 C.23415 D.14253
期末复习题中数据结构部分难点题解析 6．一个栈的输入序列是1，2，3，4，5，则下列序列中（）是栈的输出序列。 B C D.14253 分析：关键要把握“进栈和出栈可以穿插进行，同时注意先进后出 的原则。 选项A ：中先出栈的是3，则栈中必然有1和2，由于1先 于2压入栈，所以出栈时， 2要先于1出栈，而A 中1先于2违背先进后出原则，所以不对。 选项B：4先出栈，则栈中必然有1、2、3，出栈顺序不可能是1先于3，所以B也不正确。 选项D：1进栈又出栈，然后4出栈，说明栈中必然有2、 3，且3出栈顺序要先于2出栈，而D 表示 2先于3出栈，所以不对。 选项C：(↓表示入栈，↑表示出栈） 1↓2↓↑3 ↓↑4 ↓↑1↑5 ↓↑ C

178 7．已知完全二叉树有30个结点，则整个二叉树有（B）个度为1的结点。 A. 0 B. 1 C. 2 D. 不确定
8．深度为k的完全二叉树至少有（C）个结点。 A. 2k B. 2k C. 2k D. 2k-2 9．深度为k的完全二叉树至多有（A）个结点。 A. 2k B. 2k C. 2k D. 2k-2 4 2 3 1 5 6 7 8 9 10 11 12 13 14 15 4 2 3 1 5 6 7 8 9 10 1 2 3 4 5 6 7 8 7.题参见左图进行推理 题参见中间图k=4完全二叉树最少节点情况为8个 9题参见右图，性质5

179 10．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（C）次。
1 B C D. 4 分析：查找60在它之前已经排好序的6个数（15，23，38，54，72，96）中的位置时，从后往前依次比较，第3次比较，60>54 ，确定出插入的位置。 16．一个栈的入栈序列1，2，3，4，则它的不可能的输出序列是（D）。 A. 1，2，3， B. 4，3，2，1 C. 1，3，4， D. 4，1，2，3 分析同6题类似： 选项A.入栈与出栈顺序：1 ↓↑2 ↓↑3 ↓↑4 ↓↑ 选项B.入栈与出栈顺序: 1 ↓2 ↓3 ↓4 ↓↑ 3 ↑2 ↑1↑ 选项c入栈与出栈顺序: 1 ↓↑ 2 ↓ 3 ↓↑4 ↓↑ 2↑

180 19．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（C）
（n+1）/2 B.n/2 C. n D.n+1 分析：若删除的值在第i个位置，则比较次数是i次，移动次数是n-i次，合计n次。 30. 假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top= =-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（C） a[--top]=x B. a[top--]=x C. a[++top]=x D .a[top++]=x 分析： a[++top]=x 表示Top指针先加1，然后将x入栈。 a[top++]=x 表示x入栈后，Top指针再加1。

181 38在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点点数为2个，则度为0的结点数为（D）个。
A.3 B.4 C.5 D.6 解析：结点总数 n=n0+n1+n2+n3 度数之和 m=n1+2n2+3n3 关系： n=m+1 由以上三个式子:n0+n1+n2+n3=n1+2n2+3n3+1 n0=n2+2n3+1=1+2×2+1=6 43 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉 树中所包含的结点数至少为（B） A.2h B.2h-1 C.2h+1 D.h+1 分析：推测出是一个完全二叉数，参看下面图 1 1 2 2 3 3 5 4 5 4 H=3 ，包含2×3-1=5 H=4，包含2×4-1=7 8 9

182 44按照二叉树的定义，具有3个结点的二叉树有（A）种状态。 A.5 B.4 C.3 D.30
1 1 1 2 2 2 3 3 3 1 1 2 2 3 3

183 45 若查找每个元素的概率相等，则在长度为n的顺序表上查找任意元素的平均查找长度为（D）
A.n B.n+1 C.（n-1）/2 D.（n+1）/2 解析: 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度. 假设在每个位置查找概率相等,即p1=p2=…=1/n,若是从表尾向表头方向查找,则每个位置上查找比较次数为: Cn=1,Cn-1=2, …C1=n.于是, 查找成功的平均查找长度为 ASL=(1/n)×( …+n)=(n+1)/2