数据结构 教学课件 ppt 作者 李学刚电子课件源代码 单元7 查找.ppt

《数据结构 教学课件 ppt 作者 李学刚电子课件源代码 单元7 查找.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构教学目标【知识目标】了解查找的基本概念掌握顺序查找的基本思想、算法实现和查找效率分析掌握二分查找的基本思想、算法实现和查找效率分析掌握分块查找的基本思想、算法实现和查找效率分析掌握二叉查找树的插入、删除、建树和查找算法及时间性能掌握哈希查找方法、哈希函数的构造和解决冲突的方法【能力目标】具有选择恰当的查询算法解决实际问题的能力引例描述——高校最低录取分数线查询该系统用于学生、学生家长和其他人员查询各高校的最低录取分数线，为他们的了解高校录取情况、做出正确的选择和决策提供有必要的信息。该系统有以下六项功能：（1）按考生

2、分数查询高校信息；（2）按给定分数查询一定范围内的高校信息，包括：查询录取分数线比给定分数高（包括相等）的高校信息和录取分数线比给定分数低（包括相等）的高校信息；（3）按给定的分数范围查询高校信息；（4）能够添加高校信息；（5）为用户提供系统帮助，以便更好的使用系统；（6）安全退出本系统。演示执行一、基本概念1．查找定义给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。2．动态查找表和静态查找表若在查找的同时对表做修改操

3、作（如插入和删除），则相应的表称之为动态查找表。否则称之为静态查找表。3．内查找和外查找若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。7.1查找的基本概念知识储备4．平均查找长度（AverageSearchLength）ASL查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL定义：即ASL等于每个结点的查找概率pi与比较次数ci的乘积的和。其中：（1）n是结点的个数；（2

4、）pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即pl=p2=…=pn=1/n；（3）ci是找到第i个结点所需进行的比较次数。一、顺序查找（sequentialsearch）顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链表。1．基本思想从表的一端开始，顺序扫描线性表，依次按给定值kx与关键字（Key）进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表查找完毕，仍未找到与kx相同的关键字，则查找失败，给出失败信息。2．基于顺序结构的顺序查找算法的类型描述

5、7.2静态查找#defineN20typedefintKeyType;//关键字字段类型定义typedefcharOtherdataType;//非关键字字段类型定义typedefstruct{KeyTypekey;OtherdataTypedata;}NodeType;typedefNodeTypeSeqList[N+1];//0号单元用作监视哨3．具体算法4．算法分析（1）算法中监视哨R[0]的作用为了在for循环中省去判定防止下标越界的条件i≥1，从而节省比较的时间。（2）成功时的顺序查找的平均查找长度在等概率情况下，

6、pi=1/n(1≤i≤n)，故成功的平均查找长度为(n+…+2+1)/n=(n+1)/2，即查找成功时的平均比较次数约为表长的一半，若K值不在表中，则须进行n+1次比较之后才能确定查找失败。（3）顺序查找的优缺点优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。intSeqSearch(SeqlistR,KeyTypeK){//在顺序表R[1...n]中查找关键字为K的结点inti;R[0].key=K;

7、//设置哨兵for(i=n;R[i].key!=K;i--);//从表后往前找returni;//若i为0，表示查找失败，否则R[i]是要找的结点}2二、二分查找（binarysearch）1．二分查找：二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。2．二分查找的基本思想设R[low...high]是当前的查找区间。（1）首先确定该区间的中点位置：mid=[(low+high)/2];（2）然后将待查的K值与R[

8、mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：①若R[mid].key>K，则由表的有序性可知R[mid…n].key均大于K，因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1…mid-1]中，故新的查