Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng liên thông) - Trường Cao đẳng Xây dựng số 1

Giáo trình "Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng liên thông)" được biên soạn với mục tiêu nhằm giúp sinh viên nắm được các kiến thức về: Các khái niệm cơ bản về giải thuật, đánh giá độ phức tạp của giải thuật; các kiểu cấu trúc dữ liệu thông dụng và một số giải thuật trên các kiểu cấu trúc dữ liệu đó. 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 (Ngành: Công nghệ thông tin - Cao đẳng liên thông) - Trường Cao đẳng Xây dựng số 1 BỘ XÂY DỰNG TRƯỜNG CAO ĐẲNG XÂY DỰNG SỐ 1 GIÁO TRÌNHMÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGÀNH: CÔNG NGHỆ THÔNG TIN (ỨNG DỤNG PHẦN MỀM) TRÌNH ĐỘ: CAO ĐẲNG LIÊN THÔNGBan hành kèm theo Quyết định số: 374ĐT/QĐ- CĐXD1 ngày 16 tháng 08 năm 2022 của Hiệu trưởng trường CĐXD số 1 Hà Nội, năm 2022 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à thamkhả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. LỜI NÓI ĐẦU Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT được biên soạn nhằmphục vụ cho giảng dạy và học tập cho trình độ Cao đẳng liên thông ngành Công nghệthông tin (Ứng dụng phần mềm) ở trường Cao đẳng Xây dựng số 1. Cấu trúc dữ liệuvà giải thuật là môn học cơ sở ngành nhằm cung cấp các kiến thức cơ bản về các kiểucấu trúc dữ liệu thông dụng và một số giải thuật trên các kiểu cấu trúc dữ liệu đótrong ngành Công nghệ thông tin. Giáo trình này được viết theo đề cương môn học Cấu trúc dữ liệu và giải thuật Nội dung gồm 04 chương như sau: Chương 1: Giải thuật Chương 2: Danh sách Chương 3: Mô hình cây và đồ thị Chương 4: Các giải thuật sắp xếp và tìm kiếm Mặc dù có nhiều cố gắng, nhưng trong quá trình biên soạn, biên tập và in ấn khótránh khỏi những thiếu sót. Chúng tôi rất mong nhận được sự đóng góp ý kiến từphía các thầy cô và bạn đọc để hoàn thiện giáo trình hơn! Xin trân trọng cảm ơn! Hà Nội, ngày……tháng……năm……… Tham gia biên soạn Trần Thị Mơ - Chủ biên 3 MỤC LỤCCHƯƠNG 1: GIẢI THUẬT ................................................................................. 7 1.1. Các khái niệm ............................................................................................. 8 1.1.1. Giải thuật ............................................................................................. 8 1.1.2. Cấu trúc dữ liệu ................................................................................... 8 1.2. Các đặc trưng của giải thuật ....................................................................... 8 1.2.1. Dữ liệu vào .......................................................................................... 9 1.2.2. Dữ liệu ra ............................................................................................. 9 1.3. Ngôn ngữ diễn đạt ...................................................................................... 9 1.3.1. Ngôn ngữ thông thường ...................................................................... 9 1.3.2. Lưu đồ ................................................................................................. 9 1.3.3. Ngôn ngữ lập trình ............................................................................ 11 1.4. Phương pháp thiết kế giải thuật................................................................ 12 1.4.1. Phân rã bài toán thành các bài toán nhỏ hơn..................................... 12 1.4.2. Phương pháp tinh chỉnh từng bước ................................................... 12CHƯƠNG 2: DANH SÁCH ............................................................................... 15 2.1. Danh sách tuyến tính ................................................................................ 16 2.1.1. Khái niệm chung ............................................................................... 16 2.1.2. Kiểu mảng ......................................................................................... 16 2.1.3. Kiểu ngăn xếp.................................................................................... 17 2.1.4. Kiểu hàng đợi .................................................................................... 19 2.2. Danh sách liên kết .................................................................................... 20 2.2.1. Danh sách liên kết đơn (singly linked list) ....................................... 21 2.2.3. Danh sách liên kết vòng (circular linked list) ................................... 29CHƯƠNG 3: MÔ HÌNH CÂY VÀ ĐỒ THỊ ...................................................... 32 3.1. Mô hình cây .............................................................................................. 33 3.1.1. Định nghĩa ......................................................................................... 33 3.1.2. Cây nhị phân...................................................................................... 33 3.2. Đồ thị ........................................................................................................ 35 4 3.2.1. Định nghĩa ......................................................................................... 35 3.2.2. Biểu diễn đồ thị ................................................................................. 37 2.2.3. Phép duyệt đồ thị ............................................................................... 39CHƯƠNG 4: CÁC GIẢI THUẬT SẮP XẾP VÀ TÌM KIẾM........................... 43 4.1. Các giải thuật sắp xếp .............................................................................. 46 4.1.1. Bài toán sắp xếp ....... ...