Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

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

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

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

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

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

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

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

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

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

10 第1章 数据结构绪论 第一节 数据结构 五、结构 四种基本结构 集合结构 线性结构 树形结构 图形结构 10 6 3 1 2 4 5 1 2
第1章 数据结构绪论 第一节 数据结构 五、结构 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

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

12 第1章 数据结构绪论 第一节 数据结构 六、数据结构 2. 线性数据结构举例 L = {K, R}
第1章 数据结构绪论 第一节 数据结构 六、数据结构 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

13 第1章 数据结构绪论 第一节 数据结构 六、数据结构 3. 树形数据结构举例 T = {K, R}
第1章 数据结构绪论 第一节 数据结构 六、数据结构 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

14 第1章 数据结构绪论 第一节 数据结构 六、数据结构 4. 图形数据结构举例 G = {K, R}
第1章 数据结构绪论 第一节 数据结构 六、数据结构 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

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

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

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

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

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

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

21 第1章 数据结构绪论 第二节 数据的结构 二、物理结构(存储结构) 复数存储结构举例 顺序存储结构 链式存储结构 … 0300 0302
第1章 数据结构绪论 第二节 数据的结构 二、物理结构(存储结构) 复数存储结构举例 顺序存储结构 链式存储结构 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

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

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

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

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

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

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

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

29 第1章 数据结构绪论 第三节 数据类型 三、抽象数据类型(ADT定义举例) ADT Triplet {
第1章 数据结构绪论 第三节 数据类型 三、抽象数据类型(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

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

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

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

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

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

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

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

37 第1章 数据结构绪论 第四节 算法分析 三、时间复杂度
第1章 数据结构绪论 第四节 算法分析 三、时间复杂度 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

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

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

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

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

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

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

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

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

46 第2章 线性表 第二节 顺序表 b b+l … b+(i-1)*l … … … b+(n-1)*l idle 一、顺序表(元素位置)
第2章 线性表 第二节 顺序表 一、顺序表(元素位置) 顺序表数据元素的位置: 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

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

48 第2章 线性表 第二节 顺序表 三、顺序表的初始化 创建一个顺序表L 48 Status InitList_Sq(Sqlist &L) {
第2章 线性表 第二节 顺序表 三、顺序表的初始化 创建一个顺序表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

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

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

51 第2章 线性表 第二节 顺序表 三、顺序表的插入 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

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

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

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

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

56 第2章 线性表 第二节 顺序表 四、顺序表的删除 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

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

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

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

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

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

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

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

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

65 第2章 线性表 第二节 线性链表 四、找指定元素 … a1 ai an n L  65
第2章 线性表 第二节 线性链表 四、找指定元素 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

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

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

68 第2章 线性表 第二节 线性链表 五、线性链表的插入 68
第2章 线性表 第二节 线性链表 五、线性链表的插入 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

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

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

71 第2章 线性表 第二节 线性链表 六、线性链表的删除 71
第2章 线性表 第二节 线性链表 六、线性链表的删除 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

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

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

74 第2章 线性表 第二节 线性链表 七、静态链表 与单链表区别: 1、静态链表暂时不用结点,链成一个备用链表 2、插入时,从备用链表中申请结点
第2章 线性表 第二节 线性链表 七、静态链表 与单链表区别: 1、静态链表暂时不用结点,链成一个备用链表 2、插入时,从备用链表中申请结点 3、删除结点时,将结点放入备用链表 74

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

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

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

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

79 第2章 线性表 第四节 双向链表 三、双向链表的定义 定义一个双向链表的结点 对于任何一个中间结点有:
第2章 线性表 第四节 双向链表 三、双向链表的定义 定义一个双向链表的结点 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

80 第2章 线性表 第四节 双向链表 四、双向链表的插入 双向链表的插入操作需要改变两个方向的指针 p p s L 31 48 15 L 31
第2章 线性表 第四节 双向链表 四、双向链表的插入 双向链表的插入操作需要改变两个方向的指针 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

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

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

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

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

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

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

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

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

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

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

91 第3章 栈和队列 第二节 顺序栈 四、顺序栈的主要操作 ADT Stack {
第3章 栈和队列 第二节 顺序栈 四、顺序栈的主要操作 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 第3章 栈和队列 第二节 顺序栈 五、创建顺序栈 92 Status InitStack(SqStack &S) {
第3章 栈和队列 第二节 顺序栈 五、创建顺序栈 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 第3章 栈和队列 第二节 顺序栈 六、进栈(插入新元素) 93 Status Push(SqStack &S, SElemType e) {
第3章 栈和队列 第二节 顺序栈 六、进栈(插入新元素) 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 第3章 栈和队列 第二节 顺序栈 七、出栈(删除元素) 94 Status Pop(SqStack &S, SElemType &e) {
第3章 栈和队列 第二节 顺序栈 七、出栈(删除元素) 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 第3章 栈和队列 第二节 顺序栈 八、取栈顶元素 95 Status GetTop(SqStack S, SElemType &e) {
第3章 栈和队列 第二节 顺序栈 八、取栈顶元素 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

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

97 第3章 栈和队列 第三节 栈的应用举例 一、数值转换 97 void conversion () {
第3章 栈和队列 第三节 栈的应用举例 一、数值转换 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

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

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

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

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

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

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

104 第3章 栈和队列 第三节 栈的应用举例 四、表达式求值  设置两个栈: 操作数栈(OPND) 运算符栈(OPTR) 104104

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

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

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

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

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

110 第3章 栈和队列 第四节 队列 四、顺序队列的进队和出队举例 A B C D B C D C D C D E F G C D E F G
第3章 栈和队列 第四节 队列 四、顺序队列的进队和出队举例 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

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

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

113 第3章 栈和队列 第五节 循环队列 二、循环队列空与满 front = rear,循环队列空
第3章 栈和队列 第五节 循环队列 二、循环队列空与满 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

114 第3章 栈和队列 第五节 循环队列 三、循环队列定义 114114 #define MAXQSIZE 100
第3章 栈和队列 第五节 循环队列 三、循环队列定义 #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

115 第3章 栈和队列 第五节 循环队列 三、循环队列插入元素 115115
第3章 栈和队列 第五节 循环队列 三、循环队列插入元素 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

116 第3章 栈和队列 第五节 循环队列 三、循环队列删除元素 116116
第3章 栈和队列 第五节 循环队列 三、循环队列删除元素 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

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

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

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

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

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

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

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

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

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

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

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

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

129 第4章 串 第三节 串的匹配算法 一、求子串位置函数Index() 129129
第4章 串 第三节 串的匹配算法 一、求子串位置函数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

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

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

132 第4章 串 第三节 串的匹配算法 二、KMP算法(举例) 假设主串ababcabcacbab,模式abcac,改进算法的匹配过程如下
第4章 串 第三节 串的匹配算法 二、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

133 第4章 串 第三节 串的匹配算法 二、KMP算法 假设主串为‘s1s2s3…sn’,模式串为‘p1p2p3…pm’
第4章 串 第三节 串的匹配算法 二、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

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

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

136 第4章 串 第三节 串的匹配算法 二、KMP算法(next函数) next函数定义为: 0 当j=1时
第4章 串 第三节 串的匹配算法 二、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

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

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

139 第4章 串 第三节 串的匹配算法 二、KMP算法(利用next函数) 利用next函数,可写出KMP算法如下:
第4章 串 第三节 串的匹配算法 二、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

140 第4章 串 第三节 串的匹配算法 二、KMP算法(C语言实现) 140140
第4章 串 第三节 串的匹配算法 二、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

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

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

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

144 第6章 树与二叉树 第一节 树的概念与基本术语 一、树的定义(举例) A C G B D E F K L H M I J
第6章 树与二叉树 第一节 树的概念与基本术语 一、树的定义(举例) 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

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

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

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

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

149 第6章 树与二叉树 第二节 二叉树 二、二叉树性质1 在二叉树的第i层上至多有2i-1个结点 证明:
第6章 树与二叉树 第二节 二叉树 二、二叉树性质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

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

151 第6章 树与二叉树 第二节 二叉树 四、二叉树性质3 如果二叉树终端结点数为n0,度为2的结点数为n2,则n0=n2+1 证明:
第6章 树与二叉树 第二节 二叉树 四、二叉树性质3 如果二叉树终端结点数为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

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

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

154 第6章 树与二叉树 第二节 二叉树 六、完全二叉树(性质4) 具有n个结点的完全二叉树,其深度为log2n +1
第6章 树与二叉树 第二节 二叉树 六、完全二叉树(性质4) 具有n个结点的完全二叉树,其深度为log2n +1 设k为深度,由二叉树性质2,已知    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

155 第6章 树与二叉树 第二节 二叉树 六、完全二叉树(性质5) 在完全二叉树中,结点i的双亲为i/2 结点i的左孩子LCHILD(i)=2i
第6章 树与二叉树 第二节 二叉树 六、完全二叉树(性质5) 在完全二叉树中,结点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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

177 第6章 树与二叉树 第五节 树与森林 一、树的存储结构 2.孩子表示法 将每个结点的孩子排列起来,用单链表表示 将每个结点排列成一个线性表
第6章 树与二叉树 第五节 树与森林 一、树的存储结构 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

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

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

180 第6章 树与二叉树 第五节 树与森林 三、森林与二叉树的对应关系
第6章 树与二叉树 第五节 树与森林 三、森林与二叉树的对应关系 如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟,则可找到一个唯一的二叉树与之对应 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

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

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

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

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

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

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

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

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

189 第6章 树与二叉树 第六节 赫夫曼树及其应用 二、Huffman树(举例) 189189 F : {7} {5} {2} {4}
第6章 树与二叉树 第六节 赫夫曼树及其应用 二、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

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

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

192 第6章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 令左孩子分支为编码‘0’,右孩子分支为编码‘1’ 得到不等长编码:
第6章 树与二叉树 第六节 赫夫曼树及其应用 三、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

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

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

195 第7章 图 第一节 图的定义与术语 二、无向图(Undigraph) 用(x,y)表示两个顶点x,y之间的一条边(edge)
第7章 图 第一节 图的定义与术语 二、无向图(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

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

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

198 第7章 图 第一节 图的定义与术语 三、有向图(Digraph)
第7章 图 第一节 图的定义与术语 三、有向图(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

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

200 第7章 图 第一节 图的定义与术语 三、有向图 邻接:如果<x,y>E,称x邻接到y,或y邻接自x
第7章 图 第一节 图的定义与术语 三、有向图 邻接:如果<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

201 第7章 图 第一节 图的定义与术语 四、路径(Path) 路径:是一个从顶点x到y的顶点序列(x, vi1, vi2,…, vin, y)
第7章 图 第一节 图的定义与术语 四、路径(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

202 第7章 图 第一节 图的定义与术语 五、回路 回路或环:路径的开始顶点与最后一个顶点相同,即路径中(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

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

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

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

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

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

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

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

210 第7章 图 第二节 图的存储结构 一、邻接矩阵(网络)
第7章 图 第二节 图的存储结构 一、邻接矩阵(网络) 有向网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

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

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

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

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

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

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

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

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

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

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

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

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

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

224 第7章 图 第二节 图的存储结构 四、邻接多重表(举例) 1 2 3 4 5 1 3 2 5 4 224224 1 1 2 1 3 ^ 1
第7章 图 第二节 图的存储结构 四、邻接多重表(举例) 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

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

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

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

228 第7章 图 第三节 图的遍历 二、深度优先搜索(举例) 采用以下链表存储结构时,DFS次序为0,1,2,3,4,5 F 1 2 3 4 5
第7章 图 第三节 图的遍历 二、深度优先搜索(举例) 采用以下链表存储结构时,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

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

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

231 第7章 图 第三节 图的遍历 三、广度优先搜索(BFS算法) 所有顶点访问标志visited[]设置为FALSE
第7章 图 第三节 图的遍历 三、广度优先搜索(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

232 第7章 图 第三节 图的遍历 三、广度优先搜索(举例) BFS为0,1,4,5,2,3 BFS为v1,v2,v3,v4,
第7章 图 第三节 图的遍历 三、广度优先搜索(举例) 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

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

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

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

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

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

238 四、普里姆(Prim)算法生成最小生成树
第7章 图 第四节 图的连通性问题 四、普里姆(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

239 第7章 图 第四节 图的连通性问题 四、普里姆(Prim)算法举例 239239 28 5 4 6 1 3 2 10 25 14 24 22
第7章 图 第四节 图的连通性问题 四、普里姆(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)

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

241 五、克鲁斯卡尔(Kruskal)算法举例
第7章 图 第四节 图的连通性问题 五、克鲁斯卡尔(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

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

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

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

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

246 第7章 图 第五节 最短路径 二、Dijkstra算法 设S为已求得的最短路径的终点的集合 下一条最短路径(设其终点为vi)为以下之一:
第7章 图 第五节 最短路径 二、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

247 第7章 图 第五节 最短路径 二、Dijkstra算法 1. 初始化: S ← {v0 };
第7章 图 第五节 最短路径 二、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

248 第7章 图 第五节 最短路径 二、Dijkstra算法 顶点 D 1 5 2 ∞ 10 9 3 7 4 15 终点j S {0,1}
第7章 图 第五节 最短路径 二、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

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

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

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

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

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

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

255 第7章 图 第六节 有向无环图及其应用 二、拓扑排序(举例) 1 3 2 4 1 3 2 4 3 2 4 原图 输出0之后 输出0,1之后
第7章 图 第六节 有向无环图及其应用 二、拓扑排序(举例) 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之后

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

257 第7章 图 第六节 有向无环图及其应用 三、AOV-网(举例) 257257 拓扑排序结果为
第7章 图 第六节 有向无环图及其应用 三、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

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

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

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

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

262 第7章 图 第六节 有向无环图及其应用 五、关键路径 3.关键活动有关的量 e(i):活动ai最早开始时间 l(i):活动ai最迟开始时间
第7章 图 第六节 有向无环图及其应用 五、关键路径 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

263 第7章 图 第六节 有向无环图及其应用 五、关键路径 3.关键活动有关的量 ve(j):事件vj最早开始时间
第7章 图 第六节 有向无环图及其应用 五、关键路径 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

264 第7章 图 第六节 有向无环图及其应用 五、关键路径 3.关键活动有关的量 从ve(0)=0开始向前递推
第7章 图 第六节 有向无环图及其应用 五、关键路径 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

265 第7章 图 第六节 有向无环图及其应用 五、关键路径 4.求关键活动算法 从始点v0出发,令ve[0]=0,按拓扑有序求ve[j]
第7章 图 第六节 有向无环图及其应用 五、关键路径 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

266 第7章 图 第六节 有向无环图及其应用 五、关键路径(举例) 活动 e l l-e a1 4 a2 5 9 a3 a4 7 12 a5 a6
第7章 图 第六节 有向无环图及其应用 五、关键路径(举例) 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

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

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

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

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

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

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

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

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

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

276 第9章 查找 第二节 静态查找表 一、顺序查找(算法实现)
第9章 查找 第二节 静态查找表 一、顺序查找(算法实现) 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 设置“哨兵”的目的是省略对下标越界的检查,提高算法执行速度

277 第9章 查找 第二节 静态查找表 一、顺序查找(举例) 找64 0 1 2 3 4 5 6 7 8 9 10 11 64 5 13 19
第9章 查找 第二节 静态查找表 一、顺序查找(举例) 找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

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

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

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

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

282 第9章 查找 第二节 静态查找表 二、折半查找(算法) 1.n个对象从小到大存放在有序顺序表ST中,k为给定值
第9章 查找 第二节 静态查找表 二、折半查找(算法) 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

283 第9章 查找 第二节 静态查找表 二、折半查找(举例-成功) 283283 找64 1 2 3 4 5 6 7 8 9 10 11 5 13
第9章 查找 第二节 静态查找表 二、折半查找(举例-成功) 找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

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

285 第9章 查找 第二节 静态查找表 二、折半查找(判定树) 判定树:描述查找过程的二叉树。 有n个结点的判定树的深度为log2n +1
第9章 查找 第二节 静态查找表 二、折半查找(判定树) 判定树:描述查找过程的二叉树。 有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

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

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

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

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

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