静态查找表动态查找表哈希查找表.ppt

《静态查找表动态查找表哈希查找表.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、1、静态查找表2、动态查找表3、哈希查找表查找查找查找在某种数据结构中找出满足条件的结点：找到查找成功找不到查找失败关键字（键）能唯一确定结点的一个或多个域平均查找长度查找一个结点所作的平均比较次数（衡量一个查找算法优劣的主要标准）顺序表的查找静态查找表算法思想：从表的一端开始，用给定值k与表中各个结点的键值逐个比较：查找成功---找出相等键盘值；查找失败---已到达表的另一端（可在此设置一个监视哨，作为下标越界的条件），即表中所有结点的键值都不等于k。………………012n-3n-2n-1nkey8100100713i………………012n-3n-2n-1ni

2、数组ST.elemkey查找key=8的结点所在的数组元素的下标。8100100713顺序表的查找………………key8100100713i顺序表的查找静态查找表监视哨的作用：作为越界（即已查完）的检测条件，省去在循环中每次均要判定是否越界，从而节省比较的时间。顺序表的查找结点类型定义：typedefstruct{intkey;/*关键字*/folatinfo;/*其它域*/}JD;intsearch(JDr[],intn,intk){inti=n;/*从表尾开始向前查找*/r[0].key=k;/*设置监视哨*/While(r[i].key!=k)i--;retur

3、n(i);}顺序表查找算法：性能分析：平均查找长度ASL（AverageSearchLength）成功查找情况下：设每个结点的查找概率相等一般查找情况下(包括成功、不成功两种情况)：设成功与不成功两种情况可能性相等，每个结点的查找概率也相等。顺序表的查找顺序表的查找顺序查找的特点：（1）算法简单，对线性表的逻辑次序无要求（即不必按关键字值不增或不减的次序排列）（2）存储结构可采用顺序或链式存储结构均可，但其平均查找长度较大(（n+1)/2)有序表的查找折半查找（或二分查找法）二分法的特点：（1）线性表的表中结点必须按关键字有序；（2）线性表须采用顺序存储结构。二分

4、法思想：（1）用给定的k与有序表的中间位置mid上的结点的关键字比较，若相等，查完（2）若r[mid].keyk)，则执行（3）（3）在右子表中继续进行二分查找。查找key=9的结点所在的数组元素的下标地址。数组ST.elem如下图所示有序数组ST.elem：递增序ST.elem[i].Key<=ST.elem[i+1].Key;i=1,2,…n-1查找范围：low（低下标）=1;high（高下标）=7（初始时为最大下标n）;比较对象：中点元素，其下标地址为mid=（low+high）/2=4489101

5、11319有序表的查找012mid=4但key=9<10,向左key4891011131934567high=7low=1有序表的查找查找key=9的结点所在的数组元素的下标地址。012mid=4key4891011131934567high=3（mid-1）low=1有序表的查找012mid=2key4891011131934567high=3（mid-1）low=1012mid=2;但key=9>8,向右key4891011131934567high=3（mid-1）low=1012mid=3;key4891011131934567high=3low=3查找ke

6、y=5的结点所在的数组元素的下标地址。数组ST.elem如下图所示有序数组ST.elem：递增序ST.elem[i].Key<=ST.elem[I+1].Key;i=1,2,…n-1查找范围：low（低下标）=1;high（高下标）=3;比较对象：中点元素，其下标地址为mid=(low+high)/2=2有序表的查找012mid=4key4891011131934567high=3low=1012mid=4key4891011131934567high=7low=1012mid=2key4891011131934567high=3low=1有序表的查找012mid=

7、2;但key=5<8,向左key4891011131934567high=1low=1012key4891011131934567high=3low=1012mid=2key4891011131934567high=1（mid-1）low=1有序表的查找mid=1,但key=5<4,向右失败条件：low>high;处于间隙中的键值导致这种情况！表示：typedefstruct{ElemType*elem;intlength;}//length=n有序表的查找inthalfsearch(JDr[],intn,intk){inti,j,mid;i=1,j=n;Whi