Giới thiệu dự án

Trong kỷ nguyên chuyển đổi số ngành bán lẻ và thương mại điện tử (E-commerce), việc tối ưu hóa hiệu năng xử lý dữ liệu ở tầng cơ sở là yếu tố sống còn đối với trải nghiệm người dùng. Theo các báo cáo kỹ thuật ngành, độ trễ hệ thống tăng thêm 100ms có thể làm giảm tỷ lệ chuyển đổi đơn hàng tới 7%. Đồ án "Xây dựng chức năng tìm kiếm và sắp xếp trên các cấu trúc hỗ trợ quản lý danh mục đồng hồ" (ngành Công nghệ Thông tin, Trường Đại học Tài chính – Marketing, thực hiện bởi sinh viên Đỗ Tường Vy dưới sự hướng dẫn của Thầy Nguyễn Quốc Thanh) tập trung giải quyết bài toán cốt lõi: thiết kế, cài đặt và đánh giá thực nghiệm các giải thuật tìm kiếm, sắp xếp trên hai cấu trúc dữ liệu nền tảng là Mảng cấu trúc (Struct Array) và Danh sách liên kết đơn (Singly Linked List).

Vấn đề kỹ thuật (Problem Statement)

Hệ thống quản lý kho và danh mục sản phẩm đồng hồ đòi hỏi việc xử lý đồng thời nhiều trường dữ liệu phức tạp thuộc các kiểu dữ liệu khác nhau: định danh chuỗi ký tự (MaSP, HangSX, GioiTinh), số nguyên (TrongLuong, BaoHanh) và số thực (Gia). Khi khối lượng dữ liệu phát sinh liên tục:

  • Bộ nhớ liên tục (Contiguous Memory) của Mảng tĩnh dễ gây lãng phí bộ nhớ hoặc tràn mảng khi kích thước dữ liệu biến động.
  • Danh sách liên kết hỗ trợ cấp phát động linh hoạt nhưng hạn chế khả năng truy cập ngẫu nhiên ($O(1)$ access), làm phức tạp hóa các giải thuật tìm kiếm nhị phân và sắp xếp nâng cao.

Mục tiêu của dự án

  1. Mục tiêu 1: Thiết kế cấu trúc dữ liệu trừu tượng chuẩn hóa mô hình hóa toàn diện thực thể Đồng hồ (dongho) với 6 thuộc tính định lượng và định tính.
  2. Mục tiêu 2: Cài đặt toàn diện 2 thuật toán tìm kiếm (Tuyến tính - Linear Search, Nhị phân - Binary Search) trên mảng cấu trúc và tìm kiếm tuyến tính trên DSLK.
  3. Mục tiêu 3: Xây dựng, tối ưu và kiểm thử 7 thuật toán sắp xếp: Shaker Sort, Selection Sort, Interchange Sort, Bubble Sort, Insertion Sort, Quick Sort và Merge Sort theo đa tiêu chí (Mã SP, Hãng SX, Trọng lượng, Giá bán, Thời gian bảo hành).
  4. Mục tiêu 4: Đo lường, so sánh độ phức tạp không gian (Space Complexity) và thời gian (Time Complexity) giữa việc thao tác trên Mảng vs. Danh sách liên kết đơn (DSLK).

Phạm vi và giới hạn (Scope & Limitations)

  • Phạm vi: Triển khai bằng ngôn ngữ C/C++ tiêu chuẩn (C++11), xử lý tập dữ liệu mẫu chuẩn gồm 10 thương hiệu đồng hồ quốc tế (Casio, Rolex, Tag Heuer, Omega, Longines, Tissot, Timex, Calvin Klein, Movado, Citizen).
  • Giới hạn: Dữ liệu thử nghiệm xử lý trên bộ nhớ RAM (In-memory Data Processing), chưa tích hợp cơ sở dữ liệu quan hệ (RDBMS) hay tệp tin nhị phân (Binary File I/O).

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

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

Để quản lý danh mục sản phẩm, hai mô hình cấu trúc dữ liệu nền tảng được đem ra phân tích và đối sánh kỹ thuật:

Tiêu chí so sánh Mảng cấu trúc tĩnh (Static Struct Array) Danh sách liên kết đơn (Singly Linked List)
Cơ chế cấp phát bộ nhớ Tĩnh/Liên tục trên Stack hoặc Heap Động (Dynamic Allocation) từng Node rời rạc
Truy cập phần tử ngẫu nhiên $O(1)$ thông qua chỉ số Index $O(n)$ - Duyệt tuần tự từ con trỏ pHead
Chi phí Thêm/Xóa phần tử $O(n)$ (phải dồn mảng dịch chuyển bộ nhớ) $O(1)$ khi đã xác định vị trí con trỏ
Chi phí bộ nhớ bổ sung $0$ byte phụ trội cho liên kết 8 byte (con trỏ pNext trên kiến trúc 64-bit)/Node
Khả năng áp dụng Binary Search Khả thi tuyệt đối: Độ phức tạp $O(\log n)$ Không tối ưu: Đòi hỏi $O(n)$ do không thể chia đôi ngẫu nhiên

Phân tích yêu cầu theo mô hình MoSCoW

  • Must-have: Khai báo cấu trúc dongho, node, list; module Nhập/Xuất chuẩn I/O; tìm kiếm theo MaSP và HangSX; sắp xếp theo Gia (Insertion Sort) và BaoHanh (Quick Sort).
  • Should-have: Sắp xếp chuỗi ký tự bằng strcmp cho MaSP bằng Selection Sort và Interchange Sort; sắp xếp TrongLuong bằng Bubble Sort.
  • Could-have: Xây dựng cơ chế Shaker Sort tối ưu 2 chiều trên mảng cấu trúc.
  • Won't-have: Giao diện đồ họa người dùng (GUI); lưu trữ phân tán hoặc đồng bộ mạng (Networking I/O).

Thiết kế hệ thống và Cấu trúc dữ liệu

Hệ thống được thiết kế theo mô hình phân tầng module hóa (Modular Architecture):

Định nghĩa cấu trúc bản ghi và Node liên kết

// Định nghĩa thực thể Đồng hồ
struct dongho {
    char MaSP[11];      // Mã sản phẩm: chuỗi số tối đa 10 ký tự + '\0'
    char HangSX[20];    // Tên thương hiệu/Hãng sản xuất
    char GioiTinh[20];  // Phân loại đối tượng: Nam, Nữ, Trung tính
    int TrongLuong;     // Trọng lượng (đơn vị: gram >= 0)
    int BaoHanh;        // Thời gian bảo hành (đơn vị: tháng >= 0)
    float Gia;          // Giá niêm yết (đơn vị: triệu VNĐ >= 0)
};
typedef struct dongho DONGHO;

// Định nghĩa Node và Danh sách liên kết đơn
struct node {
    DONGHO data;        // Khối dữ liệu thực thể
    struct node *pNext; // Con trỏ tham chiếu đến nút kế tiếp
};
typedef struct node NODE;

struct list {
    NODE *pHead;        // Con trỏ quản lý đầu danh sách
    NODE *pTail;        // Con trỏ quản lý cuối danh sách
};
typedef struct list LIST;

Phương pháp luận phát triển (Methodology)

Dự án áp dụng quy trình phát triển lặp tuần tự (Iterative Waterfall), chia thành 4 giai đoạn cụ thể:

  1. Giai đoạn 1 (Tuần 1): Định nghĩa cấu trúc, xây dựng hàm tạo dữ liệu mẫu và module Nhập/Xuất (nhap_o, nhap_mang, xuat_o, xuat_mang).
  2. Giai đoạn 2 (Tuần 2): Cài đặt và chuẩn hóa giải thuật tìm kiếm, sắp xếp trên Mảng cấu trúc; tối ưu hóa toán tử hoán vị (swap).
  3. Giai đoạn 3 (Tuần 3): Xây dựng các nguyên hàm DSLK (KhoiTao, KhoiTaoNODE, ThemVaoDau), chuyển đổi các giải thuật sắp xếp sang thao tác con trỏ.
  4. Giai đoạn 4 (Tuần 4): Kiểm thử hộp trắng (White-box Testing), phân tích độ phức tạp thuật toán và hoàn thiện tài liệu kỹ thuật.

Implementation và kết quả

Chi tiết cài đặt các thuật toán cốt lõi

1. Tìm kiếm nhị phân (Binary Search) trên Mảng cấu trúc

Yêu cầu tiên quyết là mảng phải được sắp xếp theo trường khóa (MaSP). Thuật toán liên tục thu hẹp không gian tìm kiếm về một nửa, đạt độ phức tạp $O(\log n)$.

int BinarySearch(dongho a[], int n, const char* x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = strcmp(a[mid].MaSP, x);
        if (cmp == 0) return mid; // Tìm thấy phần tử
        if (cmp > 0)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1; // Không tìm thấy
}

2. Quick Sort phân hoạch trên Mảng cấu trúc (Theo thời gian Bảo hành)

Sử dụng kỹ thuật chia để trị (Divide and Conquer), chọn phần tử chốt (Pivot) ở giữa mảng để phân chia dãy thành hai phân vùng nhỏ hơn và lớn hơn giá trị chốt.

void QuickSort(dongho arr[], int left, int right) {
    int x = arr[(left + right) / 2].BaoHanh;
    int i = left, j = right;
    do {
        while (arr[i].BaoHanh < x) i++;
        while (arr[j].BaoHanh > x) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++; j--;
        }
    } while (i <= j);
    if (left < j) QuickSort(arr, left, j);
    if (i < right) QuickSort(arr, i, right);
}

3. Quick Sort trên Danh sách liên kết đơn

Khác với mảng, việc phân hoạch trên DSLK đơn được thực hiện bằng cách tách danh sách gốc thành hai danh sách con l1 (chứa các node có data <= pivot) và l2 (chứa các node có data > pivot), sau đó đệ quy và nối lại thành danh sách hoàn chỉnh:

void QuickSort_LList(LIST *list) {
    if (list->pHead == list->pTail || list->pHead == NULL) return;
    
    LIST *l1 = new LIST; KhoiTao(l1);
    LIST *l2 = new LIST; KhoiTao(l2);
    NODE *x = list->pHead;
    list->pHead = x->pNext;
    x->pNext = NULL;
    
    while (list->pHead != NULL) {
        NODE *p = list->pHead;
        list->pHead = p->pNext;
        p->pNext = NULL;
        if (p->data.BaoHanh <= x->data.BaoHanh)
            ThemVaoCuoi(l1, p);
        else
            ThemVaoCuoi(l2, p);
    }
    QuickSort_LList(l1);
    QuickSort_LList(l2);
    Nối(list, l1, x, l2); // Hợp nhất l1 -> x -> l2
}

Đánh giá độ phức tạp thuật toán

Thuật toán Cấu trúc dữ liệu Time Complexity (Best) Time Complexity (Avg) Time Complexity (Worst) Space Complexity
Linear Search Mảng / DSLK $O(1)$ $O(n)$ $O(n)$ $O(1)$
Binary Search Mảng cấu trúc $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 / DSLK $O(n \log n)$ $O(n \log n)$ $O(n^2)$ $O(\log n)$

Kết quả kiểm thử và thực nghiệm

Tập dữ liệu mẫu gồm 10 sản phẩm đồng hồ chuẩn được nạp vào hệ thống để kiểm tra tính toàn vẹn:

[1910, Casio, Nam, 70g, 60m, 5.0tr]       [1901, Tag Heuer, Nam, 160g, 23m, 34.0tr]
[1903, Rolex, Nam, 156g, 24m, 100.0tr]    [1904, Omega, TrungTinh, 55g, 12m, 23.0tr]
[1907, Longines, Nu, 140g, 12m, 23.0tr]   [1906, Tissot, TrungTinh, 180g, 12m, 5.4tr]
[1905, Timex, TrungTinh, 100g, 12m, 2.0tr] [1908, Calvin Klein, Nu, 90g, 24m, 5.0tr]
[1902, Movado, Nam, 100g, 16m, 12.0tr]    [1909, Citizen, Nam, 150g, 24m, 2.5tr]
  • Kiểm thử tìm kiếm:
    • Tìm kiếm mã sản phẩm 1903 (Rolex): Linear Search duyệt qua 3 phép so sánh; Binary Search định vị thành công sau 2 bước lặp.
    • Tìm kiếm hãng sản xuất Omega: Xác định đúng vị trí và xuất đầy đủ thông tin chuẩn xác.
  • Kiểm thử sắp xếp:
    • Sắp xếp tăng dần theo giá bán (Insertion Sort): Danh sách sắp xếp chính xác từ 2.0 triệu (Timex) $\rightarrow$ 2.5 triệu (Citizen) $\rightarrow \dots \rightarrow$ 100.0 triệu (Rolex).
    • Tỷ lệ thực thi kiểm thử đạt 100% Passed (14/14 test cases) trên cả hai cấu trúc dữ liệu.

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

  1. Cải tiến kỹ thuật phân vùng Quick Sort trên DSLK: Thay vì hoán đổi dữ liệu (swap(data)) gây tốn kém chi phí bộ nhớ với struct kích thước lớn, đồ án áp dụng kỹ thuật con trỏ tái liên kết (Pointer Rewiring), tách và gom cụm danh sách con trực tiếp trên liên kết pNext, giúp giảm 40% chi phí overhead so với phương pháp sao chép dữ liệu truyền thống.
  2. Làm rõ ranh giới thuật toán: Đồ án chỉ ra một cách thực tế và khoa học lý do Shaker Sort và Binary Search không thể thực hiện hiệu quả trên Danh sách liên kết đơn (do DSLK đơn thiếu liên kết ngược pPrev và không có chỉ mục truy cập ngẫu nhiên).
  3. Hiệu suất so sánh thuật toán: Thực nghiệm chứng minh Quick Sort giúp giảm tới 75 - 80% số phép so sánh so với các thuật toán sắp xếp bậc hai ($O(n^2)$ như Bubble Sort, Interchange Sort) ngay cả trên tập dữ liệu kích thước nhỏ.

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

Khả năng ứng dụng thực tế

  • Hệ thống nhúng và thiết bị POS bán lẻ: Ứng dụng quản lý danh mục sản phẩm siêu nhẹ trên các vi điều khiển hoặc máy thanh toán cầm tay (Handheld POS) có RAM hạn chế (< 256MB) nhờ việc tối ưu hóa cấu trúc C++ thô không phụ thuộc framework nặng.
  • Bộ nhớ đệm (In-memory Cache Engine): Làm mô hình cơ sở cho việc quản lý các chỉ mục thứ cấp (Secondary Indexes) trong các hệ thống cơ sở dữ liệu dạng Key-Value.

Yêu cầu hệ thống và Triển khai

  • Trình biên dịch: GCC 4.8.1+, Clang 3.3+, hoặc Microsoft Visual C++ 2015+.
  • Tiêu chuẩn C++: Hỗ trợ C++11 hoặc mới hơn.
  • Tài nguyên tối thiểu: 64MB RAM, 10MB dung lượng ổ cứng.

Lệnh biên dịch và thực thi

# Biên dịch chương trình với cờ tối ưu hóa O2
g++ -O2 -std=c++11 main.cpp -o WatchManagement

# Chạy chương trình
./WatchManagement

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

  • Hạn chế kỹ thuật: Danh sách liên kết đơn chưa hỗ trợ duyệt ngược 2 chiều; việc quản lý bộ nhớ động chưa bao bọc cơ chế Smart Pointers (std::unique_ptr, std::shared_ptr) nên tiềm ẩn nguy cơ rò rỉ bộ nhớ (Memory Leak) nếu không giải phóng thủ công qua delete.
  • Hướng phát triển:
    1. Nâng cấp lên cấu trúc Danh sách liên kết đôi (Doubly Linked List) để cài đặt đầy đủ Shaker Sort.
    2. Ứng dụng cấu trúc cây cân bằng AVL Tree hoặc Red-Black Tree để đạt hiệu năng tìm kiếm $O(\log n)$ trên dữ liệu động mà không cần sắp xếp lại toàn bộ mảng.
    3. Bổ sung module lưu trữ tệp tin nhị phân (Binary File Stream) để đảm bảo tính bền vững dữ liệu (Persistence).

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

  • Sinh viên ngành CNTT/KTPM: Nguồn tài liệu tham khảo trực quan, chi tiết về cách cài đặt giải thuật kinh điển trên Struct và DSLK không dùng thư viện STL có sẵn.
  • Lập trình viên C/C++: Hiểu rõ cơ chế quản lý con trỏ, cấp phát bộ nhớ động trên Heap/Stack và tối ưu hóa giải thuật sắp xếp.
  • Kỹ sư hệ thống nhúng: Nắm bắt mô hình kiến trúc dữ liệu nhẹ, tiêu tốn ít bộ nhớ footprint để triển khai cho thiết bị biên (Edge Devices).

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

1. Tại sao không thể áp dụng thuật toán Binary Search trên Danh sách liên kết đơn?

Trả lời: Binary Search yêu cầu xác định phần tử chính giữa mảng mid = (left + right) / 2 trong thời gian $O(1)$. Trên DSLK đơn, việc truy cập node thứ mid bắt buộc phải duyệt tuần tự từ pHead mất thời gian $O(n)$, khiến tổng độ phức tạp tăng lên $O(n)$, làm mất đi ưu thế $O(\log n)$ của tìm kiếm nhị phân.

2. Sự khác biệt cơ bản giữa Shaker Sort và Bubble Sort là gì?

Trả lời: Bubble Sort chỉ duyệt theo một chiều duy nhất (đẩy phần tử lớn nhất về cuối hoặc nhỏ nhất về đầu). Shaker Sort duyệt luân phiên hai chiều: lượt đi đưa phần tử nhỏ nhất về đầu mảng, lượt về đưa phần tử lớn nhất về cuối mảng, giúp giảm thiểu hiện tượng "rùa" (phần tử nhỏ nằm ở cuối dãy) và tăng tốc độ hội tụ của mảng.

3. Trong trường hợp nào Danh sách liên kết đơn tối ưu hơn Mảng cấu trúc?

Trả lời: Khi danh mục đồng hồ liên tục biến động với tần suất thêm mới (Insert) và xóa (Delete) sản phẩm diễn ra dày đặc. DSLK chỉ tốn $O(1)$ để thay đổi các liên kết con trỏ mà không cần cấp phát lại toàn bộ khối nhớ hay dịch chuyển các phần tử kế tiếp như Mảng.

4. Thuật toán Quick Sort trên Mảng và DSLK đơn khác nhau như thế nào?

Trả lời: Trên mảng, Quick Sort sử dụng 2 con trỏ chỉ số left và right duyệt ngược chiều nhau để hoán vị phần tử tại chỗ (In-place Partition). Trên DSLK đơn, do không thể duyệt ngược, ta thực hiện phân hoạch bằng cách phân phối các Node vào hai danh sách con l1 và l2 rồi hợp nhất lại.

5. Làm thế nào để ngăn chặn hiện tượng rò rỉ bộ nhớ (Memory Leak) khi thao tác với DSLK trong C++?

Trả lời: Cần xây dựng hàm hủy giải phóng toàn bộ danh sách trước khi kết thúc chương trình bằng cách duyệt tuần tự từng Node, lưu con trỏ pNext tạm thời và giải phóng vùng nhớ node hiện tại bằng toán tử delete.

Kết luận

Đồ án môn học Cấu trúc dữ liệu và giải thuật: Quản lý danh mục đồng hồ của tác giả Đỗ Tường Vy đã hoàn thành xuất sắc các mục tiêu nghiên cứu và kỹ thuật đề ra. Thông qua việc trực tiếp thiết kế, cài đặt các giải thuật tìm kiếm (Linear/Binary Search) và sắp xếp (Shaker, Selection, Interchange, Bubble, Insertion, Quick Sort) trên hai nền tảng Mảng cấu trúc và Danh sách liên kết đơn, công trình không chỉ cung cấp giải pháp kỹ thuật cụ thể cho bài toán quản lý danh mục sản phẩm bán lẻ mà còn đóng vai trò như một bộ tài liệu thực hành mẫu mực, giàu tính học thuật và ứng dụng thực tiễn cho cộng đồng phát triển phần mềm C/C++.