Bài giảng Lập trình hướng đối tượng: Chương 7 - ĐH Bách Khoa Hà Nội

Chia sẻ: Elysale Elysale | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

14
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lập trình hướng đối tượng: Chương 7 Đa hình (Polymophism) cung cấp cho người học những kiến thức như: Upcasting và Downcasting; Liên kết tĩnh và Liên kết động; Đa hình (Polymophism); Lập trình tổng quát (generic prog.). Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lập trình hướng đối tượng: Chương 7 - ĐH Bách Khoa Hà Nội

9/18/17 Nội dung Bộ môn Công nghệ Phần mềm 1. Upcasting và Downcasting Viện CNTT & TT 2. Liên kết tĩnh và Liên kết động Trường Đại học Bách Khoa Hà Nội 3. Đa hình (Polymophism) 4. Lập trình tổng quát (generic prog.) LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG Bài 07. Đa hình (Polymophism) 2 Nội dung 1.1. Upcasting 1. Upcasting và Downcasting n Moving up the inheritance hierarchy 2. Liên kết tĩnh và Liên kết động n Up casting là khả năng nhìn nhận đối tượng thuộc lớp dẫn xuất như là một đối tượng 3. Đa hình (Polymophism) thuộc lớp cơ sở. 4. Lập trình tổng quát (generic prog.) n Tự động chuyển đổi kiểu 3 4 1
9/18/17 Ví dụ Ví dụ (2) class Manager extends Employee { Employee assistant; // ... public void setAssistant(Employee e) { assistant = e; } public class Test1 { // ... public static void main(String arg[]){ } Person p; public class Test2 { Employee e = new Employee(); public static void main(String arg[]){ Manager junior, senior; p = e; // ... p.setName(“Hoa”); senior.setAssistant(junior); p.setSalary(350000); // compile error } } } 5 6 Ví dụ (3) 1.2. Downcasting public class Test3 { String static teamInfo(Person p1, Person p2){ n Move back down the inheritance hierarchy return "Leader: " + p1.getName() + ", member: " + p2.getName(); n Down casting là khả năng nhìn nhận một đối } tượng thuộc lớp cơ sở như một đối tượng public static void main(String arg[]){ thuộc lớp dẫn xuất. Employee e1, e2; Manager m1, m2; n Không tự động chuyển đổi kiểu // ... à Phải ép kiểu. System.out.println(teamInfo(e1, e2)); System.out.println(teamInfo(m1, m2)); System.out.println(teamInfo(m1, e2)); } } 7 8 2
9/18/17 Ví dụ Nội dung public class Test2 { public static void main(String arg[]){ 1. Upcasting và Downcasting Employee e = new Employee(); Person p = e; // up casting 2. Liên kết tĩnh và Liên kết động Employee ee = (Employee) p; // down casting 3. Đa hình (Polymophism) Manager m = (Manager) ee; // run-time error 4. Lập trình tổng quát (generic prog.) Person p2 = new Manager(); Employee e2 = (Employee) p2; Person p3 = new Employee(); Manager e3 = (Manager) p3; } 9 10 } 2.1. Liên kết tĩnh (Static Binding) Ví dụ public class Test { n Liên kết tại thời điểm biên dịch public static void main(String arg[]){ n Early Binding/Compile-time Binding Person p = new Person(); n Lời gọi phương thức được quyết định khi biên p.setName(“Hoa”); p.setSalary(350000); //compile-time error dịch, do đó chỉ có một phiên bản của phương } thức được thực hiện } n Nếu có lỗi thì sẽ có lỗi biên dịch n Ưu điểm về tốc độ 11 12 3
9/18/17 2.2. Liên kết động (Dynamic binding) Ví dụ public class Test { n Lời gọi phương thức được quyết định khi public static void main(String arg[]){ thực hiện (run-time) Person p = new Person(); // ... n Late binding/Run-time binding Employee e = new Employee(); // ... n Phiên bản của phương thức phù hợp với đối Manager m = new Manager(); tượng được gọi. // ... Person pArr[] = {p, e, m}; n Java mặc định sử dụng liên kết động for (int i=0; i< pArr.length; i++){ System.out.println( pArr[i].getDetail()); } } } 13 14 Nội dung 3. Đa hình (Polymophism) 1. Upcasting và Downcasting n Ví dụ: Nếu đi du lịch, bạn có thể chọn ô tô, thuyền, hoặc máy bay 2. Liên kết tĩnh và Liên kết động n Dù đi bằng phương tiện gì, kết quả cũng giống nhau là bạn đến được nói cần đến 3. Đa hình (Polymophism) n Cách thức đáp ứng các dịch vụ có thể khác nhau 4. Lập trình tổng quát (generic prog.) 15 16 4
9/18/17 3. Đa hình (2) 3. Đa hình (3) n Các lớp khác nhau có thể đáp ứng danh sách các thông điệp n Polymorphism: Nhiều hình thức thực hiện, giống nhau, vì vậy cung cấp các dịch vụ giống nhau nhiều kiểu tồn tại n Cách thức đáp ứng thông điệp, thực hiện n Đa hình trong lập trình dịch vụ khác nhau n Đa hình phương thức: n Chúng có thể tráo đổi n Phương thức trùng tên, phân biệt bởi danh sách tham cho nhau mà không số. ảnh hưởng đến đối tượng gửi thông điệp n Đa hình đối tượng n à Đa hình n Nhìn nhận đối tượng theo nhiều kiểu khác nhau n Các đối tượng khác nhau cùng đáp ứng chung danh sách các thông điệp có giải nghĩa thông điệp theo cách thức khác nhau. 17 18 3. Đa hình (4) 3. Đa hình (5) n Nhìn nhận đối tượng theo nhiều n Các đối tượng khác nhau giải nghĩa các kiểu khác nhau à Upcasting và thông điệp theo các cách thức khác nhau à Downcasting Liên kết động public class Test3 { n Ví dụ: public static void main(String args[]){ Person p1 = new Person(); Person p1 = new Employee(); Person p2 = new Employee(); Person p2 = new Manager(); Person p3 = new Manager(); // ... Employee e = (Employee) p1; System.out.println(p1.getDetail()); Manager m = (Manager) p2; } System.out.println(p2.getDetail()); } System.out.println(p3.getDetail()); 19 20 5
9/18/17 Ví dụ khác Toán tử instanceof class EmployeeList { public class Employee extends Person {} Employee list[]; public class Student extends Person {} ... public void add(Employee e) {...} public void print() { public class Test{ for (int i=0; i
9/18/17 Nội dung 4. Lập trình tổng quát 1. Upcasting và Downcasting n 4.1. Giới thiệu 2. Liên kết tĩnh và Liên kết động n 4.2. Java generic data structure n 4.2.1. Data structure 3. Đa hình (Polymophism) n 4.2.2. Java collection framework 4. Lập trình tổng quát (generic n 4.2.3. Các interface trong Java collection framework prog.) 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) 25 26 4. Lập trình tổng quát 4. 1. Giới thiệu về lập trình tổng quát n 4.1. Giới thiệu n Tổng quát hóa chương trình để có thể hoạt n 4.2. Java generic data structure động với các kiểu dữ liệu khác nhau, kể cả n 4.2.1. Data structure kiểu dữ liệu trong tương lai n 4.2.2. Java collection framework n thuật toán đã xác định n 4.2.3. Các interface trong Java collection framework n Ví dụ: n 4.2.4. Các cài đặt cho các interface – implementation n C: dùng con trỏ void n 4.3. Định nghĩa và sử dụng Template n C++: dùng template n Java: lợi dụng upcasting n 4.4. Ký tự đại diện (Wildcard) n Java 1.5: template 27 28 7
9/18/17 Ví dụ: C dùng con trỏ void Ví dụ: C++ dùng template template n Hàm memcpy: void sort(ItemType A[], int count Khi sử dụng,có thể thay thế ) { ItemType bằng int, string,… hoặc void* memcpy(void* region1, // Sort count items in the array, bất A, intođối kỳ một increasing order tượng của một lớp // The algorithm that is used here is nào selection đó sort const void* region2, size_t n){ for (int i = count-1; i > 0; i--) { const char* first = (const char*)region2; int index_of_max = 0; const char* last = ((const char*)region2) + n; for (int j = 1; j A[index_of_max]) index_of_max = j; char* result = (char*)region1; if (index_of_max != i) { while (first != last) ItemType temp = A[i]; *result++ = *first++; A[i] = A[index_of_max]; A[index_of_max ] = temp; return result; } } } } 29 30 Ví dụ: Java dùng upcasting và Object Nhắc lại – equals của lớp tự viết class MyStack { class MyValue { ... int i; public void push(Object obj) {...} } public Object pop() {...} public class EqualsMethod2 { } public static void main(String[] args) { MyValue v1 = new MyValue(); public class TestStack{ MyValue 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 4.1. Giới thiệu n Collection là đối tượng có khả năng chứa các đối tượng khác. n 4.2. Java generic data structure n 4.2.1. Data structure n Các thao tác thông thường trên collection n 4.2.2. Java collection framework n 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 n 4.2.4. Các cài đặt cho các interface – implementation không n 4.3. Định nghĩa và sử dụng Template n Lấy một đối tượng từ collection n 4.4. Ký tự đại diện (Wildcard) n Duyệt các đối tượng trong collection 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ữ HashSet liệu cụ thể. Ví dụ: mảng động, danh sách liên kết, cây đỏ đ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
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