TẬP ĐOÀN DỆT MAY VIỆT NAM TRƢỜNG CAO ĐẲNG CÔNG NGHỆ THÀNH PHỐ HỒ CHÍ MINH Giáo Trình CẤU TRÚC DỮ LIỆU và GIẢI THUẬT Nghề: Công nghệ thông tin Trình độ: Cao Đẳng (Ban hành theo Quyết định số: ngày tháng năm của trường Cao đẳng Công nghệ Tp.HỒ CHÍ MINH, THÁNG 07 NĂM 2021 Tuyên bố bản quyền Giáo trình này sử dụng làm tài liệu giảng dạy lưu hành nội bộ trong trường Cao đẳng Công nghệ Tp.HCM Cao đẳng Công nghệ Tp.HCM không sử dụng và không cho phép bất kỳ cá nhân hay tổ chức nào sử dụng giáo trình này với mục đích kinh doanh. Mọi trích dẫn, sử dụng giáo trình này với mục đích khác hay ở nơi khác đều phải được sự đồng ý bằng văn bản của Cao đẳng Công nghệ Tp.HCM LỜI NÓI ĐẦU Tài liệu này dùng cho học sinh hệ Trung cấp và sinh viên hệ Cao đẳng ngành công nghệ thông tin học tập và nghiêm cứu về “Cấu trúc dữ liệu và giải thuật” Tài liệu gồm các nội dung chisng sau: Chương 1: Tổng quan về cấu trúc dữ liệu và giải thuật, các tiêu chuẩn danh gia cấu trúc dữ liệu ,phản ánh đúng thực tếp, phù hợp với các thao tác trên đó, tiết kiệm tài nguyên hệ thống. Kiểu dữ liệu, kiểu dữ liệu cơ bản, các kiểu dữ liệu có cấu trúc, kiểu chuỗi ký tự, kiểu mảng, kiểu union, kiểu mẫu tin (cấu trúc), kiểu con trỏ, kiểu tập tin, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Chương 2: ệ quy và giải thuật đệ quy, khái niệm đệ quy, thuật toán đệ quy và các chương trình đệ quy, giải thuật đệ quy, các chương trình đệ quy. Các bài toán đệ quy căn bản, hàm tính giai thừa, dãy số fibonacci. Chương 3: Tìm kiếm, tìm kiếm tuyến tính,tìm kiếm nhị phân, giải thuật, cài đặt, đánh giá giải. 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), chèn (Insertion Sort), đổi chỗ (Interchange Sort), nổi bọt (Bubble Sort), sắp xếp nhanh Quick Sort, giải thuật phân hoạch dãy al, al+1, ., ar thành 2 dãy con, giải thuật phân hoạch dãy sắp xếp dãy al, al+1, ., ar, cài đánh giá giải thuật Chương 5: Danh sách, danh sách liên kết (Xâu liên kết), định nghiã, biểu diễn Xâu liên kết, danh sách liên kết đơn (Xâu đơn), khai báo xâu liên kết đơn, các thao tác trên xâu liên kết đơn, loại bỏ một phần tủ trong xâu, duyệt xâu, sắp thứ tự Xâu, thuật Toán QuickSort, ngăn xếp – stack,cài đặt ngăn xếp bằng xâu đơn, cài đặt ngăn xếp bằng mảng và các thao tác, ứng dụng ngăn xếp trong xử lý biểu thức hậu tố. Hàng đợi – Queue, khái niệm, cài đặt hàng đợi bằng xâu liên kết, cài đặt hàng đợi bằng mảng. Chương 6: Cây nhị phân, định nghĩa và các khái niệm cơ bản, định nghĩa cây, các khái niệm khác, cây nhị phân, định nghĩa, vài tính chất của cây nhị phân, biểu diễn cây nhị phân, duyệt cây nhị phân, định nghĩa, các thuật toán duyệt cây nhị phân, cài đặt thuật toán duyệt qua cây nhị phân LNR, cài đặt cây nhị phân. Cây tìm kiếm nhị phân (Binary Search Trees), định nghĩa, cài đặt cây tìm kiếm nhị phân, tìm kiếm một phần tử trên cây BST, chèn một phần tử vào cây BST, xây dựng cây BST, phương pháp sắp xếp bằng cây BST, xóa một phần tử khỏi cây BST, hủy cây nhị phân. Tài liệu không chỉ đề cập đến những vấn đề cơ sở lý luận mà còn trình bày một số kỹ năng, kinh nghiệm cần thiết để thiết kế và cài đặt các mạng máy tính. Hy vọng sẽ có ích cho các bạn học sinh sinh viên và những người muốn xây dựng các hệ thống tin học ứng dụng phục vụ cho sản xuất, quản lý trong các doanh nghiệp. Có thể còn nhiều thiếu sót trong trình bày và biên soạn do khả năng, trình độ, nhưng người biên soạn mạnh dạn giới thiệu tài liệu này và mong nhận được sự góp ý của bạn đọc. Mục lục MỤC LỤC Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT . Các tiêu chuẩn danh gia cấu trúc dữ liệu . Phản ánh đúng thực tế. Phù hợp với các thao tác trên đó. Tiết kiệm tài nguyên hệ thống. Kiểu dữ liệu . Kiểu dữ liệu cơ bản . Các kiểu dữ liệu có cấu trúc . Kiểu chuỗi ký tự . Kiểu mẫu tin (cấu trúc) . Kiểu con trỏ . Kiểu tập tin . Mối quan hệ giữa cấu trúc dữ liệu và giải thuật . 38 Chương 2: Ệ QUY V GIẢI THUẬT Ệ QUY . Khái niệm đệ quy . Thuật toán đệ quy và các chương trình đệ quy. Giải thuật đệ quy. Các chương trình đệ quy. Các bài toán đệ quy căn bản . Hàm tính giai thừa . 48 Chương 3: T M KI M . Tìm kiếm tuyến tính . Ðánh giá giải thuật . Tìm kiếm nhị phân. Ðánh giá giải thuật . 54 Mục lục 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) . Ðánh giá giải thuật . Phương pháp chèn (Insertion Sort) . ánh giá giải thuật . Phương pháp đổi chỗ (Interchange Sort) . Ðánh giá giải thuật . Phương pháp nổi bọt (Bubble Sort) . Ðánh giá giải thuậ . Phương pháp sắp xếp nhanh Quick Sort . Giải thuật phân hoạch dãy al, al+1, ., ar thành 2 dãy con . Giải thuật phân hoạch dãy sắp xếp dãy al, al+1, . Ðánh giá giải thuật . 72 Chương 5: D NH S CH . Danh sách liên kết (Xâu liên kết ) . Biểu diễn Xâu liên kết . Danh sách liên kết đơn (Xâu đơn) . Khai báo xâu liên kết đơn . Các thao tác trên xâu liên kết đơn . Loại bỏ một phần tủ trong xâu . Sắp thứ tự Xâu . Thuật Toán QuickSort . Ngăn xếp – stack . Cài đặt ngăn xếp bằng xâu đơn . Cài đặt ngăn xếp bằng mảng và các thao tác . Ứng dụng ngăn xếp trong xử lý biểu thức hậu tố . Hàng đợi – Queue . Cài đặt hàng đợi bằng xâu liên kết . Cài đặt hàng đợi bằng mảng . 99 Chương 6: CÂY NH PHÂN . ịnh nghĩa và các khái niệm cơ bản . ịnh nghĩa cây . Các khái niệm khác . Cây nhị phân . Vài tính chất của cây nhị phân . Biểu diễn cây nhị phân . Duyệt cây nhị phân. Các thuật toán duyệt cây nhị phân . Cài đặt thuật toán duyệt qua cây nhị phân LNR . Cài đặt cây nhị phân . Cây tìm kiếm nhị phân (Binary Search Trees) . Cài đặt cây tìm kiếm nhị phân. Tìm kiếm một phần tử trên cây BST . Chèn một phần tử vào cây BST, xây dựng cây BST . Phương pháp sắp xếp bằng cây BST . Xóa một phần tử khỏi cây BST, hủy cây nhị phân . 122 CHƢƠNG TRÌNH MÔN HỌC Tên môn học: Cấu trúc dữ liệu và giải thuật Mã môn học: MH 12 Thời gian thực hiện môn học: 45 giờ; (Lý thuyết: 15 giờ; Thực hành, thí nghiệm, thảo luận, bài tập: 28 giờ; Kiểm tra: 2 giờ) I. Vị trí, tính chất môn học: - Vị trí: môn học được bố trí sau khi người học học xong môn học: Lập trình căn bản, Cơ sở dữ liệu. - Tính chất: là môn học cơ sở ngành bắt buộc. Mục tiêu môn học: - Về kiến thức: Hiểu được mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Phân tích được các kiểu dữ liệu, giải thuật, sự kết hợp chúng để tạo thành một chương trình máy tính. 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 thích để giải quyết bài toán thực tế. Biết và áp dụng được các phương pháp sắp xếp, tìm kiếm đơn giản. - Về kỹ năng: ánh giá kỹ năng thực hành của người học: Dùng ngôn ngữ lập trình bất kỳ nào đó thể hiện trên máy tính các bài toán cần kiểm nghiệm về: đệ qui, danh sách, cây, đồ thị, sắp xếp, tìm kiếm. - Về năng lực tự chủ và trách nhiệm: Rèn luyện tư duy logic để phân tích, tổng hợp. Thao tác cẩn thận, tỉ mỉ. Nội dung môn học: Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 1 Chương I: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ 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. 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: Chương này trình bày về tổng quan về cấu trúc dữ liệu và giải thuật, các tiêu chuẩn danh gia cấu trúc dữ liệu ,phản ánh đúng thực tếp, phù hợp với các thao tác trên đó, tiết kiệm tài nguyên hệ thống. Kiểu dữ liệu, kiểu dữ liệu cơ bản, các kiểu dữ liệu có cấu trúc, kiểu chuỗi ký tự, kiểu mảng, kiểu union, kiểu mẫu tin (cấu trúc), kiểu con trỏ, kiểu tập tin, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. KHÁI NIỆM THUẬT GIẢI VÀ ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT 1. Khái niệm thuật giải. Tập các bước có thể tính toán được để đạt được kết quả mong muốn. Khi đã có mô hình thích hợp cho một bài toán ta cần cố gắng tìm cách giải quyết bài toán trong mô hình đó. Khởi đầu là tìm một giải thuật, đó là một chuỗi hữu hạn các chỉ thị (instruction) mà mỗi chỉ thị có một ý nghĩa rõ ràng và thực hiện được trong một lượng thời gian hữu hạn. Knuth (1973) định nghĩa giải thuật là một chuỗi hữu hạn các thao tác để giải một bài toán nào đó. Các tính chất quan trọng của giải thuật là: - Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước. - Xác định (definiteness): mỗi bước của giải thuật phải được xác định rõ ràng và phải được thực hiện chính xác, nhất quán. - Hiệu quả (effectiveness): các thao tác trong giải thuật phải được thực hiện trong một lượng thời gian hữu hạn. Mỗi thuật toán có một dữ liệu vào (Input) và một dữ liệu ra (Output); Nói tóm lại, một giải thuật phải giải quyết xong công việc khi ta cho dữ liệu vào. Có nhiều cách để thể hiện giải thuật: dùng lời, dùng lưu đồ, .
