JAVA语言面向对象程序设计 教学课件 作者 马俊 11JAVA.ppt

数据结构、集合框架 目标 了解数据结构的概念 掌握java的集合框架的体系结构 掌握常用的集合类和接口 了解泛型类 简介 按照传统的理解，一个程序应包括以下两个方面： 对数据的描述 在程序中要制定数据的类型和数据的组织方式，我们称为数据结构。 对操作的描述 即操作的步骤，也就是我们说的算法。 数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。著名的计算机科学家沃斯(Nikiklaus Wirth)提出一个公式： 数据结构+算法=程序 实际上数据结构代表数据在空间上的一种排列方式，而算法代表数据在时间上的动态变化。作为程序员，必须掌握各种基本的数据结构和算法，就跟我们研究自然世界的各种物质组成是一样的道理；我们研究的物质的静态组成以及它的运动规律，我们也研究物质的内部组成，即研究作为某一物质特有的结构和其外部表现之间的联系。 Java对数据结构的支持 集合 将多个元素组成一个单元的对象 用于存储、检索、操纵和传输数据 集合框架 提供用于管理对象集合的接口和类 包括接口、实现和算法 体系结构 用于操纵集合的接口 Collection接口 集合框架的根 通用方法 boolean contains(Object a) boolean 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接口 元素可以通过其整型下标访问 可以包含重复元素 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() 和 entrySet() 实现 2-1 用于存储集合的实际数据对象 重要集合类 AbstractCollection类提供Collection接口的框架实现 AbstractList 类提供 List 接口的框架实现 AbstractSequentialList 类是 List 接口的实现 LinkedList 类提供多个方法，用于在列表开始处和结尾 处获得、删除和插入元素 实现 2-2 重要集合类（续） ArrayList 类是 List 接口的可变大小数组实现 AbstractSet 类提供 Set 接口的框架实现 HashSet 类为基本操作提供固定时间性能 TreeSet 类确保排序集将按元素升序 算法 3-1 Collections 类中的静态方法 用于排序、搜索、混排和数据操纵 方法的第一个参数是要执行操作的集合 重要异常 ClassCastException UnsupportedOperationException 算法 3-2 算法 3-3 class AlgorithmExample { public static void main(String args[]) { LinkedList link = new LinkedList(); link.add(new Integer(10)); link.add(new Integer(35)); link.add(new Integer(23)); link.add(new Integer(54)); link.add(new Integer(36)); Comparator cmp = Collections.reverseOrder(); Collections.sort(link, cmp); Iterator it = link.iterator(