Giáo trình Cấu trúc dữ liệu và giải thuật - Nghề: Công nghệ thông tin (Cao đẳng) - CĐ Kỹ Thuật Công Nghệ Bà Rịa-Vũng Tàu

(NB) Giáo trình Cấu trúc dữ liệu và giải thuật nhằm cung cấp cho sinh viên các thuật toán tổng quát, danh sách liên kết, và các giải thuật sắp xếp, tìm kiếm. Từ đó sinh viên sẽ từng bước cải tiến thuật toán để xây dựng được những chương trình hiệu quả và có tính ứng dụng cao. Mục đích của giáo trình là trang bị cho học viên những kiến thức và kỹ năng phân tích xây dựng được thuật toán kết hợp với giải thuậ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ề: Công nghệ thông tin (Cao đẳng) - CĐ Kỹ Thuật Công Nghệ Bà Rịa-Vũng Tàu ỦY BAN NHÂN DÂN TỈNH BR – VT TRƯỜNG CAO ĐẲNG NGHỀ GIÁO TRÌNH MÔ ĐUN CẤU TRÚC DỮ LIỆU VÀ GIẢI  THUẬT NGHỀ CÔNG NGHỆ THÔNG TIN TRÌNH ĐỘ CAO ĐẲNG  Ban hành kèm theo Quyết định số: 01/QĐ­CĐN   ngày 04 tháng 01 năm 2016   của Hiệu trưởng trường Cao đẳng nghề tỉnh Bà Rịa – Vũng Tàu Bà Rịa – Vũng Tàu, năm 2016 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. LỜI GIỚI THIỆU Giáo trình cấu trúc dữ  liệu và giải thuật dùng cho học sinh hệ  Cao   Đẳng và Trung cấp của nghề lập trình máy tính và hệ cao đẳng chuyên ngành  công nghệ  thông tin  ứng dụng phần mềm trong trường Cao đẳng nghề  Tỉnh  BR – VT. Nhằm cung cấp cho sinh viên các thuật toán tổng quát, danh sách  liên kết, và các giải thuật sắp xếp, tìm kiếm. Từ  đó sinh viên sẽ  từng bước  cải tiến thuật toán để xây dựng được những chương trình hiệu quả và có tính   ứng dụng cao. Mục đích của giáo trình là trang bị  cho học viên những kiến  thức và kỹ năng phân tích  xây dựng được thuật toán kết hợp với giải thuật Để có thể nắm bắt các kiến thức học sinh cần  được trang bị các kiến  thức về  môn lập trình căn bản. Ngôn ngữ  lập trình được chọn để  minh họa   các kiến thức trên là Dev C++.  Trong qua trình biên soạn giáo trình, chắn chắn rằng trong giáo trình sẽ  còn nhiều khiếm khuyết, tác giả  mong muốn nhận được các ý kiến quí báu  đóng góp của đồng nghiệp cũng như  bạn đọc để  giáo trình này có thể  hoàn  thiện hơn nữa về mặt nội dung cũng như hình thức trong lần tái bản sau. Bà Rịa – Vũng Tàu, ngày 02 tháng 01 năm 2016                                                       Biên soạn Nguyễn Thị Mai MỤC LỤC        TRANG CHƯƠNG TRÌNH MÔ ĐUN 8 BÀI 1 GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 10 1. Mối liên hệ giải thuật và cấu trúc dữ liệu. 10 1.1. Giải thuật 10 1.2. Dữ liệu 10 1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật 11 2. Kiểu dữ liệu, mô hình dữ liệu, kiểu dữ liệu trừu tượng 11 2.1.Khái niệm về kiểu dữ liệu 11 2.2. Mô hình kiểu dữ liệu 12 2.3. Kiểu dữ liệu trừu tượng 13 3. Thiết kế và phân tích giải thuật 13 3.1. Thiết kế thuật toán. 13 3.2. Phân tích tính đúng đắn của giải thuật 13 3.3. Phân tích tính đơn giản 14 4. Một số ví dụ về thiết kế và phân tích giải thuật 14 BÀI 2 LÀM VIỆC VỚI CON TRỎ 17 1. Biến con trỏ 17 1.1. Khái niệm con trỏ ( pointer ) 17 1.3. Gán địa chỉ của biến cho biến con trỏ 18 1.4. Cấp phát vùng nhớ cho biến con trỏ 19 1.5. Giải phóng vùng nhớ cho biến con trỏ 19 1.6. Một số phép toán trên con trỏ 20 2. Con trỏ và mảng một chiều 21 3. Con trỏ và mảng nhiều chiều 22 BÀI 3 LÀM VIỆC VỚI KIỂU CẤU TRÚC 25 1. Khái niệm cấu trúc 25 2. Khai báo kiểu cấu trúc. 25 3. Truy nhập đến các thành phần trong biến cấu trúc 28 4. Nhập dữ liệu cho biến cấu trúc 28 BÀI 4 LÀM VIỆC VỚI KIỂU TẬP TIN 32 1. Khái niệm về tập tin 32 2. Các kiểu vào ra với tệp: 33 2.1. Khai báo biến tập tin 33 2.2. Mở tập tin 34 2.3. Đóng tập tin 35 2.4. Kiểm tra đến cuối tập tin hay chưa? 35 2.5. Di chuyển con trỏ tập tin về đầu tập tin - Hàm rewind() 36 3. Các thao tác trên tệp: 36 3.1. Ghi dữ liệu lên tập tin văn bản 36 3.2. Đọc dữ liệu từ tập tin văn bản 37 BÀI 5 THÊM PHẦN TỬ TRONG DANH SÁCH ĐẶC 41 1. Định nghĩa 41 2. Khởi tạo danh sách 41 3. Thêm một phần tử vào danh sách 42 3.1.Thêm vào đầu danh sách: 42 3.2.Thêm vào cuối danh sách: 42 3.3. Thêm vào vị trí bất kỳ trong danh sách: 42 BÀI 6 XÓA PHẦN TỬ TRONG DANH SÁCH ĐẶC 44 1. Xóa phần tử đầu 44 2. Xóa phần tử cuối 45 3. Xóa phần tử tại vị trí bất kỳ trong danh sách: 45 BÀI 7 LÀM VIỆC VỚI DANH SÁCH LIÊN KẾT 46 1. Định nghĩa: 46 2. Khai báo một nút 47 3. Khai báo một danh sách 47 4. Khởi tạo một nút mới 47 5. Khởi tạo một danh sách 48 6. Nhập một danh sách 48 7. Xuất một danh sách 49 BÀI 8 CHÈN PHẦN TỬ TRONG DANH SÁCH LIÊN KẾT 50 1. Chèn một nút vào đầu danh sách 50 2. Chèn một nút vào cuối danh sách 51 3. Chèn một nút vào vị trí bất kỳ 51 BÀI 9 XÓA PHẦN TỬ TRONG DANH SÁCH LIÊN KẾT 53 1. Xóa nút đầu danh sách 53 2. Xóa nút cuối danh sách 53 3. Hủy danh sách 54 BÀI 10 LÀM VIỆC VỚI NGĂN XẾP 56 1.4. Lấy một phần tử ra khỏi ngăn xếp. 58 1.5. Thêm một phần tử vào ngăn xếp. 58 2.3. Lấy một phần tử ra khỏi ngăn xếp. 59 2.4. Thêm một phần tử vào ngăn xếp. 60 2.5. Xóa phần tử ở ngăn xếp 60 BÀI 11 LÀM VIỆC VỚI HÀNG ĐỢI(QUEUE) 62 1. Biểu diễn hàng đợi dùng mảng: 63 2.4. Lấy phần tử ở ở đầu Queue 67 BÀI 12 SỬ DỤNG CÁC PHƯƠNG PHÁP SẮP XẾP 70 1. Định nghĩa bài toán sắp xếp: 70 2.3. Giải thuật: 71 3. Phương pháp sắp xếp nổi bọt 73 3.3. Giải thuật: 74 4. Phương pháp đổi chỗ trực tiếp 74 4.3. Giải thuật: 75 5. Phương pháp chèn ...