Giáo trình Cấu trúc dữ liệu & giải thuật
Cấu trúc dữ liệu và giải thuật là một trong những môn học cơ bản của sinh viên ngành Công
nghệ thông tin. Các cấu trúc dữ liệu và các giải thuật được xem như là 2 yếu tố quan trọng nhất
trong lập trình, đúng như câu nói nổi tiếng của Niklaus Wirth: Chương trình = Cấu trúc dữ liệu +
Giải thuật (Programs = Data Structures + Algorithms). Nắm vững các cấu trúc dữ liệu và các giải
thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng các
công cụ lập trình hiện đại.
Bạn đang xem trước 20 trang tài liệu Giáo trình Cấu trúc dữ liệu & giải thuật, để xem tài liệu hoàn chỉnh bạn click vào nút TẢI VỀ ở trên
.............. 49 4.1 NGĂN XẾP (STACK) .................................................................................................................. 47 4.1.1 Khái niệm ................................................................................................................................... 47 4.1.2 Cài đặt ngăn xếp bằng mảng ...................................................................................................... 48 141 4.1.3 Cài đặt ngăn xếp bằng danh sách liên kết................................................................................... 50 4.1.4 Một số ứng dụng của ngăn xếp................................................................................................... 53 4.2 HÀNG ĐỢI (QUEUE) .................................................................................................................. 60 4.2.1 Khái niệm ................................................................................................................................... 60 4.2.2 Cài đặt hàng đợi bằng mảng....................................................................................................... 61 4.2.3 Cài đặt hàng đợi bằng danh sách liên kết ................................................................................... 63 4.3 TÓM TẮT CHƯƠNG 4 ................................................................................................................ 65 4.4 CÂU HỎI VÀ BÀI TẬP ............................................................................................................... 65 CHƯƠNG 5: CẤU TRÚC DỮ LIỆU KIỂU CÂY ............................................................................. 70 5.1 KHÁI NIỆM.................................................................................................................................. 67 5.2 CÀI ĐẶT CÂY ............................................................................................................................. 68 5.2.1 Cài đặt cây bằng mảng các nút cha ............................................................................................ 68 5.2.2 Cài đặt cây thông qua danh sách các nút con ............................................................................. 69 5.3 DUYỆT CÂY................................................................................................................................ 70 5.3.1 Duyệt cây thứ tự trước................................................................................................................ 70 5.3.2 Duyệt cây thứ tự giữa ................................................................................................................. 71 5.3.3 Duyệt cây thứ tự sau................................................................................................................... 71 5.4 CÂY NHỊ PHÂN........................................................................................................................... 72 5.4.1 Cài đặt cây nhị phân bằng mảng................................................................................................. 73 5.4.2 Cài đặt cây nhị phân bằng danh sách liên kết............................................................................. 73 5.4.3 Duyệt cây nhị phân..................................................................................................................... 74 5.5 TÓM TẮT CHƯƠNG 5 ................................................................................................................ 75 5.6 CÂU HỎI VÀ BÀI TẬP ............................................................................................................... 75 CHƯƠNG 6: ĐỒ THỊ ......................................................................................................................... 80 6.1 CÁC KHÁI NIỆM CƠ BẢN......................................................................................................... 77 6.1.1 Đồ thị có hướng.......................................................................................................................... 77 6.1.2 Đồ thị vô hướng.......................................................................................................................... 78 6.1.3 Đồ thị có trọng số ....................................................................................................................... 78 6.2 BIỂU DIỄN ĐỒ THỊ..................................................................................................................... 79 6.2.1 Biểu diễn đồ thị bằng ma trận kề................................................................................................ 79 6.2.2 Biểu diễn đồ thị bằng danh sách kề ............................................................................................ 80 6.3 DUYỆT ĐỒ THỊ ........................................................................................................................... 81 6.3.1 Duyệt theo chiều sâu .................................................................................................................. 81 6.3.2 Duyệt theo chiều rộng ................................................................................................................ 82 6.3.3 Ứng dụng duyệt đồ thị để kiểm tra tính liên thông..................................................................... 84 6.4 TÓM TẮT CHƯƠNG 6 ................................................................................................................ 85 142 6.5 CÂU HỎI VÀ BÀI TẬP ............................................................................................................... 85 CHƯƠNG 7: SẮP XẾP VÀ TÌM KIẾM ............................................................................................ 90 7.1 BÀI TOÁN SẮP XẾP ................................................................................................................... 87 7.2 CÁC GIẢI THUẬT SẮP XẾP ĐƠN GIẢN ................................................................................. 88 7.2.1 Sắp xếp chọn .............................................................................................................................. 88 7.2.2 Sắp xếp chèn............................................................................................................................... 89 7.2.3 Sắp xếp nổi bọt ........................................................................................................................... 91 7.3 QUICK SORT............................................................................................................................... 94 7.3.1 Giới thiệu.................................................................................................................................... 94 7.3.2 Các bước thực hiện giải thuật..................................................................................................... 95 7.3.3 Cài đặt giải thuật......................................................................................................................... 96 7.4 HEAP SORT ................................................................................................................................. 97 7.4.1 Giới thiệu.................................................................................................................................... 97 7.4.2 Các thuật toán trên heap ............................................................................................................. 97 7.5 MERGE SORT (SẮP XẾP TRỘN) ............................................................................................ 105 7.5.1 Giới thiệu.................................................................................................................................. 105 7.5.2 Trộn 2 dãy đã sắp ..................................................................................................................... 105 7.5.3 Sắp xếp trộn.............................................................................................................................. 108 7.6 BÀI TOÁN TÌM KIẾM .............................................................................................................. 110 7.7 TÌM KIẾM TUẦN TỰ................................................................................................................ 110 7.8 TÌM KIẾM NHỊ PHÂN .............................................................................................................. 110 7.9 CÂY NHỊ PHÂN TÌM KIẾM..................................................................................................... 112 7.9.1 Tìm kiếm trên cây nhị phân tìm kiếm ...................................................................................... 112 7.9.2 Chèn một phần tử vào cây nhị phân tìm kiếm.......................................................................... 114 7.9.3 Xoá một nút khỏi cây nhị phân tìm kiếm ................................................................................. 116 7.10 TÓM TẮT CHƯƠNG 5............................................................................................................ 116 7.11 CÂU HỎI VÀ BÀI TẬP ........................................................................................................... 117 PHỤ LỤC I: HƯỚNG DẪN GIẢI CÂU HỎI VÀ BÀI TẬP .......................................................... 118 PHỤ LỤC II: MÃ NGUỒN THAM KHẢO................................................................................... 120 TÀI LIỆU THAM KHẢO................................................................................................................. 139 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Biên soạn : THS. DƯƠNG TRẦN ĐỨC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã số: 412CDG240 Chịu trách nhiệm bản thảo TRUNG TÂM ÐÀO TẠO BƯU CHÍNH VIỄN THÔNG 1
File đính kèm:
Cấu trúc dữ liệu & giải thuật.pdf
