数据结构与算法（Java语言版）课件 第11-13章 集合HashSet类、常用算法与Collections类、图论

第10章散列表与HashMap类2024/11/9110.1散列结构的特点2024/11/92生活中有些数据之间可能是密切相关的一对，例如，一副手套，一双鞋子，一对夫妻等，即数据的逻辑结构是成对的，即不是线性也不是树形结构，一对数据与另一对数据之间也无须有必然的关系。如何存储这样的数据对，也是数据结构非常关心的，以下要介绍的散列结构，就是存储“数据对”的最重用的手段之一.2024/11/9310.1散列结构的特点●散列结构与散列表数据对，也称作"键-值"对，键和值都是某种类的实例，即对象。叙述时可以把这"键-值"对记作(key,value)，称key是关键字、value是键值或值。散列结构使用两个集合存储对象，一个集合称作关键字集合，记作Key。另一个是值的集合，记作Value。Key集合中的节点（或称元素）负责存储关键字，所有关键字对应的全部值称作散列结构的值集合，记作Value，即Value中的节点负责存储值。称Value为散列结构中的散列表（hash表，也常常被音译称作哈希表）。简单说，散列结构是根据关键字直接进行访问数据的数据结构，其核心思想是使用散列函数（hash()函数）把关键字映射到散列表中一个位置，即映射到散列表中的某个节点。2024/11/9410.1散列结构的特点●散列结构与散列表hash()函数本质上就是集合Key到整数集合

2024/11/9510.1散列结构的特点●散列结构与散列表对于一个关键字，比如key1，如果hash(key1)=98，那么key1关键字对应的节点就是数组hashValue第98个元素，即hashValue[98]。2024/11/9610.1散列结构的特点●散列结构与散列表一个散列函数，即hash()函数需保证下列两点：①

对于不同的关键字，比如，key1，key2是Key中两个节点，即两个关键字，一定有hash(key1)不等于hash(key2)，即hash(key1)和hash(key2)是两个不同的节点。但节点中的对象可能是相同的（数组的两个不同的元素中的值可能是相同的）。②为了保证第①点，让hash()函数映射出的全部节点，分散地分布在一块连续的内存中，这也是人们把Value称作一个散列表的原因。由于散列表中的节点是随机、分散分布的，所以我们不在散列表上定义任何关系（见第1章）。散列表或散列二字不是指数据之间的关系，而是形容存储形式的特点（hash()函数映射存储位置）。如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。2024/11/9710.1散列结构的特点●散列结构与散列表如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。可以用链接法解决冲突，散列函数把和关键字key有相同对应的值的那些关键字所对应的存储位置依次设置为一个链表的中不同的节点（链表头节点是key对应的存储位置），这样一来，就会增大查询Value中值的时间复杂度。如果散列函数设计的合理，那么一般不会发生关键字冲突或发生关键字冲突的概率非常小，因此也就不需要使用链式方法解决冲突或使用链式方法解决冲突的概率很小。链接法是最后保证不同关键字对应的不同节点（不同的存储位置）的最后办法。2024/11/9810.1散列结构的特点●查找、添加、删除的特点由散列结构的特点可以知道，使用关键字查找、删除、添加Value中的节点，时间复杂度通常都是

（如果关键字冲突，使用了链接法）散列结构具有数组的优点，即非常快的查询速度，同时又将查询数据（Value）的索引分离到另一个独立的集合中（Key）。数组最大的缺点就是将索引（下标）和数组元素绑定，因此，一旦创建数组，就无法更改索引，即无法再改变数组的长度。而散列结构可以随时添加一个“键-值”对（一个关键字，一个相应的值），或删除一个“键-值”对。10.2简单的散列函数2024/11/99通过简单的例子：停车场，进一步理解散列结构，后面我们将使用Java的HashMap类实现的散列结构。2024/11/91010.2简单的散列函数●顺序扩建停车位当Value中节点的数目越来越多时，比如达到总内存大小的一半时，就要重新调整内存，即分配新的数组，并把原数组hashValue[]的值复制到新的数组中，新的数组成为Value的新的一块连续内存。汽车停车场（模拟散列表）初始状态有10个连续的车位，相当于散列结构中分配给散列表Value的一块连续的内存空间（数组的长度是10）。假设汽车的车牌号是3位数的正整数，相当于散列结构中的Key集合中节点里的关键字。停车场可以根据需要，随时顺序地扩大停车场，即连续地扩建停车位。

2024/11/91110.2简单的散列函数●顺序扩建停车位

2024/11/91210.2简单的散列函数●顺序扩建停车位每当一辆车来到停车场，如果用散列函数计算了若干次，得到的车位号对应的车位上都是已经停放了车辆，这个时候，就扩建停车场、让其容量增加2倍，然后再用散列函数计算车位号……，如此这般，只要内存足够大，总能找到停车位，如图所示意。由于用散列函数的算法是随机的，所以，某个时刻以后，扩建停车场的概率就很小了。2024/11/91310.2简单的散列函数●链式扩展停车位当用散列函数计算出同样的车位数时，比如都是9，就把二者的停车位分别指定为同一个链表中的不同的两个节点，链表的头节点是数组的第9个元素。2024/11/91410.2简单的散列函数例子1Key.javaExample10_1.java例子1中的ParkingOne类使用顺序办法增加停车场的车位，ParkingTwo类使用链式办法增加停车场的车位。Car.javaParkingOne.javaParkingTwo.java例子1中的主类Example10_1模拟了两个停车场的停车情况。10.3HashMap类2024/11/915HashMap<K,V>泛型类继承Map泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了Map泛型接口中的抽象方法。HashMap<K,V>泛型类的对象为散列表,散列表的Key集合是实现Set接口的一个实例，Key集合中不允许有两个结点中的对象相同，即大小一样的两个结点，Key中不同的key对应的Value中的节点是不同的，但Value中的节点中的对象，即数据可以是相同的，就像数组的不同元素（节点）里可以存放相同的数据。HashMap<K,V>泛型类提供的添加、删除、查找等操作的时间复杂度都是O(1).2024/11/91610.3HasMap类HashMap<K,V>泛型类直接实现了Map接口，注意，没有实现SortedMap接口。2024/11/91710.3HasMap类例子2Example10_2.java声明一个HashMap<K,V>泛型类的对象，即散列表，必须要指定Key和Value的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定Key中节点里的对象的类型和Value中节点里的对象的类型。例如，指定K是String类型、V是Car类型，例如：HashMap<String,Car>hashMap=newHashMap<>();或HashMap<String,Car>hashMap=newHashMap<String,Car>();Car.java例子2中的主类Example10_2中首先创建一个空散列表hashMapOne，然后向散列表hashMapOne添加4个”键-值”对，随后再用hashMapOne创建另一个散列表hashMapTwo。10.4散列表的基本操作2024/11/918publicVput(Kkey,Vvalue)向散列表添加”键-值”对，即将key存储在Key中，把value放置在Value中，如果添加成功返回null。需要注意的是，如果散列表Key中已经有了键key，那么当前添加的”键-值”对将替换已存在的”键-值”对，并返回旧”键-值”对中的value值，即返回被替换的”键-值”对的值。publicVputIfAbsent(Kkey,Vvalue)如果散列表Key中没有key，则添加该键值对(key,value)到散列表，并返回null，如果散列表Key中已经有键key，则返回旧key对应的value(不做添加操作)。10.4散列表的基本操作2024/11/919publicVget(Objectkey)返回”键-值”对(key,value)中的value，如果key不在集合Key中，方法返回null。publicbooleancontainsKey(Objectkey)判断Key中是否有关键字key，有返回true，否则返回false。publicbooleancontainsValue(Objectvalue)判断Value中是否有value，有返回true，否则返回false。publicbooleanisEmpty()如果散列表中没有任何"键-值"对，则返回true，否则返回false。10.4散列表的基本操作2024/11/920publicVremove(Objectkey)删除关键字key组合的”键-值”对(key,value)，并返回value。publicVreplace(Kkey,Vvalue)如果散列表Key已有key，就用(key,value)替换已有的key组合的”键-值”对，并返回替换后的value，如果Key中没有关键字key，不进行替换操作，并返回null。publicvoidclear()删除散列表的全部”键-值”对。2024/11/92110.4散列表的基本操作例子3Example10_3.java例子3的主类Example10_3使用了HashMap<K,V>泛型类的一些常用方法。10.5遍历散列表2024/11/922publicvoidforEach(BiConsumer<?superK,?superV>action)对散列表中的所有(key,value)执行给定的action操作，直到所有(key,value)对都被处理或操作引发异常。BiConsumer是一个函数接口，该接口里的抽象方法是voidaccept(Kk,Vv)。使用forEach()方法时将一个Lambda表达式传递给action，例如：（k,v）->{System.out.println(v);}。forEach()方法将Lambda表达式中的k,v，依次取散列表中的(key,value)。2024/11/92310.5遍历散列表例子4Example10_4.java例子4的主类Example10_4将正整数和正整数的平方根（最多保留3位小数）作为(key,value)存放在一个散列表中，然后遍历散列表。10.6散列表与字符、单词频率2024/11/924●每次读取文件的一个字符，如果是字母，并且散列表中还没有(key,value)：(字母,次数)，散列表就添加(key,value)：(字母，次数)，如果散列表中已经有(key,value)：(字母，次数)，就更新该(key,value)：(字母，次数)，将其次数增加1。●每次读取文件的一个单词，如果散列表中还没有(key,value)：(单词，次数)，散列表就添加(key,value)：(单词，次数)，如果散列表中已经有(key,value)：(单词，次数)，就更新该(key,value)：(单词，次数)，将其次数增加1。2024/11/92510.6散列表与字符、单词频率例子5LettersFrequency.java例子5中的LettersFrequency类负责统计文本文件中字符出现的次数和频率，WordsFrequency负责统计文本文件中单词出现的次数和频率。WordsFrequency.javaExample10_5.java例子5中Example10_5.java中的主类Example10_5使用LettersFrequency类统计了Example10_5.java里字母出现的次数和频率，另外一个主类MainClass使用WordsFrequency统计了Example10_5.java里单词出现的次数和频率。10.7散列表与单件模式2024/11/926●单件模式

保证一个类仅有一个实例，并提供一个访问它的全局访问点。散列表可以用来存储已知的数据，在后续的操作中，通过散列表查找是否已经存在，从而实现唯一性验证的功能。因此在实现的具体代码中可以借助散列表来实现单件模式。2024/11/92710.7散列表与单件模式例子6SingletonSun.javaExample10_6.java例子6中的SingletonSun类实现了单件模式，SingletonSun类只能创建一个“太阳”。在例子6中，SingletonSun类中的getInstance()方法检查散列表中是否已经存在当前类的实例对象，如果不存在则创建一个新的，然后将其存储到散列表中，并返回该实例。这样就保证了SingletonSun类在整个程序中只能创建它的一个对象。10.8散列表与数据缓存2024/11/928

2024/11/92910.8散列表与数据缓存例子7Hash.javaExample10_7.java例子7中的Hash类将频繁使用的阶乘放在散列表中(用到第3章例子3中的SumMulti类)10.9TreeMap类2024/11/93010.9TreeMap类2024/11/931在类的层次上，TreeMap<K,V>泛型类HashMap<K,V>泛型类不同，HashMap<K,V>泛型类直接实现Map接口，TreeMap<K,V>泛型类不是直接实现Map接口，而是实现NavigableMap接口，该接口又是SortedMap的子接口，SortedMap接口又是Map的子接口，如图前图。称TreeMap<K,V>泛型类的实例或创建的对象是一个映射树。10.9TreeMap类2024/11/932在存储数据上，TreeMap<K,V>泛型类和HashMap<K,V>泛型类似，映射树也是存储"键-值"对，但映射树不是散列结构。映射树也是使用两个集合存储对象，一个集合称作关键字集合，记作Key。另一个是值的集合，记作Value。TreeMap<K,V>的Key集合也是实现Set接口的一个实例，映射树中按着Key集合中的关键字的大小关系，将关键字key对应的value，存放在一个红黑树（平衡二叉搜索树，见第9章）上，即映射树的Value是一棵红黑树，这也是TreeMap<K,V>类名的来历。10.9TreeMap类2024/11/933

2024/11/93410.9TreeMap类TreeMap中的Value是红黑树，是按着Key中的关键字的大小关系排序的，这就意味着Value红黑树上可以有相同的对象，即可以有两个结点中的对象是相同的，甚至，所有结点中的对象都可以是相同的。

2024/11/93510.9TreeMap类例子8Example10_8.java例子8中，主类Example10_8使用了TreeMap的一些常用方法。2024/11/93610.9TreeMap类例子9Example10_9.java例子9的主类Example10_9获取的映射树的视图，查询了视图中的”键-值”对，并对视图进行更新操作。2024/11/93710.9TreeMap类例子10Example10_10.javaStudent.javaKeyStudent.java数映射中的Value，是按着Key中的关键字大小来排序的，那么，相对TreeSet（见第9章），使用映射树对Value进行排序的方便之处就是，可以随时更改Key中关键字的大小关系。例子10中的KeyStudent类实现了Comparable接口，给出了树映射的Key的大小关系。例子10中的主类Example10_10使用映射树分别按数学成绩和英语成绩排序学生.10.10Hashtable类2024/11/938Hashtable<K,V>泛型类也实现了Java集合框架中的Map接口。Hashtable<K,V>泛型类和HashMap<K,V>泛型类的主要区别是，Hashtable<K,V>泛型类提供的方法都是同步(synchronized)方法，即是线性安全的，而HashMap<K,V>泛型类不是线性安全的。2024/11/93910.10Hashtable类例子11Example10_11.javaTarget.java例子11中的主类Example10_11里的f()方法使用两个线程访问HashMap散列表，由于HashMap散列表不是线程安全的，一个线程遍历HashMap散列表的过程中，另一个线程也可以遍历HashMap散列表。例子11中另一个主类MainCalss里的f()方法使用两个线程访问Hashtable散列表，两个线程各自遍历Hashtable散列表，由于Hashtable散列表是线程安全的，一个线程遍历Hashtable散列表的过程中，另一个线程无法遍历Hashtable散列表。访问线程不安全的散列表访问线程安全的散列表第12章常用算法与Collections类2024/11/9402024/11/9412024/11/942Collections类是Object类的一个直接子类（注意Collections比Collection多了一个字母s），该类封装了一系列算法，例如，二分查找，排序、洗牌等算法，这些算法可用于List，Queue、Set。需要注意的是Collections是类，Collection是接口，Collections类没有实现Collection接口.12.1排序2024/11/943

2024/11/94412.1排序例子1Score.java例子1中的主类Example12_1使用Collections类的sort()方法排序（升序）一个链表，首先按链表中的对象实现的Comparable接口给出的比较器排序链表，然后再指定新的比较器排序链表。Example12_1.java12.2二分查找2024/11/945publicstaticintbinarySearch(List<?extendsT>list,Tkey)查找对象key是否在升序的list中（list中的对象按自然序排序），如果key在list中，方法返回key在list中的索引位置（索引位置从0开始），否则返回一个负数。publicstaticintbinarySearch(List<?extendsT>list,Tkey,Comparator<?superT>c)查找对象key是否在升序的list中（list的元素按比较器c排序），如果key在list中，方法返回key在list中的索引位置（索引位置从0开始），否则返回一个负数。注意，排序使用的比较器的算法需要和该方法使用的比较器c的算法相同。2024/11/94612.2二分查找例子2FindWords.java例子2中的FindWords类的booleanfindWords(Stringstr,Stringkey)方法使用二分法判断单词key是否在str中。Example12_2.java12.3反转与旋转2024/11/947publicstaticvoidreverse(List<?>list)反转list中元素的顺序.publicstaticvoidrotate(List<?>list,intdistance)把list向右(distance是正整数)或向左(distance是负整数)旋转distance个索引位置。例如，list节点中的对象依次是[a,b,c,d,e]，如果执行Colections.rotate(list,1)，那么list节点中的对象依次是[e,a,b,c,d]，如果执行Colections.rotate(list,-2)，那么list节点中的对象依次是[cdeab]。2024/11/94812.3反转与旋转例子3LeaveOne.javaWordReverse.java例子3中的LeaveOne类的leaveByRotate(LinkedList<Integer>list)方法通过旋转链表，解决约瑟夫问题：把list向左旋转2个索引位置，即可确定出退出圈中的人，理由是，此刻链表头节点就是数到的第3个人，即要出圈的人。例子3的WordRevers类的isReverse(Stringword)方法判断word是否是回文单词（回文单词和它的反转相同）。建议读者把这里的例子3和第4章的例子9做一个比较，体会使用旋转list解决约瑟夫问题，能让代码更加简练。Example12_3.java12.4洗牌2024/11/949我们曾在第4章的4.10节，讲解过洗牌算法，即Fisher-Yates洗牌算法。Collections类将Fisher-Yates洗牌算法封装在下列方法中：publicstaticvoidshuffle(List<?>list)使用Fisher-Yates洗牌算法排列list。2024/11/95012.4洗牌例子4例子4的主类Example12_4使用Collectiones类提供的Fisher-Yates洗牌算法演示洗牌过程。Example12_4.java12.5最大与最小2024/11/951publicstaticTmax(Collection<?extendsT>coll)按coll元素的自然序（元素实现Comparable接口中的比较器给出的大小顺序），返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll)按coll元素的自然序，返回coll中的最小值。publicstaticTmax(Collection<?extendsT>coll,Comparator<?superT>comp)

按comp比较器，返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll,,Comparator<?superT>comp)按comp比较器，返回coll中的最小值。2024/11/95212.5最大与最小例子5Example12_5.java例子5中的主类Example12_5求集合中的最大值和最小值。12.6频率2024/11/953publicstaticintfrequency(Collection<?>c,Objectobj)返回c中与指定对象obj相等的元素的数量。我们曾在第10章的例子5中，使用散列表统计文本文件中单词出现的次数和频率。下面的例子6使用intfrequency(Collection<?>c,Objectobj)方法统计文本文件中单词或汉字出现的次数和频率。2024/11/95412.5最大与最小例子6Example12_6.java例子6中的FrequencyEnglish类将英文组成的文本文件中的单词存放在一个集合中，便于统计出不相同的单词的总数，把单词存放在一个链表中，便于统计每个单词出现的次数，并计算出单词出现的频率。FrequencyChinese类将中文组成的文本文件中的汉字存放在一个集合中，便于统计出不相同的汉字的总数，把汉字存放在一个链表中，便于统计每个汉字出现的次数，并计算出汉字出现的频率。FrequencyEnglish.javaFrequencyChinese.java第13章图论2024/11/9552024/11/956

13.1无向图2024/11/957

⒈无向图的定义2024/11/95813.1无向图

⒈无向图的定义2024/11/95913.1无向图

2邻接点

2024/11/96013.1无向图3.路径

2024/11/96113.1无向图4.连通图

13.2有向图2024/11/962⒈有向图的定义

2024/11/96313.2有向图

⒈有向图的定义

2024/11/96413.2有向图2邻接点

2024/11/96513.2无向图3.路径

2024/11/96613.2有向图4.强连通图

13.3网络2024/11/967

2024/11/96813.3网络刻画北京，广州，成都和上海四个城市之间的民航航线，航线之间的权重是航线距离。2024/11/96913.3网络刻画北京，广州，成都和上海四个城市之间的民航航线，航线之间的权重是航线的票价（往返的票价不尽相同）。13.4图的存储2024/11/9701.邻接矩阵

13.4图的存储2024/11/9711.邻接矩阵

2024/11/97213.4图的存储例子1Example13_1.javaGraphByMatrix.java例子1中的GraphByMatrix类使用邻接矩阵存储图或网络的边。例子1的主类Example13_1使用GraphByMatrix类演示了无向图、有向图和有向网络使用邻接矩阵存储边.13.4图的存储2024/11/9731.邻接表

2024/11/97413.4图的存储例子2Example13_2.javaGraphByLinkedList.java例子2中的GraphByLinkedList类使用邻接链表存储图或网络的边。例子2的主类Example13_2使用GraphByLinkedList类演示了无向图、有向图和有向网络使用邻接链表存储边.13.4图的遍历2024/11/975

13.4图的遍历2024/11/976广度搜索（BFS）则是从起点开始，逐层访问所有路径可达到的顶点，一层一层地往外扩展（广度优先），直到所有路径可达到的顶点都被访问到，就结束此次遍历过程。如果图中仍然有没访问过的顶点，就在没访问过的顶点中，选择一个顶点重新开始遍历。广度优先搜索一直到图中再也没有可访问的顶点，就结束搜索过程。广度优先搜索的算法中可以用队列（Deque）这种数据结构体现广度优先.2024/11/97713.5图的遍历例子3Example13_3.javaGraphDFS.java1.深度优先搜索（DFS）算法DFS算法描述如下。①检查是否已经访问了全部的顶点，如果已经访问了全部的顶点，进行③，否则，将一个不曾访问的顶点压入栈，进行②。②如果栈是空，进行①，否则进行弹栈，把弹出的顶点标记为访问过的顶点，然后把弹出的顶点的邻接顶点压入栈（体现深度优先），但不再对访问过的顶点进行压栈操作，再进行②。③算法结束。例子3中的GraphDFS类封装了DFS算法。Vertex.java2024/11/97813.5图的遍历例子4Example13_4.javaGraphBFS.java2.广度优先搜索（BFS）算法例子4中的GraphBFS类封装了BFS算法。Vertex.javaBFS算法描述如下：①检查是否已经访问了全部的顶点，如果已经访问了全部的顶点，进行③，否则，将一个不曾访问的顶点入列，进行②。②如果队列是空，进行①，否则进行出列操作，把出列的顶点标记