数据结构与算法分析之查找技术课件

第9章查找技术9.1顺序查找9.2有序表的对分查找9.3分块查找9.4二叉排序树查找9.5hashing技术第9章查找技术9.1顺序查找19.1顺序查找9.1.1线性表在顺序存储下的顺序查找9.1.2线性链表的顺序查找9.1顺序查找9.1.1线性表在顺序存储下的顺序查找29.1顺序查找9.1.1线性表在顺序存储下的顺序查找(1)如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。9.1顺序查找9.1.1线性表在顺序存储下的顺序查找39.1顺序查找线性表在顺序存储结构下的顺序查找输入：线性表长度n以及线性表的存储空间V；

被查找的元素x。输出：被查找元素x在线性表中的序号k。

如果在线性表中不存在元素x，则输出k＝－1。PROCEDURESERCH(V，n，x，k)k＝1WHILE(k≤n)and(V(k)≠x)DOk＝k＋1IF(k＝n＋1)THENk＝－1RETURN9.1顺序查找线性表在顺序存储结构下的顺序查找49.1顺序查找/*函数返回被查找元素x在线性表中的序号，如果在线性表中不存在元素值x，则返回－1*/intserch(v，n，x)intn；ETv[]，x；/*ET为线性表数据类型*/{intk；k＝0；while((k＜n)&&(v[k]≠x))k＝k＋1；if(k＝＝n)k＝－1；return(k)；}9.1顺序查找/*函数返回被查找元素x在线性表中的序号，59.1顺序查找9.1.2线性链表的顺序查找9.1顺序查找9.1.2线性链表的顺序查找69.1顺序查找线性表在链式存储结构下的顺序查找输入：线性链表头指针HEAD以及存储空间V、NEXT；

被查找的元素x。输出：被查找元素x的结点在线性链表中的存储序号k。

如果在线性链表中不存在元素值为x的结点，则输出k＝－1。PROCEDURELSERCH(V，NEXT，HEAD，x，k)k＝HEADWHILE(k≠0)and(V(k)≠x)DOk＝NEXT(k)IF(k＝0)THENk＝－1RETURN9.1顺序查找线性表在链式存储结构下的顺序查找79.1顺序查找structnode{ETd；structnode*next；}；/*函数返回被查找元素x所在结点的存储地址，如果在线性链表中不存在元素值为x的结点，则返回NULL*/structnode*lserch(head，x)structnode*head；ETx；/*ET为线性链表中值域的数据类型*/{structnodek；k＝head；while((k≠NULL)&&(k－>d≠x))k＝k－>next；return(k)；}9.1顺序查找structnode89.2有序表的对分查找设有序线性表的长度为n，被查元素为x。将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。在最坏情况下，对分查找只需要比较log2n次，而顺序查找需要比较n次。9.2有序表的对分查找设有序线性表的长度为n，被查元素为99.2有序表的对分查找有序线性表在顺序存储结构下的对分查找输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存在元素x，则输出k＝－1。PROCEDUREBSERCH(V，n，x，k)i＝1；j＝nWHILE(i＜＝j)DO{k＝(i＋j)/2IF(V(k)＝x)THENRETURNIF(V(k)＞x)THENj＝k－1；ELSEi＝k＋1；}IF(i＞j)THENk＝－1RETURN9.2有序表的对分查找有序线性表在顺序存储结构下的对分查109.2有序表的对分查找intbserch(v，n，x)/*函数返回被查找元素x在线性表中的序号如果在线性表中不存在元素值x，则返回－1*/intn；ETx，v[]；{inti，j，k；i＝1；j＝n；while(i＜＝j){k＝(i＋j)/2；if(v[k－1]＝＝x)return(k－1)；if(v[k－1]＞x)j＝k－1；elsei＝k＋1；}return(－1)；}9.2有序表的对分查找intbserch(v，n，x119.3分块查找分块有序表将长度为n线性表分成m个子表，各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。分块有序表的结构可以分为两部分：(1)线性表本身采用顺序存储结构。(2)再建立一个索引表。在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。9.3分块查找分块有序表129.3分块查找structindnode{ETkey；/*数据域，存放子表中的最大值，其类型与线性表中元素的数据类型相同*/

intk；/*指针域，指示子表中第一个元素在线性表中的序号*/}；9.3分块查找structindnode139.3分块查找9.3分块查找149.3分块查找(1)首先查找索引表，以便确定被查元素所在的子表。由于索引表数据域中的数据是有序的，因此可以采用对分查找。(2)然后在相应的子表中用顺序查找法进行具体的查找。分块查找输入：长度为n的线性表L的存储空间V(1：n)；索引表中的数据域存储空间KEY(1：m)与指针域存储空间

K(1：m)；被查元素x。输出：被查元素x在线性表L中的序号j（即使L(j)＝x的j）。如果x不在线性表L中，则置j＝－1。9.3分块查找(1)首先查找索引表，以便确定被查元素所在159.3分块查找PROCEDUREINSERCH(V，n，KEY，K，m，x，j)i＝1；j＝mWHILE(j－i＞1)DO[对分查找索引表]{t＝(i＋j)/2IF(x≤KEY(t))THENj＝tELSEi＝t}IF(i≠j)and(x＞KEY(i))THENi＝jj＝K(i)；t＝nIF(i≠m)THENt＝K(i＋1)－1[确定顺序查找的终点]WHILE(j≤t)and(V(j)≠x)DOj＝j＋1[顺序查找子表]IF(j＞t)THENj＝－1RETURN9.3分块查找PROCEDUREINSERCH(V，169.3分块查找在分块查找中，为了找到被查元素x所在的子表，需要对分查找索引表，在最坏情况下需要查找log2(m＋1)次。在相应子表中用顺序查找法查找元素x，在最坏情况下需要查找n/m（假设各子表长度相等）次；而在平均情况下需要查找n/(2m)次。因此，分块查找的工作量为：在最坏情况下需要查找log2(m＋1)＋n/m次，平均情况下大约需要查找log2(m＋1)＋n/(2m)次。当m＝n时，线性表L即为有序表，分块查找即为对分查找当m＝1时，线性表L为一般的无序表，分块查找即为顺序查找。分块查找的效率介于对分查找和顺序查找之间。9.3分块查找在分块查找中，为了找到被查元素x所在的子表179.3分块查找structindnode{ETkey；/*数据域，存放子表中的最大值，其类型与线性表中元素的数据类型相同*/

intk；/*指针域，指示子表中第一个元素在线性表中的序号*/}；/*函数返回被查找元素x在线性表中的序号，如果在线性表中不存在元素值x，则返回－1*/

intinserch(v，n，s，m，x)intn，m；ETx，v[]；structindnodes[]；9.3分块查找structindnode189.3分块查找

{inti，j，t；i＝1；j＝m；while(j－i＞1)/*对分查找索引表*/{t＝(i＋j)/2；if(x＜＝s[t].key)j＝t；elsei＝t；}if((i!＝j)&&(x＞s[i].key))i＝j；j＝s[i].k；t＝n；if(i!＝m)t＝s[i＋1].k－1；/*确定顺序查找的终点*/

while((j＜＝t)&&(V[j]!＝x))j＝j＋1；/*顺序查找子表*/

if(j＞t)j＝－1；return(j)；}9.3分块查找{inti，j，t；199.4二叉排序树查找9.4.1二叉排序树及其构造9.4.2二叉排序树查找9.4二叉排序树查找9.4.1二叉排序树及其构造209.4二叉排序树查找9.4.1二叉排序树及其构造(1)左子树上的所有结点值均小于根结点值；(2)右子树上的所有结点值均不小于根结点值；(3)左、右子树也满足上述两个条件。9.4二叉排序树查找9.4.1二叉排序树及其构造219.4二叉排序树查找9.4二叉排序树查找229.4二叉排序树查找9.4二叉排序树查找239.4二叉排序树查找依次读入给定序列中的每一个元素：(1)若当前的二叉排序树为空，则读入的元素为根结点；(2)若读入的元素值小于根结点值，则将元素插入到左子树中；(3)若读入的元素值不小于根结点值，则将元素插入到右子树中。无论是插入到左子树还是右子树，同样按照上述方法处理。9.4二叉排序树查找依次读入给定序列中的每一个元素：249.4二叉排序树查找9.4二叉排序树查找259.4二叉排序树查找9.4二叉排序树查找269.4二叉排序树查找插入元素689.4二叉排序树查找插入元素68279.4二叉排序树查找插入元素719.4二叉排序树查找插入元素71289.4二叉排序树查找插入元素779.4二叉排序树查找插入元素77299.4二叉排序树查找插入元素889.4二叉排序树查找插入元素88309.4二叉排序树查找二叉排序树的另一种形态9.4二叉排序树查找二叉排序树的另一种形态319.4二叉排序树查找由无序序列构造二叉排序树输入：长度为n的无序序列A(1：n)。输出：二叉排序树的头指针BT。PROCEDUREINBSORT(A，n，BT)BT＝0FORk＝1TOnDO{NEW(p)[取得一个新结点]

V(p)＝A(k)；L(p)＝0；R(p)＝0j＝BTIF(j＝0)THENBT＝p[若二叉排序树为空]

ELSE[二叉排序树不空]9.4二叉排序树查找由无序序列构造二叉排序树329.4二叉排序树查找

{WHILE(L(j)≠p)and(R(j)≠p)DO[未到叶子结点]{IF(A(k)＜V(j))THEN[插入到左子树]{IF(L(j)≠0)THENj＝L(j)ELSEL(j)＝p}ELSE[插入到右子树]{IF(R(j)≠0)THENj＝R(j)ELSER(j)＝p}}}}RETURN9.4二叉排序树查找{WHILE(L(j)≠339.4二叉排序树查找#include"stdlib.h"/*malloc函数需要包含头文件stdlib.h*/structbtnode/*定义结点类型*/{ETd；/*数据域*/

structbtnode*lchild；/*左指针域*/

structbtnode*rchild；/*右指针域*/}；structbtnode*inbsort(a，n)/*函数返回二叉排序树头指针*/intn；ETa[]；{structbtnode*p，*q，*bt；intk；bt＝NULL；9.4二叉排序树查找#include"stdlib.349.4二叉排序树查找

for(k＝0；k＜n；k＋＋){p＝(structbtnode*)malloc(sizeof(structbtnode))；p－>d＝a[k]；p－>lchild＝NULL；p－>rchild＝NULL；/*置新结点的数据域与左、右指针域*/

q＝bt；if(q＝＝NULL)bt＝p；/*二叉排序树为空*/

else/*二叉排序树不空*/{while((q－>lchild!＝p)&&(q－>rchild!＝p)){if(a[k]＜q－>d)/*插入到左子树*/{if(q－>lchild!＝NULL)q＝q－>lchild；elseq－>lchild＝p；}9.4二叉排序树查找for(k＝0；k＜n；k359.4二叉排序树查找

else/*插入到右子树*/{if(q－>rchild!＝NULL)q＝q－>rchild；elseq－>rchild＝p；}}}}return(bt)；/*返回二叉排序树头指针*/}9.4二叉排序树查找else/*369.4二叉排序树查找9.4.2二叉排序树查找从二叉排序树的根结点开始与被查值进行比较：(1)若被查值等于根结点值，查找成功，查找过程结束。(2)若被查值小于根结点值，则到左子树中去查找。(3)若被查值大于根结点值，则到右子树中去查找。在左、右子树中查找时也采用上述方法。查找过程直到查找成功或所考虑的子树已空为止。9.4二叉排序树查找9.4.2二叉排序树查找379.4二叉排序树查找二叉排序树查找输入：二叉排序树头指针BT以及存储空间；被查元素x。输出：被查元素x在二叉排序树空间中的存储结点序号pPROCEDUREBSTSERCH(BT，x，p)P＝BTWHILE(p≠0)and(V(p)≠x)DO{IF(x＜V(p))THENp＝L(p)[沿左子树查找]

ELSEp＝R(p)[沿右子树查找]}RETURN9.4二叉排序树查找二叉排序树查找389.4二叉排序树查找structbtnode/*定义结点类型*/{ETd；/*数据域*/

structbtnode*lchild；/*左指针域*/

structbtnode*rchild；/*右指针域*/}；9.4二叉排序树查找structbtnode399.4二叉排序树查找/*函数返回被查值x所在结点的存储地址*/structbtnode*bstserch(bt，x)structbtnode*bt；ETx；{structbtnode*p；p＝bt；while((p!＝NULL)&&(p－>d!＝x)){if(x＜p－>d)p＝p－>lchild；/*沿左子树查找*/

elsep＝p－>rchild；/*沿右子树查找*/}

return(p)；}9.4二叉排序树查找/*函数返回被查值x所在结点的存储地409.5Hash表技术9.5.1Hash表的基本概念9.5.2几种常用的Hash表9.5Hash表技术9.5.1Hash表的基本概念419.5.1Hash表的基本概念9.51.1直接查找技术9.51.2Hash表9.51.3Hash码的构造9.5.1Hash表的基本概念9.51.1直接查找技429.51Hash表的基本概念9.51.1直接查找技术设表的长度为n。如果存在一个函数i＝i(k)，对于表中的任意一个元素的关键字k，满足以下条件：(1)1≤i≤n；(2)对于任意的元素关键字k1≠k2，恒存在i(k1)≠i(k2)。则称此表为直接查找表。其中函数i＝i(k)称为关键字k的映象函数。9.51Hash表的基本概念9.51.1直接查找技术439.51Hash表的基本概念1.直接查找表的填入要将关键字为k的元素填入到直接查找表，只需做以下两步：(1)计算关键字k的映象函数i＝i(k)；(2)将关键字k及有关元素信息填入到表的第i项。9.51Hash表的基本概念1.直接查找表的填入449.51Hash表的基本概念2.直接查找表的取出要在直接查找表中取出关键字k的元素，也只需做以下两步：(1)计算关键字k的映象函数i＝i(k)；(2)检查表中第i项：若第i项为空，则说明表中没有关键字为k的元素；否则取出第i项中的元素即可。9.51Hash表的基本概念2.直接查找表的取出459.51Hash表的基本概念9.51.2Hash表9.51Hash表的基本概念9.51.2Hash表469.51Hash表的基本概念例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的表中。设映象函数为i＝INT(k/3)＋1。9.51Hash表的基本概念例479.51Hash表的基本概念设表的长度为n。如果存在一个函数i＝i(k)，对于表中的任意一个元素的关键字k，满足1≤i≤n，则称此表为Hash表。其中函数i＝i(k)称为关键字k的Hash码。(1)构造合适的Hash码，以便尽量减少表中元素冲突的次数。即Hash码的均匀性要比较好。(2)当表中元素发生冲突时，要进行适当的处理。9.51Hash表的基本概念489.51Hash表的基本概念9.51.3Hash码的构造(1)使各关键字尽可能均匀地分布在Hash表中，即Hash码的均匀性要好，以便减少冲突发生的机会。(2)Hash码的计算要尽量简单。9.51Hash表的基本概念9.51.3Hash码的499.51Hash表的基本概念1.截段法

2.分段叠加法

3.除法

i＝mod(k，n)4.乘法

i＝mod(k*φ，n)φ一般取0.618033988747，或0.6125423371，或0.6161616161。9.51Hash表的基本概念1.截段法509.52几种常用的Hash表9.52.1线性Hash表9.52.2随机Hash表9.52.3溢出Hash表9.52.4拉链Hash表9.52.5指标Hash表9.52几种常用的Hash表9.52.1线性Hash519.52几种常用的Hash表9.52.1线性Hash表开放法9.52几种常用的Hash表9.52.1线性Hash529.52几种常用的Hash表1.线性Hash表的填入将关键字k及有关信息填入线性Hash表的步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)检查表中第i项的内容：若第i项为空，则将关键字k及有关信息填入该项；若第i项不空，则令i＝mod(i＋1，n)，转(2)继续检查。只要Hash表尚未填满，最终总可以找到一个空项，将关键字k及有关信息填入到Hash表中。9.52几种常用的Hash表1.线性Hash表的填入539.52几种常用的Hash表2.线性Hash表的取出要在线性Hash表中取出关键字k的元素，其步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)检查表中第i项的内容：若第i项登记着关键字k，则取出该项元素即可；若第i项为空，则表示在Hash表中没有该关键字的信息；若第i项不空，且登记的不是关键字k，则令

i＝mod(i＋1，n)，转(2)继续检查。9.52几种常用的Hash表2.线性Hash表的取出549.52几种常用的Hash表例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的线性Hash表中。设Hash码为i＝INT(k/3)＋1。9.52几种常用的Hash表例559.52几种常用的Hash表缺点：(1)在线性Hash表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当Hash码的冲突较多时，在线性Hash表中会存在“堆聚”现象，即许多关键字被连续登记在一起，从而会降低查找效率。(2)在线性Hash表的填入过程中，处理冲突时会带来新的冲突。9.52几种常用的Hash表569.52几种常用的Hash表9.52几种常用的Hash表579.52几种常用的Hash表9.52.2随机Hash表9.52几种常用的Hash表9.52.2随机Hash589.52几种常用的Hash表1.随机Hash表的填入将关键字k及有关信息填入随机Hash表的步骤如下：(1)计算关键字k的Hash码i0＝i(k)。且令i＝i0。(2)伪随机数序列初始化，令j＝1（即将取随机数指针指向伪随机数序列中的第1个随机数）。(3)检查表中第i项的内容：若第i项为空，则将关键字k及有关信息填入该项；若第i项不空，则令i＝mod(i0＋RN(j)，n)，并令

j＝j＋1（即将取随机数指针指向下一个随机数），转(3)继续检查。其中RN(j)表示伪随机数序列RN中的第j个随机数。9.52几种常用的Hash表1.随机Hash表的填入599.52几种常用的Hash表伪随机数序列RN按下列方法产生：

R＝1FORj＝1TOnDO{R＝mod(5*R，4n)RN(j)＝INT(R/4)}9.52几种常用的Hash表伪随机数序列RN按下列方法产609.52几种常用的Hash表例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝24＝16的随机Hash表中。设Hash码为i＝INT(k/3)＋1。伪随机数序列为：1，6，15，12，13，2，11，8，9，14，7，4，5，10，3，0。9.52几种常用的Hash表例619.52几种常用的Hash表2.随机Hash表的取出要在随机Hash表中取出关键字k的元素，其步骤如下：(1)计算关键字k的Hash码i0＝i(k)。且令i＝i0。(2)伪随机数序列初始化，令j＝1（即将取随机数指针指向伪随机数序列中的第1个随机数）。(3)检查表中第i项的内容：若第i项登记着关键字k，则取出该项元素即可；若第i项空，则表示在Hash表中没有该关键字信息；若第i项不空，且登记的不是关键字k，则令

i＝mod(i0＋RN(j)，n)，并令j＝j＋1（即将取随机数指针指向下一个随机数），转(3)继续检查。其中

RN(j)表示伪随机数序列RN中的第j个随机数。9.52几种常用的Hash表2.随机Hash表的取出629.52几种常用的Hash表9.52几种常用的Hash表639.52几种常用的Hash表9.52.3溢出Hash表溢出Hash表包括Hash表和溢出表两部分。在Hash表的填入过程中，将冲突的元素顺序填入溢出表，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。溢出表是一个顺序查找表。9.52几种常用的Hash表9.52.3溢出Hash649.52几种常用的Hash表1.溢出Hash表的填入将关键字k及有关信息填入溢出Hash表的步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)检查表中第i项的内容：若第i项为空，则将关键字k及有关信息填入该项；若第i项不空，则将关键字k及有关信息依次填入溢出表中的自由项。9.52几种常用的Hash表1.溢出Hash表的填入659.52几种常用的Hash表2.溢出Hash表的取出要在溢出Hash表中取出关键字k的元素，其步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)检查表中第i项的内容：若第i项登记着关键字k，则取出该项元素即可；若第i项为空，则表示在Hash表中没有该关键字信息；若第i项不空，且登记的不是关键字k，则转入在溢出表中进行顺序查找。9.52几种常用的Hash表2.溢出Hash表的取出669.52几种常用的Hash表例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的溢出Hash表中。设Hash码为i＝INT(k/3)＋1。9.52几种常用的Hash表例679.52几种常用的Hash表9.52.4拉链Hash表拉链Hash表又分为外链Hash表与内链Hash表。9.52几种常用的Hash表9.52.4拉链Hash689.52几种常用的Hash表1.外链Hash表的填入将关键字k及有关信息填入外链Hash表的步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)取得一个新结点p，并将关键字k及有关信息填入结点p。(3)将结点p链入以H(i)为头指针的链表的链头。9.52几种常用的Hash表1.外链Hash表的填入699.52几种常用的Hash表例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的外链Hash表中。设Hash码为i＝INT(k/3)＋1。9.52几种常用的Hash表例将关键字序列(09，31709.52几种常用的Hash表2.外链Hash表的取出要在外链Hash表中取出关键字k的元素，其步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)在以H(i)为头指针的链表中顺序查找关键字为k的结点。若找到，则从结点中取出该元素。9.52几种常用的Hash表2.外链Hash表的取出719.52几种常用的Hash表9.52.5指标Hash表指标Hash表包括指标表与内容表两部分。9.52几种常用的Hash表9.52.5指标Hash729.17answer//SearchforanddeletetherecordwithKeyK(p311)template<classKey,classElem,classKEComp,classEEComp>boolhashdict<Key,Elem,KEComp,EEComp>::hashDelete(constKey&K,Elem&e)const{inthome;//HomepositionforKintpos=home=h(K);//Initialpositonprobesequencefor(inti=1;!KEComp::eq(K,HT[pos])&&!EEComp::eq(EMPTY,HT[pos]);i++)//Nextonprobesequencepos=(home+p(K,i))%M;if(KEComp::eq(K,HT[pos])){//Foundite=HT[pos];HT[pos]=TOMBSTONE;//Deleteit(p320)returntrue;}elsereturnfalse;//Knotinhashtable}9.17answer//Searchforand73

//InserteintohashtableHT(p311)template<classKey,classElem,classKEComp,classEEComp>boolhashdict<Key,Elem,KEComp,EEComp>::hashInsert(constElem&e){inthome;//Homepositionforeintpos=home=h(getkey(e));//Initprobesequencefor(inti=1;(!(EEComp::eq(EMPTY,HT[pos]))&&!(EEComp::eq(TOMBSTONE,HT[pos])));i++){pos=(home+p(getkey(e),i))%M;//Followprobesif(EEComp::eq(e,HT[pos]))returnfalse;//Dup}HT[pos]=e;//Insertereturntrue;}Thesearchfunctionneednotbechangedatall,sincetombstoneslotsshouldbetreatedasthoughtheyarefull.

74第9章查找技术9.1顺序查找9.2有序表的对分查找9.3分块查找9.4二叉排序树查找9.5hashing技术第9章查找技术9.1顺序查找759.1顺序查找9.1.1线性表在顺序存储下的顺序查找9.1.2线性链表的顺序查找9.1顺序查找9.1.1线性表在顺序存储下的顺序查找769.1顺序查找9.1.1线性表在顺序存储下的顺序查找(1)如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。9.1顺序查找9.1.1线性表在顺序存储下的顺序查找779.1顺序查找线性表在顺序存储结构下的顺序查找输入：线性表长度n以及线性表的存储空间V；

被查找的元素x。输出：被查找元素x在线性表中的序号k。

如果在线性表中不存在元素x，则输出k＝－1。PROCEDURESERCH(V，n，x，k)k＝1WHILE(k≤n)and(V(k)≠x)DOk＝k＋1IF(k＝n＋1)THENk＝－1RETURN9.1顺序查找线性表在顺序存储结构下的顺序查找789.1顺序查找/*函数返回被查找元素x在线性表中的序号，如果在线性表中不存在元素值x，则返回－1*/intserch(v，n，x)intn；ETv[]，x；/*ET为线性表数据类型*/{intk；k＝0；while((k＜n)&&(v[k]≠x))k＝k＋1；if(k＝＝n)k＝－1；return(k)；}9.1顺序查找/*函数返回被查找元素x在线性表中的序号，799.1顺序查找9.1.2线性链表的顺序查找9.1顺序查找9.1.2线性链表的顺序查找809.1顺序查找线性表在链式存储结构下的顺序查找输入：线性链表头指针HEAD以及存储空间V、NEXT；

被查找的元素x。输出：被查找元素x的结点在线性链表中的存储序号k。

如果在线性链表中不存在元素值为x的结点，则输出k＝－1。PROCEDURELSERCH(V，NEXT，HEAD，x，k)k＝HEADWHILE(k≠0)and(V(k)≠x)DOk＝NEXT(k)IF(k＝0)THENk＝－1RETURN9.1顺序查找线性表在链式存储结构下的顺序查找819.1顺序查找structnode{ETd；structnode*next；}；/*函数返回被查找元素x所在结点的存储地址，如果在线性链表中不存在元素值为x的结点，则返回NULL*/structnode*lserch(head，x)structnode*head；ETx；/*ET为线性链表中值域的数据类型*/{structnodek；k＝head；while((k≠NULL)&&(k－>d≠x))k＝k－>next；return(k)；}9.1顺序查找structnode829.2有序表的对分查找设有序线性表的长度为n，被查元素为x。将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。在最坏情况下，对分查找只需要比较log2n次，而顺序查找需要比较n次。9.2有序表的对分查找设有序线性表的长度为n，被查元素为839.2有序表的对分查找有序线性表在顺序存储结构下的对分查找输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存在元素x，则输出k＝－1。PROCEDUREBSERCH(V，n，x，k)i＝1；j＝nWHILE(i＜＝j)DO{k＝(i＋j)/2IF(V(k)＝x)THENRETURNIF(V(k)＞x)THENj＝k－1；ELSEi＝k＋1；}IF(i＞j)THENk＝－1RETURN9.2有序表的对分查找有序线性表在顺序存储结构下的对分查849.2有序表的对分查找intbserch(v，n，x)/*函数返回被查找元素x在线性表中的序号如果在线性表中不存在元素值x，则返回－1*/intn；ETx，v[]；{inti，j，k；i＝1；j＝n；while(i＜＝j){k＝(i＋j)/2；if(v[k－1]＝＝x)return(k－1)；if(v[k－1]＞x)j＝k－1；elsei＝k＋1；}return(－1)；}9.2有序表的对分查找intbserch(v，n，x859.3分块查找分块有序表将长度为n线性表分成m个子表，各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。分块有序表的结构可以分为两部分：(1)线性表本身采用顺序存储结构。(2)再建立一个索引表。在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。9.3分块查找分块有序表869.3分块查找structindnode{ETkey；/*数据域，存放子表中的最大值，其类型与线性表中元素的数据类型相同*/

intk；/*指针域，指示子表中第一个元素在线性表中的序号*/}；9.3分块查找structindnode879.3分块查找9.3分块查找889.3分块查找(1)首先查找索引表，以便确定被查元素所在的子表。由于索引表数据域中的数据是有序的，因此可以采用对分查找。(2)然后在相应的子表中用顺序查找法进行具体的查找。分块查找输入：长度为n的线性表L的存储空间V(1：n)；索引表中的数据域存储空间KEY(1：m)与指针域存储空间

K(1：m)；被查元素x。输出：被查元素x在线性表L中的序号j（即使L(j)＝x的j）。如果x不在线性表L中，则置j＝－1。9.3分块查找(1)首先查找索引表，以便确定被查元素所在899.3分块查找PROCEDUREINSERCH(V，n，KEY，K，m，x，j)i＝1；j＝mWHILE(j－i＞1)DO[对分查找索引表]{t＝(i＋j)/2IF(x≤KEY(t))THENj＝tELSEi＝t}IF(i≠j)and(x＞KEY(i))THENi＝jj＝K(i)；t＝nIF(i≠m)THENt＝K(i＋1)－1[确定顺序查找的终点]WHILE(j≤t)and(V(j)≠x)DOj＝j＋1[顺序查找子表]IF(j＞t)THENj＝－1RETURN9.3分块查找PROCEDUREINSERCH(V，909.3分块查找在分块查找中，为了找到被查元素x所在的子表，需要对分查找索引表，在最坏情况下需要查找log2(m＋1)次。在相应子表中用顺序查找法查找元素x，在最坏情况下需要查找n/m（假设各子表长度相等）次；而在平均情况下需要查找n/(2m)次。因此，分块查找的工作量为：在最坏情况下需要查找log2(m＋1)＋n/m次，平均情况下大约需要查找log2(m＋1)＋n/(2m)次。当m＝n时，线性表L即为有序表，分块查找即为对分查找当m＝1时，线性表L为一般的无序表，分块查找即为顺序查找。分块查找的效率介于对分查找和顺序查找之间。9.3分块查找在分块查找中，为了找到被查元素x所在的子表919.3分块查找structindnode{ETkey；/*数据域，存放子表中的最大值，其类型与线性表中元素的数据类型相同*/

intk；/*指针域，指示子表中第一个元素在线性表中的序号*/}；/*函数返回被查找元素x在线性表中的序号，如果在线性表中不存在元素值x，则返回－1*/

intinserch(v，n，s，m，x)intn，m；ETx，v[]；structindnodes[]；9.3分块查找structindnode929.3分块查找

{inti，j，t；i＝1；j＝m；while(j－i＞1)/*对分查找索引表*/{t＝(i＋j)/2；if(x＜＝s[t].key)j＝t；elsei＝t；}if((i!＝j)&&(x＞s[i].key))i＝j；j＝s[i].k；t＝n；if(i!＝m)t＝s[i＋1].k－1；/*确定顺序查找的终点*/

while((j＜＝t)&&(V[j]!＝x))j＝j＋1；/*顺序查找子表*/

if(j＞t)j＝－1；return(j)；}9.3分块查找{inti，j，t；939.4二叉排序树查找9.4.1二叉排序树及其构造9.4.2二叉排序树查找9.4二叉排序树查找9.4.1二叉排序树及其构造949.4二叉排序树查找9.4.1二叉排序树及其构造(1)左子树上的所有结点值均小于根结点值；(2)右子树上的所有结点值均不小于根结点值；(3)左、右子树也满足上述两个条件。9.4二叉排序树查找9.4.1二叉排序树及其构造959.4二叉排序树查找9.4二叉排序树查找969.4二叉排序树查找9.4二叉排序树查找979.4二叉排序树查找依次读入给定序列中的每一个元素：(1)若当前的二叉排序树为空，则读入的元素为根结点；(2)若读入的元素值小于根结点值，则将元素插入到左子树中；(3)若读入的元素值不小于根结点值，则将元素插入到右子树中。无论是插入到左子树还是右子树，同样按照上述方法处理。9.4二叉排序树查找依次读入给定序列中的每一个元素：989.4二叉排序树查找9.4二叉排序树查找999.4二叉排序树查找9.4二叉排序树查找1009.4二叉排序树查找插入元素689.4二叉排序树查找插入元素681019.4二叉排序树查找插入元素719.4二叉排序树查找插入元素711029.4二叉排序树查找插入元素779.4二叉排序树查找插入元素771039.4二叉排序树查找插入元素889.4二叉排序树查找插入元素881049.4二叉排序树查找二叉排序树的另一种形态9.4二叉排序树查找二叉排序树的另一种形态1059.4二叉排序树查找由无序序列构造二叉排序树输入：长度为n的无序序列A(1：n)。输出：二叉排序树的头指针BT。PROCEDUREINBSORT(A，n，BT)BT＝0FORk＝1TOnDO{NEW(p)[取得一个新结点]

V(p)＝A(k)；L(p)＝0；R(p)＝0j＝BTIF(j＝0)THENBT＝p[若二叉排序树为空]

ELSE[二叉排序树不空]9.4二叉排序树查找由无序序列构造二叉排序树1069.4二叉排序树查找

{WHILE(L(j)≠p)and(R(j)≠p)DO[未到叶子结点]{IF(A(k)＜V(j))THEN[插入到左子树]{IF(L(j)≠0)THENj＝L(j)ELSEL(j)＝p}ELSE[插入到右子树]{IF(R(j)≠0)THENj＝R(j)ELSER(j)＝p}}}}RETURN9.4二叉排序树查找{WHILE(L(j)≠1079.4二叉排序树查找#include"stdlib.h"/*malloc函数需要包含头文件stdlib.h*/structbtnode/*定义结点类型*/{ETd；/*数据域*/

structbtnode*lchild；/*左指针域*/

structbtnode*rchild；/*右指针域*/}；structbtnode*inbsort(a，n)/*函数返回二叉排序树头指针*/intn；ETa[]；{structbtnode*p，*q，*bt；intk；bt＝NULL；9.4二叉排序树查找#include"stdlib.1089.4二叉排序树查找

for(k＝0；k＜n；k＋＋){p＝(structbtnode*)malloc(sizeof(structbtnode))；p－>d＝a[k]；p－>lchild＝NULL；p－>rchild＝NULL；/*置新结点的数据域与左、右指针域*/

q＝bt；if(q＝＝NULL)bt＝p；/*二叉排序树为空*/

else/*二叉排序树不空*/{while((q－>lchild!＝p)&&(q－>rchild!＝p)){if(a[k]＜q－>d)/*插入到左子树*/{if(q－>lchild!＝NULL)q＝q－>lchild；elseq－>lchild＝p；}9.4二叉排序树查找for(k＝0；k＜n；k1099.4二叉排序树查找

else/*插入到右子树*/{if(q－>rchild!＝NULL)q＝q－>rchild；elseq－>rchild＝p；}}}}return(bt)；/*返回二叉排序树头指针*/}9.4二叉排序树查找else/*1109.4二叉排序树查找9.4.2二叉排序树查找从二叉排序树的根结点开始与被查值进行比较：(1)若被查值等于根结点值，查找成功，查找过程结束。(2)若被查值小于根结点值，则到左子树中去查找。(3)若被查值大于根结点值，则到右子树中去查找。在左、右子树中查找时也采用上述方法。查找过程直到查找成功或所考虑的子树已空为止。9.4二叉排序树查找9.4.2二叉排序树查找1119.4二叉排序树查找二叉排序树查找输入：二叉排序树头指针BT以及存储空间；被查元素x。输出：被查元素x在二叉排序树空间中的存储结点序号pPROCEDUREBSTSERCH(BT，x，p)P＝BTWHILE(p≠0)and(V(p)≠x)DO{IF(x＜V(p))THENp＝L(p)[沿左子树查找]

ELSEp＝R(p)[沿右子树查找]}RETURN9.4二叉排序树查找二叉排序树查找1129.4二叉排序树查找structbtnode/*定义结点类型*/{ETd；/*数据域*/

structbtnode*lchild；/*左指针域*/

structbtnode*rchild；/*右指针域*/}；9.4二叉排序树查找structbtnode1139.4二叉排序树查找/*函数返回被查值x所在结点的存储地址*/structbtnode*bstserch(bt，x)structbtnode*bt；ETx；{structbtnode*p；p＝bt；while((p!＝NULL)&&(p－>d!＝x)){if(x＜p－>d)p＝p－>lchild；/*沿左子树查找*/

elsep＝p－>rchild；/*沿右子树查找*/}

return(p)；}9.4二叉排序树查找/*函数返回被查值x所在结点的存储地1149.5Hash表技术9.5.1Hash表的基本概念9.5.2几种常用的Hash表9.5Hash表技术9.5.1Hash表的基本概念1159.5.1Hash表的基本概念9.51.1直接查找技术9.51.2Hash表9.51.3Hash码的构造9.5.1Hash表的基本概念9.51.1直接查找技1169.51Hash表的基本概念9.51.1直接查找技术设表的长度为n。如果存在一个函数i＝i(k)，对于表中的任意一个元素的关键字k，满足以下条件：(1)1≤i≤n；(2)对于任意的元素关键字k1≠k2，恒存在i(k1)≠i(k2)。则称此表为直接查找表。其中函数i＝i(k)称为关键字k的映象函数。9.51Hash表的基本概念9.51.1直接查找技术1179.51Hash表的基本概念1.直接查找表的填入要将关键字为k的元素填入到直接查找表，只需做以下两步：(1)计算关键字k的映象函数i＝i(k)；(2)将关键字k及有关元素信息填入到表的第i项。9.51Hash表的基本概念1.直接查找表的填入1189.51Hash表的基本概念2.直接查找表的取出要在直接查找表中取出关键字k的元素，也只需做以下两步：(1)计算关键字k的映象函数i＝i(k)；(2)检查表中第i项：若第i项为空，则说明表中没有关键字为k的元素；否则取出第i项中的元素即可。9.51Hash表的基本概念2.直接查找表的取出1199.51Hash表的基本概念9.51.2Hash表9.51Hash表的基本概念9.51.2Hash表1209.51Hash表的基本概念例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的表中。设映象函数为i＝INT(k/3)＋1。9.51Hash表的基本概念例1219.51Hash表的基本概念设表的长度为n。如果存在一个函数i＝i(k)，对于表中的任意一个元素的关键字k，满足1≤i≤n，则称此表为Hash表。其中函数i＝i(k)称为关键字k的Hash码。(1)构造合适的Hash码，以便尽量减少表中元素冲突的次数。即Hash码的均匀性要比较好。(2)当表中元素发生冲突时，要进行适当的处理。9.51Hash表的基本概念1229.51Hash表的基本概念9.51.3Hash码的构造(1)使各关键字尽可能均匀地分布在Hash表中，即Hash码的均匀性要好，以便减少冲突发生的机会。(2)Hash码的计算要尽量简单。9.51Hash表的基本概念9.51.3Hash码的1239.51Hash表的基本概念1.截段法

2.分段叠加法

3.除法

i＝mod(k，n)4.乘法

i＝mod(k*φ，n)φ一般取0.618033988747，或0.6125423371，或0.6161616161。9.51Hash表的基本概念1.截段法1249.52几种常用的Hash表9.52.1线性Hash表9.52.2随机Hash表9.52.3溢出Hash表9.52.4拉链Hash表9.52.5指标Hash表9.52几种常用的Hash表9.52.1线性Hash1259.52几种常用的Hash表9.52.1线性Hash表开放法9.52几种常用的Hash表9.52.1线性Hash1269.52几种常用的Hash表1.线性Hash表的填入将关键字k及有关信息填入线性Hash表的步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)检查表中第i项的内容：若第i项为空，则将关键字k及有关信息填入该项；若第i项不空，则令i＝mod(i＋1，n)，转(2)继续检查。只要Hash表尚未填满，最终总可以找到一个空项，将关键字k及有关信息填入到Hash表中。9.52几种常用的Hash表1.线性Hash表的填入1279.52几种常用的Hash表2.线性Hash表的取出要在线性Hash表中取出关键字k的元素，其步骤如下：(1)计算关键字k的Hash码i＝i(k)。(2)检查表中第i项的内容：若第i项登记着关键字k，则取出该项元素即可；若第i项为空，则表示在Hash表中没有该关键字的信息；若第i项不空，且登记的不是关键字k，则令

i＝mod(i＋1，n)，转(2)继续检查。9.52几种常用的Hash表2.线性Hash表的取出1289.52几种常用的Hash表例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的线性Hash表中。设Hash码为i＝INT(k/3)＋1。9.52几种常用的Hash表例1299.52几种常用的Hash表缺点：(1)在线性Hash表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当Hash码的冲突较多时，在线性Hash表中会存在“堆聚”现象，即许多关键字被连续登记在一起，从而会降低查找效率。(2)在线性Hash表的填入过程中，处理冲突时会带来新的冲突。9.52几种常用的Hash表1309.52几种常用的Hash表9.52几种常用的Hash表1319.52几种常用的Hash表9.52.2随机Hash表9.52几种常用的Hash表9.52.2随机Hash1329.52几种常用的Hash表1.随机Hash表的填入将关键字k及有关信息填入随机Hash表的步骤如下：(1)计算关键字k的Hash码i0＝i(k)。且令i＝i0。(2)伪随机数序列初始化，令j＝1（即将取随机数指针指向伪随机数序列中的第1个随机数）。(3)检查表中第i项的内容：若第i项为空，则将关键字k及有关信息填入该项；若第i项不空，则令i＝mod(i0＋RN(j)，n)，并令

j＝j＋1（即将取随机数指针指向下一个随机数），转(3)继续检查。其中RN(j)表示伪随机数序列RN中的第j个随机数。9.52几种常用的Hash表1.随机Hash表的填入1339.52几种常用的Hash表伪随机数序列RN按下列方法产生：

R＝1FORj＝1TOnDO{R＝mod(5*R，4n)RN(j)＝INT(R/4)}9.52几种常用的Hash表伪随机数序列RN按下列方法产1349.52几种常用的Hash表例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝24＝16的随机Hash表中。设Hash码为i＝INT(k/3)＋1。伪随机数序列为：1，6，15，12，13，2，11，8，9，14，7，4，5，10，3，0。9.52几种常用的Hash表例1359.52几种常用的Hash表2.随机Hash表的取出要在随机Hash表中取出关键字k的元素，其步骤如下：(1)计算关键字k的Hash码i0＝i(k)。且令i＝i0。(2)伪随机数序列初始化，令j＝1（即将取随机数指针指向伪随机数序列中的第1个随机数）。(3)检查表中第i项的内容：若第i项登记着关键字k，则取出该项元素即可；若第i项空，则表示在Hash表中没有该关键字信息；若第i项不空，且登记的不是关键字k，则令

i＝mod(i0＋RN(j)，n)，