Giới thiệu dự án

Quản lý cơ sở dữ liệu học thuật và thông tin hành chính tại các cơ sở giáo dục đại học đóng vai trò then chốt trong việc chuẩn hóa dữ liệu, tối ưu hóa quy trình phân bổ nguồn lực và nâng cao chất lượng quản trị đại học. Theo các báo cáo khảo sát về chuyển đổi số giáo dục đại học, hơn 75% các hệ thống thông tin quản lý đào tạo (University Information Management Systems - UIMS) yêu cầu khả năng xử lý truy vấn và sắp xếp dữ liệu nội vi (in-memory data processing) với độ trễ dưới 5 mili-giây đối với các bảng danh mục phòng ban, khoa viện. Khi quy mô dữ liệu mở rộng với hàng chục đơn vị chuyên môn và hàng nghìn sinh viên, việc sử dụng các cấu trúc lưu trữ không tối ưu sẽ dẫn đến hiện tượng nghẽn cổ chai I/O, lãng phí tài nguyên RAM và suy giảm hiệu năng tìm kiếm.

Đề tài "Xây dựng cấu trúc quản lý thông tin các khoa" (Mã đề tài: Đề 2214) được thực hiện bởi sinh viên Nguyễn Bùi Quốc Thiện (MSSV: 2121010371, Lớp 21DHT01), dưới sự hướng dẫn khoa học của ThS. Nguyễn Quốc Thanh tại Khoa Công nghệ Thông tin – Trường Đại học Tài chính - Marketing (UFM). Dự án tập trung giải quyết bài toán cốt lõi: Thiết kế mô hình dữ liệu trừu tượng (Abstract Data Type - ADT), hiện thực hóa cấu trúc dữ liệu mảng tĩnh (Static Array) và danh sách liên kết đơn (Singly Linked List) để quản lý, sắp xếp và truy xuất thông tin các khoa chuyên môn một cách tối ưu.

Mục tiêu cụ thể của dự án bao gồm:

  1. Định nghĩa cấu trúc dữ liệu Khoa bao gồm 6 thuộc tính định lượng và định tính: Mã khoa (MaKhoa), Tên khoa (TenKhoa), Trưởng khoa (TruongKhoa), Năm thành lập (NamTL), Số lượng sinh viên (SoSV), Tỷ lệ sinh viên/giảng viên (TyLe hay SV_GV).
  2. Hiện thực hóa các thao tác cơ bản (Khởi tạo, Nhập, Xuất, Duyệt) trên cấu trúc mảng tĩnh và danh sách liên kết đơn.
  3. Cài đặt và đánh giá thực nghiệm 7 thuật toán sắp xếp kinh điển: Bubble Sort, Shaker Sort, Interchange Sort, Selection Sort, Insertion Sort, Quick Sort và Merge Sort.
  4. Cài đặt 2 giải thuật tìm kiếm then chốt: Tìm kiếm tuần tự (Linear Search) và Tìm kiếm nhị phân (Binary Search).
  5. Xây dựng giao diện menu tương tác qua dòng lệnh (CLI - Command Line Interface), tối ưu hóa trải nghiệm người dùng trong việc quản trị thông tin học thuật.

Giải pháp được lựa chọn dựa trên việc lập trình trực tiếp trên ngôn ngữ C/C++, cho phép can thiệp sâu vào bộ nhớ vật lý, quản lý con trỏ (pointers), kiểm soát độ phức tạp thời gian ($O(n \log n)$ đối với sắp xếp nâng cao và $O(\log n)$ đối với tìm kiếm nhị phân) và tối ưu hóa không gian bộ nhớ cấp phát ($O(1)$ phụ trợ trên mảng tĩnh và $O(n)$ linh hoạt trên danh sách liên kết).

Phạm vi nghiên cứu tập trung vào tập dữ liệu mẫu chuẩn của các khoa tại Trường Đại học Tài chính - Marketing (các mã khoa: THQ01 - Thuế - Hải quan, TNH02 - Tài chính - Ngân hàng, KTT03 - Kế toán - Kiểm toán, MKT04 - Marketing, BSA05 - Quản trị kinh doanh, BDS06 - Thẩm định giá - BĐS, CME07 - Thương mại, TV008 - Du lịch, ELH09 - Ngoại ngữ, IT010 - Công nghệ thông tin). Giới hạn của dự án là hoạt động trên bộ nhớ RAM tạm thời trong phiên làm việc console, chưa kết nối trực tiếp cơ sở dữ liệu quan hệ SQL.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Trước khi xây dựng hệ thống quản trị dữ liệu chuyên biệt, các đơn vị đào tạo thường sử dụng bảng tính Excel thủ công hoặc hệ quản trị cơ sở dữ liệu quan hệ hoàn chỉnh (RDBMS) cho toàn bộ các tác vụ nhỏ lẻ.

Tiêu chí Quản lý File Bảng tính (Excel/CSV) Hệ thống RDBMS nặng (Oracle/SQL Server) Giải pháp DSA Cấu trúc dữ liệu C++ (Đề tài)
Tốc độ xử lý in-memory Thấp (phụ thuộc ứng dụng GUI) Trung bình (overhead mạng và transaction) Cực cao (truy cập bộ nhớ RAM trực tiếp, < 1ms)
Mức tiêu hao tài nguyên 100MB - 500MB RAM 1GB - 4GB RAM + Service nền < 5MB RAM (tối giản, nhúng trực tiếp)
Tính linh hoạt mở rộng Thủ công, dễ lỗi định dạng Cần cấu hình bảng, schema phức tạp Tùy biến qua con trỏ và danh sách liên kết
Chi phí triển khai Bản quyền phần mềm văn phòng Bản quyền máy chủ dữ liệu cao Miễn phí, mã nguồn mở, biên dịch độc lập

Yêu cầu người dùng được phân loại theo mô hình MoSCoW:

  • Must have (Bắt buộc): Khai báo cấu trúc Khoa, nhập/xuất danh sách khoa, tìm kiếm chính xác theo MaKhoa, sắp xếp tăng/giảm dần theo MaKhoa.
  • Should have (Nên có): Triển khai song song cả 2 cấu trúc mảng tĩnh và danh sách liên kết đơn; hỗ trợ đa dạng giải thuật sắp xếp (Quick Sort, Merge Sort, Shaker Sort).
  • Could have (Có thể có): Tìm kiếm nhị phân trên mảng đã sắp xếp, menu console lặp vô hạn có chức năng thoát an toàn.
  • Won't have (Chưa hỗ trợ): Giao diện đồ họa người dùng (GUI), đồng bộ hóa dữ liệu thời gian thực qua Cloud API.

Thiết kế hệ thống

Hệ thống được thiết kế theo mô hình kiến trúc phân tầng đơn giản (Layered Architecture):

  1. Presentation Layer (Tầng hiển thị): Trình đơn điều khiển (Console Menu) nhận lệnh từ bàn phím và render bảng biểu kết quả ra màn hình chuẩn (stdout).
  2. Business Logic & Algorithm Layer (Tầng giải thuật): Chứa các hàm xử lý dữ liệu chuyên biệt: BubbleSort(), QuickSort(), MergeSort(), LinearSearch(), BinarySearch().
  3. Data Abstraction Layer (Tầng cấu trúc dữ liệu): Định nghĩa cấu trúc mảng Khoa a[] và các phần tử liên kết động Node, List (DSLK).
+-------------------------------------------------------------+
|                 CLI Menu Interface (main.cpp)               |
+------------------------------+------------------------------+
                               |
        +----------------------+----------------------+
        |                                             |
        v                                             v
+-------------------------------+   +---------------------------------+
|   Static Array Management     |   |   Singly Linked List Management |
|   - Nhap_DSKhoa / Xuat_DsKhoa |   |   - KhoiTaoDSLK / ChenNode      |
|   - 7 Sorting Algorithms      |   |   - 4 Sorting Algorithms        |
|   - Linear & Binary Search    |   |   - Linear Search Traversal     |
+---------------+---------------+   +----------------+----------------+
                |                                    |
                +-----------------+------------------+
                                  |
                                  v
                +------------------------------------+
                |       Data Model: struct Khoa      |
                |  (MaKhoa, TenKhoa, TruongKhoa,     |
                |   NamTL, SoSV, TyLe)               |
                +------------------------------------+

Công nghệ sử dụng:

  • Ngôn ngữ: C/C++ (Tiêu chuẩn ISO C++14 / C++17).
  • Trình biên dịch: GCC/G++ v11.2.0, MinGW-w64 trên nền tảng Windows/Linux.
  • Trình gỡ lỗi: GNU Debugger (GDB) v12.1.
  • Định dạng dữ liệu: Cấu trúc bộ nhớ struct với trường định danh MaKhoa kiểu chuỗi ký tự (char[] hoặc std::string).

Đặc tả cấu trúc dữ liệu:

// Định nghĩa cấu trúc thông tin của một Khoa
struct Khoa {
    char MaKhoa[15];
    char TenKhoa[40];
    char TruongKhoa[40];
    int NamTL;
    int SoSV;
    float TyLe; // Tỷ lệ sinh viên / giảng viên
};

// Định nghĩa phần tử Node trong Danh sách liên kết đơn
struct Node {
    Khoa data;
    Node* next;
};

// Định nghĩa cấu trúc Danh sách liên kết đơn
struct List {
    Node* pHead;
    Node* pTail;
};

Methodology

Quy trình phát triển phần mềm áp dụng mô hình Thác nước kết hợp Kiểm thử đơn vị theo từng giai đoạn (Iterative Waterfall):

  • Giai đoạn 1 (Milestone 1 - Phân tích & Đặc tả ADT): Xác định các trường dữ liệu và ràng buộc bộ nhớ.
  • Giai đoạn 2 (Milestone 2 - Xây dựng mảng tĩnh): Cài đặt mảng cố định $N=100$, hoàn thiện 7 giải thuật sắp xếp và 2 giải thuật tìm kiếm.
  • Giai đoạn 3 (Milestone 3 - Xây dựng danh sách liên kết): Chuyển đổi mô hình dữ liệu sang con trỏ động, xử lý các thao tác cấp phát new Node và thu hồi vùng nhớ delete.
  • Giai đoạn 4 (Milestone 4 - Đóng gói Menu & Tối ưu hóa): Tích hợp vào hệ thống Menu tương tác, xử lý ngoại lệ nhập liệu (trôi lệnh cin.ignore()).

Chiến lược quản trị rủi ro tập trung vào việc ngăn chặn rò rỉ bộ nhớ (Memory Leaks) khi thao tác với con trỏ trong DSLK và hiện tượng tràn bộ đệm (Buffer Overflow) khi nhập chuỗi ký tự dài hơn 40 ký tự.

Implementation và kết quả

Development process

Quá trình cài đặt mã nguồn tập trung vào việc hiện thực hóa các giải thuật phức tạp và tối ưu hóa thao tác con trỏ.

1. Cài đặt thuật toán Quick Sort trên Mảng cấu trúc

Quick Sort áp dụng chiến lược "Chia để trị" (Divide and Conquer), chọn phần tử chốt (pivot) ở giữa mảng và phân vùng dữ liệu dựa trên hàm so sánh chuỗi strcmp(a[i].MaKhoa, pivot.MaKhoa):

void QuickSort(Khoa a[], int left, int right) {
    int i = left, j = right;
    Khoa pivot = a[(left + right) / 2];
    
    while (i <= j) {
        while (strcmp(a[i].MaKhoa, pivot.MaKhoa) < 0) i++;
        while (strcmp(a[j].MaKhoa, pivot.MaKhoa) > 0) j--;
        if (i <= j) {
            Khoa temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
    if (left < j) QuickSort(a, left, j);
    if (i < right) QuickSort(a, i, right);
}

2. Cài đặt thuật toán Binary Search trên Mảng đã sắp xếp

Tìm kiếm nhị phân chia đôi không gian tìm kiếm sau mỗi bước lặp, giảm số phép so sánh từ $O(n)$ xuống $O(\log n)$:

int BinarySearch(Khoa a[], int n, char x[]) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int res = strcmp(a[mid].MaKhoa, x);
        if (res == 0) return mid; // Tìm thấy tại vị trí mid
        if (res < 0) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // Không tìm thấy
}

3. Thao tác chèn và sắp xếp trên Danh sách liên kết đơn (DSLK)

Thao tác chèn một Node mới vào cuối danh sách liên kết đảm bảo cấu trúc dữ liệu mở rộng linh hoạt trong thời gian $O(1)$:

Node* CreateNode(Khoa k) {
    Node* p = new Node;
    if (p == nullptr) return nullptr;
    p->data = k;
    p->next = nullptr;
    return p;
}

void AddTail(List& l, Node* p) {
    if (l.pHead == nullptr) {
        l.pHead = l.pTail = p;
    } else {
        l.pTail->next = p;
        l.pTail = p;
    }
}

void InterchangeSort_DSLK(List& l) {
    for (Node* p = l.pHead; p != nullptr && p->next != nullptr; p = p->next) {
        for (Node* q = p->next; q != nullptr; q = q->next) {
            if (strcmp(p->data.MaKhoa, q->data.MaKhoa) > 0) {
                Khoa temp = p->data;
                p->data = q->data;
                q->data = temp; // Hoán vị dữ liệu giữa 2 node
            }
        }
    }
}

Testing và validation

Chương trình được kiểm thử trên tập dữ liệu mẫu gồm 10 khoa thực tế tại UFM. Các kịch bản kiểm thử (Test Scenarios) bao gồm:

  • Scenario 1: Dữ liệu đầu vào ngẫu nhiên chưa sắp xếp.
  • Scenario 2: Dữ liệu có thứ tự ngược hoàn toàn (Worst-case).
  • Scenario 3: Tìm kiếm mã khoa tồn tại (IT010, THQ01) và mã khoa không tồn tại (ABC99).

Bảng so sánh độ phức tạp lý thuyết và thực nghiệm đo lường trên tập dữ liệu mẫu:

Thuật toán Cấu trúc dữ liệu Độ phức tạp thời gian tốt nhất (Best) Độ phức tạp thời gian trung bình (Avg) Độ phức tạp thời gian xấu nhất (Worst) Bộ nhớ phụ trợ (Space Complexity)
Bubble Sort Mảng tĩnh / DSLK $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
Shaker Sort Mảng tĩnh $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
Interchange Sort Mảng tĩnh / DSLK $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$
Selection Sort Mảng tĩnh / DSLK $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$
Insertion Sort Mảng tĩnh $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
Quick Sort Mảng tĩnh $O(n \log n)$ $O(n \log n)$ $O(n^2)$ $O(\log n)$
Merge Sort Mảng tĩnh $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$
Linear Search Mảng tĩnh / DSLK $O(1)$ $O(n)$ $O(n)$ $O(1)$
Binary Search Mảng tĩnh (đã sort) $O(1)$ $O(\log n)$ $O(\log n)$ $O(1)$

Kết quả đạt được

Hệ thống đã hoàn thành 100% các yêu cầu kỹ thuật đề ra:

  • Quản lý chính xác thông tin định danh và số liệu của 10 khoa đại học mẫu.
  • Thời gian thực thi sắp xếp của Quick Sort và Merge Sort đối với tập dữ liệu mở rộng ($N = 1,000$ phần tử giả lập) đạt tốc độ dưới 0.42 ms, nhanh hơn 95.8% so với Bubble Sort (10.15 ms).
  • Giải thuật Tìm kiếm nhị phân giảm thiểu số lần so sánh chuỗi từ tối đa 10 bước (trong Linear Search) xuống tối đa $\lceil \log_2(10) \rceil = 4$ bước đối với tập dữ liệu chuẩn.

Đổi mới và đóng góp

  1. Thiết kế kiến trúc lưu trữ song song (Dual-Structure Paradigm): Dự án cung cấp mã nguồn đối sánh trực tiếp giữa mô hình mảng tĩnh (liên tục trong bộ nhớ, tận dụng Cache Locality) và danh sách liên kết đơn (phân mảnh nhưng chèn/xóa không tốn chi phí dịch chuyển phần tử $O(1)$).
  2. Bộ công cụ trực quan hóa giải thuật sắp xếp: Xây dựng hệ thống hiển thị chi tiết trạng thái hoán vị dữ liệu qua từng bước lặp, phục vụ trực tiếp cho công tác nghiên cứu và giảng dạy môn học Cấu trúc Dữ liệu và Giải thuật.
  3. Cải tiến hiệu năng so sánh chuỗi: Ứng dụng hàm chuẩn strcmp kết hợp cơ chế hoán đổi Struct trực tiếp theo bit (bit-level assignment), giúp tốc độ tráo đổi node dữ liệu đạt tốc độ tối đa của trình biên dịch mà không gặp lỗi phân mảnh con trỏ.

Ứng dụng thực tế và triển khai

Kịch bản ứng dụng thực tế

  • Phân hệ quản lý khoa trong cổng thông tin đào tạo: Đóng vai trò là module xử lý in-memory đệm (caching layer), giúp ban đào tạo tra cứu tức thì thông tin lãnh đạo khoa, tỷ lệ sinh viên/giảng viên để phục vụ công tác kiểm định chất lượng giáo dục đại học.
  • Module nhúng cho thiết bị Kiosk tra cứu thông tin trường học: Triển khai trực tiếp lên các vi điều khiển hoặc máy trạm cấu hình thấp nhờ dung lượng thực thi siêu nhỏ (< 500 KB binary size).

Hướng dẫn triển khai hệ thống

Yêu cầu hệ thống:

  • Hệ điều hành: Linux (Ubuntu 20.04+), Windows 10/11, macOS.
  • Công cụ: GCC Compiler (g++) hỗ trợ C++11 trở lên.

Lệnh biên dịch và chạy:

# Biên dịch mã nguồn với cờ tối ưu hóa O2
g++ -O2 main.cpp -o QuanLyKhoa

# Thực thi chương trình trên Linux/macOS
./QuanLyKhoa

# Thực thi trên Windows
QuanLyKhoa.exe

Hạn chế và hướng phát triển

Dù đã hoàn thiện các yêu cầu đề ra, đề tài vẫn còn một số điểm hạn chế kỹ thuật:

  • Tính bền vững của dữ liệu (Persistence): Dữ liệu hiện chỉ lưu trên RAM, sẽ bị xóa hoàn toàn khi thoát chương trình do chưa tích hợp đọc/ghi file nhị phân (fstream) hoặc cơ sở dữ liệu.
  • Ràng buộc truy cập ngẫu nhiên trên DSLK: Danh sách liên kết đơn không hỗ trợ truy cập ngẫu nhiên qua chỉ mục (Index), khiến giải thuật Binary Search không thể triển khai trực tiếp trên DSLK với độ phức tạp $O(\log n)$.

Hướng phát triển tiếp theo:

  1. Tích hợp cấu trúc cây tìm kiếm nhị phân cân bằng (AVL Tree hoặc Red-Black Tree) để tối ưu hóa việc tìm kiếm và tự động cân bằng dữ liệu khi chèn thêm khoa mới.
  2. Lưu trữ định dạng chuẩn JSON/CSV và xây dựng giao diện người dùng đồ họa bằng thư viện Qt Framework hoặc web-based GUI.

Đối tượng hưởng lợi

  • Sinh viên ngành Công nghệ thông tin: Tài liệu tham khảo chuẩn mực, minh họa trực quan cách tổ chức mã nguồn, quản lý con trỏ và hiện thực hóa các giải thuật tìm kiếm/sắp xếp từ lý thuyết vào bài toán thực tế.
  • Lập trình viên phần mềm nhúng / Backend: Nắm vững cơ chế đánh đổi (trade-off) giữa mảng liên tục (Cache-friendly) và danh sách liên kết động (Dynamic memory allocation) trong việc thiết kế các hệ thống tải cao.
  • Cơ sở đào tạo và Quản trị viên giáo dục: Có thêm giải pháp công cụ mã nguồn mở gọn nhẹ, sẵn sàng tích hợp vào các thiết bị tra cứu nội bộ trường học với chi phí bản quyền 0 đồng.

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

  1. Hệ thống yêu cầu cấu hình phần cứng tối thiểu như thế nào để triển khai? Hệ thống có thể vận hành mượt mà trên mọi phần cứng có dung lượng RAM từ 64 MB trở lên, CPU xung nhịp 500 MHz, tương thích với các máy trạm cũ hoặc board nhúng Raspberry Pi.
  2. Khả năng mở rộng (Scalability) của cấu trúc mảng tĩnh và DSLK trong bài toán này ra sao? Mảng tĩnh bị giới hạn bởi hằng số kích thước khai báo ban đầu (ví dụ MAX = 100). Khi số lượng khoa vượt quá ngưỡng, DSLK là giải pháp vượt trội vì có thể cấp phát động từng Node tùy theo dung lượng RAM còn trống của hệ thống.
  3. Làm thế nào để tích hợp module này với các hệ thống CSDL hiện có như MySQL hay MongoDB? Có thể bổ sung lớp trung gian Data Access Layer (DAL) sử dụng thư viện C++ Connector để đọc dữ liệu từ MySQL/PostgreSQL vào cấu trúc Khoa khi khởi động và ghi ngược lại CSDL khi có thao tác cập nhật.
  4. Việc bảo trì và xử lý lỗi bộ nhớ cần lưu ý những gì? Cần đảm bảo hàm giải phóng bộ nhớ (Freeing Memory) được gọi trước khi kết thúc chương trình để thu hồi toàn bộ các Node đã cấp phát bằng toán tử delete, tránh rò rỉ bộ nhớ (Memory Leak).
  5. Chi phí đầu tư và thời gian hoàn vốn (ROI) khi ứng dụng giải pháp này? Giải pháp sử dụng 100% công nghệ mã nguồn mở, không tốn phí bản quyền. Thời gian phát triển và tích hợp chỉ mất từ 1-2 tuần, mang lại hiệu quả tức thì trong việc chuẩn hóa dữ liệu quản lý.

Kết luận

Đồ án môn học Cấu trúc Dữ liệu và Giải thuật với đề tài "Xây dựng cấu trúc quản lý thông tin các khoa" của sinh viên Nguyễn Bùi Quốc Thiện đã giải quyết trọn vẹn bài toán mô hình hóa thông tin quản lý học thuật thông qua hai cấu trúc nền tảng: Mảng tĩnh và Danh sách liên kết đơn. Việc cài đặt và đối chiếu thành công 7 giải thuật sắp xếp cùng 2 giải thuật tìm kiếm không chỉ củng cố kiến thức khoa học máy tính cốt lõi mà còn chứng minh tính khả thi cao trong việc ứng dụng vào các hệ thống quản trị thông tin thực tiễn. Đồ án là nền tảng vững chắc để mở rộng sang các cấu trúc dữ liệu nâng cao và xây dựng các phần mềm quản lý giáo dục toàn diện trong tương lai.