Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Lập trình máy tính, Tin ứng dụng - Trình độ CĐ/TC) - Trường Cao đẳng Nghề An Giang

Mục tiêu của giáo trình Cấu trúc dữ liệu và giải thuật giúp các bạn hiểu được nội dung của: dữ liệu, giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật; phân tích và xác định được dữ liệu, giải thuật, sự kết hợp của dữ liệu và giải thuật trong một chương trình máy tính. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Lập trình máy tính, Tin ứng dụng - Trình độ CĐ/TC) - Trường Cao đẳng Nghề An Giang ỦY BAN NHÂN DÂN TỈNH AN GIANG TRƯỜNG CAO ĐẲNG NGHỀ AN GIANG GIÁO TRÌNH Cấu trúc dữ liệu và giải thuậtNGHỀ LẬP TRÌNH MÁY TÍNH & TIN ỨNG DỤNGTRÌNH ĐỘ CAO ĐẲNG NGHỀ & TRUNG CẤP NGHỀ(Ban hành theo Quyết định số: /QĐ-CĐN ngày tháng năm 20 của Hiệu trưởng trường Cao đẳng nghề An Giang) Tên tác giả : Trần Thị Kim Ngọc Năm ban hành: 2018 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ể đượcphé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 kinhdoanh thiếu lành mạnh sẽ bị nghiêm cấm. 1 LỜI GIỚI THIỆU Bài giảng cấu trúc dữ liệu và giải thuật được viết nhằm để giảng dạy cho sinhviên chuyên ngành CNTT trường Cao Đẳng Nghề An giang. Bài giảng được thiếtkế theo chương trình môn học cấu trúc dữ liệu và giải thuật của Bộ ban hành. Bàigiảng này bao gồm 4 chương, nội dung các chương được trình bày các cấu trúc dữliệu và các giải thuật đơn giản nhất của tin học. Trước tiên bài giảng trình bày vềcác cấu trúc dữ liệu cơ bản như: mảng, con trỏ, cấu trúc, tập tin; tiếp theo là các cấutrúc dữ liệu nâng cao như: danh sách, ngăn xếp, hàng đợi và một số ứng dụng củadanh sách. Sau đó bài giảng trình bày tiếp về giải thuật sắp xếp và tìm kiếm, vớicác phương pháp sắp xếp: xen, chọn, nổi bọt, quick sort và tìm kiếm như: tuần tựvà nhị phân. Thêm vào đó, cuối chương sẽ có các bài tập tương ứng để sinh viên cóthể ôn lại lý thuyết và tùy vào mỗi chương mà có một số bài tập nâng cao đểkhuyến khích sinh viên tự học và nghiên cứu. Cuốn tài liệu giảng dạy này vẫn còn nhiều thiếu sót và hạn chế. Rất mongnhận được ý kiến đóng góp của sinh viên và các bạn đọc để bài giảng ngày cànghoàn thiện hơn. Chân thành cảm ơn quý Thầy Cô trong Hội đồng thẩm định của trường CaoĐẳng Nghề An Giang để bài giảng Cấu trúc dữ liệu và giải thuật được hoàn chỉnh. An Giang, ngày tháng năm 2018 Tham gia biên soạn Trần Thị Kim Ngọc 2 MỤC LỤCTUYÊN BỐ BẢN QUYỀN ................................................................................... 1LỜI GIỚI THIỆU ................................................................................................... 2MỤC LỤC .............................................................................................................. 3GIÁO TRÌNH MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ............... 6CHƢƠNG 1: GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT .............. 7 I. MỐI LIÊN HỆ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU ........................... 7 II. ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT ....................................... 9 1. Sự cần thiết phải phân tích giải thuật: ......................................................... 9 2. Thời gian thực hiện của giải thuật:............................................................ 10 a. Thời gian thực hiện chương trình: ......................................................... 10 b. Đơn vị đo thời gian thực hiện ................................................................ 11 c. Thời gian thực hiện trong trường hợp xấu nhất: .................................... 11 3. Tỷ suất tăng và độ phức tạp của giải thuật ................................................ 11 a. Tỷ suất tăng: ........................................................................................... 11 b. Khái niệm độ phức tạp của giải thuật .................................................... 12 4. Cách tính độ phức tạp: .............................................................................. 12 a. Qui tắc cộng: .......................................................................................... 12 b. Qui tắc nhân: .......................................................................................... 13 c. Qui tắc tổng quát để phân tích một chương trình: ................................. 13 d. Độ phức tạp của chương trình có gọi chương trình con không đệ quy: 13 5. Phân tích các chương trình đệ quy: ........................................................... 14 a. Thành lập phương trình đệ quy: ............................................................. 15 b. Giải phương trình đệ quy: ........ ...