软件技术基础第03章查找

《软件技术基础第03章查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、思考问题数据存放在计算机中如何查找？查找方法有所不同吗？不同方法的查找效率有区别吗？基本的查找方式有几种？1教学目标了解有关查找的基本概念查找的主要算法2教学要求通过本单元的学习，了解、掌握有关查找的：基本概念查找、平均查找长度主要查找算法顺序查找、折半查找、分块查找哈希查找3本单元涉及的内容第3章3.1基本的查找技术3.2哈希表技术4一、基本概念查找查找表静态查找动态查找平均查找长度5查找查找就是在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则，查找失败。查找表是一组待查数据元素的集合。静态查找是仅仅进行查询和检索操作，不改变

2、查找表中数据元素间的逻辑关系的查找。动态查找是除了进行查询和检索操作外，还对查找表进行插入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑关系。6平均查找长度平均查找长度（ASL-AverageSearchLength）在查找过程中，对每个结点记录中的关键字要进行反复比较，以确定其位置。因此，与关键字进行比较的平均次数，就成为平均查找长度。它是用来评价一个算法好坏的一个依据。对含有n个数据元素的查找表，查找成功时的平均查找长度为：ASL=Pi*Cini=1Pi=1i=1n其中：Pi为查找表中第i个数据元素的概率，且Ci为查找到第i个数据元素

3、时需进行比较的次数。显然，Ci随查找过程及DS的不同而各异。7基本的查找技术顺序查找折半查找分块查找81.顺序查找算法思想：最古老的算法。从第1个元素到最后1个元素，逐个进行比较。查找表的存储结构既适用于顺序存储结构也适用于链式存储结构算法描述算法讨论9算法描述查找操作步骤：step1从第1个元素开始查找；step2用待查关键字值与各结点（记录）的关键字值逐个进行比较；若找到相等的结点，则查找成功；否则，查找失败。10顺序查找算法seq_search(int*item,n,key){inti=0;while(i

4、;/*查找key的循环*/if(item[i]==key){printf(“查找成功!”);return(i);}else{printf(“查找失败!”);return(-1);}}11顺序查找算法（改进算法）seq_search_adv(int*item,n,key){inti=0;item[n]=key;/*设置哨兵*/while(item[i]!=key)i++;/*查找key*/if(i

5、(-1);}}注:设置哨兵目的在于免去查找过程中每一步都要检测整个表是否查完顺序查找算法中,执行频率最高的是while语句,改进后,可以节省近一半的时间12顺序查找算法主程序#include“stdio.h”#definen7main()｛intkey,loc=0;inta[10]={43,15,21,37,2,5,82};printf(“Inputkey:”);scanf(“%d”,&key);loc=s_search_adv(a,n,key);if(loc>0)printf(“loc=%d,key=%d”,loc,key);}13算法讨论平均

6、查找长度ASL在等概率的情况下平均查找长度ASL在等概率的情况下优点:对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可）无要求；当序列中的记录“基本有序”或N值较小时，是较好的算法；缺点：ASL较长讨论：能否减少比较次数，以提高效率。例如，……二分法等142.折半查找算法思想：将有序数列的中点设置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。即通过一次比较，将查找区间缩小一半。二分查找的先决条件是查找表中的数据元素必须有序。15算法描述算法步骤：step1首先确定整个查找区间的中间位置，mid=（lef

7、t+right）/2step2用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。对确定的缩小区域再按二分公式，重复上述步骤；最后，得到结果：要么，查找成功，要么，查找失败。存储结构用一维数组存放。16折半查找算法举例对给定数列（有序）{3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。leftrightmidleftrightmid第1次：{3，5，11，17，21，23，28，30，32，50}第二次：{2

8、3，28，30，32，50}mid1=（1+10）/2=5mid2=（6+10）/2=817折半查找算法bi