第11章查找与排序.

第十一章查找和排序本章内容查找•顺序查找•二分查找•二叉排序树查找•哈希查找•平均查找长度的计算排序直接插入排序直接选择排序冒泡排序查找的基本概念查找：在数据元素集合(查找表)中查找关键字与给定值相等的数据元素。关键字：数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。平均查找长度(ASL)：iniiCPASL1式中，n为查找表的长度；pi为查找第i个元素的概率，在等概率情况下pi等于1/n；Ci为找到第i个元素时的比较次数顺序查找要求：查找表必须采用线性表。基本思想：用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值相同，则查找成功；如果找遍全表也没有发现满足条件的元素，则查找失败。算法实现：顺序表类和单链表类中的search函数。实现一：顺序表类中实现顺序查找的成员函数//查找元素x并返回其下标，若元素不存在，则返回-1//被查找的数存放在一个数组中，从数组的第一个元素开始，依次往下比较，直到找到要找的元素为止。intSeqlist::Search(charx){inti=0;for(i=0;ilength;i++)if(element[i]==x)returni+1;return-1;}实现二：单链表类中实现顺序查找的成员函数//查找元素x并返回其地址，若元素不存在，则返回空Node*LinkedList::Search(intx){Node*p=head-next;while(p!=NULL){if(p-data==x)break;p=p-next;}returnp;}顺序查找的平均查找长度评价：在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况下进行查找。)(21111nOninCPASLniinii二分查找（折半查找）要求：•必须以顺序方式存储线性表•线性表中所有数据元素必须按照关键字有序排列基本思想：将给定值与处于顺序表“中间位置”上的元素的关键字进行比较，若相等则查找成功；若给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值。2.初始时，令low=0，high=n-1，mid=(low+high)/2让k与mid指向的记录比较若k==r[mid]，查找成功若kr[mid]，则high=mid-1若kr[mid]，则low=mid+13.重复上述操作，直至lowhigh时，查找失败。二分查找算法实现二分查找过程0Atlanta1Boston2Chicago3Denver4Detroit5Houston6LosAngeles7Miami8NewYork9Philadelphia10SanFrancisco11SeattleSeattle11SanFrancisco10Philadelphia9NewYork8Miami7LosAngeles6Houston5Detroit4Denver3Chicago2Boston1Atlanta0Seattle11SanFrancisco10Philadelphia9NewYork8Miami7LosAngeles6Houston5Detroit4Denver3Chicago2Boston1Atlanta0lowhighmid012345678910513192137566475808892找21例如key=21的查找过程low指示查找区间的下界high指示查找区间的上界mid=(low+high)/2lowhighmid513192137566475808892012345678910513192137566475808892lowhighmid012345678910例key=70的查找过程lowhighmid找70513192137566475808892lowhighmid513192137566475808892lowhighmid513192137566475808892lowhighmid012345678910012345678910012345678910012345678910513192137566475808892513192137566475808892lowhigh513192137566475808892当下界low大于上界high时，则说明表中没有关键字等于key的元素，查找不成功。012345678910012345678910例：二分查找函数模板及其测试程序#includeiostreamusingnamespacestd;templatetypenameTintBinSearch(TA[],intlow,inthigh,Tkey){intmid;while(low=high){mid=(low+high)/2;if(key==A[mid])returnmid;//查找成功，返回元素的下标if(keyA[mid])high=mid-1;//到表的前半部分查找?elselow=mid+1;//到表的后半部分查找}return-1;//查找失败，返回失败标志-1?}intmain(){inta[]={1,2,3,4,5,6,7,8},k=7,i;i=BinSearch(a,0,7,k);if(i==-1)例：用递归方法实现二分查找函数模板#includeiostreamusingnamespacestd;templatetypenameTintBinSearch(TA[],intlow,inthigh,Tkey){intmid;if(lowhigh)return-1;//查找失败，返回失败标志-1else{mid=(low+high)/2;if(key==A[mid])returnmid;//查找成功，返回元素的下标if(keyA[mid])BinSearch(A,low,mid-1,key);//到表的前半部分查找?elseBinSearch(A,mid+1,high,key);//到表的后半部分查找}}intmain(){inta[]={1,2,3,4,5,6,7,8},k=7,i;i=BinSearch(a,0,7,k);二分查找在二分查找中，比较的次数取决于所要查找的元素在数组中的位置。对于n个元素的数组，在最坏的情况下所要查找的元素必须查到查找区间只剩下一个元素时才能找到或者能确定该元素根本不在数组中。二分查找优缺点优点：•查找效率高•平均查找长度缺点：•查找前要将表中元素按关键字有序排列•只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。)(log1)1(log12122111nOnnnjnCPASLjkjinii搜索算法的效率顺序搜索的平均时间性能（1+2+3+…+n)/n=(n+1)/2二分查找的最坏情况的时间性能n/2/2…/2/2=1n=2k使用二分查找算法最多只需要k=log2n次比较即可K次)(nO)(log2nO平均查找长度：平均查找长度：N和log2N的值Nlog2N10310071000101,000,000201,000,000,00030二叉排序树查找将数据集合中的数据元素存储为一颗二叉排序树，然后按给定方法进行查找。二叉排序树的定义：二叉排序树或者是一棵空二叉树，或者是具有以下性质的二叉树：•若它的左子树非空，则左子树上所有结点的值均小于根结点的值；•若它的右子树非空，则右子树上所有结点的值均不小于根结点的值；•左、右子树本身又各是一棵二叉排序树。二叉排序树二叉排序树：一种特殊的二叉树，其特点是：左子树上所有结点的值均小于其双亲结点的值，右子树上所有结点的值均大于或等于其双亲结点的值。56894723152650308020901085403525238866不是二叉排序树。插入操作：若二叉排序树为空，则新结点为二叉排序树的根结点；否则将新结点的关键字值和根结点的关键字值进行比较，若小于根结点的值，则将新结点插入到左子树中去，否则，插入到右子树中去。此插入过程是递归进行的。设有整数序列{47,23,56,15,26,89},将其中的值依次插入二叉排序树568947231526152326475689中序遍历结果：对二叉排序树进行中序遍历可以得到一个数据元素由小到大的有序序列。构造二叉排序树的过程即为对无序序列进行排序的过程。删除操作：一个结点被删除后，必须保证余下的结点仍然构成一棵二叉排序树。下面分三种情况讨论：情况二：被删除的结点至少有一棵空子树，则用那棵非空子树的根成为其双亲结点的相应子女50302510153533375362605553625550301015353337情况一：若被删除的是叶结点，则将对应双亲结点指针域置空情况三：被删除的结点有两棵非空的子树方法一：找到被删除结点在中序遍历序列中的直接后继结点（它一定在被删除结点的右子树中），用此后继结点的值取代被删除结点的值，然后删除此后继结点，由于被删除的后继结点的左子树一定是空子树，所以删除后继结点的过程同情况二。方法二：用被删除结点在中序遍历序列中的直接前驱结点（该结点的右子树也一定为空）代替被删除的结点，然后删除这个前驱结点。50301015353337536255533010153533376255373010153533536255将结点50删除中序遍历结点序列：10153033353750535562用中序遍历该二叉树得到的直接后继结点代替该结点，删除直接后继结点用中序遍历该二叉树得到的直接前驱结点代替该结点，删除直接前驱结点查找操作：查找思路：当二叉排序树不为空时，将给定值与根结点的值进行比较，若相等则查找成功。如果给定值小于根结点的值，则在根结点的左子树中继续查找，否则在根结点的右子树中继续查找。当待查找的二叉排序树为空时，查找失败。平均查找长度：)(log2nOASL在二叉排序树中查找成功时走过的是一条从根结点到所寻找结点的一条路径，因此，二叉排序树查找的平均查找长度取决于二叉排序树的深度。在二叉排序树中查找关键字值等于50,35,90,955030802090854035883250505030403550508090)(log2nOASL平均查找长度：哈希查找UKT012...m-1哈希方法：使用函数将U映射到表T[0…m-1]的下标上哈希函数:h(关键值)元素存储地址所有可能出现的关键字集合U实际存储关键字集合K哈希表如果哈希函数是一一映射的，那么增、删、改、查的复杂度都是O(1)的。如果关键字的可能值太多，而数组长度是有限的，那么哈希函数就只能是多对一的，就会产生碰撞。哈希存储(哈希表)哈希存储(哈希表)：以数据元素的关键字k为自变量，通过一定的函数关系计算出对应的函数值h(k)，把这个值解释为数据元素的存储地址并把数据元素存储到相应的存储单元内（这个过程称为哈希）。h(k)称为哈希地址。例：设有一组关键字值{85,72,49,58,15,70,90,38}，哈希函数h(k)=kmod12。则对应的哈希地址为：{1,0,1,10,3,10,6,2}冲突：若有两个不同的关键字ki和kj，即ki≠kj（i≠j）。但h(ki)=h(kj)，这种情况称为冲突。ki与kj称为同义词。采用哈希技术要解决的两个主要问题：构造一个好的哈希函数，使出现冲突的机会尽可能少些；设计一个有效的解决冲突的办法哈希表碰撞的解决方法：•开放地址法：如果一个元素该在的位置已经有其他元素，就另安排一个空闲位置。•链地址法：映射到同一位置的元素被串成链表。解决冲突的方法：开放地址法和链地址法开放地址法：处理用数组存储哈希表时出现的冲突①发生冲突时按某种规则形成一个地址探