数据结构与算法分析(c++版)课件下ppt

《数据结构与算法分析(c++版)课件下ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法分析(C++版)课件下第8讲查找第9讲排序第10讲文件第11讲算法设计与分析第8章查找所谓查找，就是在数据集合中寻找满足某种条件的数据对象1.查找成功即找到满足条件的数据对象这时,作为结果,可报告该对象在结构中的位置,还可给出该对象中的具体信息2.查找不成功或查找失败。作为结果,应报告一些信息,如失败标志、位置等通常称用于查找的数据集合为查找结构，它是由同一数据类型的对象(或记录)组成在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的查找，查找结果

2、应是唯一的。但在实际应用时，查找条件是多方面的，可以使用基于属性的查找方法，但查找结果可能不唯一实施查找时有两种不同的环境静态环境查找结构不用插入和删除操作静态查找表动态环境为保持较高的查找效率,查找结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化动态查找表查找算法的评价指标查找成功:最少比较次数最多比较次数平均比较次数查找失败:最少比较次数最多比较次数平均比较次数以顺序表或线性链表表示静态查找表顺序查找elem顺序查找过程假设给定值e=64,要求ST.elem[k]=e,问:k=?k

3、ktemplateintSqSerach(ElemTypeelem[],intn,KeyTypekey)//操作结果:在顺序表中查找关键字的值等于key的记录,//如查找成功,则返回此记录的序号,否则返回-1{inti;//临时变量for(i=0;i

4、的查找表折半查找若以有序表表示静态查找表，则查找过程可以基于“折半”进行基于有序顺序表的折半查找设n个对象存放在一个有序顺序表中，并按其关键码从小到大排好了序折半查找时,先求位于查找区间正中的对象的下标mid，用其关键码与给定值x比较1.elem[mid]==x查找成功2.elem[mid]>x把查找区间缩小到表的前半部分，继续折半查找3.elem[mid]

5、lowhighmidlowmidhighmidmid=(low+high)/2Low指示查找区间的下界high指示查找区间的上界templateintBinSerach(ElemTypeelem[],intn,KeyTypekey)//操作结果:在有序表中查找其关键字的值等于key的记录,//如查找成功,则返回此记录的序号,否则返回-1{intlow=0,high=n-1;//查找区间初值while(low<=high){intmid=(low+hi

6、gh)/2;//查找区间中间位置if(key==elem[mid])returnmid;//查找成功elseif(key<=elem[mid])high=mid-1;//继续在左半区间进行查找elselow=mid+1;//继续在右半区间进行查找}return-1;//查找失败}二叉排序树（二叉查找树）（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值二叉排序树或者是一棵空树；或者是具有如下特性的二叉树（3）它的左、右子树也都分别是二叉排序树（2）若它的右子树不空，则右子树上所有结点的值均大于

7、根结点的值503080209010854035252388是二叉排序树66不二叉排序树的查找算法1）若给定值等于根结点的关键字，则查找成功2）若给定值小于根结点的关键字，则继续在左子树上进行查找3）若给定值大于根结点的关键字，则继续在右子树上进行查找否则:若二叉排序树为空，则查找不成功50308020908540358832查找关键字50505030403550508090==50,35,90,95n个结点的二叉查找树的数目3个结点的二叉查找树122133132123123{123}{132}{213}

8、{312}{321}如果对一棵二叉查找树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉查找树为二叉排序树在查找过程中，生成了一条查找路径从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点或者从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止——查找成功——查找不成功30201040352523fTkey=48fTfT22pfTfTTTTfffp3515455040251020