第2章 常用数据结构及其运算3(查找和排序)ppt课件.ppt

《第2章 常用数据结构及其运算3(查找和排序)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、概述图查找排序2.62.82.7本章主要内容查找2.12.22.32.42.5树与二叉树数组栈与队线性表2.7查找（Searching）静态查找表（线性查找、对分查找、分块查找）动态查找表（二叉排序树）哈希表查找表本节主要内容：一、基本概念查找表：用于查找的数据元素的集合称为查找表。查找表由同一类型的数据元素（或记录）构成。2.7查找查找表的操作:(1)查询某个“特定的”数据元素是否在查找表中;(2)检索某个“特定的”数据元素的各种属性;(3)在查找表中插入一个数据元素;(4)从查找表中删除某个数据元素.静态查找表:对查找表只作(1)、(2)操作；动态查找表：可以对查找表作(1

2、)-(4)操作。关键字：是数据元素（或记录）中的某个数据项的值，用以标识一个数据元素(或记录)。例如：银行帐户中的帐号是。2.7查找查找：根据给定的值,在查找表中确定一个关键字等于给定值的记录或数据元素的过程。2.7查找平均查找长度(averagesearchlength，ASL)：衡量查找算法的优劣标准。对于一个含有n个元素的查找表,查找成功时的平均查找长度可表示为：Pi为查找第i个元素的概率一般认为查找每个元素的概率相等，Pi=1/n.ci为查找第i个元素所经历的比较次数。2.7查找1、线性查找将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用给定的值与查找表中数据

3、元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。二、静态查找表2.7查找/*线性查找：在表r中查找关键字值为k的元素*/intseqsearch(noder[n+1],elemtypek){r[0].key=k;inti=n;/*从表尾开始向前扫描*/while(r[i].key!=k)i--;returni;}线性查找法最多查找次数为n+1,最少查找次数为1,平均查找次数为(n+1)/2,时间复杂度为O(n)。2.7查找如果查找表中各记录是按关键字有

4、序排列的,可以先用表的中间位置上记录的关键字与给定值K比较,若相等,则查找成功;否则,根据比较的结果确定下一步在表的前半部或后半部中继续查找。2、对分查找123mid=4key例:在顺序表中查找key=55的数组元素。mid=┗(low+high)/2┛1317424655709445678high=8low=55mid=6low=142<55查找成功2.7查找对分法查找只适用于顺序存储的有序表,其最大查找次数为log2n,最小查找次数为1,平均查找次数当n>50时约为：log2(n+1)-1,时间复杂度为O(log2n)。2.7查找//对分法查找Intbinsearch(st

5、ructnoder[n+1],elementk){int　low=1,　high=n;while　(low<=high){int　mid=(low+high)/2;/*取区间中点*/if(r[mid].key==k)returnmid;/*查找成功*/else　if(r[mid].key>k)high=mid-1;/*在左子区间中查找*/else　low=mid+1;/*在右子区间中查找*/}return　0;/*查找失败*/}又称索引顺序查找。性能介于顺序查找和对分查找之间。适用于顺序表，也适用于线性链表。分块查找要求查找表“分块有序”，即把查找表分成若干个块,每个块中关键字

6、不一定有序，但是前一个块中的最大关键字必须小于后一块中最小关键字。3、分块查找2.7查找2.7查找2.7查找三、动态查找表对二叉排序树进行中序遍历可以得到一个关键字有序序列。二叉排序树本身可以看作是一个有序结构，插入和删除操作不需要移动元素。12225030011020099105230216动态查找表的特点：表本身是在查找的过程中动态生成的。以上讲的静态查找表的三种查找中，对分查找效率最高，根本原因是查找表的数据元素有序排列，但是需要顺序存储，对于动态查找表来讲这种结构意味着要频繁地移动数据元素，为了解决这个问题，我们想到了二叉排序树（二叉查找树）。2.7查找二叉排序树的建立

7、过程就是动态查找。查找：用给定值k与根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。12225030011020099105230216查找步骤：12225030011020099105230216若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字值，查其右子树。在左右子树上做以上操作。2.7查找1.哈希表前面介绍的静