Giáo trình Cấu trúc dữ liệu và thuật giải (Nghề Lập trình máy tính) - Tổng cục dạy nghề

Giáo trình Cấu trúc dữ liệu và thuật giải cung cấp các khái niệm dữ liệu, giải thuật và mối quan hệ mật thiết giữa cấu trúc dữ liệu và giải thuật. Biết phân tích được các loại 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 tổ chức dữ liệu hợp lý, khoa học cho một chương trình từ đơn giản đến phức tạp. Biết áp dụng thuật toán hợp lý nhất đối với cấu trúc dữ liệu tương thích để giải quyết bài toán tối ưu nhất.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và thuật giải (Nghề Lập trình máy tính) - Tổng cục dạy nghề BỘ LAO ĐỘNG - THƯƠNG BINH VÀ XÃ HỘI TỔNG CỤC DẠY NGHỀ GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI Mã số : ITPRG 01 NGHỀ: LẬP TRÌNH MÁY TÍNH Trình độ Cao đẳng nghề NĂM 2012 Tuyên bố bản quyền : Tài liệu này thuộc loại sách giáo trình Cho nên các nguồn thông tin có thể được phé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 có ý đồ lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. Tổng Cục Dạy nghề sẽ làm mọi cách để bảo vệ bản quyền của mình. Tổng Cục Dạy Nghề cám ơn và hoan nghênh các thông tin giúp cho việc tu sửa và hoàn thiện tốt hơn tàI liệu này. Địa chỉ liên hệ: Dự án giáo dục kỹ thuật và nghề nghiệp Tiểu Ban Phát triển Chương trình Học liệu ……………………………………………… ................................................................ LỜI TỰA Để đáp ứng nhu cầu học tập của người học, chúng tôi đã tiến hành biên soạn giáo trình, bài giảng cho môn học cấu trúc dữ liệu. Cuốn sách này được biên dịch nhờ vào các nguồn tài liệu trên mạng, các nguồn tài liệu nước ngoài, đặc biệt là dựa trên cuốn sách Data Structures and Algorithms của Alfred V. Aho, John E. Hopcroft và Jeffrey D. Ullman do Addison-Wesley tái bản năm 1987. Đồng thời lồng ghép những kinh nghiệm giảng dạy cấu trúc dữ liệu và giải thuật của chúng tôi. Tài liệu này được biên soạn theo đề cương chi tiết môn học Cấu trúc dữ liệu và giải thuật của Tổng cục dạy nghề với mã ITPRG01. Mục tiêu của nó nhằm giúp các bạn sinh viên chuyên ngành có một tài liệu cô đọng dùng làm tài liệu học tập, nhưng chúng tôi cũng không loại trừ toàn bộ các đối tượng khác tham khảo. Chúng tôi hi vọng người đọc sẽ tìm thấy được những kiến thức bổ ích trong tài liệu này. Mặc dù đã rất cố gắng nhiều trong quá trình biên soạn giáo trình nhưng chắc chắn giáo trình sẽ còn nhiều thiếu sót và hạn chế. Rất mong nhận được sự đóng góp ý kiến quý báu của của những người đọc và người học để giáo trình ngày một hoàn thiện hơn. MỤC LỤC ĐỀ MỤC TRANG 1. LỜI TỰA ............................................................................................................... 3 2. MỤC LỤC ............................................................................................................. 4 3. GIỚI THIỆU VỀ MÔ ĐUN/MÔN HỌC ................................................................... 5 4. SƠ ĐỒ QUAN HỆ THEO TRÌNH TỰ HỌC NGHỀ ................................................ 6 5. CÁC HÌNH THỨC HỌC TẬP CHÍNH TRONG MÔ ĐUN/MÔN HỌC ..................... 7 6. YÊU CẦU VỀ ĐÁNH GIÁ HOÀN THÀNH MÔ ĐUN/MÔN HỌC ............................ 8 7. Bài 1:GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ................................... 9 8. Bài 2:CÁC KIỄU DỮ LIỆU CÓ CẤU TRÚC ĐƠN GIẢN ...................................... 28 9. Bài 3:CẤU TRÚC DỮ LIỆU ĐỘNG – DANH SÁCH............................................ 75 10. Bài 4:SẮP XẾP VÀ TÌM KIẾM ........................................................................... 138 11. Bài5:CẤU TRÚC DỮ LIỆU ĐỘNG – CÂY ......................................................... 174 12. THUẬT NGỮ CHUYÊN MÔN ............................................................................ 228 13. TÀI LIỆU THAM KHẢO ...................................................................................... 229 GIỚI THIỆU VỀ MÔ ĐUN/MÔN HỌC Vị trí, ý nghĩa, vai trò mô đun/môn học Môn học Lập trình cơ bản, một môn học chứa các kiến thức nền tảng cho việc lập trình có cấu trúc. Để phát huy tốt phương pháp lập trình có cấu trúc chúng ta tiếp tục nghiên cứu môn học Cấu trúc dữ liệu và giải thuật. Cấu trúc dữ liệu là một môn học bổ trợ rất nhiều cho các kiến thức lập trình, kiến thức logic giúp cho chúng ta rất nhiều các kiến thức để học tốt hơn hai môn học: Thiết kế hướng đối tượng; Lập trình nâng cao. Mục tiêu của mô đun/môn học Hiểu được các khái niệm dữ liệu, giải thuật và mối quan hệ mật thiết giữa cấu trúc dữ liệu và giải thuật. Biết phân tích được các loại 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 tổ chức dữ liệu hợp lý, khoa học cho một chương trình từ đơn giản đến phức tạp. Biết áp dụng thuật toán hợp lý nhất đối với cấu trúc dữ liệu tương thích để giải quyết bài toán tối ưu nhất. Biết áp dụng được các phương pháp sắp xếp, tìm kiếm từ đơn giản đến phức tạp với mức độ tương đối và biết dùng một 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. Mục tiêu thực hiện của mô đun/môn học - Nắm được cách thức tổ chức dữ liệu đề giải quyết bài toán cơ bản. - Nắm được các giải thuật cơ sở để áp dụng thiết kế các thuật toán theo phương pháp top-down và phương pháp chia để trị. - Phân tích được giải thuật về các mặt thời gian, bộ nhớ, tốc độ của chương trình. - Tổ chức, thiết kế được các kiểu dữ liệu có cấu trúc đơn giản, cấu trúc dữ liệu động để giải quyết các bài toán đơn giản và vừa. - Áp dụng được các phương pháp toán học (giải thuật) phù hợp cho cấu trúc dữ liệu đó. - Kết hợp với ngôn ngữ lập trình, viết chương trình trên cấu trúc dữ liệu và áp dụng thuật toán cho các bài toán cụ thể trên máy tính. Nội dung chính của mô đun/môn I. GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT II. CÁC KIỂU DỮ LIỆU CÓ CẤU TRÚC ĐƠN GIẢN III. CẤU TRÚC DỮ LIỆU ĐỘNG – DANH SÁCH IV. SẮP XẾP VÀ TÌM KIẾM V. CẤU TRÚC DỮ LIỆU ĐỘNG – CÂY. Sơ đồ quan hệ theo trình tự học nghề Hệ thống Giao diện Lập trình Lập trình máy tính người máy nâng cao Web Lập trình ...