第10章综合应用设计(Java版)详解.ppt

第10章 综合应用设计 10.1 Java集合框架 10.2 实现迭代器 10.3 算法设计策略 10.4 课程设计的目的、要求和选题 目的 目的：综合运用数据结构课程所讨论的基 础知识和基本理论，解决具有一定 规模的、中等难度的实际应用问 题，培养综合应用设计能力。 内容：Java集合框架；多种算法设计策 略。 10.1 Java集合框架（java.util包） 10.1.1 Comparator比较器接口 10.1.2 Arrays数组类 10.1.3 集合 【例10.1】 使用Java集合框架求解素数环问题。 10.1.4 映射 10.1.1 Comparator比较器接口 public interface ComparatorT { int compare(T cobj1, T cobj2); //指定比较两个对象大小的规则 } 10.1.2 Arrays数组类 排序 public static void sort(int a[])//整数数组排序（升序） void sort(Object[] a) //对象数组排序（升序）， //默认a数组元素实现ComparableT接口 T void sort(T[] a, Comparator? super T comp) //由比较器接口对象comp比较T对象相等和大小 2. 二分法查找 int binarySearch(int a[], int key) //在排序数组a中，按二分法查找key，返回下标 int binarySearch(Object a[], Object key) //默认数组a元素实现ComparableT接口 T int binarySearch(T a[], T key, Comparator? super T comp) 10.1.3 集合 迭代 2. CollectionT接口 3. ListT列表 4. Collections类 5. 栈和队列 6. SetT无序集合 图10.1 集合框架结构 集合框架中的主要接口和类 1. 迭代 （1）java.lang.IterableT可迭代接口 public interface IterableT { IteratorT iterator(); } （2）java.util.Iterator迭代器接口 public interface IteratorT //迭代器接口 { boolean hasNext(); //判断是否有后继元素 T next(); //返回后继元素 void remove(); //删除迭代器对象表示的集合当前元素 } 2. CollectionT接口 public interface CollectionT extends IterableT { IteratorT iterator(); //获得迭代器，继承 boolean isEmpty(); //判断集合是否为空 int size(); //返回集合的元素个数 boolean contains(Object obj); //判断是否包含元素 boolean add(T element); //增加指定元素 boolean remove(Object obj); //移去首次出现元素 void clear(); //移去所有元素 } 2. CollectionT接口 //以下方法描述集合运算，参数是另一个集合 boolean equals(Object obj); //比较集合相等 boolean containsAll(Collection? coll); //集合包含 boolean addAll(Collection? extends T coll); //集合并 boolean removeAll(Collection? coll); //集合差 boolean retain