《第08讲 常用数据结构》由会员分享，可在线阅读，更多相关《第08讲 常用数据结构（62页珍藏版）》请在金锄头文库上搜索。
1、JAVA 语言,第8讲 JAVA的数据结构,2018年9月19日,上一讲回顾,String类字符串的定义及其基本操作 Character类及其基本操作 StringBuffer类及其基本操作,2018年9月19日,学习要点,了解Java集合架构（Java Collection Framework） 了解Collection接口、Map接口及其子接口 了解Set接口，学会使用HashSet和Treeset 了解List接口，学会使用ArrayList类、LinkedList类、Vector类和Stack类 了解HashMap类和TreeMap类 学会使用Collection类和Arrays类中的
2、静态方法 分清不同类的使用范围，参考API Reference,2018年9月19日,8.1 Java集合架构概述,集合(Collection)是一个对象的容器，可以存放对象，便于组织和管理对象 java.util包中定义了各种用于集合操作的类和接口，这些类和接口构成了Java语言的集合框架(Collection Framework) 集合框架中定义了接口对常用的集合类型进行抽象，还提供了一些优化的对接口的实现类，简化程序设计,2018年9月19日,Collection Framework,根据不同类型的集合的特点和用途，集合框架在设计的时候将集合分为以下三种类型： Set（集）：集合中的对象
3、不按特定方式排序，并且没有重复对象。它的有些实现类能对集合中对象按特定方式排序。 List（列表）：集合中的对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象。List与数组有些相似。 Map（映射）：集合中的每一个元素包含一对键对象和值对象，集合中没有重复的键对象，值对象可以重复。它的有些实现类能对集合中的键对象进行排序。,2018年9月19日,Default Implementation,集合框架中提供了一些常用的集合接口的实现类：HashSet 使用散列表算法实现Set接口TreeSet 使用平衡二叉树算法实现SortedSet接口ArrayList 使用数组存
4、放对象来实现List接口LinkedList 使用双向链表来实现List接口HashMap 使用散列表算法实现Map接口TreeMap 使用平衡二叉树算法实现Map接口,2018年9月19日,8.2 Collection 接口、Map接口及其子接口,集合框架中将不同类型的集合和集合相关的操作抽象为高层的接口，并构成层次结构 java.util包中定义如下高层集合接口：Collection 除映射类型外所有集合类型的超类型，声明了针对集合的通用方法Set 用于表示数学概念中的集合List 用于表示列表类型集合Map 用于表示映射类型的集合,2018年9月19日,1 Collection接口 (j
5、ava.util.Collection Interface),接口java.util.Collection是所有集合类型的超类型。它声明所有类集都将拥有的核心方法public int size()public boolean isEmpty()public boolean contains(Object elem)public Object toArray() public Object toArray(Object dest),2018年9月19日,java.util.Collection Interface,public add(Object elem)public remove(Obje
6、ct elem)public boolean containsAll(Collection coll)public boolean addAll(Collection coll)public boolean removeAll(Collection coll)public boolean retainAll(Collection coll)public void clear()public Iterator iterator(),2018年9月19日,这些方法用于在集合中添加、删除和查询元素。,2018年9月19日,2 Set接口和Sorted Collections,有序集合指集合中容纳的对
7、象按照一定的规则进行排序 集合框架中提供了Set、List和Map的有序类型：SortedSet Set接口的子接口SortedMap Map接口的子接口,2018年9月19日,java.util.Set Interface,该接口并没有声明新的方法，但要求实现类所表示的集合中不能容纳两个相同的对象 判定两个对象是否相同是一般是通过调用对象的equals(Object other)方法来实现的,2018年9月19日,见TreeSet.doc Ch08/ TreeSetDemo.java,2018年9月19日,java.util.SortedSet Interface,该接口扩展了接口Set，新
8、增了与有序集合相关的操作：public Object first()public Object last()public SortedSet subSet(Object min, Object max)public SortedSet headSet(Object max)public SortedSet tailSet(Object min)public Comparator comparator(),SortedSet intSet=new TreeSet(); intSet.add(new Integer(50); intSet.add(new Integer(25); intSet.a
9、dd(new Integer(100); intSet.add(new Integer(-15); System.out.println(intSet.first(); System.out.println(intSet.last();SortedSet subSet=intSet.tailSet(new Integer(25); Iterator it=subSet.iterator(); while(it.hasNext()System.out.println(it.next(); ,-15 100 25 50 100,2018年9月19日,3 List接口,List接口扩展了Collec
10、tion并声明存储一系列元素的类集的特性。使用一个基于零的下标，元素可以通过它们在列表中的位置被插入和访问。一个列表可以包含复制元素。 除了由Collection定义的方法之外，List还定义了一些它自己的方法。,2018年9月19日,java.util.List Interface,由于列表集合中存放的是对象的有序序列，因此该接口新增了与有序性相关的方法：public Object get(int index)public Object set(int index, Object elem)public void add(int index, Object elem)public Objec
11、t remove(int index)public int indexOf(Object elem)public int lastIndexOf(Object elem)public List subList(int min, int max)ListIterator listIterator() ListIterator listIterator(int index),2018年9月19日,2018年9月19日,boolean removeAll(Collection c) 从列表中移除指定 collection 中包含的所有元素（可选操作）。boolean retainAll(Collec
12、tion c) 仅在列表中保留指定 collection 中所包含的元素（可选操作）。Ch08/UsingList.java Ch08/ListToArray.java Ch08/MovingPlanets.java,2018年9月19日,4 Iterator Interface,如何以一种通用的方式遍历访问集合框架中定义的所有类型的集合? java.util包中定义了接口Iterator，声明了用于遍历任何类型的集合中的对象的方法，是对设计模式中的迭代器模式的应用 接口ListIterator扩展了接口Iterator的，增加了针对List类型的集合的遍历操作,2018年9月19日,java
13、.util 接口 Iterator,所有已知子接口： ListIterator 方法摘要 Boolean hasNext() 如果仍有元素可以迭代，则返回 true。 next() 返回迭代的下一个元素。void remove() 从迭代器指向的集合中移除迭代器返回的最后一个元素（可选操作）。,2018年9月19日,java.util.Iterator Interface,该接口声明了用于遍历集合的方法：public boolean hasNext()public Object next()public void remove() 通过调用Collection接口及其子接口的实现类的对象的it
14、erator()方法可以返回一个该接口的实现类的对象，使用该对象来遍历访问集合中每个对象 在使用Iterator对象遍历集合时，如果要删除集合中的某个对象，必须使用该接口中remove()方法！,public void removeLongStrings(Collection coll, int maxLen)Iterator it=coll.iterator();while(it.hasNext()String str=(String)it.next();if(str.length()maxLen)coll.remove(str); ,错误的删除操作！,public void removeL
15、ongStrings(Collection coll, int maxLen)Iterator it=coll.iterator();while(it.hasNext()String str=(String)it.next();if(str.length()maxLen)it.remove(); ,正确的删除操作！,2018年9月19日,java.util.ListIterator Interface,该接口扩展了接口Iterator，新增了用于列表操作的方法：public void add(Object elem)public void set(Object elem)public bool
16、ean hasPrevious()public Object previous()public int previousIndex()public int nextIndex(),List objList=new ArrayList();objList.add(new Integer(100); objList.add(new Double(123.5); objList.add(“Java”);ListIterator it=objList.listIterator(objList.size(); while(it.hasPrevious()Object obj=it.previous();System.out.println(obj); ,Java 123.5 100,2018年9月19日,5 Map和SortedMap接口,映射（map）是一个存储关键字和值的关联或者说是关键字/值对的对象。给定一个关键字，可以得到它的值。关键字和值都是对象。关键字必须是唯一的。但值是可以被复制的。有些映射可以接收null关键字和null值。而有的则不行。,
