Bối cảnh và vấn đề nghiên cứu

Đồ án môn học "Cấu trúc dữ liệu và giải thuật" do sinh viên Đỗ Tường Vy (MSSV: 2021010354, Lớp 20DHT05) thực hiện dưới sự hướng dẫn của giảng viên Nguyễn Quốc Thanh tại Khoa Công nghệ Thông tin, Trường Đại học Tài chính – Marketing (hoàn thành vào tháng 12/2020 tại TP. Hồ Chí Minh).

Trong khoa học máy tính và kỹ thuật lập trình, việc lựa chọn cấu trúc dữ liệu và giải thuật xử lý phù hợp là yếu tố quyết định đến hiệu năng của hệ thống phần mềm. Đề tài xuất phát từ bài toán thực tế về quản lý danh mục sản phẩm kinh doanh: xây dựng các chức năng tìm kiếm và sắp xếp dữ liệu trên các cấu trúc lưu trữ khác nhau nhằm phục vụ công tác quản lý thông tin các mặt hàng đồng hồ tại một đơn vị kinh doanh.

Mục tiêu và nhiệm vụ nghiên cứu của đồ án được xác định cụ thể như sau:

  1. Xác định và định nghĩa cấu trúc dữ liệu đại diện cho thực thể sản phẩm đồng hồ cùng các ràng buộc về kiểu dữ liệu.
  2. Xây dựng tập dữ liệu mẫu gồm tối thiểu 10 đối tượng để phục vụ kiểm thử.
  3. Thiết kế, cài đặt và kiểm thử các giải thuật tìm kiếm (tìm kiếm tuyến tính, tìm kiếm nhị phân) và sắp xếp (Shaker Sort, Selection Sort, Interchange Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort) trên cấu trúc mảng một chiều các bản ghi (mảng cấu trúc).
  4. Thiết kế, định nghĩa và cài đặt các thao tác cơ bản cùng các giải thuật tìm kiếm và sắp xếp trên cấu trúc danh sách liên kết đơn; đồng thời đối chiếu, phân tích khả năng áp dụng của từng thuật toán trên cấu trúc này.

Đối tượng nghiên cứu của đề tài là cấu trúc dữ liệu mảng cấu trúc, danh sách liên kết đơn cùng các thuật toán tìm kiếm và sắp xếp kinh điển trong ngôn ngữ lập trình C/C++. Phạm vi nghiên cứu giới hạn trong phạm vi học phần Cấu trúc dữ liệu và giải thuật, thực nghiệm trên tập dữ liệu quản lý thông tin đồng hồ với các trường thuộc tính quy chuẩn tại thời điểm tháng 12/2020.

Cơ sở lý thuyết và phương pháp

Về cơ sở lý thuyết, đồ án dựa trên hai cấu trúc dữ liệu lưu trữ dữ liệu trong bộ nhớ chính:

  • Mảng cấu trúc (Array of Structures): Tập hợp các phần tử có cùng kiểu cấu trúc được lưu trữ liên tiếp trong các ô nhớ, cho phép truy xuất ngẫu nhiên tới từng phần tử thông qua chỉ số (index).
  • Danh sách liên kết đơn (Singly Linked List): Tập hợp các nút (node) được cấp phát động trong bộ nhớ, mỗi nút gồm hai thành phần: thành phần dữ liệu (data) và con trỏ (tiep) trỏ tới nút kế tiếp. Danh sách được quản lý thông qua hai con trỏ đầu (pHead) và con trỏ cuối (pTail).
  • Các giải thuật tìm kiếm: Tìm kiếm tuyến tính (Linear Search) duyệt tuần tự từng phần tử; Tìm kiếm nhị phân (Binary Search) tìm kiếm trên tập dữ liệu đã có thứ tự bằng cách thu hẹp không gian tìm kiếm qua mỗi bước so sánh với phần tử ở giữa.
  • Các giải thuật sắp xếp: Giải thuật đổi chỗ trực tiếp (Interchange Sort), Sắp xếp chọn trực tiếp (Selection Sort), Sắp xếp nổi bọt (Bubble Sort), Sắp xếp chèn trực tiếp (Insertion Sort), Sắp xếp Shaker (Shaker Sort / Cock-tail Sort), Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort).

Phương pháp nghiên cứu được triển khai bao gồm:

  • Phương pháp mô hình hóa và thiết kế: Định nghĩa kiểu dữ liệu có cấu trúc dongho, phân tích các trường thuộc tính và miền giá trị tương ứng.
  • Phương pháp thực nghiệm lập trình: Cài đặt mã nguồn bằng ngôn ngữ lập trình C/C++, tách module thành các chương trình con (hàm chức năng) phục vụ nhập, xuất, tìm kiếm và sắp xếp.
  • Phương pháp kiểm thử (Testing): Xây dựng hàm main kiểm tra từng chương trình con với dữ liệu đầu vào cụ thể, đánh giá trường hợp tìm thấy (khóa tồn tại trong danh sách) và trường hợp không tìm thấy (khóa không tồn tại trong danh sách).

Nguồn dữ liệu sử dụng trong đồ án là bộ dữ liệu thực nghiệm gồm 10 sản phẩm đồng hồ thuộc các thương hiệu phổ biến trên thị trường:

STT Mã SP Hãng sản xuất Giới tính Trọng lượng
1 1910 Casio Nam 70g
2 1901 Tag Heuer Nam 160g
3 1903 Rolex Nam 156g
4 1904 Omega Trung tính 55g
5 1907 Longines Nữ 140g
6 1906 Tissot Trung tính 180g
7 1905 Timex Trung tính 100g
8 1908 Calvin Klein Nữ 90g
9 1902 Movado Nam 100g
10 1909 Citizen Nam 150g

Thiết kế và triển khai

Mô hình dữ liệu thực thể đồng hồ

Thực thể đồng hồ được mô hình hóa thành cấu trúc dongho với các trường dữ liệu và ràng buộc kiểu như sau:

Tên trường Ý nghĩa Kiểu dữ liệu / Ràng buộc
MaSP Mã sản phẩm Chuỗi gồm 11 ký tự số
HangSX Hãng sản xuất Chuỗi ký tự, độ dài tối đa 10 ký tự
GioiTinh Phân loại giới tính (Nam, Nữ, Trung tính) Chuỗi ký tự, độ dài tối đa 10 ký tự
TrongLuong Trọng lượng sản phẩm Số nguyên không âm (TrongLuong >= 0)
BaoHanh Thời gian bảo hành Số nguyên không âm (BaoHanh >= 0)
Gia Giá bán sản phẩm Số thực dương (Gia >= 0)

Thiết kế cấu trúc Danh sách liên kết

Cấu trúc danh sách liên kết đơn quản lý danh mục đồng hồ gồm 3 thành phần chính:

  • Phần thông tin (Data): Chứa đối tượng kiểu dongho.
  • Nút (Node): Gồm thành phần thông tin (data) và con trỏ liên kết tiep trỏ đến nút kế tiếp.
  • Danh sách liên kết (DSLK): Được quản lý bởi hai con trỏ Head (hoặc pHead trỏ vào nút đầu tiên) và Tail (hoặc pTail trỏ vào nút cuối cùng). Khi khởi tạo danh sách rỗng, cả hai con trỏ đều trỏ về NULL.

Bảng tổng hợp các chương trình con được thiết kế và triển khai

Cấu trúc dữ liệu Tên hàm / Chương trình con Mục đích và Tham số xử lý
Mảng cấu trúc nhap_o(dongho &a) Nhập thông tin chi tiết cho một đối tượng đồng hồ
nhap_mang(dongho a[], int n) Nhập danh sách gồm n sản phẩm đồng hồ
xuat_o(dongho a) Xuất thông tin một sản phẩm đồng hồ ra màn hình
xuat_mang(dongho a[], int n) Xuất toàn bộ danh sách n sản phẩm đồng hồ
void_LinearSearch(dongho a[], int n) Tìm kiếm tuyến tính theo Mã sản phẩm (MaSP)
void BinarySearch(dongho a[], int n) Tìm kiếm nhị phân theo Mã sản phẩm (MaSP)
void_LinearSearch_h(dongho a[], int n) Tìm kiếm tuyến tính theo Hãng sản xuất (HangSX)
void BinarySearch_h(dongho a[], int n) Tìm kiếm nhị phân theo Hãng sản xuất (HangSX)
ShakerSort(dongho arr[], int n) / swap Sắp xếp mảng theo MaSP bằng Shaker Sort
SelectionSort(dongho arr[], int n) / hoanvi Sắp xếp mảng theo MaSP bằng Selection Sort
InterchangeSort(dongho arr[], int n) / hoanvi Sắp xếp mảng theo HangSX bằng Interchange Sort
BubbleSort(dongho a[], int n) / hoanvi Sắp xếp mảng theo TrongLuong bằng Bubble Sort
InsertionSort(dongho arr[], int n) / hoanvi Sắp xếp mảng theo Gia bằng Insertion Sort
QuickSort(dongho arr[], int n) Sắp xếp mảng theo BaoHanh bằng Quick Sort
Danh sách liên kết Khởi tạo DSLK Gán pHead = NULL và pTail = NULL
Nhập DSLK Thực hiện 4 bước: nhập ô, đóng gói Node, chèn vào DSLK, hỏi lặp lại
Xuất DSLK Duyệt tuần tự in từng Node từ pHead đến pTail
Tìm kiếm theo MaSP Sử dụng Linear Search duyệt từng nút so sánh mã
Tìm kiếm theo HangSX Sử dụng Linear Search duyệt từng nút so sánh tên hãng
Sắp xếp theo MaSP Triển khai bằng Selection Sort và Interchange Sort
Sắp xếp theo TrongLuong Triển khai bằng Bubble Sort
Sắp xếp theo BaoHanh Triển khai bằng Insertion Sort và Quick Sort

Nội dung chính theo từng chương

Chương 1: Giới thiệu

Chương 1 thiết lập các yêu cầu nền tảng của bài toán quản lý danh mục sản phẩm đồng hồ. Nội dung chương tập trung vào:

  • Mô tả bài toán nghiệp vụ, xác định đối tượng cần quản lý với các trường thuộc tính bắt buộc: MaSP, HangSX, GioiTinh, TrongLuong, BaoHanh, Gia.
  • Quy định các ràng buộc kiểu dữ liệu và khuôn dạng dữ liệu cho từng trường (độ dài chuỗi ký tự, miền giá trị số nguyên và số thực không âm).
  • Xây dựng bảng dữ liệu mẫu gồm 10 đối tượng đồng hồ đại diện cho các thương hiệu Casio, Tag Heuer, Rolex, Omega, Longines, Tissot, Timex, Calvin Klein, Movado, Citizen.
  • Lập danh mục chi tiết các chức năng cần xây dựng trên cả hai cấu trúc dữ liệu: mảng cấu trúc và danh sách liên kết đơn.

Chương 2: Tìm kiếm và sắp xếp trên mảng cấu trúc

Chương 2 trình bày chi tiết quá trình thiết kế, cài đặt thuật toán và kiểm thử chức năng trên cấu trúc mảng một chiều:

  • Nhập/Xuất mảng: Xây dựng cặp hàm nhap_o / nhap_mang để đưa dữ liệu vào mảng và xuat_o / xuat_mang để định dạng hiển thị danh sách sản phẩm.
  • Tìm kiếm dữ liệu:
    • Cài đặt hàm void_LinearSearch và void BinarySearch để tìm kiếm theo khóa chính là Mã sản phẩm (MaSP). Kiểm thử chạy với mã tồn tại (mã 1903) và mã không tồn tại (mã 1902).
    • Cài đặt hàm void_LinearSearch_h và void BinarySearch_h để tìm kiếm theo Hãng sản xuất (HangSX). Kiểm thử với hãng có trong danh sách (Omega) và hãng không có trong mẫu thử (Casio).
  • Sắp xếp dữ liệu:
    • Shaker Sort theo MaSP: Giải thuật duyệt hai chiều; lượt đi đẩy phần tử bé nhất về đầu dãy, lượt về đẩy phần tử lớn nhất về cuối dãy, kết hợp hàm phụ trợ swap.
    • Selection Sort theo MaSP: Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp và đưa về vị trí đầu, lặp lại từ vị trí kế tiếp cùng hàm phụ trợ hoanvi.
    • Interchange Sort theo HangSX: Quét các nghịch thế từ đầu dãy và thực hiện hoán vị trực tiếp.
    • Bubble Sort theo TrongLuong: Xuất phát từ cuối dãy, hoán vị các cặp nghịch thế liền kề để đưa phần tử nhẹ/nặng về đúng vị trí.
    • Insertion Sort theo Gia: Chia mảng thành phần đã sắp xếp T và phần chưa sắp xếp P, lần lượt lấy phần tử trong P chèn vào vị trí thích hợp trong T.
    • Quick Sort theo BaoHanh: Phân chia mảng thành ba phân vùng dựa trên phần tử chốt x (nhỏ hơn x, bằng x, lớn hơn x) và gọi đệ quy sắp xếp trên các dãy con.

Chương 3: Tìm kiếm và sắp xếp trên danh sách liên kết

Chương 3 chuyển đổi bài toán sang cấu trúc dữ liệu động – Danh sách liên kết đơn:

  • Định nghĩa và thao tác cơ bản:
    • Định nghĩa cấu trúc Node gồm phần thông tin dongho và con trỏ tiep.
    • Quản lý danh sách bằng cặp con trỏ Head (pHead) và Tail (pTail).
    • Quy trình nhập dữ liệu gồm 4 bước tuần tự: (1) Nhập thông tin ô dữ liệu; (2) Đóng gói dữ liệu kèm con trỏ để tạo Node mới; (3) Đưa Node vào danh sách; (4) Nhận yêu cầu tiếp tục nhập hoặc dừng.
    • Thao tác xuất danh sách bằng cách duyệt con trỏ từ đầu đến cuối danh sách.
  • Phân tích khả năng áp dụng thuật toán trên DSLK:
    • Tìm kiếm: Chỉ có thể áp dụng LinearSearch duyệt tuần tự từ nút đầu tiên. Thuật toán BinarySearch không thể thực hiện trên DSLK vì cấu trúc này không hỗ trợ truy xuất ngẫu nhiên và không xác định trực tiếp được chỉ số phần tử đầu - cuối để tính phần tử chính giữa.
    • Shaker Sort: Đồ án chỉ rõ Shaker Sort không thể thực hiện trên danh sách liên kết đơn vì giải thuật này đòi hỏi phải xác định phần tử cuối cùng và duyệt ngược chiều từ cuối về đầu, điều không khả thi trên DSLK đơn chỉ có liên kết một chiều.
    • Các thuật toán sắp xếp khả thi: Cài đặt thành công Selection Sort (theo MaSP), Interchange Sort (theo MaSP), Bubble Sort (theo TrongLuong), Insertion Sort và Quick Sort (theo BaoHanh).

Kết quả và đóng góp

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

  • Xây dựng hoàn chỉnh các hàm nhập, xuất dữ liệu cho cả cấu trúc mảng và cấu trúc danh sách liên kết đơn đối với kiểu thực thể dongho.
  • Cài đặt và kiểm thử thành công các giải thuật tìm kiếm tuyến tính và nhị phân trên mảng cấu trúc, xử lý chính xác các trường hợp kiểm thử biên: tìm thấy phần tử có mã 1903, hãng Omega; thông báo không tìm thấy đối với mã 1902 và hãng Casio trong bộ dữ liệu kiểm tra.
  • Cài đặt hoàn chỉnh các giải thuật sắp xếp đa dạng trên các trường thuộc tính khác nhau của thực thể: sắp xếp theo chuỗi ký tự (MaSP, HangSX), theo số nguyên (TrongLuong, BaoHanh), và theo số thực (Gia).
  • Triển khai thành công các thao tác quản lý nút và liên kết con trỏ trên danh sách liên kết đơn.

Đóng góp học thuật và thực tiễn của tác giả

  • Làm rõ sự khác biệt về mặt bản chất giữa cấu trúc dữ liệu lưu trữ liên tiếp (mảng) và cấu trúc dữ liệu liên kết động (DSLK).
  • Tự chứng minh và chỉ ra giới hạn kỹ thuật của các thuật toán: giải thích rõ nguyên nhân giải thuật tìm kiếm nhị phân (BinarySearch) và giải thuật sắp xếp Shaker (ShakerSort) không thể áp dụng trực tiếp trên cấu trúc danh sách liên kết đơn do hạn chế về truy xuất ngẫu nhiên và duyệt ngược chiều.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế

  • Đồ án thuộc phạm vi bài thực hành môn học nên tập dữ liệu kiểm thử dừng lại ở quy mô nhỏ (10 bản ghi), chưa đánh giá thực nghiệm thời gian chạy (execution time) trên tập dữ liệu lớn.
  • Chưa mở rộng cài đặt trên các biến thể khác của danh sách liên kết như danh sách liên kết đôi (Doubly Linked List) hoặc danh sách liên kết vòng (Circular Linked List) để khắc phục nhược điểm duyệt một chiều.
  • Dữ liệu chưa được liên kết với hệ thống lưu trữ lâu dài (tệp tin hoặc cơ sở dữ liệu), dữ liệu chỉ tồn tại tạm thời trong bộ nhớ RAM khi chương trình thực thi.

Hướng nghiên cứu tiếp

  • Mở rộng cài đặt các giải thuật sắp xếp và tìm kiếm trên danh sách liên kết đôi nhằm cho phép triển khai giải thuật duyệt hai chiều như Shaker Sort.
  • Nghiên cứu và áp dụng cấu trúc Cây tìm kiếm nhị phân (Binary Search Tree - BST) hoặc Cây AVL để tối ưu hóa tốc độ tìm kiếm và sắp xếp cho danh mục sản phẩm.
  • Tích hợp module đọc/ghi dữ liệu từ tệp văn bản (Text File / Binary File) để lưu trữ bền vững danh mục đồng hồ.

Giá trị tham khảo

Báo cáo đồ án là tài liệu tham khảo hữu ích cho:

  • Sinh viên chuyên ngành Công nghệ Thông tin, Kỹ thuật Phần mềm, Hệ thống Thông tin đang học tập và làm đồ án môn học Cấu trúc dữ liệu và giải thuật.
  • Người học cần tài liệu mẫu về cách chuyển đổi mô hình dữ liệu thực tế (quản lý sản phẩm) thành các kiểu dữ liệu có cấu trúc (struct) và cấu trúc danh sách liên kết trong ngôn ngữ C/C++.
  • Các phần có giá trị tham khảo cao nhất:
    • Bảng định nghĩa chi tiết các hàm kiểm tra (test) và chương trình con cho từng thuật toán sắp xếp kinh điển (Shaker Sort, Quick Sort, Insertion Sort, Selection Sort, Bubble Sort).
    • Phần phân tích nguyên lý hoạt động và lý do kỹ thuật giải thích vì sao một số thuật toán (Binary Search, Shaker Sort) không thể triển khai trên cấu trúc danh sách liên kết đơn.

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

1. Cấu trúc dữ liệu quản lý thông tin đồng hồ gồm những trường dữ liệu nào và ràng buộc kiểu ra sao?

Cấu trúc dongho quản lý 6 trường thông tin: MaSP (chuỗi 11 ký tự số), HangSX (chuỗi tối đa 10 ký tự), GioiTinh (chuỗi tối đa 10 ký tự), TrongLuong (số nguyên không âm >= 0), BaoHanh (số nguyên không âm >= 0), và Gia (số thực dương >= 0).

2. Tại sao giải thuật Binary Search không thể triển khai trên danh sách liên kết đơn trong đồ án này?

Giải thuật tìm kiếm nhị phân yêu cầu khả năng truy xuất ngẫu nhiên đến phần tử nằm ở vị trí chính giữa tập dữ liệu thông qua chỉ số và xác định được vị trí đầu - cuối. Danh sách liên kết đơn chỉ lưu trữ địa chỉ của phần tử kế tiếp thông qua con trỏ, bắt buộc phải duyệt tuần tự từ đầu danh sách (pHead), do đó không thể tính toán và nhảy trực tiếp đến phần tử giữa danh sách trong thời gian $O(1)$.

3. Nguyên tắc hoạt động của giải thuật Shaker Sort trên mảng cấu trúc được mô tả như thế nào?

Shaker Sort xuất phát từ cuối dãy, xét các phần tử liền kề và hoán vị nếu có nghịch thế. Trong mỗi lần lặp, giải thuật thực hiện 2 lượt: lượt đi đẩy phần tử bé nhất về đầu dãy, lượt về đẩy phần tử lớn nhất về cuối dãy.

4. Tại sao giải thuật Shaker Sort không thể áp dụng trên danh sách liên kết đơn?

Tương tự như Binary Search, để thực hiện Shaker Sort cần phải xác định được phần tử cuối cùng và có khả năng duyệt ngược chiều từ cuối về đầu danh sách trong lượt về. Danh sách liên kết đơn chỉ có liên kết một chiều từ nút trước đến nút sau thông qua con trỏ tiep, không thể duyệt ngược từ cuối về đầu nếu không có liên kết ngược.

5. Quá trình nhập một danh sách liên kết đơn trong đồ án gồm các bước nào?

Quá trình nhập dữ liệu danh sách liên kết gồm 4 bước tuần tự:

  • Bước 1: Nhập thông tin của một sản phẩm đồng hồ.
  • Bước 2: Đóng gói phần thông tin kèm theo con trỏ để tạo một Node mới.
  • Bước 3: Đưa Node vừa tạo vào danh sách liên kết.
  • Bước 4: Tạo yêu cầu cho người dùng lựa chọn tiếp tục nhập hoặc kết thúc.

Kết luận

Đồ án môn học "Cấu trúc dữ liệu và giải thuật" của tác giả Đỗ Tường Vy đã hoàn thành đầy đủ các yêu cầu kỹ thuật trong việc mô hình hóa và quản lý danh mục sản phẩm đồng hồ trên hai cấu trúc dữ liệu nền tảng là mảng cấu trúc và danh sách liên kết đơn. Công trình đã cài đặt, kiểm thử thành công hệ thống các giải thuật tìm kiếm tuyến tính, tìm kiếm nhị phân cùng 7 giải thuật sắp xếp nội bộ trên các trường thuộc tính khác nhau của thực thể. Báo cáo không chỉ cung cấp mã nguồn kiểm thử rõ ràng mà còn đưa ra những phân tích đúng đắn về mặt lý thuyết đối với các giới hạn kỹ thuật khi áp dụng thuật toán trên danh sách liên kết một chiều.