Giáo trình môn học: Cấu trúc dữ liệu và giải thuật nghề - Quản trị mạng (Trình độ: Cao đẳng 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à giải thuật NGHỀ: QUẢN TRỊ MẠNG TRÌNH ĐỘ: CAO ĐẲNG NGHỀ ( Ban hành kèm theo Quyết định số: 120/QĐ­TCDN ngày 25 tháng 02 năm 2013 của Tổng cục trưởng Tổng cục dạy nghề) Hà Nội, năm 2013 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ể đượ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 mang tính 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. MÃ TÀI LIỆU: MH17 1 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ản của những người muốn tìm hiểu sâu về Công nghệ thông tin đặt biệt đối với việc lập trì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ải thuậ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ổi tiế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ông cụ lập trìnhhiệ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 trong má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ệu mộ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ặt chẽ 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ựa chọ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ích sâ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ựa Pascal để 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ất mong 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 25 tháng 02 năm 2013 Tham gia biên soạn 1. Chủ biên: Ths. Ngô Thị Thanh Trang 2. Ths.Nguyễn Văn Hưng 3. Trương Văn Hòa 2 MỤC LỤC ĐỀ MỤC TRANG LỜI GIỚI THIỆU................................................................................................3 MỤC LỤC.............................................................................................................2 MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT.......................................6 CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT....9 1.Khái niệm giải thuật và đánh giá độ phức tạp của giải thuật................9 1.1. Khái niệm giải thuật.....................................................................9 1.2. Ngôn ngữ diễn đạt giải thuật.....................................................10 1.3. Thiết kế giải thuật......................................................................14 1.4. Đánh giá giải thuật .....................................................................17 2.Các kiểu dữ liệu cơ bản.........................................................................20 3.Kiểu bản ghi, kiểu con trỏ......................................................................21 3.1. Kiểu bản ghi................................................................................21 3.2. Kiểu con trỏ.................................................................................22 Bài tập thực hành của học viên.................................................................22 4.Các kiểu dữ liệu trừu tượng ..................................................................22 5.Các cấu trúc lưu trữ.................................................................................23 5.1. Mảng............................................................................................23 5.2. Danh sách liên kết........................................................................26 Bài tập thực hành của học viên.................................................................28 6.Mối quan hệ giữa CTDL và giải thuật .................................................28 Bài tập thực hành của học viên.................................................................31 Gợi ý làm bài...............................................................................................31 CHƯƠNG 2: ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY........................................32 1.Khái niệm đệ quy .................................................................................32 2.Giải thuật đệ quy và chương trình đệ quy.............................................32 2.1. Giải thuật đệ qui.........................................................................33 2.2. Chương trình đệ qui....................................................................33 3.Các bài toán đệ quy căn bản...................................................................33 3.1. Bài toán tính n giai thừa...............................................................33 3.2. Bài toán dãy số FIBONACCI......................................................33 Bài tập thực hành của học viên.................................................................34 Gợi ý làm bài...............................................................................................35 3 CHƯƠNG 3: DANH SÁCH..............................................................................37 1.Danh sách và các phép toán cơ bản trên danh sách ................................37 1.1. Khái niệm danh dách...................................................................37 1.2. Các phép toán trên danh dách.......................................................37 2.Cài đặt danh sách theo cấu trúc mảng ...................................................38 2.1. Khởi tạo danh sách rỗng.............................................................39 2.2. Kiểm tra danh sách rỗng..............................................................39 2.3. Chèn phần tử vào danh sách.......................................................39 2.4. Xóa phần tử khỏi danh sách........................................................40 3.Cài đặt danh sách theo cấu trúc danh sách liên kết (đơn, kép).............41 3.1. Khởi tạo danh sách rỗng.............................................................43 3.2. Kiểm tra danh sách rỗng..............................................................43 3.3. Chèn phần tử vào danh sách........................................................43 3.4. Xóa phần tử khỏi danh sách........................................................44 3.5. Danh sách liên kết vòng...............................................................45 3.6. Danh sách liên kết đôi..................................................................46 4. Danh sách đặc biệt.................................................................................47 4.1. Ngăn xếp......................................................................................47 4.2. Hàng đợi.......................................................................................52 Bài tập thực hành của học viên.................................................................57 CHƯƠNG 4: CÁC PHƯƠNG PHÁP SẮP XẾP CƠ BẢN..............................59 1.Định nghĩa bài toán sắp xếp ...................................................................59 2. Phương pháp chọn (Selection sort)........................................................60 2.1.Giới thiệu phương pháp...............................................................60 2.2.Giải thuật......................................................................................60 2.3.Ví dụ minh họa.............................................................................61 3. Phương pháp chèn (Insertion sort)..........................................................61 3.1.Giới thiệu phương pháp...............................................................62 3.2.Giải thuật......................................................................................62 3.3.Ví dụ minh họa.............................................................................63 4. Phương pháp đổi chỗ (Interchange sort)................................................63 ... - tailieumienphi.vn