数据结构-C语言版：DS08-查找

第 八 章 查 找 基本概念基本概念线性表的查找线性表的查找 树表的查找树表的查找 散列散列(Hash)Hash)技术技术 第八章第八章 查找查找 第 八 章 查 找 8.18.1查找的基本概念查找的基本概念 查找（查找（查找（查找（SearchingSearchingSearchingSearching）的定义是：在含有的定义是：在含有的定义是：在含有的定义是：在含有n n n n条条条条记录的表（文件）中找出关键字等于给定记录的表（文件）中找出关键字等于给定记录的表（文件）中找出关键字等于给定记录的表（文件）中找出关键字等于给定值值值值K K K K的记录。若找到，则查找成功，返回的记录。若找到，则查找成功，返回的记录。若找到，则查找成功，返回的记录。若找到，则查找成功，返回该记录的信息或该记录在表（文件）中的该记录的信息或该记录在表（文件）中的该记录的信息或该记录在表（文件）中的该记录的信息或该记录在表（文件）中的位置；否则查找失败，返回相关的指示信位置；否则查找失败，返回相关的指示信位置；否则查找失败，返回相关的指示信位置；否则查找失败，返回相关的指示信息。息。息。息。第 八 章 查 找 若在查找的同时对表做修改操作（如插入和删除等）若在查找的同时对表做修改操作（如插入和删除等）若在查找的同时对表做修改操作（如插入和删除等）若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为，则相应的表称之为，则相应的表称之为，则相应的表称之为动态查找表动态查找表动态查找表动态查找表（DynamicDynamicSearchTableSearchTable）。）。）。）。否则称之为否则称之为否则称之为否则称之为静态查找表静态查找表静态查找表静态查找表(StaticSearchTable)StaticSearchTable)。若整个查找过程都在内存进行，则称之为若整个查找过程都在内存进行，则称之为若整个查找过程都在内存进行，则称之为若整个查找过程都在内存进行，则称之为内查找内查找内查找内查找；反之，若查找过程中需要访问外存，则称之为反之，若查找过程中需要访问外存，则称之为反之，若查找过程中需要访问外存，则称之为反之，若查找过程中需要访问外存，则称之为外外外外查找查找查找查找查找表的数据结构表示查找表的数据结构表示 第 八 章 查 找 如何分析算法优劣？如何分析算法优劣？主要分析算主要分析算法运算时所需要的时间和其存储结构法运算时所需要的时间和其存储结构占用的内存空间。而对于查找算法，占用的内存空间。而对于查找算法，执行的时间通常取决于关键字的比较执行的时间通常取决于关键字的比较次数，所以本章经常用平均比较次数，次数，所以本章经常用平均比较次数，即即平均查找长度平均查找长度 ASLASL（Average Average Search LengthSearch Length）第 八 章 查 找 其中：其中：其中：其中：1 1 1 1、n n n n是结点的个数；是结点的个数；是结点的个数；是结点的个数；2 2 2 2、P P P Pi i i i是查找第是查找第是查找第是查找第i i i i个结点的概率。若不特个结点的概率。若不特个结点的概率。若不特个结点的概率。若不特别声明别声明别声明别声明 ，认为每个结点的查找概率相等，即，认为每个结点的查找概率相等，即，认为每个结点的查找概率相等，即，认为每个结点的查找概率相等，即 p p p pl l l l=p=p=p=p2 2 2 2=p p p pn n n n=1/n1/n1/n1/n3333、c c c ci i i i是找到第是找到第是找到第是找到第i i i i个结点所需进行的比较个结点所需进行的比较个结点所需进行的比较个结点所需进行的比较次数次数次数次数ASL=ASL=平均查找长度平均查找长度平均查找长度平均查找长度 ASLASLASLASL（Average Search LengthAverage Search LengthAverage Search LengthAverage Search Length）定义为定义为定义为定义为 ：第 八 章 查 找 一、顺序查找一、顺序查找一、顺序查找一、顺序查找(SequentialSearch)SequentialSearch)基本思想是：从表的一端开始，顺序基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关扫描线性表，依次将扫描到的结点关键字和给定值键字和给定值K K相比较。若当前扫描到相比较。若当前扫描到的结点关键字与的结点关键字与K K相等，则查找成功；相等，则查找成功；若扫描结束后，仍未找到关键字等于若扫描结束后，仍未找到关键字等于K K的结点，则查找失败。的结点，则查找失败。8.2线性表的查找线性表的查找 第 八 章 查 找 基于顺序结构的顺序查找算法基于顺序结构的顺序查找算法 类型说明类型说明类型说明类型说明 typedeftypedeftypedeftypedef structstructstructstruct KeyTypeKeyTypeKeyTypeKeyType key key key key；/*/*/*/*KeyTypeKeyTypeKeyTypeKeyType由用户定义由用户定义由用户定义由用户定义*/InfoTypeInfoTypeInfoTypeInfoType otherinfootherinfootherinfootherinfo；/*/*/*/*此类型依赖于应用此类型依赖于应用此类型依赖于应用此类型依赖于应用*/NodeTypeNodeTypeNodeTypeNodeType；typedeftypedeftypedeftypedef NodeTypeNodeTypeNodeTypeNodeType Seqlistn+1 Seqlistn+1 Seqlistn+1 Seqlistn+1；/*/*/*/*多出多出多出多出0 0 0 0号单元用作监视哨号单元用作监视哨号单元用作监视哨号单元用作监视哨*/第 八 章 查 找 具体算法具体算法具体算法具体算法 intintintint SeqSearchSeqSearchSeqSearchSeqSearch(SeqlistSeqlistSeqlistSeqlist R R R R，KeyTypeKeyTypeKeyTypeKeyType K)K)K)K)/*/*/*/*在顺序表在顺序表在顺序表在顺序表R1.nR1.nR1.nR1.n中顺序查找关键字为中顺序查找关键字为中顺序查找关键字为中顺序查找关键字为K K K K的结点，的结点，的结点，的结点，*/*/*/*/*成功时返回找到的结点位置，失败时返回成功时返回找到的结点位置，失败时返回成功时返回找到的结点位置，失败时返回成功时返回找到的结点位置，失败时返回0*/0*/0*/0*/intintintint i i i i；R0.key=KR0.key=KR0.key=KR0.key=K；/*/*/*/*设置监视哨设置监视哨设置监视哨设置监视哨*/for(i=nfor(i=nfor(i=nfor(i=n；Ri.key!=K;i-)Ri.key!=K;i-)Ri.key!=K;i-)Ri.key!=K;i-)；/*/*/*/*从表后往从表后往从表后往从表后往前找前找前找前找*/return ireturn ireturn ireturn i；/*/*/*/*若若若若i i i i为为为为0 0 0 0，表示查找失败，否则，表示查找失败，否则，表示查找失败，否则，表示查找失败，否则RiRiRiRi为要为要为要为要找的结点找的结点找的结点找的结点*/*/*/*/*SeqSearchSeqSearchSeqSearchSeqSearch*/*/*/*/第 八 章 查 找 算法分析算法分析查找查找查找查找成功时的成功时的成功时的成功时的顺序查找顺序查找顺序查找顺序查找的平均查找长度：的平均查找长度：的平均查找长度：的平均查找长度：在等概率情况下，在等概率情况下，在等概率情况下，在等概率情况下，p p p pi i i i=1/n(1in)=1/n(1in)=1/n(1in)=1/n(1in)，故成功的故成功的故成功的故成功的平均查找长度为平均查找长度为平均查找长度为平均查找长度为 ASL=ASL=ASL=ASL=(n+2+1)/n=(n+1)/2=(n+2+1)/n=(n+1)/2=(n+2+1)/n=(n+1)/2=(n+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的一半。即查找成功时的平均比较次数约为表长的一半。即查找成功时的平均比较次数约为表长的一半。即查找成功时的平均比较次数约为表长的一半。第 八 章 查 找 顺序查找的缺点顺序查找的缺点顺序查找的缺点顺序查找的缺点 查找效率低。查找效率低。查找效率低。查找效率低。顺序查找的优点顺序查找的优点顺序查找的优点顺序查找的优点算法简单，且对表的结构无任何要求，无算法简单，且对表的结构无任何要求，无算法简单，且对表的结构无任何要求，无算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论是用向量还是用链表来存放结点，也无论是用向量还是用链表来存放结点，也无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样论结点之间是否按关键字有序，它都同样论结点之间是否按关键字有序，它都同样论结点之间是否按关键字有序，它都同样适用。适用。适用。适用。第 八 章 查 找 n n二分查找二分查找二分查找二分查找又称又称又称又称折半查找折半查找折半查找折半查找，它是一种效率较高的查，它是一种效率较高的查，它是一种效率较高的查，它是一种效率较高的查找方法。找方法。找方法。找方法。n n二分查找要求二分查找要求二分查找要求二分查找要求：要求线性表是：要求线性表是：要求线性表是：要求线性表是有序表有序表有序表有序表，即表中结，即表中结，即表中结，即表中结点按关键字有序，并且要用点按关键字有序，并且要用点按关键字有序，并且要用点按关键字有序，并且要用向量作为表的存储结向量作为表的存储结向量作为表的存储结向量作为表的存储结构构构构。不妨设有序表是递增有序的。不妨设有序表是递增有序的。不妨设有序表是递增有序的。不妨设有序表是递增有序的。二、二分查找二、二分查找 第 八 章 查 找（1 1）首先确定该区间的中点位置）首先确定该区间的中点位置）首先确定该区间的中点位置）首先确定该区间的中点位置 mid=（2 2）然后将中间位置记录的键值然后将中间位置记录的键值然后将中间位置记录的键值然后将中间位置记录的键值Rmid.keyRmid.key和和和和所给关键字所给关键字所给关键字所给关键字K K进行比较：若相等，则查找成功进行比较：若相等，则查找成功进行比较：若相等，则查找成功进行比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，并返回此位置，否则须确定新的查找区间，并返回此位置，否则须确定新的查找区间，并返回此位置，否则须确定新的查找区间，继续二分查找。继续二分查找。继续二分查找。继续二分查找。二分查找的基本思想是：二分查找的基本思想是：二分查找的基本思想是：二分查找的基本思想是：第 八 章 查 找 例：设算法的输入实例中有序的关键字序列例：设算法的输入实例中有序的关键字序列为：为：05，13，19，21，37，56，64，75，80，88，92。查找的关键字。查找的关键字K=21 第一步：这里的n=11,mid=(1+11)/2=605，13，19，21，37，56，64，75，80，88，92 第 八 章 查 找 第二步：mid=(1+5)/2=305，13，19，21，37，56，64，75，80，88，92第三步：mid=(4+5)/2=405，13，19，21，37，56，64，75，80，88，92此时Rmid.keyK，returnmid4。第 八 章 查 找 二分查找算法二分查找算法