BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN TRƢỜNG CAO ĐẲNG CƠ ĐIỆN XÂY DỰNG VIỆT XÔ KHOA CÔNG NGHỆ THÔNG TIN VÀ NGOẠI NGỮ GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGHỀ: QUẢN TRỊ MẠNG TRÌNH ĐỘ: TRUNG CẤP TUYÊN BỐ BẢN QUYỀN: Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể đƣợc phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. MÃ TÀI LIỆU: MH14 1 LỜI GIỚI THIỆU Kiến thức môn học Cấu trúc dữ liệu và giải thuật là một trong những nền tản cơ bản của những ngƣời muốn tìm hiểu sâu về Công nghệ thông tin đặt biệt đối với việc lập trình để giải quyết các bài toán trên máy tính điện tử. 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. Cấu trúc dữ liệu có thể đƣợc xem nhƣ là 1 phƣơng pháp lƣu trữ dữ liệu trong máy tính nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử dụng các dữ liệu một cách hiệu quả thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do vậy, cấu trúc dữ liệu và giải thuật là 2 yếu tố không thể tách rời và có những liên quan chặt chẽ với nhau.
Việc lựa chọn một cấu trúc dữ liệu có thể sẽ ảnh hƣởng lớn tới việc lựa chọn áp dụng giải thuật nào. Về nguyên tắc, các cấu trúc dữ liệu và các giải thuật có thể đƣợc biểu diễn và cài đặt bằng bất cứ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để có đƣợc các phân tích sâu sắc hơn và mô phạm, có kết quả thực tế hơn, chúng tôi đã sử dụng ngôn ngữ tựa Pascal để minh hoạ cho các cấu trúc dữ liệu và thuật toán. Mặc dầu có rất nhiều cố gắng, nhƣng không tránh khỏi những khiếm khuyết, rất mong nhận đƣợc sự đóng góp ý kiến của độc giả để giáo trình đƣợc hoàn thiện hơn.
Ninh bình, ngày. tháng …năm 2018 Tham gia biên soạn 1. Chủ biên ThS. Nguyễn Bá Quân 2 MỤC LỤC ĐỀ MỤC TRANG LỜI GIỚI THIỆU.
2 MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT. 5 CHƢƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT .Khái niệm giải thuật và đánh giá độ phức tạp của giải thuật. Khái niệm giải thuật. Ngôn ngữ diễn đạt giải thuật.
Thiết kế giải thuật. Đánh giá giải thuật .Các kiểu dữ liệu cơ bản .Kiểu bản ghi, kiểu con trỏ. Kiểu bản ghi. Kiểu con trỏ.
15 Bài tập thực hành của học viên .Các kiểu dữ liệu trừu tƣợng .Các cấu trúc lƣu trữ. Danh sách liên kết. 18 Bài tập thực hành của học viên .Mối quan hệ giữa CTDL và giải thuật. 20 Bài tập thực hành của học viên.
22 Gợi ý làm bài. 22 CHƢƠNG 2: ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY .Khái niệm đệ quy .Giải thuật đệ quy và chƣơng trình đệ quy. Giải thuật đệ qui. Chƣơng trình đệ qui .Các bài toán đệ quy căn bản.
Bài toán tính n giai thừa. Bài toán dãy số FIBONACCI. 24 Bài tập thực hành của học viên. 25 Gợi ý làm bài.
25 CHƢƠNG 3: DANH SÁCH .Danh sách và các phép toán cơ bản trên danh sách. Khái niệm danh dách. Các phép toán trên danh dách .Cài đặt danh sách theo cấu trúc mảng. Khởi tạo danh sách rỗng.
Kiểm tra danh sách rỗng. Chèn phần tử vào danh sách. Xóa phần tử khỏi danh sách .Cài đặt danh sách theo cấu trúc danh sách liên kết (đơn, kép). Khởi tạo danh sách rỗng.
Kiểm tra danh sách rỗng. Chèn phần tử vào danh sách. Xóa phần tử khỏi danh sách. Danh sách liên kết vòng.
Danh sách liên kết đôi. Danh sách đặc biệt. 38 Bài tập thực hành của học viên. 41 CHƢƠNG 4: CÁC PHƢƠNG PHÁP SẮP XẾP CƠ BẢN .Định nghĩa bài toán sắp xếp.
Phƣơng pháp chọn (Selection sort) .Giới thiệu phƣơng pháp .Ví dụ minh họa. Phƣơng pháp chèn (Insertion sort) .Giới thiệu phƣơng pháp .Ví dụ minh họa. Phƣơng pháp đổi chỗ (Interchange sort) .Giới thiệu phƣơng pháp .Ví dụ minh họa .Phƣơng pháp nổi bọt (Bubble sort) .Giới thiệu phƣơng pháp .Ví dụ minh họa .Phƣơng pháp sắp xếp nhanh (Quick sort) .Giới thiệu phƣơng pháp .Ví dụ minh họa. 50 Bài tập thực hành của học viên.
51 CHƢƠNG 5: TÌM KIẾM .Tìm kiếm tuyến tính .Giới thiệu phƣơng pháp .Ví dụ minh họa .Tìm kiếm nhị phân .Giới thiệu phƣơng pháp .Ví dụ minh họa. 54 Bài tập thực hành của học viên. 55 CHƢƠNG 6: CÂY. Khái niệm về cây và cây nhị phân.
Các khái niệm về cây. Khái niệm cây nhị phân. Biểu diễn cây nhị phân và cây tổng quát. Biểu diễn cây nhị phân.
Biểu diễn cây tổng quát. Bài toán duyệt cây nhị phân. Duyệt theo thứ tự trƣớc (gốc – trái – phải). Duyệt theo thứ tự giữa (trái – gốc – phải).
Duyệt theo thứ tự sau (trái – phải – gốc). 63 Bài tập thực hành của học viên. 63 CHƢƠNG 7: ĐỒ THỊ. Biểu diễn đồ thị.
Biểu diễn đồ thị bằng ma trận kề. Biểu diễn đồ thị bằng danh sách các đỉnh kề:. Bài toán tìm đƣờng đi trên đồ thị. 66 Bài tập thực hành của học viên.
68 YÊU CẦU VỀ ĐÁNH GIÁ KẾT QUẢ HỌC TẬP. 70 5 GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã môn học: MH14 Vị trí, tính chất, ý nghĩa và vai trò của môn học: - Vị trí: Môn học đƣợc bố trí sau khi sinh viên học xong môn học, mô đun: Lập trình căn bản, Cơ sở dữ liệu. - Tính chất: Là môn học chuyên ngành. - Ý nghĩa và vai trò: Đây là môn học cơ sở ngành của các ngành liên quan đến công nghệ thông tin, cung cấp cho sinh viên các kiến thức cơ bản về cấu trúc dữ liệu và giải thuật để làm nền tản cho việc lập trình giải quyết các vấn đề cần thiết.
Mục tiêu của môn học: - Về kiến thức: Mô tả đƣợc các khái niệm về kiểu dữ liệu trừu tƣơng(danh sách, cây, đồ thị), kiểu dữ liệu, cấu trúc dữ liệu và giải thuật. - Về kỹ năng: +Biết đƣợc các phép toán cơ bản tƣơng ứng với các cấu trúc dữ liệu và các giải thuật. + Biết cách tổ chức dữ liệu hợp lý, khoa học cho một chƣơng trình đơn giản. + Biết áp dụng thuật toán hợp lý đối với cấu trúc dữ liệu tƣơng ứng để giải quyết bài toán trên máy tính.
+ Biết và áp dụng đƣợc các phƣơng pháp sắp xếp, tìm kiếm cơ bản - Về năng lực tự chủ trách nhiệm: Bố trí làm việc khoa học đảm bảo an toàn cho ngƣời và phƣơng tiện học tập. Nội dung của môn học: Thời gian Số Kiểm tra* Tên chƣơng, mục Tổng Lý Thực TT (LT số thuyết hành hoặcTH) I Tổng quan về Cấu trúc dữ liệu 5 4 1 và giải thuật II Đệ qui và giải thuật đệ qui 5 2 2 1 III Danh sách 12 4 7 1 IV Các phƣơng pháp sắp xếp cơ 22 10 11 1 bản V Tìm kiếm 6 2 3 1 VI Cây 10 5 5 Cộng 60 26 30 4 6 CHƢƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã chƣơng: MH14-01 Giới thiệu: Tổng quan về giải thuật. Đầu tiên là cách phân tích 1 vấn đề, từ thực tiễn cho tới chương trình, cách thiết kế một giải pháp cho vấn đề theo cách giải quyết bằng máy tính. Tiếp theo, các phương pháp phân tích, đánh giá độ phức tạp và thời gian thực hiện giải thuật cũng được xem xét trong chương.
Mục tiêu: - Mô tả đƣợc khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Trình bày đƣợc các tiêu chuẩn để đánh giá độ phức tạp của giải thuật. - Ghi nhớ đƣợc các kiểu dữ liệu cơ bản, kiểu dữ liệu trừu tƣợng và các cấu trúc dữ liệu cơ bản. - Thực hiện các thao tác an toàn với máy tính.
Nội dung chính: 1. Khái niệm giải thuật và đánh giá độ phức tạp của giải thuật Mục tiêu: Mô tả được khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Trình bày được các tiêu chuẩn để đánh giá độ phức tạp của giải thuật. Khái niệm giải thuật Giải thuật, còn gọi là thuật toán (algorithm) là một trong những khái niệm quan trọng nhất trong tin học.
Thuật ngữ thuật toán xuất phát từ nhà toán học Arập Abu Ja'far Mohammed ibn Musa al Khowarizmi (khoảng năm 825). Giải thuật thể hiện một giải pháp cụ thể, thực hiện từng bƣớc một để đƣa tới lời giải cho một bài toán. Nói cách khác, giải thuật là một tập hữu hạn các phép toán cơ sở, đƣợc sắp đặt theo những quy tắc chính xác, nhằm giải một bài toán, hay là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bƣớc hữu hạn, nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đƣa vào. Các phép toán cơ sở là những phép toán đơn giãn mà thời gian thực hiện nó là hữu hạn và không phụ thuộc vào kích thƣớc của dữ liệu.
Các phép toán trong giải thuật phải đƣợc xác định rỏ ràng, dễ hiểu, không mập mờ. Với mọi bộ dữ liệu vào thoả mãn các điều kiện của bài toán, thuật toán phải dừng lại sau một số hữu hạn các bƣớc cần thực hiện 1. Ngôn ngữ diễn đạt giải thuật - Ngôn ngữ tự nhiên. - Giả ngữ, là một ngôn ngữ ”tựa ngôn ngữ lập trình”.
- Ngôn ngữ lập trình (Pascal, C,. Trong tài liệu này chúng ta sử dụng ngôn ngữ tựa Pascal để trình bày. Sau đây là một số qui tắt cơ bản: 1. Quy cách về cấu trúc chƣơng trình Mỗi chƣơng trình đều đƣợc gán một tên để phân biệt, tên này đƣợc viết bằng chữ in hoa, có thể có thêm dấu gạch nối và bắt đầu bằng từ khoá Program Ví dụ : Prorgram NHAN-MA-TRAN 7 Độ dài tên không hạn chế.