数据结构与算法设计-第9章查找ppt课件

1、第 2 页第第9 9章章 查找查找9.1 静态查找表静态查找表 9.2 动态查找表动态查找表 9.3 哈希表哈希表第 3 页第第9 9章章 查找查找l查找表：由同一类型的数据元素或记录构查找表：由同一类型的数据元素或记录构成的集合。成的集合。l查找表的根本操作查找表的根本操作: 1) 查询某个查询某个“特定的数据元素能否在表中特定的数据元素能否在表中l2) 检索某个检索某个“特定的数据元素的各种属特定的数据元素的各种属性性l3) 插入一个数据元素插入一个数据元素l4) 删去某个数据元素删去某个数据元素l静态查找表：只作查询和检索操作的查找表。静态查找表：只作查询和检索操作的查找表。l动态查找表

2、：在查找过程中同时作插入或删除动态查找表：在查找过程中同时作插入或删除操作的查找表。操作的查找表。第 4 页第第9 9章章 查找查找l记录：由假设干数据项构成的数据元素。记录：由假设干数据项构成的数据元素。l关键字：能标识一个数据元素或记录的数关键字：能标识一个数据元素或记录的数据项。据项。l主关键字：能独一地标识一个记录的关键字。主关键字：能独一地标识一个记录的关键字。l次关键字：用以识别假设干记录的关键字。次关键字：用以识别假设干记录的关键字。 学号学号 姓名姓名 专业专业 年龄年龄 20190001 20190001 王洪王洪 计算机计算机 17 17 20190002 20190002

3、 李文李文 计算机计算机 18 18 20190003 20190003 谢军谢军 计算机计算机 18 18 20190004 20190004 张辉张辉 信息工程信息工程 20 20 20190005 20190005 李文李文 信息工程信息工程 19 19第 5 页第第9 9章章 查找查找l查找：根据给定的某个值，在查找表中确定一查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，假个其关键字等于给定值的记录或数据元素，假设表中存在这样的记录，那么称查找胜利，查设表中存在这样的记录，那么称查找胜利，查找结果为该记录在查找表中的位置；否那么称找结果为该记录在查找表中

4、的位置；否那么称为查找不胜利，查找结果为为查找不胜利，查找结果为0或或NULL。 学号学号 姓名姓名 专业专业 年龄年龄 20190001 20190001 王洪王洪 计算机计算机 17 17 20190002 20190002 李文李文 计算机计算机 18 18 20190003 20190003 谢军谢军 计算机计算机 18 18 20190004 20190004 张辉张辉 信息工程信息工程 20 20 20190005 20190005 李文李文 信息工程信息工程 19 19第 6 页第第9 9章章 查找查找l查找方法评价：平均查找长度查找方法评价：平均查找长度l平均查找长度平均查找长

5、度ASL ( Average Search Length)：为确定记录在表中的位置，需：为确定记录在表中的位置，需和给定值进展比较的关键字的个数的期和给定值进展比较的关键字的个数的期望值叫查找算法的平均查找长度。望值叫查找算法的平均查找长度。l用于度量查找算法的效率用于度量查找算法的效率l查找算法的根本操作：比较查找算法的根本操作：比较l设查找胜利的概率为设查找胜利的概率为1( Pi=1 )l 平均查找长度平均查找长度ASL = PiCi l Ci：查找第：查找第 i 个记录所需的比较次数个记录所需的比较次数l Pi：查找第：查找第 i 个记录的概率个记录的概率第 7 页第第9章章 查找查找l

6、关键字类型定义关键字类型定义l typedef float KeyType; 实型实型l typedef int KeyType; 整型整型l typedef char* KeyType; 字符串型字符串型l数据元素类型定义数据元素类型定义l typedef struct l KeyType key; 关键字域关键字域l 其他域其他域l ElemType; key 第 8 页第第9章章 查找查找查找条件的判别：查找条件的判别：对数值型关键字对数值型关键字 #define EQ(a,b) (a) = = (b) #define LT(a,b) (a) (b) #define LQ(a,b) (a

7、) = (b)对字符串型关键字对字符串型关键字 #define EQ(a,b) (!strcmp(a),(b) #define LT(a,b) (strcmp(a),(b) 0) #define LQ(a,b) (strcmp(a),(b) = 0)第 9 页第第9 9章章 查找查找l静态查找静态查找l在指定的表中查找某一个在指定的表中查找某一个“特定特定的数据元素能否存在，检索某一个的数据元素能否存在，检索某一个“特定数据元素的各种属性。特定数据元素的各种属性。l动态查找动态查找l在查找的过程中同时插入表中在查找的过程中同时插入表中不存在的数据元素，或者从查找表中删不存在的数据元素，或者从查

8、找表中删除已存在的某个数据元素。除已存在的某个数据元素。第 10 页l静态查找静态查找l顺序表的查找：顺序查找顺序表的查找：顺序查找l有序表的查找：折半查找有序表的查找：折半查找l索引顺序表的查找：分块查找索引顺序表的查找：分块查找9.1 9.1 静态查找表静态查找表第 11 页l 查找表查找表l用线性表表示时用线性表表示时L1=(45,61,12,3,37,24,90,53,98,78l 用顺序表表示静态查找表用顺序表表示静态查找表l 用线性链表表示静态查找表用线性链表表示静态查找表l 查找方法：顺序查找查找方法：顺序查找9.1 9.1 静态查找表静态查找表第 12 页l顺序表类型定义顺序表

9、类型定义l typedef struct l ElemType *elem; / 0号单元留空号单元留空l int length; l SSTable;9.1 9.1 静态查找表静态查找表- -顺序表查找顺序表查找与线性表顺序与线性表顺序存储构造比较一下存储构造比较一下少了初始分配容少了初始分配容量量listsize 0 1 2 3 4 5 6 7 8 9 10 m- 0 1 2 3 4 5 6 7 8 9 10 m-1 1 45 61 12 3 37 24 90 53 98 78 45 61 12 3 37 24 90 53 98 78ST.elemSSTable ST;第 13 页int

10、Search_Seq ( SSTable ST, KeyType key ) /在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于key的数据元素。假设找的数据元素。假设找到，那么函数值为该元素在表中的位置，否那么为到，那么函数值为该元素在表中的位置，否那么为0。 ST.elem0.key = key; / “哨兵哨兵 for (i=ST.length; !EQ(key,ST.elemi.Key); -i) ; / 空操作，从后往前比较空操作，从后往前比较 return i; / 假设找到前往该元素在表中的位置假设找到前往该元素在表中的位置/ 假设表中不存在待查元素假设表中不存在

11、待查元素, 那么第那么第0个元素即哨兵满足条件，所个元素即哨兵满足条件，所以以i=0 /Search_Seq9.1 9.1 静态查找表静态查找表 0 1 2 3 4 5 6 7 8 9 10 m- 0 1 2 3 4 5 6 7 8 9 10 m-1 1 45 61 12 3 37 24 90 53 98 78 45 61 12 3 37 24 90 53 98 78ST.elemkey免去查找过程中每免去查找过程中每一步都要检测整个一步都要检测整个表能否查找终了？表能否查找终了？第 14 页例例1：在下表中查找：在下表中查找 key = 8 的结点。的结点。9.1 9.1 静态查找表静态查找

12、表80 01 12 2n-3n-3n-2n-2n-1n-1n nST.elem ST.elem keykey10010010100 07 71 13 3iiiiiii查找不胜利，查找不胜利，i = 0i = 080 01 12 2n-3n-3n-2n-2n-1n-1n nST.elem ST.elem keykey例例2 2：在下表中查找：在下表中查找 key = 8 key = 8 的结点。的结点。10010010100 08 81 13 3iii查找胜利，查找胜利，i = n-2i = n-2第 15 页l特点特点l无排序要求；无排序要求；l存储构造：顺序、链式；存储构造：顺序、链式；l平

13、均查找长度平均查找长度ASLSS=(n+1)/2；9.1 9.1 静态查找表静态查找表第 16 页l查找表：用有序表表示时查找表：用有序表表示时l查找方法：折半查找二分查找查找方法：折半查找二分查找l查找过程：先确定待查记录所在的范围区查找过程：先确定待查记录所在的范围区间，然后逐渐减少范围直到找到或找不到该间，然后逐渐减少范围直到找到或找不到该记录为止。记录为止。l例：有原始查找表例：有原始查找表l45,61,12,3,37,24,90,53,98,78l为进展折半查找，需求先进展排序：为进展折半查找，需求先进展排序：l L=(3,12,24,37,45,53,61,78,90,98)9.1

14、 9.1 静态查找表静态查找表- -有序表查找有序表查找第 17 页例：查找例：查找 Key=24 的记录。的记录。9.1 9.1 静态查找表静态查找表- -有序表查找有序表查找 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98 3 12 24 37 45 53 61 78 90 98lowlow midmid high 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98 3 12 24 37 45 53 61 7

15、8 90 98lowlowmidmid high 2445 2412 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98 3 12 24 37 45 53 61 78 90 98LowLow highmidmid第 18 页int Search_Bin ( SSTable ST, KeyType key ) /在有序表在有序表ST中用折半查找法查找其关键字等于中用折半查找法查找其关键字等于key的数据元素。假设找到，那么前往该元素在表中的的数据元素。假设找到，那么前往该元素在表中的位置，否那么为前往位置，

16、否那么为前往0。 low=1; high=ST.length; while ( lowkey，因此令highmid1low=1low=1high=7high=7mid=4mid=40 01 12 2keykey4 48 89 910101111131319193 34 45 56 67 7elemelemhigh=3high=3mid=2mid=2low=1low=1此时ST.elemmid.key8 key10 key，因此令，因此令highhighmidmid1 1high=7high=7mid=4mid=4low=1low=1low=1low=1high=3high=3mid=2mid=

17、2此时此时ST.elemmid.keyST.elemmid.key8 key8 key，因此令，因此令highhighmidmid1 1low=1low=1mid=1mid=1此时此时ST.elemmid.keyST.elemmid.key4 key4 highlow high查查找不胜利找不胜利第 22 页l折半查找的特点折半查找的特点l要求元素按关键字有序陈列。要求元素按关键字有序陈列。l存储构造：顺序。存储构造：顺序。l平均查找长度平均查找长度 ASLbs= log2(n+1)-19.1 9.1 静态查找表静态查找表- -有序表查找有序表查找第 23 页l查找表的组织：分块索引，除表本身

18、以外，尚查找表的组织：分块索引，除表本身以外，尚需建立一个需建立一个“索引表。索引表。l查找方法：查找索引表；在数据块内顺序查找查找方法：查找索引表；在数据块内顺序查找9.1 9.1 静态查找表静态查找表- -索引顺序表的查找不要求索引顺序表的查找不要求1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表块内最大值索引表块内最大值查查38第 24 页l查找方法比较查找方法比较9.1 9.1 静态查找表静态查找表ASL最大最大

19、最小最小两者之间两者之间表构造表构造有序表、无序表有序表、无序表有序表有序表分块有序表分块有序表存储构造存储构造顺序存储构造顺序存储构造线性链表线性链表顺序存储构造顺序存储构造顺序存储构造顺序存储构造线性链表线性链表顺序查找顺序查找折半查找折半查找分块查找分块查找第 25 页l动态查找动态查找: 在查找过程中对查找表进展修正在查找过程中对查找表进展修正l二叉排序树：或者是一棵空树；或二叉排序树：或者是一棵空树；或者是具有以下性质的二叉树：者是具有以下性质的二叉树：l 1假设左子树不空，那么左子树上一假设左子树不空，那么左子树上一切结点的值均小于根结点的值；切结点的值均小于根结点的值；l 2假设

20、右子树不空，那么右子树上一假设右子树不空，那么右子树上一切结点的值均大于根结点的值；切结点的值均大于根结点的值；l 3根结点的左、右子树也分别为二叉根结点的左、右子树也分别为二叉排序树。排序树。 9.2 9.2 动态查找表动态查找表Question：二叉排序树上能否：二叉排序树上能否存在值一样的结点？存在值一样的结点？第 26 页例：在二叉排序树中查找关键字为例：在二叉排序树中查找关键字为24的记录。的记录。9.2 9.2 动态查找表动态查找表 45 12 3 37 53 90 24 7898 61第 27 页例：在二叉排序树中查找关键字为例：在二叉排序树中查找关键字为60的记录。的记录。9.

21、2 9.2 动态查找表动态查找表 45 12 3 37 53 90 24 7898 61第 28 页l 二叉排序树的存储二叉排序树的存储ltypedef struct BiTNode l TElemType data;l struct BiTNode * lchild, * rchild;l BiTNode,*BTree; ltypedef struct l KeyType key;l l TElemType; l/数据元素类型可以是一个含有多个成数据元素类型可以是一个含有多个成员的构造或一条含有多个字段的记录员的构造或一条含有多个字段的记录9.2 9.2 动态查找表动态查找表Lchild d

22、ata rchildLchild data rchild key 第 29 页例：二叉排序树中插入结点例：二叉排序树中插入结点 40。9.2 9.2 动态查找表动态查找表 45 12 3 37 53 90 24 7898 6140f第 30 页二叉排序树的特点：是一种动态树表，树的构二叉排序树的特点：是一种动态树表，树的构造通常不是一次生成的，而是在查找过程中，造通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进当树中不存在关键字等于给定值的结点时再进展插入。展插入。9.2 9.2 动态查找表动态查找表新插入结点的特点：一定是一个新添加的叶子新插入结点的特点：一定是

23、一个新添加的叶子结点，并且是查找不胜利时查找途径上访问的结点，并且是查找不胜利时查找途径上访问的最后一个结点的左孩子或右孩子结点。最后一个结点的左孩子或右孩子结点。插入新结点的时机：当查找不胜利时。插入新结点的时机：当查找不胜利时。第 31 页l插入算法：插入算法：l 1执行查找算法，找出被插入结点的双执行查找算法，找出被插入结点的双亲结点；亲结点；l 2判别被插入结点是其双亲结点的左孩判别被插入结点是其双亲结点的左孩子结点还是右孩子结点，将被插入结点作为叶子结点还是右孩子结点，将被插入结点作为叶子结点插入；子结点插入；l 3假设二叉树为空，那么首先单独生成假设二叉树为空，那么首先单独生成根结

24、点。根结点。9.2 9.2 动态查找表动态查找表第 32 页例例1：插入值为：插入值为280的结点。的结点。9.2 9.2 动态查找表动态查找表1221222502503003001101109999T Tf f：NULLNULL1221222502503003001101109999f fT Tkey=280key=2801221222502503003001101109999f fT Tkey=280key=280f f1221222502503003001101109999T:NULLT:NULLkey=280key=280p p12212225025030030011011099992

25、80280第 33 页例例2：在一棵空树中，查找如下的关键字序列：在一棵空树中，查找如下的关键字序列9.2 9.2 动态查找表动态查找表454590902424121253534545242412125353454524244545242453534545 45 45，2424，5353，4545，1212，2424，90 90 生成的二叉排序树如下：生成的二叉排序树如下：对二叉排序树进展中序遍历可以得到有序序列对二叉排序树进展中序遍历可以得到有序序列第 34 页l思索题思索题1：l在下面的二叉排序树删除值为在下面的二叉排序树删除值为50、60的结的结点。点。第第9 9章章 查找查找80501

26、206011015055705380551201101505370Question：能否将：能否将70作为左子作为左子树的根结点来删除？树的根结点来删除？第 35 页l思索题思索题2：l二叉排序树删除二叉排序树删除10，5。第第9 9章章 查找查找10325813548325413第 36 页二叉树排序删除操作二叉树排序删除操作删除原那么：坚持二叉排序树的特性删除原那么：坚持二叉排序树的特性。设：二叉排序树上指向被删结点的指设：二叉排序树上指向被删结点的指针为针为p，指向其双亲结点的指针为，指向其双亲结点的指针为 f，且，且 p 为为 f 的左孩子结点。的左孩子结点。9.2 9.2 动态查找表

27、动态查找表 F F P PPRPRPLPLf fp p第 37 页l二叉排序树的删除操作二叉排序树的删除操作l要删除二叉排序树中的要删除二叉排序树中的p结点，分三种情结点，分三种情况：况：lp为叶子结点，只需修正为叶子结点，只需修正 p 双亲双亲 f 的指针：的指针：f-lchild=NULL f-rchild=NULLlp只需左子树或右子树只需左子树或右子树lp左、右子树均非空左、右子树均非空9.2 9.2 动态查找表动态查找表 F F P PPRPRPLPLf fp p第 38 页l二叉排序树的删除操作二叉排序树的删除操作l要删除二叉排序树中的要删除二叉排序树中的p结点，分三种情结点，分三

28、种情况：况：lp为叶子结点，只需修正为叶子结点，只需修正 p 双亲双亲 f 的指针：的指针：f-lchild=NULL f-rchild=NULL9.2 9.2 动态查找表动态查找表pf F P删除前删除前f F删除后删除后第 39 页l二叉排序树的删除操作二叉排序树的删除操作lp只需左子树或右子树只需左子树或右子树lp只需左子树，用只需左子树，用p的左孩子替代的左孩子替代p (1)(2)9.2 9.2 动态查找表动态查找表SQPLP中序遍历：中序遍历：Q S PL PSQPL中序遍历：中序遍历：Q S PL(2)SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL

29、S Q(1)第 40 页l二叉排序树的删除操作二叉排序树的删除操作lp只需左子树或右子树只需左子树或右子树lp只需右子树，用只需右子树，用p的右孩子替代的右孩子替代p (3)(4)9.2 9.2 动态查找表动态查找表中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Q(3)SPPRQ中序遍历：中序遍历：Q S P PRSQPR中序遍历：中序遍历：Q S PR(4)SQPRP第 41 页l二叉排序树的删除操作二叉排序树的删除操作lp左、右子树均非空左、右子树均非空l沿沿 p 左子树的根左子树的根 C 的右子的右子树分支找到树分支找到 S，S的右子树的右子树为空，用为空，用

30、 S 的左子树取代的左子树取代 S 的双亲的双亲Q 的右子树，再的右子树，再用用 S 取代取代 p (5)9.2 9.2 动态查找表动态查找表FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(5)第 42 页l二叉排序树的删除操作二叉排序树的删除操作lp左、右子树均非空左、右子树均非空l假设假设 C 无右子树，用无右子树，用 C 取代取代 p (6)9.2 9.2 动态查找表动态查找表FPCPRCL中序遍历：中序遍历：CL C P PR FFCPRCL中序遍历：中序遍历：C

31、L C PR F(6)第 43 页l二叉排序树的删除操作二叉排序树的删除操作l要删除二叉排序树中的要删除二叉排序树中的p结点，分三种情结点，分三种情况：况：lp为叶子结点，只需修正为叶子结点，只需修正 p 的双亲的双亲 f 的指的指针：针： f-lchild=NULL f-rchild=NULLlp只需左子树或右子树只需左子树或右子树lp只需左子树，用只需左子树，用p的左孩子替代的左孩子替代p (1)(2)lp只需右子树，用只需右子树，用p的右孩子替代的右孩子替代p (3)(4)lp左、右子树均非空左、右子树均非空l沿沿 p 左子树的根左子树的根 C 的右子树分支找到的右子树分支找到 S，S的

32、右子树为空，用的右子树为空，用 S 的左子树取代的左子树取代 S 的双亲的双亲Q 的右子树，再用的右子树，再用 S 取代取代 p (5)l假设假设 C 无右子树，用无右子树，用 C 取代取代 p (6)9.2 9.2 动态查找表动态查找表第 44 页l二叉排序树的删除操作二叉排序树的删除操作9.2 9.2 动态查找表动态查找表例例805012060110150557053删除删除508060120110150557053删除删除60805512011015053701052581376删除删除1085257136删除删除78525613第 45 页l性能分析性能分析l查找表：查找表：3,12,

33、24,37,45,53,61,78,90,989.2 9.2 动态查找表动态查找表 45 12 3 37 53 90 24 78 98 61ASL=(1+2+3+4+ASL=(1+2+3+4+5+6+7+8+9+15+6+7+8+9+10)/10=5.50)/10=5.5ASL=(1+2ASL=(1+22+32+34+44+43)/3)/1010 =2.9 =2.9 4512337539024789861单支树单支树第 46 页二叉排序树的特点之一缺陷：没二叉排序树的特点之一缺陷：没有对树的深度进展控制。有对树的深度进展控制。在构造二叉排序树的过程中进展在构造二叉排序树的过程中进展“平衡化平衡

34、化处置，此时的二叉排序树就成为平衡二处置，此时的二叉排序树就成为平衡二叉树叉树AVL树。树。平衡二叉树：它或者是一个空树，或者是平衡二叉树：它或者是一个空树，或者是具有以下性质的二叉树：其左、右子树具有以下性质的二叉树：其左、右子树都是平衡二叉树，且左子树和右子树的都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超越深度之差的绝对值不超越1。9.2 9.2 动态查找表动态查找表第 47 页l二叉排序树的特点二叉排序树的特点l含有含有n个结点的二叉排序树不独个结点的二叉排序树不独一，与结点插入的顺序有直接关系。当一，与结点插入的顺序有直接关系。当查找失败后，在叶子结点进展插入操作。查找失败后

35、，在叶子结点进展插入操作。l删除某个结点后，二叉排序树要删除某个结点后，二叉排序树要进展重组。进展重组。l没有对树的深度进展控制。没有对树的深度进展控制。l二叉排序树的适用范围二叉排序树的适用范围l用于组织规模较小的、内存中可用于组织规模较小的、内存中可以包容的数据。对于数据量较大且必需以包容的数据。对于数据量较大且必需存放在外存中的数据，无法实现快速处存放在外存中的数据，无法实现快速处置。置。9.2 9.2 动态查找表动态查找表第 48 页9.3 9.3 哈希表哈希表关键字关键字集合集合存储地址存储地址集合集合hash第 49 页9.3 9.3 哈希表哈希表 1 2 3 51 52年份年份人

36、数人数 1949 1950 1951 2019 2000 1949 1950 1951 2019 2000 2000 2100 2200 4400 4420 2000 2100 2200 4400 4420例例 某地域的人口统计表某地域的人口统计表H(年度年度=年度年度-1948第 50 页9.3 9.3 哈希表哈希表例例 30个地域的各民族人口统计表个地域的各民族人口统计表编号编号 地域地域 总人口总人口 汉族汉族 回族回族.1 北京北京2 上海上海.以编号作关键字，以编号作关键字，构造哈希函数：构造哈希函数：H(key)=keyH(1)=1H(2)=2以地域作关键字，取地域以地域作关键字，

37、取地域称号第一个拼音字母的序号称号第一个拼音字母的序号作哈希函数：作哈希函数：H()=2 H(Shanghai)=19 H(Shenyang)=19第 51 页9.3 9.3 哈希表哈希表第 52 页9.3 9.3 哈希表哈希表第 53 页9.3 9.3 哈希表哈希表直接定址法：取关键字或关键字的某个直接定址法：取关键字或关键字的某个线性函数值为哈希地址。线性函数值为哈希地址。数字分析法：取关键字的假设干数位组数字分析法：取关键字的假设干数位组成哈希地址。成哈希地址。 平方取中法：取关键字平方后的中间几平方取中法：取关键字平方后的中间几位为哈希地址。位为哈希地址。 折叠法：将关键字分割成位数一样的几折叠法：将关键字分割成位数一样的几部分，然后取这几部分的叠加和作为哈部分，然后取这几部分的叠加和