Lập trình hướng đối tượng - Bài 9: Lập trình tổng quát

Nội dung text: Lập trình hướng đối tượng - Bài 9: Lập trình tổng quát

1. Bộ môn Công nghệ Phần mềm Viện CNTT & TT Trường Đại học Bách Khoa Hà Nội IT3100 LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG Bài 09. Lập trình tổng quát
2. Mục tiêu ◼ Giới thiệu về lập trình tổng quát và cách thực hiện trong các ngôn ngữ lập trình ◼ Giới thiệu về collection framework với các cấu trúc tổng quát: List, HashMap, Tree, Set, Vector, ◼ Định nghĩa và sử dụng Template và ký tự đại diện (wildcard) ◼ Ví dụ và bài tập về các vấn đề trên với ngôn ngữ lập trình Java 2
3. Nội dung 1. Giới thiệu về lập trình tổng quát 2. Lập trình tổng quát trong Java ◼ Giới thiệu về collection framework ◼ Giới thiệu về các cấu trúc tổng quát List, HashMap, Tree, Set, Vector 3. Định nghĩa và sử dụng Template 4. Ký tự đại diện (Wildcard) 5. Ví dụ và bài tập 3
4. 1. Giới thiệu về lập trình tổng quát (Generic programming) 4
5. 1. Giới thiệu về lập trình tổng quát ◼ Tổng quát hóa chương trình để có thể hoạt động với các kiểu dữ liệu khác nhau, kể cả kiểu dữ liệu trong tương lai Tổng quát hoá ◼ Thuật toán đã xác định chương trình ◼ Ví dụ: • Số nguyên int • Xâu ký tự String Thuật toán giống nhau, Phương thức sort() • Đối tượng số phức chỉ khác về kiểu dữ liệu Complex object • • Lớp IntegerStack → đối Các lớp có cấu tượng Integer trúc tương tự, Lớp lưu trữ kiểu • Lớp StringStack → đối khác nhau về ngăn xếp (Stack) tượng String kiểu đối tượng • Lớp AnimalStack → đối xử lý tượng animal, 5
6. 1. Giới thiệu về lập trình tổng quát ◼ Lập trình Generic có nghĩa là lập trình mà có thể tái sử dụng cho nhiều kiểu dữ liệu ◼ Cho phép trừu tượng hóa kiểu dữ liệu ◼ Giải pháp trong các ngôn ngữ lập trình: ◼ C: dùng con trỏ không định kiểu (con trỏ void) ◼ C++: dùng template ◼ Java 1.5 trở về trước: lợi dụng upcasting và kiểu tổng quát object ◼ Java 1.5: đưa ra khái niệm về template 6
7. 1. Giới thiệu về lập trình tổng quát ◼ Ví dụ C: hàm memcpy() trong thư viện string.h void* memcpy(void* region1, const void* region2, size_t n); ◼ Hàm memcpy() bên trên được khai báo tổng quát bằng cách sử dụng các con trỏ void* ◼ Điều này giúp cho hàm có thể sử dụng với nhiều kiểu dữ liệu khác nhau ◼ Dữ liệu được truyền vào một cách tổng quát thông qua địa chỉ và kích thước kiểu dữ liệu ◼ Hay nói cách khác, để sao chép dữ liệu, ta chỉ cần địa chỉ và kích cỡ của chúng 7
8. 1. Giới thiệu về lập trình tổng quát ◼ Ví dụ: Lập trình Generic từ trước Java 1.5 public class ArrayList { public Object get(int i) { . . . } public void add(Object o) { . . . } . . . private Object[] elementData; } ◼ Lớp Object là lớp cha tổng quát nhất → có thể chấp nhận các đối tượng thuộc lớp con của nó List myList = new ArrayList(); Các đối tượng myList.add("Fred"); trong một danh myList.add(new Dog()); sách khác hẳn myList.add(new Integer(42)); nhau ◼ Hạn chế: Phải ép kiểu ➔ có thể ép sai kiểu (run-time error) String name = (String) myList.get(1); //Dog!!! 8
9. 1. Giới thiệu về lập trình tổng quát ◼ Ví dụ: Lập trình Generic từ Java 1.5 ◼ Java 1.5 Template Danh sách chỉ chấp nhận các đối tượng có kiểu là Integer List myList = new LinkedList (); myList.add(new Integer(0)); Integer x = myList.iterator().next(); //Không cần ép kiểu myList.add(new String("Hello")); //Compile Error 9
10. 2. Lập trình tổng quát trong Java (Collection framework) 10
11. 2. Lập trình tổng quát trong Java ◼ Collection – tập hợp: Nhóm các đối tượng lại thành một đơn vị duy nhất ◼ Java Collections Framework: ◼ Biểu diễn các tập hợp ◼ Cung cấp giao diện tiêu chuẩn cho hầu hết các tập hợp cơ bản ◼ Xây dựng dựa trên ◼ Interface: thể hiện tính chất của các kiểu tập hợp khác nhau như List, Set, Map ◼ Class: các lớp cụ thể thực thi các giao diện ◼ Thuật toán: cài đặt một số thao tác đơn giản, là các phương thức tĩnh để xử lý trên collection như tìm kiếm, sắp xếp 11
12. 2. Lập trình tổng quát trong Java ◼ Java Collections Framework: ◼ List: Tập các đối tượng tuần tự, kế tiếp nhau, có thể lặp lại ◼ Set: Tập các đối tượng không lặp lại ◼ Map: Tập các cặp khóa-giá trị (key-value) và không cho phép khóa lặp lại ◼ Liên kết các đối tượng trong tập này với đối các đối tượng trong tập khác như tra từ điển/danh bạ điện thoại. 12
13. 2. Lập trình tổng quát trong Java ◼ Cây cấu trúc giao diện Collection > > Map Collection HashMap HashTable > Sorted Map > > Set List Tree Map HashSet > Array List Vector LinkedList Sorted Set Tree Set 13
14. 2. Lập trình tổng quát trong Java ◼ So sánh Tập hợp và mảng Tập hơp Mảng Tập hợp (có thể) truy xuất theo Mảng truy xuất 1 cách tuần tự dạng ngẫu nhiên Tập hợp có thể chứa nhiều loại Mảng chứa 1 loại đối tượng/dữ đối tượng/dữ liệu khác nhau liệu nhất định Dùng theo kiểu tập hợp xây Dùng tổ chức dữ liệu theo dựng sẵn của Java chỉ khai báo mảng phải lập trình hoàn toàn và gọi những phương thức đã được định nghĩa Duyệt các phần tử tập hợp Duyệt các phần tử mảng tuần thông qua Iterator tự thông qua chỉ số mảng 14
15. 2. Lập trình tổng quát trong Java ◼ Các giao diện và lớp thực thi trong Collection framework của Java đều được xây dựng theo template ◼ → cho phép xác định tập hợp các phần tử cùng kiểu nào đó bất kỳ ◼ Cho phép chỉ định kiểu dữ liệu của các Collection ➔ hạn chế việc thao tác sai kiểu dữ liệu 15
16. 2. Lập trình tổng quát trong Java ◼ Ví dụ public interface List { void add(E x); Iterator iterator(); } ◼ Ví dụ List myList = new ArrayList (); myList.add("Fred"); // OK myList.add(new Dog()); //Compile error! String s = myList.get(0); 16
17. Giao diện Collection ◼ Xác định giao diện cơ bản cho các thao tác với một tập các đối tượng ◼ Thêm vào tập hợp ◼ Xóa khỏi tập hợp ◼ Kiểm tra có là thành viê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 ◼ Cung cấp các phương thức cho 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 17
18. Giao diện Collection public interface Collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); boolean remove(Object element); Iterator iterator(); // Bulk Operations boolean addAll(Collection c); boolean removeAll(Collection c); boolean retainAll(Collection c); . // Array Operations Object[] toArray(); Object[] toArray(Object a[]); } 18
19. ◼ Các giao diện con kế thừa giao diện Collection 19
20. Giao diện Set ◼ Set kế thừa từ Collection, hỗ trợ các thao tác xử lý trên collection kiểu tập hợp ◼ Ví dụ: ◼ Set of cars: ◼ {BMW, Ford, Jeep, Chevrolet, Nissan, Toyota, VW} ◼ Nationalities in the class ◼ {Chinese, American, Canadian, Indian} ◼ Một tập hợp các phần tử không được trùng lặp. ◼ Set không có thêm phương thức riêng ngoài các phương thức kế thừa từ Collection. 20
21. Giao diện SortedSet ◼ SortedSet : kế thừa giao diện Set ◼ Các phần tử được sắp xếp theo một thứ tự ◼ Không có các phần tử trùng nhau ◼ Cho phép một phần tử là null ◼ Các đối tượng đưa vào trong một SortedSet phải cài đặt giao diện Comparable hoặc lớp cài đặt SortedSet phải nhận một Comparator trên kiểu của đối tượng đó ◼ Phương thức: tương tự Set, thêm 2 phương thức ◼ first( ): lấy phần tử đầu tiên (nhỏ nhất) ◼ last( ): lấy phần tử cuối cùng (lớn nhất) ◼ 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 21
22. Giao diện List ◼ List kế thừa từ Collection, nó cung cấp thêm các phương thức để xử lý collection kiểu danh sách ◼ Danh sách là một collection với các phần tử được xếp theo chỉ số ◼ Một số phương thức của List ◼ Object get(int index); ◼ Object set(int index, Object o); ◼ void add(int index, Object o); ◼ Object remove(int index); ◼ int indexOf(Object o); ◼ int lastIndexOf(Object o); 22
23. Giao diện Map ◼ Xác định giao diện cơ bản để thao tác với một tập hợp bao gồm cặp khóa-giá trị ◼ Thêm một cặp khóa-giá trị ◼ Xóa một cặp khóa-giá trị ◼ Lấy về giá trị với khóa đã có ◼ Kiểm tra có phải là thành viên (khóa hoặc giá trị) ◼ Cung cấp 3 cách nhìn cho nội dung của tập hợp: ◼ Tập các khóa ◼ Tập các giá trị ◼ Tập các ánh xạ khóa-giá trị 23
24. Giao diện Map ◼ Giao diện Map cung cấp các thao tác xử lý trên các bảng ánh xạ ◼ Bảng ánh xạ lưu các phần tử theo khoá và không được có 2 khoá trùng nhau ◼ Một số phương thức của Map ◼ Object put(Object key, Object value); ◼ Object get(Object key); ◼ Object remove(Object key); ◼ boolean containsKey(Object key); ◼ boolean containsValue(Object value); ◼ 24
25. Giao diện SortedMap ◼ Giao diện SortedMap ◼ thừa kế giao diện Map ◼ các phần tử được sắp xếp theo thứ tự ◼ tương tự SortedSet, tuy nhiên việc sắp xếp được thực hiện với các khóa ◼ Phương thức: Tương tự Map, bổ sung thêm: ◼ firstKey( ): returns the first (lowest) value currently in the map ◼ lastKey( ): returns the last (highest) value currently in the map 25
26. Các lớp thực thi giao diện Collection ◼ Java đã xây dựng sẵn một số lớp thực thi các giao diện Set, List và Map và cài đặt các phương thức tương ứng 26
27. Các lớp thực thi giao diện Collection ◼ ArrayList: Mảng động, nếu các phần tử thêm vào vượt quá kích cỡ mảng, mảng sẽ tự động tăng kích cỡ ◼ LinkedList: Danh sách liên kết ◼ Hỗ trợ thao tác trên đầu và cuối danh sách ◼ Được sử dụng để tạo ngăn xếp, hàng đợi, cây 27
28. Các lớp thực thi giao diện Collection ◼ HashSet: Bảng băm ◼ Lưu các phần tử trong một bảng băm ◼ Không cho phép lưu trùng lặp ◼ Cho phép phần tử null 28
29. Các lớp thực thi giao diện Collection ◼ 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ử ◼ Thừa kế HashSet và thực thi giao diện Set ◼ Khác HashSet ở chỗ nó lưu trữ trong một danh sách móc nối đôi ◼ Thứ tự các phần tử được sắp xếp theo thứ tự được insert vào tập hợp ◼ TreeSet: Cho phép lấy các phần tử trong tập hợp theo thứ tự đã sắp xếp ◼ Các phần tử được thêm vào TreeSet tự động được sắp xếp ◼ Thông thường, ta có thể thêm các phần tử vào HashSet, sau đó convert về TreeSet để duyệt theo thứ tự nhanh hơn29
30. Các lớp thực thi giao diện Collection ◼ HashMap: Bảng băm (cài đặt của Map) ◼ LinkedHashMap: Bảng băm kết hợp với linked list nhằm đảm bảo thứ tự các phần tử (cài đặt của Map) ◼ TreeMap: Cây (cài đặt của Map) ◼ Legacy Implementations ◼ Là các lớp cũ được cài đặt bổ sung thêm các collection interface. ◼ Vector: Có thể thay bằng ArrayList ◼ Hastable: Có thể thay bằng HashMap 30
31. Các lớp thực thi giao diện Collection ◼ Ví dụ: ArrayList names = new ArrayList (); names.add("Emily"); names.add("Bob"); names.add("Cindy"); 31
32. Các lớp thực thi giao diện Collection String name = names.get(0); ◼ Ví dụ: names.add(1, "Ann"); names.remove(1); 32
33. Câu hỏi ◼ Sau khi thực hiện đoạn chương trinh sau, danh sách names có chứa các phần tử nào? ArrayList names = new ArrayList ; names.add("Bob"); names.add(0, "Ann"); names.remove(1); names.add("Cal"); 33
34. Giao diện Iterator và Comparator ◼ Sử dụng để duyệt và so sánh trên các Collection ◼ Iterator ◼ Các phần tử trong collection có thể được duyệt thông qua Iterator Collection c; Iterator it = c.iterator(); 34
35. Giao diện Iterator và Comparator ◼ Iterator ◼ Cung cấp cơ chế thuận tiện để duyệt (lặp) qua toàn bộ nội dung của tập hợp, mỗi lần là một đối tượng trong tập hợp ◼ Giống như SQL cursor ◼ Iterator của các tập hợp đã sắp xếp duyệt theo thứ tự tập hợp ◼ ListIterator thêm các phương thức đưa ra bản chất tuần tự của danh sách cơ sở 35
36. Giao diện Iterator và Comparator ◼ Iterator : Các phương thức ◼ iterator( ): yêu cầu container trả về một iterator ◼ next( ): trả về phần tử tiếp theo ◼ hasNext( ): kiểm tra có tồn tại phần tử tiếp theo hay không ◼ remove( ): xóa phần tử gần nhất của iterator 36
37. Giao diện Iterator và Comparator ◼ Iterator: Ví dụ ◼ Định nghĩa iterator public interface Iterator { boolean hasNext(); Object next(); void remove(); } Tương tự vòng lặp for for (String name : names){ ◼ Sử dụng iterator System.out.println(name); Collection c; } Iterator i = c.iterator(); while (i.hasNext()) { Object o = i.next(); // Process this object } 37
38. Giao diện Iterator và Comparator ◼ Giao diện Comparator được sử dụng để cho phép so sánh hai đối tượng trong tập hợp ◼ Một Comparator phải định nghĩa một phương thức compare( ) lấy 2 tham số Object và trả về -1, 0 hoặc 1 ◼ Không cần thiết nếu tập hợp đã có khả năng so sánh tự nhiên (vd. String, Integer ) 38
39. Giao diện Iterator và Comparator ◼ Ví dụ lớp Person: class Person { private int age; private String name; public void setAge(int age){ this.age=age; } public int getAge(){ return this.age; } public void setName(String name){ this.name=name; } public String getName(){ return this.name; } } 39
40. Giao diện Iterator và Comparator ◼ Ví dụ Cài đặt AgeComparator : class AgeComparator implements Comparator { public int compare(Object ob1, Object ob2) { int ob1Age = ((Person)ob1).getAge(); int ob2Age = ((Person)ob2).getAge(); if(ob1Age > ob2Age) return 1; else if(ob1Age < ob2Age) return -1; else return 0; } } 40
41. Giao diện Iterator và Comparator ◼ Ví dụ Sử dụng AgeComparator : public class ComparatorExample { public static void main(String args[]) { ArrayList lst = new ArrayList (); Person p = new Person(); p.setAge(35); p.setName("A"); lst.add(p); p = new Person(); p.setAge(30); p.setName("B"); lst.add(p); p = new Person(); p.setAge(32); p.setName("C"); 41 lst.add(p);
42. Giao diện Iterator và Comparator ◼ Ví dụ Sử dụng AgeComparator : System.out.println("Order before sorting"); for (Person person : lst) { System.out.println(person.getName() + "\t" + person.getAge()); } Collections.sort(lst, new AgeComparator()); System.out.println("\n\nOrder of person" + "after sorting by age"); for (Iterator i = lst.iterator(); i.hasNext();) { Person person = i.next(); System.out.println(person.getName() + "\t" + person.getAge()); } //End of for } //End of main 42 } //End of class
43. 3. Định nghĩa và sử dụng Template 43
44. Lớp tổng quát ◼ Lớp tổng quát (generic class) là lớp có thể nhận kiểu dữ liệu là một lớp bất kỳ ◼ Cú pháp Tên Lớp { } ◼ Các phương thức hay thuộc tính của lớp tổng quát có thể sử dụng các kiểu được khai báo như mọi lớp bình thường khác 44
45. Lớp tổng quát Tên kiểu, sẽ được thay thế bằng một kiểu cụ thể khi sử dụng ◼ Ví dụ: public class Information { private T value; public Information(T value) { this.value = value; } public T getValue() { return value; } } Information mystring = new Information ("hello"); Information circle = new Information (new Circle()); Information shape = new Information<>(new 2DShape()); 45
46. Lớp tổng quát ◼ Quy ước đặt tên kiểu Tên kiểu Mục đích E Các thành phần trong một collection K Kiểu khóa trong Map V Kiểu giá trị trong Map T Các kiểu thông thường S, U Các kiểu thông thường khác ◼ Chú ý: Không sử dụng các kiểu dữ liệu nguyên thủy cho các lớp tổng quát Information integer = new Information (2012); //Error Information integer = new Information (2012); //OK 46
47. Phương thức tổng quát ◼ Phương thức tổng quát (generic method) là các phương thức tự định nghĩa kiểu tham số của nó ◼ Có thể được viết trong lớp bất kỳ (tổng quát hoặc không) ◼ Cú pháp (chỉ định truy cập) (kiểu trả về) tên phương thức (danh sách tham số) { // } ◼ Ví dụ public static void print(E[] a) }{ 47
48. Phương thức tổng quát ◼ Ví dụ: public class ArrayTool { // Phương thức in các phần tử trong mảng String public static void print(String[] a) { for (String e : a) System.out.print(e + " "); System.out.println(); } // Phương thức in các phần tử trong mảng với kiểu // dữ liệu bất kỳ public static void print(E[] a) { for (E e : a) System.out.print(e + " "); System.out.println(); } } 48
49. Phương thức tổng quát ◼ Ví dụ: String[] str = new String[5]; Point[] p = new Point[3]; int[] intnum = new int[2]; ArrayTool.print(str); ArrayTool.print(p); // Không dùng được với kiểu dữ liệu nguyên thủy ArrayTool.print(intnum); 49
50. Giới hạn kiểu dữ liệu tổng quát ◼ Có thể giới hạn các kiểu dữ liệu tổng quát sử dụng phải là dẫn xuất của một hoặc nhiều lớp ◼ Giới hạn 1 lớp ◼ Giới hạn nhiều lớp 50
51. Giới hạn kiểu dữ liệu tổng quát Chấp nhận các kiểu là lớp con của 2DShape ◼ Ví dụ: public class Information { private T value; public Information(T value) { this.value = value; } public T getValue() { return value; } } Information pointInfo = new Information (new Point()); // OK Information stringInfo = new Information (); // error 51
52. 4. Ký tự đại diện (Wildcard) 52
53. 4. Ký tự đại diện (Wildcard) ◼ Quan hệ thừa kế giữa hai lớp không có ảnh hưởng gì đến quan hệ giữa các cấu trúc tổng quát dùng cho hai lớp đó. ◼ Ví dụ: ◼ Dog và Cat là các lớp con của Animal ◼ → Có thể đưa các đối tượng Dog và Cat vào một ArrayList ◼ Tuy nhiên, ArrayList , ArrayList lại không có quan hệ gì với ArrayList 53
54. 4. Ký tự đại diện (Wildcard) ◼ Generic ◼ Kiểu khai báo trong lớp tổng quát (template) khi khởi tạo phải cùng với kiểu của các đối tượng thực sự. ◼ Nếu khai báo List ➔ Danh sách chỉ chấp nhận các đối tượng lớp Foo, các đối tượng là cha hoặc con của lớp Foo sẽ không được chấp nhận. class Parent { } class Child extends Parent { } List myList = new ArrayList (); 54
55. 4. Ký tự đại diện (Wildcard) ◼ Làm thế nào để xây dựng các tập hợp dành cho kiểu bất kì là lớp con của lớp cụ thể nào đó? → Giải pháp là sử dụng kí tự đại diện (wildcard) ◼ Ký tự đại diện: ? dùng để hiển thị cho một kiểu dữ liệu chưa biết trong collection void printCollection(Collection c) { for (Object e : c) { System.out.println(e); } } ◼ Khi biên dịch, dấu ? có thể được thay thế bởi bất kì kiểu dữ liệu nào. 55
56. 4. Ký tự đại diện (Wildcard) ◼ Tuy nhiên viết như thế này là không hợp lệ Collection c = new ArrayList (); c.add("a1"); //compile error, null ◼ Vì không biết c đại diện cho tập hợp kiểu dữ liệu nào ➔ không thể thêm phần tử vào c 56
57. 4. Ký tự đại diện (Wildcard) ◼ "? extends Type": Xác định một tập các kiểu con của Type. Đây là wildcard hữu ích ◼ "? super Type": Xác định một tập các kiểu cha của Type ◼ "?": Xác định tập tất cả các kiểu hoặc bất kỳ kiểu nào 57
58. 4. Ký tự đại diện (Wildcard) ◼ Ví dụ: ◼ ? extends Animal có nghĩa là kiểu gì đó thuộc loại Animal ◼ Hai cú pháp sau là tương đương: public void foo( ArrayList a) public void foo( ArrayList a) ◼ Dùng "T", thường được sử dụng khi còn muốn T xuất hiện ở các vị trí khác 58
59. Câu hỏi public void draw(List shape) { for(Shape s: shape) { s.draw(this); } } → Khác như thế nào với: public void draw(List shape){ for(Shape s: shape) { s.draw(this); } } 59
60. Tổng kết 60
61. Tổng kết ◼ Generic programming: tổng quát hóa chương trình để có thể hoạt động với các kiểu dữ liệu khác nhau, kể cả kiểu dữ liệu trong tương lai với thuật toán đã xác định ◼ Trong Java sử dụng Template ◼ Collection – tập hợp: Nhóm các đối tượng lại thành một đơn vị duy nhất ◼ Java Collections Framework: biểu diễn các tập hơn, cung cấp giao diện tiêu chuẩn (giao diện, lớp thực thi, thuật toán) ◼ Lớp tổng quát (generic class) là lớp có thể nhận 61 kiểu dữ liệu là một lớp bất kỳ
62. Bài tập 62
63. Bài 1 ◼ Trừu tượng hoá mô tả sau: một quyển sách là tập hợp các chương, chương là tập hợp các trang. ◼ Phác hoạ các lớp Book, Chapter, và Page ◼ Tạo các thuộc tính cần thiết cho các lớp, hãy tận dụng tập hợp như là thuộc tính của lớp ◼ Tạo các phương thức cho lớp Chapter cho việc thêm trang và xác định một chương có bao nhiêu trang ◼ Tạo các phương thức cho lớp Book cho việc thêm chương và xác định quyển sách có bao nhiêu chương, và số trang cho quyển sách 63
64. Bài 2 ◼ Xây dựng lớp Stack tổng quát với các kiểu dữ liệu StackOfChars StackOfIntegers - elements: char[] - elements: int[] - size: int - size: int + StackOfChars() + StackOfIntegers() + StackOfChars (capacity: int) + StackOfIntegers (capacity: int) + isEmpty(): boolean + isEmpty(): boolean + isFull(): boolean + isFull(): boolean + peak(): char + peak(): int + push(value:char): void + push(value:int): void + pop(): char + pop(): int + getSize(): int + getSize(): int 64