ữ ệ
ấ
ả
C u trúc d li u và gi
ậ i thu t
ÔN TẬP KIẾN THỨC
ả
Gi ng viên: ThS. Đậu Ngọc Hà Dương – ĐH KHTN HCM
Nội dung ôn tập
2
ậ
1. Đánh giá thu t toán
2. DSLK – Stack Queue
ế
ấ
ị 3. C u trúc cây: cây nh phân tìm ki m, cây AVL
ế
ắ
ậ
4. Các thu t toán s p x p
ế ượ
ế
5. Các chi n l
c tìm ki m
ố
ỗ 6. Đ i sánh chu i
ữ ệ
7. Nén d li u
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Nội dung môn học
3
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Nội dung môn học
4
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Nội dung môn học
5
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Nội dung môn học
6
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Ngôn ngữ lập trình
7
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Ngôn ngữ lập trình
8
George Boole
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Ngôn ngữ lập trình
9 Alan Turing
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Ngôn ngữ lập trình
10
Von Neumann
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Thế nào là thuật toán?
An algorithm is a sequence of steps required to
11
accomplish a task (AlKhwārizmī).
ậ
ữ
ạ
Thu t toán là t p h p h u h n các l nh chính
ể ự
ậ ệ
ặ
ộ i m t bài
ệ ợ ể ả xác đ th c hi n tính toán ho c đ gi toán (Rosen)
AlKhwārizmī
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Thuật toán – Các giai đoạn thực hiện
12
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Thuật toán – Phương pháp biểu diễn
13
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Ví dụ về lưu đồ
14 Bắt đầu
Nhập vào 2 số nguyên
Tính tổng 2 số
Hiển thị kết quả
Kết thúc
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Ví dụ về bảng quyết định
15
Luật
Máy in không in C C C C K K K K
Đèn lỗi báo sáng C C K K C C K K Điều kiện
Máy in không được nhận biết C K C K C K C K
Kiểm tra cáp nguồn X
X X
Kiểm tra cáp nối máy tinh – máy in
Kiểm tra driver X X X X Hành động
Kiểm tra/thay mực X X X X
Kiểm tra khe để giấy X X
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Thế nào là cấu trúc dữ liệu?
ứ
ộ
ổ
ch c các d li u thành
C u trúc d li u
16
ấ ộ ơ
ữ ệ ầ
ầ
ị
ữ ệ
ữ
ố
ơ ả
ữ ệ là m t cách t ồ m t đ n v hoàn ch nh bao g m các thành ph n (ph n ầ ử t ) là các d li u c b n, các m i liên k t gi a các ph n ử ấ t
ỉ ế ơ ả y và các thao tác c b n trên chúng.
ượ
ọ
Các thao tác này th
c g i là các
ườ
phép toán trên ơ ả ng
ữ ệ ạ ậ (create), h yủ (dipose), thêm (add), chèn t o l p
ườ ng đ ị ấ c u trúc d li u xác đ nh. Các phép toán c b n th ặ g p là (insert), xóa (delete), tìm ki m ế (search),...
ươ
, khi thi
ầ ị
Tùy theo yêu c u c a ườ
ế ế t k ch ấ
ơ ả
ấ
(array), danh sách (list), ngăn x p ế (stack),
ậ ấ ả i thu t HCMUS
ậ ủ thu t toán ng ữ ử ụ i ta đ nh nghĩa và s d ng các c u trúc d trình ng ữ ệ ệ li u khác nhau. Các c u trúc d li u c b n hay dùng là: m ng ả ữ ệ C u trúc d li u và gi hàng đ i ợ (queue), cây(tree),...
[Wikipedia, tháng 6 2009]
Tóm tắt
17
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
Mở rộng
18
Programming is for programmers
[C++ in Action]
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
19
Hỏi và Đáp
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS
