OOP with Java 通知 Project 6: 5 月 24 日晚 9 点

Size: px

Start display at page:

Download "OOP with Java 通知 Project 6: 5 月 24 日晚 9 点"

伤又愈
6 years ago
Views:

1 OOP with Java Yuanbin Wu

2 OOP with Java 通知 Project 6: 5 月 24 日晚 9 点

3 复习内部类定义在一个类的内部 class Outer{ class Inner{ public class Parcel{ class Contents{ private int i = 11; public int value() {return i; class Destination{ private String label; Destination(String r) {label = r; String readlabel() { return label; public Destination to(string s){ return new Destination(s); public Contents contents(){ return new Contents(); public void ship(string dest){ Contents c = new Contents(); Destination d = new Destination(dest); System.out.println(d.readLabel()); public static void main(string []args){ Parcel p = new Parcel(); Parcel.Destination d = p.to( Tasmania ); Parcel.Contents c = p.contents();

4 复习内部类每个内部类对象包含的有一个外部类对象的引用 OuterClassName.this 创建内部类在外部类的方法中 : 直接创建在其他地方 : OuterClassObject.new

5 public class Parcel{ class Contents{ private int i = 11; public int value() {return i; class Destination{ private String label; Destination(String r) {label = r; String readlabel() { return label; public Destination to(string s){ return new Destination(s); public Contents contents(){ return new Contents(); public static void main(string []args){ Parcel p = new Parcel(); Parcel.Destination d = p.new Destination( T ); Parcel.Contents c = p.new Contents();

6 复习匿名内部类没有名字的内部类必须继承某个类, 或实现某个接口 public class Parcel{ public Contents contents(){ return new Contents() { // anonymous inner class definition private int i = 11; public int value() {return i; ; public static void main(string []args){ Parcel p = new Parcel(); Contents c = p.contents(); public class Parcel{ class PContents implements Contents{ private int i = 11; public int value() {return i; public Contents contents(){ return new PContents() ; public static void main(string []args){ Parcel p = new Parcel(); Contents c = p.contents();

7 OOP with Java 容器简介 Collection List, Set, Queue Map Collection and Iterator

8 容器简介如何将对象组织起来? int a = 0; int b = 0;... int z = 0; MyType m_a = new MyType(); MyType m_b = new MyType();... MyType m_c = new MyType();

9 容器简介数组 int [ ] a = new int[]{1,2,3; MyType [ ] b = new MyType[3]; MyType [ ] c = new MyType[3] { new MyType(), new MyType(), new MyType() ; 长度不可变 1. 无法添加和删除数组元素 2. 数组元素之间的关系? (Set)

10 容器简介容器提供更灵活的组织对象的方式动态添加, 删除例如 List, Set, Queue Map 位于包 java.util 中

11 Item1 Item2 ItemN List: 一列对象 ( 数组, 链表 ) import java.util.*; ArrayList a = new ArrayList(); LinkedList b = new LinkedList(); //Implement List interface List c = a; List d = b; List 接口

12 Add Item1 Item2 Item2 Item3 Item2 Set: 集合 ( 没有重复元素 ) import java.util.*; HashSet a = new HashSet(); TreeSet b = new TreeSet(); //implement Set interface Set c = a; Set d = b; Set 接口

13 Item1 Item2 Item3 Item4 Queue: 队列 - enqueue ( 进队 ) - dequeue ( 出队 ) - 先进先出 - 应用 : 任务调度 import java.util.*; LinkedList a = new LinkedList(); PriorityQueue b = new PriorityQueue(); //Implement Queue interface Queue c = a; Queue d = b; Queue 接口

14 Key 1 Value 1 Key 2 Value 23 Map: - Key-value 对 - Key 不重复 - value 可以重复 - 应用 : 单词出现次数 put Key n Value n import java.util.*; //Implement Map interface HashMap a = new HashMap(); Key 2 Value 3 Map 接口

15 容器简介泛型 (generic) 与类型安全的容器容器可以存放的类型为 Object 任何类型的对象都能放入容器容器的类型只能在运行时确定

16 class Apple { private static long counter; private final long id = counter++; public long id() { return id; class Orange { public class ApplesAndOrangesWithoutGenerics { public static void main(string[] args) { ArrayList apples = new ArrayList(); for(int i = 0; i < 3; i++) apples.add(new Apple()); // Not prevented from adding an Orange to apples: apples.add(new Orange()); for(int i = 0; i < apples.size(); i++) ((Apple)apples.get(i)).id(); // Orange is detected only at run time

17 容器简介类型安全的容器定义容器为只能存放某种类型的对象编译时确定类型泛型编程 (generic)

18 class Apple { private static long counter; private final long id = counter++; public long id() { return id; class Orange { public class ApplesAndOrangesWithGenerics { public static void main(string[] args) { ArrayList<Apple> apples = new ArrayList<Apple>(); for(int i = 0; i < 3; i++) apples.add(new Apple()); // Compile error! // apples.add(new Orange()); for(int i = 0; i < apples.size(); i++) apples.get(i).id(); for(apple c: apples) System.out.println(c.id());

19 类型安全的容器 Upcasting 适用容器简介

20 class GrannySmith extends Apple { class Gala extends Apple { class Fuji extends Apple { class Braeburn extends Apple { public class GenericsAndUpcasting { public static void main(string[] args) { ArrayList<Apple> apples = new ArrayList<Apple>(); apples.add(new GrannySmith()); apples.add(new Gala()); apples.add(new Fuji()); apples.add(new Braeburn()); for(apple c : apples) System.out.println(c);

21 容器简介类型安全的容器不能指定基本类型使用基本类型的 wrapper Autoboxing and unboxing import java.util.*; // compile error // ArrayList<int> a = new ArrayList<int>(); ArrayList<Integer> a = new ArrayList<Integer>(); For (int i = 0; i < 10; ++i) a.add(i); //autoboxing

22 容器简介容器接口 Collection 接口 : 用于存放一组对象 List 接口 : 需按照插入顺序排列 Set 接口 : 不能有重复的元素 Queue 接口 : 按照 " 队列 " 规则输出元素 Map 接口一组 key-value 按照 key 查找对应的 value 也称为 dictionary, associative array

23 容器简介 import java.util.*; //List is an interface List<Apple> a = new ArrayList<Apple>(); List<Apple> b = new LinkedList<Apple>(); //Collection is an interface Collection<Apple> c = new ArrayList<Apple>();

24 容器简介输出容器容器重写了 tostring() 方法, 可以帮助可视化容器的内容 import java.util.*; ArrayList<String> a = new ArrayList<String>(); a.add( rat ); a.add( cat ); a.add( dog ); a.add( dog ); System.out.println(a);

25 public class PrintContainers{ static Collection fill(collection<string> c){ c.add( rat ); c.add( cat ); c.add( dog ); c.add( dog ); static Map fill(map<string, String> m){ m.put( rat, Fuzzy ); m.put( cat, Rags ); m.put( dog, Bosco ); m.put( dog, Spot ); public static void main(string [] args){ System.out.println(fill(new ArrayList<String>())); System.out.println(fill(new LinkedList<String>())); System.out.println(fill(new HashSet<String>())); System.out.println(fill(new TreeSet<String>())); System.out.println(fill(new LinkedHashSet<String>())); [rat, cat, dog, dog] //ArrayList [rat, cat, dog, dog] //LinkedList [cat, dog, rat] // HashSet [cat, dog, rat] // TreeSet [rat, cat, dog] // LinkedHashSet {cat=fuzzy, dog=spot, rat=fuzzy //HashMap {cat=fuzzy, dog=spot, rat=fuzzy //TreeMap {rat=fuzzy, cat=fuzzy, dog=spot //LinkedHashMap List: - ArrayList 实现为数组 - LinkedList 实现为链表 Set/Map - Hash: 实现为 hash 表, 查询较块 - Tree: 实现为查询树, 按顺序排列 - LinkedHash: 按照插入顺序排列 System.out.println(fill(new HashMap<String, String>())); System.out.println(fill(new TreeMap<String, String>())); System.out.println(fill(new LinkedHashMap<String, String>()));

26 容器简介总结容器类型 Collection: List, Set, Queue Map 类型安全的容器 ArrayList<T> a = new ArrayList<T>(); Upcasting and Autoboxing

27 List 两种类型的 List ArrayList 可扩展数组适用于随机访问, 插入删除较慢 LinkedList 双向链表适用于顺序访问, 插入删除较快实现了 Queue 接口

28 List Collection List Set Queue ArrayList LinkedList

29 List List 接口 add(): 添加元素 remove(): 删除元素 get(): 返回第 i 个位置的元素 size(): 返回元素数量...

30 ArrayList 对象存储在数组中 ( 可变长数组 ) 优点 : 随机访问快缺点 : 添加 / 删除慢, 空间浪费 ItemN+1 capacity=n Item1 Item2 ItemN 扩张 capacity=2n Item1 Item2 ItemN ItemN+1 ItemN+2 Item2N capacity=2n Item1 Item2 ItemN/2+1 ItemN ItemN+1 ItemN+2 Item2N N/2 capacity=n Item1 Item2 缩减 N/2 free 每次扩张或缩减数组长度时, 保证新的数组有一半的可用空间

31 LinkedList 双向链表优点 : 添加 / 删除较快, 无空间浪费缺点 : 随机访问慢 next next Item1 Item2 Item3... ItemN previous previous next next next Item next Item1 Item2 previous Item3 previous previous previous 插入 next next Item1 Item2 Item3... 删除 previous previous

32 List 构造函数 ArrayList ArrayList<E>(); ArrayList<E>(int initialcapacity); ArrayList<E>(Collection<E> c); LinkedList LinkedList<E>(); LinkedList<E>(Collection<E> c);

33 ArrayList import java.util.*; ArrayList<String> a = new ArrayList<String>(); // 插入 add(object o) a.add( rat ); a.add( cat ); a.add( dog ); a.add( dog ); // 查询 contains (Object o) System.out.println(a.contains( cat )); // 删除 remove(object o) ( 若不在 List 中, 返回 false, 否则返回 true) a.remove( dog ); a.remove( dag ); // 访问第 i 个元素 : get(int) a.get(0); // 对象的数量 : size() a.size(); // 序号 indexof a.indexof( cat );

34 import java.util.*; ArrayList<String> a = new ArrayList<String>(); // 插入 add(object o) a.add( rat ); a.add( cat ); a.add( dog ); a.add( dog ); // 子表 sublist(int fromindex, int toindex) List<String> sub = a.sublist(2, 3); // 是否为空 isempty() System.out.println(a.isEmpty()); // 返回迭代器 iterator() Iterator it = a.iterator(); // 返回 List 迭代器 listiterator() ListIterator lit = a.listiterator(); // 转为数组 String [] aarray = a.toarray();.

35 List Iterator ( 迭代器 ) 通常需要访问 / 遍历 Collection 中的元素 ArrayList<String> a = new ArrayList<String>();... a.get(i); LinkedList<String> b = new LinkedList<String>(); b.get(i); Static void visit(list<string> ls) { ls.get(i);. 缺点依赖于 Collection 接口其他没有实现 Collection 接口的类无法使用函数 visit 解决方法 iterator, 包含方法 next() hasnext() remove() Collection 接口 iterator() 返回该 List 的迭代器

36 List iterator() Import java.util.* public class SimpleIteration { ArrayList<String> a = new ArrayList<String>(); a.add( rat );a.add( cat );a.add( dog );a.add( dog ); Iterator<String> it = a.iterator(); while(it.hasnext()){ String s = it.next(); System.out.println(s); // identical to for(string i: a) System.out.println(i);

37 List iterator Import java.util.* public class Iteration { public static void display(iterator<string> it) while(it.hasnext()){ String s = it.next(); System.out.println(s); public static void main(string[]args){ ArrayList<String> a = new ArrayList<String>(); a.add( rat );a.add( cat );a.add( dog );a.add( dog ); LinkedList<String> b = new LinkedList<String>(a); HashSet<String> c = new HashSet<String>(a); TreeSet<String> d = new TreeSet<String>(a); display(a.iterator()); display(b.iterator()); display(c.iterator()); display(d.iterator());

38 List ListIterator List 接口提供扩展了 Iterator 双向遍历 hasnext(), hasprevious() next(), previous()

39 List LinkedList 实现 List 接口实现 Queue 接口 add(), remove(), element() offer(), poll(), peek() 提供更多的方法

40 List LinkedList 方法 import java.util.*; LinkedList<String> a = new LinkedList<String>(); a.add( rat ); a.add( cat ); a.add( dog ); a.add( dog ); // 返回链表首元素 getfirst(), element(), 若链表为空则抛出异常 a.getfirst(); a.element(); // 返回链表首元素 peek(), 若链表为空则返回 null a.peek(); // 删除并返回链表首元素 removefirst(), remove(), 若链表为空则抛出异常 String s = a.remove(); // 删除并返回链表首元素 poll, 若链表为空则返回 null String s = a.poll();

41 List LinkedList 方法 import java.util.*; LinkedList<String> a = new LinkedList<String>(); a.add( rat ); a.add( cat ); a.add( dog ); a.add( dog ); // 在链表头添加对象 addfirst() a.addfirst( tiger ); // 在链表尾添加对象 add(), addlast(), offer() a.add( cow ); a.addlast( cow );

42 List LinkedList 应用 : Stack 后进先出 (Last In First Out, LIFO) push: 将一个对象入栈 pop: 从栈中取出一个元素 : 按照 LIFO 原则

43 List Item5 Item3 Item4 LinkedList<Item> s = new LinkedList<Item>(); s.push(item1); s.push(item2); s.push(item3); s.pop(); s.push(item4); s.push(item5); s.pop(); s.pop(); Item2 Item1

44 List import java.util.linkedlist; public class Stack<T> { private LinkedList<T> storage = new LinkedList<T>(); public void push(t v) { storage.addfirst(v); public T peek() { return storage.getfirst(); public T pop() { return storage.removefirst(); public boolean empty() { return storage.isempty(); public String tostring() { return storage.tostring(); public class StackTest { public static void main(string[] args) { Stack<String> stack = new Stack<String>(); for(string s : "My dog has fleas".split(" ")) stack.push(s); while(!stack.empty()) System.out.print(stack.pop() + " ");

45 List Stack 的应用上下文无关文法

46 List 总结 List 接口 add(), remove(), get(), size(), indexof() ArrayList 可变长度数组 LinkedList 链表实现 Queue 接口迭代器 Iterator

47 Set Collection List Set Queue HashSet TreeSet LinkedHasList

48 Set Set 接口容器中不能出现重复的元素没有对 Collection 接口扩展三种主要实现 HashSet TreeSet LinkedHashSet

49 Set Set 接口 add(object o), addall(collection<e> c) remove(object o), removeall(collection<e> c) contains(object o) iterator() size() toarray()...

50 Set HashSet 特点 : 快速 ( 插入, 删除, 查找 ), 无序 import java.util.* public class SetOfInteger { public static void main(string[] args) { Random rand = new Random(47); Set<Integer> intset = new HashSet<Integer>(); for (int i = 0; i < 10000; i++) intset.add(rand.nextint(30)); System.out.println(intset);

51 Set TreeSet 特点 : 速度较慢 ( 插入, 删除, 查找 ), 有序 LinkedHashSet 特点 : 速度快, 按插入顺序排列

52 Queue Collection List Set Queue ArrayList LinkedList PriorityQueue

53 Queue Queue 接口队列规则 : 先进先出 (First in, First out) 接口 offer(object o), add(object o): 将对象加入队列尾部 poll(), remove(): 弹出位于队首的对象 peek(), element(): 返回位于队首的对象, 并不删除 LinkedList PriorityQueue

54 import java.util.* public class QueueTest { public static void printq(queue queue) { while(queue.peek()!= null) System.out.print(queue.remove() + " "); System.out.println(); public static void main(string[] args) { Queue<Integer> queue = new LinkedList<Integer>(); Random rand = new Random(47); for(int i = 0; i < 10; i++) queue.offer(rand.nextint(i + 10)); printq(queue); Queue<Character> qc = new LinkedList<Character>(); for(char c : "Brontosaurus".toCharArray()) qc.offer(c); printq(qc);

55 Queue PriorityQueue 优先级队列每次出队时, 选择优先级最高的对象队列中的对象可以比较优先级普通队列也可看成优先级队列 : 优先级为加入队列的时间

56 import java.util.*; public class PriorityQueueTest { public static void main(string[] args) { PriorityQueue<Integer> qi = new PriorityQueue<Integer>(); int [ ] iarray = {25, 22, 20, 18, 14, 9, 3, 1, 1, 2, 3, 9, 14, 18, 21, 23, 25; for (int i: iarray) qi.offer(i); printq(qi); PriorityQueue<Character> qc = new PriorityQueue<Character>(); for(char c : "Brontosaurus.toCharArray()) qc.offer(c); printq(qc);

57 Queue 自定义优先级构造函数 PriorityQueue<E>(int initialcapacity, Comparator<E> comparator) Comparator 接口定义两个元素的优先级关系包含方法 compare(e e1, E e2) Compare 返回负数当 e1 优先级低于 e2 Compare 返回正数当 e1 优先级高于 e2 Compare 返回 0 当 e1 优先级等于 e2

58 public class PriorityQueueTest { public static void main(string[] args) { PriorityQueue<Character> qc = new PriorityQueue<Character>(); for(char c : "Brontosaurus.toCharArray()) qc.offer(c); printq(qc); PriorityQueue<Character> rqc = new PriorityQueue<Character>(10, new Comparator<Character>(){ public int compare(character c1, Character c2){ if (c1 > c2) return -1; else if (c1 < c2) return 1; else return 0; ); for(char c : "Brontosaurus".toCharArray()) rqc.offer(c); printq(rqc);

59 Map Collection Map List Set Queue HashMap TreeMap LinkedHashMap

60 Map Map Key-value pair Key 1 Value 1 Key 2 Value 23 Key n Value n

61 Map Map 接口存入键值对 : put(k key, V value) 返回键对应的值 : get(k key) 是否包含键 key: containskey(object key) 是否包含值 value: containsvalue(object value) 返回键组成的 Set: keyset() 返回值组成的 Collection: values()

62 import java.util.* public class MapTest { public static void main(string[] args) { HashMap<String, String>m = new HashMap<String, String>() m.put( rat, Fuzzy ); m.put( cat, Rags ); m.put( dog, Bosco ); m.put( dog, Spot ); System.out.println(m.get( dog )); System.out.println(m.containKey( dog )); System.out.println(m.containValue( dog )); System.out.println(m.keySet()); System.out.println(m.values());

63 import java.util.* public class MapTest { public static void main(string[] args) { HashMap<String, ArrayList<Integer>>m = new HashMap<>() m.put( rat, new ArrayList<Integer>(Array.asList(1,2,3))); m.put( cat, new ArrayList<Integer>(Array.asList(4,5,6))); m.put( dog, new ArrayList<Integer>(Array.asList(7,8,9))); m.put( dog, new ArrayList<Integer>(Array.asList(10,11,12))); System.out.println(m.get( dog )); System.out.println(m.containKey( dog )); System.out.println(m.keySet()); System.out.println(m.values()); HashMap<String, HashMap<String, Integer>>n = new HashMap<>();...

64 Map Map 建议 : Immutable key

65 迭代器与 foreach Iterable 接口提供 iterator(): 返回迭代器 Collection 扩展了 Iterable 接口 foreach 语句对所有实现 Iterable 接口的类数组

66 Collection Map List Set Queue HashMap TreeMap LinkedHashMap

OOP with Java 通知 Project 4: 4 月 18 日晚 9 点关于抄袭没有分数

OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 4: 4 月 18 日晚 9 点关于抄袭没有分数复习类的复用组合 (composition): has-a 关系 class MyType { public int i; public double d; public char c; public void set(double