《数据结构总复习》ppt课件

《《数据结构总复习》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查找￡9.1.1查找表￡9.1概述查找表（SearchTable）：是由同一类型的数据元素（或记录）构成的集合。对查找表经常进行的操作通常有：（1）查询某个“特定的”数据元素是否在查找表中；（2）检索某个“特定的”数据元素的各种属性；（3）在查找表中插入一个数据元素；（4）从查找表中删去某个数据元素。静态查找表（StaticSearchTable）：只对查找表作“查找”操作的一类查找表。动态查找表（DynamicSearchTable）：对查找表不仅作“查找”操作，在查找过程中还同时插入查找表中不存在的数据元素，或

2、者从查找表中删除已存在的某个数据元素的一类查找表。￡9.1.2相关术语关键字（Key）：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。主关键字（PrimaryKey）：可以唯一的标识一个建立的关键字。次关键字（SecondaryKey）：用以识别若干记录的关键字。查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。查找成功：查找表中存在关键字等于给定值的记录。此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置。查找失败：查找

3、表中不存在关键字等于给定值的记录。此时查找的结果可给出一个“空”记录或“空”指针。（2）查找操作的性能分析衡量查找算法好坏的依据：其关键字和给定值进行过比较的记录个数的平均值。平均查找长度（AverageSearchLength）：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于含有n个记录的表，查找成功时的平均查找长度为：（9－1）其中：Pi为查找表中查找第i个记录的概率，且；Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个

4、数。查找算法的平均查找长度＝查找成功时的平均查找长度＋查找不成功时的平均查找长度￡9.2.2顺序表的查找（1）顺序存储结构的类型定义typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按//实际长度分配，0号单元留空intlength;//表长度}SSTable（2）顺序查找的实现顺序查找（SequentialSearch）的查找过程为：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关

5、键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0。ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(ST.elem[i].key,key);――i);//从后往前找returni;//找不到时i为0}//Search_Seq算法9.1如下：i例01234567891011513192137566

6、475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1P217监视哨的作用（3）性能分析假设n＝ST.length，则顺序查找的平均长度为：ASL=nP1+(n－1)P2+…+2Pn-1+Pn①只考虑查找成功时的情况在顺序查找的过程中，式（9－1）中Ci取决于所查记录在表中的位置。假设查找每个记录的概率相等，即Pi＝1/n。则在等概率情况下顺序查找的平均查找长度为：②考虑查找成功和查找不成功时的情况顺序查

7、找中，不论给定值key为何值，查找不成功时和给定值进行比较的关键字个数均为n＋1。假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则Pi＝1/(2n)，此时顺序查找的平均查找长度为：缺点：平均查找长度较大，特别是当n很大时，查找效率较低。（4）顺序查找算法的特点优点：算法简单且适应面广。它对表的结构无任何要求，无论记录是否按关键字有序均可应用。￡9.2.3有序表的查找（1）有序表查找的实现折半查找（BinarySearch）的查找过程：先选定待查记录所在范围（区间），然后逐步缩小范围直到找到或找不到该记录为

8、止。特点:查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现:设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==r[mid].key，查找成