Bài giảng môn học: Cấu trúc dữ liệu và giải thuật

Bài giảng môn học: Cấu trúc dữ liệu và giải thuật với năm chương được chia thành các chủ đề khác nhau từ các khái niệm cơ bản cho tới thuật toán sắp xếp, tìm kiếm, cấu trúc dữ liệu cơ bản như ngăn xếp, hàng đợi, danh sách liên kết, cây cân bằng... Hy vọng tài liệu sẽ cung cấp cho các bạn sinh viên và độc giả những thông tin hữu ích.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học: Cấu trúc dữ liệu và giải thuậtBài giảng môn học: Cấu trúc Dữ liệu và Giải thuậtMỤC LỤCLỜI NÓI ĐẦU .................................................................................................................................... 1CHƯƠNG 1: THUẬT TOÁN VÀ CẤU TRÚC DỮ LIỆU ....................................................... 2 1. Thuật toán (giải thuật) - Algorithm ............................................................................................. 2 1.1. Định nghĩa thuật toán ....................................................................................................................2 1.2. Đặc trưng của thuật toán ..............................................................................................................2 2. Biểu diễn thuật toán ..................................................................................................................... 2 2.1. Mô tả các bước thực hiện .............................................................................................................2 2.2. Sử dụng sơ đồ (lưu đồ) giải thuật (flowchart)............................................................................3 3. Độ phức tạp thuật toán – Algorithm Complexity ..................................................................... 3 3.1. Các tiêu chí đánh giá thuật toán ..................................................................................................3 3.2. Đánh giá thời gian thực hiện thuật toán .....................................................................................4 3.3. Các định nghĩa hình thức về độ phức tạp thuật toán ...............................................................5 3.4. Các lớp thuật toán..........................................................................................................................6 4. Cấu trúc dữ liệu – Data structure ............................................................................................... 8 4.1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật...........................................................................8 4.2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu...................................................................................8 4.3. Các kiểu dữ liệu cơ bản của ngôn ngữ C ..................................................................................8 4.4. Các kiểu dữ liệu có cấu trúc .........................................................................................................8 4.5. Một số kiểu dữ liệu có cấu trúc cơ bản ......................................................................................8 5. Các chiến lược thiết kế thuật toán. ............................................................................................ 8 5.1. Chiến lược vét cạn (Brute force) .................................................................................................8 5.2. Chiến lược quay lui (Back tracking / try and error) ...................................................................9 5.3. Chia để trị (Divide and Conquer) ...............................................................................................12 5.4. Chiến lược tham lam (Greedy) ..................................................................................................12 5.5. Qui hoạch động (Dynamic Programming) ................................................................................13 6. Bài tập .......................................................................................................................................... 13CHƯƠNG 2: TÌM KIẾM (SEARCHING) ................................................................................ 14 1. Bài toán tìm kiếm ........................................................................................................................ 14 2. Tìm kiếm tuần tự (Sequential search)...................................................................................... 14 3. Tìm kiếm nhị phân (binary search)........................................................................................... 16 4. Bài tập .......................................................................................................................................... 18 -i-Bài giảng môn học: Cấu trúc Dữ liệu và Giải thuậtCHƯƠNG 3: SẮP XẾP (SORTING) ....................................................................................... 19 1. Bài toán sắp xếp ................................................................................................................ ...