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

Tài liệu học tập học phần Cấu trúc dữ liệu và Giải thuật (Mã học phần: COS321, biên soạn phục vụ công tác đào tạo tại Trường Đại học Công nghệ TP.HCM - HUTECH) là tài liệu hướng dẫn thực hành chuyên sâu thuộc khối kiến thức cơ sở ngành Công nghệ thông tin và Kỹ thuật phần mềm. Trong chương trình đào tạo kỹ sư và cử nhân ngành Công nghệ thông tin, học phần đóng vai trò bản lề, kết nối giữa kỹ thuật lập trình cơ bản và các môn học nâng cao như Thiết kế giải thuật, Cơ sở dữ liệu và Phát triển phần mềm.

+-----------------------------------------------------------------------+
|                 HỌC PHẦN CƠ SỞ: KỸ THUẬT LẬP TRÌNH C/C++               |
+-----------------------------------------------------------------------+
                                    │
                                    ▼
+-----------------------------------------------------------------------+
|  COS321: THỰC HÀNH CẤU TRÚC DỮ LIỆU & GIẢI THUẬT (Lab Manual / HUTECH) |
|  • Bài 1: Ôn tập Hàm, Mảng, Struct, Giải thuật Đệ quy                 |
|  • Bài 2: Cấu trúc Danh sách liên kết (Singly & Circular Linked List) |
|  • Bài 3: Cấu trúc Ngăn xếp (Stack) & Hàng đợi (Queue)                |
|  • Bài 4: Cây nhị phân & Cây nhị phân tìm kiếm (BST)                  |
|  • Bài 5: Cây cân bằng AVL (Adelson-Velsky & Landis)                  |
+-----------------------------------------------------------------------+
                                    │
                                    ▼
+-----------------------------------------------------------------------+
|         CÁC HỌC PHẦN CHUYÊN NGÀNH: CSDL, THIẾT KẾ GIẢI THUẬT,         |
|                     KIẾN TRÚC PHẦN MỀM NÂNG CAO                       |
+-----------------------------------------------------------------------+

Về chuẩn đầu ra (learning outcomes), giáo trình định hình mục tiêu cụ thể:

  • Trang bị cho người học tư duy logic có hệ thống và nền tảng toán học ứng dụng trong lập trình.
  • Rèn luyện kỹ năng hiện thực hóa các kiểu dữ liệu trừu tượng (Abstract Data Types - ADTs) bằng ngôn ngữ C/C++.
  • Thành thạo thao tác quản lý bộ nhớ động thông qua con trỏ và cấu trúc dữ liệu liên kết.
  • Tự triển khai, tối ưu hóa các giải thuật tìm kiếm, sắp xếp và cân bằng trên các cấu trúc dữ liệu tuyến tính cũng như phi tuyến.

Cấu trúc giáo trình tiếp cận theo mô hình sư phạm thực hành có hướng dẫn (guided lab). Tài liệu dẫn dắt người học từ việc củng cố kỹ thuật tổ chức chương trình, mảng dữ liệu tĩnh, cấu trúc bản ghi (struct), cho đến việc làm chủ các cấu trúc dữ liệu động phức tạp như danh sách liên kết, ngăn xếp, hàng đợi, cây nhị phân tìm kiếm và cây tự cân bằng AVL. Mỗi chủ đề đều tích hợp phần tóm lược cú pháp mẫu, phân tích mã nguồn chuẩn hóa và hệ thống bài tập thực hành nâng cao.

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

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

Nội dung giáo trình được phân bổ qua 5 bài học thực hành tương ứng với tiến trình phát triển kiến thức từ cấu trúc tuyến tính sang cấu trúc phi tuyến:

[Bài 1: Nền tảng & Đệ quy] ──► [Bài 2: Danh sách liên kết] ──► [Bài 3: Stack & Queue]
                                                                      │
[Bài 5: Cây tự cân bằng AVL] ◄── [Bài 4: Cây nhị phân tìm kiếm BST] ◄──┘

Bài 1: Kỹ thuật lập trình cơ bản và Giải thuật Đệ quy

  • Tổ chức hàm: Cung cấp quy tắc khai báo nguyên mẫu hàm (function prototype), định nghĩa hàm không trả về giá trị (void) và hàm trả về kiểu dữ liệu cụ thể (KieuDL Ten_Ham(...)).
  • Xử lý mảng và cấu trúc dữ liệu tĩnh: Cú pháp khai báo mảng 1 chiều, mảng nhiều chiều; xây dựng các hàm nhập xuất (NhapMang, XuatMang), thuật toán tìm kiếm tuyến tính (TimTuyenTinh), tìm kiếm nhị phân (TimNhiPhan), và thuật toán sắp xếp (sapxep).
  • Dữ liệu cấu trúc (struct): Mô hình hóa đối tượng thực tế thông qua kiểu dữ liệu tự định nghĩa, tiêu biểu là cấu trúc CuonSach (gồm masach: int, tensach: char[40], gia: float) cùng hệ thống hàm thao tác trên danh sách sách (nhapDS, xuatDS, timTuanTu, timNhiPhan).
  • Giải thuật đệ quy: Phân tích điều kiện dừng (base case) và bước đệ quy qua các bài toán mẫu:
    • Tính tổng dãy số: $S(n) = S(n-1) + n$ với điều kiện dừng $S(0) = 0$.
    • Dãy số Fibonacci: $f(n) = f(n-1) + f(n-2)$ với $f(0) = f(1) = 1$.
    • Tìm ước số chung lớn nhất (UCLN) theo thuật toán Euclid trừ lùi.
    • Tính tổng phần tử trong mảng: Tong(a, n) = Tong(a, n-1) + a[n-1].
  • Thực hành nâng cao: Chuỗi 16 bài tập đệ quy chuyên sâu như tính chuỗi lũy thừa bậc ba $\sum n^3$, chuỗi đan dấu $\sum (-1)^n \cdot n$, chuỗi phân thức $\sum \frac{n}{n+1}$, chuỗi tích $\sum n(n+1)(n+2)$, chuỗi nghịch đảo tích $\sum \frac{1}{n(n+1)}$, và công thức tổ hợp $C(n,k) = C(n-1, k) + C(n-1, k-1)$.

Bài 2: Cấu trúc Danh sách liên kết (Linked Lists)

  • Mô hình hóa danh sách liên kết: Giới thiệu danh sách kế tiếp và danh sách liên kết (đơn, vòng).
  • Cấu trúc nút (Node): Khai báo nút gồm trường dữ liệu DataType info (hoặc int, SV) và con trỏ liên kết struct node* next.
  • Các thao tác nền tảng: Khởi tạo danh sách rỗng (init(Node* &phead)), kiểm tra danh sách rỗng (isEmpty), cấp phát nút mới (createNode), chèn phần tử đầu danh sách (insertFirst), chèn phần tử cuối danh sách (insertLast), và duyệt xuất danh sách (showList).
  • Ứng dụng quản lý sinh viên: Định nghĩa cấu trúc SinhVien (SV) chứa masv[10], hoten[40], dtb: float; cài đặt danh sách liên kết đơn quản lý danh sách sinh viên và giải thuật tìm kiếm sinh viên theo mã masv.

Bài 3: Cấu trúc Ngăn xếp (Stack) và Hàng đợi (Queue)

  • Ngăn xếp (Stack): Hoạt động theo nguyên lý LIFO (Last In First Out). Cài đặt thông qua danh sách liên kết đơn với con trỏ đỉnh STACK. Triển khai hai thao tác chính là thêm (push/insert) và xóa (pop/remove).
    • Ứng dụng mẫu: Giải thuật chuyển đổi số nguyên dương từ hệ thập phân sang hệ nhị phân (Convert(int n, Stack &s)).
  • Hàng đợi (Queue): Hoạt động theo nguyên lý FIFO (First In First Out). Khai báo cấu trúc quản lý bằng hai con trỏ đầu và cuối (pHead, pTail).
    • Ứng dụng mẫu: Mô phỏng quy trình tiếp nhận và xử lý hồ sơ bệnh nhân trong phòng khám y tế (BenhNhan).
STACK (LIFO: Vào sau, Ra trước)
Push ──► [ Top: Node 3 ] ──► Pop
         [      Node 2 ]
         [      Node 1 ]

QUEUE (FIFO: Vào trước, Ra trước)
Enqueue ──► [ Tail: Node 3 ] ──► [ Node 2 ] ──► [ Head: Node 1 ] ──► Dequeue

Bài 4: Cây nhị phân và Cây nhị phân tìm kiếm (BST)

  • Khái niệm và định nghĩa: Khai báo nút cây gồm trường giá trị int info và hai con trỏ nhánh con left, right.
  • Các thao tác duyệt cây: Cài đặt các thứ tự duyệt: Tiền thứ tự (PreOrder - Node-Left-Right), Trung thứ tự (InOrder - Left-Node-Right), và Hậu thứ tự (PostOrder - Left-Right-Node).
  • Cây nhị phân tìm kiếm (BST): Ràng buộc khóa tại nút con trái nhỏ hơn khóa nút gốc, khóa tại nút con phải lớn hơn khóa nút gốc. Cài đặt các hàm khởi tạo (Init), cấp phát (CreateNode), chèn phần tử đệ quy (Insert), và giải thuật xóa nút phức tạp (Remove).
  • Giải thuật xóa nút trên BST: Xử lý triệt để 3 trường hợp xóa: nút lá, nút có 1 cây con, và nút có đủ 2 cây con (bằng kỹ thuật tìm nút thế mạng cực trái của cây con bên phải rp->left == NULL).

Bài 5: Cây cân bằng AVL (Adelson-Velsky & Landis)

  • Lý thuyết cân bằng: Định nghĩa cây AVL là cây BST có độ cao của hai cây con bên trái và bên phải tại mọi nút chênh lệch không quá 1.
  • Hệ số cân bằng (Balance Factor - $bf$): $$\text{bf}(p) = \text{height}(\text{left}) - \text{height}(\text{right}) \in {-1, 0, 1}$$
  • Cấu trúc nút mở rộng: Tích hợp thêm thuộc tính chiều cao p->height vào mỗi nút để phục vụ việc kiểm tra và thực hiện các phép quay cây (xoay đơn, xoay kép).
  • Hiện thực: Xây dựng hàm tạo cây AVL tự động từ mảng dữ liệu đầu vào (createAVL(int a[], int n)).

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

  1. Lý thuyết bộ nhớ và con trỏ: Giáo trình xây dựng sự hiểu biết về cách tổ chức bộ nhớ trong ngôn ngữ C/C++, phân biệt giữa cấp phát tĩnh (vùng nhớ Stack) và cấp phát động (vùng nhớ Heap) qua toán tử new, delete.
  2. Nguyên lý trừu tượng hóa dữ liệu (ADTs): Rèn luyện phương pháp đóng gói dữ liệu và các thao tác đi kèm, tách biệt giữa giao diện sử dụng hàm và chi tiết cài đặt bên trong.
  3. Mô hình toán học và logic thuật toán: Thiết lập tư duy toán học thông qua các quan hệ truy hồi đệ quy, kỹ thuật chia để trị, và cấu trúc cây phân cấp.

Kỹ năng phát triển

  • Kỹ năng lập trình hệ thống C/C++: Sử dụng con trỏ, con trỏ cấp hai, tham chiếu (&), định nghĩa cấu trúc phức hợp typedef struct.
  • Kỹ năng phân tích và xử lý trường hợp biên: Xử lý các tình huống lỗi runtime như con trỏ NULL, danh sách rỗng, giải phóng bộ nhớ để tránh rò rỉ dữ liệu (memory leak).
  • Kỹ năng tổ chức cấu trúc chương trình: Thiết kế hệ thống điều khiển tương tác dạng bảng chọn (switch-case), phân tách các module chức năng độc lập.

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

Giáo trình áp dụng mô hình sư phạm tích hợp lý thuyết - thực hành trực quan:

[1. Tóm tắt cú pháp & nguyên mẫu] ──► [2. Phân tích mã nguồn mẫu]
                                                 │
[4. Thực hành mở rộng & nâng cao] ◄── [3. Thực thi kiểm chứng trên IDE]

Các ví dụ và bài toán ứng dụng thực tế

Tài liệu liên tục sử dụng các bài toán nghiệp vụ thực tiễn để minh họa cho cấu trúc dữ liệu:

  • Quản lý thông tin sách: Quản lý mã, tên, đơn giá trên mảng cấu trúc và danh sách liên kết.
  • Quản lý điểm số sinh viên: Xây dựng danh sách liên kết sinh viên gồm mã số, họ tên, điểm trung bình phục vụ tra cứu.
  • Chuyển đổi hệ cơ số: Ứng dụng cấu trúc Stack để tính toán và đảo ngược chuỗi số dư khi đổi từ hệ thập phân sang nhị phân.
  • Mô phỏng hàng đợi bệnh nhân: Ứng dụng cấu trúc Queue trong bài toán điều phối lượt khám chữa bệnh theo thứ tự tiếp nhận.

Đánh giá và hướng dẫn tự học

  • Phương pháp đánh giá: Dựa trên khả năng phân tích logic, viết đúng cú pháp nguyên mẫu hàm, biên dịch không lỗi và xử lý chính xác dữ liệu đầu vào/đầu ra trên môi trường máy ảo hoặc IDE C/C++.
  • Chỉ dẫn học tập: Sinh viên được yêu cầu đọc trước tài liệu, gạch chân các đoạn mã nguồn hoặc khái niệm chưa rõ trước khi tham gia buổi thực hành trên phòng máy, sau đó hoàn thành toàn bộ hệ thống bài tập nâng cao tại nhà.

Điểm đặc sắc và Giá trị sư phạm

  • Tính chuẩn hóa mã nguồn: Các đoạn mã trong tài liệu được trình bày đồng bộ theo chuẩn C/C++, sử dụng kiểu định danh typedef, truyền tham chiếu rõ ràng (Node* &phead, NODEPTR &proot), giúp người học nắm bắt quy chuẩn lập trình chuyên nghiệp.
  • Chi tiết hóa giải thuật phức tạp: Khác với các tài liệu thuần lý thuyết, giáo trình mô tả từng bước thực thi của các thuật toán khó, đặc biệt là giải thuật xóa nút trên cây BST và kỹ thuật tính hệ số cân bằng $bf$ trên cây AVL.
  • Phân cấp bài tập khoa học: Hệ thống bài tập được phân cấp từ các thao tác cơ bản (thêm, xóa, sửa, duyệt) đến các bài toán đệ quy phức tạp (tính chuỗi lũy thừa, tính tổ hợp chập $k$ của $n$), hỗ trợ tối đa việc phân hóa năng lực học tập của sinh viên.

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

Đối tượng Mục đích và Cách thức sử dụng
Sinh viên đại học/cao đẳng Sinh viên năm thứ nhất hoặc năm thứ hai chuyên ngành CNTT, Kỹ thuật phần mềm, Hệ thống thông tin học học phần COS321; dùng làm tài liệu thực hành chính khóa trên phòng lab.
Giảng viên & Trợ giảng Sử dụng làm đề cương hướng dẫn thực hành (Lab Manual), ngân hàng bài tập mẫu, và cơ sở chuẩn hóa ngân hàng đề thi đánh giá kỹ năng lập trình.
Người tự học lập trình Người học cần củng cố kiến thức nền tảng về cấu trúc dữ liệu và giải thuật bằng C/C++, rèn luyện kỹ năng cài đặt thuật toán từ mức cơ sở.

Yêu cầu tiên quyết: 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++ cơ bản, bao gồm: biến, kiểu dữ liệu nguyên thủy, các cấu trúc điều khiển rẽ nhánh (if-else, switch-case), vòng lặp (for, while, do-while), và thao tác vào/ra chuẩn (scanf, printf, cin, cout).

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

1. Giáo trình này phục vụ cho môn học cụ thể nào?

Tài liệu được thiết kế trực tiếp cho học phần Cấu trúc dữ liệu và Giải thuật (mã học phần COS321) trong chương trình đào tạo đại học của HUTECH.

2. Người học cần chuẩn bị kiến thức nền tảng gì trước khi bắt đầu?

Cần nắm vững kỹ thuật lập trình C/C++ cơ bản: cú pháp hàm, mảng, con trỏ cơ bản và kỹ thuật tổ chức câu lệnh điều khiển.

3. Cấu trúc dữ liệu nào được tập trung phân tích sâu nhất trong tài liệu?

Tài liệu phân bổ đồng đều từ cấu trúc dữ liệu tuyến tính (Danh sách liên kết, Stack, Queue) đến cấu trúc dữ liệu phi tuyến (Cây nhị phân, Cây BST, Cây AVL), trong đó cây nhị phân tìm kiếm và cây cân bằng AVL được phân tích chi tiết về mặt giải thuật.

4. Giải thuật đệ quy trong giáo trình được triển khai qua những dạng bài tập nào?

Giải thuật đệ quy được áp dụng từ các bài toán cơ bản như tính tổng dãy số, Fibonacci, ước số chung lớn nhất đến 16 dạng bài tập nâng cao tính chuỗi phân thức, đa thức và công thức tổ hợp $C(n,k)$.

5. Giáo trình có cung cấp mã nguồn mẫu để thực hành không?

Có. Giáo trình cung cấp đầy đủ định nghĩa cấu trúc dữ liệu (struct), khai báo nguyên mẫu hàm, và mã nguồn chi tiết cho các hàm thao tác chính để sinh viên chạy thử nghiệm và kiểm chứng trên máy tính.

Kết luận

Tài liệu hướng dẫn học tập học phần Cấu trúc dữ liệu và Giải thuật (COS321) cung cấp một khung thực hành bài bản, chuẩn mực và có tính hệ thống cao cho việc học tập các cấu trúc dữ liệu cốt lõi trong khoa học máy tính.

LỘ TRÌNH ĐỀ XUẤT:
[Ôn tập Hàm, Mảng, Struct & Đệ quy]
                 │
                 ▼
[Danh sách liên kết Đơn & Vòng]
                 │
                 ▼
[Cấu trúc Tuyến tính: Stack & Queue]
                 │
                 ▼
[Cấu trúc Cây: BST & Cây cân bằng AVL]

Bằng cách đi từ kỹ thuật lập trình nền tảng, giải thuật đệ quy, đến các cấu trúc dữ liệu động tuyến tính và phi tuyến, tài liệu định hình rõ ràng lộ trình phát triển năng lực tư duy logic và kỹ năng lập trình hệ thống cho sinh viên ngành Công nghệ thông tin.