[清航考研]暑期数据结构辅导-05

1111清航考研查找(Search)的概念�所谓所谓所谓所谓查找查找查找查找，，，，就是在数据集合中寻找满足某种条件就是在数据集合中寻找满足某种条件就是在数据集合中寻找满足某种条件就是在数据集合中寻找满足某种条件的数据元素的数据元素的数据元素的数据元素。。。。�查找的结果通常有两种可能：查找的结果通常有两种可能：查找的结果通常有两种可能：查找的结果通常有两种可能：�查找成功查找成功查找成功查找成功，即找到满足条件的数据元素。这，即找到满足条件的数据元素。这，即找到满足条件的数据元素。这，即找到满足条件的数据元素。这时，作为结果时，作为结果时，作为结果时，作为结果,,,,可报告该元素在结构中的位置可报告该元素在结构中的位置可报告该元素在结构中的位置可报告该元素在结构中的位置,,,,还可给出该元素中的具体信息。还可给出该元素中的具体信息。还可给出该元素中的具体信息。还可给出该元素中的具体信息。�查找不成功查找不成功查找不成功查找不成功，或查找失败。作为结果，或查找失败。作为结果，或查找失败。作为结果，或查找失败。作为结果,,,,应报告应报告应报告应报告一些信息，如失败标志、位置等。一些信息，如失败标志、位置等。一些信息，如失败标志、位置等。一些信息，如失败标志、位置等。�通常称用于查找的数据集合为通常称用于查找的数据集合为通常称用于查找的数据集合为通常称用于查找的数据集合为查找结构查找结构查找结构查找结构，它是由，它是由，它是由，它是由同一数据类型的元素（或记录）同一数据类型的元素（或记录）同一数据类型的元素（或记录）同一数据类型的元素（或记录）组成。组成。组成。组成。清航考研�在每个元素中有若干属性，其中有一个属性，其在每个元素中有若干属性，其中有一个属性，其在每个元素中有若干属性，其中有一个属性，其在每个元素中有若干属性，其中有一个属性，其值可唯一地标识这个元素。称为关键字（值可唯一地标识这个元素。称为关键字（值可唯一地标识这个元素。称为关键字（值可唯一地标识这个元素。称为关键字（keykeykeykey）。）。）。）。使用基于关键字的查找，查找结果应是唯一的。使用基于关键字的查找，查找结果应是唯一的。使用基于关键字的查找，查找结果应是唯一的。使用基于关键字的查找，查找结果应是唯一的。但在实际应用时，查找条件是多方面的，可以但在实际应用时，查找条件是多方面的，可以但在实际应用时，查找条件是多方面的，可以但在实际应用时，查找条件是多方面的，可以使使使使用基于属性的查找方法，但查找结果可能不唯一。用基于属性的查找方法，但查找结果可能不唯一。用基于属性的查找方法，但查找结果可能不唯一。用基于属性的查找方法，但查找结果可能不唯一。�衡量一个查找算法的时间效率的标准是：在查找过程衡量一个查找算法的时间效率的标准是：在查找过程衡量一个查找算法的时间效率的标准是：在查找过程衡量一个查找算法的时间效率的标准是：在查找过程中关键字的中关键字的中关键字的中关键字的平均比较次数平均比较次数平均比较次数平均比较次数，也称为，也称为，也称为，也称为平均查找长度平均查找长度平均查找长度平均查找长度ASL(AverageASL(AverageASL(AverageASL(AverageSearchLength)SearchLength)SearchLength)SearchLength)，通常它是查找结构中，通常它是查找结构中，通常它是查找结构中，通常它是查找结构中元素总数元素总数元素总数元素总数nnnn的函数。的函数。的函数。的函数。�静态查找常基于静态查找常基于静态查找常基于静态查找常基于线性表线性表线性表线性表，动态查找常基于，动态查找常基于，动态查找常基于，动态查找常基于树树树树或或或或字典字典字典字典。。。。2222清航考研静态查找表结构的定义#define#define#define#definemaxSize100////////查找表最大尺寸typedeftypedeftypedeftypedefintintintintElemType;;;;////////查找数据的类型typedeftypedeftypedeftypedefstructstructstructstruct{{{{////////查找表结点定义ElemTypekey;;;;////////关键字域other;other;other;other;////////其他数据信息}}}}ListNode;;;;typedeftypedeftypedeftypedefstructstructstructstructdataList{{{{////////查找表结点定义ListNodedata[maxSize];;;;////////数据存储数组intintintintn;;;;////////数组当前长度}}}}清航考研顺序查找(SequentialSearch)�所谓顺序查找所谓顺序查找所谓顺序查找所谓顺序查找,,,,又称线性查找又称线性查找又称线性查找又称线性查找,,,,主要用于在线性结主要用于在线性结主要用于在线性结主要用于在线性结构中进行查找。构中进行查找。构中进行查找。构中进行查找。�设若表中有设若表中有设若表中有设若表中有nnnn个元素，则顺序查找从表的先端个元素，则顺序查找从表的先端个元素，则顺序查找从表的先端个元素，则顺序查找从表的先端（或后端）（或后端）（或后端）（或后端）开始，依次用各元素的关键字与给定开始，依次用各元素的关键字与给定开始，依次用各元素的关键字与给定开始，依次用各元素的关键字与给定值值值值xxxx进行比较，直到找到与其值相等的元素，则查进行比较，直到找到与其值相等的元素，则查进行比较，直到找到与其值相等的元素，则查进行比较，直到找到与其值相等的元素，则查找成功；给出该元素在表中的位置。找成功；给出该元素在表中的位置。找成功；给出该元素在表中的位置。找成功；给出该元素在表中的位置。�若整个表都已检测完仍未找到关键字与若整个表都已检测完仍未找到关键字与若整个表都已检测完仍未找到关键字与若整个表都已检测完仍未找到关键字与xxxx相等的元相等的元相等的元相等的元素素素素,,,,则查找失败。给出失败信息。则查找失败。给出失败信息。则查找失败。给出失败信息。则查找失败。给出失败信息。清航考研设置“监视哨”的顺序查找算法intintintintLinearSearch(dataList&&&&L,ElemTypex){{{{////////在数据表L.data[0]..L.data[n-1]L.data[0]..L.data[n-1]L.data[0]..L.data[n-1]L.data[0]..L.data[n-1]中顺序查找关键字////////值与给定值x相等的数据元素,L.data[n].keyL.data[n].keyL.data[n].keyL.data[n].key作为////////控制搜索自动结束的“监视哨”使用L.data[L.n].key=x;;;;intintintinti=0;;;;////////将x送表尾的下一个位置设置监视哨whilewhilewhilewhile(L.data[i].key!=x)i++;;;;////////从前向后顺序查找returnreturnreturnreturni;;;;}}}}清航考研�设查找第设查找第设查找第设查找第iiii个元素的概率为个元素的概率为个元素的概率为个元素的概率为ppppiiii，查找到第，查找到第，查找到第，查找到第iiii个元素个元素个元素个元素所需比较次数为所需比较次数为所需比较次数为所需比较次数为cccciiii，，，，则查找成功的平均查找长度则查找成功的平均查找长度则查找成功的平均查找长度则查找成功的平均查找长度为为为为::::�在顺序查找并设置在顺序查找并设置在顺序查找并设置在顺序查找并设置““““监视哨监视哨监视哨监视哨””””情形，情形，情形，情形，cccciiii====iiii+1,+1,+1,+1,iiii=0=0=0=0,,,,1,1,1,1,…………,,,,nnnn-1-1-1-1，因此，因此，因此，因此∑∑===⋅=-1-1-1-10000-1-1-1-10000succsuccsuccsucc))))1111((((....ASLASLASLASLnnnniiiiiiiinnnniiiiiiiiiiiippppccccpppp1)1)1)1)((((ASLASLASLASL-1-1-1-10000succsuccsuccsucc+⋅=∑=iiiippppnnnniiiiiiii算法分析3333清航考研�设查找概率相等，即设查找概率相等，即设查找概率相等，即设查找概率相等，即ppppiiii=1/=1/=1/=1/nnnn,,,,iiii=1,2,=1,2,=1,2,=1,2,…………,,,,nnnn。则。则。则。则查找成功的平均查找长度为：查找成功的平均查找长度为：查找成功的平均查找长度为：查找成功的平均查找长度为：�而查找不成功时，一定把表中所有元素检测了一而查找不成功时，一定把表中所有元素检测了一而查找不成功时，一定把表中所有元素检测了一而查找不成功时，一定把表中所有元素检测了一遍，一直到监视哨。所以查找不成功的平均查找遍，一直到监视哨。所以查找不成功的平均查找遍，一直到监视哨。所以查找不成功的平均查找遍，一直到监视哨。所以查找不成功的平均查找长度为：长度为：长度为：长度为：ASLASLASLASLunsuccunsuccunsuccunsucc====nnnn+1+1+1+1。。。。�顺序查找可以用顺序查找可以用顺序查找可以用顺序查找可以用递归方法递归方法递归方法递归方法实现。实现。实现。实现。当查找表中第一当查找表中第一当查找表中第一当查找表中第一个元素即为所求，查找成功；否则个元素即为所求，查找成功；否则个元素即为所求，查找成功；否则个元素即为所求，查找成功；否则对除第一个元对除第一个元对除第一个元对除第一个元素外的后续表元素构成的查找表使用相同方法递素外的后续表元素构成的查找表使用相同方法递素外的后续表元素构成的查找表使用相同方法递素外的后续表元素构成的查找表使用相同方法递归查找归查找归查找归查找。当后续查找表为空，则查找失败。。当后续查找表为空，则查找失败。。当后续查找表为空，则查找失败。。当后续查找表为空，则查找失败。.∑=+=+⋅=+=-1-1-1-100002222111122221)1)1)1)((((11111)1)1)1)((((1111nnnniiiisuccsuccsuccsuccnnnnnnnnnnnnnnnniiiinnnnASLASLASLASL清航考研(dataList&&&&L,ElemTypex,intintintintloc){{{{////////在数据表L.data[0]..L.data[n