《北京理工大学数据结构查找课件》由会员分享，可在线阅读，更多相关《北京理工大学数据结构查找课件（56页珍藏版）》请在金锄头文库上搜索。
1、 第9章 查 找l查找表：由同一类型的数据元素（或记录）构成的 集合。l查找表的基本操作 1) 查询某个“特定的”数据元素是否在表中 2) 检索某个“特定的”数据元素的各种属性 3) 插入一个数据元素 4) 删去某个数据元素l静态查找表：只作查询和检索操作的查找表。l动态查找表：在查找过程中同时作插入或删除操作 的查找表。2第9章 查 找l关键字：能标识一个数据元素（或记录）的数据项 。l主关键字：能唯一地标识一个记录的关键字。l次关键字：用以识别若干记录的关键字。学号 姓名 专业 年龄20090001 王洪 自动化 1720090002 李文 自动化 1820090003 谢军 自动化 18
2、20090004 张辉 信息工程 2020090005 李文 信息工程 193第9章 查 找l查找：根据给定的某个值，在查找表中确定一个其 关键字等于给定值的记录或数据元素，若表中存在 这样的记录，则称查找成功，查找结果为该记录在 查找表中的位置；否则称为查找不成功，查找结果 为0或NULL。学号 姓名 专业 年龄20090001 王洪 自动化 1720090002 李文 自动化 1820090003 谢军 自动化 1820090004 张辉 信息工程 2020090005 李文 信息工程 19 4第9章 查 找l查找方法评价l查找算法的基本操作：比较l平均查找长度ASL ( Average
3、Search Length)：为确 定记录在表中的位置，需和给定值进行比较的关键 字个数的期望值。l平均查找长度： ASL = PiCi l Pi：查找第 i 个记录的概率，且Pi=1 ；l Ci：查找第 i 个记录所需的比较次数。5第9章 查 找l关键字类型定义typedef float KeyType; 实型typedef int KeyType; 整型typedef char* KeyType; 字符串型l数据元素类型定义typedef struct KeyType key; 关键字域 其他域 ElemType;key 6第9章 查 找l对数值型关键字#define EQ(a,b) (a
4、) = = (b)#define LT(a,b) (a) key，令highmid1low=1high=7mid=4012key4891011131934567elemhigh=3mid=2low=1ST.elemmid.key8 key，令highmid1high=7mid=4low=1low=1high=3mid=2ST.elemmid.key8 key，令highmid1low=1mid=1ST.elemmid.key4 highlow high，查找不成功！查找不成功！521l折半查找的特点： 要求元素按关键字有序。 存储结构：顺序。 平均查找长度 ASLbs= log2(n+1)-1
5、9.1 静态查找表-有序表查找22l查找表的组织：分块索引，除表本身以外，尚 需建立一个“索引表”。l查找方法：查找索引表；在数据块内顺序查找9.1 静态查找表-索引顺序表的查找1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表（块内最大值） 查3823l查找方法比较9.1 静态查找表ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构 线性链表顺序存储结构顺序存储结构 线性链表顺序查找折半查找
6、分块查找24l二叉排序树：或者是一棵空树；或者是具有下列 性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均 小于根结点的值；（2）若右子树不空，则右子树上所有结点的值均 大于根结点的值；（3）根结点的左、右子树也分别为二叉排序树。 9.2 动态查找表25例：在二叉排序树中查找关键字为24的记录。9.2 动态查找表451233753 902478986126例：在二叉排序树中查找关键字为60的记录。9.2 动态查找表451233753 902478986127l二叉排序树的存储typedef struct BiTNode TElemType data;struct BiTNode *
7、lchild, * rchild; BiTNode,*BTree; typedef struct KeyType key; TElemType;9.2 动态查找表Lchild data rchildkey 28例：二叉排序树中插入结点 40。9.2 动态查找表451233753 902478986140f29l 二叉排序树的特点：是一种动态树表，树的 结构通常不是一次生成的，而是在查找过程中 ，当树中不存在关键字等于给定值的结点时再 进行插入。9.2 动态查找表l 新插入结点的特点：一定是一个新添加的叶 子结点，并且是查找不成功时查找路径上访问 的最后一个结点的左孩子或右孩子结点。l 插入新结
8、点的时机：当查找不成功时。30l插入算法：（1）执行查找算法，找出被插入结点的双亲结点；（2）判断被插入结点是其双亲结点的左孩子结点还 是右孩子结点，将被插入结点作为叶子结点插入；（3）若二叉树为空，则首先单独生成根结点。9.2 动态查找表31例1：插入值为280的结点。9.2 动态查找表12225030011099Tf：NULL 12225030011099fTkey=28012225030011099fTkey=280f12225030011099T:NULLkey=280p1222503001109928032例2：在一棵空树中，查找如下的关键字序列9.2 动态查找表4590241253
9、45241253452445245345 45，24，53，45，12，24，90 依次生成的二叉排序树如下：对二叉排序树进行中序遍历可以得到有序序列33l思考题1： 二叉排序树删除50，60。第9章 查找8050120601101505570538055120110150537034l思考题2： 二叉排序树删除10，5。第9章 查找1032581354832541335l二叉树排序删除操作 删除原则：保持二叉排序树的特性。 设：二叉排序树上指向被删结点的指针为p，指向其 双亲结点的指针为 f，且 p 为 f 的左孩子结点。9.2 动态查找表FPPRPLfp36l二叉排序树的删除操作要删除二叉
10、排序树中的p结点，分三种情况：l p为叶子结点，只需修改 p 双亲 f 的指针：f -lchild=NULL f-rchild=NULLl p只有左子树或右子树l p左、右子树均非空9.2 动态查找表FPPRPLfp37l二叉排序树的删除操作（一）lp为叶子结点：9.2 动态查找表pfFP删除前fF删除后l 只需修改 p 双亲 f 的指针： f-lchild=NULL f-rchild=NULL38l二叉排序树的删除操作（二）n p只有左子树：用p的左孩子代替p (1)(2)9.2 动态查找表SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P
11、S QSPLQ中序遍历：PL S Q(1)39l二叉排序树的删除操作（二）n p只有右子树：用p的右孩子代替p (3)(4)9.2 动态查找表中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP40l二叉排序树的删除操作（三）：p左、右子树均非空n沿 p 左子树的根 C 的右子树分支找到 S，S的右子 树为空，将 S 的左子树成为 S 的双亲Q 的右子树 ，用 S 取代 p (5)9.2 动态查找表FPCPRCLQQLSSL 中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL
12、中序遍历：CL C QL Q SL S PR F(5)41l二叉排序树的删除操作（三）：p左、右子树均非空n 若p 左子树的根 C 无右子树，用 C 取代 p (6)9.2 动态查找表FPCPRCL中序遍历：CL C P PR FFCPRCL中序遍历：CL C PR F(6) 42l二叉排序树的删除操作，分三种情况：n p为叶子结点，只需修改 p 双亲 f 的指针： f-lchild=NULL f-rchild=NULLn p只有左子树或右子树 p只有左子树，用p的左孩子代替p (1)(2) p只有右子树，用p的右孩子代替p (3)(4)n p左、右子树均非空 沿 p 左子树的根 C 的右子树
13、分支找到 S，S的右子树 为空，将 S 的左子树成为 S 的双亲Q 的右子树，用 S 取代 p (5) 若 C 无右子树，用 C 取代 p (6)9.2 动态查找表43l二叉排序树的删除操作9.2 动态查找表例805012060110150557053删除508060120110150557053删除60805512011015053701052581376删除1085257136删除7852561344l性能分析 查找表：3,12,24,37,45,53,61,78,90,989.2 动态查找表45123 37 53 9024 78 9861ASL=(1+2+3+4+5 +6+7+8+9+1
14、0 )/10=5.5ASL=(1+22+34+43)/10=2.9 4512337539024789861单支树45二叉排序树的特点之一（缺陷）：没有对 树的深度进行控制。l在构造二叉排序树的过程中进行“平衡化”处理 ，成为平衡二叉树（AVL树）。l平衡二叉树：左子树和右子树的深度之差的绝 对值不超过计划。9.2 动态查找表46l二叉排序树的特点 含有n个结点的二叉排序树不唯一，与结点插 入的顺序有直接关系。当查找失败后，在叶结点插 入。 删除某个结点后，二叉排序树要重组。 没有对树的深度进行控制。l二叉排序树的适用范围 用于组织规模较小的、内存中可以容纳的数据 。对于数据量较大必须存放在外存
15、中的数据，则无 法快速处理。9.2 动态查找表47l l散列法（哈希法）散列法（哈希法） 在记录的存储地址和它的关键字之间建立一个确 定的对应关系，一次存取就能得到所查元素的查找 方法。即：通过简单计算直接得到数据的地址。通过简单计算直接得到数据的地址。 1) 哈希(Hash)函数是一个映象，即：将关键字 的集合映射到某个地址集合上， 映象原则：地址集合的大小不超出允许范围。 哈希函数：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字。9.3 哈希表关键字 集合存储地址 集合hash48l l散列法（哈希法）散列法（哈希法） 2) 由于哈希函数是一个压缩映象，因此，在一般 情况下，很容易产生“冲突”现象， 即：key1 key2，而
