Đặt vấn đề (5) Thao tác thêm phần tử chỉ cần thay đổi các mối liên kết tại chỗ 10 20 30 … … 18 Chi phí O(1) 09/2013 9 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết là gì ? (1) Hãy viết ra các đặc điểm của DSLK Ít nhất 5 đặc điểm 09/2013 10 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết là gì ? (2) Đặc điểm của DSLK Sử dụng con trỏ (pointer) Cấp phát bộ nhớ động Dãy tuần tự các node Giữa hai node có 1 hay nhiều con trỏ liên kết Các node không cần phải lưu trữ liên tiếp nhau trong bộ nhớ Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ) Thao tác Thêm/Xóa không cần phải dịch chuyển phần tử 09/2013 11 (C) Nguyen Tri Tuan - DH.HCM So sánh Mảng và Danh sách liên kết Mảng Danh sách liên kết Kích thước cố định Số phần tử thay đổi tùy ý Các phần tử lưu trữ tuần tự Các phần tử lưu trữ rời rạc, (địa chỉ tăng dần) trong bộ liên kết với nhau bằng con trỏ nhớ Phải tịnh tiến các phần tử khi Chỉ cần thay đổi con trỏ liên muốn Thêm/Xóa 1 phần tử - kết khi muốn Thêm/Xóa 1 chi phí O(n) phần tử - chi phí O(1) Truy xuất ngẫu nhiên (nhanh) Truy xuất tuần tự (chậm) Sử dụng ít bộ nhớ hơn Sử dụng nhiều bộ nhớ hơn 09/2013 12 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (1) Đặc điểm: Mỗi node chỉ có 1 con trỏ liên kết (đến node kế tiếp trong danh sách) 09/2013 13 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (2) Các thao tác cơ bản Khởi tạo danh sách Xóa danh sách Kiểm tra danh sách rỗng Đếm số phần tử trong danh sách Thêm node Xóa node Tìm một node Lấy thông tin một node 09/2013 14 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (3) Minh họa thao tác thêm node Minh họa thao tác xóa node 09/2013 15 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (4) template <class T> class LINKED_LIST { private: struct ListNode { T data; // data of node ListNode *next; // pointer to next node }; int size; // number of node in list ListNode *head; // pointer to 1st node in list public: LINKED_LIST(); // default constructor LINKED_LIST(const LINKED_LIST &aList); // copy constructor ~LINKED_LIST(); // destructor // operations bool isEmpty(); int getLength(); bool insert(int index, T newItem); // insert after “index” bool remove(int index); int findNode(T key); // return node index or -1 bool retrieve(int index, T &itemData); }; // end class 09/2013 16 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (1) Đặc điểm: Mỗi node có 2 con trỏ liên kết đến node kế tiếp (next) và node phía trước (prev) trong danh sách 09/2013 17 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (2) Các thao tác cơ bản Khởi tạo danh sách Xóa danh sách Kiểm tra danh sách rỗng Đếm số phần tử trong danh sách Thêm node Xóa node Tìm một node Lấy thông tin một node 09/2013 18 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (3) Minh họa thao tác thêm node 09/2013 19 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (4) Minh họa thao tác xóa node 09/2013 20 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (5) template <class T> class DLINKED_LIST { private: struct ListNode { T data; // data of node ListNode *prev, *next; }; int size; // number of node in list ListNode *head; // pointer to 1st node in list public: DLINKED_LIST(); // default constructor DLINKED_LIST(const DLINKED_LIST &aList);// copy constructor ~DLINKED_LIST(); // destructor // operations bool isEmpty(); int getLength(); bool insert(int index, T newItem); // insert after “index” bool remove(int index); int findNode(T key); // return node index, or -1 int retrieve(int index, T &itemData); }; // end class 09/2013 21 (C) Nguyen Tri Tuan - DH.HCM Các cấu trúc dữ liệu cơ bản (Fundamental Data Structures) 1.1 Các danh sách liên kết – Linked Lists 1.2 Ngăn xếp – Stack 1.3 Hàng đợi - Queue 09/2013 22 (C) Nguyen Tri Tuan - DH.HCM Ngăn xếp - Stack Định nghĩa Các thao tác cơ bản Cài đặt Stack bằng mảng Cài đặt Stack bằng DSLK đơn Ứng dụng Stack 09/2013 23 (C) Nguyen Tri Tuan - DH.HCM Định nghĩa Stack là một cấu trúc dữ liệu: Dùng để lưu trữ nhiều phần tử dữ liệu Hoạt động theo cơ chế “Vào sau – Ra trước” (Last In/First Out – LIFO) ** Cấu trúc Stack được phát minh năm 1955, được đăng ký bản quyền năm 1957, bởi tác giả Friedrich L. Bauer (người Đức) 09/2013 24 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (1) Khởi tạo Stack rỗng Xóa Stack Kiểm tra Stack rỗng Thêm một phần tử vào đỉnh Stack (Push) Xóa một phần tử ở đỉnh Stack (Pop) Lấy phần tử ở đỉnh Stack mà không loại bỏ nó 09/2013 25 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (2) Push: thêm 1 phần tử vào đỉnh Stack Pop: lấy ra 1 phần tử ở đỉnh Stack 09/2013 26 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng mảng template <class T> class STACK { private: T *items; // array of stack items int top; // index to top of stack int maxSize; // maximum size of stack public: STACK(int size); // create stack with // ‘size’ items STACK(const STACK &aStack);// copy constructor ~STACK(); // destructor // operations bool isEmpty(); bool push(T newItem); bool pop(T &item); bool topValue(T &item); }; // end class 09/2013 27 (C) Nguyen Tri Tuan - DH.HCM Áp dụng Viết lệnh để thực hiện các yêu cầu sau đây: Khai báo biến stack S, và khởi tạo S có N phần tử Đưa các giá trị sau vào S: 15, 8, 6, 21 Lấy 21 ra khỏi S Lấy 8 ra khỏi S Gán các giá trị 1->99 vào S Lần lượt lấy các phần tử trong S ra và in lên màn hình Cho mảng a chứa dãy số nguyên từ 1->N, hãy đảo ngược các phần tử của mảng a 09/2013 28 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng DSLK đơn (1) Hình minh họa cấu trúc Stack sử dụng DSLK đơn 09/2013 29/203 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng DSLK đơn (2) Push(): chính là thêm node vào đầu DSLK 09/2013 30/203 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng DSLK đơn (3) template <class T> class STACK { private: struct StackNode { T data; // data of item on the stack StackNode *next; // pointer to next node }; StackNode *top; // pointer to top of stack public: STACK(); // default constructor STACK(const STACK &aStack); // copy constructor ~STACK(); // destructor // operations bool isEmpty(); bool push(T newItem); bool pop(T &item); bool topValue(T &item); }; // end class 09/2013 31 (C) Nguyen Tri Tuan - DH.HCM So sánh 2 cách cài đặt Stack So sánh Cài đặt Stack bằng mảng (array-based stack) Cài đặt Stack bằng Danh sách liên kết đơn (pointer- based stack) 09/2013 32 (C) Nguyen Tri Tuan - DH.HCM Ứng dụng của Stack Tính giá trị biểu thức toán học (thuật toán Balan ngược – Reverse Polish notation) Bài toán tìm đường đi trong mê cung, bài toán mã đi tuần, bài toán 8 quân hậu,… Khử đệ qui … 09/2013 33 (C) Nguyen Tri Tuan - DH.HCM Thuật toán Balan ngược Cho 1 biểu thức ở dạng chuỗi: S = “5 + ((1 + 2) * 4) − 3” Biểu thức gồm các toán tử +,-,*,/ và dấu ngoặc () Tính giá trị biểu thức trên 09/2013 34 (C) Nguyen Tri Tuan - DH.HCM Các cấu trúc dữ liệu cơ bản (Fundamental Data Structures) 1.1 Các danh sách liên kết – Linked Lists 1.2 Ngăn xếp – Stack 1.3 Hàng đợi - Queue 09/2013 35 (C) Nguyen Tri Tuan - DH.HCM Hàng đợi - Queue Định nghĩa Các thao tác cơ bản Cài đặt Queue bằng mảng Cài đặt Queue bằng DSLK đơn Ứng dụng Queue 09/2013 36 (C) Nguyen Tri Tuan - DH.HCM Định nghĩa Queue là một cấu trúc dữ liệu: Dùng để lưu trữ nhiều phần tử dữ liệu Hoạt động theo cơ chế “Vào trước – Ra trước” (First In/First Out – FIFO) 09/2013 37 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (1) Khởi tạo Queue rỗng Xóa Queue Kiểm tra Queue rỗng ? Thêm 1 phần tử vào cuối Queue (EnQueue) Lấy ra 1 phần tử ở đầu Queue (DeQueue) Lấy phần tử ở đầu Queue mà không loại bỏ nó 09/2013 38 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (2) EnQueue: thêm 1 phần tử vào cuối Queue DeQueue: lấy ra 1 phần tử ở đầu Queue 09/2013 39/203 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (3) Minh họa thao tác EnQueue 09/2013 40/203 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (4) Minh họa thao tác DeQueue 09/2013 41 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (1) Cấu tạo của Queue 09/2013 42 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (2) Minh họa hình ảnh các phần tử đang chứa trong Queue 09/2013 43 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (3) Khi thêm nhiều phần tử, sẽ làm “tràn” mảng “Tràn giả” 09/2013 44 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (4) Giải pháp cho tình huống “tràn giả”: xử lý mảng như là 1 danh sách vòng 09/2013 45 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (5) template <class T> class QUEUE { private: T *items; // array of queue items int front; int rear; int count; int maxSize; // maximum size of queue public: QUEUE(int size); // create queue with // ‘size’ items QUEUE(const QUEUE &aQueue); // copy constructor ~QUEUE(); // destructor // operations bool isEmpty(); bool enqueue(T newItem); bool dequeue(T &item); bool frontValue(T &item); }; // end class 09/2013 46 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng DSLK đơn (1) - Enqueue: thêm node vào cuối DSLK đơn - Dequeue: xóa node ở đầu DSLK đơn 09/2013 47 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng DSLK đơn (2) template <class T> class QUEUE { private: struct QueueNode { T data; // data of item on the queue QueueNode *next; // pointer to next node }; QueueNode *front; QueueNode *rear; public: QUEUE(); // default constructor QUEUE(const QUEUE &aStack); // copy constructor ~QUEUE(); // destructor // operations bool isEmpty(); bool enqueue(T newItem); bool dequeue(T &item); bool frontValue(T &item); }; // end class 09/2013 48 (C) Nguyen Tri Tuan - DH.HCM Ứng dụng của Queue Quản lý xếp hàng (theo số thứ tự). Tại các ngân hàng, bệnh viện,… Quản lý phục vụ in ấn (máy in) 09/2013 49 (C) Nguyen Tri Tuan - DH.
THƯ MỤC HỌC THUẬT VÀ BẢN MÔ TẢ GIÁO TRÌNH: CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Tổng quan về giáo trình (250-300 từ)
Giáo trình Cấu trúc dữ liệu & Giải thuật (Data Structures and Algorithms) do tác giả Nguyễn Trí Tuấn (Đại học Quốc gia TP.HCM / DH.HCM, phiên bản lưu hành học thuật tháng 09/2013, quy mô 203 trang bài giảng chuyên đề) biên soạn, giữ vị trí học phần bắt buộc thuộc khối kiến thức cơ sở ngành trong chương trình đào tạo Cử nhân và Kỹ sư các ngành Khoa học Máy tính, Kỹ thuật Phần mềm, Công nghệ Thông tin và Hệ thống Thông tin tại bậc đại học.
Mục tiêu học tập của giáo trình hướng đến việc trang bị cho người học hệ thống lý thuyết về các cấu trúc lưu trữ dữ liệu tuyến tính và phi tuyến; cung cấp công cụ phân tích độ phức tạp thời gian $O(1)$, $O(n)$ của các thao tác dữ liệu; rèn luyện năng lực hiện thực hóa cấu trúc dữ liệu trừu tượng (Abstract Data Types - ADT) thông qua ngôn ngữ lập trình hướng đối tượng với kỹ thuật lập trình tổng quát (C++ Template).
Cấu trúc tài liệu được thiết kế theo lộ trình sư phạm phân tầng từ cơ bản đến chuyên sâu, chia làm ba phần chính: Cấu trúc dữ liệu cơ bản (Danh sách liên kết, Ngăn xếp, Hàng đợi), Cây nhị phân (Binary Trees) và Các cấu trúc dữ liệu nâng cao. Phương pháp tiếp cận của giáo trình đi từ việc phân tích hạn chế vật lý của mảng tĩnh (Array) trong bộ nhớ, dẫn dắt đến nhu cầu cấp phát động và quản trị liên kết con trỏ.
Điểm đặc sắc của giáo trình nằm ở tính hệ thống và tính quy chuẩn trong việc mô tả thuật toán: mỗi cấu trúc dữ liệu đều được trình bày song song dưới hai mô hình hiện thực hóa kinh điển là cài đặt dựa trên mảng tĩnh/động (Array-based) và cài đặt dựa trên danh sách liên kết dùng con trỏ (Pointer-based), đi kèm các lớp định nghĩa C++ hoàn chỉnh và bài toán ứng dụng thực tế.
Nội dung kiến thức cốt lõi (500-600 từ)
Các chương/chủ đề chính
Tài liệu tổ chức khối lượng kiến thức học phần thành ba phân hệ nội dung nối tiếp nhau:
[Phần 1: Cấu trúc dữ liệu cơ bản]
├── 1.1 Danh sách liên kết (Linked Lists)
│ ├── Danh sách liên kết đơn (Singly Linked List)
│ └── Danh sách liên kết đôi (Doubly Linked List)
├── 1.2 Ngăn xếp (Stack)
│ ├── Cài đặt bằng Mảng (Array-based Stack)
│ └── Cài đặt bằng DSLK đơn (Pointer-based Stack)
└── 1.3 Hàng đợi (Queue)
├── Cài đặt bằng Mảng & Xử lý mảng vòng (Circular Queue)
└── Cài đặt bằng DSLK đơn (Pointer-based Queue)
[Phần 2: Cây nhị phân (Binary Trees)]
[Phần 3: Các cấu trúc dữ liệu nâng cao]
- Chương 1: Các cấu trúc dữ liệu cơ bản (Fundamental Data Structures)
- Danh sách liên kết (Linked Lists): Định nghĩa cơ chế cấp phát động, các node rời rạc kết nối bằng con trỏ (
pointer). Giáo trình phân tích hai dạng cấu trúc: Danh sách liên kết đơn (LINKED_LISTvới con trỏnext) và Danh sách liên kết đôi (DLINKED_LISTvới cặp con trỏnextvàprev). Cung cấp mã nguồn các thao tác cơ bản: khởi tạo, hủy (destructor), kiểm tra rỗng (isEmpty), đếm số phần tử (getLength), chèn node (insert), xóa node (remove), tìm kiếm (findNode), trích xuất thông tin (retrieve). - Ngăn xếp (Stack): Định nghĩa cơ chế lưu trữ "Vào sau – Ra trước" (Last In / First Out – LIFO), ghi nhận lịch sử phát minh năm 1955 và cấp bản quyền năm 1957 bởi tác giả Friedrich L. Bauer (Đức). Nội dung bao quát các thao tác thêm vào đỉnh (
push), lấy ra khỏi đỉnh (pop), xem đỉnh (topValue), kiểm tra rỗng (isEmpty). Giáo trình trình bày hai kỹ thuật cài đặt: dùng mảng động (STACKquản lý bởi con trỏitems, chỉ sốtop,maxSize) và dùng danh sách liên kết đơn (StackNode *top). - Hàng đợi (Queue): Định nghĩa cơ chế "Vào trước – Ra trước" (First In / First Out – FIFO). Bao gồm các thao tác đưa vào cuối (
enqueue), lấy ra ở đầu (dequeue), xem đầu (frontValue), kiểm tra rỗng (isEmpty). Giáo trình mô tả hai phương pháp cài đặt: dùng mảng tuyến tính kèm giải pháp danh sách vòng (circular queuevới các biến quản lýfront,rear,count,maxSizenhằm khắc phục hiện tượng "tràn giả") và dùng danh sách liên kết đơn (quản trị bởi hai con trỏQueueNode *frontvàQueueNode *rear).
- Danh sách liên kết (Linked Lists): Định nghĩa cơ chế cấp phát động, các node rời rạc kết nối bằng con trỏ (
- Chương 2: Cây nhị phân (Binary Trees): Chuyển dịch từ cấu trúc tuyến tính sang cấu trúc phi tuyến dạng phân cấp, thiết lập nền tảng cho việc biểu diễn dữ liệu có quan hệ cha - con và tối ưu hóa phép duyệt cây.
- Chương 3: Các cấu trúc dữ liệu nâng cao: Mở rộng các mô hình lưu trữ phức hợp phục vụ xử lý các bài toán tìm kiếm và cân bằng dữ liệu nâng cao.
- Logic phát triển nội dung (Progression logic): Bắt đầu từ cấu trúc tuyến tính đơn giản (Mảng, Danh sách liên kết) $\rightarrow$ Cấu trúc tuyến tính có ràng buộc truy cập (Stack LIFO, Queue FIFO) $\rightarrow$ Cấu trúc phi tuyến (Cây nhị phân) $\rightarrow$ Cấu trúc dữ liệu nâng cao.
Kiến thức nền tảng được xây dựng
- Lý thuyết đánh giá độ phức tạp thuật toán (Time Complexity): Giáo trình đối chiếu trực quan chi phí chèn và xóa:
- Trên cấu trúc mảng: Thao tác chèn/xóa đòi hỏi tịnh tiến các phần tử kế sau, dẫn đến chi phí thời gian là $O(n)$.
- Trên danh sách liên kết: Thao tác chèn/xóa chỉ thực hiện cập nhật các liên kết con trỏ tại chỗ, đạt chi phí thời gian $O(1)$.
- Mô hình kiểu dữ liệu trừu tượng (ADT - Abstract Data Types): Tách biệt giao diện thao tác công khai (
public interface) khỏi chi tiết tổ chức dữ liệu riêng tư (private data members). - Nguyên lý quản trị bộ nhớ động trong C++: Cơ chế cấp phát và thu hồi con trỏ, xây dựng hàm tạo (
constructor), hàm tạo sao chép (copy constructor) và hàm hủy (destructor) nhằm tránh thất thoát bộ nhớ (memory leaks).
| Tiêu chí so sánh | Mảng (Array) | Danh sách liên kết (Linked List) |
|---|---|---|
| Kích thước | Cố định (Fixed size) |
Thay đổi tùy ý theo bộ nhớ (Dynamic) |
| Bố trí bộ nhớ | Tuần tự, địa chỉ liên tục | Rời rạc, kết nối qua con trỏ (Pointer) |
| Chi phí Thêm/Xóa | $O(n)$ do phải tịnh tiến phần tử | $O(1)$ chỉ thay đổi liên kết con trỏ |
| Truy xuất phần tử | Ngẫu nhiên (Nhanh - $O(1)$) | Tuần tự (Chậm - $O(n)$) |
| Chi phí bộ nhớ | Ít hơn (không tốn vùng nhớ trỏ) | Nhiều hơn (tốn bộ nhớ lưu trữ con trỏ) |
Kỹ năng phát triển
- Kỹ năng kỹ thuật (Technical skills): Năng lực xây dựng hoàn chỉnh các lớp thư viện cấu trúc dữ liệu bằng C++ Template (
template <class T>); xử lý con trỏ bậc một, con trỏ liên kết đơn (next), con trỏ liên kết kép (prev,next); giải thuật điều hướng chỉ số mảng vòng (modulo arithmetic) trong xử lý hàng đợi. - Kỹ năng phân tích (Analytical skills): Khả năng so sánh định lượng và định tính giữa Array-based và Pointer-based; năng lực phát hiện hiện tượng "tràn giả" (false overflow) trong hàng đợi mảng; phân tích sự đánh đổi (trade-off) giữa không gian bộ nhớ phụ trợ và thời gian truy xuất.
- Kỹ năng giải quyết bài toán (Practical competencies): Ứng dụng Stack trong tính toán biểu thức hậu tố / thuật toán Ba Lan ngược (Reverse Polish notation), khử đệ quy, xử lý thuật toán quay lui (Bài toán tìm đường đi trong mê cung, Mã đi tuần, Bài toán 8 quân hậu); ứng dụng Queue trong bài toán mô phỏng hàng đợi dịch vụ ngân hàng, bệnh viện và quản lý tiến trình in ấn (
spooling).
Phương pháp giảng dạy và học tập (300-350 từ)
Giáo trình triển khai phương pháp tiếp cận sư phạm định hướng vấn đề (Problem-Based Learning). Tiến trình bài giảng được bắt đầu từ việc đặt câu hỏi trực tiếp: "Nếu muốn thêm (Insert) 1 phần tử vào mảng, phải làm sao?", minh họa tường minh thao tác dịch chuyển mảng $O(n)$, từ đó hình thành nhu cầu tự nhiên đối với cấu trúc danh sách liên kết $O(1)$.
[Vấn đề: Chèn/Xóa mảng O(n)] ──> [Đề xuất: Tách rời phần tử & Móc xích con trỏ] ──> [Chuẩn hóa: ADT & C++ Template]
Hệ thống minh họa trực quan đóng vai trò nòng cốt: sơ đồ các node dữ liệu nối tiếp nhau bằng địa chỉ con trỏ, cơ chế dịch chuyển đỉnh top của Stack trong thao tác push/pop, sơ đồ biến động của hai chỉ số front và rear khi thực hiện enqueue/dequeue trong hàng đợi tuyến tính và hàng đợi vòng.
Phương pháp thực hành và đánh giá được thiết kế thông qua các dạng bài tập cụ thể:
- Bài tập thao tác lệnh cơ bản: Yêu cầu viết chuỗi câu lệnh khai báo Stack $S$, đẩy các giá trị $15, 8, 6, 21$ vào $S$, rút trích có điều kiện phần tử $21$ và $8$, gán tuần tự giá trị từ $1 \to 99$ vào $S$ và in ra màn hình.
- Bài tập thuật toán mảng: Ứng dụng cơ chế LIFO của Stack để đảo ngược dãy số nguyên từ $1 \to N$ lưu trong mảng $a$.
- Bài tập hiện thực hóa giải thuật ứng dụng: Viết chương trình tính giá trị biểu thức toán học chứa toán tử
+,-,*,/và dấu ngoặc()bằng thuật toán Ba Lan ngược, xử lý chuỗi mẫu $S = \text{"}5 + ((1 + 2) * 4) - 3\text{"}$.
Hướng dẫn tự học: Sinh viên được khuyến nghị hiện thực hóa độc lập các lớp template LINKED_LIST, DLINKED_LIST, STACK, QUEUE trong môi trường lập trình C++, tự vẽ sơ đồ con trỏ từng bước trước khi viết mã nguồn và kiểm thử các trường hợp biên (danh sách rỗng, chèn/xóa ở đầu, chèn/xóa ở cuối, hàng đợi đầy/rỗng).
Điểm nổi bật và cập nhật (250-300 từ)
- Tính chính xác và chuẩn mực về dữ liệu học thuật: Giáo trình ghi nhận đầy đủ nguồn gốc lịch sử của các cấu trúc dữ liệu, tiêu biểu là việc chỉ rõ cấu trúc Ngăn xếp (Stack) do tác giả người Đức Friedrich L. Bauer phát minh năm 1955 và đăng ký bản quyền vào năm 1957.
- Thiết kế lập trình hướng đối tượng generic chuẩn mực: Toàn bộ các cấu trúc dữ liệu đều được mô hình hóa bằng cú pháp
template <class T>của C++, cho phép tái sử dụng cấu trúc cho mọi kiểu dữ liệu nguyên thủy hoặc kiểu dữ liệu tự định nghĩa. Cấu trúc lớp phân định rõ ràng giữa thành phần lưu trữ nội bộ (struct ListNode,struct StackNode,struct QueueNode) và giao diện tương tác công khai. - Phân tích sâu các tình huống biên trong cài đặt hệ thống: Giáo trình không chỉ dừng lại ở mô hình lý thuyết mà mổ xẻ trực tiếp hiện tượng kỹ thuật "tràn giả" trong cài đặt Queue bằng mảng tuyến tính (khi chỉ số
rearchạm ngưỡngmaxSizedù các vị trí trướcfrontđã bị giải phóng), đồng thời cung cấp giải pháp xử lý triệt để thông qua mô hình danh sách vòng (circular buffer). - Gắn kết thuật toán với ứng dụng hệ thống và công nghiệp phần mềm: Các bài toán ứng dụng được trích xuất trực tiếp từ các bài toán lõi trong công nghệ phần mềm: bộ biên dịch biểu thức toán học, thuật toán tìm kiếm đường đi trong trí tuệ nhân tạo (Mê cung, 8 quân hậu, Mã đi tuần), cơ chế điều phối hàng đợi tác vụ của hệ điều hành (tiến trình in ấn máy in) và hệ thống phân phối số thứ tự giao dịch thực tế.
Đối tượng sử dụng giáo trình (200-250 từ)
- Đối tượng sinh viên: Giáo trình phục vụ trực tiếp cho sinh viên năm thứ nhất và năm thứ hai chuyên ngành Khoa học Máy tính, Kỹ thuật Phần mềm, Công nghệ Thông tin, Hệ thống Thông tin và các ngành kỹ thuật liên quan tại các trường đại học.
- Kiến thức tiên quyết (Prerequisites): Người học cần hoàn thành các học phần Nhập môn Lập trình và Kỹ thuật Lập trình; nắm vững ngôn ngữ lập trình C/C++, kỹ thuật thao tác con trỏ (
pointer), quản lý bộ nhớ động (dynamic memory allocation), cấu trúc dữ liệu tự định nghĩa (struct) và các khái niệm cơ bản về lập trình hướng đối tượng (class,constructor,destructor). - Đối với giảng viên: Tài liệu cung cấp cấu trúc bài giảng slide chuẩn hóa (203 trang), hệ thống mã nguồn mẫu (C++ ADT) và ngân hàng bài tập thực hành phòng lab, có thể sử dụng làm giáo án chính thức cho học phần Cấu trúc dữ liệu & Giải thuật.
- Đối với người tự học và nghiên cứu: Tài liệu là nguồn tra cứu chuẩn xác về định nghĩa, mã nguồn khung và phân tích chi phí thuật toán, phù hợp cho người chuẩn bị tham gia các kỳ đánh giá kỹ thuật lập trình và phỏng vấn kỹ sư phần mềm.
Câu hỏi thường gặp (250-300 từ)
1. Giáo trình này phù hợp với đối tượng người học nào?
Giáo trình được thiết kế chuẩn hóa cho sinh viên đại học khối ngành Công nghệ Thông tin - Khoa học Máy tính học phần Cấu trúc dữ liệu & Giải thuật, cùng những người học cần nắm vững bản chất tổ chức dữ liệu cấp thấp và kỹ thuật lập trình C++.
2. Cần chuẩn bị kiến thức nền tảng nào trước khi tiếp cận tài liệu?
Người học cần có nền tảng lập trình C++ vững chắc, đặc biệt là kiến thức về con trỏ, cấp phát bộ nhớ động, struct/class và kỹ thuật lập trình mẫu (template).
3. Giáo trình này có điểm gì khác biệt trong phương pháp tiếp cận?
Tài liệu tiếp cận dựa trên việc so sánh trực tiếp hiệu năng giữa Mảng và Danh sách liên kết ($O(n)$ so với $O(1)$), đồng thời luôn trình bày song song cả hai giải pháp hiện thực hóa: Array-based và Pointer-based cho từng cấu trúc dữ liệu trừu tượng.
4. Phương pháp tự học giáo trình như thế nào để đạt hiệu quả cao?
Người học cần tự cài đặt lại toàn bộ các lớp LINKED_LIST, DLINKED_LIST, STACK, QUEUE bằng C++ Template từ đầu mà không sử dụng thư viện chuẩn (std::list, std::stack, std::queue), sau đó giải quyết các bài toán ứng dụng như thuật toán Ba Lan ngược và bài toán quay lui.
5. Có những tài liệu bổ trợ nào gắn liền với nội dung giáo trình?
Tài liệu bao gồm bộ slide bài giảng 203 trang của tác giả Nguyễn Trí Tuấn (DH.HCM), hệ thống mã nguồn C++ Template mẫu và các chuyên đề thuật toán mở rộng về Cây nhị phân và Cấu trúc dữ liệu nâng cao.
Kết luận (150 từ)
Giáo trình Cấu trúc dữ liệu & Giải thuật của tác giả Nguyễn Trí Tuấn (Đại học Quốc gia TP.HCM, 09/2013) cung cấp hệ thống tri thức chuẩn xác, khoa học về các cấu trúc lưu trữ dữ liệu tuyến tính và phi tuyến. Giá trị cốt lõi của tài liệu thể hiện ở tính chuẩn mực của các lớp C++ Template ADT, sự đối chiếu chi tiết giữa hai mô hình cài đặt Array-based và Pointer-based, cùng các bài toán ứng dụng kinh điển trong khoa học máy tính.
Lộ trình học tập khuyến nghị bắt đầu từ việc nắm vững cấu trúc Danh sách liên kết đơn/đôi $\rightarrow$ làm chủ Ngăn xếp và Hàng đợi kèm kỹ thuật xử lý mảng vòng $\rightarrow$ làm chủ giải thuật Ba Lan ngược và quay lui $\rightarrow$ tiến tới Cây nhị phân và Cấu trúc nâng cao. Người học nên kết hợp nghiên cứu trọn bộ 203 trang bài giảng với việc thực hành lập trình độc lập để làm chủ hoàn toàn các cấu trúc dữ liệu nền tảng.