《计算机软件技术基础 教学课件 ppt 作者 牟艳 陈慧萍 第6章 查找和排序》由会员分享，可在线阅读，更多相关《计算机软件技术基础 教学课件 ppt 作者 牟艳 陈慧萍 第6章 查找和排序（75页珍藏版）》请在金锄头文库上搜索。
1、第六章 查找和排序,本章基本内容与要求,基本内容 顺序查找、二分查找、二叉树查找以及散列表上查找 及算法思想 排序的基本概念以及选择、插入、交换和归并四类排序的基本思想和算法 要求 掌握线性表、树和散列表(或称哈希表)的查找方法及算法实现以及各种查找方法的应用 熟练掌握选择、插入、交换和归并四类排序的基本思想和算法,本节重点： 顺序查找、二分查找、二叉树查找以及散列表上查找的基本思想和算法实现,第一节 查找,1动态查找和静态查找 查找的同时对表做修改操作(如插入或删除)的表称之为动态查找表，否则称之为静态查找表。,2. 平均查找长度 衡量一个查找算法优劣的标准是在查找过程中对关键字需要执行的平
2、均比较次数(即平均查找长度ASL)。将查找算法进行的关键字的比较次数的数学期望值定义为平均查找长度 ,计算公式为：,ASL=,其中：n：问题规模，查找集合中的记录个数； pi：查找第i个记录的概率； ci：查找第i个记录所需的关键字的比较次数。,一、 查找的基本概念,1顺序查找 基本思想 从线性表的一端向另一端逐个将关键字与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键字，则查找失败，给出失败信息。,顺序查找方法可用链式存储结构和顺序存储结构实现。,线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找。,二、线性表的查找,在顺序存
3、储结构的顺序查找算法中所设的哨兵(监视哨)是为了简化循环的边界条件而引入的附加结点(元素)，其作用是使循环中省去判定防止下标越界的条件从而节省了比较的时间。,以顺序存储结构为例，设数据元素存放在数组中下标从1到n的记录中，0号记录位置留作监视哨，从下标为n的一端开始向另一端检索，顺序检索算法可描述如下： int seqsearch(sqlist R,keytype k) int i=n; R0.key=k; /设置R0为监视哨 while(Ri.key != k) i-; return i; /返回检索结果i ,在等概率情况下，查找成功时，其平均查找长度约为表长的一半即(n+1)/2。查找失败
4、的话，其平均查找长度为n+1。,2二分查找(又称折半查找) 二分查找的算法思想是在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,二分查找的递归算法如下： int BinSearch (SeqList R,int low, int hight,RecType k) int mid=(low+hight)/2; if(lowk)return BinSearch(R,low,mid-1
5、,k); else return BinSearch(R,mid+1,hight,k); else return 0; ,例如：已知一个含15个记录的有序表，其关键字序列如下： （07 10 14 18 21 23 25 29 31 35 38 42 46 49 52）,用low和high分别表示检索区间的下界和上界；用mid指示中间位置，即mid=(low +high)/2；检索开始时low=1，high=n；即检索区间为1，n。,检索k=18的过程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 5 low=1 mid=8 high=15,检索开始时，
6、low=1，high=15，mid=(1+15)/2=8。由于k=18R8.key=29，所以应在左半区继续检索。此时，high=mid-1=8-1=7，mid=(1+7)/2=4，即：,07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=4 high=7 由于k=18=R4.key，此时检索18成功。,例如：已知一个含15个记录的有序表，其关键字序列如下： （07 10 14 18 21 23 25 29 31 35 38 42 46 49 52）,用low和high分别表示检索区间的下界和上界；用mid指示中间位置，即mid=(lo
7、w +high)/2；检索开始时low=1，high=n；即检索区间为1，n。,检索46的过程： 07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=1 mid=8 high=15 由于k=4629=R8.key，所以应在右半区继续检索；此时low=mid+1=8+1=9，mid= (9+15)/2=12，即：,07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=9 mid=12 high=15 由于k=4642=R14.key，所以应在当前区间的右半区继续检索； 此时low=12+1 =13，mid=
8、(13+15)/2=14，即：,07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=13mid=14high=15,由于k=4649=R14.key，所以应在当前区间的左半区继续检索；此时high=mid-1= 14-1=13，mid=(13+13)/2=13，即：,07 10 14 18 21 23 25 29 31 35 38 42 46 49 52 low=13 mid=13 high=13 由于k=46=R13.key，此时检索46成功。,二分查找在等概率的情况下查找成功的平均查找长度ASL为log2(n+1)-1,在查找失败时所需比较的关
9、键字个数不超过判定树的深度，最坏情况下查找成功的比较次数也不超过判定树的深度log2(n+1) (不小于log2(n+1)的最小整数) 二分查找只适用于顺序存储结构而不能用链式存储结构实现,3分块查找(又称索引顺序查找),分块查找的基本思想是将原表分成若干块，各块内部不一定有序，但第i块内所有记录的关键字都小于第i+1块内所有记录的关键字，这样的表叫做“分块有序”。抽取各块中的最大关键字及其起始位置建立索引表，因为原表是“分块有序”的，所以索引必定有序，参见图,4三种查找方法的比较, 若二叉检索树为空，检索失败，返回特定值NULL； 若二叉检索树非空，用给定值k与根结点的关键字值比较： 1）相
10、等时，检索成功，返回指向当前根结点的指针； 2）k小时，继续在根的左子树中检索，即转； 3）k大时，继续在根的右子树中检索，即转。,以树做为表的组织形式有一个好处，就是可以实现对动态查找表进行高效率的查找。我们在前面讲到了二叉排序树，如果把检索表中各记录按关键字值大小组织为二叉排序树，则检索关键字值等于给定值k的记录的过程为：,三、树的查找,哈希（Hash）技术又称为散列技术，其基本思想是在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 。,1. 哈希检索与哈希表,例:对于一组关键字序列（25，74，36，15，40，29，82，19
11、，65，33，57，47，50），选取函数h(key)key%13建立记录与其在检索表中存储位置之间的关系，可得到如下表6-2所示的一张检索表：,四、哈希技术,将关键字映射为检索表中适当存储位置的函数h(key)称作哈希函数，也称作散列函数或杂凑函数； 利用哈希函数来实现从记录的关键字值到该记录在检索表中存储位置地址的计算，哈希函数h(key)的值称作哈希地址，也称作散列地址或杂凑地址； 把利用哈希函数h(key)组织检索表并利用h(key)进行检索的这种方法称作哈希方法，也称作散列法或杂凑法； 采用哈希技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为哈希表。 对于n个记录的关键字
12、集合，我们总能找到其关键字值与存储地址之间的一对一函数。若最大关键字值为m，可以分配m个记录空间组织哈希表，选取哈希函数h(key)key即可。然而，这样会造成存储空间的大量浪费，甚至不可能分配有这么大的存储空间。 对于两个不同关键字key1key2，有h(key1)h(key2)，即两个不同的记录需要存放在同一个存储位置的现象。则key1和key2相对于h称做同义词。因而经过哈希函数h(key)变换后，可能会将不同的关键字值映射到同一个哈希地址上，我们称这种现象为地址冲突,在一般情况下，地址冲突是不可避免的，只能通过选取合适的哈希函数尽可能地减少这种冲突现象，而不可能做到完全避免这种冲突现象
13、，所以哈希检索技术中必须解决如下两个问题： 如何选择一个计算简单且地址冲突尽可能少的哈希函数； 在出现地址冲突时采用怎样的办法来消解冲突。,2哈希函数的构造方法,哈希函数是记录的关键字和它的存储位置之间的对应关系函数。若对于关键字值集合中的任何一个关键字，经哈希函数映射到哈希表中任何一个地址的概率相等（即得到一个随机地址），这组关键字的哈希地址就会均匀地分布在哈希表中整个地址区间中从而减少地址冲突。,构造哈希函数的一般原则是，哈希函数的运算尽可能地简单，哈希函数的值在表长范围内，并且尽可能使不同的关键字值有不同的哈希函数值（即尽可能地减少地址冲突）。常见的哈希函数构造方法有如下七种： a 直接
14、定址法 d 折叠法 b 数字分析法 e 除留余数法 c 平方取中法 f 乘余取整法 g 随机数法,(1) 直接定址法 直接定址法是取关键字的某个线性函数值为哈希地址，即： h(key)=akey+b (其中a和b为常数),例如，对于一个各年龄（如1到110岁）人口统计表，年龄作为关键字，哈希函数可取自身即h(key)=key，又如对于一个解放后各年份出生的人口统计表，年份作为关键字，哈希函数可取为h(key)=key-1948，等等。,(2) 数字分析法 数字分析法是根据关键字在各个位上的分布情况，选取分布比较均匀的若干位组成哈希地址。例如对于一个班的学生记录，其关键字为学号，学号的前面几位为
15、学校编号、年份、院系编号和专业编号等，而最后两位或三位是学生编号分布较均匀，因此可选后两位或三位作为哈希地址。,3. 处理冲突的方法 常用的地址冲突的消解策略有两类，一类是开放定址法；另一类是拉链法。 （1）开放定址法 开放定址法就是把哈希表中的空位置向处理地址冲突开放。具体做法是，当发生地址冲突时，从发生地址冲突的那个位置开始，使用某种方法在哈希表中形成一个探查序列，沿此序列逐个位置查看，直到找到一个空闲的位置把发生地址冲突时的待插入记录存入其中。 产生探查序列的常用方法有线性探查法，平方探查法和随机探查法等。,1）线性探查法 线性探查法是开放定址法消解地址冲突的一种最简单的探查方法。它把表长为m的哈希表看作是环形表，若发生地址冲突的位置地址为d，则依次探查d+1、d+2、m-1，直到找到一个空闲位置为止。其开放定址公式为： di=(h(key)+i)% m i=1,2,m-1 其中di为第i次冲突时的哈希地址, i是第i 次探查冲突时的地址增量。 例如:一组关键字为（19,14,23,1,68,20,84,28,55,11,10,79），哈希函
