ỦY BAN NHÂN DÂN TP. HỒ CHÍ MINH TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THỦ ĐỨC KHOA CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH HỌC PHẦN: CẤU TRÚC DỮ LIỆU & GIẢI THUẬT NGÀNH/NGHỀ: CÔNG NGHỆ THÔNG TIN TRÌNH ĐỘ: CAO ĐẲNG Ban hành kèm theo Quyết định số:. Hồ Chí Minh, năm 2018 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.
GIỚI THIỆU Giáo trình này được biên soạn dựa theo đề cương học phần “Cấu trúc dữ liệu & Giải thuật” mới xây dựng theo mô hình CDIO của Khoa Công nghệ thông tin Trường Cao đẳng Công nghệ Thủ Đức. Mặc dù tôi đã rất cố gắng, song chắc chắn sẽ không tránh khỏi những sai sót về nội dung lẫn hình thức, rất mong nhận được sự góp ý chân thành từ các quý thầy cô và các em sinh viên để giáo trình ngày càng hoàn thiện hơn. Hồ Chí Minh, ngày 3 tháng 4 năm 2018 Chủ biên Nguyễn Thị Vân MỤC LỤC 1.1 | BIẾN, KIỂU DỮ LIỆU, CẤU TRÚC DỮ LIỆU .2 | Kiểu dữ liệu (Data types) .3 | Cấu trúc dữ liệu .2 | KIỂU DỮ LIỆU TRỪU TƯỢNG (ADTS) .3 | KHÁI NIỆM GIẢI THUẬT VÀ PHÂN TÍCH GIẢI THUẬT. MỘT SỐ GIẢI THUẬT TÌM KIẾM .1 | BÀI TOÁN TÌM KIẾM .2 | TÌM KIẾM TUẦN TỰ .3 | TÌM KIẾM NHỊ PHÂN.
MỘT SỐ THUẬT TOÁN SẮP XẾP .1 | BÀI TOÁN SẮP XẾP .2 | SẮP XẾP LỰA CHỌN (SELECTION SORT) .3 | SẮP XẾP CHÈN (INSERTION SORT) .4 | SẮP XẾP ĐỔI CHỖ TRỰC TIẾP (INTERCHANGE SORT) .5 | SẮP XẾP NỔI BỌT (BUBBLE SORT).6 | SẮP XẾP NHANH (QUICK SORT) .7 | SẮP XẾP TRỘN (MERGE SORT) .8 | SẮP XẾP VUN ĐỐNG (HEAP SORT). KIỂU DỮ LIỆU DANH SÁCH .1 | KHÁI NIỆM DANH SÁCH .2 | PHÂN LOẠI DANH SÁCH .3 | LINKED LISTS ADT .4 | TỔNG QUAN VỀ SÁCH LIÊN KẾT (LINKED LIST) VÀ MẢNG.5 | CÀI ĐẶT DANH SÁCH ĐẶC (MẢNG) .1 | Khai báo cấu trúc dữ liệu .6 | CÀI ĐẶT DANH SÁCH LIÊN KẾT ĐƠN .1 | Khai báo cấu trúc dữ liệu .2 | Cài đặt danh sách móc nối .7 | VẤN ĐỀ VÀ GIẢI PHÁP. NGĂN XẾP, HÀNG ĐỢI.3 | Ứng dụng stack.4 | Cài đặt stack bằng mảng .5 | Cài đặt stack bằng linked list .6 | Vấn đề và giải pháp .3 | Ứng dụng queue .4 | Cài đặt queue bằng mảng .5 | Cài đặt queue bằng linked list .6 | Vấn đề và giải pháp .3 | GIỚI THIỆU VỀ CÁC STL STACK, STL QUEUE. CẤU TRÚC CÂY .1 | KHÁI NIỆM CÂY .2 | CÂY NHỊ PHÂN .2 | Tính chá t củ a cay nhị phan .3 | Biể u diễ n cay nhị phan .4 | Duyệ t cay nhị phan .5 | Biểu diễn cây tổng quát bằng cây nhị phân .6 | Một cách khác để biểu diễn cây nhị phân .3 | CÂY NHỊ PHÂN TÌM KIẾM .2 | Các thao tác trên cây nhị phân tìm kiếm .4 | CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG .2 | Lịch sử cây cân nhị phân tìm kiếm bằng (AVL Tree) .3 | Cấu trúc dữ liệu cho cây AVL .4 | Cân bằng lại cây AVL.
139 TÀI LIỆU THAM KHẢO. 146 GIÁO TRÌNH HỌC PHẦN Tên học phần: Cấu trúc dữ liệu & Giải thuật Mã học phần: CSC106200 Vị trí, tính chất, ý nghĩa và vai trò của học phần: - Vị trí: Đây là học phần thuộc khối kiến thức cơ sở chuyên ngành. - Tích chất, ý nghĩa và vai trò của học phần: Đây là học phần cơ sở chuyên ngành giúp sinh viên ngành Công nghệ thông tin và sinh viên ngành Truyền thông & Mạng máy tính có khả năng sử dụng một số cấu trúc dữ liệu và giải thuật cơ bản để giải một số bài toán vừa và nhỏ trên máy tính. Thông qua các hoạt động học tập, sinh viên còn có thể rèn luyện khả năng tư duy lập trình, hoàn thiện dần tính chủ động, tích cực, khả năng tự học, kỹ năng thuyết trình và thói quen tuân thủ các quy định làm việc trong môi trường chuyên nghiệp.
Mục tiêu của học phần: - Kiến thức: Phân biệt các loại cấu trúc dữ liệu cơ bản; Trình bày cấu trúc dữ liệu của cấu trúc cây và một số thao tác trên cây; Ước lượng thời gian thực hiện cho một số thuật toán đơn giản; - Kỹ năng: Cài đặt các cấu trúc dữ liệu và các thao tác cho kiểu dữ liệu danh sách (Mảng, Danh sách móc nối đơn), ngăn xếp, hàng đợi; Cài đặt một số giải thuật tìm kiếm và sắp xếp; Có khả năng trình bày vấn đề trước lớp rõ ràng, mạch lạc; - Năng lực tự chủ và trách nhiệm: Luôn viết code theo chuẩn; Thường xuyên chủ động tìm hiểu vấn đề; Luôn luôn chủ động làm bài tập về nhà, nộp bài đúng qui định. Nội dung của học phần: 1. GIỚI THIỆU Giới thiệu: Chương này giải thích tầm quan trọng của cấu trúc dữ liệu và giải thuật và tầm quan trọng của việc phân tích giải thuật khi giải quyết một số bài toán tin học vừa và nhỏ. Mục tiêu: - Nhận biết các loại cấu trúc dữ liệu cơ bản.
- Ước lượng thời gian thực hiện cho một số thuật toán đơn giản.1 | BIẾN, KIỂU DỮ LIỆU, CẤU TRÚC DỮ LIỆU 1.1 | Biến (Variables) Trước khi hiểu biến là gì, hãy liên hệ tới một biểu thức toán học rất quen thuộc: 𝑥 2 + 2𝑦 − 2 = 1 Chúng ta không cần lo lắng về cách sử dụng công thức này. Điều quan trọng là cần hiểu trong biểu thức này có hai tên (x và y) dùng để chứa giá trị (dữ liệu). Tức x và y là nơi để lưu trữ giá trị. Tương tự, trong lập trình khoa học máy tính chúng ta dùng biến (variables) để lưu trữ dữ liệu.2 | Kiểu dữ liệu (Data types) Trong biểu thức toán học đã được đề cập ở trên, hai biến x và y có thể chứa bất kỳ giá trị gì như số nguyên (10, 20), số thực (0.
Để giải được thì chúng ta cần biết loại giá trị mà x, y có thể nhận. Trong khoa học máy tính kiểu dữ liệu được dùng để phân loại dữ liệu. Một kiểu dữ liệu (data type) trong một ngôn ngữ lập trình là một tập hợp các giá trị nằm trong miền xác định trước. Một vài kiểu dữ liệu như: số nguyên (interger), số thực (floating point), kí tự (charactrer), chuỗi (string),.
Mỗi một loại dữ liệu khi được lưu trữ thì sẽ chiếm dung lượng bộ nhớ khác nhau phụ thuộc vào ngôn ngữ, trình biên dịch và hệ điều hành. Ví dụ số nguyên (interger) chiếm 2 bytes hoặc 4 bytes, kiểu kí tự chiếm 1 byte (kiểu char, lưu mã ASCII của ký tự) hoặc 2 byte (kiểu wchar_t, lưu trữ dựa trên bảng mã quốc tế UTF-16 – một dạng mã unicode),. Có hai loại kiểu dữ liệu: Kiểu dữ liệu cơ sở (System-defined data types or Primitive data types) Kiểu dữ liệu do người dùng tự định nghĩa (User-defined data types) Kiểu dữ liệu cơ sở 2 Một số kiểu dữ liệu cơ sở được cung cấp trong nhiều ngôn ngữ lập trình là int, float, char, double, bool,. Số lượng bit được cấp phát cho mỗi kiểu dữ liệu phụ thuộc vào ngôn ngữ, trình biên dịch và hệ điều hành.
Phụ thuộc vào kích thước của kiểu dữ liệu mà miền giá trị (domain) của biến sẽ thay đổi. Ví dụ kiểu int chiếm 2 bytes hoặc 4 bytes. Nếu chiếm 2 bytes (16 bits) thì miền giá trị của một biến của int từ -32,768 đến 32,767 (tức từ −215 đế𝑛 215 − 1). Nhưng nếu chiếm 4 bytes (32 bits) thì miền giá trị biến từ -2,147,483,648 đến 2,147,483,647 (tức từ −231 𝑡ớ𝑖 231 − 1).
Tương tự với một số kiểu dữ liệu khác. Kiểu dữ liệu do người dùng tự định nghĩa Nếu với những bài toán phức tạp, có những dữ liệu thực tế chúng ta cần lưu trữ vào máy tính nhưng kiểu dữ liệu cơ sở không đáp ứng đủ thì khi đó hầu hết các ngôn ngữ lập trình đều cho phép người dùng định nghĩa kiểu dữ liệu để đáp ứng nhu cầu lưu trữ những đối tượng phức tạp trên thực tế. Trong ngôn ngữ C/C++ thì để định nghĩa kiểu dữ liệu mới có thể dùng từ khóa struct. struct newType { int data1; float data2; .3 | Cấu trúc dữ liệu Cấu trúc dữ liệu (data structures) là cách lưu trữ và tổ chức dữ liệu trong máy tính sao cho dữ liệu được sử dụng một cách hiệu quả nhất.
Một số loại cấu trúc dữ liệu như arrays, files, linked lists, stacks, queues, trees, graphs,. 3 Phụ thuộc vào cách tổ chức của các phần tử mà cấu trúc dữ liệu được chia thành hai loại: Cấu trúc dữ liệu tuyến tính (linear data structures): Các phần tử được truy cập tuần tự. Ví dụ như Linked Lists, Stacks và Queues Cấu trúc dữ liệu phi tuyến tính (non- linear data structures): các phần tử được truy cập không theo trật tự tuyến tính. Ví dụ như Trees và graphs 1.2 | KIỂU DỮ LIỆU TRỪU TƯỢNG (ADTS) Trước khi tìm hiểu về kiểu dữ liệu trừu tượng thì cần hiểu rõ về một số khái niệm sau: Trừu tượng hóa (Abstraction): là quá trình tách biệt thiết kế chi tiết với cách sử dụng (tức người sử dụng không cần biết thiết kế chi tiết bên dưới nhưng vẫn có thể sử dụng dễ dàng).
Trừu tượng hóa chức năng (Function abstraction): là quá trình tách biệt cài đặt chi tiết các chức năng với cách sử dụng các chức năng đó. Trừu tượng hóa dữ liệu (Data abstraction): là quá trình tách biệt cài đặt chi tiết của cấu trúc dữ liệu với cách sử dụng cấu trúc dữ liệu đó (ví dụ người sử dụng dùng cấu trúc List để lưu trữ dữ liệu và không cần biết bên trong nó được lưu trữ bằng cách nào). Đối với kiểu dữ liệu cơ sở (int, float,.), mặc định đã được hệ thống hỗ trợ các thao tác ví dụ như +, -,.Nhưng đối với các kiểu dữ liệu do người dùng định nghĩa thì các thao tác trên những kiểu dữ liệu này không được cung cấp sẵn, vì vậy chúng cũng cần định nghĩa các thao tác. Nói tóm lại thì khi người dùng tự định nghĩa thêm một kiểu dữ liệu thì phải định nghĩa luôn cả tập các thao tác hợp lệ đi cùng với kiểu dữ liệu đó.
Vậy việc kết hợp cấu trúc dữ liệu cùng với các thao tác trên loại cấu trúc đó (tức là sự kết hợp data abstraction và function abstraction) tạo thành kiểu dữ liệu trừu tượng (Abtract Data Types – ADTs).