Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành/Nghề: Công nghệ thông tin – Trình độ: Cao đẳng) - Trường CĐ Kinh tế - Kỹ thuật Vinatex TP. HCM (2019)

Giáo trình Cấu trúc dữ liệu và giải thuật được biên soạn gồm có 6 chương với những nội dung chính sau: Chương I: Tổng quan về cấu trúc dữ liệu và giải thuật; Chương II: Đệ quy và giải thuật đệ quy; Chương III: Tìm kiếm; Chương IV: Các phương pháp sắp xếp cơ bản; Chương V: Danh sách; Chương VI: Cây nhị phân. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiế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 (Ngành/Nghề: Công nghệ thông tin – Trình độ: Cao đẳng) - Trường CĐ Kinh tế - Kỹ thuật Vinatex TP. HCM (2019) TẬP ĐOÀN DỆT MAY VIỆT NAM TRƢỜNG CAO ĐẲNG KINH TẾ - KỸ THUẬT VINATEX TP.HCM  Giáo Trình 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 theo Quyết định số: ngày tháng năm của trường Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM) TP.HỒ CHÍ MINH, THÁNG 03 NĂM 2019 Tuyên bố bản quyền Giáo trình này sử dụng làm tài liệu giảng dạy lƣu hành nội bộ trong trƣờng Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM không sử dụng và không cho phép bất kỳ cá nhân hay tổ chức nào sử dụng giáo trình này với mục đích kinh doanh. Mọi trích dẫn, sử dụng giáo trình này với mục đích khác hay ở nơi khác đều phải đƣợc sự đồng ý bằng văn bản của Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM LỜI NÓI ĐẦU Tài liệu này dùng cho học sinh hệ Trung cấp và sinh viên hệ Cao đẳng ngành công nghệ thông tin học tập và nghiêm cứu về “Cấu trúc dữ liệu và giải thuật” Tài liệu gồm các nội dung chisng sau: Chƣơng 1: Tổng quan về cấu trúc dữ liệu và giải thuật, các tiêu chuẩn danh gia cấu trúc dữ liệu ,phản ánh đúng thực tếp, phù hợp với các thao tác trên đó, tiết kiệm tài nguyên hệ thống. Kiểu dữ liệu, kiểu dữ liệu cơ bản, các kiểu dữ liệu có cấu trúc, kiểu chuỗi ký tự, kiểu mảng, kiểu union, kiểu mẫu tin (cấu trúc), kiểu con trỏ, kiểu tập tin, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Chƣơng 2: ệ quy và giải thuật đệ quy, khái niệm đệ quy, thuật toán đệ quy và các chƣơng trình đệ quy, giải thuật đệ quy, các chƣơng trình đệ quy. Các bài toán đệ quy căn bản, hàm tính giai thừa, dãy số fibonacci. Chƣơng 3: Tìm kiếm, tìm kiếm tuyến tính,tìm kiếm nhị phân, giải thuật, cài đặt, đánh giá giải. Chƣơng 4: Các phƣơng pháp sắp xếp cơ bản, định nghĩa bài toán sắp xếp, phƣơng pháp chọn (Selection Sort), chèn (Insertion Sort), đổi chỗ (Interchange Sort), nổi bọt (Bubble Sort), sắp xếp nhanh Quick Sort, giải thuật phân hoạch dãy al, al+1, ., ar thành 2 dãy con, giải thuật phân hoạch dãy sắp xếp dãy al, al+1, ., ar, cài đánh giá giải thuật Chƣơng 5: Danh sách, danh sách liên kết (Xâu liên kết), định nghiã, biểu diễn Xâu liên kết, danh sách liên kết đơn (Xâu đơn), khai báo xâu liên kết đơn, các thao tác trên xâu liên kết đơn, loại bỏ một phần tủ trong xâu, duyệt xâu, sắp thứ tự Xâu, thuật Toán QuickSort, ngăn xếp – stack,cài đặt ngăn xếp bằng xâu đơn, cài đặt ngăn xếp bằng mảng và các thao tác, ứng dụng ngăn xếp trong xử lý biểu thức hậu tố. Hàng đợi – Queue, khái niệm, cài đặt hàng đợi bằng xâu liên kết, cài đặt hàng đợi bằng mảng. Chƣơng 6: Cây nhị phân, định nghĩa và các khái niệm cơ bản, định nghĩa cây, các khái niệm khác, cây nhị phân, định nghĩa, vài tính chất của cây nhị phân, biểu diễn cây nhị phân, duyệt cây nhị phân, định nghĩa, các thuật toán duyệt cây nhị phân, cài đặt thuật toán duyệt qua cây nhị phân LNR, cài đặt cây nhị phân. Cây tìm kiếm nhị phân (Binary Search Trees), định nghĩa, cài đặt cây tìm kiếm nhị phân, tìm kiếm một phần tử trên cây BST, chèn một phần tử vào cây BST, xây dựng cây BST, phƣơng pháp sắp xếp bằng cây BST, xóa một phần tử khỏi cây BST, hủy cây nhị phân. Tài liệu không chỉ đề cập đến những vấn đề cơ sở lý luận mà còn trình bày một số kỹ năng, kinh nghiệm cần thiết để thiết kế và cài đặt các mạng máy tính. Hy vọng sẽ có ích cho các bạn học sinh sinh viên và những ngƣời muốn xây dựng các hệ thống tin học ứng dụng phục vụ cho sản xuất, quản lý trong các doanh nghiệp. Có thể còn nhiều thiếu sót trong trình bày và biên soạn do khả năng, trình độ, nhƣng ngƣời biên soạn mạnh dạn giới thiệu tài liệu này và mong nhận đƣợc sự góp ý của bạn đọc. CHƢƠNG TRÌNH MÔN HỌC ....................................................................................................... 7 I. Vị trí, tính chất môn học: ...................................................................................................... 7 II. Mục tiêu môn học: .............................................................................................................. 7 III. Nội dung môn học: ............................................................................................................ 7 Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ................................... 8 I. CÁC TIÊU CHUẨN DANH GIA CẤU TRÚC DỮ LIỆU ...................................................... 8 1. Phản ánh đúng thực tế :........................................................................................................ 8 2. Phù hợp với các thao tác trên đó: ......................................................................................... 8 3. Tiết kiệm tài nguyên hệ thống: ............................................................................................ 9 II. KIỂU DỮ LIỆU ...................................................................................................................... 9 III. KIỂU DỮ LIỆU CƠ BẢN ................................................................................................... 10 IV. CÁC KIỂU DỮ LIỆU CÓ CẤU TRÚC .............................................................................. 11 1. Kiểu chuỗi ký tự ................................................................................................................ 11 2. Kiểu mảng .......................................................................................................................... 12 3. Kiểu union.......................................................................................................................... 13 4. Kiểu mẫ ...