1
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1
Trình bày khái niệm tổng
quát về kiểu dữ liệu
Cài đặt các kiểu dữ liệu
theo hướng cấu trúc
Cài đặt các kiểu dữ liệu
theo hướng đối tượng bằng
C++
Kiểu dữ liệu trừu tượng – (ADT)
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2
Nội dung trình bày
Kiểu dữ liệu trừu tượng (ADT)
So sánh một số cài đặt kiểu dữ liệu theo
hướng cấu trúc và cài đặt kiểu dữ liệu theo
hướng đối tượng bằng C++
Áp dụng Template và việc xây dựng các
kiểu dữ liệu tổng quát
2
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3
Kiểu dữ liệu trừu tượng (ADT)
ADT - Abstract Data Type
Kiểu dữ liệu trừu tượng: T = <V, O>
V (Values - miền giá trị): tập hợp các giá trị
mà kiểu T có thể nhận
O (Operators – các thao tác): tập hợp các thao
tác cơ bản được định nghĩa trên V
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 4
Kiểu dữ liệu trừu tượng (ADT)
Ví dụ:
T = int:
V = {-32768 .. +32767}
O = {+, -, *, div, mod, >, >=, <, <=, ==, !=,…}
Có nhiều cách để xây dựng các kiểu dữ
liệu, và không có 1 qui định cụ thể về việc
cần phải xây dựng các thao tác như thế nào
3
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5
Kiểu dữ liệu trừu tượng (ADT)
Cài đặt kiểu dữ liệu theo hướng cấu trúc (struct):
Áp dụng khi chưa có công cụ lập trình hướng đối
tượng
Xây dựng các thao tác dưới dạng những thủ tục/hàm
Các thao tác và dữ liệu (V, O) tách rời nhau
Dữ liệu không được “bảo vệ”, vì ta có thể truy xuất
đến ở bất cứ đâu trong phạm vi mà dữ liệu đã được
định nghĩa
…
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 6
Kiểu dữ liệu trừu tượng (ADT)
Cài đặt kiểu dữ liệu theo hướng đối tượng:
Dữ liệu và thao tác được tích hợp lại
Dữ liệu được “ẩn” (hiding) và bảo vệ, tránh
những truy xuất trực tiếp
Chương trình chỉ truy xuất đến dữ liệu thông
qua các thao tác đã được định nghĩa
…
4
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 7
Kiểu dữ liệu trừu tượng (ADT)
Ưu điểm của cài đặt kiểu dữ liệu bằng hướng đối tượng
Chương
trình
Dữ liệu và
các thao tác
Yêu cầu truy
xuất dữ liệu
Kết quả thực
hiện
Bảo vệ
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 8
Kiểu dữ liệu trừu tượng (ADT)
Truy xuất “tự do” đến dữ liệu
Program Data
Add
Remove
Find
Display
Program
Yêu cầu
Kết quả
Dữ liệu được “bảo vệ”
Data
Add
Remove
Find
Display
5
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 9
Kiểu dữ liệu trừu tượng (ADT)
Cài đặt kiểu dữ liệu theo hướng đối
tượng…: (tt)
Có thể “che dấu” những thao tác xử lý cục
bộ, giúp đơn giản hoá việc sử dụng bằng cách
chỉ cung cấp cho người dùng những thao tác
thực sự cần thiết
Nâng cao tính “module hoá” của chương trình
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 10
Kiểu dữ liệu trừu tượng (ADT)
Che dấu các thao tác xử lý cục bộ