Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Trừu tượng hóa dữ liệu

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Trừu tượng hóa dữ liệu

1. Bài 3: Trừu tượng hóa dữ liệu Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
2. Nội dung chính  Biểu diễn dữ liệu trong các ngôn ngữ lập trình  Sự trừu tượng hóa dữ liệu  Kiểu dữ liệu trừu tượng  Đặc tả  Cài đặt 2 diepht@vnu
3. Biểu diễn như thế nào?  Tuổi của một người.  Điểm của một môn học tín chỉ.  Một phân số. Một dãy phân số.  Một điểm ảnh (pixel) của ảnh RGB biết cường độ mỗi màu nằm trong [0; 255]. Một ảnh RGB.  Một điểm, một đoạn thẳng, một tam giác trong hệ tọa độ 2 chiều.  Một đa thức bậc n.  Giá trị của n! với n nhỏ. Giá trị của n! với n lớn. 3 diepht@vnu
4. Dữ liệu  Dữ liệu là những thông tin mà máy tính có thể xử lý: số nguyên, số thực, xâu kí tự, và các dữ liệu phức tạp được tạo từ nhiều thành phần  Trong bộ nhớ máy tính, dữ liệu được biểu diễn dưới dạng nhị phân (dãy 0, 1)  Trong các ngôn ngữ lập trình bậc cao (C++, Java ), dữ liệu được biểu diễn dưới dạng trừu tượng, xuất phát từ biểu diễn toán học và dễ hiểu cho con người:  int age  double weight 4 diepht@vnu
5. Kiểu dữ liệu cơ bản Kiểu dữ liệu được xác định bởi: 1. Phạm vi giá trị 2. Các phép toán Ví dụ trong C++ kiểu phạm vi phép toán thường dùng bool true/false &&, ||, ! char -128 -> 127 >, 32,767 >, , , <, ==, +, -, *, / 5 diepht@vnu
6. Kiểu dữ liệu có cấu trúc Ngôn ngữ lâp trình cung cấp cho ta những luật để xây dựng kiểu dữ liệu mới T từ những kiểu dữ liệu đã biết t1, t2, ,tn. Ví dụ trong C++: struct T { t1 x1 ; t2 x2 ; tn xn ; }; 6 diepht@vnu
7. Kiểu dữ liệu có cấu trúc • Xây dựng cấu trúc dữ liệu để biểu diễn dữ liệu của 1 điểm trên mặt phẳng struct Point { double x; double y; }; • Xây dựng cấu trúc dữ liệu để biểu diễn dữ liệu của 1 đoạn thẳng trên mặt phẳng struct Line { Point start; Point end; }; 7 diepht@vnu
8. Phạm vi và các phép toán trên kiểu dữ liệu có cấu trúc Xét kiểu dữ liệu mới T được tạo từ những kiểu dữ liệu đã biết t1, t2, ,tn, Ví dụ: struct Complex{ double real; double image; }; Phạm vi: Xác định bởi phạm vi của các kiểu dữ liệu thành phần  real: là số thực nằm trong phạm vi kiểu ‘double’  image: là số thực nằm trong phạm vi kiểu ‘double’ 8 diepht@vnu
9. Phạm vi và các phép toán trên kiểu dữ liệu có cấu trúc Phép toán: Do người dùng định nghĩa Ví dụ: struct Complex{ double real; double image; }; Complex createComplex (double real, double image) { Complex c; c.real = real; c.image = image; return c; } 9 diepht@vnu
10. Phạm vi và các phép toán trên kiểu dữ liệu có cấu trúc Complex add (Complex c1, Complex c2) { Complex c12; c12.real = c1.real + c2.real; c12.image = c1.image + c2.image; return c12; } Complex multiply (Complex c1, Complex c2) { Complex c12; c12.real = (c1.real * c2.real) – (c1.image * c2.image); c12.image = (c1.real * c2.image) + (c1.image * c2.real); return c12; } 10 diepht@vnu
11. Trừu tượng hóa dữ liệu (abstraction) 1. Đặc tả đối tượng dữ liệu (các thành phần dữ liệu của đối tượng) Ví dụ: đối tượng số phức (Complex) – real – image 2. Đặc tả các phép toán trên đối tượng dữ liệu (operations) Ví dụ: đối tượng số phức (Complex) – createComplex (real, image) – getReal (complexNumber) – getImage (complexNumber) – add (complexNumber1, complexNumber2) – multiply (complexNumber2, complexNumber2) – print (complexNumber) 11 diepht@vnu
12. Trừu tượng hóa dữ liệu Trừu tượng hóa đối tượng sinh viên (Student) 1. Đặc tả đối tượng dữ liệu name, age, sex, address 2. Đặc tả các phép toán trên đối tượng dữ liệu createStudent (name, age, sex, address) compare (student1, student2) getName (student) getAge (student) getSex (student) getAdd (student) 12 diepht@vnu
13. Trừu tượng hóa dữ liệu Trừu tượng hóa đối tượng lớp học (StudentClass) 1. Đặc tả đối tượng dữ liệu className, numberStudent, studentArr, address 2. Đặc tả các phép toán trên đối tượng dữ liệu addStudent (studentClass, student) findStudent (studentClass, student) deleteStudent (studentClass, student) getClassName (studentClass) getNumberStudent (studentClass) getStudentArr (studentClass) getClassAddress (studentClass) 13 diepht@vnu
14. Giải một bài toán tin học  Đặc tả vấn đề  Thiết kế cấu trúc dữ liệu  Thiết kế giải thuật  Cài đặt (C++, Java )  Thử nghiệm và sửa lỗi  Tối ưu chương trình 14 diepht@vnu
15. Ví dụ  Bài toán: Giả sử chúng ta cần viết chương trình lập lịch thi. Vấn đề như sau. Mỗi người dự thi đăng kí thi một số môn trong số các môn tổ chức thi. Chúng ta cần xếp lịch thi, mỗi ngày thi một số môn trong cùng một thời gian, sao cho mỗi người dự thi có thể thi tất cả các môn họ đã đăng kí.  Đặc tả bằng danh sách?  Đặc tả bằng đồ thị? 15 diepht@vnu
16. Ví dụ: Đặc tả bằng danh sách  Input:  1 danh sách người dự thi  mỗi người dự thi biểu diễn bằng 1 danh sách môn thi người đó đăng kí  Output:  1 danh sách ngày thi  mỗi ngày thi là 1 danh sách các môn thi  không có môn thi nào xuất hiện trong 2 ngày  không có 2 môn thi nào trong 1 ngày cùng xuất hiện trong danh sách của 1 người dự thi nào đó 16 diepht@vnu
17. Ví dụ: Đặc tả bằng đồ thị  Input:  1 đồ thị  đỉnh biểu diễn môn thi  giữa 2 môn thi có cạnh nối nếu chúng được đăng kí bởi cùng 1 người dự thi nào đó  Output:  1 danh sách ngày thi  mỗi ngày thi là 1 danh sách các đỉnh không kề nhau 17 diepht@vnu
18. Ví dụ: Đặc tả bằng đồ thị  Ví dụ: S1 = (A, B, C) S2 = (A, C, D) S3 = (C, E, F) S4 = (A, C) S5 = (C, B, E) S6 = (C, F)  Thuật toán  i = 0, Li=() // ds môn thi ngày đầu  Lặp:  Chọn đỉnh bất kì chưa đánh dấu, đưa vào Li  Đánh dấu nó và các đỉnh kề nó  Nếu tất cả đều đã đánh dấu:  Loại các đỉnh trong Li khỏi đồ thị. o Nếu đồ thị rỗng: Kết thúc! o Ngược lại: i++, Li=(), xóa đánh dấu // Xây dựng ds cho ngày tiếp  Kết quả: 18 diepht@vnu
19. Lập trình hướng đối tượng Object oriented programming (OOP)  Lâp trình hướng đối tượng giúp chúng ta cài đặt các mô tả trừu tượng (đối tượng dữ liệu và các phép toán) thành các đoạn mã chương trình  Chương trình được thiết kế thành từng đoạn nhỏ, mỗi đoạn mô tả về một đối tượng (thuộc tính dữ liệu, các phép toán trên dữ liệu)  Hai thuộc tính quan trọng: đóng gói (encapsulation) và thừa kế (inheritance) 19 diepht@vnu
20. OOP: Tính đóng gói (encapsulation) Class: Cài đặt một lớp đối tượng dữ liệu trừu tượng. Việc cài đặt bao gồm cài đặt các thành phần dữ liệu và các phép toán trên dữ liệu Ví dụ: class Complex { double real; double image; • Liên kết chặt chẽ giữa dữ public: liệu và phép toán void create (double r, double i) { • Che giấu dữ liệu real = r; image = i; • Dễ dàng tìm lỗi } • Các đối tượng liên kết với double getReal () { nhau thông qua các phép toán return real; } void print { cout << real << “ +i ” << image << “ \ n” ; } 20 }; diepht@vnu
21. OOP: Tính đóng gói (encapsulation) Object: Biểu diễn cho một đối tượng cụ thể của một lớp Complex c1; Complex c2; 21 diepht@vnu
22. C++  Lập trình tổng quát (Generic programming)  Con trỏ và cấp phát động  Lớp 22 diepht@vnu