Bài giảng Lập trình hướng đối tượng - Chương 7: Đa hình

yValue v2 = new MyValue();
 MyStack s = new MyStack();
 v1.i = v2.i = 100;
 Point p = new Point(); System.out.println(v1.equals(v2));
 Circle c = new Circle(); System.out.println(v1==v2);
 s.push(p); s.push(c); }
 Circle c1 = (Circle) s.pop(); }
 Point p1 = (Point) s.pop();
}
 31 32
 8
 9/18/17
 Bài tập class MyValue {
 int i;
 public boolean equals(Object obj) {
n Viết lại phương thức equals cho lớp MyValue return (this.i == ((MyValue) obj).i);
 (phương thức này kế thừa từ lớp Object) }
 }
 public class EqualsMethod2 {
 public static void main(String[] args) {
 MyValue v1 = new MyValue();
 MyValue v2 = new MyValue();
 v1.i = v2.i = 100;
 System.out.println(v1.equals(v2));
 System.out.println(v1==v2);
 }
 } 34
 Ví dụ: Java 1.5: Template Ví dụ: Java 1.5: Template (2)
 n Dùng Template:
 List myList = new LinkedList();
 myList.add(new Integer(0));
 Integer x = myList.iterator().next();
 //myList.add(new Long(0)); à Error
 n Không dùng Template
 List myList = new LinkedList();
 myList.add(new Integer(0));
 Integer x = (Integer) 
 myList.iterator().next();
 35 36
 9
 9/18/17
 4. Lập trình tổng quát 4.2.1. Cấu trúc dữ liệu-data structure
n 4.1. Giới thiệu n Cấu trúc dữ liệu là cách tổ chức dữ liệu để 
n 4.2. Java generic data structure giải quyết vấn đề.
 n 4.2.1. Data structure n Một số cấu trúc dữ liệu phổ biến:
 n 4.2.2. Java collection framework n Mảng (Array)
 n 4.2.3. Các interface trong Java collection framework n Danh sách liên kết (Linked List)
 n 4.2.4. Các cài đặt cho các interface – implementation
 n Ngăn xếp (Stack)
n
 4.3. Định nghĩa và sử dụng Template n Hàng đợi (Queue)
n 4.4. Ký tự đại diện (Wildcard) n Cây (Tree)
 37 38
 a. Linked List a. Linked List (2)
 n Linked list là cấu trúc gồm các node liên kết với nhau 
 n Thể hiện Node thông qua lớp tự tham chiếu (self-
 thông qua các mối liên kết. Node cuối linked list referential class)
 được đặt là null để đánh dấu kết thúc danh sách.
 class Node 
 n Linked list giúp tiết kiệm bộ nhớ so với mảng trong {
 các bài toán xử lý danh sách. private int data;
 private Node nextNode;
 n Khi chèn/xoá một node trên linked list, không phải 
 // constructors and methods ...
 dãn/dồn các phần tử như trên mảng.
 }
 n Việc truy nhập trên linked list luôn phải tuần tự.
 15 10
 39 40
 10
 9/18/17
 a. Linked List (3) b. Stack
n Một linked list được quản lý bởi tham chiếu tới node n Stack là một cấu trúc theo kiểu LIFO (Last In 
 đầu và node cuối. First Out), phần tử vào sau cùng sẽ được lấy ra 
 trước.
 firstNode lastNode n Hai thao tác cơ bản trên Stack
 n Chèn phần tử: Luôn chèn vào đỉnh Stack 
 (push)
 H D ... Q n Lấy ra phần tử: Luôn lấy ra từ đỉnh Stack 
 (pop)
 41 42
 c. Tree d. Queue
 n Tree là một cấu trúc phi tuyến (non-linear). n Queue (Hàng đợi) là cấu trúc theo kiểu FIFO 
 n Mỗi node trên cây có thể có nhiều liên kết tới node (First In First Out), phần tử vào trước sẽ được 
 khác. lấy ra trước.
 Nút gốc
 n Hai thao tác cơ bản trên hàng đợi
 Nút trong n Chèn phần tử: Luôn chèn vào cuối hàng đợi 
 (enqueue)
 n Lấy ra phần tử: Lấy ra từ đầu hàng đợi 
 (dequeue)
 Nút lá
 43 44
 11
 9/18/17
 e. Binary Search Tree e. Binary Search Tree (2)
 n Cây nhị phân là cây mà mỗi node không có quá 2 
 node con. n Ví dụ về Binary Search Tree
 n Cây tìm kiếm nhị phân là cây nhị phân mà:
 47
 n Giá trị các nút thuộc cây con bên trái nhỏ hơn giá trị của 
 nút cha.
 Cây con trái Cây con phải
 n Giá trị các nút thuộc cây con bên phải lớn hơn giá trị của 
 nút cha. 25 77
 n Duyệt cây nhị phân 11 43 65 93
 n Inorder traversal
 n Preorder traversal 7 17 31 44 68
 n Postorder traversal
 45 46
 4. Lập trình tổng quát 4.2.2. Java Collection Framework
 n Collection là đối tượng có khả năng chứa 
n 4.1. Giới thiệu
 các đối tượng khác.
n 4.2. Java generic data structure
 n Các thao tác thông thường trên collection
 n 4.2.1. Data structure
 n
 n 4.2.2. Java collection framework Thêm/Xoá đối tượng vào/khỏi collection
 n 4.2.3. Các interface trong Java collection framework n Kiểm tra một đối tượng có ở trong collection 
 không
 n 4.2.4. Các cài đặt cho các interface – implementation
 n Lấy một đối tượng từ collection
n 4.3. Định nghĩa và sử dụng Template
 n Duyệt các đối tượng trong collection
n 4.4. Ký tự đại diện (Wildcard)
 n Xoá toàn bộ collection
 47 48
 12
 9/18/17
 4.2.2. Java Collection Framework (2) 4.2.2. Java Collection Framework (3)
n Các collection đầu tiên của Java: n Một số lợi ích của Collections Framework
 n Mảng n Giảm thời gian lập trình
 n Vector: Mảng động n Tăng cường hiệu năng chương trình
 n Hastable: Bảng băm n Dễ mở rộng các collection mới
n Collections Framework (từ Java 1.2) n Khuyến khích việc sử dụng lại mã chương trình
 n Là một kiến trúc hợp nhất để biểu diễn và thao 
 tác trên các collection.
 n Giúp cho việc xử lý các collection độc lập với biểu 
 diễn chi tiết bên trong của chúng.
 49 50
 4.2.2. Java Collection Framework (4) 4. Lập trình tổng quát
n Collections Framework bao gồm n 4.1. Giới thiệu
 n Interfaces: Là các giao tiếp thể hiện tính chất n 4.2. Java generic data structure
 của các kiểu collection khác nhau như List, Set, n 4.2.1. Data structure
 Map.
 n 4.2.2. Java collection framework
 n Implementations: Là các lớp collection có sẵn n 4.2.3. Các interface trong Java collection 
 được cài đặt các collection interfaces. framework
 n Algorithms: Là các phương thức tĩnh để xử lý n 4.2.4. Các cài đặt cho các interface – implementation
 trên collection, ví dụ: sắp xếp danh sách, tìm 
 n 4.3. Định nghĩa và sử dụng Template
 phần tử lớn nhất...
 n 4.4. Ký tự đại diện (Wildcard)
 51 52
 13
 9/18/17
 4.2.3. Interfaces a. Giao diện Collection
n List: Tập các đối tượng tuần tự, kế tiếp nhau, có thể lặp lại n Xác định giao diện cơ bản cho các 
n Set: Tập các đối tượng không lặp lại thao tác với một tập các đối tượng
n Map: Tập các cặp khóa-giá trị (key-value) và không cho n Thêm vào tập hợp
 phép khóa lặp lại n Xóa khỏi tập hợp
 > > n Kiểm tra có là thành viên
 Collection Map
 n Chứa các phương thức thao tác 
 trên các phần tử riêng lẻ hoặc theo 
 khối
 > > > n Cung cấp các phương thức cho 
 Set List SortedMap phép thực hiện duyệt qua các 
 phần tử trên tập hợp (lặp) và 
 > chuyển tập hợp sang mảng
 SortedSet 53 54
 b. Giao diện List c. Giao diện Set
n List kế thừa từ Collection, nó cung cấp thêm các n Set kế thừa từ Collection, hỗ trợ các thao tác xử lý trên 
 phương thức để xử lý collection kiểu danh sách (Danh collection kiểu tập hợp (Một tập hợp yêu cầu các phần 
 sách là một collection với các phần tử được xếp theo tử phải không được trùng lặp).
 chỉ số). n Set không có thêm phương thức riêng ngoài các 
n Một số phương thức của List phương thức kế thừa từ Collection.
 n Object get(int index);
 n Object set(int index, Object o);
 n void add(int index, Object o);
 n Object remove(int index);
 n int indexOf(Object o);
 n int lastIndexOf(Object o);
 55 56
 14
 9/18/17
 d. Giao diện SortedSet
n SortedSet kế thừa từ Set, nó hỗ trợ thao tác trên tập 
 hợp các phần tử có thể so sánh được. Các đối tượng 
 đưa vào trong một SortedSet phải cài đặt giao tiếp Collection, 
 Comparable hoặc lớp cài đặt SortedSet phải nhận một Set và List
 Comparator trên kiểu của đối tượng đó.
n Một số phương thức của SortedSet:
 n Object first(); // lấy phần tử đầu tiên (nhỏ nhất)
 n Object last(); // lấy phần tử cuối cùng (lớn nhất)
 n SortedSet subSet(Object e1, Object e2); // lấy một tập các phần tử 
 nằm trong khoảng từ e1 tới e2.
 57 58
 e. Duyệt collection e. Duyệt collection (2)
n Các phần tử trong collection có thể được duyệt thông n Iterator cho phép duyệt tuần tự một collection.
 qua Iterator. n Các phương thức của Iterator:
n Các lớp cài đặt Collection cung cấp phương thức trả về n boolean hasNext();
 iterator trên các phần tử của chúng. n Object next();
 n void remove();
 Collection c; n Ví dụ:
 Iterator it = c.iterator();
 while ( it.hasNext() ) {
 Point p = (Point) it.next();
 System.out.println( p.toString() );
 }
 Iterator it = c.iterator(); ...
 59 60
 15
 9/18/17
 f. Giao diện Iterator f. Giao diện Iterator (2) - Ví dụ
n Cung cấp cơ chế thuận tiện để Collection c;
 duyệt (lặp) qua toàn bộ nội // Some code to build the 
 dung của tập hợp, mỗi lần là collection
 một đối tượng trong tập hợp
 n Giống như SQL cursor
 Iterator i = c.iterator();
n ListIterator thêm các phương 
 while (i.hasNext()) {
 thức đưa ra bản chất tuần tự 
 của danh sách cơ sở Object o = i.next();
n Iterator của các tập hợp đã sắp // Process this object
 xếp duyệt theo thứ tự tập hợp 61 } 62
 g. Giao diện Map g. Giao tiếp Map (2)
n Xác định giao diện cơ bản để thao tác với một n Map cung cấp 3 cách view dữ liệu:
 tập hợp bao gồm cặp khóa-giá trị
 n View các khoá: 
 n Thêm một cặp khóa-giá trị
 n Xóa một cặp khóa-giá trị Set keySet(); // Trả về các khoá
 n Lấy về giá trị với khóa đã có
 n View các giá trị: 
 n Kiểm tra có phải là thành viên
 (khóa hoặc giá trị) Collection values(); // Trả về các giá trị
n Cung cấp 3 cách nhìn cho n View các cặp khoá-giá trị
 nội dung của tập hợp: Set entrySet(); // Trả về các cặp khoá-giá trị
 n Tập các khóa n Sau khi nhận được kết quả là một collection, ta có 
 n Tập các giá trị thể dùng iterator để duyệt các phần tử của nó.
 n Tập các ánh xạ khóa-giá trị
 63 64
 16
 9/18/17
 h. Giao diện SortedMap 4. Lập trình tổng quát
n Giao diện SortedMap kế thừa từ Map, nó cung cấp thao n 4.1. Giới thiệu
 tác trên các bảng ánh xạ với khoá có thể so sánh được.
 n 4.2. Java generic data structure
n Giống như SortedSet, các đối tượng khoá đưa vào 
 n 4.2.1. Data structure
 trong SortedMap phải cài đặt giao tiếp Comparable 
 hoặc lớp cài đặt SortedMap phải nhận một Comparator n 4.2.2. Java collection framework
 trên đối tượng khoá. n 4.2.3. Các interface trong Java collection framework
 n 4.2.4. Các cài đặt cho các interface –
 implementation
 n 4.3. Định nghĩa và sử dụng Template
 n 4.4. Ký tự đại diện (Wildcard)
 65 66
 4.2.4. Implementations 4.2.4. Implementations (2)
 LinkedList
n Các cài đặt trong Collections Framework chính là các List
 lớp collection có sẵn trong Java. Chúng cài đặt các ArrayList
 collection interface ở trên để thể hiện các cấu trúc dữ 
 liệu cụ thể. Ví dụ: mảng động, danh sách liên kết, cây HashSet
 đỏ đen, bảng băm... Set LinkedHashSet
 SortedSet TreeSet
 HashMap
 Map LinkedHashMap
 SortedMap TreeMap
 67 68
 17
 9/18/17
 4.2.4. Implementations (3) -Mô tả các cài 4.2.4. Implementations (3) -Mô tả các cài 
 đặt đặt
n ArrayList: Mảng động, nếu các phần tử thêm vào vượt n HashMap: Bảng băm (cài đặt của Map).
 quá kích cỡ mảng, mảng sẽ tự động tăng kích cỡ. n LinkedHashMap: Bảng băm kết hợp với linked list nhằm 
n LinkedList: Danh sách liên kết 2 chiều. Hỗ trợ thao tác đảm bảo thứ tự các phần tử (cài đặt của Map).
 trên đầu và cuối danh sách. n TreeMap: Cây đỏ đen (cài đặt của Map).
n HashSet: Bảng băm.
n LinkedHashSet: Bảng băm kết hợp với linked list nhằm 
 đảm bảo thứ tự các phần tử.
n TreeSet: Cây đỏ đen (red-black tree).
 69 70
 public class MapExample {
 public static void main(String args[]) {
 4.2.4. Implementations (3) – Tổng kết Map map = new HashMap();
 Integer ONE = new Integer(1);
 for (int i=0, n=args.length; i<n; i++) {
 String key = args[i];
 Integer frequency =(Integer)map.get(key);
 if (frequency == null) { frequency = ONE; } 
 else {
 int value = frequency.intValue();
 frequency = new Integer(value + 1);
 }
 map.put(key, frequency);
 }
 System.out.println(map);
 Map sortedMap = new TreeMap(map);
 System.out.println(sortedMap);
 71 } 72
 }
 18
 9/18/17
 4. Lập trình tổng quát 4.3. Định nghĩa và sử dụng Template
n 4.1. Giới thiệu
n 4.2. Java generic data structure class MyStack {
 n 4.2.1. Data structure ...
 n 4.2.2. Java collection framework public void push(T x) {...}
 n 4.2.3. Các interface trong Java collection framework public T pop() {
 n 4.2.4. Các cài đặt cho các interface – implementation ...
n 4.3. Định nghĩa và sử dụng Template }
 }
n 4.4. Ký tự đại diện (Wildcard)
 73 74
 Nhắc lại ví dụ: Lập trình tổng quát trên 
 Java dùng upcasting và Object Sử dụng template
class MyStack { public class Test {
 ... public static void main(String args[]) {
 public void push(Object obj) {...}
 MyStack s1 = new MyStack();
 public Object pop() {...} s1.push(new Integer(0));
} Integer x = s1.pop();
public class TestStack{
 MyStack s = new MyStack(); //s1.push(new Long(0)); à Error
 Point p = new Point();
 MyStack s2 = new MyStack();
 Circle c = new Circle(); s2.push(new Long(0));
 s.push(p); s.push(c); Long y = s2.pop();
 Circle c1 = (Circle) s.pop();
 Point p1 = (Point) s.pop(); }
} }
 75 76
 19
 9/18/17
 Định nghĩa Iterator 4. Lập trình tổng quát
public interface List{ n 4.1. Giới thiệu
 void add(E x);
 n 4.2. Java generic data structure
 Iterator iterator();
 n 4.2.1. Data structure
}
 n 4.2.2. Java collection framework
public interface Iterator{ n 4.2.3. Các interface trong Java collection framework
 E next(); n 4.2.4. Các cài đặt cho các interface – implementation
 boolean hasNext(); n 4.3. Định nghĩa và sử dụng Template
}
 n 4.4. Ký tự đại diện (Wildcard)
class LinkedList implements List { 
// implementation 
} 77 78
 4.4. Ký tự đại diện (Wildcard) Ví dụ: Sử dụng Wildcards
 public class Test {
public class Test { void printList(List lst) {
 public static void main(String args[]) { Iterator it = lst.iterator();
 List lst0 = new LinkedList(); while (it.hasNext())
 //List lst1 = lst0; à Error System.out.println(it.next());
 //printList(lst0); à Error }
 }
 public static void main(String args[]) {
 void static printList(List lst) { List lst0 = 
 Iterator it = lst.iterator(); new LinkedList();
 while (it.hasNext()) List lst1 = 
 System.out.println(it.next()); new LinkedList();
 }
} printList(lst0); // String
 printList(lst1); // Employee
 79 } 80
 }
 20
 9/18/17
 Các ký tự đại diện Java 1.5 Ví dụ wildcard (1)
 public void printCollection(Collection c) { 
n "? extends Type": Xác định một tập các kiểu 
 con của Type. Đây là wildcard hữu ích nhất. Iterator i = c.iterator(); 
 for(int k = 0;k<c.size();k++) { 
n "? super Type": Xác định một tập các kiểu System.out.println(i.next()); 
 cha của Type } 
 } 
n "?": Xác định tập tất cả các kiểu hoặc bất kỳ 
 kiểu nào. à Sử dụng wildcard:
 void printCollection(Collection c) { 
 for(Object o:c) { 
 System.out.println(o); 
 } 
 } 
 81 82
 Ví dụ wildcard (2) Template Java 1.5 vs. C++
public void draw(List shape) { 
 n Template trong Java không sinh ra các lớp 
 for(Shape s: shape) { mới
 s.draw(this); 
 } n Kiểm tra sự thống nhất về kiểu khi biên dịch
 } n Các đối tượng về bản chất vẫn là kiểu Object
à Khác như thế nào với:
public void draw(List shape) { 
 // rest of the code is the same 
} 
 83 84
 21