Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định

Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 1 cung cấp cho người học những kiến thức như: Cấu trúc dữ liệu và các vấn đề liên quan; Ngôn ngữ diễn đạt giải thuật. Mời các bạn cùng tham khảo để nắm chi tiết nội dung giáo trình!
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: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định MỤC LỤCMỤC LỤC ............................................................................................................. 1CHƢƠNG 1: MỞ ĐẦU........................................................................................ 4 1.1. Giải thuật ..................................................................................................... 4 1.1.1 Khái niệm giải thuật .............................................................................. 4 1.1.2. Các đặc trưng của giải thuật ................................................................. 4 1.2. Cấu trúc dữ liệu và các vấn đề liên quan .................................................... 5 1.2.1. Cấu trúc dữ liệu và giải thuật ............................................................... 5 1.2.2. Cấu trúc dữ liệu và ngôn ngữ lập trình ................................................ 5 1.3. Ngôn ngữ diễn đạt giải thuật ....................................................................... 6 1.3.1. Đặt vấn đề ............................................................................................ 6 1.3.2. Quy cách về cấu trúc chương trình ...................................................... 7 1.3.3. Ký tự và biểu thức ................................................................................ 7 1.3.4. Các câu lệnh ......................................................................................... 7CHƢƠNG 2 : THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT .......................... 11 2.1. Từ bài toán đến chương trình .................................................................... 11 2.1.1 Mô - đun hoá và việc giải quyết bài toán ............................................ 11 2.1.2. Phương pháp tinh chỉnh từng bước .................................................... 13 2.2. Phân tích giải thuật .................................................................................... 21 2.2.1. Đặt vấn đề .......................................................................................... 24 2.2.2. Phân tích thời gian thực hiện giải thuật ............................................. 24 2.3. Bài tập ....................................................................................................... 26CHƢƠNG 3 : ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY ..................................... 35 3.1. Khái niệm về đệ quy ................................................................................. 35 3.2. Giải thuật đệ quy và chương trình con đệ quy .......................................... 35 3.3. Thiết kế giải thuật đệ quy .......................................................................... 37 3.3.1. Hàm N ! .............................................................................................. 37 3.3.2. Bài toán Tháp Hà Nội ........................................................................ 38 3.3.3. Bài toán 8 quân hậu và giải thuật quay lui ......................................... 40 3.4. Hiệu lực của đệ quy ................................................................................... 44 3.5. Đệ quy và quy nạp toán học ...................................................................... 45 3.6. Bài tập ....................................................................................................... 48CHƢƠNG 4: MẢNG VÀ DANH SÁCH .......................................................... 50 4.1. Các khái niệm ............................................................................................ 50 4.2. Cấu trúc lưu trữ của mảng ......................................................................... 51 4.3. Lưu trữ kế tiếp của danh sách tuyến tính .................................................. 54 4.4. Ngăn xếp (Stack) ....................................................................................... 55 4.4.1. Định nghĩa .......................................................................................... 55 4.4.2. Lưu trữ Stack kế tiếp .......................................................................... 55 4.4.3. Các giải thuật PUSH, POP ................................................................. 53 4.4.4. Ứng dụng của Stack ........................................................................... 58 4.4.5. Stack và việc cài đặt thủ tục đệ quy ................................................... 63 4.5. Hàng đợi (Queue) ...................................................................................... 66 4.5.1. Định nghĩa .......................................................................................... 66 4.5.2. Lưu trữ Queue kế tiếp ........................................................................ 66 ...