Ủ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 2021 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ù đã rất cố gắng, song chắc chắn sẽ không tránh khỏi những thiếu 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 30 tháng 12 năm 2021 Chủ biên Phan Thị Trinh 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). 2 Cấu trúc dữ liệu. 4 KIỂU DỮ LIỆU TRỪU TƯỢNG (ADTS). 5 KHÁI NIỆM GIẢI THUẬT VÀ PHÂN TÍCH GIẢI THUẬT.
6 Khái niệm giải thuật. 6 Phân tích giải thuật. MỘT SỐ GIẢI THUẬT TÌM KIẾM. 16 BÀI TOÁN TÌM KIẾM.
17 Bài toán tìm kiếm. 17 TÌM KIẾM TUẦN TỰ (SEQUENCE SEARCH). 17 TÌM KIẾM NHỊ PHÂN (Binary search). MỘT SỐ GIẢI THUẬT SẮP XẾP.
25 BÀI TOÁN SẮP XẾP. KIỂU DỮ LIỆU DANH SÁCH. 54 KHÁI NIỆM DANH SÁCH. 55 PHÂN LOẠI DANH SÁCH.
55 LINKED LISTS ADT. 57 TỔNG QUAN VỀ SÁCH LIÊN KẾT MÓC NỐI (LINKED LIST) VÀ MẢNG. 57 CÀI ĐẶT DANH SÁCH ĐẶC (MẢNG). 59 Khai báo cấu trúc dữ liệu.
61 CÀI ĐẶT DANH SÁCH LIÊN KẾT ĐƠN. 64 Khai báo cấu trúc dữ liệu. 66 VẤN ĐỀ VÀ GIẢI PHÁP. 83 GIỚI THIỆU VỀ CLASS ARRAYLIST, LIST<T> VÀ LINKEDLIST<T> TRONG.
85 ArrayList và List<T>. NGĂN XẾP, HÀNG ĐỢI. 93 Trường hợp sử dụng Stack. 94 Ứng dụng stack.
94 Cài đặt stack bằng mảng. 95 Cài đặt stack bằng linked list. 98 Vấn đề và giải pháp. 102 Class Stack và Stack<T>.
109 Trường hợp sử dụng Queue. 110 Ứng dụng queue. 110 Cài đặt queue bằng mảng. 111 Cài đặt queue bằng linked list.
117 Vấn đề và giải pháp. 121 Class Queue và Queue<T>. CẤU TRÚC CÂY. 127 KHÁI NIỆM CÂY.
128 CÂY NHỊ PHÂN. 130 Tính chấ t củ a cây nhị phân. 131 Một số thao tác trên cây nhị phân. 131 Biể u diễ n cây nhị phân.
131 Duyệ t cây nhị phân. 133 Biểu diễn cây tổng quát bằng cây nhị phân. 135 CÂY NHỊ PHÂN TÌM KIẾM. 136 Các thao tác trên cây nhị phân tìm kiếm.
137 CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG. 145 Lịch sử cây cân nhị phân tìm kiếm bằng (AVL Tree). 145 Cấu trúc dữ liệu cho cây AVL. 145 Cân bằng lại cây AVL.
TÀI LIỆU THAM KHẢO. 153 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: CSC106330 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ính 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 quy đị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 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. Kiểu dữ liệu (Data types) 1.1 | Khái niệm Dữ liệu cần lưu trữ vào máy tính có rất nhiều loại như số, chữ, hình ảnh, âm thanh,…Tính đa dạng của dữ liệu đòi hỏi phải tổ chức và phân phối bộ nhớ thích hợp để lưu trữ, xử lý tốt các dữ liệu. Các dữ liệu được chia thành từng nhóm riêng trên đó xây dựng một số phép toán, tạo nên các kiểu dữ liệu khác nhau. Mỗi kiểu dữ liệu là một tập hợp các giá trị.
Kiểu dữ liệu gồm có 2 thành phần: • Miền giá trị của kiểu dữ liệu • Các toán tử được thực hiện trên giá trị này. 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. Các kiểu dữ liệu cơ bản của ngôn ngữ lập trình như: kiểu số nguyên (interger), kiểu số thực (floating point), kiểu kí tự (charactrer), kiểu chuỗi (string), kiểu luận lý (Boolean), kiểu cấu trúc (struct), kiểu lớp (class), kiểu con trỏ (pointer).
Tùy vào từng kiểu dữ liệu mà các toán tử có thể thực thực hiện trên các giá trị là khác nhau. Ví dụ không thể thực hiện các phép toán số học như cộng, trừ nhân, chia trên dữ liệu kiểu chuỗi, phép modulo (phép chia lấy số dư) không thể thực hiện trên kiểu số thực. 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ữ lập trình, 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 1byte (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), … 1.2 | Phân loại 2 Có hai loại kiểu dữ liệu: • Built-in data type: là kiểu dữ liệu cơ sở, do ngôn ngữ lập trình cung cấp.
• User-defined data type: là Kiểu dữ liệu do người dùng tự định nghĩa, do lập trình viên tự lập trình để sử dụng. Ngoài ra, trong. • Kiểu tham chiếu được lưu trữ hai nơi: địa chỉ của biến kiểu tham chiếu thì được lưu trữ trong vùng nhớ stack nhưng đối tượng thật lại được lưu trữ trong vùng nhớ heap. Bộ nhớ Stack và Heap 1.3 | Kiểu dữ liệu cơ sở 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.4 | 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# thì để định nghĩa kiểu dữ liệu mới có thể dùng từ khóa struct, class và cú pháp khai báo như sau: struct Struct_Name { // Các trường dữ liệu <access_modifier> <data_type> field_name; // Các hàm thành phần <access_modifier> <return_type> function_name([parameters]); // Các hàm tạo [Struct_Name([parameters]) {. };] } class Class_Name { // Các thuộc tính <access_modifier> <data_type> attribute_name; // Các hàm tạo [Class_Name([parameters]) { };] // Các phương thức khác <access_modifier> <return_type> method_name([parameters]){ }; } Các access_modifier trong class sử dụng được tất cả các bổ từ truy xuất như private, public, protected, internal, protected internal.
Các access_modifier trong struct là public. 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, linked lists, stacks, queues, trees, graphs,. 4 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.