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

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

Mục tiêu học tập của giáo trình được thiết kế nhằm trang bị cho sinh viên năng lực thực hiện và cài đặt các cấu trúc dữ liệu kinh điển cùng các giải thuật xử lý tương ứng trên máy tính. Sau khi hoàn thành học phần, người học đạt được các chuẩn đầu ra cụ thể:

  • Nắm vững và cài đặt được các giải thuật tìm kiếm (tuần tự, nhị phân) và sắp xếp (Interchange Sort, Bubble Sort) trên cấu trúc mảng và cấu trúc dữ liệu tự định nghĩa.
  • Hiểu rõ bản chất tổ chức bộ nhớ của danh sách kế tiếp và danh sách liên kết; hiện thực hóa thành thạo danh sách liên kết đơn, danh sách liên kết kép và danh sách liên kết vòng.
  • Cài đặt cấu trúc dữ liệu trừu tượng Stack (ngăn xếp) và Queue (hàng đợi), ứng dụng giải quyết các bài toán kỹ thuật và mô phỏng thực tế.
  • Xây dựng cấu trúc cây nhị phân, cây nhị phân tìm kiếm (Binary Search Tree) và cây nhị phân tìm kiếm cân bằng; hiện thực các phép duyệt và hiệu chỉnh cây.
  • Thiết lập bảng băm (Hash Table), xây dựng hàm băm và áp dụng các kỹ thuật xử lý xung đột dữ liệu.
  • Rèn luyện tư duy logic và kỹ năng lập trình xử lý con trỏ trên ngôn ngữ C/C++.

Giáo trình được cấu trúc thành 6 bài thực hành tuần tự từ cơ bản đến nâng cao. Điểm đặc trưng trong cách tiếp cận của tài liệu là phương pháp tích hợp mã nguồn mẫu: mỗi chủ đề đều bắt đầu bằng định nghĩa kiểu dữ liệu (struct, typedef), các nguyên mẫu hàm xử lý thao tác nguyên tử, đi kèm khung chương trình điều khiển dạng menu (switch-case) giúp người học thực nghiệm trực tiếp và kiểm chứng thuật toán.

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

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

Nội dung giáo trình gồm 6 bài học chính với tiến trình phát triển từ cấu trúc dữ liệu tuyến tính đến phi tuyến:

  • Bài 1: Giải thuật tìm kiếm: Cung cấp nguyên lý và mã nguồn cài đặt của phương pháp tìm kiếm tuần tự (tuyến tính) trên tập dữ liệu bất kỳ và tìm kiếm nhị phân trên tập dữ liệu đã có thứ tự. Nội dung áp dụng trên dãy số nguyên mảng một chiều int a[] và mở rộng sang mảng cấu trúc bản ghi struct CuonSach (chứa các trường masach, tensach[40], gia), kết hợp hàm xử lý chuỗi strcmp.
  • Bài 2: Giải thuật sắp xếp: Trình bày cơ chế sinh dữ liệu ngẫu nhiên với hàm srand(time(NULL)) và rand()%100 từ thư viện <stdlib.h>. Giáo trình hiện thực các giải thuật đổi chỗ trực tiếp (Interchange Sort) và sắp xếp nổi bọt (Bubble Sort) trên dãy số nguyên và danh sách đối tượng struct, tổ chức thực thi qua menu lựa chọn.
  • Bài 3: Cấu trúc danh sách và Danh sách liên kết: Phân biệt hai phương thức cài đặt danh sách: danh sách kế tiếp (mảng một chiều) và danh sách liên kết (đơn, kép, vòng). Hướng dẫn khai báo cấu trúc nút Node (gồm trường dữ liệu info và con trỏ next), xây dựng các thao tác: init, isEmpty, createNode, insertFirst, insertLast, showList. Ứng dụng quản lý danh sách sinh viên struct SinhVien (masv[10], hoten[40], dtb).
  • Bài 4: Cấu trúc Queue và Stack:
    • Stack (Ngăn xếp): Cài đặt theo nguyên lý vào sau - ra trước (LIFO - Last In First Out) với các thao tác Push, Pop, IsEmpty; giải quyết bài toán chuyển đổi hệ cơ số từ thập phân sang nhị phân (Convert(int n, Stack &s)).
    • Queue (Hàng đợi): Cài đặt theo nguyên lý vào trước - ra trước (FIFO - First In First Out) với các thao tác Insert, Remove; ứng dụng vào bài toán điều phối thứ tự tiếp nhận hồ sơ khám của struct BenhNhan (stt, hoten, tuoi).
  • Bài 5: Cấu trúc Cây và Cây nhị phân tìm kiếm (BST): Khảo sát cấu trúc nút cây nhị phân chứa con trỏ nhánh trái (left) và nhánh phải (right). Định nghĩa tính chất cây nhị phân tìm kiếm: mọi khóa thuộc nhánh con trái nhỏ hơn khóa nút gốc, mọi khóa thuộc nhánh con phải lớn hơn khóa nút gốc. Cài đặt các phép duyệt PreOrder (NLR), InOrder (LNR), PostOrder (LRN); giải thuật chèn nút Insert và giải thuật xóa nút Remove giải quyết 3 trường hợp (nút lá, nút có một cây con, và nút có đủ hai cây con thông qua tìm phần tử thay thế).
  • Bài 6: Cấu trúc Bảng băm (Hash Table): Định nghĩa tập khóa $K$, tập địa chỉ $M$ ($M=10$), hàm băm dạng modulo $f(key) = key \pmod M$. Giới thiệu ba chiến lược xử lý xung đột: phương pháp kết nối trực tiếp (Direct Chaining), phương pháp nối kết hợp nhất (Coalesced Hashing), và phương pháp dò tuyến tính (Linear Probing). Trình bày toàn bộ mã nguồn cài đặt bảng băm theo phương pháp Direct Chaining sử dụng mảng con trỏ NODEPTR bucket[M], các hàm push, pop, insafter, place, insert, search, delafter, remove, traverse, clear.

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

Giáo trình hình thành nền tảng lý thuyết và kỹ thuật lập trình hệ thống:

  • Lý thuyết cấu trúc dữ liệu trừu tượng (ADT): Phân tách rõ ràng giữa định nghĩa giao diện các phép toán logic và cấu trúc lưu trữ vật lý trong bộ nhớ RAM.
  • Nguyên lý phân cấp và ánh xạ dữ liệu: Quy tắc tổ chức dữ liệu tuyến tính (kế tiếp, liên kết), dạng ngăn xếp/hàng đợi, cấu trúc phân nhánh cây nhị phân, và cơ chế ánh xạ địa chỉ của hàm băm.
  • Kỹ thuật xử lý con trỏ và bộ nhớ động: Quản lý cấp phát và giải phóng vùng nhớ thông qua toán tử new/delete trong C++ hoặc các hàm chuẩn malloc()/free() trong thư viện C.

Kỹ năng phát triển

  • Kỹ năng lập trình cài đặt: Hiện thực hóa các thuật toán xử lý dữ liệu phức tạp bằng ngôn ngữ C/C++, kiểm soát việc truyền tham biến (&), xử lý chuỗi ký tự, và điều khiển cấu trúc dữ liệu lồng nhau.
  • Kỹ năng phân tích trường hợp: Nhận diện và xử lý các điều kiện biên trong giải thuật (danh sách rỗng, chèn/xóa ở vị trí đầu/cuối, xóa nút có hai con trên cây BST, đụng độ chỉ mục trong bảng băm).
  • Kỹ năng thiết kế ứng dụng: Xây dựng các ứng dụng mô phỏng xử lý dữ liệu theo menu tương tác dòng lệnh (Console Interface), chuẩn hóa dữ liệu đầu vào và kết xuất thông tin định dạng.

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

Giáo trình áp dụng phương pháp sư phạm thực hành trực quan (Hands-on Lab-based Learning), tích hợp chặt chẽ giữa lý thuyết cấu trúc và mã lệnh cài đặt:

  • Tiến trình bài học có cấu trúc: Mỗi bài thực hành đều xác định mục tiêu chuẩn đầu ra, hệ thống lại lý thuyết ngắn gọn, định nghĩa cấu trúc dữ liệu mẫu, cung cấp mã nguồn từng thao tác và hoàn thiện bằng hàm main() điều khiển menu.
  • Hệ thống bài tập gắn với bài toán ứng dụng:
    • Mô hình quản lý danh mục sách với thao tác tìm kiếm giá trị lớn nhất, tìm sách theo mã và theo tên qua so sánh chuỗi strcmp.
    • Mô phỏng quy trình xử lý chuyển đổi bit nhị phân bằng ngăn xếp Stack.
    • Mô phỏng hệ thống cấp phát số thứ tự khám chữa bệnh của phòng khám bằng hàng đợi Queue.
    • Quản lý điểm số sinh viên, lọc sinh viên đạt loại khá, tìm sinh viên có điểm trung bình cao nhất/thấp nhất hoặc sinh viên có điểm thấp nhất trong nhóm xếp loại giỏi.
  • Phương pháp thực nghiệm và đối chiếu: Giáo trình yêu cầu sinh viên thực hiện các thí nghiệm mã nguồn cụ thể, ví dụ: chạy thử nghiệm hàm nhập dữ liệu với số lượng phần tử $n = 3$, lần lượt thêm $x = 1, 2, 3$ bằng insertFirst và thay thế bằng insertLast, quan sát sự thay đổi thứ tự các phần tử để tự rút ra kết luận về cơ chế hoạt động của danh sách liên kết.
  • Quy định đánh giá học phần:
    • Điểm quá trình chiếm tỷ trọng 50% tổng điểm học phần.
    • Hình thức đánh giá: Bài thi thực hành trên máy tính.
    • Phạm vi nội dung kiểm tra: Bao quát toàn bộ kiến thức và kỹ năng từ Bài thực hành số 1 đến Bài thực hành số 6.
  • Hướng dẫn tự học: Sinh viên được yêu cầu nghiên cứu kỹ tài liệu trước khi lên lớp thực hành, chủ động gạch chân các đoạn mã nguồn và khái niệm chưa hiểu để trao đổi trực tiếp với giảng viên; tự giải quyết các bài tập phần Thực hành nâng cao ở cuối mỗi bài.

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

  • Tính hoàn chỉnh và khả thi của mã nguồn: Tài liệu cung cấp đầy đủ các khai báo thư viện (<stdio.h>, <stdlib.h>, <time.h>), định nghĩa hằng số (#define MAX 100, #define TRUE 1, #define FALSE 0, #define M 10), và mã nguồn chi tiết của từng hàm xử lý mà không dừng lại ở mức mã giả trừu tượng.
  • Hệ thống hóa các phương pháp giải quyết xung đột bảng băm: Giáo trình phân loại rõ ràng 3 kỹ thuật xử lý đụng độ phổ biến trong cấu trúc bảng băm:
    1. Phương pháp nối kết trực tiếp (Direct Chaining): Mỗi địa chỉ trên bảng băm tương ứng với một danh sách liên kết lưu các nút bị xung đột.
    2. Phương pháp nối kết hợp nhất (Coalesced Hashing): Cài đặt bằng danh sách kề trên mảng, sử dụng trường key và trường next trỏ đến nút kế tiếp bị xung đột.
    3. Phương pháp dò tuyến tính (Linear Probing): Tìm kiếm tuần tự vị trí địa chỉ trống tiếp theo khi xảy ra đụng độ tại địa chỉ băm ban đầu.
  • Minh họa giải thuật xóa nút trên Cây BST chi tiết: Mã nguồn hàm Remove trong Bài 5 xử lý tường minh trường hợp nút có hai cây con bằng kỹ thuật tìm nút cực trái của cây con bên phải (rp = p->right; while (rp->left != NULL)) để kế thừa dữ liệu và bảo toàn tính chất cây tìm kiếm nhị phân.
  • Liên kết tài liệu tham khảo chuẩn mực: Giáo trình tổng hợp và đối chiếu nội dung dựa trên các tài liệu học thuật uy tín:
    • Tài liệu của tác giả Lê Minh Hoàng.
    • Giáo trình quốc tế: Richard Neapolitan & Kumarss (2004), Foundations of Algorithms Using C++ Pseudocode, Jones and Bartlett Publishers.

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

  • Sinh viên bậc Đại học và Cao đẳng: Phục vụ trực tiếp cho sinh viên năm thứ nhất và năm thứ hai theo học các ngành Công nghệ Thông tin, Kỹ thuật Phần mềm, Hệ thống Thông tin, Khoa học Máy tính và Mạng máy tính đăng ký học phần COS321.
  • Điều kiện tiên quyết (Prerequisites): Người học cần hoàn thành học phần Kỹ thuật lập trình hoặc Nhập môn lập trình, nắm vững cú pháp ngôn ngữ C/C++, cấu trúc điều khiển, mảng, con trỏ, kiểu dữ liệu có cấu trúc (struct) và cấp phát bộ nhớ động.
  • Giảng viên chuyên ngành: Sử dụng làm đề cương chi tiết hướng dẫn thực hành trên phòng máy, khung chuẩn hóa các bài lab và ngân hàng câu hỏi phục vụ đánh giá thi thực hành kết thúc học phần.
  • Người tự học và nghiên cứu: Tài liệu tham khảo hữu ích cho lập trình viên cần củng cố lại bản chất cài đặt mức cơ sở của các cấu trúc dữ liệu và giải thuật mà không phụ thuộc vào các thư viện mẫu có sẵn (như C++ STL).

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 được biên soạn phục vụ sinh viên khối ngành Công nghệ Thông tin tại Trường Đại học Công nghệ TP.HCM (HUTECH) và các cơ sở đào tạo đại học đang học môn Cấu trúc dữ liệu và giải thuật hệ thực hành cơ bản (mã học phần COS321).

2. Cần kiến thức nền nào để học?

Người học cần có kiến thức lập trình cơ bản bằng ngôn ngữ C hoặc C++, đặc biệt là kỹ năng sử dụng con trỏ (pointer), truyền tham chiếu (&), định nghĩa cấu trúc (struct), sử dụng hàm và các cấu trúc lặp/điều kiện.

3. Điểm khác biệt với giáo trình khác?

Giáo trình tập trung tuyệt đối vào khía cạnh triển khai thực hành (Implementation). Thay vì chỉ trình bày thuật toán bằng mã giả, tài liệu xây dựng từng hàm thao tác hoàn chỉnh trên ngôn ngữ C/C++, kèm cấu trúc chương trình dạng menu để người học thực thi, kiểm tra và gỡ lỗi trực tiếp trên máy tính.

4. Làm sao để tự học hiệu quả?

Người học nên đọc trước lý thuyết từng bài, gõ lại các khối lệnh khai báo cấu trúc và hàm thao tác, sau đó tự tay viết hàm main() ghép nối chương trình. Cần thực hiện các thí nghiệm thay đổi tham số (như đổi hàm chèn đầu insertFirst thành chèn cuối insertLast) và hoàn thành các bài tập nâng cao ở cuối mỗi chương.

5. Có tài liệu bổ trợ nào kèm theo?

Tài liệu viện dẫn trực tiếp đến giáo trình của tác giả Lê Minh Hoàng và cuốn sách học thuật chuẩn mực Foundations of Algorithms Using C++ Pseudocode (Richard Neapolitan & Kumarss, 2004). Người học có thể liên hệ bộ phận hỗ trợ tài liệu học tập qua email: tailieuhoctap@hutech.edu.vn.

Kết luận

Giáo trình "Cấu trúc dữ liệu và giải thuật: Thực hành cơ bản" (COS321) cung cấp hệ thống bài tập thực hành mẫu mực, bám sát các cấu trúc dữ liệu nền tảng từ danh sách, ngăn xếp, hàng đợi, cây nhị phân tìm kiếm đến bảng băm. Lộ trình học tập 6 bài thực hành được thiết kế theo trật tự logic chặt chẽ, giúp người học chuyển hóa kiến thức lý thuyết trừu tượng thành năng lực lập trình cụ thể trên máy tính. Để đạt hiệu quả cao nhất, người học nên kết hợp việc thực hành mã nguồn trong tài liệu với việc nghiên cứu chuyên sâu các tài liệu tham khảo quốc tế của Richard Neapolitan và tài liệu giải thuật chuyên khảo của Lê Minh Hoàng.