《数据结构》-静态查找表.ppt

￡￡￡￡￡￡￡￡￡￡￡￡￡-树和B+树￡￡￡￡￡ 查找￡￡{ 数据对象D:D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同,可唯一标识数据元素的关键字。 数据关系R:数据元素同属一个集合。 基本操作P: Create(&ST,n); 操作结果:构造一个含n个数据元素的静态查找表ST。 Destroy(&ST); 初始条件:静态查找表ST存在。操作结果:销毁表ST。 Search(ST,key); 初始条件:静态查找表ST存在,key为和关键字类型相同的给定值。操作结果:若ST中存在其关键字等于key的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。 Traverse(ST,Visit()); 初始条件:静态查找表ST存在,Visit是对元素操作的应用函数。操作结果:按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败,则操作失败。}ADTStaticSearchTable(1)静态查找表的抽象数据类型定义:(2)查找操作的性能分析衡量查找算法好坏的依据:其关键字和给定值进行过比较的记录个数的平均值。平均查找长度(AverageSearchLength):为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度。对于含有n个记录的表,查找成功时的平均查找长度为:(9-1)其中:Pi为查找表中查找第i个记录的概率,且;Ci为找到表中其关键字与给定值相等的第i个记录时,和给定值已进行过比较的关键字个数。查找算法的平均查找长度=查找成功时的平均查找长度+查找不成功时的平均查找长度静态查找表可以有不同的表示方法,在不同的表示方法中,实现查找操作的方法也不同。一、顺序查找表顺序查找是最基本,最简单的查找方法。其查找过程为:从表中第n个记录开始,逐个进行记录的关键字和给定值的比较。若某个关见键字与给定值像相等,则查找成功,找到所查找记录;反之,若直之第一个记录,其关键字与给定值不等,则表明表中没有所查记录,查找不成功。(1)顺序存储结构的类型定义typedefstruct{ ElemType*elem; //数据元素存储空间基址,建表时按//实际长度分配,0号单元留空 int length; //表长度 }SSTableintSearch_Seq(SSTableST,KeyTypekval){//在顺序表ST中顺序查找其关键字等于//key的数据元素。若找到,则函数值为//该元素在表中的位置,否则为0。[0].key=kval;//设置“哨兵”for(i=;--i);//从后往前找returni;//找不到时,i为0}//[i].key!=kval;(3)性能分析假设n=,则顺序查找的平均长度为: ASL=nP1+(n-1)P2+…+2Pn-1+Pn①只考虑查找成功时的情况在顺序查找的过程中,式(9-1)中Ci取决于所查记录在表中的位置。假设查找每个记录的概率相等,即Pi=1/n。则在等概率情况下顺序查找的平均查找长度为:(3)性能分析②考虑查找成功和查找不成功时的情况顺序查找中,不论给定值key为何值,查找不成功时和给定值进行比较的关键字个数均为n+1。假设查找成功与不成功的可能性相同,对每个记录的查找概率也相等,则Pi=1/(2n),此时顺序查找的平均查找长度为:缺点:平均查找长度较大,特别是当n很大时,查找效率较低。(4)顺序查找算法的特点优点:算法简单且适应面广。它对表的结构无任何要求,无论记录是否按关键字有序均可应用。上述顺序查找表的查找算法简单,但平均查找长度较大,特别不适用于表长较大的查找表。二、有序查找表若以有序表表示静态查找表,则查找过程可以基于“折半”进行。