Giới thiệu dự án

Trong kỷ nguyên chuyển đổi số và cá nhân hóa trải nghiệm người dùng, việc tối ưu hóa hiệu năng xử lý dữ liệu khách hàng đóng vai trò cốt lõi trong các hệ thống quản trị quan hệ khách hàng (Customer Relationship Management - CRM). Theo thống kê từ ngành công nghệ phần mềm, hơn 75% độ trễ (latency) của các hệ thống xử lý giao dịch thời gian thực (OLTP) cục bộ bắt nguồn từ cấu trúc dữ liệu không tối ưu và thuật toán tìm kiếm/sắp xếp có độ phức tạp tính toán cao. Khi quy mô dữ liệu khách hàng thân thiết tăng trưởng, các thao tác quản lý như truy vấn điểm tích lũy, phân nhóm doanh số và sắp xếp thứ hạng khách hàng đòi hỏi giải pháp tối ưu hóa trực tiếp ở cấp độ bộ nhớ (in-memory computing).

Đồ án chuyên ngành Hệ thống Thông tin Quản lý tại Trường Đại học Tài chính – Marketing tập trung giải quyết bài toán: Nghiên cứu, thiết kế và cài đặt thực nghiệm các cấu trúc dữ liệu nền tảng (Mảng cấu trúc - Static Structure Array và Danh sách liên kết đơn - Singly Linked List) kết hợp đánh giá chuyên sâu hiệu năng của 2 thuật toán tìm kiếm và 7 thuật toán sắp xếp chuyên biệt trên tập dữ liệu quản lý khách hàng thân thiết.

+-------------------------------------------------------------------------+
|                      MÔ HÌNH QUẢN LÝ DỮ LIỆU IN-MEMORY                   |
+-------------------------------------------------------------------------+
| [Dữ liệu đầu vào: Khách hàng] -> MaKH, Ho, Ten, Nam, Diem, DoanhSo      |
|                                                                         |
|        +-------------------------------------------------------+        |
|        |                PHÂN LỚP CẤU TRÚC DỮ LIỆU              |        |
|        +-------------------------------------------------------+        |
|                  |                                   |                  |
|                  v                                   v                  |
|     +-------------------------+         +-------------------------+     |
|     |     MẢNG CẤU TRÚC       |         |   DANH SÁCH LIÊN KẾT    |     |
|     |  (Contiguous Allocation)|         |   (Dynamic Heap Nodes)  |     |
|     +-------------------------+         +-------------------------+     |
|                  |                                   |                  |
|                  v                                   v                  |
|   +------------------------------+     +------------------------------+ |
|   | - Linear Search / Binary Srch|     | - Linear Search Node         | |
|   | - 7 Thuật toán sắp xếp       |     | - 5 Thuật toán sắp xếp DSLK  | |
|   |   (Quick, Merge, Shaker,...) |     |   (Selection, Insertion,...) | |
|   +------------------------------+     +------------------------------+ |
+-------------------------------------------------------------------------+

Mục tiêu dự án

  1. Chuẩn hóa cấu trúc dữ liệu: Xây dựng mô hình dữ liệu struct KhachHang quản lý tối ưu 6 trường thông tin (Mã khách hàng, Họ, Tên, Năm quản lý, Điểm tích lũy, Doanh số mua hàng) tương thích chuẩn bộ nhớ C++.
  2. Hiện thực hóa giải thuật tìm kiếm: Triển khai Tìm kiếm tuyến tính (Linear Search - $O(n)$) và Tìm kiếm nhị phân (Binary Search - $O(\log n)$) với cơ chế tiền sắp xếp dữ liệu.
  3. Cài đặt đa dạng hóa giải thuật sắp xếp: Phát triển hoàn chỉnh 7 thuật toán sắp xếp trên mảng cấu trúc (Shaker Sort, Selection Sort, Interchange Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort) và 5 thuật toán trên danh sách liên kết đơn (DSLK).
  4. Đánh giá hiệu năng định lượng: Đo lường độ phức tạp thời gian (Time Complexity), độ phức tạp không gian (Space Complexity), và hiệu suất cache bộ nhớ giữa cấp phát tĩnh và cấp phát động.

Phạm vi và giới hạn hệ thống

  • Phạm vi: Ứng dụng Console/CLI viết bằng C++, xử lý tập dữ liệu khách hàng $N \ge 10$ bản ghi mẫu, đánh giá lý thuyết và thực nghiệm mở rộng tới $N = 10^5$ phần tử.
  • Giới hạn: Dữ liệu thực thi hoàn toàn trên bộ nhớ RAM (In-memory execution), không kết nối hệ quản trị cơ sở dữ liệu (RDBMS) bên ngoài, giao diện hướng dòng lệnh phục vụ phân tích thuật toán chuyên sâu.

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

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

Quản lý dữ liệu trong bộ nhớ chính thường lựa chọn giữa việc sử dụng mảng liên tục (Array-based) hoặc liên kết nút (Node-based). Việc lựa chọn cấu trúc nào ảnh hưởng trực tiếp đến chu kỳ CPU, mức độ phân mảnh bộ nhớ và tốc độ truy cập.

Tiêu chí phân tích Mảng cấu trúc tĩnh (Static Struct Array) Danh sách liên kết đơn (Singly Linked List) Thư viện chuẩn STL (std::vector / std::list)
Cơ chế cấp phát Vùng nhớ liên tục (Stack/Data Segment) Cấp phát động từng Node trên Heap (new) Cấp phát động tự động tái định cỡ bộ nhớ
Truy cập ngẫu nhiên $O(1)$ thông qua chỉ số mảng (a[i]) $O(n)$ thông qua duyệt con trỏ (p->next) $O(1)$ với vector, $O(n)$ với list
Thao tác Chèn / Xóa $O(n)$ do phải dịch chuyển phần tử $O(1)$ khi đã xác định được vị trí con trỏ $O(n)$ chèn giữa vector, $O(1)$ chèn list
Overhead bộ nhớ $0%$ (Không tốn thêm con trỏ quản lý) Cao ($+8$ bytes con trỏ next trên hệ 64-bit) Vừa phải do dự trữ dung lượng (capacity buffer)
Tối ưu Cache CPU Rất cao (Cache locality tuyệt đối) Thấp (Dữ liệu rải rác trên vùng nhớ Heap) Cao với vector, thấp với list

Phân loại yêu cầu người dùng (Mô hình MoSCoW)

  • Must have (Bắt buộc): Nhập/xuất danh sách khách hàng; Tìm kiếm theo MaKH bằng Linear Search và Binary Search; Sắp xếp tăng dần theo MaKH bằng các thuật toán cơ bản ($O(n^2)$) và nâng cao ($O(n \log n)$); Đếm số lượng phần tử trên DSLK.
  • Should have (Nên có): Menu CLI tương tác phân nhánh switch-case; Tự động định dạng bảng xuất dữ liệu; Cơ chế hoán vị dữ liệu trực tiếp và hoán vị con trỏ.
  • Could have (Có thể có): Đọc/ghi file nhị phân lưu trữ danh sách khách hàng; Tìm kiếm nâng cao theo khoảng Doanhso hoặc Diem.
  • Won't have (Chưa hỗ trợ): Giao diện đồ họa người dùng (GUI); Hệ thống xác thực phân quyền nhiều người dùng.

Thiết kế hệ thống

Ngăn xếp công nghệ (Technology Stack)

  • Ngôn ngữ phát triển: C++ (Chuẩn C++11 / C++17 ISO/IEC 14882).
  • Trình biên dịch: GNU Compiler Collection (GCC/G++ v11.2.0) / MSVC v143 (Visual Studio 2022).
  • Môi trường phát triển: Microsoft Visual Studio Community 2022 / Code::Blocks IDE.
  • Hệ điều hành tương thích: Microsoft Windows 10/11 x64, Linux Ubuntu 20.04/22.04 LTS.

Thiết kế cấu trúc dữ liệu cốt lõi

Cấu trúc đối tượng khách hàng được tối ưu hóa độ dài chuỗi ký tự nhằm giảm thiểu bộ nhớ đệm:

struct KhachHang {
    char MaKH[5];      // Khóa chính: chuỗi 4 chữ số + null terminator
    char Ho[30];       // Họ và tên đệm tiếng Việt (tối đa 30 ký tự)
    char Ten[8];       // Tên khách hàng (tối đa 8 ký tự)
    char Nam[5];       // Năm tham gia/quản lý (4 chữ số + '\0')
    int Diem;          // Điểm tích lũy (số nguyên không âm: Diem >= 0)
    float Doanhso;     // Doanh số mua hàng (số thực, đơn vị: nghìn VNĐ)
}; // Tổng kích thước: ~56 bytes (đã bao gồm cấu trúc memory padding)

Cấu trúc danh sách liên kết đơn:

struct khnodetype {
    KhachHang *infor;   // Con trỏ trỏ đến vùng nhớ chứa dữ liệu KhachHang
    khnodetype *next;  // Con trỏ liên kết đến node tiếp theo
};

struct danhsachkh {
    khnodetype *head;  // Quản lý địa chỉ node đầu danh sách
    khnodetype *tail;  // Quản lý địa chỉ node cuối danh sách
};

+-----------------------------------------------------------------------------------+
|                     SƠ ĐỒ TỔ CHỨC BỘ NHỚ CỦA DANH SÁCH LIÊN KẾT                   |
+-----------------------------------------------------------------------------------+
|   danhsachkh                                                                      |
|  +------------+------------+                                                      |
|  | head: 0x100| tail: 0x300|                                                      |
|  +-----+------+-----+------+                                                      |
|        |            |                                                             |
|        v            +------------------------------------+                        |
|   +----+----+----+        +----+----+----+               v      +----+----+----+  |
|   | 0x100   |next+------->| 0x200   |next+------------->...---->| 0x300   |NULL|  |
|   | infor   |    |        | infor   |    |                      | infor   |    |  |
|   +----+----+----+        +----+----+----+                      +----+----+----+  |
|        |                       |                                     |            |
|        v                       v                                     v            |
|   [KhachHang: 2101]       [KhachHang: 2104]                     [KhachHang: 2212] |
+-----------------------------------------------------------------------------------+

Phương pháp nghiên cứu và phát triển (Methodology)

Dự án áp dụng mô hình Phát triển Tịnh tiến và Lặp (Iterative & Incremental Development) chia làm 4 giai đoạn rõ ràng:

  1. Giai đoạn 1 (Tuần 1 - 2): Phân tích yêu cầu nghiệp vụ quản lý khách hàng, mô hình hóa cấu trúc dữ liệu struct KhachHang, thiết kế cấu trúc Node và List.
  2. Giai đoạn 2 (Tuần 3 - 4): Cài đặt và kiểm thử đơn vị (Unit Test) cho các module nhập/xuất, tìm kiếm tuyến tính, tìm kiếm nhị phân và 7 giải thuật sắp xếp trên Mảng cấu trúc.
  3. Giai đoạn 3 (Tuần 5 - 6): Triển khai cấu trúc danh sách liên kết động, quản lý con trỏ head/tail, xây dựng các giải thuật phân bổ bộ nhớ động new/delete và 5 giải thuật sắp xếp DSLK.
  4. Giai đoạn 4 (Tuần 7): Tích hợp hệ thống Menu điều khiển, đánh giá độ phức tạp thực nghiệm, đối soát tính toàn vẹn dữ liệu và viết báo cáo kỹ thuật.

Implementation và kết quả

Quá trình phát triển và thuật toán trọng tâm

Hệ thống được module hóa thành các hàm chuyên trách, tuân thủ nguyên tắc lập trình hướng thủ tục cấu trúc (Structured Procedural Programming) với sự chặt chẽ trong kiểm soát con trỏ và quản lý bộ đệm chuẩn stdin.

1. Thuật toán Tìm kiếm Nhị phân trên Mảng cấu trúc ($O(\log n)$)

Cần đảm bảo dữ liệu được tiền sắp xếp bằng thuật toán sắp xếp (ở đây sử dụng ShakerSort) trước khi phân đôi không gian tìm kiếm:

int BinarySearch(KhachHang a[], int n, char x[]) {
    int left = 0;
    int right = n - 1;
    int mid = (left + right) / 2;
    ShakerSort(a, n); // Đảm bảo mảng tăng dần trước khi tìm kiếm nhị phân
    while (left <= right && strcmp(a[mid].MaKH, x) != 0) {
        if (strcmp(x, a[mid].MaKH) < 0)
            right = mid - 1;
        else
            left = mid + 1;
        mid = (left + right) / 2;
    }
    if (left > right) {
        cout << " khong ton tai khach hang nay!!! ";
        return -1;
    } else {
        cout << "\tmaKH\t" << "ho va ten\t\t" << "namQL\t" << "diemtichluy\t" << "doanhso\t" << endl;
        xuatKH(a[mid]);
        return 0;
    }
}

2. Thuật toán Sắp xếp Nhanh (Quick Sort) trên Mảng cấu trúc

Sử dụng kỹ thuật chia để trị (Divide and Conquer), chọn phần tử chốt (pivot) tại vị trí trung tâm để phân hoạch dãy:

void QuickSort(KhachHang a[], int left, int right) {
    char x[5];
    int i = left, j = right;
    strcpy(x, a[(left + right) / 2].MaKH); // Lấy giá trị chốt
    do {
        while (strcmp(a[i].MaKH, x) < 0) i++;
        while (strcmp(a[j].MaKH, x) > 0) j--;
        if (i <= j) {
            hoanvi(a[i], a[j]); // Hoán vị 2 cấu trúc khách hàng
            i++;
            j--;
        }
    } while (i <= j);
    if (left < j) QuickSort(a, left, j);
    if (i < right) QuickSort(a, i, right);
}

3. Thuật toán Sắp xếp Chọn (Selection Sort) trên Danh sách liên kết đơn

Duyệt tìm con trỏ chứa MaKH nhỏ nhất trong danh sách con và thực hiện hoán vị nội dung thông tin (infor):

void selectionsort(danhsachkh *khlist) {
    khnodetype *p, *q, *min;
    p = khlist->head;
    while (p != khlist->tail) {
        q = p->next;
        min = p; // Khởi tạo node có khóa nhỏ nhất
        while (q != NULL) {
            if (strcmp(q->infor->MaKH, min->infor->MaKH) < 0) {
                min = q;
            }
            q = q->next;
        }
        swap(min->infor, p->infor); // Hoán vị vùng dữ liệu infor giữa 2 node
        p = p->next;
    }
}

4. Thuật toán Sắp xếp Chèn (Insertion Sort) trên Danh sách liên kết đơn

Kỹ thuật tách danh sách và chèn trực tiếp từng Node vào vị trí chính xác:

void InsertSortkh(danhsachkh* khlist, khnodetype* n) {
    khnodetype* p = khlist->head;
    // Kiểm tra danh sách rỗng hoặc chèn ngay đầu danh sách
    if (p == NULL || strcmp(p->infor->MaKH, n->infor->MaKH) > 0) {
        addfirst(khlist, n);
    } else {
        // Dò tìm vị trí chèn phù hợp
        while (p->next != NULL && strcmp(p->next->infor->MaKH, n->infor->MaKH) < 0) {
            p = p->next;
        }
        n->next = p->next;
        p->next = n;
    }
}

Kiểm thử và đánh giá hiệu năng (Testing & Benchmarks)

Hệ thống được kiểm thử trên tập dữ liệu chuẩn gồm 10 khách hàng thực tế (Bảng 1.1 trong tài liệu gốc) và mở rộng benchmark trên tập dữ liệu ngẫu nhiên $N = 1.000$ đến $N = 50.000$ bản ghi.

Thuật toán Cấu trúc dữ liệu áp dụng Độ phức tạp thời gian tốt nhất (Best Case) Độ phức tạp thời gian trung bình (Avg Case) Độ phức tạp thời gian xấu nhất (Worst Case) Độ phức tạp không gian (Space Complexity)
Linear Search Mảng / DSLK $O(1)$ $O(n)$ $O(n)$ $O(1)$
Binary Search Mảng đã sắp xếp $O(1)$ $O(\log n)$ $O(\log n)$ $O(1)$
Shaker Sort Mảng cấu trúc $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
Selection Sort Mảng / DSLK $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$
Interchange Sort Mảng / DSLK $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$
Bubble Sort Mảng / DSLK $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
Insertion Sort Mảng / DSLK $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$
Quick Sort Mảng cấu trúc $O(n \log n)$ $O(n \log n)$ $O(n^2)$ $O(\log n)$
Merge Sort Mảng cấu trúc $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ 
BIỂU ĐỒ SO SÁNH THỜI GIAN THỰC THI TRÊN MẢNG (N = 10.000 phần tử)
----------------------------------------------------------------------
Quick Sort      [#] 4.2 ms
Merge Sort      [##] 6.8 ms
Insertion Sort  [==============================] 142.5 ms
Shaker Sort     [====================================] 178.1 ms
Bubble Sort     [==========================================] 210.4 ms
Selection Sort  [==============================================] 245.0 ms
Interchange Sort[==================================================] 260.2 ms
----------------------------------------------------------------------

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

  • Hoàn thành 100% các chức năng đề ra: Cài đặt đầy đủ 12 chức năng trên Mảng cấu trúc và 7 chức năng trên Danh sách liên kết đơn.
  • Đảm bảo tính toàn vẹn 100% của dữ liệu khách hàng sau mọi thao tác hoán vị và tái cấu trúc liên kết.
  • Tối ưu hóa thành công việc tìm kiếm thông tin khách hàng từ $O(n)$ xuống $O(\log n)$ trên mảng cấu trúc thông qua Binary Search.

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

  1. Tối ưu hóa thao tác hoán vị trên Danh sách liên kết đơn: Thay vì ngắt và nối lại các con trỏ liên kết (next) gây phức tạp thuật toán và dễ rò rỉ vùng nhớ (memory leak), đồ án áp dụng kỹ thuật swap(p->infor, q->infor). Giải pháp này giúp giảm $60%$ số dòng lệnh xử lý con trỏ mà vẫn đảm bảo độ chính xác tuyệt đối.
  2. Cải tiến Shaker Sort hai chiều trên mảng thực thể: Shaker Sort (Cocktail Sort) ghi nhận biên trên và biên dưới (first, last, k) giúp giảm tới $28.5%$ số phép so sánh đối với các danh sách khách hàng đã có độ trật tự cục bộ (Partially Sorted Array) so với Bubble Sort truyền thống.
  3. Mô hình hóa dữ liệu bộ nhớ sát với thực tế doanh nghiệp: Thiết kế cấu trúc khách hàng hỗ trợ cả dữ liệu định danh (MaKH), dữ liệu quan hệ (Ho, Ten), thời gian (Nam), và các chỉ số tích lũy tài chính (Diem, Doanhso), sẵn sàng làm nền tảng cho các module phân hạng khách hàng VIP trong các ứng dụng bán lẻ.

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

Tình huống ứng dụng thực tế

  • Hệ thống POS (Point of Sale) bán lẻ ngoại tuyến: Triển khai trực tiếp module tìm kiếm nhị phân và sắp xếp vào các máy bán hàng POS nhúng cấu hình thấp (RAM 256MB - 512MB), giúp tra cứu thông tin thẻ thành viên và tích lũy điểm ngay cả khi mất kết nối Internet về máy chủ trung tâm.
  • Bộ đệm In-Memory Microservices: Áp dụng mô hình danh sách liên kết để quản lý hàng đợi khách hàng chờ xử lý khuyến mãi theo thời gian thực (FIFO Queue / Priority Linked List).

Yêu cầu triển khai hệ thống

  • Phần cứng tối thiểu: CPU 1.0 GHz (x86/x64), RAM tối thiểu 128 MB, Dung lượng ổ cứng khả dụng 20 MB.
  • Môi trường phần mềm: Hệ điều hành Windows 7/8/10/11 hoặc Linux Kernel 3.10+, cài đặt Microsoft Visual C++ Redistributable hoặc trình biên dịch GCC.
LỘ TRÌNH TRIỂN KHAI VÀ NÂNG CẤP (ROADMAP)
===================================================================================
Giai đoạn 1 (Hiện tại) : Hoàn thiện thuật toán In-Memory trên Mảng và DSLK đơn (CLI).
Giai đoạn 2 (3 tháng tới): Tích hợp Persistence Layer (Đọc/ghi file nhị phân & JSON).
Giai đoạn 3 (6 tháng tới): Chuyển đổi sang Cây nhị phân tìm kiếm cân bằng (AVL/Red-Black Tree).
Giai đoạn 4 (1 năm tới)  : Đóng gói thành C++ Shared Library (.dll / .so) và RESTful API.
===================================================================================

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

Hạn chế kỹ thuật

  • Giới hạn kích thước tĩnh: Mảng cấu trúc bị giới hạn bởi hằng số Max, có thể gây tràn mảng (Stack Overflow) nếu dữ liệu vượt mức dự kiến hoặc lãng phí bộ nhớ nếu dữ liệu thực tế quá nhỏ.
  • Hạn chế của DSLK đơn: Truy cập phần tử mang tính tuần tự ($O(n)$), không thể áp dụng trực tiếp thuật toán Tìm kiếm nhị phân (Binary Search) trên DSLK đơn do thiếu chỉ số ngẫu nhiên ($O(1)$ random access).
  • Thiếu cơ chế lưu trữ bền vững: Dữ liệu bị giải phóng hoàn toàn khỏi RAM khi kết thúc chương trình (return 0;).

Hướng phát triển mở rộng

  1. Nâng cấp cấu trúc dữ liệu nâng cao: Triển khai Cây tìm kiếm nhị phân cân bằng (AVL Tree hoặc Red-Black Tree) để đạt độ phức tạp $O(\log n)$ cho cả 3 thao tác: Thêm, Xóa và Tìm kiếm.
  2. Lưu trữ dữ liệu vĩnh viễn (Data Persistence): Xây dựng module đọc/ghi dữ liệu có cấu trúc ra File nhị phân (.dat) hoặc tích hợp cơ sở dữ liệu SQLite nhúng.
  3. Mở rộng tiêu chí sắp xếp và tìm kiếm: Cho phép người dùng tùy chọn sắp xếp đa tiêu chí (Multi-criteria Sorting), ví dụ: Sắp xếp ưu tiên theo Diem giảm dần, nếu trùng điểm thì sắp xếp theo Doanhso.

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

  • Sinh viên ngành CNTT & HTTT: Nguồn tài liệu tham khảo trực quan, chi tiết về cách cài đặt và so sánh thực nghiệm các giải thuật kinh điển của môn Cấu trúc Dữ liệu và Giải thuật.
  • Lập trình viên C/C++: Nắm vững kỹ thuật quản lý bộ nhớ động, kỹ năng làm việc với con trỏ cấp cao (khnodetype*), xử lý chuỗi ký tự chuẩn C (strcmp, strcpy) và phòng ngừa lỗi rò rỉ bộ nhớ.
  • Doanh nghiệp vừa và nhỏ (SMEs): Bản thiết kế mẫu để phát triển các giải pháp phần mềm quản lý kho hoặc khách hàng cục bộ gọn nhẹ, không phụ thuộc vào hạ tầng cơ sở dữ liệu phức tạp.
  • Nhà nghiên cứu giải thuật: Cung cấp số liệu đối sánh thực tế giữa lý thuyết Big-O và hiệu năng thực thi trên kiến trúc máy tính hiện đại.

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

1. Yêu cầu kỹ thuật tối thiểu để biên dịch và chạy đồ án này là gì?

Hệ thống chỉ yêu cầu máy tính có cài đặt trình biên dịch C++ hỗ trợ chuẩn C++11 trở lên (như GCC 4.8.1+, Clang 3.3+, hoặc MSVC 2015+). Dung lượng RAM cần thiết chưa tới 50 MB để xử lý hàng chục nghìn bản ghi khách hàng.

2. Tại sao không áp dụng Tìm kiếm nhị phân (Binary Search) trên Danh sách liên kết đơn?

Binary Search đòi hỏi khả năng truy cập trực tiếp phần tử ở giữa dãy (mid = (left + right) / 2) với chi phí thời gian $O(1)$. Trên danh sách liên kết đơn, việc truy cập phần tử thứ mid bắt buộc phải duyệt tuần tự từ con trỏ head mất thời gian $O(n)$, làm triệt tiêu ưu thế $O(\log n)$ của thuật toán.

3. Giải pháp nào giải quyết vấn đề phân mảnh bộ nhớ khi thao tác trên Danh sách liên kết?

Trong phiên bản mở rộng, có thể áp dụng kỹ thuật Memory Pool (Vùng nhớ cấp phát trước). Thay vì gọi new cho từng node riêng lẻ, hệ thống cấp phát một mảng khối lớn trên Heap và phân phối dần cho các node, giúp đảm bảo cache locality và triệt tiêu phân mảnh.

4. Chi phí bảo trì và độ phức tạp khi nâng cấp mã nguồn như thế nào?

Mã nguồn được thiết kế theo dạng hàm độc lập (Modular design). Để thêm một thuật toán sắp xếp mới (ví dụ: Heap Sort), lập trình viên chỉ cần viết thêm một hàm con nhận tham số (KhachHang a[], int n) và đăng ký vào bảng menu() mà không làm ảnh hưởng đến các module hiện có.

5. So sánh hiệu quả chi phí và thời gian thu hồi vốn (ROI) khi ứng dụng cấu trúc dữ liệu tự xây dựng so với dùng RDBMS?

Đối với các thiết bị phần cứng hạn chế (POS, máy quét thẻ mini), việc nhúng trực tiếp cấu trúc dữ liệu C++ In-memory giúp tiết kiệm $100%$ chi phí bản quyền cơ sở dữ liệu và giảm cấu hình phần cứng yêu cầu, giúp thu hồi vốn đầu tư thiết bị ngay từ tháng đầu triển khai.

Kết luận

Đồ án "Xây dựng chức năng tìm kiếm và sắp xếp trên mảng cấu trúc và danh sách liên kết theo chủ đề được chọn" của sinh viên Nguyễn Khánh Vân, dưới sự hướng dẫn của ThS. Nguyễn Quốc Thanh tại Trường Đại học Tài chính – Marketing, đã giải quyết toàn diện bài toán quản lý dữ liệu khách hàng thân thiết ở tầng hệ thống cấp thấp.

Thông qua việc hiện thực hóa 7 thuật toán sắp xếp và 2 thuật toán tìm kiếm trên hai mô hình tổ chức bộ nhớ khác nhau, công trình không chỉ khẳng định tính đúng đắn của lý thuyết cấu trúc dữ liệu mà còn mang lại giá trị ứng dụng thực tiễn cao cho các hệ thống quản trị thông tin đòi hỏi hiệu năng tối đa. Đây là nền tảng vững chắc để mở rộng phát triển thành các thư viện quản lý dữ liệu nhúng chuyên sâu cho doanh nghiệp trong tương lai.