数据结构第9章查找new

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

1、数据结构第四十三讲第四十三讲第四十三讲第四十三讲顺序查找与折半查找主讲：刘立嘉主讲：刘立嘉1、查找的基本概念�查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素若表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。n�查找方法评价对含有n个记录的表，ASL=∑picii=1�查找速度n其中：pi为查找表中第i个元素的概率，∑pi=1�占用存储空间多少i=1c为找到表中第i个元

2、素所需比较次数i�算法本身复杂程度�平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~关键字——是数据元素中某个数据项的值，它可以标识一个数据元素若此关键字可以唯一的标识一个记录，则称此关键字为“主关键字”。若此关键字能识别若干记录，则称之“次关键字”。高考成绩表准考证号姓名各科成绩总分政治语文外语…主关..键字179325陈红858688259179326陆华787590243179327张平828080242Key=1

3、79326…Key=179238..查找表可分为两类查找表可分为两类::静态查找表仅作查询和检索操作的查找表。动态查找表有时在查询之后，还需要将““查询””结果为““不在查找表中””的数据元素插入到查找表中；或者，从查找表中删除其““查询””结果为““在查找表中””的数据元素。2、静态查找表ADTStaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同、可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST,n);Dest

4、roy(&ST);Search(ST,key);Traverse(ST,Visit());}ADTStaticSearchTable3、顺序表的查找：顺序查找以顺序表或线性链表表示静态查找表静态查找表的顺序存储结构typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时//按实际长度分配，0号单元留空intlength;//表的长度}SSTable;顺序查找的查找过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到

5、所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。顺序查找iiST.elem当i不为0时，查找成功6464213788199205645680751301234567891011key=64ST.Lengthi当i为0时，查找不成功iST.elem6060213788199205645680751301234567891011key=60ST.LengthintintSearch_Seq(SSTableSearch_Seq(SSTableST,ST,KeyType

6、KeyTypekey){key){//在顺序表ST中顺序查找其关键字等于//key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。ST.elem[0].key=key;ST.elem[0].key=key;////““哨兵””forfor((i=ST.length;!EQ(ST.elem[i].key,key);--i););////从后往前找returni;returni;////找不到时，ii为00}//}//Search_SeqSearch_Seq分析顺序查找的时间性能查找算法中的基本操作

7、是将记录的关键字和给定值进行比较，因此，常以““其关键字和给定值进行过比较的记录个数的平均值””作为衡量查找算法好坏的依据。定义：查找成功时的平均查找长度((AAverageverageSSearchearchLLength)ength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值nASL=∑PiCii=1其中::n为表长，Pi为查找表中第i个记录的概n率，且∑Pi=1，Ci为找到该记录时，曾和给定i=1值进行过比较的关键字个数。对顺序表而言，CCi=n-i+1=n-i+1ASL=nPAS

8、L=nP1+(n-1)P+(n-1)P2++……+2P+2Pn-1+P+Pn1在等概率查找的情况下，P=in顺序查找的平均查找长度为：n1n+1ASLss=∑(n−i+1)=ni=12�在不等概率查找的情况下，ASLss在Pn≥Pn-1≥···≥P2≥P1时取极小值�若查找概率预先无法测定，为提高查找概率，在每个记录中附设一个访问频度域，并使记录始终按访问频度非递减有序的次序排列，使得