《Java集合架构》PPT课件.ppt
Java高级程序设计(上),1,Chapter14 Java集合架构,Collection接口和AbstractCollection类 规则集Set比较器接口Comparator 线性表ListMap,Java高级程序设计(上),2,简介,几种常见的数据结构：链表、堆栈、队列、堆、优先队列等。集合(collection):存储一组对象的容器对象。Java集合架构支持三种类型的集合：规则集(set)、线性表(list)、图(map)Set:存储一组互不相同的元素。List:存储一组顺序排列的元素。Map:存储一组均有一个关联键的对象。注意：java集合架构中的类都实现了Cloneable和Serializable接口。本章所学的类位于：java.util包中。重点：如何使用集合架构中的接口和类。,Java高级程序设计(上),3,主要接口和类的关系图,Java高级程序设计(上),4,主要接口和类的关系图,Java高级程序设计(上),5,Collection接口和AbstrctCollection接口,Java高级程序设计(上),6,散列集(HashSet类),三个：散列集(HashSet类)、链式散列集(LinkedHashSet类)、树形集(TreeSet类)。散列集(HashSet类)：添加到散列集中的对象必须实现hashCode()方法。实例：创建一个散列集来存储文本中解析出来的单词，并使用迭代器遍历该集合中的每一个单词。注意：1.将多个相同元素添加到规则集中，只有一个被存储。2.集合中的元素没有按插入时的顺序存储(集合的无序性)。3.添加到集合中的元素必须和集合声明的元素类型相同。4.for(Object element:set)语句，用于遍历集合中的每个元素。,Java高级程序设计(上),7,LinkedHashSet：使用链表实现，可以按照元素插入的顺序进行访问。实例：用文本文件中提取的字符串构造链式散列集，并用foreach语句对其中的元素进行访问。程序：ex16_2.java提示：如果不需要使元素按照其插入的顺序进行存储，应该使用HashSet,它的效率比LinkedHashSet高。TreeSet：可以对加入其中的元素进行排序(升序或降序)几个方法：first()、last()、headSet(toElement)、tailSet(fromElement)注意：加入树形集中的元素必须是可比较的。,链式散列集(LinkedHashSet)和树形集(TreeSet),Java高级程序设计(上),8,实现对象比较的方法：方法1：实现Comparable接口。实例：使用TreeSet类按照字母顺序显示单词。程序：ex16_3.java 使用TreeSet(Collection c)可以提高效率，仅排序一次。注意：更新集合，需保持顺序时，使用树形集，否则使用散列集。方法2：实现Comparator 接口。可以将实现了Comparator 接口的不同类型的元素加入到树形集中。实现两个方法：public int compare(Object element1,Object element2)public boolean equals(Object element)实例：几何图形面积的比较。并将不同的几何图形加入到树形集中。然后输出加入的元素。程序：ex16_4.java注意：Comparable用于比较相同类型的两个对象，Comparator可比较不同类型的两个对象。,链式散列集(LinkedHashSet)和树形集(TreeSet),Java高级程序设计(上),9,线性表,使用线性表：1.允许在一个集合中存储重复的元素。2.可以指定元素的存储位置。3.可以用下标来访问元素。4.但不支持有序存储。,Java高级程序设计(上),10,线性表,Java高级程序设计(上),11,ArrayList和LinkedList的区别：1.实现方式不同 数组线性表用数组实现的线性表，链式线性表是用链表结构实现的线性表。2.不同应用场合效率不同 数组线性表可以用下标随机访问元素，但不适合在任意的位置频繁插入和删除元素。ArrayList 创建动态可变的数组。trimToSize():用于调整数组大小到线性表实际的大小。LinkedList 包含了从线性表两端提取、插入和删除元素的方法。getFirst(),getLast(),addFirst(o:E),addLast(o:E),removeFirst(),removeLast(),ArrayList和LinkedList,Java高级程序设计(上),12,实例：创建用数组填充的数组线性表，并将新元素插入到线性表指定的位置，且利用该数组线性表创建一个链表，并从该链表中插入和删除元素。最后分别用向前和向后遍历的方法遍历该链表。程序：ex16_5.java列表的创建：使用类中的asList(T.a)方法。如：List list=Arrays.asList(“red”,”green”,”blue”);,ArrayList和LinkedList,Java高级程序设计(上),13,线性表不支持有序存储,但是：类提供了:1.用于线性表排序的静态方法。2.用于求集合的最大、最小元素等的方法。例1：List list=Arrays.asList(2,3,4,7,11,45,50,59,60);Collections.binarySearch(list,11);Collections.binarySearch(list,5);例2：Set set=new HashSet();set.add(“red”);set.add(“blue”);Collections.max(set);,线性表(List)和集合(Collection)的静态方法,Java高级程序设计(上),14,Stack类：peek()返回栈顶元素 pop()弹出栈顶元素 push(o:E)在栈顶添加一个新元素Queue接口：LinkedList offer(element:E)向队列中插入一个元素 poll()返回并删除队列头，队列为空，则返回null remove()返回并删除队列头，队列为空，抛出异常 peek()返回但不删除队列头，如果队列为空，返回null.实例：分别创建一个栈和一个队列，插入和删除元素并显示。程序：ex16_6.java,栈类(Stack)、队列(Queue),Java高级程序设计(上),15,是Queue接口的实例。使用Comparable对元素排序，拥有最小数值的元素被赋予最高的优先级，最先从队列中移出。也可以使用实现了比较器接口的实例对元素进行比较。优先队列创建的构造方法：PriorityQueue()PriorityQueue(initialCapacity:int)PriorityQueue(c:Collection)PriorityQueue(initialCapacity:int,comparator:Comparator)实例：创建一个优先队列，并以正序和倒序的方式输出。程序：ex16_7.java,优先队列(PriorityQueue),Java高级程序设计(上),16,图(map),Map接口：Map 建立元素和键的映射关系。键：可以是任意类型的对象，一个图中不能有重复的键，每个键对应一个值。,Java高级程序设计(上),17,实现Map接口的具体类,1.散列图HashMap 元素是没有顺序的 2.链式散列图 LinkedHashMap 按元素插入的顺序排序或最后访问的时间顺序排序 3.树形图 TreeMap 按照键的顺序排序实例：创建一个散列图，一个链式散列图和一个树形图，建立学生与年龄之间的映射关系。按照递增的顺序显示树形图中的映射。程序：ex16_8.java,Java高级程序设计(上),18,实例：单词出现次数,统计文本中单词的出现次数，并按照单词从低到高的升序将每个单词及其对应的次数显示出来。分析：使用一个散列图来存储单词及其统计次数的偶对，对每一个单词来说，判断是否已经是图中的一个键，如果不是将其作为键，1作为值存入图中，否则，将图中该单词对应的值加1.程序：ex16_9.java,
