Bài 9 lập trình tổng quát | Bài giảng lập trình hướng đối tượng

Mục tiêu
v 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
v Giới thiệu về col ecBài 9: Lập trình tổng
tổng quát: List, HashMap, Tree, Set, Vector,… quát
v Định nghĩa và sử dụng Template và ký tự đại diện (wildcard)
v Ví dụ và bài tập về các vấn đề trên với ngôn ngữ lập trình Java 1 2 1 2 Nội dung Nội dung
1. Giới thiệu về lập trình tổng quát
1. Giới thiệu về lập trình tổng quát
2. Định nghĩa và sử dụng Template
2. Định nghĩa và sử dụng Template
3. Lập trình tổng quát trong Java col ections
3. Lập trình tổng quát trong Java col ecframework framework
4. Ký tự đại diện (Wildcard)
4. Ký tự đại diện (Wildcard) 5. Ví dụ và bài tập 5. Ví dụ và bài tập 3 4 3 4 1
1. Giới thiệu về lập trình tổng quát
1. Giới thiệu về lập trình tổng quát
v Lập trình tổng quát(Generic programming): Tổng v Lập trình tổng quát
quát hóa chương trình để có thể hoạt động với các kiểu dữ
§ C: dùng con trỏ không định kiểu (con trỏ void)
liệu khác nhau, kể cả kiểu dữ liệu trong tương lai § C++: dùng template
§ Thuật toán đã xác định
§ Java 1.5 trở về trước: lợi dụng upcasting, downcasting v Ví dụ: và lớp object • Số nguyên int
§ Java 1.5: đưa ra khái niệm về template • Xâu ký tự String
Thuật toán giống nhau, chỉ Phương thức sort()
• Đối tượng số phức
khác về kiểu dữ liệu Complex object • ...
• Lớp IntegerStack à đối
Các lớp có cấu trúc tượng Integer
tương tự, khác nhau Lớp lưu trữ kiểu ngăn
• Lớp StringStack à đối
về kiểu đối tượng xếp (Stack) tượng String xử lý
• Lớp AnimalStack à đối tượng animal,… 5 6 5 6
1. Giới thiệu về lập trình tổng quát
1. Giới thiệu về lập trình tổng quát
v Ví dụ C: hàm memcpy() trong thư viện string.h
v Ví dụ: Lập trình tổng quát từ trước Java 1.5
void* memcpy(void* region1, const void* region2, size_t n);
public class ArrayList {
public Object get(int i) { . . . }
§ Hàm memcpy() bên trên được khai báo tổng quát bằng
public void add(Object o) { . . . }
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
private Object[] elementData; 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
v Lớp Object là lớp cha tổng quát nhất à có thể chấp nhận
• Hay nói cách khác, để sao chép dữ liệu, ta chỉ cần địa chỉ và
các đối tượng thuộc lớp con của nó kích cỡ của chúng
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 nhau
myList.add(new Integer(42));
v Hạn chế: Phải ép kiểu è có thể ép sai kiểu (run-time error)
String name = (String) myList.get(1); //Dog!!! 7 8 7 8 2
1. Giới thiệu về lập trình tổng quát Nội dung
v Ví dụ: Lập trình Generic từ Java 1.5
1. Giới thiệu về lập trình tổng quát § Java 1.5 Template
2. Định nghĩa và sử dụng Template
3. Lập trình tổng quát trong Java col ecframework
Danh sách chỉ chấp nhận các
đối tượng có kiểu là Integer
4. Ký tự đại diện (Wildcard) 5. Ví dụ và bài tập 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 9 10 Lớp tổng quát Lớp tổng quát
Tên kiểu, sẽ được thay thế bằng một kiểu cụ
v Lớp tổng quát (generic class) là lớp có thể nhận thể khi sử dụng
kiểu dữ liệu là một lớp bất kỳ v Ví dụ: v Cú pháp
public class Information { private T value; Tên Lớp
public Information(T value) { { this.value = value; } public T getValue() { return value; } } }
v Các phương thức hay thuộc tính của lớp tổng quát Information mystring =
có thể sử dụng các kiểu được khai báo như mọi
new Information("hello"); lớp bình thường khác Information circle =
new Information(new Circle());
Information<2DShape> shape =
new Information<>(new 2DShape()); 11 12 11 12 3 Lớp tổng quát
Phương thức tổng quát
v Quy ước đặt tên kiểu
v 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ó Tên kiểu Mục đích
v Có thể được viết trong lớp bất kỳ (tổng quát hoặc E
Các thành phần trong một col ection không) K Kiểu khóa trong Map v Cú pháp V Kiểu giá trị trong Map
(chỉ định truy cập) T Các kiểu thông thường
(kiểu trả về) tên phương thức (danh S, U
Các kiểu thông thường khác sách tham số) {
v 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 } v Ví dụ Information integer =
public static void print(E[] a) { …
new Information(2012); // Error } Information integer =
new Information(2012); // OK 13 14 13 14
Ví dụ Phương thức tổng quát
Ví dụ Phương thức tổng quát
public class ArrayTool { ...
// Phương thức in các phần tử trong mảng String
String[] str = new String[5];
public static void print(String[] a) {
Point[] p = new Point[3];
for (String e : a) System.out.print(e + " ");
int[] intnum = new int[2]; System.out.println(); } ArrayTool.print(str);
// Phương thức in các phần tử trong mảng với kiểu ArrayTool.print(p);
// dữ liệu bất kỳ
public static void print(E[] a) {
// Không dùng được với kiểu dữ liệu nguyên thủy
for (E e : a) System.out.print(e + " ");
ArrayTool.print(intnum); System.out.println(); } } 15 16 15 16 4
Giới hạn kiểu dữ liệu tổng quát
Giới hạn kiểu dữ liệu tổng quát
v Có thể giới hạn các kiểu dữ liệu tổng quát sử dụng
Chấp nhận các kiểu là lớp con
phải là dẫn xuất của một hoặc nhiều lớp v Ví dụ: của 2DShape v Giới hạn 1 lớp
public class Information { private T value; v Giới hạn nhiều lớp
public Information(T value) { this.value = value; } public T getValue() { return value; } } Information pointInfo =
new Information(new Point()); // OK
Information stringInfo = new Information(); // error 17 18 17 18 Nội dung
3. Java Collections Framework
1. Giới thiệu về lập trình tổng quát
2. Định nghĩa và sử dụng Template
v Col ection là đối tượng có khả năng chứa các đối tượng khác.
3. Lập trình tổng quát trong Java col ecIons framework
v Các thao tác thông thường trên col ection
§ Thêm/Xoá đối tượng vào/khỏi col ection
4. Ký tự đại diện (Wildcard)
§ Kiểm tra một đối tượng có ở trong col ection không 5. Ví dụ và bài tập
§ Lấy một đối tượng từ col ection
§ Duyệt các đối tượng trong col ection § Xoá toàn bộ col ection 19 20 19 20 5
3. Java Collections Framework
3. Java Collections Framework
v Các col ection đầu tiên của Java:
v Một số lợi ích của Col ections Framework § Mảng
§ Giảm thời gian lập trình § Vector: Mảng động
§ Tăng cường hiệu năng chương trình § Hastable: Bảng băm
§ Dễ mở rộng các col ection mới
v Col ections Framework (từ Java 1.2)
§ Khuyến khích việc sử dụng lại mã chương trình
§ Là một kiến trúc hợp nhất để biểu diễn và thao tác trên các col ection.
§ Giúp cho việc xử lý các col ection độc lập với biểu diễn chi
tiết bên trong của chúng. 21 22 21 22
3. Java Collections Framework
Interfaces trong Java collections framework
v Col ections Framework bao gồm
v List: Tập các đối tượng tuần tự, kế tiếp nhau, có thể
§ Interfaces: Là các giao tiếp thể hiện tính chất của các kiểu lặp lại
col ection khác nhau như List, Set, Map.
v Set: Tập các đối tượng không lặp lại
§ Implementations: Là các lớp col ection có sẵn được cài đặt
v Map: Tập các cặp khóa-giá trị (key-value) và không cho các col ection interfaces. phép khóa lặp lại
§ Algorithms: Là các phương thức tĩnh để xử lý trên col ection,
ví dụ: sắp xếp danh sách, tìm phần tử lớn nhất... <> <> Col ection Map <> <> <> Set List SortedMap <> SortedSet 23 24 23 24 6
3. Java Collections Framework
So sánh Collection và Array << interface>> Collection Array Map << interface>> Col ec=on
Collection (có thể) truy xuất theo Mảng truy xuất 1 cách tuần tự HashMap dạng ngẫu nhiên << interface>> HashTable
Collection có thể chứa nhiều loại
Mảng chứa 1 loại đối tượng/dữ SortedMap
đối tượng/dữ liệu khác nhau liệu nhất định << interface>> << interface>> Set List TreeMap
Dùng Java Collection, chỉ cần
Dùng tổ chức dữ liệu theo mảng
khai báo và gọi những phương
phải lập trình hoàn toàn HashSet << interface>>
thức đã được định nghĩa sẵn ArrayList Vector LinkedList SortedSet
Duyệt các phần tử tập hợp thông
Duyệt các phần tử mảng tuần tự qua Iterator thông qua chỉ số mảng TreeSet 25 26 25 26
3. Java Collections Framework Ví dụ
v Các giao diện và lớp thực thi trong Collecqon framework public interface List {
của Java đều được xây dựng theo template void add(E x);
§ Cho phép xác định tập các phần tử cùng kiểu nào đó bất kỳ Iterator iterator();
§ Cho phép chỉ định kiểu dữ liệu của các Collec|on è hạn chế việc
thao tác sai kiểu dữ liệu }
List myList = new ArrayList(); myList.add("Fred"); // OK
myList.add(new Dog()); //Compile error!
String s = myList.get(0); 27 28 27 28 7 Giao diện Collection Giao diện Collection
v 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
public interface Collection { // Basic Operations § Thêm vào col ection int size(); boolean isEmpty(); § Xóa khỏi col ection
boolean contains(Object element);
boolean add(Object element);
§ Kiểm tra có là thành viên
boolean remove(Object element);
v Chứa các phương thức thao tác Iterator iterator();
trên các phần tử riêng lẻ hoặc theo // Bulk Operations khối
boolean addAll(Collection c);
boolean removeAll(Collection c);
v Cung cấp các phương thức cho
boolean retainAll(Collection c);
phép thực hiện duyệt qua các phần …. // Array Operations
tử trên col ection (lặp) và chuyển Object[] toArray(); tập hợp sang mảng
Object[] toArray(Object a[]); } 29 30 29 30 Giao diện Set v Các giao diện con kế thừa giao
v Set kế thừa từ Col ection nên cũng hỗ trợ toàn bộ các diện Collecqon
thao tác xử lý trên Col ection v Ví dụ: § Set of cars:
• {BMW, Ford, Jeep, Chevrolet, Nissan, Toyota, VW} § Nationalities in the class
• {Chinese, American, Canadian, Indian}
v Set là một tập hợp các phần tử không được trùng lặp.
v Set không có thêm phương thức riêng ngoài các
phương thức kế thừa từ Col ection. 31 32 31 32 8 Giao diện SortedSet Giao diện List
v SortedSet: kế thừa giao diện Set
v List kế thừa từ Col ection. List cung cấp thêm các
§ Các phần tử được sắp xếp theo một thứ tự
phương thức để xử lý Col ection kiểu danh sách
§ Không có các phần tử trùng nhau
§ Danh sách là một col ection với các phần tử được xếp theo
§ Cho phép một phần tử là nul chỉ số
§ 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
v Một số phương thức của List
Comparator trên kiểu của đối tượng đó § Object get(int index); v Một số phương thức:
§ Object set(int index, Object o);
§ first( ): lấy phần tử đầu tiên (nhỏ nhất)
§ void add(int index, Object o);
§ last( ): lấy phần tử cuối cùng (lớn nhất) § Object remove(int index);
§ SortedSet subSet(Object e1, Object e2): lấy một tập các phần tử § int indexOf(Object o);
nằm trong khoảng từ e1 tới e2 § int lastIndexOf(Object o); 33 33 34 Giao diện Map Giao diện Map v
v Xác định giao diện cơ bản để thao
Giao diện Map cung cấp các thao tác xử lý trên các
tác với một tập hợp bao gồm cặp bảng ánh xạ khóa-giá trị
§ Bảng ánh xạ lưu các phần tử theo khoá và không được có 2
§ Thêm một cặp khóa-giá trị khoá trùng nhau
§ Xóa một cặp khóa-giá trị
v Một số phương thức của Map
§ Lấy về giá trị với khóa đã có
§ Object put(Object key, Object value);
§ Kiểm tra có phải là thành viên (khóa hoặc giá trị) § Object get(Object key); § Object remove(Object key);
v Cung cấp 3 cách nhìn cho nội dung
§ boolean containsKey(Object key); của tập hợp:
§ boolean containsValue(Object value); § Tập các khóa § ... § Tập các giá trị
§ Tập các ánh xạ khóa-giá trị 35 35 36 9 Giao diện SortedMap
Các lớp thực thi giao diện Collection
v 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 v Giao diện SortedMap tương ứng § 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
v 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 37 37 38
Các lớp thực thi giao diện Collection
Các lớp thực thi giao diện Collection
v ArrayList: Mảng động, nếu các phần tử thêm vào vượt v HashSet: Bảng băm
quá kích cỡ mảng, mảng sẽ tự động tăng kích cỡ
§ Lưu các phần tử trong một bảng băm
v LinkedList: Danh sách liên kết
§ Không cho phép lưu trùng lặp
§ Hỗ trợ thao tác trên đầu và cuối danh sách § Cho phép phần tử null
§ Được sử dụng để tạo ngăn xếp, hàng đợi, cây… 39 40 39 40 10
Các lớp thực thi giao diện Collection
Các lớp thực thi giao diện Collection
v LinkedHashSet: Bảng băm kết hợp với linked list nhằm
v HashMap: Bảng băm (cài đặt của Map)
đảm bảo thứ tự các phần tử
v LinkedHashMap: Bảng băm kết hợp với linked list nhằm
§ Thừa kế HashSet và thực thi giao diện Set
đảm bảo thứ tự các phần tử (cài đặt của Map)
§ Khác HashSet ở chỗ nó lưu trữ trong một danh sách móc nối đôi
v TreeMap: Cây (cài đặt của Map)
§ Thứ tự các phần tử được sắp xếp theo thứ tự được insert vào v tập hợp Legacy Implementations
v TreeSet: Cho phép lấy các phần tử trong tập hợp theo thứ
§ Là các lớp cũ được cài đặt bổ sung thêm các col ection tự đã sắp xếp interface.
§ Vector: Có thể thay bằng ArrayList
§ Các phần tử được thêm vào TreeSet tự động được sắp xếp
§ Hastable: Có thể thay bằng HashMap
§ 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ơn 41 42 41 42 Ví dụ Ví dụ
String name = names.get(0);
ArrayList names = new ArrayList(); names.add(1, "Ann"); names.add("Emily"); names.remove(1); names.add("Bob"); names.add("Cindy"); 43 44 43 44 11 Bài tập 1
Giao diện Iterator và Comparator
v Sử dụng để duyệt và so sánh trên các Col ection
v Sau khi thực hiện đoạn chương trình sau, danh sách names
có chứa các phần tử nào? v Iterator
§ Các phần tử trong collection có thể được duyệt thông qua
ArrayList names = new ArrayList; Iterator names.add("Bob"); names.add(0, "Ann"); names.remove(1); names.add("Cal"); Col ection c; Iterator it = c.iterator(); ... 45 46 45 46
Giao diện Iterator và Comparator
Giao diện Iterator và Comparator v Iterator
v Iterator : Các phương thức
§ Cung cấp cơ chế thuận tiện
§ iterator( ): yêu cầu container trả về một iterator
để duyệt (lặp) qua toàn bộ
nội dung của tập hợp, mỗi
§ next( ): trả về phần tử tiếp theo
lần là một đối tượng trong
§ hasNext( ): kiểm tra có tồn tại phần tử tiếp theo hay không tập hợp
§ remove( ): xóa phần tử gần nhất của iterator • 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ở 47 48 47 48 12
Giao diện Iterator và Comparator
Giao diện Iterator và Comparator v Iterator: Ví dụ v § Định nghĩa iterator
Giao diện Comparator được sử dụng để cho phép so
sánh hai đối tượng trong tập hợp
public interface Iterator { boolean hasNext();
v Một Comparator phải định nghĩa một phương thức Object next(); void remove();
compare( ) lấy 2 tham số Object và trả về -1, 0 hoặc 1 }
Tương tự vòng lặp for § Sử dụng iterator
for (String name : names){
v Không cần thiết nếu tập hợp đã có khả năng so sánh tự Collection c;
System.out.println(name);
nhiên (vd. String, Integer…) } Iterator i = c.iterator(); while (i.hasNext()) { Object o = i.next(); // Process this object } 49 50 49 50
Giao diện Iterator và Comparator
Giao diện Iterator và Comparator v Ví dụ lớp Person:
v Ví dụ Cài đặt AgeComparator : class Person { private int age;
class AgeComparator implements Comparator { private String name;
public int compare(Object ob1, Object ob2) {
public void setAge(int age){
int ob1Age = ((Person)ob1).getAge(); this.age=age;
int ob2Age = ((Person)ob2).getAge(); } public int getAge(){ return this.age; if(ob1Age > ob2Age) }
public void setName(String name){ return 1; this.name=name;
else if(ob1Age < ob2Age) } return -1;
public String getName(){ return this.name; else } return 0; } } } 51 52 51 52 13
Giao diện Iterator và Comparator
Giao diện Iterator và Comparator
v Ví dụ Sử dụng AgeComparator :
v Ví dụ Sử dụng AgeComparator :
public class ComparatorExample {
System.out.println("Order before sorting");
public static void main(String args[]) {
for (Person person : lst) {
System.out.println(person.getName() + ArrayList lst = new
"\t" + person.getAge()); ArrayList(); }
Person p = new Person();
Collections.sort(lst, new AgeComparator());
p.setAge(35); p.setName("A");
System.out.println("\n\nOrder of person" + lst.add(p);
"after sorting by age"); p = new Person();
for (Iterator i = lst.iterator(); i.hasNext();) {
p.setAge(30); p.setName("B");
Person person = i.next(); lst.add(p);
System.out.println(person.getName() + "\t" + person.getAge()); } //End of for p = new Person(); } //End of main
p.setAge(32); p.setName("C"); } //End of class lst.add(p); 53 54 53 54 Nội dung
4. Ký tự đại diện (Wildcard)
1. Giới thiệu về lập trình tổng quát
v Quan hệ thừa kế giữa hai lớp không có ảnh
2. Định nghĩa và sử dụng Template
hưởng gì đến quan hệ giữa các cấu trúc tổng
quát dùng cho hai lớp đó.
3. Lập trình tổng quát trong Java col ections framework v Ví dụ:
4. Ký tự đại diện (Wildcard)
§ 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 5. Ví dụ và bài tập
ArrayList (sử dụng phương thức add)
§ Tuy nhiên, ArrayList, ArrayList lại không có quan hệ gì với ArrayList 55 56 55 56 14
4. Ký tự đại diện (Wildcard) Ví dụ
v Không thể ép kiểu ArrayList về kiểu ArrayList public class Test {
public static void main(String args[]) {
List lst0 = new LinkedList(); List lst1 = lst0; // Error printList(lst0); // Error class Parent { } }
class Child extends Parent { }
void static printList(List lst) {
ArrayList myList = new ArrayList(); Iterator it = lst.iterator(); while (it.hasNext()) System.out.println(it.next()); } } 57 58 57 58
4. Ký tự đại diện (Wildcard)
Ví dụ: Sử dụng Wildcards
v Giải pháp: sử dụng kí tự đại diện (wildcard)
v Ký tự đại diện: ? dùng để hiển thị cho một kiểu public class Test {
void printList(List<?> lst) { dữ liệu bất kỳ Iterator it = lst.iterator(); v Khi biên dịch, dấu while (it.hasNext())
? có thể được thay thế bởi bất
System.out.println(it.next()); kì kiểu dữ liệu nào. }
public static void main(String args[]) {
List lst0 = new LinkedList();
List lst1 = new LinkedList(); printList(lst0); // String printList(lst1); // Employee } } 59 60 59 60 15
4. Ký tự đại diện (Wildcard)
4. Ký tự đại diện (Wildcard)
v Lưu ý: cách làm sau là không hợp lệ
v "? extends Type": Xác định một tập các kiểu con
ArrayList<?> list = new
của Type. Đây là wildcard hữu ích ArrayList();
list.add("a1"); //compile error
list.add(new Object()); //compile error
v "? super Type": Xác định một tập các kiểu cha của Type
v Nguyên nhân: Vì không biết list là danh sách liên
kết cho kiểu dữ liệu nào, nên không thể thêm
v "?": Xác định tập tất cả các kiểu hoặc bất kỳ kiểu
phần tử vào list, kể cả đối tượng của lớp Object nào 61 62 61 62
4. Ký tự đại diện (Wildcard)
Khác biệt giữa print1 và print2? v Ví dụ:
public void print1(List list) {
§ ? extends Animal có nghĩa là kiểu gì đó thuộc loại Animal (là
for (Employee e : list) {
Animal hoặc con của Animal) System.out.println(e);
v Lưu ý: Hai cú pháp sau là tương đương: } }
public void foo( ArrayList<? extends Animal> a)
public void foo( ArrayList a)
public void print2(List<? extends Employee> list) {
for (Employee e : list) { System.out.println(e); } } 63 64 63 64 16 Nội dung Bài tập 2
1. Giới thiệu về lập trình tổng quát
v Trừu tượng hoá mô tả sau: một quyển sách là
2. Định nghĩa và sử dụng Template
tập hợp các chương, chương là tập hợp các trang.
3. Lập trình tổng quát trong Java col ections framework
§ 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, sử dụng
4. Ký tự đại diện (Wildcard) Collection
5. Ví dụ và bài tậ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 65 66 65 66 Bài tập 3
v 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 67 68 67 68 17