›

Giáo trình Cấu trúc dữ liệu - Trần Ngọc Bảo

pdf 27 trang huongle 3814
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu - Trần Ngọc Bảo", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_cau_truc_du_lieu_tran_ngoc_bao.pdf

Nội dung text: Giáo trình Cấu trúc dữ liệu - Trần Ngọc Bảo

  1. Đạ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
  2. Đạ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
  3. Đạ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
  4. Cấu trúc mảng một chiều • Các giảithui thuậtttìmki tìm kiếm P P ìm kiếm tuần tự (Sequence Search) Ệ Ệ – T HI HI UUUU – Tìm ki ếmnhm nhị phân (Binary Search) ỆỆ T NG T NG LI LI • Các giải thuật sắp xếp Ố Ố ỮỮ T T – Sắpxp xếp đổichi chỗ trựctic tiếp DDDD – Sắp xếp chọn trực tiếp ÔN THI ÔN THIÔN THI RÚC RÚC – Sắp xếp chèn trực tiếp T TTT – Sắp xếp nổi bọt NG NG U U ẢẢ ẤẤ – Sắp xếp nổi bọt cải tiến CC I GII GI – Shell sort BÀBÀ – Heap sort – Quick sort – Merge sort TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN H4ỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((44))
  5. Cấu trúc mảng một chiều • Yêu cầu P P Ệ Ệ – Trình bày ý tưởng giải thuật HI HI UUUU ỆỆ – Cho ví dụ minh họa T NG T NG LI LI Ố Ố ỮỮ T T DDDD – Biểudiu diễngin giảithui thuật • Biểu diễn giải thuật bằng mã giả ÔN THI ÔN THIÔN THI RÚC RÚC • Biểudiu diễnngi giảithui thuậtbt bằng sơ đồ khối T TTT NG NG U U ẢẢ ẤẤ – Cài đặt bằng ngôn ngữ C/C++ CC I GII GI – Cho biếttk kếtqut quả thựcchi hiệnnch chạy BÀBÀ từng bước giải thuật TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN H5ỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((55))
  6. Giải thuật tìm kiếm tuần tự • Bài t oá n P P Ệ Ệ – Cho mảng a có n số nguyên (n ≤ HI HI UUUU ỆỆ 100) T NG T NG LI LI Ố Ố ỮỮ T T – Yêu cầu: cho biết số nguyên x c ó DDDD tồn tại trong mảng a không ? ÔN THI ÔN THIÔN THI RÚC RÚC • Nếucóchobiu có cho biếttv vị trí đầuutiênxxu tiên x xuất T TTT NG NG U U hiện trong mảng ẢẢ ẤẤ CC I GII GI • Ngược lại thônggg báo x không tồn tại BÀBÀ trong mảng. TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN H6ỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((66))
  7. Giải thuật tìm kiếm tuần tự • Ví d ụ P P Ệ Ệ – Cho mảng a có 6 phần tử (n = 6) như HI HI UUUU sau: ỆỆ T NG T NG LI LI 1 54237 Ố Ố ỮỮ T T DDDD – Yêu cầu: • Tìm x = 3 ? ÔN THI ÔN THIÔN THI RÚC RÚC T TTT • Tìm x = 10 ? NG NG U U ẢẢ ẤẤ – Kết quả: CC I GII GI • X=3xuX = 3 xuấthit 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-TIN H7ỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((77))
  8. Giải thuật tìm kiếm tuần tự • ÝtÝ tưởng giiảiith thuật P P Ệ Ệ – Cho mảng a có 6 phần tử (n = 6) như HI HI UUUU sau: ỆỆ T NG T NG LI LI Ố Ố ỮỮ T T 1 5 4 2 3 7 DDDD ÔN THI ÔN THIÔN THI RÚC RÚC T TTT NG NG U U ẢẢ ẤẤ CC I GII GI BÀBÀ X = 3 X = 3 xuất hiện ở vị trí thứ 5 trong mảng TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN H8ỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((88))
  9. Giải thuật tìm kiếm tuần tự • ÝtÝ tưởng giiảiith thuật P P Ệ Ệ – Cho mảng a có 6 phần tử (n = 6) như HI HI UUUU sau: ỆỆ T NG T NG LI LI Ố Ố ỮỮ T T 1 5 4 2 3 7 DDDD ÔN THI ÔN THIÔN THI RÚC RÚC T TTT NG NG U U ẢẢ ẤẤ CC I GII GI BÀBÀ X = 10 X = 10 không tồn tại trong mảng TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN H9ỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((99))
  10. Giải thuật tìm kiếm tuần tự • Ví d ụ P P – Cho mảng a có 6 phần tử (n = 6) như sau: Ệ Ệ HI HI UUUU 1 5 4 2 3 7 ỆỆ – Yêu cầu: T NG T NG LI LI Ố Ố ỮỮ • Tìm x = 3 ? T T DDDD – Kết quả: ÔN THI ÔN THIÔN THI RÚC RÚC Lầnlặp i a[i] = x ? Kếtquả T TTT 10a[0]=1 ≠ x=3 i=i+1 =1 NG NG U U ẢẢ ẤẤ 21a[1]=5 ≠ x=3 i=i+1 =2 CC I GII GI 3 2 a[2]=4 ≠ x=3 i=i+1 =3 BÀBÀ 43a[3]=2 ≠ x=3 i=i+1 =4 54a[0]=3 = x=3 Kết thúc gt X = 3 xuấtthihiện ở vị trí thứ 5 trong mảng TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1010))
  11. Giải thuật tìm kiếm tuần tự P P Ệ Ệ HI HI UUUU ỆỆ T NG T NG LI LI Ố Ố ỮỮ T T DDDD ÔN THI ÔN THIÔN THI RÚC RÚC T TTT NG NG U U ẢẢ ẤẤ CC I GII GI BÀBÀ TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1111))
  12. Giải thuật tìm kiếm nhị phân • Bài t oá n P P Ệ Ệ – Cho mảng a có n số nguyên (n ≤ HI HI UUUU ỆỆ 100) T NG T NG LI LI Ố Ố ỮỮ T T – Yêu cầu: cho biết số nguyên x c ó DDDD tồn tại trong mảng a không ? ÔN THI ÔN THIÔN THI RÚC RÚC • Nếucóchobiu có cho biếttv vị trí đầuutiênxxu tiên x xuất T TTT NG NG U U hiện trong mảng ẢẢ ẤẤ CC I GII GI • Ngược lại thônggg báo x không tồn tại BÀBÀ trong mảng. – Điềukiu kiện: Mảng a đã được sắpthp thứ tự tăng TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN12 HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1212))
  13. Giải thuật tìm kiếm tuần tự • Ví d ụ P P Ệ Ệ – Cho mảng a có 6 phần tử (n = 6) như HI HI UUUU sau: ỆỆ T NG T NG LI LI 1 23457 Ố Ố ỮỮ T T DDDD – Yêu cầu: • Tìm x = 3 ? ÔN THI ÔN THIÔN THI RÚC RÚC T TTT – Kết quả: NG NG U U ẢẢ ẤẤ • X = 3 xuất hiện ở vị trí thứ 5 trong mảng CC I GII GI BÀBÀ TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN13 HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1313))
  14. Giải thuật tìm kiếm nhị phân • Ví d ụ P P – Cho mảng a có 6 phần tử (n = 6) như sau: Ệ Ệ HI HI UUUU 1 2 3 4 5 7 ỆỆ – Yêu cầu: T NG T NG LI LI Ố Ố ỮỮ • Tìm x = 4 ? T T DDDD – Kết quả: Lầnlặp l r m=[(l+r)/2] a[m] = x ? Kếtquả ÔN THI ÔN THIÔN THI RÚC RÚC T TTT 1 0 5 [(0+5)/2]=2 a[2]=3 x=4 r=m-1 =3 CC I GII GI 333 [(3+3)/ 2] =3 a[[]3]=4 = x=4 Kết thúc gt BÀBÀ X = 4 xuấtthihiện ở vị trí thứ 4 trong mảng TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1414))
  15. Giải thuật tìm kiếm nhị phân P P Ệ Ệ HI HI UUUU ỆỆ T NG T NG LI LI Ố Ố ỮỮ T T DDDD ÔN THI ÔN THIÔN THI RÚC RÚC T TTT NG NG U U ẢẢ ẤẤ CC I GII GI BÀBÀ TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1515))
  16. Cấu trúc mảng một chiều • Các giải thuật tìm kiếm P P ìm kiếmtuầntự (Sequence Search) Ệ Ệ – T HI HI UUUU – Tìm kiếm nhị phân (Binary Search) ỆỆ T NG T NG LI LI • Các giảithuậtsắpxếp Ố Ố ỮỮ T T – Sắp xếp đổi chỗ trực tiếp DDDD – Sắpxếpchọntrựctiếp ÔN THI ÔN THIÔN THI RÚC RÚC – Sắpxếpchèntrựctiếp T TTT – Sắpxếpnổibọt NG NG U U ẢẢ ẤẤ – Sắpxếpnổibọtcảitiến CC I GII GI – Shell sort BÀBÀ – Heap sort – Quick sort – Merge sort TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN16 HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1616))
  17. Các giải thuật sắp xếp trên mảng 1 chiều • Yêu cầu P P Ệ Ệ – Trình bày ý tưởng giải thuật HI HI UUUU ỆỆ – Cho ví dụ minh họa T NG T NG LI LI Ố Ố ỮỮ T T DDDD – Biểudiu diễngin giảithui thuật • Biểu diễn giải thuật bằng mã giả ÔN THI ÔN THIÔN THI RÚC RÚC • Biểudiu diễnngi giảithui thuậtbt bằng sơ đồ khối T TTT NG NG U U ẢẢ ẤẤ – Cài đặt bằng ngôn ngữ C/C++ CC I GII GI – Cho biếttk kếtqut quả thựcchi hiệnnch chạy BÀBÀ từng bước giải thuật Demo TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN17 HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1717))
  18. Struct và sắp xếp mảng struct • Struct P P Ệ Ệ – Cho thông tin học sinh, sinh viên, là 1 HI HI UUUU struct có nhiều thông tin ỆỆ T NG T NG LI LI • Sắpxếp danh sách (mảng struct) Ố Ố ỮỮ T T – Chọn 1 trong các giải thuật sắp xếp trên mảng DDDD 1 chiều để sắpxếpcácphầntử trong danh sách theo mộthoặc nhiềutiêuchí(điềukiện) ÔN THI ÔN THIÔN THI RÚC RÚC • Sắp xếp danh sách sinh viên theo họ tên T TTT NG NG U U • Sắpxếp danh sách sinh viên giảmdầntheođiểmtốt ẢẢ ẤẤ nghiệp CC I GII GI • Sắp xếp danh sách sinh viên theo họ tên, điểm thi tốt nghiệp BÀBÀ Ví d ụ TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((1818))
  19. Đạ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
  20. Danh sách liên kết • Cấutrúctu trúc tự trỏ – Thành phần dữ liệu: data P P Ệ Ệ – Thành phần con trỏ: Next, Previous HI HI UUUU • Cálác loại d an h s ách liên k ết ỆỆ T NG T NG – Danh sách liên kết đơn LI LI Ố Ố ỮỮ – Danh sách liên kết đôi T T DDDD – Danh sách vòng – Danh sách đa liên kết ÔN THI ÔN THIÔN THI RÚC RÚC – Stack/Queue T TTT NG NG U U • Các thao tác trên sách liên kết ẢẢ ẤẤ – Thêm phần tử CC I GII GI – Xóa ph ầnnt 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 Demo TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((2020))
  21. Danh sách liên kết Ví d ụ 1 P P Ệ Ệ HI HI UUUU Cho danh sách liên kết đơn với các ỆỆ T NG T NG LI LI phầntử trong danh sách là số nguyên Ố Ố ỮỮ T T DDDD Vẽ sơ đồ khối và cài đặt giải thuật sắp xếpcácphầntử trong danh sách theo ÔN THI ÔN THIÔN THI RÚC RÚC T TTT NG NG phương pháp đổi chỗ trựctiếp. U U ẢẢ ẤẤ CC Lưuý: định nghĩacấu trúc danh sách I GII GI BÀBÀ liên kết đôi trướckhithựchiệncàiđặt các giải ttuhuật TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((2121))
  22. Danh sách liên kết Ví d ụ 2.1 P P Ệ Ệ HI HI UUUU Cho mảng a có n số nguyên ỆỆ T NG T NG LI LI Vẽ sơđồkhốivàcàiđặtgiảithuậtchèn Ố Ố ỮỮ T T DDDD 1 phầntử vàomảng đã đượcsắpxếpthứ ÔN THI ÔN THIÔN THI RÚC RÚC tự tăng (kếtquả mảng cũng đượcsắp T TTT NG NG U U tăng). ẢẢ ẤẤ CC I GII GI BÀBÀ TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((2222))
  23. Danh sách liên kết Ví d ụ 2.2 P P Ệ Ệ HI HI UUUU Cho danh sách liên kết đơn với các ỆỆ T NG T NG LI LI phầntử trong danh sách là số nguyên Ố Ố ỮỮ T T DDDD Vẽ sơ đồ khối và cài đặtgiải thuậtchèn ÔN THI ÔN THIÔN THI RÚC RÚC 1phầntử vào danh sách đã đượcsắpxếp T TTT NG NG U U thứ tự tăng (kếtquả danh sách cũng được ẢẢ ẤẤ CC I GII GI sắp tăng). BÀBÀ TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((2323))
  24. Danh sách liên kết Ví d ụ 3 P P Ệ Ệ HI HI UUUU Cho danh sách liên kết đôi với các ỆỆ T NG T NG LI LI phầntử trong danh sách là số nguyên Ố Ố ỮỮ T T DDDD Vẽ sơ đồ khối và cài đặt giải thuật sắp xếpcácphầntử trong danh sách theo ÔN THI ÔN THIÔN THI RÚC RÚC T TTT NG NG phương pháp chèn trựctiếp. U U ẢẢ ẤẤ CC Lưuý: định nghĩacấu trúc danh sách I GII GI BÀBÀ liên kết đôi trướckhithựchiệncàiđặt các giải ttuhuật TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((2424))
  25. Đạ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
  26. Cây nhị phân • Cấutrúccâyu trúc cây – Thành phần dữ liệu: data P P Ệ Ệ – Thành phần con trỏ: Left, Right HI HI UUUU • Cálác loạiâi cây nh ị phân ỆỆ T NG T NG – Cây nhị phân LI LI Ố Ố ỮỮ – Cây nhị phân cân bằng T T DDDD – Cây nhị phân tìm kiếm – Cây nhị phân tìm kiếm cân bằng ÔN THI ÔN THIÔN THI RÚC RÚC T TTT • Các thao tác trên cây nh ị phân tìm ki ếm NG NG U U – Tạo cây ẢẢ ẤẤ – Duyệt cây theo thứ tự: NLR, LNR, LRN CC I GII GI – Thêm ph ầnnt 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 Demo TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((2626))
  27. P P Ệ Ệ HI HI UUUU ỆỆ T NG T NG LI LI Ố Ố ỮỮ T T DDDD ÔN THI ÔN THIÔN THI RÚC RÚC T TTT NG NG U U ẢẢ ẤẤ CC I GII GI BÀBÀ TRẦN NGỌC BẢO ” KHOA TOÁN -TIN-TIN27 HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” ((2727))