Cấu trúc dữ liệu và giải thuật - Ôn thi tốt nghiệp

Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học Ô Ố ỆN THI T T NGHI P ấC u trúc dữ liệu Trần Ngọc Bảo Email: tnbao.dhsp@gmail.com Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học CẤU TRÚC DỮ LIỆU • Cấu trúc dữ liệu mảng • Danh sách liên kết • Cấu trúc dữ liệu cây Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học CẤU TRÚC DỮ LIỆU • Cấu trúc dữ liệu mảng • Danh sách liên kết • Cấu trúc dữ liệu cây Cấu trúc mảng một chiều • Các giải thuật tìm kiếm H I Ệ P H I Ệ P U U – Tìm kiếm tuần tự (Sequence Search) – Tìm kiếm nhị phân (Binary Search) T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U • Các giải thuật sắp xếp – Sắp xếp đổi chỗ trực tiếp Ô N T H I Ô N T H I T R Ú C D T R Ú C D – Sắp xếp chọn trực tiếp – Sắp xếp chèn trực tiếp ắ I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T – S p xếp nổi bọt – Sắp xếp nổi bọt cải tiến Shell sort B À B À – – Heap sort – Quick sort TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (4)4 – Merge sort Cấu trúc mảng một chiều Yê ầ H I Ệ P H I Ệ P U U • u c u –Trình bày ý tưởng giải thuật T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U –Cho ví dụ minh họa –Biểu diễn giải thuật Ô N T H I Ô N T H I T R Ú C D T R Ú C D • Biểu diễn giải thuật bằng mã giả • Biểu diễn giải thuật bằng sơ đồ khối I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T –Cài đặt bằng ngôn ngữ C/C++ Cho biết kết quả thực hiện chạy B À B À – từng bước giải thuật TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (5)5 Giải thuật tìm kiếm tuần tự Bài t á H I Ệ P H I Ệ P U U • o n –Cho mảng a có n số nguyên (n ≤ T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U 100) –Yêu cầu: cho biết số nguyên x có Ô N T H I Ô N T H I T R Ú C D T R Ú C D tồn tại trong mảng a không ? •Nếu có cho biết vị trí đầu tiên x xuất I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T hiện trong mảng •Ngược lại thông báo x không tồn tại B À B À trong mảng. TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (6)6 Giải thuật tìm kiếm tuần tự Ví d H I Ệ P H I Ệ P U U • ụ – Cho mảng a có 6 phần tử (n = 6) như T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U sau: 1 5 4 2 3 7 Yê ầ Ô N T H I Ô N T H I T R Ú C D T R Ú C D – u c u: • Tìm x = 3 ? Tìm x 10 ? I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T • = – Kết quả: • X = 3 xuất hiện ở vị trí thứ 5 trong mảng B À B À • X = 10 không tồn tại trong mảng TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (7)7 Giải thuật tìm kiếm tuần tự Ý tưở iải th ật H I Ệ P H I Ệ P U U • ng g u – Cho mảng a có 6 phần tử (n = 6) như T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U sau: 1 5 4 2 3 7 Ô N T H I Ô N T H I T R Ú C D T R Ú C D I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T B À B À 3X = TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (8)8 X = 3 xuất hiện ở vị trí thứ 5 trong mảng Giải thuật tìm kiếm tuần tự Ý tưở iải th ật H I Ệ P H I Ệ P U U • ng g u – Cho mảng a có 6 phần tử (n = 6) như T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U sau: 1 5 4 2 3 7 Ô N T H I Ô N T H I T R Ú C D T R Ú C D I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T B À B À 10X = TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (9)9 X = 10 không tồn tại trong mảng Giải thuật tìm kiếm tuần tự Ví dụ H I Ệ P H I Ệ P U U • – Cho mảng a có 6 phần tử (n = 6) như sau: 1 5 4 2 3 7 T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U – Yêu cầu: • Tìm x = 3 ? Ô N T H I Ô N T H I T R Ú C D T R Ú C D – Kết quả: Lần lặp i a[i] = x ? Kết quả I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T 1 0 a[0]=1 ≠ x=3 i=i+1 =1 2 1 a[1]=5 ≠ x=3 i=i+1 =2 3 2 a[2]=4 ≠ x=3 i=i+1 =3 B À B À 4 3 a[3]=2 ≠ x=3 i=i+1 =4 5 4 a[0]=3 = x=3 Kết thúc gt TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (10) X = 3 xuất hiện ở vị trí thứ 5 trong mảng Giải thuật tìm kiếm tuần tự H I Ệ P H I Ệ P U U T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U Ô N T H I Ô N T H I T R Ú C D T R Ú C D I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T B À B À TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (11) Giải thuật tìm kiếm nhị phân Bài t á H I Ệ P H I Ệ P U U • o n –Cho mảng a có n số nguyên (n ≤ T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U 100) –Yêu cầu: cho biết số nguyên x có Ô N T H I Ô N T H I T R Ú C D T R Ú C D tồn tại trong mảng a không ? •Nếu có cho biết vị trí đầu tiên x xuất I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T hiện trong mảng •Ngược lại thông báo x không tồn tại B À B À trong mảng. –Điều kiện: TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (12)12 Mảng a đã được sắp thứ tự tăng Giải thuật tìm kiếm tuần tự Ví d H I Ệ P H I Ệ P U U • ụ – Cho mảng a có 6 phần tử (n = 6) như T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U sau: 1 2 3 4 5 7 Yê ầ Ô N T H I Ô N T H I T R Ú C D T R Ú C D – u c u: • Tìm x = 3 ? Kết ả I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T – qu : • X = 3 xuất hiện ở vị trí thứ 5 trong mảng B À B À TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (13)13 Giải thuật tìm kiếm nhị phân Ví dụ H I Ệ P H I Ệ P U U • – Cho mảng a có 6 phần tử (n = 6) như sau: 1 2 3 4 5 7 T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U – Yêu cầu: • Tìm x = 4 ? Ô N T H I Ô N T H I T R Ú C D T R Ú C D – Kết quả: Lần lặp l r m=[(l+r)/2] a[m] = x ? Kết quả I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T 1 0 5 [(0+5)/2]=2 a[2]=3 < x=4 l=m+1 =3 2 3 5 [(3+5)/2]=4 a[4]=5 > x=4 r=m-1 =3 3 3 3 [(3+3)/2]=3 a[3]=4 = x=4 Kết thúc gt B À B À TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (14) X = 4 xuất hiện ở vị trí thứ 4 trong mảng Giải thuật tìm kiếm nhị phân H I Ệ P H I Ệ P U U T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U Ô N T H I Ô N T H I T R Ú C D T R Ú C D I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T B À B À TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (15) Cấu trúc mảng một chiều • Các giải thuật tìm kiếm H I Ệ P H I Ệ P U U – Tìm kiếm tuần tự (Sequence Search) – Tìm kiếm nhị phân (Binary Search) T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U • Các giải thuật sắp xếp – Sắp xếp đổi chỗ trực tiếp Ô N T H I Ô N T H I T R Ú C D T R Ú C D – Sắp xếp chọn trực tiếp – Sắp xếp chèn trực tiếp ắ I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T – S p xếp nổi bọt – Sắp xếp nổi bọt cải tiến Shell sort B À B À – – Heap sort – Quick sort TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (16)16 – Merge sort Các giải thuật sắp xếp trên mảng 1 chiều Yê ầ H I Ệ P H I Ệ P U U • u c u –Trình bày ý tưởng giải thuật T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U –Cho ví dụ minh họa –Biểu diễn giải thuật Ô N T H I Ô N T H I T R Ú C D T R Ú C D • Biểu diễn giải thuật bằng mã giả • Biểu diễn giải thuật bằng sơ đồ khối I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T –Cài đặt bằng ngôn ngữ C/C++ Cho biết kết quả thực hiện chạy B À B À – từng bước giải thuật TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (17)17 Demo Struct và sắp xếp mảng struct • Struct H I Ệ P H I Ệ P U U – Cho thông tin học sinh, sinh viên,là 1 struct có nhiều thông tin T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U • Sắp xếp danh sách (mảng struct) – Chọn 1 trong các giải thuật sắp xếp trên mảng Ô N T H I Ô N T H I T R Ú C D T R Ú C D 1 chiều để sắp xếp các phần tử trong danh sách theo một hoặc nhiều tiêu chí (điều kiện) • Sắp xếp danh sách sinh viên theo họ tên I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T • Sắp xếp danh sách sinh viên giảm dần theo điểm tốt nghiệp • Sắp xếp danh sách sinh viên theo họ tên, điểm thi tốt B À B À nghiệp TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (18) Ví dụ Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học CẤU TRÚC DỮ LIỆU • Cấu trúc dữ liệu mảng • Danh sách liên kết • Cấu trúc dữ liệu cây Danh sách liên kết • Cấu trúc tự trỏ H I Ệ P H I Ệ P U U – Thành phần dữ liệu: data – Thành phần con trỏ: Next, Previous Cá l i d h á h liê kế T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U • c oạ an s c n t – Danh sách liên kết đơn – Danh sách liên kết đôi Ô N T H I Ô N T H I T R Ú C D T R Ú C D – Danh sách vòng – Danh sách đa liên kết – Stack/Queue I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T • Các thao tác trên sách liên kết – Thêm phần tử Xóa phần tử B À B À – – Tìm phần tử trong danh sách – Sắp xếp các phần tử trong danh sách TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (20) Demo Danh sách liên kết H I Ệ P H I Ệ P U U Cho danh sách liên kết đơn với các Ví dụ 1 T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U phần tử trong danh sách là số nguyên Vẽ sơ đồ khối và cài đặt giải thuật sắp Ô N T H I Ô N T H I T R Ú C D T R Ú C D xếp các phần tử trong danh sách theo h h đổi hỗ iế I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T p ương p áp c trực t p. Lưu ý: định nghĩa cấu trúc danh sách B À B À liên kết đôi trước khi thực hiện cài đặt các giải thuật TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (21) Danh sách liên kết H I Ệ P H I Ệ P U U Cho mảng a có n số nguyên Ví dụ 2.1 T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U Vẽ sơ đồ khối và cài đặt giải thuật chèn 1 hầ ử à ả đã đ ắ ế hứ Ô N T H I Ô N T H I T R Ú C D T R Ú C D p n t v o m ng ược s p x p t tự tăng (kết quả mảng cũng được sắp I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T tăng). B À B À TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (22) Danh sách liên kết H I Ệ P H I Ệ P U U Cho danh sách liên kết đơn với các Ví dụ 2.2 T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U phần tử trong danh sách là số nguyên Vẽ đồ khối à ài đặ iải h ậ hè Ô N T H I Ô N T H I T R Ú C D T R Ú C D sơ v c t g t u t c n 1 phần tử vào danh sách đã được sắp xếp ế I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T thứ tự tăng (k t quả danh sách cũng được sắp tăng). B À B À TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (23) Danh sách liên kết H I Ệ P H I Ệ P U U Cho danh sách liên kết đôi với các Ví dụ 3 T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U phần tử trong danh sách là số nguyên Vẽ sơ đồ khối và cài đặt giải thuật sắp Ô N T H I Ô N T H I T R Ú C D T R Ú C D xếp các phần tử trong danh sách theo h h h iế I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T p ương p áp c èn trực t p. Lưu ý: định nghĩa cấu trúc danh sách B À B À liên kết đôi trước khi thực hiện cài đặt các giải thuật TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (24) Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học CẤU TRÚC DỮ LIỆU • Cấu trúc dữ liệu mảng • Danh sách liên kết • Cấu trúc dữ liệu cây Cây nhị phân • Cấu trúc cây H I Ệ P H I Ệ P U U – Thành phần dữ liệu: data – Thành phần con trỏ: Left, Right Cá l i â hị hâ T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U • c oạ c y n p n – Cây nhị phân – Cây nhị phân cân bằng Ô N T H I Ô N T H I T R Ú C D T R Ú C D – Cây nhị phân tìm kiếm – Cây nhị phân tìm kiếm cân bằng • Các thao tác trên cây nhị phân tìm kiếm I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T – Tạo cây – Duyệt cây theo thứ tự: NLR, LNR, LRN Thêm phần tử vào cây B À B À – – Xóa phần tử: nút lá, nút có 1 cây con, nút có 2 cây con. – Tìm phần tử trong cây TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (26) Demo HI Ệ P H I Ệ P U U T Ố T N G T Ố T N G D Ữ L I Ệ U D Ữ L I Ệ U Ô N T H I Ô N T H I T R Ú C D T R Ú C D I G I Ả N G I G I Ả N G C Ấ U T C Ấ U T B À B À TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (27)27