数据结构第8章 查找

《数据结构第8章 查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8章查找1本章主要内容基本概念线性表的查找树表查找哈希表查找8.1基本概念查找表关键字查找查找成功或查找不成功静态查找和动态查找查找效率和平均查找长度查找表定义查找表定义#definemaxsize100/*查找表最大长度*/typedefintKeyType；/*整型*/涉及的数据记录至少含有一个关键字段（域）：typedefstruct{KeyTypekey；………}DataType；typedefstruct{DataTyper[maxsize]；/*数据元素存储空间*/intlength；/*表的长度*/}Sqlist；

2、8.2线性表的查找常见的线性表查找算法顺序查找折半查找分块查找8.2.1顺序查找顺序查找改进算法：intSeqSearch(Sqlists,KeyTypek){/*在表s中顺序查找关键字k，若查找成功，则函数值为该元素在表中的位置，若查找失败，返回-1。*/inti；for(i=0；i

3、,KeyTypek){inti；i=s.length-1；s.r[-1].key=k；/*设置前哨站*/while(s.r[i].key!=k)/*从表尾开始向前扫描*/i--；return(i)；}请比较这两个算法,由于改进后的算法不需要判断当前下标是否出界,时间效率几乎提高了一倍.顺序查找的平均查找长度为i例-1012345678910513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+

4、18.2.2有序表的查找前提：表中的结点按关键字递增有序首先将待查值k和表中间位置上的结点关键字进行比较，若两者相等，则查找成功；否则，若k值小，则在表的前半部分中继续利用折半查找法查找，若k值大，则在表的后半部分中继续利用折半查找法查找这样，经过一次关键字比较缩小一半的查找区间，如此进行下去，直到查找到该关键字或查找失败。8.2.2折半查找算法intBinSearch(Sqlists,KeyTypek){/*在表s中用折半查找法查找关键字k，若查找成功，则函数值为该元素在表中的位置，若查找失败，返回-1。*/intlow,mid

5、,high；low=0；high=s.length-1；while(low<=high){mid=(low+high)/2；/*取区间中点*/if(s.r[mid].key==k)return(i)；/*查找成功*/elseif(s.r[mid].key>k)high=mid-1；/*在左区间中查找*/elselow=mid+1；/*在右区间中查找*/}return(-1)；/*查找失败*/}算法描述lowhighmid例1234567891011513192137566475808892找21123456789101151319

6、2137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid123456789101151319

7、2137566475808892lowhigh1185210741936判定树：1234567891011513192137566475808892ASL=(1*1+2*2+4*3+4*4)/11=38.2.2折半查找查找过程可用二叉树来描述(如图所示)折半查找的ASL近似8.2.3分块查找将关键字分块，块内可无序，但块间有序将每块的最大关键字值组成索引表，每个索引指向本块的第一个关键字索引表有序查381234567891011121314151617182212138920334244382448605874578653查找表2

8、248861713索引表关键码字段指针字段分块查找示例8.3树表查找静态查找:主要适用于顺序表结构，对表中的结点仅做查找操作。动态查找:要不断地插入和删除结点.当表采用顺序结构时，这需花费大量的时间用于结点的移动，效率很低。用树结构存储结点（即树表