《第10章 综合应用设计(Java版)》由会员分享，可在线阅读，更多相关《第10章 综合应用设计(Java版)（60页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Java版）（第3版）,第10章 综合应用设计,10.1 数组和集合10.2 实现迭代器 10.3 算法设计策略10.4 课程设计的目的、要求和选题,数据结构（Java版）（第3版）,目的,目的：综合运用数据结构课程所讨论的基 础知识和基本理论，解决具有一定 规模的、中等难度的实际应用问 题，培养综合应用设计能力。内容：Java集合框架；多种算法设计策 略。,数据结构（Java版）（第3版）,10.1 数组和集合,10.1.1 Arrays数组类（1） 比较两个数组是否相等public static boolean equals(Object a, Object b) （2） 填充p
2、ublic static void fill(Object a, Object obj) public static void fill(long a, int begin, int end, long value),数据结构（Java版）（第3版）,10.1.1 Arrays数组类,（3） 排序public static void sort(Object a) public static void sort(T a, Comparator c) （4） 二分法查找public static int binarySearch(Object a, int begin, int end, Obje
3、ct key)public static int binarySearch(T a, T key, Comparator c),数据结构（Java版）（第3版）,java.util.Comparator比较器接口,public interface Comparator int compare(T cobj1, T cobj2); /指定比较两个对象大小的规则,数据结构（Java版）（第3版）,10.1.2 Java集合框架,集合框架结构,数据结构（Java版）（第3版）,表10-1集合框架中的主要接口和类,数据结构（Java版）（第3版）,2.迭代,（1）java.util.Iterator和
4、ListIterator迭代器接口public interface Iterator /迭代器接口 boolean hasNext(); /判断是否有后继元素 T next(); /返回后继元素 void remove(); /删除迭代器对象表示的集合当前元素,数据结构（Java版）（第3版）,java.util.ListIterator列表迭代器接口,public interface ListIterator extends Iterator boolean hasPrevious();/判断是否有前驱元素 T previous(); /返回前驱元素 int nextIndex(); /返回
5、后继元素序号 int previousIndex(); /返回前驱元素序号 void set(T x); /将集合当前元素替换为x void add(T x); /增加元素x,数据结构（Java版）（第3版）,（2）java.lang.Iterable可迭代接口,public interface Iterable Iterator iterator();,数据结构（Java版）（第3版）,3.Collection接口,public interface Collection extends Iterable Iterator iterator(); /获得迭代器 boolean isEmpty(
6、); /判断集合是否为空 int size(); /返回集合的元素个数 boolean contains(Object obj); /判断是否包含指定元素 boolean add(T element); /增加指定元素 boolean remove(Object obj); /移去首次出现指定元素 void clear(); /移去所有元素 /以下方法描述集合运算，参数是另一个集合 boolean equals(Object obj); /比较两个集合是否相等 boolean containsAll(Collection c); /判断集合包含 boolean addAll(Collectio
7、n c); /集合并 boolean removeAll(Collection c); /集合差 boolean retainAll(Collection c); /仅保留那些也包含在集合c中的元素,数据结构（Java版）（第3版）,4.列表,（1）List接口public interface List extends Collection T get(int i) /返回第i（i0）个元素 T set(int i, T x) /用x替换原第i个元素 ListIterator listIterator() /返回列表迭代器对象（2）ArrayList类 （3）LinkedList类,数据结构（
8、Java版）（第3版）,5. Collections类,public class Collections public static T max(Collection coll,Comparator c) /最大值 public static T min(Collection coll, Comparator c) /最小值 public static int binarySearch(List list,T key) public static void sort(List list, Comparator c) /排序,数据结构（Java版）（第3版）,【例10.1】 电话簿。,Frien
9、d类表示电话簿对象，实现可比较、比较器和序列化接口。TelephoneBookTreeSet类实现电话簿的存储和管理。 TelephoneBookJFrame类实现电话簿的图形用户界面，提供添加、查找和删除功能。,数据结构（Java版）（第3版）,电话簿管理窗口中两个分割窗格的布局层次,数据结构（Java版）（第3版）,10.2 实现迭代器,10.2.1 基于迭代器的操作10.2.2 提供迭代器对象,数据结构（Java版）（第3版）,10.2.1 基于迭代器的操作,抽象集合类public abstract class AbstractCCollection implements Iterabl
10、e public abstract java.util.Iterator iterator(); public String toString() java.util.Iterator it = this.iterator(); String str=(; while (it.hasNext() /若有后继元素 str += it.next().toString(); /添加后继元素字符串 if (it.hasNext() str += , ; return str+); ,数据结构（Java版）（第3版）,2.抽象列表类,public abstract class AbstractLList
11、 extends AbstractCCollection public boolean equals(Object obj) if (obj = this) return true; if (!(obj instanceof AbstractLList) return false; java.util.Iterator it1 = this.iterator(); java.util.Iterator it2 = (AbstractLList)obj).iterator(); while (it1.hasNext() ,数据结构（Java版）（第3版）,10.2.2 提供迭代器对象,顺序表类提
12、供迭代器对象 public class SeqList extends AbstractLList implements LList public java.util.Iterator iterator() /返回Java迭代器对象 return new SeqIterator(); private class SeqIterator implements java.util.Iterator /私有内部类，实现迭代器接口 ,数据结构（Java版）（第3版）,2. 单链表类提供迭代器对象,public class SinglyLinkedList extends AbstractLList implements LList public java.util.Iterator iterator() /返回Java迭代器对象 return new SinglyIterator(); private class SinglyIterator implements java.util.Iterator/私有内部类，实现迭代器接口 ,数据结构（Java版）（第3版）,本书线性表接口和类的层次关系,数据结构（Java版）（第3版）,10.3 算法设计策略,10.3.1 分治法10.3.2 动态规划法10.3.3 贪心法10.3.4 回溯法,
