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 (2021)

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 (2021) TẬP ĐOÀN DỆT MAY VIỆT NAM TRƢỜNG CAO ĐẲNG CÔNG NGHỆ THÀNH PHỐ HỒ CHÍ MINH  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 Công nghệ Tp.HCM) TP.HỒ CHÍ MINH, THÁNG 07 NĂM 2021 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 Công nghệ Tp.HCM Cao đẳng Công nghệ 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 Công nghệ 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. Mục lục MỤC LỤC Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ............. 01 I. Các tiêu chuẩn danh gia cấu trúc dữ liệu ............................................................... 01 1. Phản ánh đúng thực tế. ......................................................................................... 01 2. Phù hợp với các thao tác trên đó. .......................................................................... 01 3. Tiết kiệm tài nguyên hệ thống. .............................................................................. 02 II. Kiểu dữ liệu .......................................................................................................... 02 III. Kiểu dữ liệu cơ bản ............................................................................................. 03 IV. Các kiểu dữ liệu có cấu trúc ................................................................................ 04 1. Kiểu chuỗi ký tự .................................................................................................... 04 2. Kiểu mảng ............................................................................................................. 05 3. Kiểu Union ............................................................................................................ 06 4. Kiểu mẫu tin (cấu trúc) ......................................................................................... 07 5. Kiểu con trỏ ........................................................................................................... 12 6. Kiểu tập tin ............................................................................................................ 26 7. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật .................................................... 37 Bài tập ....................................................................................................................... 38 Chương 2: Ệ QUY V GIẢI THUẬT Ệ QUY .................................................. 39 I. Khái niệm đệ quy ................................ ...