数据结构(第八章-查找)

数据结构第8章查找主要内容8.1查找的基本概念8.2二分法查找8.3基于索引表的分块查找8.4散列8.5二叉排序树和平衡二叉树查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素(因有同名同姓的人)，而考号可以唯一标识一个数据元素(每个考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。8.1查找的基本概念——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录

(预先确定的记录的某种标志)

——可以唯一标识一个记录的关键字例如“学号”例如“女”是一种数据结构——识别若干记录的关键字8.1查找的基本概念因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为内查找；反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内查找。8.1查找的基本概念查找条件、查找操作和查找结果查找条件：数据元素（包含关键字key）。查找操作：比较元素相等，T类的equals(Object)

查找结果：查找成功，查找不成功。查找是删除、替换等操作的基础8.1查找的基本概念（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。

（3)有哪些查找方法？

查找方法取决于表中数据的排列方式;讨论：（1）查找的过程是怎样的？

给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。例如查字典针对静态查找表和动态查找表的查找方法也有所不同。“特定的”=关键字8.1查找的基本概念明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：averagesearchlength）。其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。统计意义上的数学期望值物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。（4）如何评估查找方法的优劣？å=×=niiiCPASL18.1查找的基本概念针对静态查找表的查找算法主要有：

一、顺序查找（线性查找）二、二分查找（二分或对分查找）三、分块查找（索引顺序查找）线性表查找8.1查找的基本概念顺序查找（sequentialsearch，又称线性查找--linearsearch）即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。

对顺序结构如何线性查找？对单链表结构如何线性查找？对非线性树结构如何顺序查找?顺序查找8.1查找的基本概念顺序查找的基本思想顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。顺序查找的存储结构要求8.1查找的基本概念8.1查找的基本概念顺序查找顺序表查找的算法实现线性表的顺序查找intsearch(Tkey)//顺序表SeqList<T>Node<T>search(Tkey)//SinglyList<T>DoubleNode<T>search(Tkey)//CirDoublyList<T>8.1查找的基本概念非线性表的顺序查找BinaryNode<T>search(Tkey)//BinaryTree<T>TreeNode<T>search(Tkey)//Tree<T>顺序表查找的算法实现8.1查找的基本概念优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL太长，时间效率太低。讨论：顺序查找的特点：讨论

：如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n=(1+n)n/2未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1这是查找成功的情况若求某一个元素的平均查找次数，还应当除以n（等概率），即：ASL＝（1＋n）/2，时间效率为O(n)顺序查找8.1查找的基本概念顺序查找8.1查找的基本概念排序线性表的顺序查找算法及效率//排序线性表，覆盖，采用T类的compareTo(T)方法（实现java.lang.Comparable<T>接口）比较对象相等和大小。intsearch(Tkey)//SortedSeqList<T>Node<T>search(Tkey)//SortedSinglyList<T>DoubleNode<T>search(Tkey)

//SortedCirDoublyList<T>8.1查找的基本概念提高查找效率的措施基本原则是缩小查找范围。数据元素排序：以事先准备时间换取查找时间。排序线性表建立索引：以空间换取时间。字典采用顺序存储结构，事先按字母排序并建立多级索引。散列存储建立二叉排序树8.1查找的基本概念这是一种容易想到的查找方法:先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。对顺序表结构如何编程实现二分查找算法？

对单链表结构如何二分查找？对非线性(树)结构如何二分查找？

8.2二分法查找②运算步骤：(1)low=1,high=11,mid=6，待查范围是[1,11]；(2)若ST.elem[mid].key<key，说明key[mid+1,high]，则令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>

key，说明key[low,mid-1]，则令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high≤low

（意即区间长度小于0）解：①先设定3个辅助标志:

low,high,mid，二分查找举例：Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置

已知如下11个元素的有序表：

（0513192137566475808892）,请查找关键字为21和85的数据元素。显然有：mid=(low+high)/2二分查找演示8.2二分法查找二分查找：（1）mid=(low+high)/2」

（2）比较ST.elem[mid].key==key?

如果ST.elem[mid].key==key，则查找成功，返回mid值如果ST.elem[mid].key>key，则置high=mid-1

如果ST.elem[mid].key<key，则置low=mid+1(3)重复计算mid以及比较ST.elem[mid].key与key，当low>high时，表明查找不成功，查找结束。8.2二分法查找二分查找举例8.2二分法查找二分查找算法实现publicclassSortedArray{//已知value数组元素按升序排序，在begin～end范围内，二分法查找关键字为key元素，若查找成功返回下标，否则返回-1；若begin、end越界，返回-1publicstatic<TextendsComparable<?superT>>

intbinarySearch(T[]value,intbegin,intend,Tkey)

publicstatic<TextendsComparable<?superT>>intbinarySearch(T[]value,Tkey)}8.2二分法查找publicstaticintcount=0;//统计比较次数，计算ASL成功

//已知value数组元素按升序排序，在begin～end范围内，二分法查找关键字为key元素，若查找成功返回下标，否则返回-1；

//若begin、end越界，返回-1。若key==null，Java抛出空对象异常。

publicstatic<TextendsComparable<?superT>>intbinarySearch(T[]value,intbegin,intend,Tkey){count=0;//统计比较次数，计算ASL成功

while(begin<=end)//边界有效

{intmid=(begin+end)/2;//取中间位置，当前比较元素位置

System.out.print("["+mid+"]="+value[mid]+"？");//显示比较中间结果，可省略

count++;if(pareTo(value[mid])==0)//两对象相等

returnmid;//查找成功

if(pareTo(value[mid])<0)//key对象较小

end=mid-1;//查找范围缩小到前半段

elsebegin=mid+1;//查找范围缩小到后半段

}return-1;//查找不成功

}//已知value数组元素按升序排序，二分法查找关键字为key元素，若查找成功返回下标，否则返回-1publicstatic<TextendsComparable<?superT>>intbinarySearch(T[]value,Tkey){returnbinarySearch(value,0,value.length-1,key);}二分查找算法实现8.2二分法查找【思考题8-1】二分查找的递归算法publicstaticintbinarySearch(int[]value,intkey,intbegin,intend){if(begin<=end)

{intmid=(begin+end)/2;

if(value[mid]==key)returnmid;

if(key<value[mid])

returnbinarySearch(value,key,begin,mid-1);

returnbinarySearch(value,key,mid+1,end);

}return-1;}8.2二分法查找查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的二分查找的判定树是唯一的，即：判定树由表中元素个数决定。

找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。

比较的关键字个数：为该结点在判定树上的层次数。二分查找效率分析法8.2二分法查找二叉判定树二分查找算法分析8.2二分法查找查找成功的情形查找不成功的情形从有序表构造出的二叉查找树(判定树)

若设n=2h-1，则描述对分查找的二叉查找树是高度为h

的满二叉树。2h=n+1,h=log2(n+1)。第1层结点有1个，查找第1层结点要比较1次；第2层结点有2个，查找第2层结点要比较2次；…，8.2二分法查找查找成功时比较的关键字个数最多不超过树的深度d:d=log2n+1

若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。

查找不成功的过程就是走了一条从根结点到外部结点的路径。二分查找效率分析法8.2二分法查找习题8-9二分法查找{5,17,20,32,43,55,61,61*,72,96}，查找96、35、61，分别与哪些元素比较？画出相应的二叉判定树，计算和。查找96，比较{43,61*,72,96}查找35，比较{43,17,20,32}8.2二分法查找习题8-9二分法查找首次出现元素查找61，比较{43,61*}查找72*，比较{43,72}8.2二分法查找分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。索引表最大关键字起始地址2212138920334244382448605874498653第1块第2块第3块例：2248861713特点：块间有序，块内无序8.3基于索引表的分块查找索引与分块查找索引项完全索引表不完全索引分块查找查找索引表在一块中查找key8.3基于索引表的分块查找查找步骤分两步进行：①对索引表使用二分查找法（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找效率：ASL=Lb+Lw对索引表查找的ASL对块内查找的ASLS为每块内部的记录个数，n/s即块的数目例如当n=9，s=3时，ASLbs=3.5,而二分法为3.1,顺序法为58.3基于索引表的分块查找字典的分块查找【例8.1】判断一个字符串是否为Java关键字。8.3基于索引表的分块查找PublicclassKeyWordprivatestaticString[]keywords={"abstract","boolean",……};

//排序主表privatestaticclassIndexItemimplementsComparable<IndexItem>//索引项{charfirst;//首字符

intbegin,end;//块的始末下标

publicIndexItem(charfirst,intbegin,intend)

publicStringtoString()publicintcompareTo(IndexItemitem)比较相等和大小}privatestaticIndexItem[]index;//索引表static//创建扩充索引表；静态初始化块，类加载时执行一次publicstaticbooleanisKeyword(Stringstr)//判断str是否关键字8.3基于索引表的分块查找支持插入和删除操作的索引结构及其分块查找（1）以排序顺序表存储缺点：顺序查找插入或删除，移动8.3基于索引表的分块查找各块分散存储，链式索引缺点：块满，扩容8.3基于索引表的分块查找块单链表存储8.3基于索引表的分块查找考虑：如果边查找边插入删除（动态查找），采用以上方法有什么缺点？？？如何解决？？？线性查找

8.3基于索引表的分块查找

在线性表、树结构中查找纪录是通过与关键字的“比较”完成的：顺序查找，比较的结果为“=”或“≠”非顺序查找，比较的结果为“<”，“=”，“>”

散列的思想：根据纪录的关键字直接找到记录的存储位置，即为关键字和记录的存储位置建立一个对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。对应关系f为散列函数，按该思想建立的表为散列表。散列技术（HASH）8.4散列

根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为纪录在表中的存储位置，这种表便称为哈希表，这一影像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。哈希（HASH）表的定义：8.4散列散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系Hash()，使每个关键字与结构中一个唯一存储位置相对应：

Address＝Hash(Rec.key)在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，依相同函数计算存储位置，并按此位置存放。8.4散列选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。哈希方法(杂凑法)哈希函数(杂凑函数)哈希表(杂凑表)

冲突哈希方法中使用的转换函数称为哈希函数(杂凑函数)按上述思想构造的表称为哈希表(杂凑表)

8.4散列有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=kmod7通过哈希函数对6个元素建立哈希表：253923914冲突现象举例：6个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有冲突！01234568.4散列散列函数与冲突散列函数i=hash(key)冲突8.4散列（装填因子通常取值0.75）所以，哈希方法必须解决以下两个问题：1）构造好的哈希函数（a）所选函数尽可能简单，以便提高转换速度；（b）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。8.4散列哈希函数的构造方法常用的哈希函数构造方法有：直接定址法除留余数法

乘余取整法数字分析法平方取中法折叠法随机数法要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。8.4散列Hash(key)=a·key+b(a、b为常数)优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。

例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：01234567899008007005003001001、直接定址法8.4散列哈希函数的构造方法Hash(key)=keymodp(p是一个整数)特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取p≤m且为质数

（也可以是不包含小于20质因子的合数）。2、除留余数法散列表长度8163264128256最大素数71331611272518.4散列哈希函数的构造方法Hash(key)=B*(A*keymod1)

(A、B均为常数，且0<A<1，B为整数)特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。3、乘余取整法（A*keymod1）就是取A*key的小数部分例：欲以学号最后两位作为地址，则哈希函数应为：

H(k)=100*(0.01*k%1)其实也可以用法2实现：H(k)=k%1008.4散列哈希函数的构造方法特点：某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。34705243491487348269634852703486305349805834796713473919例：有一组（例如80个）关键码，其样式如下：4、数字分析法讨论：①第1、2位均是“3和4”，第3位也只有“

7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号：①②③④⑤⑥⑦②

若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。8.4散列哈希函数的构造方法特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。理由：因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。5、平方取中法8.4散列哈希函数的构造方法6、折叠法特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。适用于：每一位上各符号出现概率大致相同的情况。法1：移位法──将各部分的最后一位对齐相加。法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。例：元素42751896,用法1：427＋518＋96=1041

用法2：42751896—>724+518+69=13118.4散列哈希函数的构造方法7、随机数法Hash(key)=random(key)(random为伪随机函数)适用于：关键字长度不等的情况。造表和查找都很方便。8.4散列哈希函数的构造方法①执行速度（即计算哈希函数所需时间）；②关键字的长度；③哈希表的大小；④关键字的分布情况；⑤查找频率。小结：构造哈希函数的原则：8.4散列哈希函数的构造方法常见的冲突处理方法有：开放定址法（开地址法）链地址法（拉链法）再哈希法（双哈希函数法）建立一个公共溢出区8.4散列冲突处理1、开放定址法（开地址法）设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。具体实现：Hi=(Hash(key)+di)modm(1≤i<m)

其中：

Hash(key)为哈希函数

m为哈希表长度

di

为增量序列1，2，…m-1，且di=i1.线性探测法含义：一旦冲突，就找附近（下一个）空地址存入。开放定址法建立散列表演示8.4散列冲突处理关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=keymod11；拟用线性探测法处理冲突。建哈希表如下：解释：①47、7（以及11、16、92）均是由哈希函数得到的没有冲突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8为空，因此将29存入。③

另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。其中3

还连续移动了两次（二次聚集）8.4散列冲突处理线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。讨论：8.4散列冲突处理仍举上例，关键码集为{47，7，29，11，16，92，22，8，3}改用二次探测法处理冲突，建表如下：012345678910112234792167298△▲△△注：只有3这个关键码的冲突处理与上例不同，Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)+12)mod11=4，仍然冲突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。2.二次探测法Hi=(Hash(key)±di)modm其中：Hash(key)为哈希函数

m为哈希表长度，m要求是某个4k+3的质数；

di为增量序列

12，-12，22，-22，…，q2

3.若di＝伪随机序列，就称为伪随机探测法8.4散列冲突处理2、链地址法(拉链法）基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

设{47,7,29,11,16,92,22,8,3,50,37,89}的哈希函数为：Hash(key)=keymod11，用拉链法处理冲突，则建表如右图所示。

例：

01234567891022118934737922971650810注：有冲突的元素可以插在表尾,也可以插在表头8.4散列冲突处理链地址法散列数组同义词单链表计算i=hash(key)，O(1)

查找插入删除8.4散列冲突处理图8.12（a）链地址法散列表（a）散列表满，元素个数=散列表容量×装填因子8.4散列冲突处理图8.12（b）

散列表扩充容量（b）添加10，扩充散列表容量为原2倍，各元素重新存储8.4散列冲突处理习题8-12散列表采用链地址法设初始容量length为10；散列函数hash(key)=key%length；装填因子为0.75，散列数组容量以2倍扩充。关键字序列{16,75,60,43,54,90,46,31,27,88,64,50}构造散列表，分别画出扩容前和最终状态图，计算。8.4散列冲突处理习题解答8-128.4散列冲突处理3、再哈希法（双哈希函数法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。优点：不易产生聚集；缺点：增加了计算时间。4.建立一个公共溢出区思路：除设立哈希基本表外，另设立一个溢出向量表。 所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。8.4散列冲突处理构造链地址法的散列表publicclassHashSet<T>//散列表类{privateSinglyList<T>[]table; //散列表，同义词单链表对象数组

publicHashSet(intlength)

publicHashSet()

privateinthash(Tx)//散列函数

publicTsearch(Tkey)//查找

publicbooleanadd(Tx)

//插入publicvoidremove(Tkey)//删除}【思考题8-3】实现contains(key)、toString()等。8.4散列T类定义对象的散列码privateinthash(Tx)//散列函数{intkey=Math.abs(x.hashCode());//对象散列码returnkey%this.table.length;}publicclassObject{inthashCode()//对象散列码，约定对象到int的一对一映射}publicfinalclassInteger

//子类{publicinthashCode()//整数对象散列码是其值，覆盖

{returnvalue;}}8.4散列【例8.2】使用散列表表示元素互异的集合

//产生n个互异的随机数publicstaticInteger[]randomDifferent(intn,intsize){Integer[]values=newInteger[n];HashSet<Integer>set=newHashSet<Integer>();//互异，查找不成功时插入set}8.4散列散列映射映射映射（Map）是指实现数学中“映射”概念的集合。元素结构结构如下，关键字不能重复。映射元素（关键字，值）提供从关键字到值的映射功能，即根据关键字查找值。8.4散列映射接口Map<K,V>

//映射接口，K、V指定映射元素的关键字和值的数据类型publicinterfaceMap<K,V>{booleanisEmpty();//判空

int

size();//元素个数

StringtoString();//描述字符串

Vget(Kkey);//关键字key映射的值

Vput(Kkey,Vvalue);//添加元素(键,值)；关键字相同，替换

Vremove(Kkey);//删除关键字为key元素

booleancontainsKey(Kkey); //包含

voidclear();//删除所有元素

Object[]values();//返回包含值集合的数组}8.4散列散列映射的实现publicclassKeyValue<K,V>//映射元素类{finalKkey;//关键字，最终变量

Vvalue;//值

publicKeyValue(Kkey,Vvalue)publicStringtoString()//描述串“(关键字,值)”publicfinalinthashCode()//散列码publicbooleanequals(Objectobj)//仅比较关键字}8.4散列散列映射类//散列映射类，实现Map<K,V>接口publicclassHashMap<K,V>implementsMap<K,V>{HashSet<KeyValue<K,V>>set;//散列表publicHashMap(intlength)publicHashMap()publicbooleanisEmpty()//判空publicVget(Kkey)//关键字key映射的值publicVput(Kkey,Vvalue)//添加映射元素publicVremove(Kkey)//删除publicHashSet<K>keySet()//返回关键字集合}8.4散列【例8.3】采用散列映射，统计文本中各字符的出现次数Huffman算法已知给定文本的字符集合和权值集合。设字符串为“classHash”，8.4散列

例给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、散列查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及两种散列查找的散列表)，并求出每一种查找的成功平均查找长度。散列函数H(k)=k%11。顺序查找的顺序表（一维数组）如图9-8所示，从图9-8可以得到顺序查找的成功平均查找长度为：ASL=(1+2+3+4+5+6+7+8)/8=4.5；8.4散列二分查找的判定树（中序序列为从小到大排列的有序序列）如图9-9示，从图9-9可以得到二分查找的成功平均查找长度为：ASL=(1+2*2+3*4+4)/8=2.625；8.4散列二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图9-10所示，从图9-10可以得到二叉排序树查找的成功平均查找长度为：ASL=(1+2*2+3*2+4+5*2)=3.125；8.4散列线性探查法解决冲突的散列表如图9-11所示，从图9-11可以得到线性探查法的成功平均查找长度为：ASL=（1+1+2+1+3+2+1+8）/8=2.375；8.4散列10^4^3^278^11^21^1012345678910拉链法解决冲突的散列表如图9-12所示。从图9-12可以得到拉链法的成功平均查找长度为：ASL=(1*6+2*2)/8=1.25。图9-12拉链法的散列表8.4散列一、二叉排序树（Binary Sort Tree）的定义（a）（b）练：下列2种图形中，哪个不是二叉排序树？--或是一棵空树；或者是具有如下性质（BST性质）的非空二叉树：

（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于或等于根的值；（3）它的左右子树也分别为二叉排序树。讨论：对(a)中序遍历后的结果是什么？二叉排序树8.5二叉排序树和平衡二叉树二、二叉排序树的特点由BST性质可得：元素可比较相等和大小，关键字互不相同。结点，左子树元素均小于该结点，右子树元素均大于该结点。左、右子树也是二叉排序树。中根次序遍历，升序序列。二叉排序树8.5二叉排序树和平衡二叉树【思考题8-4】画出关键字序列为{1,2,3}的所有形态的二叉排序树。//答见教案二叉排序树8.5二叉排序树和平衡二叉树将1～9填入如图所示的二叉树中，构造一棵二叉排序树，计算。习题8-19二叉排序树8.5二叉排序树和平衡二叉树三、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：①查找过程与顺序结构有序表中的二分查找相似，查找效率高；②中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；③如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！——这种既查找又插入的过程称为动态查找。二叉排序树既有类似于二分查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。二叉排序树8.5二叉排序树和平衡二叉树4524531290如果待查找的关键字序列输入顺序为：（24，53，45，45，12，24，90），2453451290查找成功，返回查找成功，返回讨论1：二叉排序树的插入和查找操作则生成二叉排序树的过程为：例：输入待查找的关键字序列=（45，24，53，45，12，24，90）则生成的二叉排序树形态不同：查找成功，返回查找成功，返回二叉排序树8.5二叉排序树和平衡二叉树二叉排序树的构造过程：从空树出发，依次插入R1～

Rn各数据值：（1）如果二叉排序树是空树，则插入结点就是二叉排序树的根结点；（2）如果二叉排序树是非空的，则插入值与跟结点比较，若小于根结点的值，就插入到左子树中去；否则插入到右子树中。算法实现：不要求二叉排序树8.5二叉排序树和平衡二叉树二叉排序树的查找&插入算法如何实现？查找算法静态查找算法动态查找算法（插入）二叉排序树8.5二叉排序树和平衡二叉树二叉排序树的静态查找思想：从根开始若key==p.data，则查找成功返回；若key<p.data，则查找p的左子树；否则查找p的右子树。重复执行②，直到p为空，查找不成功。二叉排序树8.5二叉排序树和平衡二叉树二叉排序树8.5二叉排序树和平衡二叉树二叉排序树的动态查找算法查找算法：若二叉排序树为空，则返回插入位置，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤。插入算法：若二叉排序树为空，则被查结点为新的根节点；否则，作为一个新的叶子结点插入在由查找返回的位置上。算法：不做要求二叉排序树8.5二叉排序树和平衡二叉树插入40二叉排序树8.5二叉排序树和平衡二叉树构造二叉排序树{54,18,12,81,99,36,12,76,57,6,66,40}二叉排序树8.5二叉排序树和平衡二叉树习题8-20画出由以下关键字序列构造的一棵二叉排序树，计算。{50,16,74,60,43,16,90,46,31,29, 88,71,64,13,65}二叉排序树8.5二叉排序树和平衡二叉树二叉树的三叉链表结点类publicclassTriNode<T>{publicTdata;

publicTriNode<T>parent,left,right;

publicTriNode(Tdata,TriNode<T>parent,TriNode<T>left,TriNode<T>right)

publicTriNode(Tdata)publicTriNode()publicStringtoString()publicbooleanisLeaf()}二叉排序树8.5二叉排序树和平衡二叉树二叉排序树类publicclassBinarySortTree<TextendsComparable<?superT>>{TriNode<T>root;//根

BinarySortTree()//构造空树BinarySortTree(T[]values)booleanisEmpty()TriNode<T>searchNode(Tkey)//查找结点Tsearch(Tkey)//查找元素booleanadd(Tx)//插入}二叉排序树8.5二叉排序树和平衡二叉树中根次序迭代遍历TriNode<T>first(TriNode<T>p)TriNode<T>next(TriNode<T>p)StringtoString()二叉排序树8.5二叉排序树和平衡二叉树【思考题8-5】BinarySortTree<T>类的成员方法voidinorderPrevious()//中根次序遍历（逆序）TriNode<T>last(TriNode<T>p)//p子树最后一个结点TriNode<T>previous(TriNode<T>p)//p的前驱结点booleancontains(Tkey)//判断否包含keyvoidaddAll(T[]values)//插入values数组元素voidclear() //删除所有元素intsize() //元素个数Object[]toArray()//包含所有元素的数组二叉排序树8.5二叉排序树和平衡二叉树【例8.4】使用二叉排序树表示互异的排序集合

//产生n个互异的排序的随机数，范围是0～size-1，返回二叉排序树

publicstaticBinarySortTree<Integer>random(intn,intsize)二叉排序树8.5二叉排序树和平衡二叉树（1）p是叶子结点

（2）p是1度结点，删除12、36二叉排序树删除二叉排序树8.5二叉排序树和平衡二叉树（3）p是2度结点，删除54；插入54publicTremove(Tkey)二叉排序树删除二叉排序树8.5二叉排序树和平衡二叉树二叉排序树的查找性能分析二叉排序树