[工学]数据结构第17次课-查找C.ppt

《[工学]数据结构第17次课-查找C.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.上机实现顺序查找的改进算法。2.上机实现折半查找的递归及非递归算法。选做：3.设计一个算法，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性，上机实现。实验三1针对静态查找表的查找算法主要有：8.2静态查找表一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、静态树表的查找四、分块查找（索引顺序查找）上节课内容回顾2一、顺序查找（Linearsearch，又称线性查找）顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？挨个比较对单链表结构如何线性查找？函数虽未给出，但也很容

2、易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL＝(n+1)/2,ASL太大，时间效率太低。顺序查找的特点：3二、折半查找（又称二分查找或对分查找）先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。①low=1；high=length；//设置初始区间②当low>high时，返回查找失败信息//表空，查找失败③l

3、ow≤high，mid=(low+high)/2;//取中点a.若kxelem[mid].key，low=mid+1；转②//查找在右半区进行c.若kx=elem[mid].key，返回数据元素在表中位置//查找成功4四、分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子

4、表的起始地址（即头指针）。索引表最大关键字起始地址2212138920334244382448605874498653第1块第2块第3块224886例：2248861713特点：块间有序，块内无序5查找步骤分两步进行：①对索引表使用折半查找法（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找效率：ASL=Lb+Lw对索引表查找的ASL对块内查找的ASLS为每块内部的记录个数，n/s即块的数目例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为56ASL最大最小

5、两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表三种静态查找方法比较顺序查找折半查找分块查找小结：7针对动态查找表的查找算法主要有：8.3动态查找表一、二叉排序树（BST）二、平衡二叉树（AVL树）三、B-、B+树81、二叉排序树的定义回顾----或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。递归定义（4）其中序遍历序列为一个递增序列一.二叉排序树搜索92、二叉排序树的插入

6、与删除将数据元素构造成二叉排序树的优点：①查找过程与顺序结构有序表中的折半查找相似，查找效率高；②如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！——这种既查找又插入的过程称为动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。104524531290如果待查找的关键字序列输入顺序为：（24，53，45，45，12，24，90）2453451290查找成功，返回查找成功，返回讨论

7、1：二叉排序树的插入和查找操作则生成二叉排序树的过程为：例：输入待查找的关键字序列=（45，24，53，45，12，24，90）则生成的二叉排序树形态不同：查找成功返回查找成功返回11bstnodeBSTSEARCH(bstnodet,keytypek){bstnodep;p=t;while(p){if(p.key==k)returnp;if(p.key>k)p=p.lchild;elsep=p.rchild;}returnNULL;}1.二叉排序树的查找452453122890二叉排序树的查找&插入算法如何实现？122.二叉排序树的结

8、点插入452453122890a.若原树为空，返回以新插入结点为树根的树。b.否则，找到要插入的父结点。c.将新结点插入确定位置4747>45,向右子树搜索47<53,向左子树搜索53左子树为空，47应该插