数据结构课程简介深圳大学计算机系蔡茂国.

数据结构课程简介深圳大学计算机系蔡茂国

《数据结构》课程简介《数据结构》(C语言版) 主要参考教材本课程教材为：严蔚敏，吴伟民清华大学出版社
　严蔚敏，吴伟民　清华大学出版社　2004年11月（第28次印刷） 2

《数据结构》课程简介课件下载所有课件、作业及实验，均上传至：深圳大学首页－－课程中心－－输入学生姓名及密码，实现登录－－
　所有课件、作业及实验，均上传至：深圳大学首页－－课程中心－－输入学生姓名及密码，实现登录－－从《数据结构》课程下下载 3

数据结构第一章数据结构绪论深圳大学计算机系蔡茂国

第１章　数据结构绪论第一节　数据结构一、数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据非数值性数据 5

第１章数据结构绪论第一节数据结构二、数据元素（Data Element）
第１章　数据结构绪论第一节　数据结构二、数据元素（Data Element）数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(Data Item)组成（此时数据元素被称为记录）数据元素又称为元素、结点、记录 6

第１章　数据结构绪论第一节　数据结构三、数据项（Data Item）具有独立含义的最小标识单位。学号姓名学院专业 7

第１章数据结构绪论第一节数据结构四、数据对象（Data Object）具有相同性质的数据元素的集合。整数数据对象
第１章　数据结构绪论第一节　数据结构四、数据对象（Data Object）具有相同性质的数据元素的集合。整数数据对象 N = {0, 1, 2, … } 字母字符数据对象 C={ ‘A’, ‘B’, ‘C’, … ‘F’ }。 8

第１章　数据结构绪论第一节　数据结构五、结构（Structure）　结构是元素之间的：空间位置关系相互作用和依赖关系 9

第１章数据结构绪论第一节数据结构五、结构四种基本结构集合结构线性结构树形结构图形结构 10 6 3 1 2 4 5 1 2
第１章　数据结构绪论第一节　数据结构五、结构 6 3 1 2 4 5 　四种基本结构集合结构线性结构树形结构图形结构 1 2 3 4 5 6 4 5 6 2 3 1 1 2 3 4 5 6 10

六、数据结构（Data Structure）
第１章　数据结构绪论第一节　数据结构六、数据结构（Data Structure） 1. 形式定义：某一数据对象的所有数据成员之间的关系。记为： Data_Structure = {D, S} 其中，D 是某一数据对象， S 是该对象中所有数据成员之间的关系的有限集合。 11

第１章数据结构绪论第一节数据结构六、数据结构 2. 线性数据结构举例 L = {K, R}
第１章　数据结构绪论第一节　数据结构六、数据结构 2. 线性数据结构举例 L = {K, R} K = {1, 2, 3, 4, 5, 6} R = {<1,2>, <2,3>, <3,4>, <4,5>, <5,6>} 1 2 3 4 5 6 12

第１章数据结构绪论第一节数据结构六、数据结构 3. 树形数据结构举例 T = {K, R}
第１章　数据结构绪论第一节　数据结构六、数据结构 3. 树形数据结构举例 T = {K, R} K = {1, 2, 3, 4, 5, 6} R = {<1,2>, <1,3>, <2,4>, <2,5>, <3,6>} 4 5 6 2 3 1 13

第１章数据结构绪论第一节数据结构六、数据结构 4. 图形数据结构举例 G = {K, R}
第１章　数据结构绪论第一节　数据结构六、数据结构 4. 图形数据结构举例 G = {K, R} K = {1, 2, 3, 4, 5, 6} R = {(1,2), (1,5), (1,6), (2,3), (2,4), (2,6), (3,4), (4,5), (4,6), (5,6)} 1 2 3 4 5 6 14

第１章数据结构绪论第一节数据结构七、应用举例 1. 线性数据结构举例数据结构学生选课名单（部分） 15 学号姓名学院专业
第１章　数据结构绪论第一节　数据结构七、应用举例 1. 线性数据结构举例数据结构学生选课名单（部分）学号姓名学院专业黄磊信息工程学院熊玲玲彭智俊徐元庆吴小池陈明亮 15

第１章数据结构绪论第一节数据结构七、应用举例 2. 树形数据结构举例 UNIX文件系统结构图（部分） / root bin lib
第１章　数据结构绪论第一节　数据结构七、应用举例 2. 树形数据结构举例 UNIX文件系统结构图（部分） / root bin lib user etc math ds sw hang xiong pan 16

第１章数据结构绪论第一节数据结构七、应用举例 3. 图形数据结构举例深圳城市交通示意图（部分）南山福田罗湖盐田宝安西丽
第１章　数据结构绪论第一节　数据结构七、应用举例 3. 图形数据结构举例深圳城市交通示意图（部分）南山福田罗湖盐田宝安西丽梅林布吉龙华龙岗 17

第１章数据结构绪论第一节数据结构八、数据结构要解决的问题
第１章　数据结构绪论第一节　数据结构八、数据结构要解决的问题如何为应用程序中涉及到各种各样的数据，建立相应的数据结构（表、树或图），并依此实现软件功能从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现 18

第１章数据结构绪论第二节数据的结构一、逻辑结构逻辑结构描述数据元素之间的关系线性结构非线性结构线性表（表，栈，队列，串等）
第１章　数据结构绪论第二节　数据的结构一、逻辑结构逻辑结构描述数据元素之间的关系线性结构线性表（表，栈，队列，串等）非线性结构树（二叉树，Huffman树，二叉排序树等）图（有向图，无向图等） 1 2 3 4 5 6 4 5 6 2 3 1 1 2 3 4 5 6 19

第１章数据结构绪论第二节数据的结构二、物理结构（存储结构）物理结构是数据结构在计算机中的表示（或映象）
第１章　数据结构绪论第二节　数据的结构二、物理结构（存储结构）物理结构是数据结构在计算机中的表示（或映象）顺序存储表示（可以用C语言中一维数组表示）链接存储表示（可以用C语言中的指针表示）索引存储表示散列存储表示 20

第１章数据结构绪论第二节数据的结构二、物理结构（存储结构）复数存储结构举例顺序存储结构链式存储结构 … 0300 0302
第１章　数据结构绪论第二节　数据的结构二、物理结构（存储结构）复数存储结构举例顺序存储结构链式存储结构 … 0300 0302 0632 0634 3.0 -2.3 -0.7 4.8 … 0415 0611 0613 -2.3 3.0 z1= i z2= i z1= i 指针或链 (地址) 21

第１章数据结构绪论第三节数据类型一、数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称
第１章　数据结构绪论第三节　数据类型一、数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称如C语言中的整型变量(int)，其值集为某个区间上的整数，定义在其上的操作为+, -, x, /等 22

第１章数据结构绪论第三节数据类型二、原子数据类型和结构数据类型 1. 原子数据类型是不可分解的数据类型
第１章　数据结构绪论第三节　数据类型二、原子数据类型和结构数据类型 1. 原子数据类型是不可分解的数据类型如C语言中的整型(int)，实型(float)，字符型(char)，指针类型(*)和空类型(void)等 23

第１章数据结构绪论第三节数据类型二、原子数据类型和结构数据类型 2. 结构数据类型
第１章　数据结构绪论第三节　数据类型二、原子数据类型和结构数据类型 2. 结构数据类型由若干成分（原子类型或结构类型）按某种结构组成的数据类型结构数据类型可以看作是一种数据结构和定义在其上的一组操作组成的整体如数组，由若干分量组成，每个分量可以是整数，也可以是数组（如int A[10]） 24

三、抽象数据类型（Abstract Data Type）
第１章　数据结构绪论第三节　数据类型三、抽象数据类型（Abstract Data Type）由用户定义，用以表示应用问题的数据模型由基本的数据类型组成, 并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离 25

第１章数据结构绪论第三节数据类型三、抽象数据类型（ADT）抽象数据类型（ADT）是一个数学模型以及定义在该模型上的一组操作
第１章　数据结构绪论第三节　数据类型三、抽象数据类型（ADT）抽象数据类型（ADT）是一个数学模型以及定义在该模型上的一组操作抽象数据类型 = 数据结构 + 定义在此数据结构上的一组操作 26

第１章数据结构绪论第三节数据类型三、抽象数据类型（ADT表示）抽象数据类型可用（D，S，P）三元组表示 D是数据对象
第１章　数据结构绪论第三节　数据类型三、抽象数据类型（ADT表示）抽象数据类型可用（D，S，P）三元组表示 D是数据对象 S是D上的关系集 P是对D的基本操作集。 27

第１章数据结构绪论第三节数据类型三、抽象数据类型（ADT定义） ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉
第１章　数据结构绪论第三节　数据类型三、抽象数据类型（ADT定义） ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作(函数)的定义〉 } ADT 抽象数据类型名 28

第１章数据结构绪论第三节数据类型三、抽象数据类型（ADT定义举例） ADT Triplet {
第１章　数据结构绪论第三节　数据类型三、抽象数据类型（ADT定义举例） ADT Triplet { 数据对象：D = {e1,e2,e3 | e1,e2,e3∈ElemSet} 数据关系：R = {<e1,e2>, <e2,e3>} 基本操作：Max(T, &e) 初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最大值。　　　　　　 Min(T, &e) 操作结果：用e返回T的3个元素中的最小值。　 } ADT Triplet 29

第１章数据结构绪论第三节数据类型三、抽象数据类型（ADT定义实现）
第１章　数据结构绪论第三节　数据类型三、抽象数据类型（ADT定义实现）抽象数据类型可以通过固有数据类型(C语言中已实现的数据类型)来实现抽象数据类型类 class 数据对象数据成员基本操作成员函数(方法) 30

第１章　数据结构绪论第四节　算法分析一、算法（Algorithm）算法是对特定问题求解步骤的一种描述是一有限长的操作序列 31

第１章数据结构绪论第四节算法分析一、算法（特性）有穷性：算法在执行有穷步后能结束确定性：每步定义都是确切、无歧义
第１章　数据结构绪论第四节　算法分析一、算法（特性）有穷性：算法在执行有穷步后能结束确定性：每步定义都是确切、无歧义可行性：每一条运算应足够基本(已验算正确) 输入：　有0个或多个输入输出：　有一个或多个输出 32

第１章数据结构绪论第四节算法分析一、算法（举例）例子：选择排序问题：递增排序解决方案：逐个选择最小数据算法框架：
第１章　数据结构绪论第四节　算法分析一、算法（举例）例子：选择排序问题：递增排序解决方案：逐个选择最小数据算法框架： for ( int i = 0; i < n-1; i++ ) { //n-1趟从a[i]检查到a[n-1]，找到最小数; 若最小整数在a[k], 交换a[i]与a[k]; } 33

第１章数据结构绪论第四节算法分析二、算法设计的要求正确性：满足具体问题的需求可读性：便于理解和修改
第１章　数据结构绪论第四节　算法分析二、算法设计的要求正确性：满足具体问题的需求可读性：便于理解和修改健壮性：当输入数据非法时，也能适当反应效率高：执行时间少空间省：执行中需要的最大存储空间 34

第１章数据结构绪论第四节算法分析三、时间复杂度衡量算法的效率，主要依据算法执行所需要的时间，即时间复杂度
第１章　数据结构绪论第四节　算法分析三、时间复杂度衡量算法的效率，主要依据算法执行所需要的时间，即时间复杂度事后统计法：计算算法开始时间与完成时间差值事前统计法：依据算法选用何种策略及问题的规模n，是常用的方法 35

第１章数据结构绪论第四节算法分析三、时间复杂度时间复杂度是问题规模n的函数f(n)，即：
第１章　数据结构绪论第四节　算法分析三、时间复杂度时间复杂度是问题规模n的函数f(n)，即： T(n) = O(f(n)) 一般地，时间复杂度用算法中最深层循环内的语句中的原操作的重复执行次数表示 36

第１章数据结构绪论第四节算法分析三、时间复杂度
第１章　数据结构绪论第四节　算法分析三、时间复杂度 a. {y *= x;} b. for (i=1; i<=n; i++} {y *= x;} c. for (j=1; j<=n; j++} for (i=1; i<=n; i++} {y *= x;} a, b, c三个算法中，“ y *= x;”程序段的时间复杂度分别为O(1), O(n), O(n2)，分别称为常量阶，线性阶，平方阶 37

第１章数据结构绪论第四节算法分析三、时间复杂度
第１章　数据结构绪论第四节　算法分析三、时间复杂度时间复杂度除常量阶[O(1)], 线性阶[O(n)], 平方阶[O(n2)]外，还有对数阶[O(logn)]，排列阶[O(n!)]，指数阶[O(2n)]等，是相对于问题规模n的增长率的表示方法指数阶随问题规模增长过快，一般不宜使用 38

第１章数据结构绪论第四节算法分析三、时间复杂度如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度
第１章　数据结构绪论第四节　算法分析三、时间复杂度如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度如果无法求取平均时间复杂度，则采用最坏情况下的时间复杂度时间复杂度是衡量算法好坏的一个最重要的标准 39

第１章数据结构绪论第四节算法分析四、空间复杂度空间复杂度指算法执行时，所需要存储空间的量度，它也是问题规模的函数，即：
第１章　数据结构绪论第四节　算法分析四、空间复杂度空间复杂度指算法执行时，所需要存储空间的量度，它也是问题规模的函数，即：　　　S(n) = O(f(n)) 40

数据结构第二章线性表深圳大学计算机系蔡茂国

第２章线性表第一节线性表一、线性数据结构的特点在数据元素的非空有限集中１、存在惟一的一个被称作“第一个”的数据元素(如“１”)
第２章　线性表第一节　线性表一、线性数据结构的特点在数据元素的非空有限集中１、存在惟一的一个被称作“第一个”的数据元素(如“１”) ２、存在惟一的一个被称作“最后一个”的数据元素(如“６”) ３、除第一个元素外，每个数据元素均只有一个前驱４、除最后一个元素外，每个数据元素均只有一个后继(next)(如“1”的next是“2”, “2”的next是“3”) 1 2 3 4 5 6 42

第２章线性表第一节线性表二、线性表线性表是最简单的一类线性数据结构
第２章　线性表第一节　线性表二、线性表线性表是最简单的一类线性数据结构线性表是由n个数据元素组成的有限序列，相邻数据元素之间存在着序偶关系，可以写为： (a1, a2,…ai-1, ai, ai+1,…an-1, an) 其中,ai是表中元素,i表示元素ai的位置,n是表的长度 43

第２章线性表第一节线性表二、线性表线性表中的元素具有相同的特性，属于同一数据对象，如：
第２章　线性表第一节　线性表二、线性表线性表中的元素具有相同的特性，属于同一数据对象，如： 1.26个字母的字母表: (A,B,C,D,…,Z) 2.近期每天的平均温度:(30℃, 28℃, 29℃,…) 44

第２章线性表第二节顺序表一、顺序表顺序表是线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素 A B C D E
第２章　线性表第二节　顺序表一、顺序表顺序表是线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素 b b+1 b+2 b+3 b … b+24 b+25 A B C D E … Y Z 45

第２章线性表第二节顺序表 b b+l … b+(i-1)*l … … … b+(n-1)*l idle 一、顺序表（元素位置）
第２章　线性表第二节　顺序表一、顺序表（元素位置）顺序表数据元素的位置： LOC(a i) = LOC( a i-1 ) + l LOC(a i) = LOC(a1)+(i-1)*l l表示元素占用的内存单元数 a1 a2 … a i … … … an … i … … … n b b+l … b+(i-1)*l … … … b+(n-1)*l idle 46

第２章线性表第二节顺序表二、顺序表的定义采用C语言中动态分配的一维数组表示顺序表 47
第２章　线性表第二节　顺序表二、顺序表的定义采用C语言中动态分配的一维数组表示顺序表 #define LIST_INIT_SIZE // 线性表存储空间的初始分配量 #define LISTINCREMENT // 线性表存储空间的分配增量 Typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量(元素数) } Sqlist; 47

第２章线性表第二节顺序表三、顺序表的初始化创建一个顺序表L 48 Status InitList_Sq(Sqlist &L) {
第２章　线性表第二节　顺序表三、顺序表的初始化创建一个顺序表L Status InitList_Sq(Sqlist &L) { L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 空表长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq 48

第２章　线性表第二节　顺序表三、顺序表的插入顺序表的插入操作是指在顺序表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，即将长度为n的顺序表： (a1,…ai-1, ai, …, an) 变成长度为n+1的顺序表： (a1,…ai-1, e, ai, …, an) 49

第２章线性表第二节顺序表三、顺序表的插入插入 e 在第3个元素与第4个元素之间插入新元素b
第２章　线性表第二节　顺序表三、顺序表的插入在第3个元素与第4个元素之间插入新元素b 需要将最后元素n至第4元素(共7-4+1)都向后移一位置   50 插入 e i=4 50

第２章　线性表第二节　顺序表三、顺序表的插入 Status ListInsert_Sq(Sqlist &L, int i, ElemType e) { if (i<1 || i>L.length+1) return ERROR; if (L.length >= L.listsize) { newbase = realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCRMENT; } // 以上皆为准备阶段 q = &(L.elem[i-1]); // 找到插入位置 for (p=&(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p; // 右移 *q = e; ++L.length; return OK; } // ListInsert_Sq // 请注意元素位置数值较元素序号少1 51

第２章线性表第二节顺序表三、顺序表的插入在顺序表中插入一个元素，需要向后移动元素个数为：n-i+1 平均移动元素数为： n+1
第２章　线性表第二节　顺序表三、顺序表的插入在顺序表中插入一个元素，需要向后移动元素个数为：n-i+1 平均移动元素数为： n+1 Eis = ∑ pi x (n-i+1) i=1 52

第２章线性表第二节顺序表三、顺序表的插入当插入位置等概率时，pi=1/(n+1)，因此： n+1
第２章　线性表第二节　顺序表三、顺序表的插入当插入位置等概率时，pi=1/(n+1)，因此： n+1 Eis = ∑ [1/(n+1)] x (n-i+1) = n/2 i=1 顺序表插入操作的时间复杂度为O(n) 53

第２章线性表第二节顺序表四、顺序表的删除顺序表的删除操作是指将顺序表的第i个数据元素删除，即将长度为n的顺序表：
第２章　线性表第二节　顺序表四、顺序表的删除顺序表的删除操作是指将顺序表的第i个数据元素删除，即将长度为n的顺序表： (a1,…ai-1, ai, ai+1,…, an) 变成长度为n-1的顺序表： (a1,…ai-1, ai+1, …, an) 54

第２章线性表第二节顺序表四、顺序表的删除删除16 将第4个元素删除需要将最后元素n至第5元素(共7-4)都向前移一位置
第２章　线性表第二节　顺序表四、顺序表的删除将第4个元素删除需要将最后元素n至第5元素(共7-4)都向前移一位置   16 删除16 i=4 55

第２章　线性表第二节　顺序表四、顺序表的删除 Status ListDelete_Sq(Sqlist &L, int i, ElemType e) { if (i<1 || i>L.length) return ERROR; p = &(L.elem[i-1]); // 找到要删除的元素位置 e = *p; q = L.elem + L.length –1; // 找到最后一个元素位置 for (++p; p<=q; ++p) *(p-1) = *p; // 左移 --L.length; // 表长减1 return OK; } // ListDelete_Sq 56

第２章线性表第二节顺序表四、顺序表的删除在顺序表中删除一个元素，需要向前移动元素个数为：n-i 平均移动元素数为： n
第２章　线性表第二节　顺序表四、顺序表的删除在顺序表中删除一个元素，需要向前移动元素个数为：n-i 平均移动元素数为： n Edl = ∑ qi x (n-i) i=1 57

第２章线性表第二节顺序表四、顺序表的删除当插入位置等概率时，qi=1/n，因此： n
第２章　线性表第二节　顺序表四、顺序表的删除当插入位置等概率时，qi=1/n，因此： n Edl = ∑ [1/n] x (n-i) = (n-1)/2 i=1 顺序表删除操作的时间复杂度为O(n) 58

第２章线性表第三节链表五、顺序表的优缺点优点：元素可以随机存取元素位置可用一个简单、直观的公式表示并求取缺点：
第２章　线性表第三节　链表五、顺序表的优缺点　优点：元素可以随机存取元素位置可用一个简单、直观的公式表示并求取　缺点：在作插入或删除操作时，需要移动大量元素 59

第２章线性表第二节线性链表一、链表链表是线性表的链式存储表示
第２章　线性表第二节　线性链表一、链表链表是线性表的链式存储表示链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系　线性表的链式存储表示主要有三种形式：线性链表循环链表双向链表 60

第２章线性表第二节线性链表 data next 二、线性链表线性链表的元素称为结点(node)
第２章　线性表第二节　线性链表二、线性链表线性链表的元素称为结点(node) 结点除包含数据元素信息的数据域外，还包含指示直接后继的指针域每个结点，在需要时动态生成，在删除时释放 data next 61

第２章线性表第二节线性链表二、线性链表动态单独生成结点的线性链表也称单链表线性链表可由头指针惟一确定
第２章　线性表第二节　线性链表二、线性链表动态单独生成结点的线性链表也称单链表线性链表可由头指针惟一确定为了操作方便，有时在线性链表的第一个结点之前附设一个头结点，其数据域可以为空，也可以为线性链表的长度信息。 4 a1 a2 a3 a4  L 62

第２章线性表第二节线性链表 data next 三、线性链表的定义定义一个结点 63 typedef struct LNode {
第２章　线性表第二节　线性链表三、线性链表的定义定义一个结点 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 后继指针 } LNode, *LinkList; data next 63

第２章线性表第二节线性链表四、找指定元素在线性链表中找第i个元素
第２章　线性表第二节　线性链表四、找指定元素在线性链表中找第i个元素由于线性链表中元素的存储位置具有随机性，因此，只有从头结点开始，顺链一步步查找 n a1 ai an  L … 64

第２章线性表第二节线性链表四、找指定元素 … a1 ai an n L  65
第２章　线性表第二节　线性链表四、找指定元素 Status GetElem_L(LinkList &L, int i, ElemType &e) { // L为带头结点的单链表的头指针，e为返回值 p = L->next; j=1; // p指向第一个结点 while (p && j<i) {p = p->next; j++;} // 顺指针查指 if (!p || j>i) return ERROR; // 第i元素不存在 e = p->data; // 取第i元素值 return OK; } // GetElem_L n a1 ai an  L … 65

第２章线性表第二节线性链表四、找指定元素算法时间复杂度主要取决于while循环中的语句频度频度与被查找元素在单链表中的位置有关
第２章　线性表第二节　线性链表四、找指定元素算法时间复杂度主要取决于while循环中的语句频度频度与被查找元素在单链表中的位置有关若1≤i≤n，则频度为i-1，否则为n 因此时间复杂度为O(n) n a1 ai an  L … 66

第２章线性表第二节线性链表五、线性链表的插入在线性链表的第i-1元素与第i元素之间插入一个新元素 ai-1 ai e ai-1
第２章　线性表第二节　线性链表五、线性链表的插入在线性链表的第i-1元素与第i元素之间插入一个新元素 s->next = p->next; p->next = s; ai-1 ai s … e 插入前 p … ai-1 ai s e 插入后 p 67

第２章线性表第二节线性链表五、线性链表的插入 68
第２章　线性表第二节　线性链表五、线性链表的插入 Status ListInsert_L(LinkList &L, int i, ElemType e) { // 在带头结点的单链表L中第i个位置之前插入元素e p = L; j = 0; while (p && j<i-1) {p = p->next; j++;} // 寻找i-1结点 if (!p || j>i-1) return ERROR; s = (LinkList) malloc(sizeof(LNode); // 生成新结点 s->data = e; s->next = p->next; p->next = s; // 插入L中 return OK; } // ListInsert_L 68

第２章线性表第二节线性链表五、线性链表的插入同样，算法时间复杂度主要取决于while循环中的语句频度
第２章　线性表第二节　线性链表五、线性链表的插入同样，算法时间复杂度主要取决于while循环中的语句频度频度与在线性链表中的元素插入位置有关因此线性链表插入的时间复杂度为O(n) 69

第２章线性表第二节线性链表六、线性链表的删除将线性链表的第i元素删除 p ai-1 ai+1 ai 删除前  ai-1 ai
第２章　线性表第二节　线性链表六、线性链表的删除将线性链表的第i元素删除 p ai-1 ai+1 ai 删除前 p->next = p->next ->next  ai-1 ai ai+1 p q 删除后 70

第２章线性表第二节线性链表六、线性链表的删除 71
第２章　线性表第二节　线性链表六、线性链表的删除 Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 在带头结点的单链表L中，删除第i个位置的元素 p = L; j = 0; while (p->next && j<i-1) {p = p->next; j++;} // 寻找i结点 if (!p->next || j>i-1) return ERROR; q = p->next; p->next = q->next; // 删除i结点 e = q->data; free(q); // 取值并释放结点 return OK; } // ListDelete_L 71

第２章线性表第二节线性链表六、线性链表的删除同样，算法时间复杂度主要取决于while循环中的语句频度
第２章　线性表第二节　线性链表六、线性链表的删除同样，算法时间复杂度主要取决于while循环中的语句频度频度与被删除元素在线性链表中的位置有关因此线性链表删除元素的时间复杂度为O(n) 72

第２章线性表第二节线性链表七、静态链表线性链表也可以采用静态数组实现与顺序表有两点不同：１、每个元素包括数据域和指针域
第２章　线性表第二节　线性链表七、静态链表线性链表也可以采用静态数组实现与顺序表有两点不同：１、每个元素包括数据域和指针域２、元素的逻辑关系由指针确定 … D C F B A E … 7 5 9 2 ^ 8 3 6 10 4 11 数据指针 73

第２章线性表第二节线性链表七、静态链表与单链表区别：１、静态链表暂时不用结点，链成一个备用链表２、插入时，从备用链表中申请结点
第２章　线性表第二节　线性链表七、静态链表与单链表区别：１、静态链表暂时不用结点，链成一个备用链表２、插入时，从备用链表中申请结点３、删除结点时，将结点放入备用链表 74

第２章线性表第三节循环链表一、循环链表循环链表是一种特殊的线性链表循环链表中最后一个结点的指针域指向头结点，整个链表形成一个环。
第２章　线性表第三节　循环链表一、循环链表循环链表是一种特殊的线性链表循环链表中最后一个结点的指针域指向头结点，整个链表形成一个环。 n a1 ai an L … 75

第２章线性表第三节循环链表二、查找、插入和删除在循环链表中查找指定元素，插入一个结点或删除一个结点的操作与线性链表基本一致
第２章　线性表第三节　循环链表二、查找、插入和删除在循环链表中查找指定元素，插入一个结点或删除一个结点的操作与线性链表基本一致差别仅在于算法中的循环条件不是p->next或p是否为空(^)，而是它们是否等于头指针(L) n a1 ai an L … 76

第２章线性表第四节双向链表一、双向链表双向链表也是一种特殊的线性链表
第２章　线性表第四节　双向链表一、双向链表双向链表也是一种特殊的线性链表双向链表中每个结点有两个指针，一个指针指向直接后继(next)，另一个指向直接前驱(prior) prior data next 指向直接前驱指向直接后继 77

第２章线性表第四节双向链表二、双向循环链表双向循环链表中存在两个环(一个是直接后继环(红)，另一个是直接前驱环(蓝)) L
第２章　线性表第四节　双向链表二、双向循环链表双向循环链表中存在两个环(一个是直接后继环(红)，另一个是直接前驱环(蓝)) 非空表空表 L 78

第２章线性表第四节双向链表三、双向链表的定义定义一个双向链表的结点对于任何一个中间结点有：
第２章　线性表第四节　双向链表三、双向链表的定义定义一个双向链表的结点 Typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList; 对于任何一个中间结点有： p = p->next->prior p = p->prior->next prior data next 指向直接前驱指向直接后继 79

第２章线性表第四节双向链表四、双向链表的插入双向链表的插入操作需要改变两个方向的指针 p p s L 31 48 15 L 31
第２章　线性表第四节　双向链表四、双向链表的插入双向链表的插入操作需要改变两个方向的指针 s->next = p; s->prior = p->prior; p->prior->next = s; p->prior = s; L 31 48 15 p L 31 48 25 15 p s 80

第２章线性表第四节双向链表四、双向链表的删除双向链表的删除操作需要改变两个方向的指针 p L 31 48 15 L 31 15
第２章　线性表第四节　双向链表四、双向链表的删除双向链表的删除操作需要改变两个方向的指针 L 31 48 15 p L 31 15 p->prior->next = p->next; p->next->prior = p->prior; 81

第２章线性表第五节顺序表与链表的比较一、基于空间的比较存储分配的方式
第２章　线性表第五节　顺序表与链表的比较一、基于空间的比较存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度 = 1 链表的存储密度 < 1 82

第２章线性表第五节顺序表与链表的比较二、基于时间的比较存取方式插入/删除时移动元素个数顺序表可以随机存取，也可以顺序存取
第２章　线性表第五节　顺序表与链表的比较二、基于时间的比较存取方式顺序表可以随机存取，也可以顺序存取链表必须顺序存取插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素，只需要修改指针 83

第２章线性表第五节顺序表与链表的比较三、基于应用的比较如果线性表主要是存储大量的数据，并主要用于查找时，采用顺序表较好，如数据库
第２章　线性表第五节　顺序表与链表的比较三、基于应用的比较如果线性表主要是存储大量的数据，并主要用于查找时，采用顺序表较好，如数据库如果线性表存储的数据元素经常需要做插入与删除操作，则采用链表较好，如操作系统中进程控制块(PCB)的管理，内存空间的管理等 84

数据结构第三章栈和队列深圳大学计算机系蔡茂国

第３章栈和队列第一节栈一、栈栈是限定仅在表尾(top)进行插入或删除操作的线性表。
第３章　栈和队列第一节　栈一、栈 a1 top bottom an . 进栈出栈栈是限定仅在表尾(top)进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top，表尾)，另一端称为栈底(bottom，表头) 特点：后进先出 (LIFO) 86

第３章栈和队列第一节栈二、栈的实现栈的存储结构主要有两种： 1. 顺序栈 2. 链式栈 87 top ^ data next …
第３章　栈和队列第一节　栈二、栈的实现栈的存储结构主要有两种： 1. 顺序栈 2. 链式栈 top ^ data next … 栈底栈顶 a1 top base an . 进栈出栈 87

第３章栈和队列第二节顺序栈一、顺序栈顺序栈是栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素
第３章　栈和队列第二节　顺序栈一、顺序栈顺序栈是栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素指针top指向栈顶元素在顺序栈中的下一个位置， base为栈底指针，指向栈底的位置。 a1 top base an . 进栈出栈 88

第３章栈和队列第二节顺表栈二、顺序栈的定义采用C语言中动态分配的一维数组表示顺序表 89
第３章　栈和队列第二节　顺表栈二、顺序栈的定义采用C语言中动态分配的一维数组表示顺序表 #define STACK_INIT_SIZE // 栈存储空间的初始分配量 #define STACKINCREMENT // 栈存储空间的分配增量 Typedef struct { SElemType *base // 存储空间基址 SElemType *top; // 当前长度 int stacksize; // 当前分配的存储容量(元素数) } SqStack; 89

第３章栈和队列第二节顺序栈三、顺序栈的特性 top=0 或top=base 表示空栈 base=NULL表示栈不存在
第３章　栈和队列第二节　顺序栈三、顺序栈的特性 top=0 或top=base 表示空栈 base=NULL表示栈不存在当插入新的栈顶元素时,指针top+1 删除栈顶元素时，指针top-1 当top>stacksize时，栈满，溢出 a1 top base an . 进栈出栈 90

第３章栈和队列第二节顺序栈四、顺序栈的主要操作 ADT Stack {
第３章　栈和队列第二节　顺序栈四、顺序栈的主要操作 ADT Stack { 数据对象：D = {ai | ai∈ElemSet, i=1,2,3,…,n} 数据关系：R = {<ai-1, ai> | ai-1,ai∈D} 基本操作：InitStack(&S) // 构造空栈 Push(&S, e) // 进栈 Pop(&S, &e) // 出栈 GetTop(S, &e) // 取栈顶元素值　　StackEmpty(S) // 栈是否为空　 } ADT Stack 91

第３章栈和队列第二节顺序栈五、创建顺序栈 92 Status InitStack(SqStack &S) {
第３章　栈和队列第二节　顺序栈五、创建顺序栈 Status InitStack(SqStack &S) { S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } // InitStack top base 空栈 92

第３章栈和队列第二节顺序栈六、进栈（插入新元素） 93 Status Push(SqStack &S, SElemType e) {
第３章　栈和队列第二节　顺序栈六、进栈（插入新元素） Status Push(SqStack &S, SElemType e) { if (S.top – S.base >= S.stacksize) { // 栈满，追加存储空间 S.base = (SElemType *) realloc(S.base, (S.stacksize + STACKINCRMENT* sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCRMENT;} *S.top++ = e; return OK; } // Push top base b a 操作前 top base e b a e进栈 93

第３章栈和队列第二节顺序栈七、出栈（删除元素） 94 Status Pop(SqStack &S, SElemType &e) {
第３章　栈和队列第二节　顺序栈七、出栈（删除元素） Status Pop(SqStack &S, SElemType &e) { if (S.top == S.base) return ERROR; e = *--S.top; return OK; } // Pop top base e b a 操作前 top base e b a e出栈 94

第３章栈和队列第二节顺序栈八、取栈顶元素 95 Status GetTop(SqStack S, SElemType &e) {
第３章　栈和队列第二节　顺序栈八、取栈顶元素 Status GetTop(SqStack S, SElemType &e) { if (S.top == S.base) return ERROR; e = *(S.top-1); return OK; } // GetTop top base e b a 操作前 top base e b a e进栈 95

第３章栈和队列第三节栈的应用举例一、数值转换计算顺序输出顺序将十进制转换为其它进制(d)，其原理为：
第３章　栈和队列第三节　栈的应用举例一、数值转换将十进制转换为其它进制(d)，其原理为： N = (N/d)*d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N /8 N mod 8 输出顺序计算顺序 96

第３章栈和队列第三节栈的应用举例一、数值转换 97 void conversion () {
第３章　栈和队列第三节　栈的应用举例一、数值转换 void conversion () { InitStack(S); // 创建新栈S scanf (“%d”,N); // 输入一个十进制数N while (N) { Push(S, N % 8); // 将余数送入栈中 N = N/8; // 求整除数 } while (!StackEmpty(S)) { // 如果栈不空 Pop(S,e); // 将栈中数出栈 printf ( "%d", e ); } // conversion 97

第３章栈和队列第三节栈的应用举例二、行编辑程序用户输入一行字符允许用户输入出差错，并在发现有误时，可以用退格符“#”及时更正
第３章　栈和队列第三节　栈的应用举例二、行编辑程序用户输入一行字符允许用户输入出差错，并在发现有误时，可以用退格符“#”及时更正假设从终端接受两行字符： whli##ilr#e（s#*s) 实际有效行为： while (*s) 98

第３章栈和队列第三节栈的应用举例二、行编辑程序对用户输入的一行字符进行处理，直到行结束(“\n”) 99
第３章　栈和队列第三节　栈的应用举例二、行编辑程序对用户输入的一行字符进行处理，直到行结束(“\n”) ch = getchar(); // 从终端输入一个字符 while (ch != ’\n’) { switch(ch) { case ’#’: Pop(S, c); break; // 仅当栈非空时退栈 default: Push(S, ch); break; // 有效字符进栈 } ch = getchar(); // 从终端输入一个字符将从栈底到栈顶的栈内字符传送到调用过程的数据区; 99

第３章栈和队列第三节栈的应用举例三、迷宫求解迷宫求解一般采用“穷举法”
第３章　栈和队列第三节　栈的应用举例三、迷宫求解迷宫求解一般采用“穷举法” 逐一沿顺时针方向查找相邻块（一共四块－东 (右)、南(下)，西(左)、北(上)）是否可通，即该相邻块既是通道块，且不在当前路径上用一个栈来记录已走过的路径 100100

第３章　栈和队列第三节　栈的应用举例三、迷宫求解举例 # 101101

第３章栈和队列第三节栈的应用举例三、迷宫求解（算法）设定当前位置为入口位置 do {若当前位置可通，则 {
第３章　栈和队列第三节　栈的应用举例三、迷宫求解（算法）设定当前位置为入口位置　do {若当前位置可通，则 { 　将该位置插入栈顶(Push)；若该位置是出口，则结束　否则切换当前位置的东邻方块为当前位置； } 否则 { 　若栈不空则｛　如果栈顶位置的四周均不可通,则删除栈顶位置(Pop) 　并重新测试新的栈顶位置　　如果找到栈顶位置的下一方向未经探索，则将该方向　　方块设为当前位置}}}while(栈不空)；找不到路径；

第３章栈和队列第三节栈的应用举例四、表达式求值表达式由操作数、运算符和界限符组成，它们皆称为单词操作数：常数或变量
第３章　栈和队列第三节　栈的应用举例四、表达式求值　　表达式由操作数、运算符和界限符组成，它们皆称为单词操作数：常数或变量运算符：+, -, *, / 等界限符：(, ), #(表达式开始及结束符) 103103

第３章　栈和队列第三节　栈的应用举例四、表达式求值　设置两个栈：操作数栈（OPND）运算符栈（OPTR） 104104

第３章栈和队列第三节栈的应用举例四、表达式求值运算符的优先级关系新运算符运算符栈顶元素 105105 + - * / ( )
第３章　栈和队列第三节　栈的应用举例四、表达式求值运算符的优先级关系新运算符 + - * / ( ) # > < = 出错运算符栈顶元素 105105

第３章栈和队列第三节栈的应用举例四、表达式求值（算法）置运算符栈(OPTR)和操作数栈(OPND)为空
第３章　栈和队列第三节　栈的应用举例四、表达式求值（算法）从栈顶取出元素，包括取值及删除栈顶元素两个过程置运算符栈(OPTR)和操作数栈(OPND)为空 ’#’插入OPTR栈；取表达式第一个单词； while(单词或 OPTR栈顶元素不为’#’) { 　若单词是操作数，则插入OPND栈顶，且取下一个单词　否则｛ OPTR栈顶元素优先级与新运算符优先级关系为：　　小于，则插入OPTR栈顶，取下一单词　　等于，则删除OPTR栈顶元素，取下一单词　　大于，则从OPND栈顶依次取出两个操作数，用从OPTR 　　　　　栈顶取出的元素进行计算，结果插入OPND栈顶}}

第３章栈和队列第四节队列一、队列队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。
第３章　栈和队列第四节　队列一、队列队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为对头(front)。特点：先进先出 (FIFO) a1 a2 a an 出队入队  队头队尾 107107

第３章栈和队列第四节队列二、顺序队列顺序队列：采用一组地址连续的存储单元依次存储从队列头到队列尾的元素
第３章　栈和队列第四节　队列二、顺序队列顺序队列：采用一组地址连续的存储单元依次存储从队列头到队列尾的元素顺序队列有两个指针：队头指针front和队尾指针rear 108108

第３章栈和队列第四节队列三、顺序队列的进队和出队原则
第３章　栈和队列第四节　队列三、顺序队列的进队和出队原则进队时，新元素按rear指针位置插入，然后队尾指针增一，即 rear = rear + 1 出队时，将队头指针位置的元素取出，然后队头指针增一，即 front = front + 1 队头指针始终指向队列头元素队尾指针始终指向队列尾元素的下一个位置 109109

第３章栈和队列第四节队列四、顺序队列的进队和出队举例 A B C D B C D C D C D E F G C D E F G
第３章　栈和队列第四节　队列四、顺序队列的进队和出队举例 A B C D front rear 空队列 front rear A,B,C,D进队 B C D C D front rear A退队 front rear B退队 C D E F G C D E F G front rear E,F,G进队 front rear H进队,溢出 110110

第３章栈和队列第四节队列五、顺序队列存在的问题当队尾指针指向队列存储结构中的最后单元时，如果再继续插入新的元素，则会产生溢出
第３章　栈和队列第四节　队列五、顺序队列存在的问题当队尾指针指向队列存储结构中的最后单元时，如果再继续插入新的元素，则会产生溢出当队列发生溢出时，队列存储结构中可能还存在一些空白位置（已被取走数据的元素）解决办法之一：将队列存储结构首尾相接，形成循环(环形)队列 111111

第３章栈和队列第五节循环队列一、循环队列循环队列采用一组地址连续的存储单元将整个队列的存储单元首尾相连 112112 C 1 2
第３章　栈和队列第五节　循环队列一、循环队列循环队列采用一组地址连续的存储单元将整个队列的存储单元首尾相连 C 1 2 3 4 5 6 front MAXQSIZE-1 D E A B rear 112112

第３章栈和队列第五节循环队列二、循环队列空与满 front = rear，循环队列空
第３章　栈和队列第五节　循环队列二、循环队列空与满 front = rear，循环队列空 (rear+1) % MAXQSIZE = front，循环队列满 C 1 2 3 4 5 6 front MAXQSIZE-1 rear 队列空 C D E F G B H 1 2 3 4 5 6 front MAXQSIZE-1 rear 队列满 113113

第３章栈和队列第五节循环队列三、循环队列定义 114114 #define MAXQSIZE 100
第３章　栈和队列第五节　循环队列三、循环队列定义 #define MAXQSIZE 100 Typedef struct { QElemType *base; int front; int rear; } SqQueue; C D E F 1 2 3 4 5 6 front base rear 114114

第３章栈和队列第五节循环队列三、循环队列插入元素 115115
第３章　栈和队列第五节　循环队列三、循环队列插入元素 Status EnQueue(SqQueue &Q, QElemType e) { if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; //队满 Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return OK; } C D E F G B H 1 2 3 4 5 6 front MAXQSIZE-1 rear 115115

第３章栈和队列第五节循环队列三、循环队列删除元素 116116
第３章　栈和队列第五节　循环队列三、循环队列删除元素 Status DeQueue(SqQueue &Q, QElemType e) { if (Q.rear == Q.front) return ERROR; //队空 e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return OK; } C 1 2 3 4 5 6 front rear 116116

第３章栈和队列第六节链队列一、链队列链队列采用链表存储单元链队列中，有两个分别指示队头和队尾的指针。
第３章　栈和队列第六节　链队列一、链队列链队列采用链表存储单元链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。 data next front rear 117117

第３章栈和队列第六节链队列二、链队列指针变化状况链队列是链表操作的子集 front rear x y ^ 元素y入队元素x出队
第３章　栈和队列第六节　链队列二、链队列指针变化状况链队列是链表操作的子集 front rear x y ^ 元素y入队元素x出队空队列 118118

数据结构第四章串深圳大学计算机系蔡茂国

第４章串第一节字符串一、字符串（string）字符串是n(≥0)个字符的有限序列，记作： S = ‘a1a2a3…an’
第４章　串第一节　字符串一、字符串（string）字符串是n(≥0)个字符的有限序列，记作： S = ‘a1a2a3…an’ 其中，S 是串名字 ‘a1a2a3…an’是串值 ai 是串中字符 n 是串的长度(串中字符的个数) 例如, S = “Shenzhen University” 120120

第４章串第一节字符串二、字符串术语空串：不含任何字符的串，串长度=0 空格串：仅由一个或多个空格组成的串
第４章　串第一节　字符串二、字符串术语空串：不含任何字符的串，串长度=0 空格串：仅由一个或多个空格组成的串子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。如：A=’Shenzhen University’ B=’University’ A为主串，B为子串。 121121

第４章串第一节字符串二、字符串术语位置：字符在序列中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。
第４章　串第一节　字符串二、字符串术语位置：字符在序列中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。模式匹配：确定子串在主串中首次出现的位置的运算 122122

第４章串第一节字符串三、字符串与线性表的关系串的逻辑结构和线性表极为相似，它们都是线性结构串中的每个字符都仅有一个前驱和一个后继
第４章　串第一节　字符串三、字符串与线性表的关系串的逻辑结构和线性表极为相似，它们都是线性结构串中的每个字符都仅有一个前驱和一个后继 123123

第４章串第一节字符串三、字符串与线性表的关系串与线性表又有区别，主要表现为：串的数据对象约定是字符集
第４章　串第一节　字符串三、字符串与线性表的关系　串与线性表又有区别，主要表现为：串的数据对象约定是字符集在线性表的基本操作中，以“单个元素”作为操作对象在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、在串的某个位置上插入一个子串等。 124124

第４章串第二节串的表示和实现一、定长顺序存储表示用一组地址连续的存储单元存储字符序列
第４章　串第二节　串的表示和实现一、定长顺序存储表示用一组地址连续的存储单元存储字符序列如C语言中的字符串定义(以“\0”为串结束标志) char Str[MAXSTRLEN+1]; 定义了长度为MAXSTRLEN字符存储空间字符串长度可以是小于MAXSTRLEN的任何值（最长串长度有限制，多余部分将被截断） 125125

第４章串第二节串的表示和实现二、堆分配存储表示在程序执行过程中，动态分配（malloc）一组地址连续的存储单元存储字符序列
第４章　串第二节　串的表示和实现二、堆分配存储表示在程序执行过程中，动态分配（malloc）一组地址连续的存储单元存储字符序列在C语言中，由malloc()和free()动态分配与回收的存储空间称为堆堆分配存储结构的串既有顺序存储结构的特点，处理方便,操作中对串长又没有限制,更显灵活 126126

第４章串第二节串的表示和实现三、链存储表示采用链表方式存储串值每个结点中，可以存放一个字符，也可以存放多个字符 H e l ^
第４章　串第二节　串的表示和实现三、链存储表示采用链表方式存储串值每个结点中，可以存放一个字符，也可以存放多个字符 H e l ^ S S h e n d ^ a # 127127

第４章串第三节串的匹配算法一、求子串位置函数Index() 子串的定位操作通常称做串的模式匹配算法（穷举法）：
第４章　串第三节　串的匹配算法一、求子串位置函数Index() 子串的定位操作通常称做串的模式匹配算法（穷举法）：从主串的指定位置开始，将主串与模式（要查找的子串）的第一个字符比较， 1.若相等，则继续逐个比较后续字符； 2.若不等，从主串的下一个字符起再重新和模式的字符比较 128128

第４章串第三节串的匹配算法一、求子串位置函数Index() 129129
第４章　串第三节　串的匹配算法一、求子串位置函数Index() Int Index(Sstring S, Sstring T, int pos) { //S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构 i = pos; j = 1; // 从第一个位置开始比较 while (i<=S[0] && j<=T[0]) { if (S[i] == T[j]) {++i; ++j;} // 继续比较后继字符 else {i = i – j + 2; j = 1;} // 指针后退重新开始匹配 } if (j > T[0]) return i-T[0]; // 返回与模式第一字符相等 else return 0; // 匹配不成功 // 的字符在主串中的序号 129129

第４章串第三节串的匹配算法一、求子串位置函数Index()
第４章　串第三节　串的匹配算法一、求子串位置函数Index() 在最好的情况下，除比较成功的位置外，其余位置仅需比较一次（模式第一个字符），其时间复杂度为：O(n+m)(n，m分别为主串和模式的长度) 但在最坏的情况下，如模式为‘ ’，主串为 ‘ ’, 则每次模式的前7个0都要与主串逐一比较，因此，其时间复杂度为：O(n*m) 130130

第４章　串第三节　串的匹配算法二、KMP算法是index函数的一种改进,由D.E.Knuth(克努特)－J.H.Morris(莫里斯)－V.R.Pratt(普拉特)发现当一趟匹配过程中出现字符比较不等(失配)时 1.不需回溯i指针 2.利用已经得到的“部分匹配”的结果 3.将模式向右“滑动”尽可能远的一段距离(next[j])后，继续进行比较 131131

第４章串第三节串的匹配算法二、KMP算法(举例) 假设主串ababcabcacbab,模式abcac,改进算法的匹配过程如下
第４章　串第三节　串的匹配算法二、KMP算法(举例) 假设主串ababcabcacbab,模式abcac,改进算法的匹配过程如下 ↓i=3 第一趟匹配 a b a b c a b c a c b a b a b c ↑j=3 ↓i=3----7 第二趟匹配 a b a b c a b c a c b a b a b c a c ↑j=1 ↓i=7--10 第三趟匹配 a b a b c a b c a c b a b ↑j=2 132132

第４章串第三节串的匹配算法二、KMP算法假设主串为‘s1s2s3…sn’,模式串为‘p1p2p3…pm’
第４章　串第三节　串的匹配算法二、KMP算法假设主串为‘s1s2s3…sn’,模式串为‘p1p2p3…pm’ 若主串中第i个字符与模式串中第j个字符“失配”(si!=pj),需要与模式串中第k(k<j)个字符比较,则有以下关系成立： ‘p1p2…pk-1’ = ‘si-k+1si-k+2…si-1’ 而已经得到的“部分匹配”结果为：　　　 ‘pj-k+1pj-k+2…pj-1’ = ‘si-k+1si-k+2…si-1’ 133133

第４章串第三节串的匹配算法二、KMP算法从而有下式成立： ‘p1p2…pk-1’ = ‘pj-k+1pj-k+2…pj-1’
第４章　串第三节　串的匹配算法二、KMP算法从而有下式成立： ‘p1p2…pk-1’ = ‘pj-k+1pj-k+2…pj-1’ 上式是只依赖于模式串的关系式上式说明,在主串中第i个字符“失配”时,仅需与模式串中的第k个字符再开始比较（不需要回溯） 134134

第４章　串第三节　串的匹配算法二、KMP算法或者换言之,在模式串中第j个字符“失配”时, 模式串第k个字符再同主串中对应的失配位置 (i)的字符继续进行比较　　　‘p1p2…pk-1’ = ‘pj-k+1pj-k+2…pj-1’ k值可以在作串的匹配之前求出一般用next函数求取k值 135135

第４章串第三节串的匹配算法二、KMP算法(next函数) next函数定义为： 0 当j=1时
第４章　串第三节　串的匹配算法二、KMP算法(next函数) next函数定义为：　0 当j=1时 next[j] =　max{k | 1<k<j且‘p1…pk-1’=‘pj-k+1…pj-1’ 　1 其它情况如k=2,则p1=pj-1 　　　(有1个字符相同)[除j=2外]; 　k=3,则p1p2=pj-2pj-1(有2个字符相同); 136136

第４章串第三节串的匹配算法二、KMP算法(next函数举例) 现有模式串abcac,求其next值 j 1 2 3 4 5 模式串
第４章　串第三节　串的匹配算法二、KMP算法(next函数举例) 现有模式串abcac,求其next值 j 1 2 3 4 5 模式串 a b c next[j] 137137

第４章串第三节串的匹配算法二、KMP算法(next函数举例) 现有模式串abaabacaca,求其next值 j 1 2 3 4 5
第４章　串第三节　串的匹配算法二、KMP算法(next函数举例) 现有模式串abaabacaca,求其next值 j 1 2 3 4 5 6 7 8 9 10 模式串 a b c next[j] 138138

第４章串第三节串的匹配算法二、KMP算法(利用next函数) 利用next函数,可写出KMP算法如下：
第４章　串第三节　串的匹配算法二、KMP算法(利用next函数) 利用next函数,可写出KMP算法如下： 1. 令i的初值为pos,j的初值为1 2. While((i<主串长度)且(j<模式串长度)) { (1).若j=0或者si=pj,则i++, j++ (2).否则,j=next[j] }　 j=0表示第一个字符失配 139139

第４章串第三节串的匹配算法二、KMP算法(C语言实现) 140140
第４章　串第三节　串的匹配算法二、KMP算法(C语言实现) Int Index_KMP(Sstring S, Sstring T, int pos) { //S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构 i = pos; j = 1; // 从第一个位置开始比较 while (i<=S[0] && j<=T[0]) { if ((j==0) || S[i] == T[j])){++i; ++j;} // 继续比较后继字符 else j = next[j]; // 模式串向右移 } if (j > T[0]) return i-T[0]; // 返回与模式第一字符相等 else return 0; // 匹配不成功 // 的字符在主串中的序号 140140

第４章串第三节串的匹配算法二、KMP算法(时间复杂度) Index_KMP()函数的时间复杂度为O(n)
第４章　串第三节　串的匹配算法二、KMP算法(时间复杂度) Index_KMP()函数的时间复杂度为O(n) 为了求模式串的next值,其算法与Index_KMP很相似,其时间复杂度为O(m) 因此,KMP算法的时间复杂度为O(n+m) 141141

数据结构第六章树与二叉树深圳大学计算机系蔡茂国

第６章树与二叉树第一节树的概念与基本术语一、树的定义(Tree) 树是有n(n≥0)个结点的有限集合。如果 n=0，称为空树；
第６章　树与二叉树第一节　树的概念与基本术语一、树的定义(Tree) 树是有n(n≥0)个结点的有限集合。如果 n=0，称为空树；如果 n>0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱) 如果 n>1，则除根以外的其它结点划分为 m (m>0)个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。每个结点都有唯一的直接前驱，但可能有多个后继 143143

第６章树与二叉树第一节树的概念与基本术语一、树的定义(举例) A C G B D E F K L H M I J
第６章　树与二叉树第一节　树的概念与基本术语一、树的定义(举例) A C G B D E F K L H M I J A 只有根结点的树有13个结点的树其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树 144144

第６章树与二叉树第一节树的概念与基本术语二、树的基本术语结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数
第６章　树与二叉树第一节　树的概念与基本术语二、树的基本术语结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数叶结点：度为0的结点[没有子树的结点] 分支结点：度不为0 　的结点[包括根结点]，　也称为非终端结点。　除根外称为内部结点 1层 2层 4层 3层 Height = 4 A C G B D E F K L H M I J 145145

第６章树与二叉树第一节树的概念与基本术语二、树的基本术语孩子：结点的子树的根[直接后继，可能有多个]
第６章　树与二叉树第一节　树的概念与基本术语二、树的基本术语孩子：结点的子树的根[直接后继，可能有多个] 双亲：孩子的直接前驱[最多只能有一个] 兄弟：同一双亲的孩子子孙：以某结点为根的　树中的所有结点祖先：从根到该结点　所经分支上的所有结点 1层 2层 4层 3层 Height = 4 A C G B D E F K L H M I J 146146

第６章树与二叉树第一节树的概念与基本术语二、树的基本术语层次：根结点为第一层，其孩子为第二层，依此类推深度：树中结点的最大层次
第６章　树与二叉树第一节　树的概念与基本术语二、树的基本术语层次：根结点为第一层，其孩子为第二层，依此类推深度：树中结点的最大层次森林：互不相交的树的集合。　对树中每个结点而言，　其子树的集合即为森林 1层 2层 4层 3层 Height = 4 A C G B D E F K L H M I J 147147

第６章树与二叉树第二节二叉树一、二叉树(Binary Tree) 二叉树是一种特殊的树每个结点最多有２棵子树
第６章　树与二叉树第二节　二叉树一、二叉树(Binary Tree) 二叉树是一种特殊的树每个结点最多有２棵子树二叉树的子树有左右之分 L R 空树　　只有根　　只有左子树　只有右子树　　有左右子树 148148

第６章树与二叉树第二节二叉树二、二叉树性质１在二叉树的第i层上至多有2i-1个结点证明：
第６章　树与二叉树第二节　二叉树二、二叉树性质１在二叉树的第i层上至多有2i-1个结点证明： 1.i=1, 只有一个根节点，因此2i-1=20=1 2.设第i-1层上，以上性质成立，即第i-1层至多有2(i-1)-1结点。由二叉树的定义可知，任何结点的度小于2，因此，第i层上的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1 149149

第６章树与二叉树第二节二叉树三、二叉树性质２深度为k的二叉树至多有2k-1个结点证明：
第６章　树与二叉树第二节　二叉树三、二叉树性质２深度为k的二叉树至多有2k-1个结点证明： 1.由性质１，已知第i层上结点数最多为2i-1 　 k 2.　∑ 2i-1 = 2k-1 i=1 150150

第６章树与二叉树第二节二叉树四、二叉树性质３如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明：
第６章　树与二叉树第二节　二叉树四、二叉树性质３如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明： 1.设n1为度为1的结点，则总结点数= n0+n1+n2 2.设B为二叉树的分支数，除根结点外，每个结点有且只有一个分支，因此n=B+1 3.每个分支皆由度为1或2的结点发出，B=n1+2n2 4.n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1 151151

第６章树与二叉树第二节二叉树五、满二叉树一个深度为k且有2k-1个结点的二叉树每层上的结点数都是最大数可以自上而下、
第６章　树与二叉树第二节　二叉树五、满二叉树一个深度为k且有2k-1个结点的二叉树每层上的结点数都是最大数可以自上而下、　自左至右连续编号 6 2 1 7 5 4 3 8 9 10 11 13 14 15 12 152152

第６章树与二叉树第二节二叉树六、完全二叉树当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树
第６章　树与二叉树第二节　二叉树六、完全二叉树当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树叶子结点只在最大两层上出现左子树深度与右子树　深度相等或大１ 6 2 1 7 5 4 3 8 9 10 11 12 153153

第６章树与二叉树第二节二叉树六、完全二叉树(性质４) 具有n个结点的完全二叉树,其深度为log2n +1
第６章　树与二叉树第二节　二叉树六、完全二叉树(性质４) 具有n个结点的完全二叉树,其深度为log2n +1 设k为深度，由二叉树性质２，已知　　 2k-1-1 < n ≤ 2k-1 即　 2k-1 ≤ n < 2k 即 k = log2n +1 6 2 1 7 5 4 3 8 9 10 11 12 154154

第６章树与二叉树第二节二叉树六、完全二叉树(性质５) 在完全二叉树中，结点i的双亲为i/2 结点i的左孩子LCHILD(i)=2i
第６章　树与二叉树第二节　二叉树六、完全二叉树(性质５) 在完全二叉树中，结点i的双亲为i/2 结点i的左孩子LCHILD(i)=2i 结点i的右孩子RCHILD(i)=2i+1 6 2 1 7 5 4 3 8 9 10 11 12 2i+2 i 2i+3 2i+1 2i i+1 i/2 155155

第６章树与二叉树第二节二叉树七、二叉树的顺序存储结构 1 2 3 4 5 6 7 8 910
第６章　树与二叉树第二节　二叉树七、二叉树的顺序存储结构用一组连续的存储单元依次自上而下,自左至右存储结点 1 2 4 8 9 10 5 6 7 3 9 1 2 3 6 4 7 8 10 5 完全二叉树的顺序表示　　　　　一般二叉树的顺序表示 156156

第６章树与二叉树第二节二叉树七、二叉树的链式存储结构 1.二叉链表采用数据域加上左、右孩子指针 data lChild
第６章　树与二叉树第二节　二叉树七、二叉树的链式存储结构 1.二叉链表采用数据域加上左、右孩子指针 data lChild rChild lChild data rChild 157157

第６章树与二叉树第二节二叉树七、二叉树的链式存储结构 1.二叉链表(举例) 二叉树（左）及其二叉链表（右） 158158 A B C
第６章　树与二叉树第二节　二叉树七、二叉树的链式存储结构 1.二叉链表(举例) 二叉树（左）及其二叉链表（右） A B C D F E root  A B C D F E root 158158

lChild data parent rChild
第６章　树与二叉树第二节　二叉树七、二叉树的链式存储结构２.三叉链表采用数据域加上左、右孩子指针及双亲指针 parent data lChild rChild lChild data parent rChild 159159

第６章树与二叉树第二节二叉树七、二叉树的链式存储结构２.三叉链表(举例) 二叉树（左）及其三叉链表（右） A B C D F E
第６章　树与二叉树第二节　二叉树七、二叉树的链式存储结构２.三叉链表(举例) 二叉树（左）及其三叉链表（右） A B C D F E root  A B C D F E root 160160

第６章树与二叉树第三节遍历二叉树一、遍历二叉树树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次
第６章　树与二叉树第三节　遍历二叉树一、遍历二叉树树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次一个二叉树由根节点与左子树和右子树组成设访问根结点用D表示，遍历左、右子树用L、R表示Ｄ L R 161161

第６章树与二叉树第三节遍历二叉树一、遍历二叉树如果规定先左子树后右子树，则共有三种组合 1.DLR [先序遍历]
第６章　树与二叉树第三节　遍历二叉树一、遍历二叉树如果规定先左子树后右子树，则共有三种组合 1.DLR [先序遍历] 2.LDR [中序遍历] 3.LRD [后序遍历] Ｄ L R 162162

第６章树与二叉树第三节遍历二叉树二、先序遍历二叉树算法： 1.若二叉树为空，则返回；否则： 2.访问根节点(D)
第６章　树与二叉树第三节　遍历二叉树二、先序遍历二叉树算法： 1.若二叉树为空，则返回；否则： 2.访问根节点(D) 3.先序遍历左子树(L) 4.先序遍历右子树(R) Ｄ L R 163163

第６章树与二叉树第三节遍历二叉树二、先序遍历二叉树算法(举例)：输出结果：ABDEGCF 1.若二叉树为空，则返回；否则：
第６章　树与二叉树第三节　遍历二叉树二、先序遍历二叉树算法(举例)： 1.若二叉树为空，则返回；否则： 2.访问根节点(D) 3.先序遍历左子树(L) 4.先序遍历右子树(R) 输出结果：ABDEGCF A D B F C G E 164164

第６章树与二叉树第三节遍历二叉树二、先序遍历二叉树算法(C语言实现)：
第６章　树与二叉树第三节　遍历二叉树二、先序遍历二叉树算法(C语言实现)： void PreOrderTraverse ( BinTree T ) { if (T) { cout << T->data; PreOrderTraverse ( T->lChild ); PreOrderTraverse ( T->rChild ); } 165165

第６章树与二叉树第三节遍历二叉树三、中序遍历二叉树算法： 1.若二叉树为空，则返回；否则： 2.中序遍历左子树(L)
第６章　树与二叉树第三节　遍历二叉树三、中序遍历二叉树算法： 1.若二叉树为空，则返回；否则： 2.中序遍历左子树(L) 3.访问根节点(D) 4.中序遍历右子树(R) Ｄ L R 166166

第６章树与二叉树第三节遍历二叉树三、中序遍历二叉树算法(举例)：输出结果：DBGEAFC 1.若二叉树为空，则返回；否则：
第６章　树与二叉树第三节　遍历二叉树三、中序遍历二叉树算法(举例)： 1.若二叉树为空，则返回；否则： 2.中序遍历左子树(L) 3.访问根节点(D) 4.中序遍历右子树(R) 输出结果：DBGEAFC A D B F C G E 167167

第６章树与二叉树第三节遍历二叉树三、中序遍历二叉树算法(C语言实现)：
第６章　树与二叉树第三节　遍历二叉树三、中序遍历二叉树算法(C语言实现)： void InOrderTraverse ( BinTree T ) { if (T) { InOrderTraverse ( T->lChild ); cout << T->data; InOrderTraverse ( T->rChild ); } 168168

第６章树与二叉树第三节遍历二叉树四、后序遍历二叉树算法： 1.若二叉树为空，则返回；否则： 2.后序遍历左子树(L)
第６章　树与二叉树第三节　遍历二叉树四、后序遍历二叉树算法： 1.若二叉树为空，则返回；否则： 2.后序遍历左子树(L) 3.后序遍历右子树(R) 4.访问根节点(D) Ｄ L R 169169

第６章树与二叉树第三节遍历二叉树四、后序遍历二叉树算法(举例)：输出结果：DGEBFCA 1.若二叉树为空，则返回；否则：
第６章　树与二叉树第三节　遍历二叉树四、后序遍历二叉树算法(举例)： 1.若二叉树为空，则返回；否则： 2.访问根节点(D) 3.后序遍历左子树(L) 4.后序遍历右子树(R) 输出结果：DGEBFCA A D B F C G E 170170

第６章树与二叉树第三节遍历二叉树四、后序遍历二叉树算法(C语言实现)：
第６章　树与二叉树第三节　遍历二叉树四、后序遍历二叉树算法(C语言实现)： void PostOrderTraverse ( BinTree T ) { if (T) { PostOrderTraverse ( T->lChild ); PostOrderTraverse ( T->rChild ); cout << T->data; } 171171

第６章树与二叉树第四节线索二叉树一、增加新指针最简单的方法是在每个结点中，增加前驱(fwd) 和后继(bkwd)指针
第６章　树与二叉树第四节　线索二叉树一、增加新指针最简单的方法是在每个结点中，增加前驱(fwd) 和后继(bkwd)指针在做二叉树遍历（前、中、后序），将每个结点的前驱和后继信息添入fwd和bkwd域中 fwd lChild data rChild bkwd 172172

第６章树与二叉树第四节线索二叉树二、利用空指针在有n个结点的二叉树中，必定存在n+1个空链域
第６章　树与二叉树第四节　线索二叉树二、利用空指针在有n个结点的二叉树中，必定存在n+1个空链域因为每个结点有两个链域（左、右孩子指针），因此共有2n个链域除根结点外，每个结点都有且仅有一个分支相连，即n-1个链域被使用 173173

第６章树与二叉树第四节线索二叉树二、利用空指针在结点中增加两个标记位（LTag, RTag)
第６章　树与二叉树第四节　线索二叉树二、利用空指针在结点中增加两个标记位（LTag, RTag) LTag=0, lChild域指示结点的左孩子　LTag=1, lChild域指示结点的前驱结点 RTag=0, lChild域指示结点的右孩子　RTag=1, lChild域指示结点的后继结点 LTag lChild data rChild RTag 174174

第６章树与二叉树第五节树与森林一、树的存储结构 1.双亲表示法采用一组连续的存储空间由于每个结点只有一个双亲，只需要一个指针 A
第６章　树与二叉树第五节　树与森林一、树的存储结构 1.双亲表示法采用一组连续的存储空间由于每个结点只有一个双亲，只需要一个指针 A E B G D F C A B C D E F G -1 1 3 175175

第６章树与二叉树第五节树与森林一、树的存储结构 2.孩子表示法可以采用多重链表，即每个结点有多个指针最大缺点是空链域太多
第６章　树与二叉树第五节　树与森林一、树的存储结构 2.孩子表示法可以采用多重链表，即每个结点有多个指针最大缺点是空链域太多　[(d-1)n+1个] data child1 child2 child3 childd A E B G D F C 176176

第６章树与二叉树第五节树与森林一、树的存储结构 2.孩子表示法将每个结点的孩子排列起来，用单链表表示将每个结点排列成一个线性表
第６章　树与二叉树第五节　树与森林一、树的存储结构 2.孩子表示法将每个结点的孩子排列起来，用单链表表示将每个结点排列成一个线性表 Root 1 2 3 4 5 6 A B C D E F G 1 2 3 ^ A E B G D F C 4 5 ^ 6 ^ 177177

第６章树与二叉树第五节树与森林一、树的存储结构 3.孩子兄弟表示法采用二叉链表左边指针指向第一个孩子，右边指针指向兄弟
第６章　树与二叉树第五节　树与森林一、树的存储结构 3.孩子兄弟表示法采用二叉链表左边指针指向第一个孩子，右边指针指向兄弟 data firstChild nextSibling B C D G F E  A A E B G D F C 178178

第６章树与二叉树第五节树与森林二、树与二叉树的对应关系树与二叉树都可以采用二叉链表作存储结构
第６章　树与二叉树第五节　树与森林二、树与二叉树的对应关系树与二叉树都可以采用二叉链表作存储结构任意给定一棵树，可以找到一个唯一的二叉树(没有右子树) A B G D F C E A E B G D F C B C D G F E  A 树对应的二叉树 179179

第６章树与二叉树第五节树与森林三、森林与二叉树的对应关系
第６章　树与二叉树第五节　树与森林三、森林与二叉树的对应关系如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应 A B C E D H I K F G J T T T3 A F H B C D G I J E K 三棵树的森林对应的二叉树 180180

第６章树与二叉树第五节树与森林四、树的遍历对树的遍历主要有两种： 1. 先根（次序）遍历 2. 后根（次序）遍历 A E B G
第６章　树与二叉树第五节　树与森林四、树的遍历对树的遍历主要有两种： 1. 先根（次序）遍历 2. 后根（次序）遍历 A E B G D F C 181181

第６章树与二叉树第五节树与森林四、树的遍历 1. 先根（次序）遍历当树非空时访问根结点依次先根遍历根的各棵子树
第６章　树与二叉树第五节　树与森林四、树的遍历 1. 先根（次序）遍历　当树非空时访问根结点依次先根遍历根的各棵子树　输出结果：ABEFCDG A E B G D F C 182182

第６章树与二叉树第五节树与森林四、树的遍历 2. 后根（次序）遍历当树非空时依次后根遍历根的各棵子树访问根结点
第６章　树与二叉树第五节　树与森林四、树的遍历 2. 后根（次序）遍历　当树非空时依次后根遍历根的各棵子树访问根结点　输出结果：EFBCGDA A E B G D F C 183183

第６章树与二叉树第六节赫夫曼树及其应用一、最优二叉树路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
第６章　树与二叉树第六节　赫夫曼树及其应用一、最优二叉树路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径长度：路径上的分支数目树的路径长度：从树根到　每个结点的路径长度之和右树路径长度为：　2*1 + 3*2 + 1*3 = 11 A D B F C G E 184184

第６章树与二叉树第六节赫夫曼树及其应用一、最优二叉树带权路径长度：从结点到树根之间的路径长度与结点上权的乘积
第６章　树与二叉树第六节　赫夫曼树及其应用一、最优二叉树带权路径长度：从结点到树根之间的路径长度与结点上权的乘积树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和 WPL = 2*5+3*3+2*4=27 A D B F C G E 5 ３４ 185185

第６章树与二叉树第六节赫夫曼树及其应用一、最优二叉树
第６章　树与二叉树第六节　赫夫曼树及其应用一、最优二叉树最优二叉树：假设二叉树有n个叶子，其每个叶子结点带权wi，则带权路径长度WPL最小的二叉树称为最优二叉树赫夫曼(Huffman)树就是一棵最优二叉树 WPL = 1*5+2*3+2*4=19 A D B C E 5 ３４ 186186

第６章树与二叉树第六节赫夫曼树及其应用二、Huffman树(构造) 在Huffman树中，权值最大的结点离根最近
第６章　树与二叉树第六节　赫夫曼树及其应用二、Huffman树(构造) 在Huffman树中，权值最大的结点离根最近权值最小的结点离根最远 A D B C E 5 ３４ 187187

第６章树与二叉树第六节赫夫曼树及其应用二、Huffman树(算法)
第６章　树与二叉树第六节　赫夫曼树及其应用二、Huffman树(算法) 1.根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点 2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和 3.在F中删除这两棵树，同时将新得到的二叉树加入F中 4.重复2, 3，直到F只含一棵树为止 188188

第６章树与二叉树第六节赫夫曼树及其应用二、Huffman树(举例) 189189 F : {7} {5} {2} {4}
第６章　树与二叉树第六节　赫夫曼树及其应用二、Huffman树(举例) F : {7} {5} {2} {4} F : {7} {5} {6} F : {7} {11} 7 5 2 4 初始合并{2} {4} 6 F : {18} 11 合并{5} {6} 合并{7} {11} 18 189189

第６章树与二叉树第六节赫夫曼树及其应用三、Huffman编码设给出一段报文：GOOD_GOOD_GOODGODG
第６章　树与二叉树第六节　赫夫曼树及其应用三、Huffman编码设给出一段报文：GOOD_GOOD_GOODGODG 字符集合是 { O, G, _, D }，各个字符出现的频度(次数)是 W＝{ 7, 5, 2, 4 }。若给每个字符以等长编码 O: 00 G: _: D: 11 则总编码长度为 ( ) * 2 = 36. 190190

第６章树与二叉树第六节赫夫曼树及其应用三、Huffman编码若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。
第６章　树与二叉树第六节　赫夫曼树及其应用三、Huffman编码若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为{ 2/18, 7/18, 4/18, 5/18 },化整为 { 2, 7, 4, 5 } 可构成右图所示Huffman树 5 2 7 4 191191

第６章树与二叉树第六节赫夫曼树及其应用三、Huffman编码令左孩子分支为编码‘0’，右孩子分支为编码‘1’ 得到不等长编码：
第６章　树与二叉树第六节　赫夫曼树及其应用三、Huffman编码令左孩子分支为编码‘0’，右孩子分支为编码‘1’ 得到不等长编码：　O:0 G:10 _:110 D:111 则总编码长度为 7*1+5*2+4*3+2*3 = 35 Huffman是一种前缀编码，解码时不会混淆 5 2 7 4 1 192192

数据结构第七章图深圳大学计算机系蔡茂国

第７章图第一节图的定义与术语一、图的定义(Graph) 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：
第７章　图第一节　图的定义与术语一、图的定义(Graph) 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E ) 其中V = {x | x数据对象}是顶点的有穷非空集合 E是顶点之间关系的有穷集合，包括 E1 = {(x, y) | x, y  V } 边的集合或 E2 = {<x, y> | x, y  V } 弧的集合 194194

第７章图第一节图的定义与术语二、无向图(Undigraph) 用(x,y)表示两个顶点x,y之间的一条边(edge)
第７章　图第一节　图的定义与术语二、无向图(Undigraph) 用(x,y)表示两个顶点x,y之间的一条边(edge) N={V,E}，V={0,1,2,3,4,5}，E={(0,1), (0,4), (0,5), (1,2), (1,3), (1,5), (2,3), (3,4), (3,5), (4,5)} 1 3 2 5 4 195195

第７章图第一节图的定义与术语二、无向图(完全图) 如果无向图有n(n-1)/2条边，则称为无向完全图 1 3 2 5 4
第７章　图第一节　图的定义与术语二、无向图(完全图) 如果无向图有n(n-1)/2条边，则称为无向完全图 1 3 2 5 4 196196

第７章图第一节图的定义与术语二、无向图邻接点：如果(x,y)E,称x,y互为邻接点，即x,y相邻接
第７章　图第一节　图的定义与术语二、无向图邻接点：如果(x,y)E,称x,y互为邻接点，即x,y相邻接依附：边(x,y)依附于顶点x,y 相关联：边(x,y)与x,y相关联顶点的度：和顶点相关联的边的数目，记为TD(x) 1 3 2 5 4 197197

第７章图第一节图的定义与术语三、有向图(Digraph)
第７章　图第一节　图的定义与术语三、有向图(Digraph) 用<x,y>表示从x到y的一条弧(Arc)，且称x为弧尾，y为弧头， N={V,E}，V={0,1,2,3,4}，E={<0,1>，<0,3>，<0,4>，<1,2>，<2,4>，<3,2> } 1 3 2 4 198198

第７章　图第一节　图的定义与术语三、有向图(完全图) 如果有向图有n(n-1)条边，则称为有向完全图 1 2 199199

第７章图第一节图的定义与术语三、有向图邻接：如果<x,y>E,称x邻接到y,或y邻接自x
第７章　图第一节　图的定义与术语三、有向图邻接：如果<x,y>E,称x邻接到y,或y邻接自x 相关联：弧<x,y>与x,y相关联入度：以顶点为头的弧的数目，记为ID(x) 出度：以顶点为尾的弧的数目，记为OD(x) 度：TD(x)=ID(x)+OD(x) 1 3 2 4 200200

第７章图第一节图的定义与术语四、路径(Path) 路径：是一个从顶点x到y的顶点序列(x, vi1, vi2,…, vin, y)
第７章　图第一节　图的定义与术语四、路径(Path) 路径：是一个从顶点x到y的顶点序列(x, vi1, vi2,…, vin, y) 其中，(x,vi1),(vij-1,vij),(vin,y)皆属于E 1 3 2 5 4 1 3 2 4 1到3有路径(1,0,4,3) 1到4有路径(1,2,4) 201201

第７章　图第一节　图的定义与术语五、回路回路或环：路径的开始顶点与最后一个顶点相同，即路径中(x, vi1, vi2,…, vin, y)，x=y 简单路径：路径的顶点序列中，顶点不重复出现 1 3 2 5 4 1到3是简单路径(1,0,4,3) 1到1构成环(1,0,4,3,1) 202202

第７章图第一节图的定义与术语六、连通连通：如果顶点x到y有路径，称x和y是连通的连通图：图中所有顶点都连通 1 3 2 4 1
第７章　图第一节　图的定义与术语六、连通连通：如果顶点x到y有路径，称x和y是连通的连通图：图中所有顶点都连通 1 3 2 4 1 3 2 5 4 连通图非连通图 203203

第７章　图第一节　图的定义与术语七、子图设有两个图 G＝(V, E) 和 G’＝(V’, E’)。若 V’ V 且 E’E, 称图G’是图G的子图 1 3 2 5 4 3 2 4 204204

第７章　图第一节　图的定义与术语八、生成树一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边 1 3 2 5 4 1 3 2 5 4 205205

一、邻接矩阵(Adjacency Matrix)
第７章　图第二节　图的存储结构一、邻接矩阵(Adjacency Matrix) 邻接矩阵：记录图中各顶点之间关系的二维数组。对于不带权的图，以1表示两顶点存在边(或弧)(相邻接)，以0表示两顶点不邻接，即 1 如果(i,j)E 或 <i,j>E A[i][j] = 0 其它 206206

第７章图第二节图的存储结构一、邻接矩阵无向图的邻接矩阵为：有向图的邻接矩阵为： 207207 0 1 0 0 1 1
第７章　图第二节　图的存储结构一、邻接矩阵无向图的邻接矩阵为：　有向图的邻接矩阵为： 1 3 2 4 1 3 2 5 4 207207

第７章图第二节图的存储结构一、邻接矩阵(性质) 无向图的邻接矩阵是对称的其第i行1的个数或第i列1的个数，等于顶点i的度TD(i)
第７章　图第二节　图的存储结构一、邻接矩阵(性质) 无向图的邻接矩阵是对称的其第i行1的个数或第i列1的个数，等于顶点i的度TD(i) 有向图的邻接矩阵可能是不对称的其第i行1的个数等于顶点i的出度OD(i)，第j列1的个数等于顶点j的入度ID(j) 208208

第７章图第二节图的存储结构一、邻接矩阵(网络)
第７章　图第二节　图的存储结构一、邻接矩阵(网络) 在网络中，两个顶点如果不邻接，则被视为距离为无穷大；如果邻接，则两个顶点之间存在一个距离值(即权值) wi,j 如果(i,j)E 或 <i,j>E A[i][j] = ∞ 其它 209209

第７章图第二节图的存储结构一、邻接矩阵(网络)
第７章　图第二节　图的存储结构一、邻接矩阵(网络) 有向网N={V,E}，V={0,1,2,3,4}，E={<0,1,5>，<0,3,7>，<0,4,15>，<1,2,5>，<2,4,1>，<3,2,2> }，E中每个元组的第三个元素表示权。 1、画出该网, 2、写出该网的邻接矩阵。 ∞ 5 ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 3 2 4 5 15 7 210210

二、邻接表(Adjacency List)
第７章　图第二节　图的存储结构二、邻接表(Adjacency List) 邻接表是图的一种链式存储结构在邻接表中，每个顶点设置一个单链表，其每个结点都是依附于该顶点的边（或以该顶点为尾的弧） 211211

第７章图第二节图的存储结构二、邻接表(结点结构) 边(弧)的结点结构 adjvex; // 该边(弧)所指向的顶点的位置
第７章　图第二节　图的存储结构二、邻接表(结点结构) 边(弧)的结点结构 adjvex; // 该边(弧)所指向的顶点的位置 nextarc;// 指向下一条边(弧)指针 info; // 该边(弧)相关信息的指针或权值顶点的结点结构 data; // 顶点信息 firstarc;//指向第一条依附该顶点的边(弧) adjvex nextarc info data firstarc 212212

第７章　图第二节　图的存储结构二、邻接表(无向图) 1 2 3 4 5 1 4 5 ^ 2 3 1 3 2 5 4 213213

第７章　图第二节　图的存储结构二、邻接表(有向图) 1 2 3 4 ^ 1 3 4 ^ 2 1 3 2 4 214214

第７章图第二节图的存储结构二、邻接表(网络) 1 2 3 4 1 5 3 7 4 15 ^ 2 1 3 2 4 5 15 7
第７章　图第二节　图的存储结构二、邻接表(网络) 1 2 3 4 1 5 3 7 4 15 ^ 2 1 3 2 4 5 15 7 215215

第７章图第二节图的存储结构二、邻接表(性质)
第７章　图第二节　图的存储结构二、邻接表(性质) 对于有向图的邻接表，其第i个链表中结点的个数只是该顶点的出度；如果要计算入度，必须遍历整个邻接表[也可以建立一个逆邻接表] 要判定两个顶点i和j是否有边（或弧），必须搜索整个第i个和第j个链表，不及邻接矩阵方便 216216

第７章图第二节图的存储结构二、邻接表(有向图的逆邻接表) 逆邻接表中，弧的箭头向内(入弧) ^ 1 2 3 4 3 ^ 2 1 1
第７章　图第二节　图的存储结构二、邻接表(有向图的逆邻接表) 逆邻接表中，弧的箭头向内(入弧) ^ 1 2 3 4 3 ^ 2 1 1 3 2 4 217217

三、十字链表(Orthogonal List)
第７章　图第二节　图的存储结构三、十字链表(Orthogonal List) 十字链表是有向图的另一种存储结构十字链表是将有向图的邻接表和逆邻接表结合起来的一种存储结构 218218

第７章图第二节图的存储结构三、十字链表(结点结构) 弧的结点结构 tailvex;// 弧尾顶点的位置
第７章　图第二节　图的存储结构三、十字链表(结点结构) 弧的结点结构 tailvex;// 弧尾顶点的位置 headvex;// 弧头顶点的位置 tlink; // 指向弧尾相同的下一条弧 hlink; // 指向弧头相同的下一条弧 info; // 该弧相关信息的指针或权值 tailvex headvex hlink tlink info 219219

第７章图第二节图的存储结构三、十字链表(结点结构) 顶点的结点结构 data; // 与顶点相关的信息
第７章　图第二节　图的存储结构三、十字链表(结点结构) 顶点的结点结构 data; // 与顶点相关的信息 firstin; // 指向以顶点为弧头的第一个弧结点 firstout;// 指向以顶点为弧尾的第一个弧结点 data firstin firstout 220220

第７章图第二节图的存储结构三、十字链表(举例) ^ 1 2 3 4 1 3 2 4 221221 ^ 1 ^ 3 ^ 4 1 2 ^
第７章　图第二节　图的存储结构三、十字链表(举例) ^ 1 2 3 4 ^ 1 ^ 3 ^ 4 1 2 ^ 1 3 2 4 2 4 ^ 3 ^ 2 221221

四、邻接多重表(Adjacency Multilist)
第７章　图第二节　图的存储结构四、邻接多重表(Adjacency Multilist) 邻接多重表是无向图的另一种存储结构在无向图中，一条边要用2个结点表示(分别从2个顶点的角度看) 在邻接多重表中，一条边只用一个结点表示将所有具有某顶点的结点，全部用链连结起来，链所在的域为该顶点对应的指针域 222222

第７章图第二节图的存储结构四、邻接多重表(结点结构) 边的结点结构 mark; // 标记域，如指示该边是否被搜索过
第７章　图第二节　图的存储结构四、邻接多重表(结点结构) 边的结点结构 mark; // 标记域，如指示该边是否被搜索过 ivex,jvex;// 该边所依附的两个顶点的位置 ilink;// 指向下一条依附于ivex的边 jlink;// 指向下一条依附于jvex的边 info; // 该边相关信息的指针或权值 ivex mark ilink jvex jlink info 223223

第７章图第二节图的存储结构四、邻接多重表(举例) 1 2 3 4 5 1 3 2 5 4 224224 1 1 2 1 3 ^ 1
第７章　图第二节　图的存储结构四、邻接多重表(举例) 1 2 3 4 5 1 1 2 1 3 ^ 1 ^ 5 1 3 2 5 4 3 2 ^ 3 4 3 5 4 5 ^ 5 4 ^ 224224

第７章图第三节图的遍历一、图的遍历从图的某一顶点开始，访遍图中其余顶点，且使每一个顶点仅被访问一次图的遍历主要应用于无向图
第７章　图第三节　图的遍历一、图的遍历从图的某一顶点开始，访遍图中其余顶点，且使每一个顶点仅被访问一次图的遍历主要应用于无向图 225225

第７章图第三节图的遍历二、深度优先搜索(DFS) 图的深度优先搜索是树的先根遍历的推广
第７章　图第三节　图的遍历二、深度优先搜索(DFS) 图的深度优先搜索是树的先根遍历的推广图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ] 226226

第７章图第三节图的遍历二、深度优先搜索(DFS算法) 所有顶点访问标志visited[]设置为FALSE
第７章　图第三节　图的遍历二、深度优先搜索(DFS算法) 所有顶点访问标志visited[]设置为FALSE 从某顶点v0开始，设v=v0 1.如果visited[v]=FALSE，则访问该顶点，且设visited[v]=TRUE 2.如果找到当前顶点的一个新的相邻顶点w,设v=w,重复1 3.否则(说明当前顶点的所有相邻顶点都已被访问过，或者当前顶点没有相邻顶点)，如果当前顶点是v0，退出；否则返回上一级顶点，重复2

第７章图第三节图的遍历二、深度优先搜索(举例) 采用以下链表存储结构时，DFS次序为0,1,2,3,4,5 F 1 2 3 4 5
第７章　图第三节　图的遍历二、深度优先搜索(举例) 采用以下链表存储结构时，DFS次序为0,1,2,3,4,5 F 1 2 3 4 5 1 4 5 ^ 2 3 1 3 2 5 4 228228 visit

第７章图第三节图的遍历二、深度优先搜索(举例) DFS次序为V1,V2,V4,V8,V5,V3,V6,V7 229229 V1 V3
第７章　图第三节　图的遍历二、深度优先搜索(举例) DFS次序为V1,V2,V4,V8,V5,V3,V6,V7 V1 V3 V2 V5 V4 V6 V7 V8 229229

第７章图第三节图的遍历三、广度优先搜索(BFS) 广度优先搜索(BFS)是一种分层搜索方法
第７章　图第三节　图的遍历三、广度优先搜索(BFS) 广度优先搜索(BFS)是一种分层搜索方法 BFS每向前走一步可能访问一批顶点, 不存在往回退的情况 BFS不是一个递归的过程。 230230

第７章图第三节图的遍历三、广度优先搜索(BFS算法) 所有顶点访问标志visited[]设置为FALSE
第７章　图第三节　图的遍历三、广度优先搜索(BFS算法) 所有顶点访问标志visited[]设置为FALSE 从某顶点v0开始，访问v0，visited[v0]=TRUE，将v0插入队列Q 1.如果队列Q不空，则从队列Q头上取出一个顶点v,否则结束 2.依次找到顶点v的所有相邻顶点v’，如果visited[v’]=FALSE，访问该顶点v’，visited[v’]=TRUE，将v’插入队列Q 3.重复1,2 231231

第７章图第三节图的遍历三、广度优先搜索(举例) BFS为0,1,4,5,2,3 BFS为v1,v2,v3,v4,
第７章　图第三节　图的遍历三、广度优先搜索(举例) V1 V3 V2 V5 V4 V6 V7 V8 1 3 2 5 4 BFS为0,1,4,5,2, BFS为v1,v2,v3,v4, v5,v6,v7,v8

第７章图第四节图的连通性问题一、无向图的连通性如果无向图中，存在不连通的顶点，则该图称为非连通图 A C D E B F O G
第７章　图第四节　图的连通性问题一、无向图的连通性如果无向图中，存在不连通的顶点，则该图称为非连通图 A C D E B F O G N M L K 233233

第７章图第四节图的连通性问题二、无向图的连通分量非连通图的极大连通子图叫做连通分量
第７章　图第四节　图的连通性问题二、无向图的连通分量非连通图的极大连通子图叫做连通分量若从无向图的每一个连通分量中的一个顶点出发进行DFS或BFS遍历，可求得无向图的所有连通分量的生成树(DFS或BFS生成树) 所有连通分量的生成树组成了非连通图的生成森林 234234

第７章图第四节图的连通性问题二、无向图的生成树由DFS遍历，求得连通分量称为DFS生成树
第７章　图第四节　图的连通性问题二、无向图的生成树由DFS遍历，求得连通分量称为DFS生成树由BFS遍历，求得连通分量称为BFS生成树 A C D E B F O G N M L K BFS生成树 DFS生成树 235235

第７章图第四节图的连通性问题三、最小生成树如果无向图中，边上有权值，则称该无向图为无向网
第７章　图第四节　图的连通性问题三、最小生成树如果无向图中，边上有权值，则称该无向图为无向网如果无向网中的每个顶点都相通，称为连通网最小生成树(Minimum Cost Spanning Tree)是代价最小的连通网的生成树，即该生成树上的边的权值和最小 236236

第７章图第四节图的连通性问题三、最小生成树(准则) 必须使用且仅使用连通网中的n-1条边来联结网络中的n个顶点；
第７章　图第四节　图的连通性问题三、最小生成树(准则) 必须使用且仅使用连通网中的n-1条边来联结网络中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。 237237

四、普里姆(Prim)算法生成最小生成树
第７章　图第四节　图的连通性问题四、普里姆(Prim)算法生成最小生成树假设N=(V,E)是连通网 TE是N上最小生成树中边的集合 1.U={u0}，(u0V), TE={} 2.在所有uU,vV-U的边(u,v)E中找一条代价最小的边(u,v0)并入集合TE，同时v0并入U 3.重复2，直到U=V 238238

第７章图第四节图的连通性问题四、普里姆(Prim)算法举例 239239 28 5 4 6 1 3 2 10 25 14 24 22
第７章　图第四节　图的连通性问题四、普里姆(Prim)算法举例 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 10 5 4 6 1 3 2 5 4 6 1 3 2 10 25 原图　　　　 (a) 　　　　 (b) 25 5 4 6 1 3 2 10 22 25 5 4 6 1 3 2 10 22 12 5 4 6 1 2 10 25 14 22 16 12 3 239239 (c) 　　　　　 (d) 　　　　 (e) (f)

五、克鲁斯卡尔(Kruskal)算法生成最小生成树
第７章　图第四节　图的连通性问题五、克鲁斯卡尔(Kruskal)算法生成最小生成树假设N=(V,E)是连通网 1.非连通图T={V,{}}，图中每个顶点自成一个连通分量 2.在E中找一条代价最小，且其两个顶点分别依附不同的连通分量的边，将其加入T中 3.重复2，直到T中所有顶点都在同一连通分量上 240240

五、克鲁斯卡尔(Kruskal)算法举例
第７章　图第四节　图的连通性问题五、克鲁斯卡尔(Kruskal)算法举例 28 5 4 6 1 3 2 10 25 14 24 22 16 18 12 5 4 6 1 3 2 10 5 4 6 1 3 2 10 12 原图　　　　 (a) 　　　　 (b) 5 4 6 1 3 2 10 14 12 5 4 6 1 3 2 10 14 16 12 5 4 6 1 3 2 10 25 14 22 16 12 (c) 　　　　　 (d) 　　　　 (e) (f) 241241

第７章图第五节最短路径一、最短路径最短路径是求从图（或网）中某一顶点，到其余各顶点的最短路径最短路径与最小生成树主要有三点不同：
第７章　图第五节　最短路径一、最短路径最短路径是求从图（或网）中某一顶点，到其余各顶点的最短路径最短路径与最小生成树主要有三点不同： 1.最短路径的操作对象主要是有向图(网)，而最小生成树的操作对象是无向图 2.最短路径有一个始点，最小生成树没有 3.最短路径关心的是始点到每个顶点的路径最短，而最小生成树关心的是整个树的代价最小 242242

第７章图第五节最短路径二、Dijkstra算法最短路径可以采用迪杰斯特拉(Dijkstra)算法求解
第７章　图第五节　最短路径二、Dijkstra算法最短路径可以采用迪杰斯特拉(Dijkstra)算法求解 Dijkstra算法采用按路径长度递增的次序产生最短路径 243243

第７章图第五节最短路径二、Dijkstra算法在Dijkstra算法中，引进了一个辅助向量D
第７章　图第五节　最短路径二、Dijkstra算法在Dijkstra算法中，引进了一个辅助向量D 每个分量D[i]表示当前所找到的从始点到每个终点vi的最短路径长度 D[i]初值为始点v0到各终点vi的直接距离，即若从始点到某终点有(出)弧，则为弧上的权值，否则为∞ 244244

第７章图第五节最短路径二、Dijkstra算法对于下图，如果0是始点v0，则D[i]的初值为：D[i]={5,∞,7,15}
第７章　图第五节　最短路径二、Dijkstra算法对于下图，如果0是始点v0，则D[i]的初值为：D[i]={5,∞,7,15} 显然， D[j]=Min{D[i] | viV} 是从始点出发的长度最短的一条最短路径 1 3 2 4 5 15 7

第７章图第五节最短路径二、Dijkstra算法设S为已求得的最短路径的终点的集合下一条最短路径(设其终点为vi)为以下之一：
第７章　图第五节　最短路径二、Dijkstra算法设S为已求得的最短路径的终点的集合下一条最短路径(设其终点为vi)为以下之一： 1.中间只经过S中的顶点而后到达顶点vi的路径 2.弧<v0,vi> D[j’]=Min{D[i] | viV-S} D[k]=<v0,vi> or D[i]=D[j]+<vj,vi> 1 3 2 4 5 15 7

第７章图第五节最短路径二、Dijkstra算法 1. 初始化： S ← {v0 };
第７章　图第五节　最短路径二、Dijkstra算法 1. 初始化： S ← {v0 }; D[i] ← arc[0][i], i = 1, 2, …, n-1; 2. 求出最短路径的长度： D[j] ← min { D[i] }, i  V-S ; S←S U {j }; 3. 修改： D[i] ← min{D[i], D[j] + arc[j][i] }, iV-S 4. 判断：若 S = V, 则算法结束，否则转 2。 247247

第７章图第五节最短路径二、Dijkstra算法顶点 D 1 5 2 ∞ 10 9 3 7 4 15 终点j S {0,1}
第７章　图第五节　最短路径二、Dijkstra算法顶点 D 1 5 2 ∞ 10 9 3 7 4 15 终点j S {0,1} {0,1,3} {0,1,3,2} {0,1,3,2,4} 1 3 2 4 5 15 7

第７章图第六节有向无环图及其应用一、有向无环图(DAG)
第７章　图第六节　有向无环图及其应用一、有向无环图(DAG) 有向无环图(DAG:Directed Acycline Graph)是图中无环的有向图 1 3 2 4 1 3 2 4 DAG 非DAG 249249

第７章图第六节有向无环图及其应用一、有向无环图(DAG) 有向图中，可以用深度优先搜索(DFS)，找出是否存在环
第７章　图第六节　有向无环图及其应用一、有向无环图(DAG) 有向图中，可以用深度优先搜索(DFS)，找出是否存在环从某个顶点v出发，进行DFS，如果存在一条从顶点u到v的回边，则有向图中存在环 DFS: 0,1,2,4,3 1 3 2 4 非DAG

第７章图第六节有向无环图及其应用二、拓扑排序 1.偏序若集合X上的关系R是： ⑴.自反的：x R x
第７章　图第六节　有向无环图及其应用二、拓扑排序 1.偏序若集合X上的关系R是： ⑴.自反的：x R x ⑵.反对称的：x R y => y R x ⑶.传递的：xRy & yRz => xRz 则称R是集合X上的偏序关系 1 3 2 4

第７章图第六节有向无环图及其应用二、拓扑排序 2.全序
第７章　图第六节　有向无环图及其应用二、拓扑排序 2.全序设关系R是集合X上的偏序，如果对每个x,yX，必有xRy或者yRx，则称R是X上的全序关系偏序指集合中仅有部分成员之间可比较全序指集合中全体成员之间均可比较 252252

第７章图第六节有向无环图及其应用二、拓扑排序 3.拓扑有序右图是一个偏序关系，因为1,3没有先后关系
第７章　图第六节　有向无环图及其应用二、拓扑排序 3.拓扑有序右图是一个偏序关系，因为1,3没有先后关系如果人为地增加1,3先后关系，　如1先于3，则右图变为全序，称为拓扑有序 1 3 2 4

第７章图第六节有向无环图及其应用二、拓扑排序 4.拓扑排序由偏序定义得到的拓扑有序的操作称拓扑排序算法：
第７章　图第六节　有向无环图及其应用二、拓扑排序 4.拓扑排序由偏序定义得到的拓扑有序的操作称拓扑排序算法： ⑴.在有向图中选一个没有前驱的顶点且输出之 ⑵.从图中删除该顶点和所有以它为尾的弧　重复⑴⑵两步，直到所有顶点输出为止 254254

第７章图第六节有向无环图及其应用二、拓扑排序(举例) 1 3 2 4 1 3 2 4 3 2 4 原图输出0之后输出0,1之后
第７章　图第六节　有向无环图及其应用二、拓扑排序(举例) 1 3 2 4 1 3 2 4 3 2 4 原图输出0之后输出0,1之后 2 4 4 最后输出拓扑排序结果：0,1,3,2,4 输出0,1,3之后输出0,1,3,2之后

第７章图第六节有向无环图及其应用三、AOV-网
第７章　图第六节　有向无环图及其应用三、AOV-网如果用有向图的顶点表示活动，用弧表示活动间的优先关系，则称该有向图为顶点表示活动的网AOV(Activity On Vertex Network) AOV一定是DAG，即图中不存在环，因为存在环意味着某项活动应以自己为先决条件 AOV的应用包括流程图等 256256

第７章图第六节有向无环图及其应用三、AOV-网(举例) 257257 拓扑排序结果为
第７章　图第六节　有向无环图及其应用三、AOV-网(举例) 课程代号课程名称先修课程　C 高等数学　C 程序设计基础　C 离散数学 C1, C2 　C 数据结构 C3, C2 　C 高级语言程序设计 C2 　C 编译方法 C5, C4 　C 操作系统 C4, C9 　C 普通物理 C1 　C9 　计算机原理 C8 拓扑排序结果为 C1 , C2 , C3 , C4 , C5 , C6, C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 C8 C3 C5 C4 C9 C6 C7 C1 C2 257257

第７章图第六节有向无环图及其应用四、AOE-网
第７章　图第六节　有向无环图及其应用四、AOE-网如果用有向图的顶点表示事件，用弧表示活动，则称该有向图为边表示活动的网AOE(Activity On Edge) AOE同样是DAG AOE包括估算工程的完成时间 1 3 2 4 a1=5 a2=5 a5=15 a6=1 a3=7 a4=2

第７章图第六节有向无环图及其应用五、关键路径求工程的完成时间是AOE的一个应用在工程问题中，需要研究的问题有：
第７章　图第六节　有向无环图及其应用五、关键路径求工程的完成时间是AOE的一个应用在工程问题中，需要研究的问题有： ⑴.完成整个工程至少需要多少时间？ ⑵.哪些活动是影响工程进度的关键？ 259259

第７章图第六节有向无环图及其应用五、关键路径 1.关键路径
第７章　图第六节　有向无环图及其应用五、关键路径 1.关键路径工程问题的AOE网中，从工程开始(顶点)到工程结束(顶点)之间路径长度最长的路径叫关键路径提前完成关键路径上的活动，工程进度会加快提前完成非关键路径上的活动，对工程无帮助 260260

第７章图第六节有向无环图及其应用五、关键路径 2.关键活动关键路径上的所有活动称为关键活动
第７章　图第六节　有向无环图及其应用五、关键路径 2.关键活动关键路径上的所有活动称为关键活动找到工程AOE中的所有关键活动，即找到了关键路径 261261

第７章图第六节有向无环图及其应用五、关键路径 3.关键活动有关的量 e(i)：活动ai最早开始时间 l(i)：活动ai最迟开始时间
第７章　图第六节　有向无环图及其应用五、关键路径 3.关键活动有关的量 e(i)：活动ai最早开始时间 l(i)：活动ai最迟开始时间 l(i)-e(i)：活动ai开始时间余量如果l(i)=e(i)，则称活动ai为关键活动 1 3 2 4 a1=5 a2=5 a5=15 a6=1 a3=7 a4=2 262262

第７章图第六节有向无环图及其应用五、关键路径 3.关键活动有关的量 ve(j)：事件vj最早开始时间
第７章　图第六节　有向无环图及其应用五、关键路径 3.关键活动有关的量 ve(j)：事件vj最早开始时间 vl(j)：事件vj最迟开始时间 e(i)=ve(j) l(j)=vl(k)-dut(<j,k>) 　dut(<j,k>)为活动ai的持续时间 1 3 2 4 a1=5 a2=5 a5=15 a6=1 a3=7 a4=2 263263

第７章图第六节有向无环图及其应用五、关键路径 3.关键活动有关的量从ve(0)=0开始向前递推
第７章　图第六节　有向无环图及其应用五、关键路径 3.关键活动有关的量从ve(0)=0开始向前递推 ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>T，T是所有以第j个顶点为头的弧的集合从vl(n-1)=ve(n-1)起向后递推 vl(i)=Min{vl(j)-dut(<i,j>)} <i,j>S，S是所有以第i个顶点为尾的弧的集合　 1 3 2 4 a1=5 a2=5 a5=15 a6=1 a3=7 a4=2 264264

第７章图第六节有向无环图及其应用五、关键路径 4.求关键活动算法从始点v0出发，令ve[0]=0，按拓扑有序求ve[j]
第７章　图第六节　有向无环图及其应用五、关键路径 4.求关键活动算法从始点v0出发，令ve[0]=0，按拓扑有序求ve[j] 从终点vn-1出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求vl[i] 根据各顶点的ve和vl值，求每条弧(活动)ai的最早开始时间e[ai]和最迟开始时间l[ai] 如果e[ai]=l[ai]，则ai为关键活动 265265

第７章图第六节有向无环图及其应用五、关键路径(举例) 活动 e l l-e a1 4 a2 5 9 a3 a4 7 12 a5 a6
第７章　图第六节　有向无环图及其应用五、关键路径(举例) ve(j)=Max{ve(i)+dut(<i,j>)} vl(i)=Min{vl(j)-dut(<i,j>)} e(i)=ve(j) l(j)=vl(k)-dut(<j,k>) 拓扑有序　0,1,3,2,4 活动 e l l-e a1 4 a2 5 9 a3 a4 7 12 a5 a6 10 14 顶点 ve vl 1 5 9 2 10 14 3 7 12 4 15 1 3 2 4 a1=5 a2=5 a5=15 a6=1 a3=7 a4=2

数据结构第九章查找深圳大学计算机系蔡茂国

第９章查找第一节查找的概念一、查找表(Search Table) 查找表是由同一类型的数据元素(或记录)构成的集合对查找表的操作:
第９章　查找第一节　查找的概念一、查找表(Search Table) 查找表是由同一类型的数据元素(或记录)构成的集合对查找表的操作: 1.查询某个“特定的”数据元素是否在查找表中； 2.检索某个“特定的”数据元素的各种属性； 3.在查找表中插入一个数据元素； 4.从查找表中删去某个数据元素 268268

第９章查找第一节查找的概念一、查找表(分类) 静态查找表仅作查询和检索操作的查找表。动态查找表
第９章　查找第一节　查找的概念一、查找表(分类) 静态查找表　仅作查询和检索操作的查找表。动态查找表　在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素 269269

第９章查找第一节查找的概念二、关键字(Key) 关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）
第９章　查找第一节　查找的概念二、关键字(Key) 关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）主关键字：可以识别唯一的一个记录的关键字次关键字：能识别若干记录的关键字 270270

第９章查找第一节查找的概念三、查找(Searching)
第９章　查找第一节　查找的概念三、查找(Searching) 查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。查找成功：在查找表中查找到指定的记录查找不成功：在查找表中没有找到指定记录 271271

第９章　查找第一节　查找的概念四、衡量查找算法的标准时间复杂度空间复杂度平均查找长度ASL 272272

第９章查找第一节查找的概念五、平均查找长度(ASL) 平均查找长度定义为确定记录在表中的位置所进行的和关键字比较的次数的平均值 n
第９章　查找第一节　查找的概念五、平均查找长度(ASL) 平均查找长度定义为确定记录在表中的位置所进行的和关键字比较的次数的平均值 n ASL = ∑ PiCi i=1 n为查找表的长度，即表中所含元素的个数 Pi为查找第i个元素的概率(∑Pi=1) Ci是查找第i个元素时同给定值K比较的次数 273273

第９章查找第二节静态查找表一、顺序查找顺序查找算法是顺序表的查找方法在顺序查找算法中，以顺序表或线性链表表示静态查找表
第９章　查找第二节　静态查找表一、顺序查找顺序查找算法是顺序表的查找方法在顺序查找算法中，以顺序表或线性链表表示静态查找表 274274

第９章查找第二节静态查找表一、顺序查找(算法) 顺序查找算法： 1.从表中最后一个记录开始 2.逐个进行记录的关键字和给定值的比较
第９章　查找第二节　静态查找表一、顺序查找(算法) 顺序查找算法： 1.从表中最后一个记录开始 2.逐个进行记录的关键字和给定值的比较 3.若某个记录比较相等，则查找成功 4.若直到第1个记录都比较不等，则查找不成功 275275

第９章查找第二节静态查找表一、顺序查找(算法实现)
第９章　查找第二节　静态查找表一、顺序查找(算法实现) int Search_Seq(SSTable ST, KeyType key) { // 若查找成功，返回位置 ST.elem[0].key = key; // “哨兵”， for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时,i=0 } // Search_Seq 设置“哨兵”的目的是省略对下标越界的检查，提高算法执行速度

第９章查找第二节静态查找表一、顺序查找(举例) 找64 0 1 2 3 4 5 6 7 8 9 10 11 64 5 13 19
第９章　查找第二节　静态查找表一、顺序查找(举例) 找64 64 5 13 19 21 37 56 75 80 88 92 i=7 i=8 i=9 i=10 i=11 监视哨比较次数=5 比较次数：查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1

第９章查找第二节静态查找表一、顺序查找(算法性能分析) 对顺序表而言，Ci=n-i+1 在等概率查找的情况下，Pi=1/n
第９章　查找第二节　静态查找表一、顺序查找(算法性能分析) 对顺序表而言，Ci=n-i+1 在等概率查找的情况下，Pi=1/n ASL=n*P1 +(n-1)P2 +…+ 2Pn-1+ Pn = (n+1)/2 278278

第９章查找第二节静态查找表一、顺序查找(不等概率) 如果被查找的记录概率不等时，取 Pn≥Pn-1≥···≥P2≥P1
第９章　查找第二节　静态查找表一、顺序查找(不等概率) 如果被查找的记录概率不等时，取 Pn≥Pn-1≥···≥P2≥P1 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上 279279

第９章查找第二节静态查找表一、顺序查找(特点) 优点： 1.简单 2.适应面广(对表的结构无任何要求) 缺点： 1.平均查找长度较大
第９章　查找第二节　静态查找表一、顺序查找(特点) 优点： 1.简单 2.适应面广(对表的结构无任何要求) 缺点： 1.平均查找长度较大 2.特别是当n很大时，查找效率很低 280280

第９章查找第二节静态查找表二、折半查找折半查找算法是有序表的查找方法
第９章　查找第二节　静态查找表二、折半查找折半查找算法是有序表的查找方法在折半查找算法中，静态查找表按关键字大小的次序，有序地存放在顺序表中折半查找的原理是： 1.先确定待查记录所在的范围(前部分或后部分) 2.逐步缩小(一半)范围直到找(不)到该记录为止 281281

第９章查找第二节静态查找表二、折半查找(算法) 1.n个对象从小到大存放在有序顺序表ST中，k为给定值
第９章　查找第二节　静态查找表二、折半查找(算法) 1.n个对象从小到大存放在有序顺序表ST中，k为给定值 2.设low、high指向待查元素所在区间的下界、上界，即low=1, high=n 3.设mid指向待区间的中点，即mid=(low+high)/2 4.让k与mid指向的记录比较若k=ST[mid].key，查找成功若k<ST[mid].key，则high=mid-1 [上半区间] 若k>ST[mid].key，则low=mid+1 [下半区间] 5.重复3,4操作，直至low>high时，查找失败。 282282

第９章查找第二节静态查找表二、折半查找(举例－成功) 283283 找64 1 2 3 4 5 6 7 8 9 10 11 5 13
第９章　查找第二节　静态查找表二、折半查找(举例－成功) 找64 5 13 19 21 37 56 64 75 80 88 92 Low=1 High=11 mid=6 5 13 19 21 37 56 64 75 80 88 92 Low=7 High=11 mid=9 5 13 19 21 37 56 64 75 80 88 92 Low=7 mid=7 High=8 283283

第９章查找第二节静态查找表二、折半查找(举例－不成功)
第９章　查找第二节　静态查找表二、折半查找(举例－不成功) 当下界low大于上界high时，说明有序表中没有关键字等于K的元素，查找不成功找59 5 13 19 21 37 56 64 75 80 88 92 High=6 Low=7 284284

第９章查找第二节静态查找表二、折半查找(判定树) 判定树：描述查找过程的二叉树。有n个结点的判定树的深度为log2n +1
第９章　查找第二节　静态查找表二、折半查找(判定树) 判定树：描述查找过程的二叉树。有n个结点的判定树的深度为log2n +1 折半查找法在查找过程中进行的比较次数最多不超过log2n +1 有11个元素的表的例子 6 3 9 1 4 2 5 7 8 10 11 i 1 2 3 4 5 6 7 8 9 10 11 Ci

第９章查找第二节静态查找表二、折半查找(性能分析)
第９章　查找第二节　静态查找表二、折半查找(性能分析) 设有序表的长度n=2h-1（即h=log2(n+1)）,则描述折半查找的判定树是深度为h的满二叉树树中层次为1的结点有1个，层次为2的结点有2个，层次为h的结点有2h-1个假设表中每个记录的查找概率相等，则查找成功时折半查找的平均查找长度

第９章查找第二节静态查找表二、折半查找(特点) 折半查找的效率比顺序查找高(特别是在静态查找表的长度很长时)
第９章　查找第二节　静态查找表二、折半查找(特点) 折半查找的效率比顺序查找高(特别是在静态查找表的长度很长时) 折半查找只能适用于有序表，并且以顺序存储结构存储

第９章查找第二节静态查找表三、分块查找分块查找是一种索引顺序表(分块有序表)查找方法，是折半查找和顺序查找的简单结合
第９章　查找第二节　静态查找表三、分块查找分块查找是一种索引顺序表(分块有序表)查找方法，是折半查找和顺序查找的简单结合索引顺序表(分块有序表)将整个表分成几块，块内无序，块间有序所谓块间有序是指后一块表中所有记录的关键字均大于前一块表中的最大关键字 288288

第９章查找第二节静态查找表三、分块查找(分块有序表) 主表：用数组存放待查记录,每个数据元素至少含有关键字域
第９章　查找第二节　静态查找表三、分块查找(分块有序表) 主表：用数组存放待查记录,每个数据元素至少含有关键字域索引表：每个结点含有最大关键字域和指向本块第一个结点的指针 21 1 75 5 92 9 索引表 5 19 13 21 75 56 64 37 88 80 92 主表 289289

第９章查找第二节静态查找表三、分块查找(举例) 采用折半查找方法在索引表中找到块[第2块] 用顺序查找方法在主表对
第９章　查找第二节　静态查找表三、分块查找(举例) 采用折半查找方法在索引表中找到块[第2块] 用顺序查找方法在主表对应块中找到记录[第3记录] 21 1 75 5 92 9 索引表 5 19 13 21 75 56 64 37 88 80 92 主表找64 290290

第９章查找第二节静态查找表三、分块查找(性能分析) 若将长度为n的表分成b块，每块含s个记录，并设表中每个记录查找概率相等
第９章　查找第二节　静态查找表三、分块查找(性能分析) 若将长度为n的表分成b块，每块含s个记录，并设表中每个记录查找概率相等用折半查找方法在索引表中查找索引块，　ASL块间≈log2(n/s+1) 用顺序查找方法在主表对应块中查找记录，ASL块内=s/2 ASL≈log2(n/s+1) + s/2 291291

第９章查找第三节动态查找表一、动态查找表表结构本身是在查找过程中动态生成的
第９章　查找第三节　动态查找表一、动态查找表表结构本身是在查找过程中动态生成的若表中存在其关键字等于给定值key的记录,表明查找成功；否则插入关键字等于key的记录。 292292

第９章查找第三节动态查找表二、二叉排序树空树或者是具有如下特性的二叉树：
第９章　查找第三节　动态查找表二、二叉排序树空树或者是具有如下特性的二叉树： ⑴.若它的左子树不空，则左子树上所有结点的值均小于根结点的值； ⑵.若它的右子树不空，则右子树上所有结点的值均大于根结点的值； ⑶.它的左、右子树也都分别是二叉排序树。 293293

第９章查找第三节动态查找表二、二叉排序树(举例) 二叉排序树非二叉排序树 294294 56 64 5 92 37 88 19
第９章　查找第三节　动态查找表二、二叉排序树(举例) 56 64 5 92 37 88 19 80 21 13 75 56 64 5 92 37 88 19 80 21 13 75 60 二叉排序树非二叉排序树 294294

第９章查找第三节动态查找表二、二叉排序树(查找) 二叉排序树又称二叉查找树查找算法：给定值与根结点比较： 1.若相等，查找成功
第９章　查找第三节　动态查找表二、二叉排序树(查找) 56 64 5 92 37 88 19 80 21 13 75 二叉排序树又称二叉查找树查找算法：给定值与根结点比较： 1.若相等，查找成功 2.若小于，查找左子树 3.若大于，查找右子树在二叉排序树中查找关键字值等于37,88,94 295295

第９章查找第三节动态查找表二、二叉排序树(插入) 二叉排序树是一种动态树表当树中不存在查找的结点时，作插入操作
第９章　查找第三节　动态查找表二、二叉排序树(插入) 二叉排序树是一种动态树表当树中不存在查找的结点时，作插入操作新插入的结点一定是叶子结点（只需改动一个结点的指针）该叶子结点是查找不成功时路径上访问的最后一个结点左孩子或右孩子(新结点值小于或大于该结点值) 296296

第９章查找第三节动态查找表二、二叉排序树(插入举例) 插入结点94 297297 56 64 5 92 37 88 19 80 21
第９章　查找第三节　动态查找表二、二叉排序树(插入举例) 插入结点94 56 64 5 92 37 88 19 80 21 13 75 94 297297

第９章查找第三节动态查找表二、二叉排序树(生成举例)
第９章　查找第三节　动态查找表二、二叉排序树(生成举例) 画出在初始为空的二叉排序树中依次插入56,64,92,80,88,75时该树的生长全过程 56 56 64 56 64 92 56 64 92 80 56 64 92 88 80 56 64 92 88 80 75 298298

第９章查找第三节动态查找表二、二叉排序树(中序遍历)
第９章　查找第三节　动态查找表二、二叉排序树(中序遍历) 中序遍历二叉排序树，可得到一个关键字的有序序列,如5,13,19,21,37,56,64,92,75,80,88 56 64 5 92 37 88 19 80 21 13 75 299299

第９章查找第三节动态查找表二、二叉排序树(删除)
第９章　查找第三节　动态查找表二、二叉排序树(删除) 删除二叉排序树中的一个结点后，必须保持二叉排序树的特性（左子树的所有结点值小于根结点，右子树的所有结点值大于根结点）也即保持中序遍历后，输出为有序序列 300300

第９章查找第三节动态查找表二、二叉排序树(删除) 被删除结点具有以下三种情况： 1.是叶子结点 2.只有左子树或右子树
第９章　查找第三节　动态查找表二、二叉排序树(删除) 被删除结点具有以下三种情况： 1.是叶子结点 2.只有左子树或右子树 3.同时有左、右子树 301301

第９章查找第三节动态查找表二、二叉排序树(删除) 1.被删除结点是叶子结点直接删除结点，并让其父结点指向该结点的指针变为空
第９章　查找第三节　动态查找表二、二叉排序树(删除) 1.被删除结点是叶子结点直接删除结点，并让其父结点指向该结点的指针变为空 56 64 5 92 37 88 19 80 21 13 75 删除结点88 302302

第９章查找第三节动态查找表二、二叉排序树(删除) 2.被删除结点只有左子树或右子树
第９章　查找第三节　动态查找表二、二叉排序树(删除) 2.被删除结点只有左子树或右子树删除结点,让其父结点指向该结点的指针指向其左子树(或右子树),即用孩子结点替代被删除结点即可 56 64 5 92 88 19 80 21 13 75 56 64 5 92 37 88 19 80 21 13 75 56 5 92 37 88 19 80 21 13 75 原图删除结点37(只有左子树) 删除结点64(只有右子树)

第９章查找第三节动态查找表二、二叉排序树(删除) 3.被删除结点p既有左子树，又有右子树
第９章　查找第三节　动态查找表二、二叉排序树(删除) P C p F PR f CL Q SL QL S q s 3.被删除结点p既有左子树，又有右子树以中序遍历时的直接前驱s替代被删除结点p，然后再删除该直接前驱（只可能有左孩子） 304304

第９章查找第三节动态查找表二、二叉排序树(删除) 3.被删除结点既有左子树，又有右子树(举例) 原图删除结点13 删除结点56
第９章　查找第三节　动态查找表二、二叉排序树(删除) 3.被删除结点既有左子树，又有右子树(举例) 56 64 5 92 37 88 19 80 21 13 75 56 64 92 37 88 19 80 21 5 75 37 64 5 92 21 88 80 19 13 75 原图删除结点13 删除结点56 305305

第９章查找第三节动态查找表二、二叉排序树(性能分析)
第９章　查找第三节　动态查找表二、二叉排序树(性能分析) 在最好的情况下，二叉排序树为一近似完全二叉树时，其查找深度为log2n量级，即其时间复杂性为O(log2n) 75 56 19 64 5 37 21 80 13 88 92 306306

第９章查找第三节动态查找表二、二叉排序树(性能分析)
第９章　查找第三节　动态查找表二、二叉排序树(性能分析) 80 88 92 64 75 21 19 13 56 37 5 在最坏的情况下，二叉排序树为近似线性表时(如以升序或降序输入结点时)，其查找深度为n量级，即其时间复杂性为O(n) 307307

第９章查找第三节动态查找表二、二叉排序树(特性) 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列（通过中序遍历）
第９章　查找第三节　动态查找表二、二叉排序树(特性) 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列（通过中序遍历）插入新记录时，只需改变一个结点的指针，相当于在有序序列中插入一个记录而不需要移动其它记录二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构 308308

第９章查找第三节动态查找表二、二叉排序树(特性)
第９章　查找第三节　动态查找表二、二叉排序树(特性) 80 88 92 64 75 21 19 13 56 37 5 但当插入记录的次序不当时(如升序或降序)，则二叉排序树深度很深(11)，增加了查找的时间 309309

第９章查找第三节动态查找表三、平衡二叉树[AVL](定义) 平衡二叉树是二叉排序(查找)树的另一种形式
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](定义) 平衡二叉树是二叉排序(查找)树的另一种形式平衡二叉树又称AVL树(Adelsen-Velskii and Landis) 其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1，即|hL-hR|≤1 56 64 5 92 37 88 19 80 21 13 75 56 5 64 19 13 75 37 80 92 88 21 310310 AVL树非AVL树

第９章查找第三节动态查找表三、平衡二叉树[AVL](平衡因子)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](平衡因子) 每个结点附加一个数字, 给出该结点左子树的高度减去右子树的高度所得的高度差,这个数字即为结点的平衡因子balance AVL树任一结点平衡因子只能取 -1, 0, 1 56 5 64 19 13 75 37 80 92 88 21 -1 1 311311

第９章查找第三节动态查找表三、平衡二叉树[AVL](平衡化旋转)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](平衡化旋转) 如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。平衡化旋转(处理)有两类： 1.单向旋转 (单向右旋和单向左旋) 2.双向旋转 (先左后右旋转和先右后左旋转) 312312

第９章查找第三节动态查找表三、平衡二叉树[AVL](平衡化旋转) 每插入一个新结点时, AVL树中相关结点的平衡状态会发生改变。
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](平衡化旋转) 每插入一个新结点时, AVL树中相关结点的平衡状态会发生改变。在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。 313313

三、平衡二叉树[AVL](平衡化单向旋转)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](平衡化单向旋转) 如果这三个结点处于一条直线上(“/”型或“\”型)，则采用单向旋转进行平衡化单向旋转分为单向右旋(“/”型)和单向左旋(“\”型) A C B 单向右旋 A C B 单向左旋 314314

三、平衡二叉树[AVL](平衡化双向旋转)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](平衡化双向旋转) 如果这三个结点处于一条折线上(“<”型或“>”型)，则采用双向旋转进行平衡化。双旋转分为先左后右(“<”型)和先右后左(“>”型) A C B A C B A B C A B C B C A A C B 先左后右旋转先右后左旋转 315315

第９章查找第三节动态查找表三、平衡二叉树[AVL](单向右旋)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](单向右旋) 在B左子树BL上插入新结点使其高度增1，导致结点A的平衡因子增到 +2，造成不平衡。 h A AR BR B BL + 1 +1 +2 316316

第９章查找第三节动态查找表三、平衡二叉树[AVL](单向右旋) 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和BL(“/”型)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](单向右旋) 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和BL(“/”型) 以结点B为旋转轴，将结点A顺时针(右)旋转。 h A AR BR B BL + 1 +1 +2 317317

第９章查找第三节动态查找表三、平衡二叉树[AVL](单向左旋)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](单向左旋) 在B右子树BR中插入新结点，该子树高度增1导致结点A的平衡因子变成-2，出现不平衡。 h A B BR AL BL + 1 -1 -2 318318

第９章查找第三节动态查找表三、平衡二叉树[AVL](单向左旋) 沿插入路径检查三个结点A、B和BR(“\”型)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](单向左旋) 沿插入路径检查三个结点A、B和BR(“\”型) 以结点B为旋转轴，让结点A反时针(左)旋转 h A B BR AL BL + 1 -1 -2 319319

三、平衡二叉树[AVL](先左后右双向旋转)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](先左后右双向旋转) 在C的子树CL或CR中插入新结点，该子树的高度增1。结点A的平衡因子变为+2，发生了不平衡 +1 h A AR C BL h-1 B CL CR +2 -1 +1 h A h-1 AR C BL B CL CR 320320

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](先左后右双向旋转) 从结点A起沿插入路径选取3个结点A、B和C(“<”型) 以结点B为旋转轴，做单向左旋 +2 -1 +1 h A h-1 AR C BL B CL CR +2 h A AR C BL h-1 B CL CR 321321

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](先左后右双向旋转) 再以结点C为旋转轴，做单向右旋 +2 h A AR C BL h-1 B CL CR -1 h A h-1 AR C BL B CL CR 322322

三、平衡二叉树[AVL](先右后左双向旋转)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](先右后左双向旋转) 在C的子树CL或CR中插入新结点，该子树的高度增1。结点A的平衡因子变为-2，发生了不平衡 -1 -2 h A B AL CL CR h-1 C BR -1 h A B BR C h-1 AL CL CR 323323

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](先右后左双向旋转) 从结点A起沿插入路径选取3个结点A、C和D(“>”型) 以结点B为旋转轴，作单向右旋 -2 h A B BR h-1 AL CL CR C -1 -2 h A B AL CL CR h-1 C BR 324324

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](先右后左双向旋转) 再以结点C为旋转轴，作单向左旋 -2 h A B BR h-1 AL CL CR C +1 h A h-1 B BR C AL CL CR 325325

第９章查找第三节动态查找表三、平衡二叉树[AVL](举例)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](举例) 画出在初始为空的AVL树中依次插入64,5,13,21,19,80,75,37,56时该树的生长过程，并在有旋转时说出旋转的类型。 64 64 5 +1 64 5 13 -1 +2 左右双旋 13 5 21 +1 -1 64 1 2 3 4 326326

第９章查找第三节动态查找表三、平衡二叉树[AVL](续例)
第９章　查找第三节　动态查找表三、平衡二叉树[AVL](续例) 继续插入19,80,75,37,56时该树的生长过程，并在有旋转时说出旋转的类型。 13 5 64 21 19 +1 +2 右单旋 -1 -2 5 327327

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](续例) 继续插入19,80,75,37,56时该树的生长过程，并在有旋转时说出旋转的类型。 5 13 21 80 19 64 -1 -2 5 64 19 左单旋 -1 13 21 80 6 328328

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](续例) 继续插入19,80,75,37,56时该树的生长过程，并在有旋转时说出旋转的类型。 -2 右左双旋 13 5 19 75 80 21 +1 64 -1 75 64 13 5 80 21 19 7 329329

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](续例) 继续插入19,80,75,37,56时该树的生长过程，并在有旋转时说出旋转的类型。 75 5 +1 13 64 37 80 19 -1 21 8 330330

第９章　查找第三节　动态查找表三、平衡二叉树[AVL](续例) 继续插入19,80,75,37,56时该树的生长过程，并在有旋转时说出旋转的类型。 56 -2 5 75 64 +2 13 37 19 21 80 -1 75 13 5 21 +1 64 56 -1 80 37 19 左右双旋 9 331331

第９章查找第三节动态查找表三、平衡二叉树(删除)
第９章　查找第三节　动态查找表三、平衡二叉树(删除) 如果被删结点A最多只有一个孩子，那么将结点A从树中删去，并将其双亲指向它的指针指向它的唯一的孩子，并作平衡化处理如果被删结点A没有孩子，则直接删除之，并作平衡化处理如果被删结点A有两个子女，则用该结点的直接前驱S替代被删结点，然后对直接前驱S作删除处理(S只有一个孩子或没有孩子) 332332

第９章　查找第三节　动态查找表四、B-/B+树移至17周上 333333

第９章查找第四节哈希表一、哈希表(散列表) 哈希(Hash)表又称散列表
第９章　查找第四节　哈希表一、哈希表(散列表) 哈希(Hash)表又称散列表散列表是一种直接计算记录存放地址的方法，它在关键码与存储位置之间直接建立了映象。 334334

第９章查找第四节哈希表一、哈希表(函数) 哈希函数是从关键字空间到存储地址空间的一种映象
第９章　查找第四节　哈希表一、哈希表(函数) 哈希函数是从关键字空间到存储地址空间的一种映象哈希函数在记录的关键字与记录的存储地址之间建立起一种对应关系。可写成： addr(ai)= H(keyi) H(·)为哈希函数 keyi是表中元素ai关键字,addr(ai)是存储地址 335335

第９章查找第四节哈希表一、哈希表(查找) 哈希查找也叫散列查找，是利用哈希函数进行查找的过程。
第９章　查找第四节　哈希表一、哈希表(查找) 哈希查找也叫散列查找，是利用哈希函数进行查找的过程。首先利用哈希函数及记录的关键字计算出记录的存储地址然后直接到指定地址进行查找不需要经过比较，一次存取就能得到所查元素 336336

第９章查找第四节哈希表一、哈希表(冲突) 不同的记录，其关键字通过哈希函数的计算，可能得到相同的地址
第９章　查找第四节　哈希表一、哈希表(冲突) 不同的记录，其关键字通过哈希函数的计算，可能得到相同的地址把不同的记录映射到同一个散列地址上，这种现象称为冲突 337337

第９章查找第四节哈希表一、哈希表(定义) 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法
第９章　查找第四节　哈希表一、哈希表(定义) 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上并以关键字在地址集中的“象”作为相应记录在表中的存储位置如此构造所得的查找表称之为“哈希表” 338338

第９章查找第四节哈希表二、哈希函数(均匀性)
第９章　查找第四节　哈希表二、哈希函数(均匀性) 哈希函数实现的一般是从一个大的集合（部分元素，空间位置上一般不连续）到一个小的集合（空间连续）的映射一个好的哈希函数，对于记录中的任何关键字，将其映射到地址集合中任何一个地址的概率应该是相等的即关键字经过哈希函数得到一个“随机的地址” 339339

第９章查找第四节哈希表二、哈希函数(要求) 哈希函数应是简单的，能在较短的时间内计算出结果。
第９章　查找第四节　哈希表二、哈希函数(要求) 哈希函数应是简单的，能在较短的时间内计算出结果。哈希函数的定义域必须包括需要存储的全部关键字，如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。散列函数计算出来的地址应能均匀分布在整个地址空间中 340340

第９章查找第四节哈希表二、哈希函数(直接定址法) 直接定址法中，哈希函数取关键字的线性函数 H(key) = a x key + b
第９章　查找第四节　哈希表二、哈希函数(直接定址法) 直接定址法中，哈希函数取关键字的线性函数 H(key) = a x key + b 　其中a和b为常数 341341

第９章查找第四节哈希表二、哈希函数(直接定址法－举例) H(key) = key - 2004131000 342342 06
第９章　查找第四节　哈希表二、哈希函数(直接定址法－举例) H(key) = key 06 邓煦男信息工程学院 11 张国明 17 刘金棠 22 陈俊东 25 邱益林 31 陈明亮 32 郭宁 342342

第９章查找第四节哈希表二、哈希函数(直接定址法－特性) 直接定址法仅适合于地址集合的大小与关键字集合的大小相等的情况
第９章　查找第四节　哈希表二、哈希函数(直接定址法－特性) 直接定址法仅适合于地址集合的大小与关键字集合的大小相等的情况当a=1时，H(key)=key，即用关键字作地址在实际应用中能使用这种哈希函数的情况很少 343343

第９章查找第四节哈希表二、哈希函数(数字分析法) 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)
第９章　查找第四节　哈希表二、哈希函数(数字分析法) 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us) 分析关键字集中的全体从中提取分布均匀的若干位或它们的组合作为地址。 344344

第９章查找第四节哈希表二、哈希函数(数字分析法－举例) 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数 
第９章　查找第四节　哈希表二、哈希函数(数字分析法－举例) 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数 …..  分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址 345345

第９章查找第四节哈希表二、哈希函数(数字分析法－特性) 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况
第９章　查找第四节　哈希表二、哈希函数(数字分析法－特性) 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况数字分析法完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。 346346

第９章查找第四节哈希表二、哈希函数(平方取中法) 以关键字的平方值的中间几位作为存储地址。
第９章　查找第四节　哈希表二、哈希函数(平方取中法) 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” 同时平方值的中间各位又能受到整个关键字中各位的影响。 347347

第９章查找第四节哈希表二、哈希函数(平方取中法－举例) 此方法在词典处理中使用十分广泛。
第９章　查找第四节　哈希表二、哈希函数(平方取中法－举例) 此方法在词典处理中使用十分广泛。它先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址。 348348

第９章查找第四节哈希表二、哈希函数(平方取中法－举例) 标识符的八进制内码表示及其平方值标识符内码内码的平方散列地址
第９章　查找第四节　哈希表二、哈希函数(平方取中法－举例) 标识符的八进制内码表示及其平方值标识符　内码　　　　　内码的平方　散列地址 A A B DMAX DMAX AMAX AMAX 349349

第９章查找第四节哈希表二、哈希函数(平方取中法－特性) 平方取中法是较常用的构造哈希函数的方法
第９章　查找第四节　哈希表二、哈希函数(平方取中法－特性) 平方取中法是较常用的构造哈希函数的方法适合于关键字中的每一位都有某些数字重复出现且频度很高的情况中间所取的位数，由哈希表长决定 350350

第９章查找第四节哈希表二、哈希函数(折叠法)
第９章　查找第四节　哈希表二、哈希函数(折叠法) 将关键字分割成位数相同的若干部分(最后部分的倍数可以不同)，然后取它们的叠加和(舍去进位)为哈希地址。移位叠加:将分割后的几部分低位对齐相加间界叠加:从一端沿分割界来回折送，然后对齐相加 351351

第９章查找第四节哈希表二、哈希函数(折叠法－举例) 关键字为：0442205864，哈希地址位数为4 5 8 6 4 4 2 2 0
第９章　查找第四节　哈希表二、哈希函数(折叠法－举例) 关键字为：，哈希地址位数为4 0 4 H(key)=0088 移位叠加 0 4 H(key)=6092 间界叠加 352352

第９章查找第四节哈希表二、哈希函数(折叠法－特性) 折叠法适合于关键字的数字位数特别多，而且每一位上数字分布大致均匀的情况
第９章　查找第四节　哈希表二、哈希函数(折叠法－特性) 折叠法适合于关键字的数字位数特别多，而且每一位上数字分布大致均匀的情况 353353

第９章查找第四节哈希表二、哈希函数(除留余数法) 取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址
第９章　查找第四节　哈希表二、哈希函数(除留余数法) 取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址 H(key) = key MOD p ( p≤m ) m为表长 p为不大于m的素数或是不含20以下的质因子 354354

第９章查找第四节哈希表二、哈希函数(除留余数法－p值)
第９章　查找第四节　哈希表二、哈希函数(除留余数法－p值) 给定一组关键字为: 12,39,18,24,33,21，若取 p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3 可见，若p中含质因子3, 则所有含质因子3的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能 355355

第９章查找第四节哈希表二、哈希函数(除留余数法－特性) 除留余数法是一种最简单、最常用的构造哈希函数的方法
第９章　查找第四节　哈希表二、哈希函数(除留余数法－特性) 除留余数法是一种最简单、最常用的构造哈希函数的方法不令可以对关键字直接取模(MOD)，也可在折叠、平方取中等运算之后取模 356356

第９章查找第四节哈希表三、处理冲突的方法 “处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。
第９章　查找第四节　哈希表三、处理冲突的方法 “处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。处理冲突的方法主要有三种： 1.开放定址法 2.再哈希法 3.链地址法 357357

第９章查找第四节哈希表三、处理冲突的方法(开放定址法)
第９章　查找第四节　哈希表三、处理冲突的方法(开放定址法) 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs，1≤s≤m-1 Hi = [H(key)+di] MOD m i=1,2,…,s H(key)为哈希函数 m为哈希表长 358358

三、处理冲突的方法(开放定址法－线性探测)
第９章　查找第四节　哈希表三、处理冲突的方法(开放定址法－线性探测) 当di取1,2,3,…,m-1时，称这种开放定址法为线性探测再散列举例：给定关键字集合{19,01,23,14,55,68, 11,82,36}，设定哈希函数H(key)=key MOD 11 (表长=11) 55 01 23 14 68 11 82 36 19 359359

三、处理冲突的方法(开放定址法－二次探测)
第９章　查找第四节　哈希表三、处理冲突的方法(开放定址法－二次探测) 当di取= 12,22,32,…时，称这种开放定址法为二次探测再散列举例：给定关键字集合{19,01,23,14,55,68, 11,82,36}，设定哈希函数H(key)=key MOD 11 (表长=11) 55 01 23 14 36 82 68 19 11 360360

第９章查找第四节哈希表三、处理冲突的方法(开放定址法－特性) 优点：只要哈希表中有空位置，总能找到一个不发生冲突的地址
第９章　查找第四节　哈希表三、处理冲突的方法(开放定址法－特性) 优点：只要哈希表中有空位置，总能找到一个不发生冲突的地址缺点：易产生“二次聚集”，即在处理同义词的冲突过程中，又添加了非同义词的冲突，对查找不利 361

第９章查找第四节哈希表三、处理冲突的方法(再哈希法) 构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，直到冲突不再发生，即：
第９章　查找第四节　哈希表三、处理冲突的方法(再哈希法) 构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，直到冲突不再发生，即： Hi = Rhi(key) i=1,2,……k Rhi—不同的哈希函数特点：不易产生聚集，但增加计算时间 362

第９章查找第四节哈希表三、处理冲突的方法(链地址法) 将所有哈希地址相同的记录都链接在同一链表中
第９章　查找第四节　哈希表三、处理冲突的方法(链地址法) 将所有哈希地址相同的记录都链接在同一链表中举例：给定关键字集合{19,01,23,14,55,68, 11,82,36}，设定哈希函数H(key)=key MOD 11 (表长=11)[表后插入] 1 2 3 4 5 6 7 8 9 10 ^ 55 11 ^ 01 ^ 23 68 ^ 14 36 ^ 82 ^ 19 ^ 363

第９章查找第四节哈希表三、处理冲突的方法(链地址法－举例)
第９章　查找第四节　哈希表三、处理冲突的方法(链地址法－举例) 79 ^ 27 1 14 55 68 84 19 20 10 23 11 例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为： H(key)=key MOD 13,用链地址法处理冲突[表头插入] 364

第９章查找第四节哈希表四、哈希表的实现假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，其结构可以定义如下：
第９章　查找第四节　哈希表四、哈希表的实现假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，其结构可以定义如下： #define LEN 32 struct node { int data; struct node *next; }; struct node *HashTab[LEN]; 365

第９章查找第四节哈希表四、哈希表的实现－哈希函数hash() 返回值为哈希表地址 int hash(int key) {
第９章　查找第四节　哈希表四、哈希表的实现－哈希函数hash() 返回值为哈希表地址 int hash(int key) { retAddr = key MOD LEN; return(retAddr); } 366

第９章查找第四节哈希表四、哈希表的实现－查找过程对于给定值key，计算哈希地址 p=hash(Key)
第９章　查找第四节　哈希表四、哈希表的实现－查找过程给定k值计算hash(key) 此地址为空关键字==key 查找失败查找成功按处理冲突方法计算下一地址 Y N 对于给定值key，计算哈希地址 p=hash(Key) 若HashTab[p].next=NULL，则查找不成功若HashTab[p].next.data = key，则查找成功否则 “求下一地址”，再进行比较 367

四、哈希表的实现－查找函数search()
第９章　查找第四节　哈希表四、哈希表的实现－查找函数search() 若找到key，返回其结点指针；否则将其插入表中再返回其结点指针[表头插入] node *search(int key) { p = hash(key); q = HashTab[p].next; while (q != NULL)) { if (q.data == key) return(q); q = q.next;} q = malloc(sizeof(node)); q.data = key; q.next = HashTab[p]; HashTab[p].next = q; return(q);} 368

四、哈希表的实现－删除函数remove()
第９章　查找第四节　哈希表四、哈希表的实现－删除函数remove() 若key在表中，删除并返回1；否则仅返回0。 int remove(int key) { p = hash(key); r = HashTab[p]; q = r.next; while (q != NULL) { if (q.data == key) { r.next = q.next; free(q); return(1);} r = q; q = q.next;} return(0);} 369

第９章查找第四节哈希表五、哈希查找的性能分析
第９章　查找第四节　哈希表五、哈希查找的性能分析虽然哈希表在关键字与记录的存储位置之间建立了直接映象，但由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程因此，仍需以平均查找长度(ASL)作为衡量哈希表的查找效率的量度 370

五、哈希查找的性能分析(线性探测再散列举例)
第９章　查找第四节　哈希表五、哈希查找的性能分析(线性探测再散列举例) 假设每个关键字的查找概率相同，则： ASL = (1/9)(1x4 + 2x2 + 3x1 + 5x1 + 6x1) = 22/9 55 01 23 14 68 11 82 36 19 371

五、哈希查找的性能分析(二次探测再散列举例)
第９章　查找第四节　哈希表五、哈希查找的性能分析(二次探测再散列举例) 假设每个关键字的查找概率相同，则： ASL = (1/9)(1x5 + 2x2 + 3x2) = 15/9 55 01 23 14 36 82 68 19 11 372

第９章查找第四节哈希表五、哈希查找的性能分析(链地址法举例) 假设每个关键字的查找概率相同，则：
第９章　查找第四节　哈希表五、哈希查找的性能分析(链地址法举例) 假设每个关键字的查找概率相同，则： ASL = (1/9)(1x6 + 2x3) = 12/9 1 2 3 4 5 6 7 8 9 10 ^ 55 11 ^ 01 ^ 23 68 ^ 14 36 ^ 82 ^ 19 ^ 373

第９章查找第四节哈希表五、哈希查找的性能分析决定哈希表查找的ASL的因素： 1.选用的哈希函数 2.选用的处理冲突的方法
第９章　查找第四节　哈希表五、哈希查找的性能分析决定哈希表查找的ASL的因素： 1.选用的哈希函数 2.选用的处理冲突的方法 3.哈希表的装填因子 374

第９章查找第四节哈希表五、哈希查找的性能分析(装填因子) 哈希表的装填因子是哈希表中填入的记录数与哈希表的长度的比值，即：
第９章　查找第四节　哈希表五、哈希查找的性能分析(装填因子) 哈希表的装填因子是哈希表中填入的记录数与哈希表的长度的比值，即： α = 哈希表中填入的记录数 / 哈希表的长度装填因子α标志哈希表的装满程序 375

第９章查找第四节哈希表五、哈希查找的性能分析(装填因子) 直观来看：装填因子α越小，发生冲突的可能性就越小
第９章　查找第四节　哈希表五、哈希查找的性能分析(装填因子) 直观来看：装填因子α越小，发生冲突的可能性就越小装填因子α越大，发生冲突的可能性就越大 376

五、哈希查找的性能分析(平均查找长度ASL)
第９章　查找第四节　哈希表五、哈希查找的性能分析(平均查找长度ASL) 线性探测再散列的哈希表查找成功时： ASL ≈ (½)(1 + 1/(1-α)) 二次探测再散列的哈希表查找成功时： ASL ≈ -(1/α)ln(1-α) 链地址法处理冲突的哈希表查找成功时： ASL ≈ (1 + α/2) 377

数据结构第十章内部排序深圳大学计算机系蔡茂国

第10章内部排序第一节排序一、排序(Sorting) 排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列
第10章　内部排序第一节　排序一、排序(Sorting) 排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列内部排序：在排序期间数据对象全部存放在内存的排序；外部排序：在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 379379

第10章内部排序第一节排序二、排序基本操作排序的基本操作包括：比较：比较两个关键字的大小移动：将记录从一个位置移动至另一个位置
第10章　内部排序第一节　排序二、排序基本操作排序的基本操作包括：比较：比较两个关键字的大小移动：将记录从一个位置移动至另一个位置 380380

第10章内部排序第一节排序三、排序时间复杂度排序的时间复杂度可用算法执行中的记录关键字比较次数与记录移动次数来衡量。
第10章　内部排序第一节　排序三、排序时间复杂度排序的时间复杂度可用算法执行中的记录关键字比较次数与记录移动次数来衡量。 381381

第10章内部排序第一节排序四、排序方法的稳定性
第10章　内部排序第一节　排序四、排序方法的稳定性如果在记录序列中有两个记录r[i]和r[j], 它们的关键字 key[i] == key[j] , 且在排序之前, 记录r[i]排在r[j]前面。如果在排序之后, 记录r[i]仍在记录r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 382382

第10章　内部排序第二节　插入排序每步将一个待排序的对象, 按其关键字大小, 插入到前面已经排好序的有序表的适当位置上, 直到对象全部插入为止。 383383

第10章内部排序第二节插入排序一、直接插入排序
第10章　内部排序第二节　插入排序一、直接插入排序当插入第i(i≥1)个对象时, 前面的r[0], r[1], …, r[i-1]已经排好序。用r[i]的关键字与r[i-1], r[i-2], …的关键字顺序进行比较(和顺序查找类似)，如果小于，则将r[x]向后移动(插入位置后的记录向后顺移) 找到插入位置即将r[i]插入 384384

第10章内部排序第二节插入排序一、直接插入排序(举例)
第10章　内部排序第二节　插入排序一、直接插入排序(举例) 已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08 21 25 49 25* 16 08 385385

第10章内部排序第二节插入排序一、直接插入排序(举例) i = 1 i = 2 0 1 2 3 4 5 temp 21 25 49
第10章　内部排序第二节　插入排序一、直接插入排序(举例) temp 21 25 49 25* 16 08 i = 1 temp 21 25 49 25* 16 08 i = 2 386386

第10章内部排序第二节插入排序一、直接插入排序(举例) i = 3 i = 4 21 25 49 25* 16 08
第10章　内部排序第二节　插入排序一、直接插入排序(举例) 21 25 49 25* 16 08 i = 3 temp 21 25 49 25* 16 08 i = 4 387387

第10章内部排序第二节插入排序一、直接插入排序(举例) i = 5 完成 0 1 2 3 4 5 temp 21 25 49 25*
第10章　内部排序第二节　插入排序一、直接插入排序(举例) temp 21 25 49 25* 16 08 i = 5 21 25 49 25* 16 08 完成 388388

第10章内部排序第二节插入排序一、直接插入排序(算法实现) 389389
第10章　内部排序第二节　插入排序一、直接插入排序(算法实现) void InsertSort (int r[ ], int m ) { // 假设关键字为整型，放在向量r[]中 int n, j, temp; for ( n = 1; n < m; n++ ) { temp = r[n]; for ( j = n; j > 0; j-- ) //从后向前顺序比较，并依次后移 if ( temp < r[j-1] ) r[j] = r[j-1]; else break; r[j] = temp; } 389389

第10章内部排序第二节插入排序一、直接插入排序(算法分析) 关键字比较次数和记录移动次数与记录关键字的初始排列有关。
第10章　内部排序第二节　插入排序一、直接插入排序(算法分析) 关键字比较次数和记录移动次数与记录关键字的初始排列有关。最好情况下, 排序前记录已按关键字从小到大有序, 每趟只需与前面有序记录序列的最后一个记录比较1次, 移动2次记录, 总的关键字比较次数为 n-1, 记录移动次数为 2(n-1)。 390390

第10章内部排序第二节插入排序一、直接插入排序(算法分析)
第10章　内部排序第二节　插入排序一、直接插入排序(算法分析) 最坏情况下, 第i趟时第i个记录必须与前面i个记录都做关键字比较, 并且每做1次比较就要做1次数据移动。则总关键字比较次数KCN和记录移动次数RMN分别为 391391

第10章内部排序第二节插入排序一、直接插入排序(算法分析) 在平均情况下的关键字比较次数和记录移动次数约为 n2/4。
第10章　内部排序第二节　插入排序一、直接插入排序(算法分析) 在平均情况下的关键字比较次数和记录移动次数约为 n2/4。直接插入排序的时间复杂度为O(n2)。直接插入排序是一种稳定的排序方法直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法 392392

第10章内部排序第二节插入排序二、折半插入排序折半插入排序在查找记录插入位置时，采用折半查找算法
第10章　内部排序第二节　插入排序二、折半插入排序折半插入排序在查找记录插入位置时，采用折半查找算法折半查找比顺序查找快, 所以折半插入排序在查找上性能比直接插入排序好但需要移动的记录数目与直接插入排序相同(为O(n2)) 折半插入排序的时间复杂度为O(n2)。折半插入排序是一种稳定的排序方法 393393

第10章内部排序第二节插入排序三、希尔排序从直接插入排序可以看出，当待排序列为正序时，时间复杂度为O(n)
第10章　内部排序第二节　插入排序三、希尔排序从直接插入排序可以看出，当待排序列为正序时，时间复杂度为O(n) 若待排序列基本有序时，插入排序效率会提高希尔排序方法是先将待排序列分成若干子序列分别进行插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序希尔排序又称为缩小增量排序。 394394

第10章内部排序第二节插入排序三、希尔排序(算法)
第10章　内部排序第二节　插入排序三、希尔排序(算法) 首先取一个整数 gap < n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2 重复上述的子序列划分和排序工作，直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。 395395

第10章内部排序第二节插入排序三、希尔排序(举例) 已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08
第10章　内部排序第二节　插入排序三、希尔排序(举例) 已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08 21 08 25 49 25* 16 396396

第10章内部排序第二节插入排序三、希尔排序(举例) Gap = 3 Gap = 2 0 1 2 3 4 5 21 08 25 49
第10章　内部排序第二节　插入排序三、希尔排序(举例) Gap = 3 21 08 25 49 25* 16 Gap = 2 21 08 25 49 25* 16 397397

第10章　内部排序第二节　插入排序三、希尔排序(举例) Gap = 1 21 08 25 49 25* 16 398398

第10章内部排序第二节插入排序三、希尔排序(算法分析) 开始时 gap 的值较大, 子序列中的记录较少, 排序速度较快
第10章　内部排序第二节　插入排序三、希尔排序(算法分析) 开始时 gap 的值较大, 子序列中的记录较少, 排序速度较快随着排序进展, gap 值逐渐变小, 子序列中记录个数逐渐变多,由于前面大多数记录已基本有序, 所以排序速度仍然很快。 Gap的取法有多种。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。 399399

第10章内部排序第二节插入排序三、希尔排序(算法分析) 对特定的待排序记录序列，可以准确地估算关键字的比较次数和记录移动次数。
第10章　内部排序第二节　插入排序三、希尔排序(算法分析) 对特定的待排序记录序列，可以准确地估算关键字的比较次数和记录移动次数。希尔排序所需的比较次数和移动次数约为n 1.3 当n趋于无穷时可减少到n x(log2 n)2 希尔排序的时间复杂度约为O(n x(log2 n)2) 希尔排序是一种不稳定的排序方法 400400

第10章内部排序第三节快速排序一、起泡排序设待排序记录序列中的记录个数为n。一般地，第i趟起泡排序从1到n-i+1
第10章　内部排序第三节　快速排序一、起泡排序设待排序记录序列中的记录个数为n。一般地，第i趟起泡排序从1到n-i+1 依次比较相邻两个记录的关键字，如果发生逆序，则交换之其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。 401401

第10章内部排序第三节快速排序一、起泡排序 i=1时，为第一趟排序，关键字最大的记录将被交换到最后一个位置
第10章　内部排序第三节　快速排序一、起泡排序 i=1时，为第一趟排序，关键字最大的记录将被交换到最后一个位置 i=2时，为第二趟排序，关键字次大的记录将被交换到最后第二个位置：关键字小的记录不断上浮(起泡)，关键字大的记录不断下沉(每趟排序最大的一直沉到底) 402402

第10章内部排序第三节快速排序一、起泡排序 21 25 49 16 08 403403 初始关键字第一趟排序第四趟排序
第10章　内部排序第三节　快速排序一、起泡排序 21 08 25 49 16 初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序 403403

第10章内部排序第三节快速排序一、起泡排序(性能分析)
第10章　内部排序第三节　快速排序一、起泡排序(性能分析) 最好情况：在记录的初始排列已经按关键字从小到大排好序时,此算法只执行一趟起泡,做n-1次关键字比较,不移动记录 404404

第10章内部排序第三节快速排序一、起泡排序(性能分析)
第10章　内部排序第三节　快速排序一、起泡排序(性能分析) 最坏情况：执行n-1趟起泡,第i趟做n-i次关键字比较, 执行n-i次记录交换，共计：起泡排序的时间复杂度为O(n2) 起泡排序是一种稳定的排序方法 405405

第10章　内部排序第三节　快速排序二、快速排序任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列：左侧子序列中所有记录的关键字都小于或等于基准记录的关键字右侧子序列中所有记录的关键字都大于基准记录的关键字 406406

第10章内部排序第三节快速排序二、快速排序基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。
第10章　内部排序第三节　快速排序二、快速排序基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。基准记录也称为枢轴（或支点）记录。 407407

第10章内部排序第三节快速排序二、快速排序(算法) 取序列第一个记录为枢轴记录，其关键字为Pivotkey
第10章　内部排序第三节　快速排序二、快速排序(算法) 取序列第一个记录为枢轴记录，其关键字为Pivotkey 指针low指向序列第一个记录位置指针high指向序列最后一个记录位置 408408

第10章内部排序第三节快速排序二、快速排序(算法) 一趟排序(某个子序列)过程
第10章　内部排序第三节　快速排序二、快速排序(算法) 一趟排序(某个子序列)过程 1.从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low+1 2.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-1 3.重复1,2，直到low=high，将枢轴记录放在low(high)指向的位置 409409

第10章内部排序第三节快速排序二、快速排序(算法) 对枢轴记录前后两个子序列执行相同的操作，直到每个子序列都只有一个记录为止
第10章　内部排序第三节　快速排序二、快速排序(算法) 对枢轴记录前后两个子序列执行相同的操作，直到每个子序列都只有一个记录为止 410410

第10章内部排序第三节快速排序二、快速排序(举例) 21 08 25 49 25* 16 初始关键字一次交换二次交换三次交换
第10章　内部排序第三节　快速排序二、快速排序(举例) 21 08 25 49 25* 16 初始关键字 pivotkey 一次交换二次交换三次交换 high-1 完成一趟排序 low high 411411

第10章内部排序第三节快速排序二、快速排序(举例) 25 49 25* 16 21 08 完成一趟排序分别进行快速排序有序序列
第10章　内部排序第三节　快速排序二、快速排序(举例) 25 49 25* 16 21 08 完成一趟排序分别进行快速排序有序序列 412412

第10章内部排序第三节快速排序二、快速排序(性能分析) 快速排序是一个递归过程, 其递归树如图所示
第10章　内部排序第三节　快速排序二、快速排序(性能分析) 快速排序是一个递归过程, 其递归树如图所示 21 25* 25 49 08 16 利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧 413413

第10章内部排序第三节快速排序二、快速排序(性能分析) 快速排序的趟数取决于递归树的高度。
第10章　内部排序第三节　快速排序二、快速排序(性能分析) 快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后, 该记录的左侧子序列与右侧子序列的长度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。 414414

第10章内部排序第三节快速排序二、快速排序(性能分析)
第10章　内部排序第三节　快速排序二、快速排序(性能分析) 在 n个元素的序列中,对一个记录定位所需时间为 O(n)。若设 t(n) 是对 n 个元素的序列进行排序所需的时间, 而且每次对一个记录正确定位后, 正好把序列划分为长度相等的两个子序列, 此时, 总的计算时间为： T(n)  cn + 2T(n/2 ) // c 是一个常数  cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)  2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) ………  cn log2n + nT(1) = O(n log2n ) 415415

第10章内部排序第三节快速排序二、快速排序(性能分析) 可以证明, 快速排序的平均计算时间也是O(nlog2n)。
第10章　内部排序第三节　快速排序二、快速排序(性能分析) 可以证明, 快速排序的平均计算时间也是O(nlog2n)。实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。但快速排序是一种不稳定的排序方法 416416

第10章内部排序第三节快速排序二、快速排序(性能分析)
第10章　内部排序第三节　快速排序二、快速排序(性能分析) 在最坏情况下, 即待排序记录序列已经按其关键字从小到大排好序, 其递归树成为单支树, 每次划分只得到一个比上一次少一个记录的子序列。必须经过n-1 趟才能把所有记录定位, 而且第 i 趟需要经过 n-i 次关键字比较才能找到第 i 个记录的安放位置，总的关键字比较次数将达到 417417

第10章内部排序第三节快速排序二、快速排序(改进) 枢轴记录取low、high、(low+high)/2三者指向记录关键字居中的记录
第10章　内部排序第三节　快速排序二、快速排序(改进) 枢轴记录取low、high、(low+high)/2三者指向记录关键字居中的记录 418418

第10章内部排序第四节选择排序一、简单选择排序
第10章　内部排序第四节　选择排序一、简单选择排序每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i个待排序记录中选出关键字最小的记录,与第i个记录交换 419419

第10章内部排序第四节选择排序一、简单选择排序(举例) 0 1 2 3 4 5 21 08 25 49 25* 16 21 08
第10章　内部排序第四节　选择排序一、简单选择排序(举例) 21 08 25 49 25* 16 21 08 25 49 25* 16 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21 i=0 i=1 i=2 08 21 25 49 25* 16 08 21 25 49 25* 16 420420

第10章内部排序第四节选择排序一、简单选择排序(举例) 0 1 2 3 4 5 21 08 25 49 25* 16 08 25
第10章　内部排序第四节　选择排序一、简单选择排序(举例) 21 08 25 49 25* 16 08 25 49 25* 16 21 i=3 i=4 i=5 最小者 25* 不需交换最小者 25 结束 08 25 49 16 21 25* 08 49 16 21 25* 25 421421

第10章内部排序第四节选择排序一、简单选择排序(性能分析) 直接选择排序的关键字比较次数 KCN 与记录的初始排列无关。
第10章　内部排序第四节　选择排序一、简单选择排序(性能分析) 直接选择排序的关键字比较次数 KCN 与记录的初始排列无关。设整个待排序记录序列有n个记录,则第i趟选择具有最小关键字记录所需的比较次数总是 n-i-1次。总的关键字比较次数为 422422

第10章内部排序第四节选择排序一、简单选择排序(性能分析)
第10章　内部排序第四节　选择排序一、简单选择排序(性能分析) 记录的移动次数与记录序列的初始排列有关。当这组记录的初始状态是按其关键字从小到大有序的时候,记录的移动次数RMN=0,达到最少。最坏情况是每一趟都要进行交换，总的记录移动次数为 RMN = 3(n-1)。直接选择排序是一种不稳定的排序方法。 423423

第10章　内部排序第四节　选择排序二、堆排序设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 1 开始连续编号。若满足 Ki  K2i && Ki  K2i+1 则称该关键字集合构成一个堆(最大堆) 424424

第10章　内部排序第四节　选择排序二、堆排序(举例) 49 25 25* 16 21 08 1 3 6 5 4 2 425425

第10章内部排序第四节选择排序二、堆排序堆排序主要要解决两个问题： 1.如何根据给的序列建初始堆
第10章　内部排序第四节　选择排序二、堆排序堆排序主要要解决两个问题： 1.如何根据给的序列建初始堆 2.如何在交换掉根结点后，将剩下的结点调整为新的堆(筛选) 426426

第10章内部排序第四节选择排序二、堆排序(筛选) 输出根结点用最后结点代替根结点值
第10章　内部排序第四节　选择排序二、堆排序(筛选) 输出根结点用最后结点代替根结点值比较根结点与两个子结点的值，如果小于其中一个子结点，则选择大的子结点与根结点交换继续将交换的结点与其子结点比较直到叶子结点或者根节点值大于两个子结点 427427

第10章内部排序第四节选择排序二、堆排序(筛选举例) 49 08 25* 16 21 25 1 3 6 5 4 2 49 25
第10章　内部排序第四节　选择排序二、堆排序(筛选举例) 49 08 25* 16 21 25 1 3 6 5 4 2 49 25 25* 16 21 08 1 3 6 5 4 2 49 25* 08 16 21 25 1 3 6 5 4 2 428428

第10章内部排序第四节选择排序二、堆排序(创建初始堆) 根据给定的序列，从1至n按顺序创建一个完全二叉树
第10章　内部排序第四节　选择排序二、堆排序(创建初始堆) 根据给定的序列，从1至n按顺序创建一个完全二叉树由最后一个非终端结点(第n/2个结点)开始至第1个结点，逐步做筛选 429429

第10章内部排序第四节选择排序二、堆排序(创建初始堆举例) 已知待序的一组记录的初始排列为：21,25,49, 25*,16,08
第10章　内部排序第四节　选择排序二、堆排序(创建初始堆举例) 已知待序的一组记录的初始排列为：21,25,49, 25*,16,08 21 25 25* 49 16 08 1 2 3 4 5 6 i 初始排序码集合 430430

第10章内部排序第四节选择排序二、堆排序(创建初始堆举例) i i 21 25 49 16 08 1 2 3 4 5 6 21 25
第10章　内部排序第四节　选择排序二、堆排序(创建初始堆举例) 21 25 25* 49 16 08 1 2 3 4 5 6 i 21 25 25* 16 49 08 1 3 6 5 4 2 i 初始排序码集合 i = 3 时的局部调整 431431

第10章内部排序第四节选择排序二、堆排序(创建初始堆举例) i 21 25 49 16 08 1 2 3 4 5 6 49 25
第10章　内部排序第四节　选择排序二、堆排序(创建初始堆举例) 21 25 25* 49 16 08 1 2 3 4 5 6 i 49 25 25* 16 21 08 1 3 6 5 4 2 i = 2 时的局部调整 i = 1 时的局部调整形成最大堆 432432

第10章内部排序第四节选择排序二、堆排序(举例) 49 25 25* 21 16 08 1 2 3 4 5
第10章　内部排序第四节　选择排序二、堆排序(举例) 49 25 25* 21 16 08 1 2 3 4 5 * * 交换 0 号与 5 号记录, 5 号记录就位初始最大堆 433433

第10章内部排序第四节选择排序二、堆排序(举例) 25 25* 08 21 16 49 1 2 3 4 5
第10章　内部排序第四节　选择排序二、堆排序(举例) 25 25* 08 21 16 49 1 2 3 4 5 25 25* 16 25* 交换 0 号与 4 号记录, 4 号记录就位从 0 号到 4 号重新调整为最大堆 434434

第10章内部排序第四节选择排序二、堆排序(举例) 25* 16 08 21 25 49 1 2 3 4 5
第10章　内部排序第四节　选择排序二、堆排序(举例) 25* 16 08 21 25 49 1 2 3 4 5 25* * 交换 0 号与 3 号记录, 3 号记录就位从 0 号到 3 号重新调整为最大堆 435435

第10章　内部排序第四节　选择排序二、堆排序(举例) 21 16 25* 08 25 49 1 2 3 4 5 * * 交换 0 号与 2 号记录, 2 号记录就位从 0 号到 2 号重新调整为最大堆 436436

第10章　内部排序第四节　选择排序二、堆排序(举例) 16 08 25* 21 25 49 1 2 3 4 5 * * 交换 0 号与 1 号记录, 1 号记录就位从 0 号到 1 号重新调整为最大堆 437437

第10章内部排序第四节选择排序二、堆排序(性能分析) 对于长度为n的序列，其对应的完全二叉树的深度为k(2k-1  n  2k)
第10章　内部排序第四节　选择排序二、堆排序(性能分析) 对于长度为n的序列，其对应的完全二叉树的深度为k(2k-1  n  2k) 对深度为k的堆，筛选算法中进行的关键比较次数至多为2(k-1)次堆排序时间主要耗费在建初始堆和调整建新堆(筛选)上建初始堆最多做n/2次筛选 438438

第10章内部排序第四节选择排序二、堆排序(性能分析) 对长度为n的序列，排序最多需要做n-1次调整建新堆(筛选)
第10章　内部排序第四节　选择排序二、堆排序(性能分析) 对长度为n的序列，排序最多需要做n-1次调整建新堆(筛选) 因此共需要O(nxk)量级的时间 k = log2n 堆排序时间复杂度为O(nlog2n) 堆排序是一个不稳定的排序方法 439439

第10章　内部排序第五节　归并排序一、归并归并是将两个或两个以上的有序表合并成一个新的有序表。 440440

第10章内部排序第五节归并排序二、两路归并 441441 typedef int SortData;
第10章　内部排序第五节　归并排序 Left mid right InitList mergedList 二、两路归并 typedef int SortData; void merge ( SortData InitList[ ], SortData mergedList[ ], int left, int mid, int right ) { int i = left, j = mid+1, k = left; while ( i <= mid && j <= right ) //两两比较将较小的并入 if ( InitList[i] <= InitList[j] ) { mergedList [k] = InitList[i]; i++; k++; } else { mergedList [k] = InitList[j]; j++; k++; } while (i <= mid) { mergedList[k] = InitList[i]; i++; k++; }//将mid前剩余的并入 while (j <= right){ mergedList[k] = InitList[j]; j++; k++; }//将mid后剩余的并入 } 441441

第10章内部排序第五节归并排序二、两路归并(性能分析) 假设待归两个有序表长度分别为m和n，则两路归并后，新的有序表长度为m+n
第10章　内部排序第五节　归并排序二、两路归并(性能分析) 假设待归两个有序表长度分别为m和n，则两路归并后，新的有序表长度为m+n 两路归并操作至多只需要m+n次移位和m+n次比较因此两路归并的时间复杂度为O(m+n) 442442

第10章内部排序第五节归并排序三、2路－归并排序将n个记录看成是n个有序序列
第10章　内部排序第五节　归并排序三、2路－归并排序将n个记录看成是n个有序序列将前后相邻的两个有序序列归并为一个有序序列(两路归并) 重复做两路归并操作，直到只有一个有序序列为止 443443

第10章内部排序第五节归并排序三、2路－归并排序(举例) 0 1 2 3 4 5 21 08 25 49 25* 16 21 08
第10章　内部排序第五节　归并排序三、2路－归并排序(举例) 21 08 25 49 25* 16 21 08 25 49 25* 16 一趟归并之后二趟归并之后三趟归并之后 21 08 25 49 25* 16 21 08 25 49 25* 16 444444

第10章内部排序第五节归并排序三、2路－归并排序(性能分析) 如果待排序的记录为n个，则需要做log2n趟两路归并排序
第10章　内部排序第五节　归并排序三、2路－归并排序(性能分析) 如果待排序的记录为n个，则需要做log2n趟两路归并排序每趟两路归并排序的时间复杂度为O(n) 因此2路－归并排序的时间复杂度为O(nlog2n) 归并排序是一种稳定的排序方法 445445

第10章内部排序第六节基数排序一、多关键字的排序例：对52张扑克牌按以下次序排序：
第10章　内部排序第六节　基数排序一、多关键字的排序例：对52张扑克牌按以下次序排序： 2<3<……<A<2<3<……<A< 2<3<……<A<2<3<……<A 两个关键字：花色（<<<）面值（2<3<…<A）并且“花色”地位高于“面值” 446446

一、多关键字的排序(最低位优先法LSD)
第10章　内部排序第六节　基数排序一、多关键字的排序(最低位优先法LSD) 从最低位关键字kd起进行排序，然后再对高一位的关键字排序，…… 依次重复，直至对最高位关键字k1排序后，便成为一个有序序列 447447

一、多关键字的排序(最低位优先法LSD－举例)
第10章　内部排序第六节　基数排序一、多关键字的排序(最低位优先法LSD－举例) 21 08 25 49 25* 16 21 08 25 49 25* 16 最低位(个位)排序后最高位(十位)排序后 21 08 25 49 25* 16 448448

第10章内部排序第六节基数排序二、链式基数排序基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法
第10章　内部排序第六节　基数排序二、链式基数排序基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法链式基数排序方法：用链表作存储结构的基数排序设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾指针 449449

第10章内部排序第六节基数排序二、链式基数排序
第10章　内部排序第六节　基数排序二、链式基数排序第i趟分配：根据第i位关键字的值，改变记录的指针，将链表中记录分配至10个链队列中，每个队列中记录关键字的第i位关键字相同第i趟收集：改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 450450

第10章　内部排序第六节　基数排序二、链式基数排序从最低位至最高位，逐位执行上述两步操作，最后得到一个有序序列 451451

第10章内部排序第六节基数排序二、链式基数排序(举例) 278 109 063 930 589 184 505 269 008
第10章　内部排序第六节　基数排序二、链式基数排序(举例) 初始状态 278 109 063 930 589 184 505 269 008 083 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 一趟分配一趟收集

第10章　内部排序第六节　基数排序二、链式基数排序(举例) 505 008 109 930 063 269 278 083 184 589 二趟收集 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配一趟收集

第10章　内部排序第六节　基数排序二、链式基数排序(举例) 008 063 083 109 184 269 278 505 589 930 三趟收集 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配二趟收集

第10章内部排序第六节基数排序二、链式基数排序(性能分析) 若每个关键字有 d 位,关键字的基数为radix
第10章　内部排序第六节　基数排序二、链式基数排序(性能分析) 若每个关键字有 d 位,关键字的基数为radix 需要重复执行d 趟“分配”与“收集” 每趟对 n 个对象进行“分配”，对radix个队列进行“收集” 总时间复杂度为O(d(n+radix))。 455455

第10章内部排序第六节基数排序二、链式基数排序(性能分析)
第10章　内部排序第六节　基数排序二、链式基数排序(性能分析) 若基数radix相同, 对于对象个数较多而关键字位数较少的情况, 使用链式基数排序较好。基数排序需要增加n+2radix个附加链接指针。基数排序是稳定的排序方法。 456456

第10章内部排序第七节各种排序方法比较排序方法平均时间最坏情况辅助存储适合情况插入排序 O(n2) O(1) 记录数不很多
第10章　内部排序第七节　各种排序方法比较排序方法平均时间最坏情况辅助存储适合情况插入排序 O(n2) O(1) 记录数不很多希尔排序 O(n(log2n)2) 不太多快速排序 O(nlog2n) O(log2n) 较多堆排序归并排序 O(n) 都可以基数排序 O(d(n+rd)) O(rd) 关键字位数少 457457

数据结构课程简介深圳大学计算机系蔡茂国.

Similar presentations

Presentation on theme: "数据结构课程简介深圳大学计算机系蔡茂国."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

数据结构 课程简介 深圳大学计算机系 蔡茂国.

Similar presentations

Presentation on theme: "数据结构 课程简介 深圳大学计算机系 蔡茂国."— Presentation transcript:

Similar presentations

About project

反馈

数据结构课程简介深圳大学计算机系蔡茂国.

Presentation on theme: "数据结构课程简介深圳大学计算机系蔡茂国."— Presentation transcript: