第11章查找与排序ppt课件.ppt

《第11章查找与排序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章查找和排序本章内容查找顺序查找二分查找二叉排序树查找哈希查找平均查找长度的计算排序直接插入排序直接选择排序冒泡排序查找的基本概念查找：在数据元素集合(查找表)中查找关键字与给定值相等的数据元素。关键字：数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。平均查找长度(ASL)：式中，n为查找表的长度；pi为查找第i个元素的概率，在等概率情况下pi等于1/n；Ci为找到第i个元素时的比较次数顺序查找要求：查找表必须采用线性表。基本思想：用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值相同，则查找成功；如果找遍全表也没有发现满足条件的元素，则查找失败。算

2、法实现：顺序表类和单链表类中的search函数。实现一：顺序表类中实现顺序查找的成员函数//查找元素x并返回其下标，若元素不存在，则返回-1//被查找的数存放在一个数组中，从数组的第一个元素开始，依次往下比较，直到找到要找的元素为止。intSeqlist::Search(charx){inti=0;for(i=0;ine

3、xt;while(p!=NULL){if(p->data==x)break;p=p->next;}returnp;}顺序查找的平均查找长度评价：在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况下进行查找。二分查找（折半查找）要求：必须以顺序方式存储线性表线性表中所有数据元素必须按照关键字有序排列基本思想：将给定值与处于顺序表“中间位置”上的元素的关键字进行比较，若相等则查找成功；若给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查找区为空

4、，此时查找失败。1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值。2.初始时，令low=0，high=n-1，mid=(low+high)/2让k与mid指向的记录比较若k==r[mid]，查找成功若kr[mid]，则low=mid+13.重复上述操作，直至low>high时，查找失败。二分查找算法实现二分查找过程0Atlanta1Boston2Chicago3Denver4Detroit5Houston6LosAngeles7Miami8NewYork9Philadelphia10S

5、anFrancisco11SeattleSeattle11SanFrancisco10Philadelphia9NewYork8Miami7LosAngeles6Houston5Detroit4Denver3Chicago2Boston1Atlanta0Seattle11SanFrancisco10Philadelphia9NewYork8Miami7LosAngeles6Houston5Detroit4Denver3Chicago2Boston1Atlanta0lowhighmid012345678910513192137566475808892找21例如key=21的查找过程low指示查找

6、区间的下界high指示查找区间的上界mid=(low+high)/2lowhighmid513192137566475808892012345678910513192137566475808892lowhighmid012345678910例key=70的查找过程lowhighmid找70513192137566475808892lowhighmid513192137566475808892lowhighmid513192137566475808892lowhighmid01234567891001234567891001234567891001234567891051319213756647

7、5808892513192137566475808892lowhigh513192137566475808892当下界low大于上界high时，则说明表中没有关键字等于key的元素，查找不成功。012345678910012345678910例：二分查找函数模板及其测试程序例：用递归方法实现二分查找函数模板二分查找在二分查找中，比较的次数取决于所要查找的元素在数组中的位置。对于n个元素的数组，在最