资源描述：
《数据结构第九章 查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第9章查找查找(Search)的概念算法与数据结构查找的概念所谓查找，就是在数据集合中寻找满足某种条件顺序查找的数据元素。查找的结果通常有两种可能：折半查找第9章查找查找成功，即找到满足条件的数据元素。这静态树表的查找时，作为结果,可报告该元素在结构中的位置,还可给出该元素中的具体信息。二叉排序树和平衡二叉树查找不成功，或查找失败。作为结果,应报告索引结构与B树一些信息，如失败标志、位置等。散列法通常称用于查找的数据集合为查找结构，它是由同一数据类型的元素（或记录）组成。Copyright@2013-HECopyright@2013-HE静态查找表结构的定义顺序
2、查找(SequentialSearch)在每个元素中有若干属性，其中有一个属性，其值可唯一地标识这个元素。称为关键字（key）。#definemaxSize100//查找表最大尺寸所谓顺序查找,又称线性查找,主要用于在线性结使用基于关键字的查找，查找结果应是唯一的。typedefintElemType;//查找数据的类型构中进行查找。但在实际应用时，查找条件是多方面的，可以使typedefstruct{//查找表结点定义设若表中有n个元素，则顺序查找从表的先端用基于属性的查找方法，但查找结果可能不唯一。ElemTypekey;//关键字域（或后端）开始，依次用各元素
3、的关键字与给定衡量一个查找算法的时间效率的标准是：在查找过程other;//其他数据信息值x进行比较，直到找到与其值相等的元素，则查中关键字的平均比较次数，也称为平均查找长度}ListNode;找成功；给出该元素在表中的位置。ASL(AverageSearchLength)，通常它是查找结构中typedefstructdataList{//查找表结点定义若整个表都已检测完仍未找到关键字与x相等的元元素总数n的函数。ListNodedata[maxSize];//数据存储数组素,则查找失败。给出失败信息。静态查找常基于线性表，动态查找常基于树或字典。intn;//数组
4、当前长度}Copyright@2013-HECopyright@2013-HECopyright@2013-HE设置“监视哨”的顺序查找算法算法分析设查找概率相等，即pi=1/n,i=1,2,,n。则intLinearSearch(dataList&L,ElemTypex){设查找第i个元素的概率为pi，查找到第i个元素查找成功的平均查找长度为：//在数据表L.data[0]..L.data[n-1]中顺序查找关键字n-111n(n1)n1所需比较次数为ci，则查找成功的平均查找长度//值与给定值x相等的数据元素,L.data[n].key作为ASLsucc
5、(i1).为:i0nn22//控制搜索自动结束的“监视哨”使用n-1n-1ASLpc.(p1)而查找不成功时，一定把表中所有元素检测了一L.data[L.n].key=x;inti=0;succiiii0i0遍，一直到监视哨。所以查找不成功的平均查找//将x送表尾的下一个位置设置监视哨长度为：ASLunsucc=n+1。while(L.data[i].key!=x)i++;在顺序查找并设置“监视哨”情形，ci=i+1,i=0,1,,n-1，因此顺序查找可以用递归方法实现。当查找表中第一//从前向后顺序查找n-1个元素即为所求，查找成功；否则
6、对除第一个元returni;ASLsuccpi(i1)素外的后续表元素构成的查找表使用相同方法递}i0归查找。当后续查找表为空，则查找失败。Copyright@2013-HECopyright@2013-HECopyright@2013-HE基于有序顺序表的顺序查找基于有序顺序表的顺序查找算法有序顺序表的顺序查找示例及分析其查找效率的判定树：有序顺序表限定表中的元素按照其关键字值从小intSeqSearch(dataList&L,ElemTypex){到大或从大到小依次排列。在这类表中进行查找//在数据表L.data[0]..L.dada[n-1]中顺序查找
7、关键字(10,20,30,40,50,60)比表中元素任意存放，查找速度会有所提高。//值为x的数据元素<10>157在有序顺序表中做顺序查找时，若查找不成功，for(inti=0;i6i02不必检测到表尾才停止，只要发现有比它的关键=if(L.data[i].key==x)returni;//成功成功<30>字值大的即可停止查找。=elseif(L.data[i].key>x)break;//查找失败<40>若设表中有n个元素，则查找成功的平均查找长=retur
