大学教程(零起点)数据结构-查找

第九章查找9.1基本概念9.2线性表的查找9.3树上的查找9.4散列技术1基本概念集合：是一种逻辑结构，其特点是元素之间没有逻辑关系，元素只是共处于一个集合当中。集合的操作：插入删除查找2查找：是指在数据元素集合中查找满足某种条件的数据元素。查找表：称用于查找的数据集合为查找表。查找表由同一类型的数据元素所构成，在查找表的结构中每一个数据元素称为查找对象。关键字：其中应当有一个属性，其值可以唯一地标识这个数据元素基本概念3仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类:内查找外查找4根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）

若查找表中存在这样一个记录，则称“查找成功”，给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，给出“空记录”或“空指针”。查找平均查找长度59.2线性表的查找1顺序查找2有序表上的二分查找3索引顺序表上的分块查找61顺序表上的查找顺序查找是一种最简单的查找方法基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。71顺序表上的查找利用一段连续内存存储待查找数据key其他信息N个数据Maxsize个100位置不存数据8顺序表的类型定义typedefstruct{KeyTypekey;//key为关键字InfoTypeotherinfo；//其他信息}NodeType;typedefNodeTypeSeqList[n+1];

SeqListR;//问：R的内存中有什么信息？9key其他信息N个数据n个1查找时，假设要查找数据为K，则将K存入0位置即：R[0].key=K;从i=n位置开始，当R[i].key<>K,i--向前找查找结束后i即为要找的位置问题：若找到了，i值为？未找到，i值为？？R10key其他信息N个数据n个1查找时，假设要查找数据为K，则将K存入0位置即：R[0].key=K;从i=n位置开始，当R[i].key<>K,i--向前找查找结束后i即为要找的位置R11顺序查找的平均查找长度：Ｐi为查找第i个元素的概率Ｃi为查找第i个元素所用到的比较次数。顺序查找的时间复杂度：O（n）122,有序表上的查找策略：选中间点比较，缩小查找范围二分查找，也称折半查找，是一种高效率的查找方法。但要求表中元素必须按关键字有序(升序或降序，现设表中元素为升序排列)。13查找key=16的过程[3101623263853]lowhighmid1234567]14二分查找的基本思想是：将待查元素K与有序表中点上的元素R[mid].key进行比较，若相等，则查找成功；若k>R[mid].key，则在大于的区间继续查找；若k<R[mid].key，则在小于的区间继续查找。通过每比较一次，查找区间的长度就缩小一半，如此不断进行下去，直到查找成功或失败。15key其他信息highn个lowRmid16二分查找的算法intbinsearch(R,K){low=1;high=n;while(low<=high){mid=(low+high)/2;if(K==R[mid].key)returnmid;if(K<R[mid].key)high=mid-1;if(K>R[mid].key)low=mid+1；}return0；}17二分查找的判定树6391425781011判定树12233334444二分查找判定树的深度与

n个结点的完全二叉树深度一样18二分查找的平均查找长度：

假设结点数为n，则其判定树深度为k=log2n+1

则深度为1的1个结点

深度为2的2个

深度为3的4个

深度为k的2k-1个

假设为等概率情况，则二分查找的平均查找长度：log2n193索引顺序表上的查找分块查找22488606122212138920334244382448605874498653顺序表索引表分块：将一个主表分成n个子表，分块有序：要求子表之间按关键字有序，块内无序：子表中元素可以无序的，建立索引表：用每个子表最大关键字和指示块中第一个记录在表中位置建立索引表。20分块查找的查找过程22488606122212138920334244382448605874498653顺序表索引表21分块查找的效率分析b是索引表长度（块数），s是块长度分块查找的时间复杂度：O（索引表查找+块内查找）索引表内查找：可以利用顺序、折半查找块内查找：顺序查找221.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)/2B.n/2C.(n+1)/2D.n习题C232.对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序B243.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减D254.分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成_________块最好：若分成25块，其平均查找长度为_________。即要计算x=n/s的值即当平均查找长度最小时，计算得到s的值，即可即对其求导数f’（s）=0时即可求得s值=30269.3树上的查找属于动态查找，查找过程改变了原查找表二叉排序树，定义如下：或者是一棵空树，或者是具有如下特征的非空二叉树：1)若其左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；

2)若其右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字；

3)左、右子树本身又都是一棵二叉排序树。27二叉排序树中序遍历的结果是一个递增的序列。20

40815

530

101020119

5306否是28图中二叉排序树的各结点的值为1～9，标出各结点的值29已知二叉排序树10个结点值依次为1-10，其结构如图所示，试标出该二叉树各结点所对应得具体值。3050308020908540358832查找关键字==50,505035,503040355090,5080909531二叉排序树上的查找思想

若二叉排树为非空，先拿根结点值与待查值进行比较，①若相等，则查找成功；②若根结点值大于待查值，则进入左子树继续查找，③否则，进入右子树继续查找；若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找失败。32构造二叉排序树二叉排序树的插入二叉排序树的形态与结点插入顺序有关根据动态查找表的定义，“插入”操作在查找不成功时才进行；33构造二叉排序树二叉排序树的插入基本思想为：new为待插入结点若二叉排序树为空，将new结点作为根结点；非空时，若树中已有此结点，无须插入若new关键字小于树根关键字，左子树中，否则将new插到右子树中34将33插入到如下的二叉排序树中36125282640661829361226293335将56插入到如下的二叉排序树中39331750925621628563350623632.给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。39142286528882967131037二叉排序树的删除被删除的结点是叶子结点被删除的结点只有左子树或者只有右子树被删除的结点既有左子树，也有右子树38（1）被删除的结点是叶子结点50308020908540358832被删关键字=8820其双亲结点中相应指针域的值改为“空”3950302040809085883532（2）被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。被删关键字=804040503080209085883532（3）被删除的结点既有左子树，也有右子树40方式1：以其中序前驱替代被删除结点，然后再删除该前驱结点被删关键字=5041503080209085883532（3）被删除的结点既有左子树，也有右子树40方式1：以其中序前驱替代被删除结点，然后再删除该前驱结点被删关键字=504236425080908588（3）被删除的结点既有左子树，也有右子树3020353240被删关键字=50方式2：p为被删除结点P的左孩子代替p，p原来的右孩子做原来左孩子的最右侧孩子43平衡二叉树(AVL树)若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。平衡因子：结点的左、右子树高度差-1,0,1548254821是平衡树不是平衡树4445构造二叉平衡（查找）树的方法是：按照构造二叉排序树的方法进行构造，出现不平衡时，进行旋转调整321231LL型RR型312321LR型RL型四种不平衡形态465020有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树3547设结点A为不平衡的最小子树根结点，设结点B为插入结点，对该子树进行平衡化调整的规则如下：1）从A开始，在A到B的路径上连续选取三个结点作为调整对象；2）将三个结点按关键字值由小到大排序，取中间结点作为新根结点，较小结点作为其左孩子，较大结点作为其右孩子；3）若根结点在调整前有左孩子，调整后将其作为现有左孩子的右孩子；若根结点在调整前有右孩子，调整后将其作为现有右孩子的左孩子。48有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树502035502035809049有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树802035509050203580903285408850有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树8020355090328540888020355085328840903051有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树802035508532884090308030355085328840902052有数据序列：{20，50，35，80，90，32，85，40，88，30}请按顺序构造一棵二叉平衡树8030355085328840902053有数据序列：{15，20，11，8，14，13}请按顺序构造一棵二叉平衡树2011151413815111454设结点A为不平衡的最小子树根结点，设结点B为插入结点，对该子树进行平衡化调整的规则如下：1）从A开始，在A到B的路径上连续选取三个结点作为调整对象；2）将三个结点按关键字值由小到大排序，取中间结点作为新根结点，较小结点作为其左孩子，较大结点作为其右孩子；3）若新根结点在调整前有左孩子，调整后将其作为现有左孩子的右孩子；若根结点在调整前有右孩子，调整后将其作为现有右孩子的左孩子。55有数据序列：{15，20，11，8，14，13}请按顺序构造一棵二叉平衡树1420151181313平衡调整过程56有数据序列：{15，20，11，8，13，14}请按顺序构造一棵二叉平衡树2011151314815111357有数据序列：{15，20，11，8，14，13}请按顺序构造一棵二叉平衡树1320151181414平衡调整过程58设结点A为不平衡的最小子树根结点，设结点B为插入结点，对该子树进行平衡化调整的规则如下：1）从A开始，在A到B的路径上连续选取三个结点作为调整对象；2）将三个结点按关键字值由小到大排序，取中间结点作为新根结点，较小结点作为其左孩子，较大结点作为其右孩子；3）若新根结点在调整前有左孩子，调整后将其作为现有左孩子的右孩子；若根结点在调整前有右孩子，调整后将其作为现有右孩子的左孩子。59B树分为B-树和B+树1．B-树的定义m阶B-树，或为空树，或为m叉树满足：1）树中每个结点至多有m棵子树；2）若根结点不是叶子结点，则至少有两棵子树；3）除根结点之外的所有非终端结点至少有m/2棵子树；B-树60B树分为B-树和B+树1．B-树的定义m阶B-树，或为空树，或为m叉树满足：4）所有的非终端结点中包含以下信息数据：（n，P0，K1，P1，K2，…，Kn，Pn）n为关键字的个数Pi为指向子树根结点的指针Ki为关键字，且Ki<Ki+1，，Pi-1所指子树中所有结点的关键字均小于KiPn所指子树中所有结点的关键字均大于Knm/2-1<=n<=m-161B树分为B-树和B+树，这里主要介绍B_树的查找和插入。1．B-树的定义m阶的B-树，或为空树，或为m叉树满足：5）所有的叶子结点都出现在同一层次上，并且不带信息（实际上这些结点不存在）622．B-树的运算1)B-树的查找B-树的查找和二叉排序树的查找相类似B-树每个结点上是多关键字的有序表，首先把根结点取出，在根结点所包含的关键字K1,…Kn中查找给定的关键字(顺序查找\折半查找)，若找到，则查找成功；否则，到子树中去查找，到达叶子结点时，查找失败。632．B-树的运算2)B-树的插入首先要经过查找过程，查找出K的插入位置，然后再进行插入。

关键字的插入是在最底层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成；否则，若该结点的关键字个数已达到m个，这与B-树定义不符，将引起结点的“分裂”。642．B-树的运算2)B-树的插入若插入新数据后，结点关键字个数已达到m个，这与B-树定义不符，将引起结点的“分裂”。分裂方法为：将结点中的关键字分成三部分，使得前后两部分关键字个数均大于等于m/2-1，而中间部分只有一个关键字。前后两部分成为两个结点，中间部分的关键字将插入到父结点中。若中间部分关键字插入父结点后，父结点中关键字个数超过m-1，则父结点继续分裂，直到插入某个父结点，其关键字个数小于m。65在e结点中插入40，插入后e结点中关键字个数为1<=2<=4，仍然符合B-树定义。m/2-1<=n<=m-1此处m=466679.4散列技术1散列表的概念2散列函数的构造3冲突解决方法4散列表上的计算5开散列表和闭散列表的比较68静态查找表和动态查找表的特点是：要经过一系列的关键字比较查找所需时间总是与比较次数有关。如果将记录的存储位置与它的关键字之间建立一个确定的关系H，使每个关键字和一个唯一的存储位置对应，在查找时，只需要根据对应关系计算出给定的关键字值k对应的值H(k)，就可以得到记录的存储位置这就是哈希表查找方法的基本思想。69若以下标为000-999的顺序表表示之。例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。70散列表的基本概念散列又称哈希（Hash）以结点的关键字k为自变量，通过一个确定的函数H，计算出对应的函数值H(k)，作为结点的存储位置，将结点存入H(k)所指的存储位置上。将关键字值转换成存储地址的函数:关键字为K的记录所在位置为＝H(K)给定一个关键字K即可计算得到一个记录位置71散列表的基本概念将关键字值转换成存储地址的函数:关键字为K的记录所在位置为＝H(K)给定一个关键字K即可计算得到一个记录位置用哈希法存储的线性表叫做哈希表。上述的H函数称为哈希函数。H(k)称为哈希地址。基于这种存储结构的查找称为哈希查找。72{Zhao,Qian,Sun,Li,Wu,Chen,Han}设哈希函数H(key)=首字母序/2例如：对于如下7个关键字261719122338ZhaoQianSunLiWuChenHan12345678910111213进行查找时，只要根据给定关键字，然后利用H函数，即可计算得到关键字所在位置查找方便73{Zhao,Qian,Sun,Li,Wu,Chen,Han,zhou}设哈希函数H(key)=首字母序/2例如：对于如下7个关键字261719122338ZhaoQianSunLiWuChenHan12345678910111213同义词:若H(k1)==H(k2),则K1，K2对于H称为同义词此时H(k1)==H(k2),说明K1和K2应存入相同位置，此情况称为冲突74散列表的两个问题：1，如何构造均匀的散列函数2，如何解决冲突75相乘取整法除余法平方取中法随机数法2散列函数的构造762.除余法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key%p，pm772.除余法已知一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79}则按哈希函数H（key）=key%13构造所得的哈希表HT[0..14]。0123456789101112131419142301682084275511107978当发生冲突时，在散列表中按某地址序列进行探查，直到遇到开放的地址为止（即该内存单元未被占用）3冲突的处理方法：1）开放定址法探查未被占用单元79闭散列表（开放定址）基本思想所有元素存储在散列表数组中经散列函数计算出来的地址称为基地址每个键值K生成一个散列地址序列d0，d1…dm-1d0=H（K）,之后地址为后继散列地址若插入K时，d0已占用则在按该序列探测找到第一个未被占用的地址存入，若全部地址被占用则散列表溢出探测下一存储位置的策略：线性探测法二次探测法80对K键值计算H（K）=d设散列表容量为m，则后继散列地址为：

d+1，d+2，…m-1，0，1，2，…d-1如此探测可能出现非同义词争夺同一个地址的现象，称为“堆积”，又称“二次聚集”线性探测法8101234563047523634设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=kmod6，采用线性探测法解决冲突，要求：（7分）1）构造散列表；

2）求查找数34需要的比较次数。H（30）=30mod6=0H（36）=36mod6=0H（47）=47mod6=5H（52）=52mod6=4H（34）=34mod6=4查找34时，首先计算H（34）=34mod6=4比较散列空间4位置比较散列空间5位置比较散列空间6位置查找成功共比较3次8201234566832255048H（25）=25mod7=4H（48）=48mod7=6H（32）=32mod7=4H（50）=50mod7=1H（68）=68mod7=5查找34时，首先计算H（68）=68mod6=5比较散列空间5位置比较散列空间6位置比较散列空间0位置查找成功共比较3次已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：(1)构造一散列表，用线性探测法解决有关地址冲突；(2)若要用该散列表查找元素68，给出所需的比较次数。83对K键值计算d0

=

H（K）设散列表容量为m，则后继散列地址为：

d1=（d0+12）modmd2=（d0-12）modmd3=（d0-22）modmd4=（d0-22）modm……………二次探测法84多重散列法公共溢出去法简单了解85开散列表设有H（K）计算得到的地址范围0..m-1设置一个“地址向量”

HP[m]每个HP[i]指向一个单链表该单链表中存放散列地址为i的同义词，即该单链表称为一个同义词子表

3冲突的处理方法：2）开散列（链地址、拉链法）86地址向量和同义词子表，此法也称“拉链法”012345678910111213141914230168208427551110798701234567891011121314191423已知一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79}按哈希函数H（key）=key%13和开散列法处理冲突构造所得的哈希表HT[0..14]头插法8801234567891011121314141923已知一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79}按哈希函数H（key）=key%13和开散列法处理冲突构造所得的哈希表HT[0..14]016820头插法89012345678910111213141923已知一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79}按哈希函数H（key）=key%13和开散列法处理冲突构造所得的哈希表