数据结构与算法-东北林业大学 数据结构演示文稿9[1].ppt

《数据结构与算法-东北林业大学 数据结构演示文稿9[1].ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查找基本概念静态查找表动态查找表哈希表基本概念1.查找表：同类数据元素（或记录）构成的集合。查找表是一种非常灵便的数据结构。2.静态查找表：在表中只进行查找元素（或记录）的存在性或查阅元素（或记录）的各种属性等不会改变表状态的操作。3.动态查找表：在查找过程中要对表进行插入元素（记录）或删除元素（记录）等导致查找表状态改变的操作。4.关键字：标识一个数据元素的某个数据项的值。若唯一标识一个数据元素，称为主关键字(对不同的数据元素其主关键字均不同)；反之称为次关键字(仅用来识别某个数据元素)。5.

2、查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。若表中存在这样的数据元素，则返回这个元素的位置（或给出该元素）,此时称查找成功；否则，返回一个“空”，称查找不成功。＊由于结构的不同及数据元素在结构中位置不同，查找的方法也不完全相同。§9.1静态查找表一、静态搜索概述1、搜索——按给定值，在数据集合寻找与给定值相等的数据对象。2、静态——指一种搜索的环境（结构），其执行插入和删除的前后结构不发生变化。3、静态搜索表——基于数组的静态搜索结构。4、方法——顺序搜索和折半搜索。5、平

3、均搜索长度ASL——搜索的时间效率标准即搜索过程中给定值与数据集合中对象的关键字的平均比较次数。基本操作：Creat(ST,n),Search(ST,K),Traverse(ST)9.1.1顺序表的查找typedefstruct{ElemType*elem;intlength;}SSTable;1.顺序查找intseqsrch_Seq(SSTableST,KeyTypekey){key为给定值，返回关键字等于key的记录在表r中的序号i,如果查找不成功则返回0}ST.elem[0]=key;i=ST.

4、length;while(ST.elem[i]!=key)i--;return(i);};//seqsrch012…n（K）ir

5、Element[i]=x，结束，返回i=4，成功Element[i]=x，结束，返回i=0，失败ii1、方法x=70监视哨640123456783351702807461570Elementx=20640123456783351702807461520Element监视哨查找操作的性能分析定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算

6、法在查找成功时的平均查找长度（ASL）。ASL=∑PiCi(1≤i≤n)Pi为查找表中第I个记录的概率，且∑Pi=1；Ci为和给定值已进行过比较的关键字个数。则等概率情况下：Pi=1/n∴ASL=∑PiCi=1/n*(n+n-1+n-2+…+1)=(n+1)/29.1.2基于有序表的折半搜索1、方法2、基本算法m=(l+h)/2；若Element[m]x则h=m–1；（左缩搜索区）lmhm=4ml6mh5x=18040123456780710

7、1518253643–2Elementl<=h成功！lmhm=4mh1ml2hl>h失败！x=050401234567807101518253643–2Element＊r[1..n]中存储n个记录，且r[i+1].key>r[i].kdy,i=1,2,…,n-1用折半查找方法在11个元素(只含关键字)构成的有序表中查找关键字21的过程示意图1234567891011r513192137566475808892(1)(2)(3):low:mid:higr[mid].key=K表明

8、查找成功用折半查找方法在11个元素(只含关键字)构成的有序表中查找关键字85的过程示意图1234567891011r513192137566475808892(1)(2)(3)(4):low:mid:highigST

9、.elem[mid]:low=mid+1;caseKey==ST.elem[mid]:returnmid;caseKey