VB教程03查找和排序ppt课件.ppt

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

1、查找查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字——是数据元素中某个数据项的值，它可以标识一个数据元素查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~1顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较算法描述i例01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元

2、素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1顺序查找方法的ASL2折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==r[mid].key，查找成功若kr[mid].key，则low=mid+1重复上述操作，直

3、至low>high时，查找失败算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid123456789101151319213756647

4、5808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh1185110742936判定树：1234567891011513192137566475808892算法评价判定树：描述查找过程的二叉树叫~有n个结点的判定树的深度为log2n+1折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度折半查找的ASL3分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块

5、内查找适用条件：分块有序表算法实现用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针算法描述Ch7_3.c12345678910111213141516171822121389203342443824486058745786532248861713索引表查38分块查找方法评价ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找4哈希查找基本思想：在记录的存储地址和它的关键字之间

6、建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法定义哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字关键字集合存储地址集合hash哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~例30个地区的各民族人口统计表编号地区别总人口

7、汉族回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫~同义词：具有相同函数值的两个关键字，叫该哈希函数的~哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量

8、减少；同时，冲突发生后，应该有处理冲突的方法哈希函数的构造方法直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·k