算法与数据结构课件查找

第7章查找7.1根本概念与术语7.2静态查找表7.3动态查找表7.4哈希表7.5典型例题17.1根本概念与术语—以图书信息表为例书号 书名 作者 出版社 定价015010C程序设计谭浩强清华大学出版社 26.00 015024 数据结构严蔚敏清华大学出版社22.00 015025 离散数学左孝凌上海科学技术文献出版社14.00 015080计算机操作系统汤子瀛西安电子科技大学出版社24.00

关键码：表中的每个数据元素有假设干属性〔项〕，某个项或组合项的值就称为关键码，它可以标识一个数据元素。主关键码：能唯一标识一个数据元素的关键码。其他的属性那么称为次关键码。查找结果唯一查找结果不唯一27.1根本概念与术语查找表用于查找的数据集合。具有同一类型的数据元素〔或记录〕组成的集合。对查找表进行的操作查询某个“特定的〞数据元素是否在查找表中；检索某个“特定的〞数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素；根据操作的不同，查找表可分为：静态查找表：仅对查找表进行前两种操作，不能被改变；动态查找表：除进行“查找〞操作外，可能还要向表中插入数据元素或删除数据元素，可以被改变。3根本概念查找：根据给定的某个值，在查找表中确定一个其关键码等于给定值的数据元素〔或记录〕。查找成功：查找表中存在满足条件的数据元素；查找结果为：整个记录的信息，或指示该记录在查找表中的位置；查找不成功：查找表中不存在满足条件的数据元素；查找结果为：“空记录〞或者“空指针〞。4平均查找长度〔AverageSearchLength〕:与给定值进行比较的关键码个数的期望值衡量查找算法性能的主要依据对于长度为n的查找表，查找成功时的平均查找长度为：平均查找长度()表中记录的个数找到第i个记录时，需要进行的比较次数查找第i个记录的概率5查找表中的元素是无序的，元素间不存在逻辑关系。为了查找的方便，需在数据元素间人为地加上一些关系，即以另一种数据结构来表示查找表。组织查找表的方法静态查找表〔线性表、索引结构〕动态查找表〔树表〕哈希表〔散列表〕

6静态查找表上的三种查找方法：

(1)顺序查找

(2)折半查找

(3)分块查找7.2静态查找表77.2.1静态查找表结构以顺序表作为存储结构#defineMaxSize100//表中最多记录个数typedefstruct{ KeyTypekey; ∥关键码字段…… ∥其他字段}ElemType;typedefstruct{ElemTypedata[MaxSize+1];intlength; }SqList;8从表的一端开始，顺序扫描线性表，依次将扫描到的关键码与给定值kx相比较；假设相等，那么查找成功，给出数据元素在表中的位置；假设整个表检测完，仍未找到与kx相等的关键码，那么查找失败，给出失败信息。7.2.2顺序查找intSeqSearch1(SqListL,KeyTypekx){i=1;while(i<=L.length&&L.data[i].key!=kx)i++;if(i<=L.length)returni;elsereturn0;}教材有误9顺序查找中使用监测哨intSeqSearch2(SqListL，KeyTypekx){∥在顺序表L中顺序查找关键码为kx的数据元素，成功那么∥返回其位置，失败返回0，注：0号单元用作监视哨 L.data[0].key=k；∥设置监测哨 for(i=L.length；L.data[i].key!=kx；i--)； ∥从表尾向前查找 returni；}10关键码之间的比较次数取决于所查记录在表中的位置。假设查找表中第1个记录，仅需比较一次；而查找表中最后一个记录时，需比较n次。查找成功时，顺序查找的平均查找长度为：思考：不成功时的平均查找长度是多少？顺序查找的平均查找长度=11顺序查找总结优点：算法简单且适用面广。对表的结构无任何要求，无论记录是否按关键字有序均可应用，而且上述所有讨论对线性链表也同样适用。缺点:平均查找长度较大，特别是当n很大时，查找效率低。

12又称为二分查找，要求线性表中的数据元素按关键码升序或降序排列。思想：取中间位置的元素作为比较对象；假设给定值与中间位置元素的关键码相等，那么查找成功；假设给定值小于中间元素的关键码，那么在左半区继续查找；假设给定值大于中间元素的关键码，那么在右半区继续查找；不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败；7.2.3有序表的折半查找13例如:key=64的查找过程lowhighmidlow

mid

high

midlow指示查找区间的下界;high指示查找区间的上界;mid=(low+high)/214查找关键码为18的数据元素031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhighhighlow15intBinary_Search(SqListL，KeyTypekx){/*在表L中查找关键码为kx的数据元素，假设找到返回该元素在表中的位置，否那么，返回0*/ intmid,low,high； low=1；high=L.length；/*①设置初始区间*/ while(low<=high)/*②表空测试*/ {/*非空，进行比较测试*/ mid=(low+high)/2；/*③得到中点*/ if(kx==L.data[mid].key) return(mid)；/*查找成功*/ if(kx<L.data[mid].key)high=mid-1；/*调整到左半区*/ elselow=mid+1；/*调整到右半区*/ } return0;}折半查找的算法16折半查找的递归算法intSearchBin2(RecTyper[n+1],KeyTypek,intlow,inthigh){∥在有序表r[1..n]中递归折半查找关键字为k的结点，成功那么返回∥数据元素的位置，失败返回0if(low>high)return0;mid=(low+high)/2;if(k==r[mid].key)returnmid;∥找到待查元素elseif(k>r[mid].key)returnSearchBin2(r,k,mid+1,high);∥继续在后半区间查找elsereturnSearchBin2(r,k,low,mid-1);∥继续在前半区间查找}∥SearchBin217折半查找过程可用二叉树来描述：把当前查找区间的中间位置上的记录作为根；左子表和右子表中的记录分别作为根的左子树和右子树。9个结点的判定树判定树〔比较树〕52713684918带外部结点的判定树527136849-11-22-35-66-77-83-44-58-99-19对于给定11个数据元素的有序表{2,3,10,15,20,25,28,29,30,35,40}，采用折半查找，试问：(1)假设查找给定值为20的元素，将依次与表中哪些元素比较？(2)假设查找给定值为26的元素，将依次与哪些元素比较？(3)假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度。举例20(2)假设查找给定值为26的元素,依次与25,30,28元素比较,共比较3次。(3)在查找成功时,会找到图中某个圆形结点,那么成功时的平均查找长度：(1)假设查找给定值为20的元素,依次与表中25,10,15,20元素比较,共比较4次。在查找不成功时,会找到图中某个方形结点,那么不成功时的平均查找长度：21折半查找总结优点：效率比顺序查找高比较次数少，查找速度快，平均性能好缺点：要求查找表有序仅限于顺序存储结构22237.2.4分块查找又称索引顺序查找，是对顺序查找的改进。将顺序表分成假设干个子表B1、B2、…、Bn，并要求当i<j时，Bi中记录的关键码都小于Bj中记录的关键码。记录的这种排列方式称为分块有序。分块之后，另建一个线性表，称为索引表。每个子表在索引表中有一项，称为索引项。索引项中包括两个域，一个域存放子表中的最大关键码，另一个域存放子表的第一个记录在线性表中的位置。最大关键字255689起始地址1611

10525201856342932476872618489索引表24分块查找例如索引表最大关键字255689起始地址1611

10525201856342932476872618489步骤①确定待查记录所在的子表：用给定值kx在索引表中检测索引项，依次与索引表中的关键码进行比较。可用顺序查找法或折半查找法进行。②在相应子表内进行顺序查找，查找关键码为kx的记录。25分块查找性能分析平均查找长度假设用顺序查找确定所在的块：假设用折半查找确定所在的块：平均查找长度不仅和表的总长度有关，而且和所分的子表的个数有关。26静态查找表总结顺序查找适用于任何线性表，但效率较低；分块查找不需要对全部的数据元素排序，它的插入删除在块内进行，由于不要求有序，操作比较容易，其主要代价是增加一个辅助数组的存储空间和将初始顺序表分块排序的操作；折半查找效率最高，但要求查找表有序且顺序存储，故插入删除时必须移动元素，这种由移动元素引起的额外时间开销，就会抵消折半查找的优点。也就是说，折半查找只适用于静态查找表。假设要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。27二叉排序树：或者是一棵空树，或者是具有以下性质的二叉树：假设左子树不空，那么左子树上所有结点的关键码值均小于根结点的关键码值；假设右子树不空，那么右子树上所有结点的关键码值均大于根结点的关键码值；左、右子树也都是二叉排序树。7.3动态查找表30125332394187189中序遍历序列为：3，12，18，23，30，53，71，89，9428二叉排序树的查找过程假设二叉排序树为空，那么查找失败；否那么：1〕假设给定值等于根结点的关键码值，查找成功；2〕假设给定值小于根结点的关键码值，那么继续在左子树上进行查找；3〕假设给定值大于根结点的关键码值，那么继续在右子树上进行查找；2950308020908540358832查找关键字50,505035,503040355090,5080909530用二叉链表存储二叉排序树typedefstructBiTNode{ElemTypedata;∥数据元素structBiTNode*lchild,*rchild;

∥左、右孩子指针}BiTNode,*BiTree;

31二叉排序树非递归查找算法BSTreeSearchBST2(BSTreet,KeyTypek){//在根指针t所指二叉排序树中非递归查找某关键字//等于k的数据元素，假设查找成功，那么返回指向//该数据元素结点的指针，否那么返回空指针p=t;while(p!=NULL&&p->key!=k){if(k<p->key)p=p->lchild;elsep=p->rchild;}returnp;}//SearchBST232intsearchBST(BiTreeT,KeyTypekx,BiTree*p,BiTree*q){/*在二叉排序树T上查找关键码为kx的元素，假设找到，返回1，且p指向该结点，q指向其父结点；否那么，返回0，且q指向查找失败的最后一个结点*/ *p=T; while(*p) /*从根结点开始查找*/ { if((*p)->data.key==kx) return1; else if((*p)->data.key>kx)/*kx大于当前结点*q的元素关键码*/ {*q=*p;*p=(*p)->lchild;}/*将当前结点*q的右子女置为新根*/ else {*q=*p;*p=(*p)->rchild;}/*将当前结点*q的左子女置为新根*/ } return0;}33intsearchBST_rc(BiTreeT,KeyTypekx,BiTree*p,BiTree*q){/*在二叉排序树T上查找关键码为kx的元素，假设找到，返回1；且p指向该结点，q指向其父结点，否那么，返回0，且q指向查找失败的最后一个结点*/if(!T)return0;elseif(kx==T->data.key){p=T;return1;}elseif(kx<T->data.key)searchBST_rc(T->lchild,kx,p,&T);elsesearchBST_rc(T->rchild,kx,p,&T);}二叉排序树递归查找算法34二叉排序树的查找分析123456425136二叉排序树的平均查找长度是O()

最好情况：二叉排序树的形态和折半查找的判定树相同最坏情况：二叉排序树为单支树，和顺序查找相同35二叉排序树的插入步骤：〔1〕假设二叉排序树是空树，那么k成为二叉排序树的根；〔2〕假设二叉排序树非空，那么将k与二叉排序树的根进行比较，如果k的值等于根结点的值，那么停止插入；如果k的值小于根结点的值，那么将k插入左子树；如果k的值大于根结点的值，那么将k插入右子树。36二叉排序树的插入351545504025102030插入新结点2828插入新结点4242插入在查找的根底上进行；每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶子结点插入。37二叉排序树的插入算法voidinsertBST(BiTree*T,KeyTypekx){/*在二叉排序树*T上插入关键码为kx的结点*/BiTreep,q,s; p=q=NULL;if(!searchBST(*T,kx,&p,&q));//插入在查找不成功时进行{s=(BiTree)malloc(sizeof(BiTNode));/*申请结点，并赋值*/s->data.key=kx;s->lchild=NULL;s->rchild=NULL;if(!*T)*T=s; /*向空树中插入时*/else{if(q->data.key>kx)q->lchild=s;/*插入结点为q的左孩子*/elseq->rchild=s; /*插入结点为q的左孩子*/}}}3839从空二叉树开始，每读入一个元素，就建立一个新的结点，调用插入算法将它插入到当前已生成的二叉排序树中。二叉排序树的创立123532264520(g)(b)32(c)3226(d)322645(a)ø32264535(e)3226451235(f)序列:32,26,45,35,12,20,1240一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。解：生成的二叉排序树如右图所示。举例41void

CreateBST(BiTree

*T)/*从键盘输入元素的值，创立相应的二叉排序树*/{KeyTypekx;

*T=NULL;

scanf("%d",&kx);

while(kx!=ENDKEY)

/*EDNKEY为自定义常量*/

{

insertBST(T,kx);

scanf("%d",&kx);

}}二叉排序树的创立算法〔略〕42平衡二叉树〔AVL树〕形态匀称的二叉排序树，使平均查找长度接近最小平衡因子：结点的左、右子树深度之差平衡二叉树：或者是一棵空二叉树，或者是具有以下性质的二叉树：二叉树中任一结点的平衡因子的绝对值不超过1即平衡二叉树中每个结点的平衡因子只能取-1，0，101-1001-11010043不平衡的二叉树例如210-1001-20100044构造平衡二叉树插入一个结点时，首先检查是否破坏了树的平衡性，如果因插入结点破坏了二叉排序树的平衡，那么找出其中的最小不平衡子树。最小不平衡子树离插入结点最近，且平衡因子的绝对值大于1的祖先结点，因为此结点失去平衡，使得该结点的祖先结点也可能随之失去平衡。所以，失衡后应该调整以该结点为根的子树。45方法：在插入过程中，采用平衡旋转技术例如:依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转构造平衡二叉树LLRL46426589426895向左旋转一次继续插入关键字9RR构造平衡二叉树47总结以上讨论的各种查找表的共同特点：数据元素的存储位置和它的关键码之间不存在确定的关系，查找时需要进行一系列对关键码的比较；查找算法建立在比较的根底上，平均查找长度不为零对于频繁使用的查找表，希望ASL=0只有一个方法：预先知道所查关键码在表中的位置即要求：数据元素的存储位置和其关键码之间存在一种确定的关系。487.4.1哈希表与哈希方法哈希表(HashTable)又称散列表，是除顺序存储结构、链式存储结构和索引存储结构之外的又一种存储线性表的存储结构。哈希函数：将关键码值转换成存储位置的函数，又称散列函数。addr(Ri)＝H(key)哈希表：根据哈希函数建立的表；其根本思想是：以记录的关键码值为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容。当对记录进行查找时，再根据给定的关键码值，用同一个哈希函数计算出给定关键码值对应的存储地址，随后进行访问。哈希表即是一种存储形式，又是一种查找方法，通常将这种查找方法称为哈希查找。7.4哈希表49对于两个关键字ki和kj(i≠j),有ki≠kj(i≠j),但H(ki)=H(kj)。这种现象称为哈希冲突。冲突：不同的关键码映射到了同一个地址上的现象。同义词：映射到同一哈希地址上的关键码。同义词冲突是很难防止的。哈希方法需要解决两个问题：如何构造哈希函数？如何处理冲突？冲突的概念50好的哈希函数函数本身要便于计算，尽可能简单，以便提高转换速度；对关键码计算出的地址，应大致均匀分布，以尽可能减少冲突常用的哈希函数的构造方法有：直接定址法除留余数法数字分析法平方取中法折叠法7.4.2常用的哈希函数构造方法511、直接定址法取关键码的某个线性函数值为哈希地址。即

H(key)=a*key+b

其中a，b为常数，调整a与b的值可以使哈希地址取值范围与存储空间范围一致。【举例】解放后每年出生人口的调查表。H(key)=key+(-1949)地址01…51年份19491950…2000人数…………522、除留余数法取关键码除以p的余数作为哈希地址：h(key)=keymodp通常p取小于等于哈希表长的最大素数。如表长为12，那么p可取11，假设关键字为22，18，9，35，那么对应哈希地址为0，7，9，2。533、数字分析法抽取关键字中某几位随机性较好的数位，然后把这些数位拼接起来作为哈希地址。所抽取的位数取决于哈希表的表长。有如下关键字：〔设哈希表长度为100〕8046532680722426808136578013655780587657可取关键字的3、4位〔5、6位〕或4位+6位的值作为哈希地址。544、平方取中法取关键字平方后的中间几位为哈希地址。由于平方后的中间几位数与原关键字的每一位数字都相关，只要原关键字的分布是随机的，以平方后的中间几位数作为哈希地址一定也是随机分布。〔下例设哈希表长为512=29〕标识符关键字(关键字)2哈希地址A01000010000010I11001210000210J12001440000440I011601370400370P120614310541310P220624314704314555、折叠法折叠法是将较长的关键字从左到右分割成位数相同的几段(最后一段的位数可以少一些)，然后把这几段叠加并舍去进位，得到的结果作为哈希地址。有两种叠加的方法：移位叠加和间界叠加。例如：关键字从左到右按3个位数一段分割，共得到5个段。12320324111220699+移位叠加：12330224121120897+间界叠加：567.4.3处理冲突的方法解决冲突的实际含义是：为产生冲突的关键字寻找下一个哈希地址解决方法开放定址法拉链法〔链地址法〕两种方法的区别是：发生冲突的元素是存储在相同数组空间的另外一个地址里〔闭散列〕还是数组空间之外〔开散列〕的其他空间571.开放定址法根本思想：把所有的元素存储在哈希表数组中每个元素经哈希函数计算出来的地址称为基地址。如果要插入一个元素x，而x的基地址已被某个同义词占用，那么根据某种策略将x存储在数组的另一个位置。探测：冲突发生时，在冲突位置的附近寻找可存放记录的“下一个〞空位置的过程Hi＝(H(key)+di)％mi=1,2,…,k(k≤m-1)线性探测法、二次探测法、双哈希函数探测法58线性探测法根本思想：当发生冲突时，从冲突位置的下一个单元顺序寻找可存放记录的空单元，只要找到一个空位，就把元素放入此空位中。顺序查找时，我们把哈希表看成一个循环表，即如果到最后一个位置也没有找到空单元，那么回到表头开始继续查找。此时，如果仍然未找到空位，那么说明哈希表已满，需要进行溢出处理。di的取值为：1，2，3，…，m-159关键字集合

{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11(表长=11)190123145568假设采用线性探测法处理冲突118236112136251012345678910线性探测法例如ASLsucc＝〔1＋1+2+1＋3+6+2+5+1〕/9=22/9ASLunsucc＝〔10＋9+8+7+6+5+4+3+2+1+1〕/11=56/11600123456

198268

1436

01

ASLsucc

=(6×1+2×2+3)/9=13/9{19,01,23,14,55,68,11,82,36}表长为7，H(key)=keyMOD7所有哈希地址相同的记录链接在同一链表中

23

11

552.拉链法〔链地址法〕ASLunsucc＝〔2＋3+2+1+2+4+2〕/7=16/761散列表的查找及分