Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Lập trình viên máy tính - Cao đẳng) - Trường CĐ Nghề Kỹ thuật Công nghệ

(NB) Giáo trình Cấu trúc dữ liệu và giải thuật cung cấp cho sinh viên các kiến thức cơ bản về cấu trúc dữ liệu và giải thuật để làm nền tản cho việc lập trình giải quyết các vấn đề cần thiế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à giải thuật (Nghề: Lập trình viên máy tính - Cao đẳng) - Trường CĐ Nghề Kỹ thuật Công nghệ BỘ LAO ĐỘNG -THƯƠNG BINH VÀ XÃ HỘI TRƯỜNG CAO ĐẲNG NGHỀ KỸ THUẬT CÔNG NGHỆ -----š› & š›----- GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGHỀ: LẬP TRÌNH VIÊN MÁY TÍNH TRÌNH ĐỘ: CAO ĐẲNGBan hành kèm theo Quyết định số: 13A/QĐ-CĐNKTCN ngày 10 tháng 01 năm 2019 của Hiệu trưởng Trường Cao đẳng nghề Kỹ thuật Công nghệ Hà Nội, năm 2021 (Lưu hành nội bộ) 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 kinh doanhthiếu lành mạnh sẽ bị nghiêm cấm. MÃ TÀI LIỆU: MĐLTV 10 LỜI GIỚI THIỆU Kiến thức môn học Cấu trúc dữ liệu và giải thuật là một trong những nền tản cơ bảncủa những người muốn tìm hiểu sâu về Công nghệ thông tin đặc biệt đối với việc lậptrình để giải quyết các bài toán trên máy tính điện tử. Các cấu trúc dữ liệu và các giảithuật được xem như là 2 yếu tố quan trọng nhất trong lập trình, đúng như câu nói nổitiếng của Niklaus Wirth: Chương trình = Cấu trúc dữ liệu + Giải thuật (Programs =Data Structures + Algorithms). Nắm vững các cấu trúc dữ liệu và các giải thuật là cơ sởđể sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng các côngcụ lập trình hiện đại. Cấu trúc dữ liệu có thể được xem như là 1 phương pháp lưu trữ dữ liệu trongmáy tính nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử dụng các dữ liệumột cách hiệu quả thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do vậy,cấu trúc dữ liệu và giải thuật là 2 yếu tố không thể tách rời và có những liên quan chặtchẽ với nhau. Việc lựa chọn một cấu trúc dữ liệu có thể sẽ ảnh hưởng lớn tới việc lựachọn áp dụng giải thuật nào. Về nguyên tắc, các cấu trúc dữ liệu và các giải thuật có thể được biểu diễn và càiđặt bằng bất cứ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để có được các phân tíchsâu sắc hơn và mô phạm, có kết quả thực tế hơn, chúng tôi đã sử dụng ngôn ngữ tựaPascal để minh hoạ cho các cấu trúc dữ liệu và thuật toán. Mặc dầu có rất nhiều cố gắng, nhưng không tránh khỏi những khiếm khuyết, rấtmong nhận được sự đóng góp ý kiến của độc giả để giáo trình được hoàn thiện hơn. Hà Nội, ngày 23 tháng 04 năm 2021 Tham gia biên soạn 1. Chủ biên Nguyễn Thị Kim Dung 2. Tập thể Giảng viên Khoa CNTTMọi thông tin đóng góp chia sẻ xin gửi về hòm thư kimdunghd2009@gmail.com, hoặc liên hệ số điện thoại 0977881209. MỤC LỤCCHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ............... 91.Khái niệm giải thuật và đánh giá độ phức tạp của giải thuật ...................................... 91.1. Khái niệm giải thuật .............................................................................................. 91.2. Ngôn ngữ diễn đạt giải thuật ................................................................................. 91.3. Thiết kế giải thuật ............................................................................................... 131.4. Đánh giá giải thuật .............................................................................................. 152.Các kiểu dữ liệu cơ bản........................................................................................... 173.Kiểu bản ghi, kiểu con trỏ ....................................................................................... 173.1. Kiểu bản ghi ....................................................................................................... 183.2. Kiểu con trỏ ........................................................................................................ 184.Các kiểu dữ liệu trừu tượng..................................................................................... 185.Mối quan hệ giữa CTDL và giải thuật ..................................................................... 19Bài tập thực hành ....................................................................................................... 21CHƯƠNG 2: ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY ................................................. 221.Khái niệm đệ quy .................................................................................................... 222.Giải thuật đệ quy và chương trình đệ quy ................................................................ 222.1. Giải thuật đệ qui ............................ ...