搜索
井冈山大学计算机科学系井冈山大学计算机科学系冷明冷明lengming@jgsu.edu.cnlengming@jgsu.edu.cn基本概念基本概念查找表用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。动态查找表若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。关键字是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字（即每个元素的关键字值互不相同）称为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值等于某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。查找方法评价：¾查找速度¾占用存储空间多少¾算法本身复杂程度¾平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值。个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：个记录的表，对含有icpipcpASLniniiiniii111==∑∑==9.1静态查找表静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。9.1.1顺序查找(SequentialSearch)1.顺序查找的基本思想顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。2.顺序查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。算法描述：Ch7_1.txti例01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1顺序查找方法的ASL212)1(1)1(1则1概率相等设表中每个元素的查找11+=+⋅=+−===∑∑==nnnninncpASLnpniniiii∑==niiicpASLn1个记录的表，对含有3.链表的顺序查找链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。链表的类型定义如下所示：typedefstructnode{keytypekey;//结点的关键字类型anytypeotheritem;//结点的其他成分structnode*next;//指向链表结点的指针}Link_Node,*Link;将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。对链表实现顺序查找就是在有头结点的链式查找表中查找关键字值等于给定值的记录。若查找成功，返回指向相应结点的指针，否则返回空指针。Link_Node*link_search(Linkh,keytypek){//link为带头结点链表的头指针，查找关键字值等//于k的记录：查找成功，返回指向找到的结点的//指针，查找失败返回空指针p=h-next;while((p!=NULL)&&(p-key!=k))p=p-next;returnp;}顺序查找特点：算法简单，对表的结构无任何要求；但是执行效率较低，尤其当n较大时，不宜采用这种查找方法。平均查找长度：ASL=(n+1)/29.1.2折半查找(BinarySearch)查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较:r[mid].Key=x，搜索成功；r[mid].Keyx，把搜索区间缩小到表的前半部分，再继续进行对分搜索；r[mid].Keyx，把搜索区间缩小到表的后半部分，再继续进行对分搜索。每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到，则搜索失败。折半查找算法实现：设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值。初始时，令low=1,high=n,mid=⎣(low+high)/2⎦让k与mid指向的记录比较若k==r[mid].key，查找成功；若kr[mid].key，则high=mid-1；若kr[mid].key，则low=mid+1；重复上述操作，直至lowhigh，查找失败算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmidCh7_2.txt例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh1185210741936判定树：12345678910115131921375664758088929.1.3分块查找(BlockingSearch)是顺序查找的一种改进方法，又称索引顺序查找。性能介于顺序查找和二分查找之间。1、查找表存储结构由“分块有序”的线性表和索引表组成。（1）“分块有序”的线性表线性表R被均分为若干块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序。（2）索引表抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序，所以索引表是一个递增有序表。【例】下图是一个带索引的分块有序的线性表。其中线性表L共有20个结点，被分成3块，第一块中最大关键字25小于第二块中的最小关键字27，第二块中最大关键字55小于第三块中的最小关键字60。分块有序表的索引存储表示图分块有序表的索引存储表示图12345678910111213141516171822121389203342443824486058745786532248861713索引表查38最大关键字起始地址22、分块查找的基本思想：、分块查找的基本思想：（（11））首先查找索引表首先查找索引表索引表是有序表，可采用索引表是有序表，可采用二分查找二分查找或顺序查找或顺序查找，以确定待查的结点在哪一块。，以确定待查的结点在哪一块。（（22）然后）然后在已确定的块中进行顺序查找在已确定的块中进行顺序查找由于块内无序，只能用由于块内无序，只能用顺序查找顺序查找。。分块查找方法通过将查找缩小在某个块中从而分块查找方法通过将查找缩小在某个块中从而提高了检索的效率。提高了检索的效率。分块查找方法评价2)1(log)2(1)(21212111)1(211ssnASLssnsbisjbASLsbnLLLLASLbssibjbswbwbbs++≈++=+++=+=+=∑∑==：用折半查找确定所在块：用顺序查找确定所在块找概率相等，则：并设表中每个记录的查个记录，块，每块含的表平均分成若将表长为均查找长度—在块中查找元素的平—块的平均查找长度—查找索引表确定所在—其中：ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找9.2动态查找表9.2.1二叉排序树（BinarySortTree）二叉排序树是一种常用的动态查找表。¾非递归形式定义：二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：（1）任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。（2）任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。¾递归形式定义：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：（1）若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。（2）若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。（3）它的左右子树都是二叉排序树。¾示例参见教材P227图9.7例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的一棵二叉排序树如图所示。非空二叉排序树中，根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值。如果对上述二叉排序树进行中根遍历可以得到一个关键字有序序列（12,15,35,46,57,62,65,68,79），这是二叉排序树的一个重要特征，也正是由此将其称为“二叉排序树”。9.2.2二叉排序树的查找在二叉排序树中查找一个关键字值为k的结点的基本思想：用给定值k与根结点关键字值比较：如果k小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找；否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。二叉排序树查找的过程描述如下：（1）若二叉树为空树，则查找失败，（2）将给定值k与根结点的关键字值比较，若相等，则查找成功，（3）若根结点的关键字值小于给定值k，则在左子树中继续搜索，（4）否则，在右子树中继续查找。假定二叉排序树的链式存储结构的类型定义如下：typedefstructnode{keytypekey;//结点的关键字类型anytypeotheritem;//结点的其它成分structnode*lchild；structnode*rchild;}BiSortNode,*BiSortTree；二叉排序树查找操作的递归算法如下：BiSortNode*bt_search(BiSortTreebt,keytypek){//在根指针为bt的二叉排序树上查找关键字值为k的结//点.成功则返回指向该结点的指针，否则返回空指针if(bt==NULL)||(bt-key==k)returnbt;elseif(kbt-key)returnbt_search(bt-lchild,k);//在左子树中搜索elsereturnbt_search(bt-rchild,k);//在右子树中搜索}//参见教材P228算法9.5(a)二叉排序树查找操作的非递归算法如下：BiSortNode*bt_search1(BiSortTreebt,keytypek){p=bt;//指针p指向根结点，查找从根结点开始while(p!=NULL&&p-key!=k){if(k