将多个元素组成一个单元的对象

1、DYNAMIC DATA STRUCTURES A data structure is a construct used to organize data in a specific way. So in this chapter we will: Become familiar with vectors and how they are used in Java. Learn what a linked data structure is and how it can be realized in Java. Find out how to manipulate linked lists L

2、earn what iterators are and how to create and use them CHAPTER 10简介 集合 将多个元素组成一个单元的对象 用于存储、检索、操纵和传输数据 集合框架 提供用于管理对象集合的接口和类 包括接口、实现和算法体系结构 用于操纵集合的接口CollectionSetListSortedSetMapSortedMapCollection接口 集合框架的根 通用方法 boolean contains(Object a) boolean equals(Object a) Iterator iterator() int size() void cl

3、ear() boolean add(Object a) Set接口 扩展Collection接口 不允许重复元素 对 add()、equals() 和 hashcode() 方法添加了限制 HashSet和TreeSet是Set的实现SortedSet接口 扩展了Set接口 元素按升序排序 重要异常 ClassCastException NullPointerException List接口 2-1 具有顺序的集合 扩展了Collection接口 元素可以通过其整型下标访问 可以包含重复元素List接口 2-2 方法分类 定位方法get()、set()、add()、remove()、addAl

4、l() 搜索方法indexOf() 和和 lastIndexOf() ListIterator方法listIterator() 和和 subList() Map接口 将键映射至值的对象 每个键最多都只能映射至一个值 重要方法 基本操作 put()、get()、remove()、containsKey()、containsValue()、size() 和和 isEmpty() 批操作 putAll() 和和 clear() 集合视图 keySet()、values() 和和 entrySet() 实现 2-1 用于存储集合的实际数据对象 重要集合类 AbstractCollection类提供Co

5、llection接口的框架实现 AbstractList 类提供 List 接口的框架实现 AbstractSequentialList 类是 List 接口的实现 LinkedList 类提供多个方法，用于在列表开始处和结尾 处获得、删除和插入元素简介 集合 将多个元素组成一个单元的对象 用于存储、检索、操纵和传输数据 集合框架 提供用于管理对象集合的接口和类 包括接口、实现和算法体系结构 用于操纵集合的接口CollectionSetListSortedSetMapSortedMapCollection接口 集合框架的根 通用方法 boolean contains(Object a) boo

6、lean equals(Object a) Iterator iterator() int size() void clear() boolean add(Object a) Set接口 扩展Collection接口 不允许重复元素 对 add()、equals() 和 hashcode() 方法添加了限制 HashSet和TreeSet是Set的实现SortedSet接口 扩展了Set接口 元素按升序排序 重要异常 ClassCastException NullPointerException List接口 2-1 具有顺序的集合 扩展了Collection接口 元素可以通过其整型下标访问

7、可以包含重复元素List接口 2-2 方法分类 定位方法get()、set()、add()、remove()、addAll() 搜索方法indexOf() 和和 lastIndexOf() ListIterator方法listIterator() 和和 subList() Map接口 将键映射至值的对象 每个键最多都只能映射至一个值 重要方法 基本操作 put()、get()、remove()、containsKey()、containsValue()、size() 和和 isEmpty() 批操作 putAll() 和和 clear() 集合视图 keySet()、values() 和和 e

8、ntrySet() 实现 2-1 用于存储集合的实际数据对象 重要集合类 AbstractCollection类提供Collection接口的框架实现 AbstractList 类提供 List 接口的框架实现 AbstractSequentialList 类是 List 接口的实现 LinkedList 类提供多个方法，用于在列表开始处和结尾 处获得、删除和插入元素实现 2-2 重要集合类（续） ArrayList 类是 List 接口的可变大小数组实现 AbstractSet 类提供 Set 接口的框架实现 HashSet 类为基本操作提供固定时间性能 TreeSet 类确保排序集将按元素

9、升序exampleimport java.util.*;public class ListOper public static void main(String args) if(args.length=0) System.out.println(你必须提供列表元素，作为命令行参数。请重试！你必须提供列表元素，作为命令行参数。请重试！); System.exit(0); System.out.println(); List l=new ArrayList(); for(int i=0;iB else hanno(A,C,B,n-1); move(A,B);hanno(C,B,A,n1); RE

10、CURSIONSuccessful Recursion A define of a method that includes a recursive invocation of the method being defined will not behave correctly unless you follow some specific design guidelines. The follwing rules apply to most cases that involve recursion. The heart of the method definition can be an i

11、f-else-statement or some other branching statement that leads to different cases, depending on some property of a parameter to the method being defiend.Successful Recursion 2 One or more of the brances include a recursive invocation of the method. These recursive invocations should in some sense use

12、 “smaller” arguments or solve “smaller” versions of the task performed by the method. One or more branches should include no recursive invocations. These are the stopping cases (alse known as the base cases.)Stack Overflow When a method invocation leads to infinite recursion, your program is likely

13、to end with an error message that refers to a “stack overflow”. The term stack refers to a data structure that is used to keep track of recursive calls (and other things as well). Intuitively a record of each recursive call is stored on something analogous to a piece of paper. These pieces of paper

14、are intuitively stacked one on top of the other. When this “stack” becomes too large for the computer to handle, that is called a stack overflow.Summary Vectors can be thought of as arrays that can grow in length. The base type of all vectors is Object. Thus, the elements of a vector may be of any c

15、lass type, but they cannot be of a primitive type. A linked list is a data structure consisting of objects known as nodes, such that each node can contain data and such that each node has a reference to one other node so that the entire linked list forms a list.Summary You can make a linked list sel

16、f-contained by making the node class an inner class of the linked class. You can use an iterator to step through the elements of a collection, such as the elements in a linked list.Summary If a method definition includes an invocation of the very method being defined, that is called a recursive call

17、. Recursive calls are legal in Java and can somethimes make a method definition clearer. In order to avoid infinite recursion, a recursive method definition should contain two kinds of cases: one or more case that include recursive call(s) and one or more stopping cases that do not involve any recur

18、sive calls.Self-test Question Suppose v is a vector. How do you add the string “Hello” to the vector v? If you create a vector with the following, can the vector contain more than 20 elements? Vector v=new Vector(20); What is the base type of a vector? Can you store a value of type int in a vector? Suppose v is a vector. What is the difference between v.capacity() and v.size()?Self-test Question Why does th