Tổng quan về giáo trình

Tài liệu học thuật Data Structure and Algorithms [CO2003] - Chapter 4: List là bài giảng chuyên ngành thuộc chương trình đào tạo kỹ sư và cử nhân ngành Khoa học Máy tính và Kỹ thuật Máy tính tại Trường Đại học Bách Khoa – Đại học Quốc gia TP.HCM (Hochiminh City University of Technology – HCMUT). Tài liệu được biên soạn bởi TS. Nguyễn Đức Dũng (Faculty of Computer Science and Engineering).

Trong khung chương trình đào tạo ngành Công nghệ Thông tin, Cấu trúc dữ liệu và Giải thuật [CO2003] là học phần cơ sở ngành bắt buộc. Nội dung Chương 4 tập trung vào cấu trúc dữ liệu danh sách (List) – một cấu trúc tuyến tính nền tảng phục vụ cho việc tổ chức, lưu trữ và thao tác dữ liệu trong bộ nhớ máy tính.

Mục tiêu đào tạo (Learning Outcomes) của tài liệu được chuẩn hóa theo hệ thống chuẩn đầu ra môn học:

  • L.1: Mô tả và phân biệt các khái niệm về danh sách mảng (array list), danh sách liên kết (singly linked list, doubly linked list, multiple links), ngăn xếp (stack), hàng đợi và hàng đợi vòng (queue, circular queue).
  • L.2 & L.3: Biểu diễn cấu trúc lưu trữ và thiết kế giải thuật cho các phương thức thao tác dữ liệu thông qua mã giả (pseudocode).
  • L.4: Hiện thực hóa đầy đủ các cấu trúc dữ liệu và giải thuật tương ứng bằng ngôn ngữ lập trình C/C++.
  • L.5 & L.6: Lựa chọn giải pháp cài đặt tối ưu (mảng động đối chiếu với danh sách liên kết) cho các bài toán thực tế; phân tích độ phức tạp tính toán thông qua ký hiệu toán học Big-O và xây dựng chương trình thực nghiệm đánh giá hiệu năng.

Tài liệu được xây dựng theo cấu trúc chuyển giao hai bậc: thiết lập mô hình kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) ở mức logic, sau đó chuyển giao sang hiện thực hóa chi tiết ở mức vật lý (Contiguous Implementation và Linked Implementation). Điểm đặc thù của tài liệu là cung cấp trực tiếp mã nguồn C++ hoàn chỉnh với các kỹ thuật quản lý bộ nhớ động và lập trình tổng quát (templates).

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Căn cứ theo đề cương và nội dung chi tiết trong tài liệu, cấu trúc bài giảng bao gồm các chủ đề học thuật:

                            CẤU TRÚC DANH SÁCH (LIST)
   1. MÔ HÌNH TRỪU TƯỢNG (ADT)                                2. CÀI ĐẶT BỘ NHỚ VẬT LÝ
Phân loại:                 Thao tác:             Dạng mảng liên tục          Dạng liên kết
- General List             - Cơ bản (6 ops)      (Dynamic Array)             (Linked List)
  (Ordered / Unordered)    - Mở rộng (7 ops)     - Memory reallocation       - Singly Linked List
- Restricted List                                  (ensureCapacity, pack)    - Node structure
  (FIFO / LIFO)                                  - Shift memory (memmove)    - Pointer manipulation

  1. Khái niệm danh sách tuyến tính (Linear List Concepts):

    • Định nghĩa: Danh sách tuyến tính là cấu trúc dữ liệu trong đó mỗi phần tử đều có một phần tử kế tiếp duy nhất (unique successor).
    • Phân loại danh sách tổng quát (General List): Không giới hạn vị trí thêm/xóa dữ liệu; chia thành danh sách không thứ tự (Unordered/Random List) và danh sách có thứ tự (Ordered List - sắp xếp theo khóa).
    • Danh sách hạn chế (Restricted List): Giới hạn vị trí thao tác tại các đầu mút danh sách (cơ sở cho Ngăn xếp - LIFO và Hàng đợi - FIFO).
    • Kiểu dữ liệu trừu tượng List (List ADT): Định nghĩa danh sách là dãy hữu hạn các phần tử kiểu $T$. Hệ thống hóa 6 phép toán cơ bản (Khởi tạo rỗng, Thêm, Xóa, Tìm kiếm, Truy xuất, Duyệt) và 7 phép toán mở rộng (Kiểm tra rỗng, Kiểm tra đầy, Lấy kích thước, Xóa toàn bộ, Thay thế phần tử, Trộn hai danh sách có thứ tự, Nối danh sách).

  2. Hiện thực danh sách bằng mảng động (Dynamic Array Implementation):

    • Kiến trúc lớp DynamicArray trong C++ với các trường dữ liệu: int size (số phần tử hiện có), int capacity (dung lượng tối đa được cấp phát) và con trỏ int* storage.
    • Các thuật toán quản lý dung lượng: setCapacity (tái cấp phát và sao chép qua memcpy), ensureCapacity (mở rộng dung lượng theo hệ số $(capacity \times 3)/2 + 1$), pack (thu hẹp dung lượng khi $size \le capacity/2$), và trim (thu hẹp capacity bằng size).
    • Kỹ thuật kiểm tra chỉ số biên thông qua phương thức rangeCheck(index) và xử lý ngoại lệ throw "Index out of bounds!".
    • Các thao tác chèn (insertAt) và xóa (removeAt) sử dụng hàm memmove của C++ để tịnh tiến vùng nhớ.

  3. Hiện thực danh sách liên kết đơn (Singly Linked List Implementation):

    • Định nghĩa cấu trúc Nút (Node) gồm hai thành phần: trường dữ liệu (data) và trường liên kết trỏ đến nút kế tiếp (link / Node* link).
    • Ứng dụng mẫu: Biểu diễn đa thức toán học (Polynomial representation) bằng chuỗi liên kết các nút dữ liệu.
    • Cài đặt cấu trúc lớp tổng quát bằng C++ Templates: template <class ItemType> class Node và template <class List_ItemType> class LinkedList với con trỏ quản lý đầu danh sách Node<List_ItemType>* head và biến đếm int count.
    • Thiết kế thuật toán mã giả và mã nguồn C++ cho các trường hợp chèn nút: chèn vào danh sách rỗng, chèn tại vị trí đầu danh sách (cập nhật con trỏ head), và chèn vào vị trí giữa danh sách (thông qua nút tiền nhiệm pPre).

  4. Các dạng danh sách liên kết khác (Other Linked Lists) và So sánh hiệu năng cài đặt (Comparison of implementations of list):

    • Khái quát hóa danh sách liên kết đôi (Doubly linked list) và danh sách liên kết vòng (Circular linked list).
    • Đánh giá sự đánh đổi (trade-offs) về mặt tài nguyên bộ nhớ và độ phức tạp thời gian giữa cài đặt mảng và cài đặt liên kết.

Kiến thức nền tảng được xây dựng

  • Mô hình hóa dữ liệu trừu tượng: Tách biệt hoàn toàn giữa giao diện hành vi (Interface) của kiểu dữ liệu trừu tượng (ADT) với cấu trúc lưu trữ nội tại (Implementation details).
  • Cơ chế quản lý bộ nhớ thủ công trong C++: Cấp phát và giải phóng vùng nhớ trên Heap bằng toán tử new, delete, delete[], cùng các hàm thao tác bộ nhớ mức byte (memcpy, memmove).
  • Lý thuyết phân tích thuật toán: Ứng dụng ký hiệu Big-O để đánh giá độ phức tạp thuật toán. Cụ thể với cấu trúc mảng liên tục (Contiguous List):
    • Phép toán Insert và Remove có độ phức tạp thời gian tỷ lệ với $n$ ($O(n)$) do yêu cầu dịch chuyển vật lý các phần tử (physical shifting).
    • Phép toán Clear, Empty, Full, Size, Replace, Retrieve (truy xuất ngẫu nhiên qua chỉ số) có độ phức tạp thời gian hằng số ($O(1)$).
+---------------------------+-----------------------------------+-----------------------------------+
| Thao tác / Đặc tính       | Cài đặt Mảng Động (Dynamic Array) | Danh sách liên kết (Linked List)  |
+---------------------------+-----------------------------------+-----------------------------------+
| Truy xuất theo chỉ mục    | O(1) - Truy cập ngẫu nhiên        | O(n) - Phải duyệt tuần tự         |
| Chèn/Xóa tại đầu/giữa     | O(n) - Dịch chuyển bộ nhớ vật lý  | O(1) - Nếu đã có con trỏ vị trí   |
| Quản lý dung lượng bộ nhớ | Cần cấp phát lại & sao chép       | Cấp phát động từng nút riêng biệt |
| Chi phí bộ nhớ phụ        | Dư thừa capacity chưa dùng        | Con trỏ liên kết (link) ở mỗi nút |
+---------------------------+-----------------------------------+-----------------------------------+

Kỹ năng phát triển

  • Kỹ năng lập trình hệ thống và cấu trúc dữ liệu: Khả năng tự cài đặt các thư viện cấu trúc dữ liệu từ mức cơ bản mà không phụ thuộc vào thư viện chuẩn (STL), kiểm soát rò rỉ bộ nhớ (memory leak) qua hàm hủy (destructor).
  • Kỹ năng viết mã giải thuật: Chuyển đổi chính xác giữa mô tả bài toán, mã giả chuẩn mực và mã nguồn C++ có sử dụng Generic Programming (template).
  • Kỹ năng phân tích và đo lường hiệu năng: Đánh giá chi phí tính toán lý thuyết và thiết kế kịch bản thực nghiệm để kiểm chứng thời gian thực thi của các thao tác dữ liệu.

Phương pháp giảng dạy và học tập

Tài liệu áp dụng phương pháp sư phạm tiếp cận từ trừu tượng đến cụ thể (Top-Down Pedagogical Approach), chia tiến trình bài học thành ba giai đoạn logic:

  1. Đặc tả hình thức (Specification): Trình bày định nghĩa toán học và logic của Linear List, phân tích các điều kiện tiên quyết (Pre-conditions) và hậu điều kiện (Post-conditions) của từng thao tác (ví dụ: điều kiện chèn thành công là danh sách chưa đầy; điều kiện xóa/truy xuất thành công là danh sách không rỗng).
  2. Mô hình hóa thuật toán (Algorithmic Modeling): Trình bày thuật toán dưới dạng mã giả chuẩn (Algorithm createList(ref list <metadata>)), minh họa sự thay đổi liên kết con trỏ bằng sơ đồ trực quan.
  3. Hiện thực hóa mã nguồn (Source Code Implementation): Cung cấp trực tiếp mã C++ hướng đối tượng, phân tích chi tiết từng khối lệnh xử lý con trỏ và vùng nhớ.
       ĐẶC TẢ HÌNH THỨC
  (Khái niệm, List ADT, Pre/Post)
      MÔ HÌNH HÓA THUẬT TOÁN
   (Mã giả Pseudocode, Sơ đồ nút)
     HIỆN THỰC HÓA MÃ NGUỒN
 (C++ Templates, Con trỏ, Memory)

Về mặt thực hành, tài liệu lồng ghép các bài toán điển hình như biểu diễn đa thức đại số (Polynomial Representation) bằng danh sách liên kết, trong đó mỗi nút lưu trữ hệ số và số mũ.

Phương pháp đánh giá bám sát hệ thống chuẩn đầu ra $L.1 - L.6$. Người học được định hướng tự học thông qua việc:

  • Tự viết mã nguồn hoàn chỉnh dựa trên các phương thức khung được cung cấp (rangeCheck, insertAt, removeAt, pack, trim).
  • Tự thực hiện các bài toán phân tích độ phức tạp Big-O cho các cấu trúc điều khiển tuần tự, rẽ nhánh và lặp.
  • Thiết kế chương trình đối sánh thực nghiệm hiệu năng giữa hai phương pháp cài đặt mảng và danh sách liên kết.

Điểm nổi bật và cập nhật

Nội dung bài giảng thể hiện tính cập nhật và sự chặt chẽ về mặt kỹ thuật phần mềm thông qua các khía cạnh:

  • Chiến lược co giãn bộ nhớ tối ưu hóa: Trong phần cài đặt DynamicArray, tác giả không sử dụng kỹ thuật tăng kích thước cố định mà cài đặt công thức tăng trưởng động: $$\text{newCapacity} = \frac{\text{capacity} \times 3}{2} + 1$$ Công thức này giúp cân bằng giữa số lần phải cấp phát lại bộ nhớ và dung lượng bộ nhớ dư thừa. Đồng thời, giáo trình cung cấp phương thức pack() để tự động giải phóng vùng nhớ thừa khi số phần tử giảm xuống dưới ngưỡng $50%$ dung lượng ($size \le capacity / 2$), cùng hàm trim() để giải phóng toàn bộ vùng nhớ dư thừa.
  • Tính chính xác trong thao tác bộ nhớ: Bài giảng phân biệt rõ ràng việc sử dụng hàm memcpy (khi tạo vùng nhớ mới hoàn toàn không chồng lấn trong setCapacity) và hàm memmove (khi dịch chuyển các phần tử trên cùng một mảng nội bộ trong insertAt và removeAt để tránh lỗi ghi đè dữ liệu).
  • Ứng dụng lập trình tổng quát (Generic Programming): Toàn bộ cấu trúc Node và LinkedList được xây dựng bằng cơ chế template <class ItemType> và template <class List_ItemType>, cho phép cấu trúc dữ liệu lưu trữ đa dạng kiểu dữ liệu nguyên thủy hoặc đối tượng phức hợp.

Đối tượng sử dụng giáo trình

Tài liệu được thiết kế phục vụ các đối tượng trong môi trường học thuật đại học:

  • Sinh viên đại học: Sinh viên năm thứ nhất hoặc năm thứ hai thuộc các ngành Khoa học Máy tính, Kỹ thuật Máy tính, Công nghệ Thông tin, Hệ thống Thông tin đang theo học môn học Cấu trúc dữ liệu và Giải thuật (Data Structures and Algorithms).
  • Yêu cầu kiến thức tiên quyết (Prerequisites):
    • Nắm vững cú pháp và tư duy lập trình C/C++ cơ bản.
    • Hiểu rõ bản chất con trỏ (pointers), địa chỉ ô nhớ và cơ chế cấp phát động (new/delete).
    • Kiến thức toán rời rạc căn bản phục vụ cho việc tính toán độ phức tạp thời gian Big-O.
  • Giảng viên và Nghiên cứu sinh: Sử dụng làm đề cương bài giảng chuẩn, khung tham chiếu thiết kế bài tập thực hành phòng máy (Lab assignments), đề thi tự luận và trắc nghiệm chuyên ngành.
  • Người tự học và kỹ sư phần mềm: Dùng làm tài liệu tham khảo để củng cố nền tảng về tổ chức bộ nhớ mức thấp, rèn luyện kỹ năng cài đặt cấu trúc dữ liệu thủ công phục vụ các kỳ đánh giá kỹ thuật.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu phù hợp trực tiếp với sinh viên đại học khối ngành Công nghệ Thông tin - Điện tử Viễn thông cần học tập môn Cấu trúc dữ liệu và Giải thuật mã [CO2003], cũng như người học cần nắm chắc cấu trúc bên trong của các dạng danh sách tuyến tính.

2. Cần kiến thức nền nào để học tốt nội dung này?

Người học cần có kiến thức nền tảng về ngôn ngữ lập trình C/C++, bao gồm: lập trình hướng đối tượng cơ bản (class/struct), kỹ thuật sử dụng con trỏ, quản lý bộ nhớ heap, cơ chế template, và khái niệm cơ bản về giải thuật và độ phức tạp Big-O.

3. Điểm khác biệt giữa hai phương pháp cài đặt List trong tài liệu là gì?

Cài đặt bằng mảng động (Contiguous/Dynamic Array) sử dụng các ô nhớ liên tiếp, cho phép truy xuất ngẫu nhiên $O(1)$ qua chỉ số nhưng thao tác chèn/xóa tốn chi phí $O(n)$ do phải dịch chuyển bộ nhớ. Ngược lại, danh sách liên kết (Linked List) sử dụng các nút nhớ phân tán nối với nhau bằng con trỏ, cho phép chèn/xóa tối ưu hơn khi đã định vị được nút nhưng việc truy xuất bắt buộc phải duyệt tuần tự $O(n)$.

4. Làm sao để tự học và làm chủ kiến thức trong chương này hiệu quả?

Người học nên kết hợp đọc hiểu định nghĩa trừu tượng (ADT), vẽ sơ đồ biến đổi liên kết con trỏ trên giấy đối với từng trường hợp (chèn đầu, chèn giữa, chèn vào danh sách rỗng), sau đó tự gõ lại và hoàn thiện toàn bộ mã nguồn C++ của hai lớp DynamicArray và LinkedList kèm theo các chương trình main() kiểm thử.

5. Có tài liệu bổ trợ nào kèm theo trong chương trình môn học?

Nội dung bài giảng nằm trong chuỗi bài giảng đồng bộ của học phần CO2003 tại HCMUT, kết nối trực tiếp với các chương tiếp theo bao gồm: Ngăn xếp và Hàng đợi (Stack and Queue), Cây (Tree), Đống (Heap), Thuật toán tìm kiếm (Searching) và Cấu trúc đồ thị (Graphs).

Kết luận

Bài giảng Data Structure and Algorithms [CO2003] Chapter 4 - List của TS. Nguyễn Đức Dũng cung cấp hệ thống kiến thức hoàn chỉnh, chuẩn xác về mặt kỹ thuật đối với cấu trúc dữ liệu danh sách tuyến tính. Bằng việc kết hợp chặt chẽ giữa lý thuyết hình thức (List ADT), biểu diễn giải thuật mã giả và mã nguồn C++ hoàn chỉnh, tài liệu trang bị cho người học tư duy nền tảng vững chắc về quản trị bộ nhớ và tối ưu hóa giải thuật.

Lộ trình học tập đề xuất từ tài liệu bao gồm: nắm vững các phép toán List ADT $\rightarrow$ cài đặt và tối ưu hóa lớp Mảng động (DynamicArray) $\rightarrow$ triển khai Danh sách liên kết đơn (LinkedList) $\rightarrow$ mở rộng sang Danh sách liên kết đôi/vòng $\rightarrow$ ứng dụng xây dựng Ngăn xếp (Stack), Hàng đợi (Queue) và các cấu trúc dữ liệu phi tuyến tính nâng cao.