Bối cảnh và vấn đề nghiên cứu
Trong chương trình đào tạo ngành Công nghệ Thông tin tại Trường Đại học Tài chính – Marketing (UFM), học phần "Cấu trúc dữ liệu và giải thuật" đóng vai trò nền tảng trong việc rèn luyện tư duy lập trình và kỹ năng tổ chức dữ liệu cho sinh viên. Đồ án môn học của sinh viên Nguyễn Xuân Tính (Mã số sinh viên/Mã môn học: 2121001038, Lớp học phần: 2121112001202), dưới sự hướng dẫn của ThS. Nguyễn Quốc Thanh, được thực hiện nhằm giải quyết bài toán quản lý danh mục môn học thông qua việc áp dụng các cấu trúc lưu trữ và giải thuật cơ bản.
Mục tiêu và nhiệm vụ nghiên cứu của đồ án được xác định cụ thể như sau:
- Xây dựng cấu trúc dữ liệu bản ghi
MONHOC phản ánh các thuộc tính quản lý học phần trong trường đại học.
- Thiết kế và cài đặt các thao tác cơ bản bao gồm nhập dữ liệu, xuất dữ liệu và đếm số lượng phần tử trên hai cấu trúc lưu trữ: mảng tĩnh (array) và danh sách liên kết đơn (singly linked list).
- Cài đặt các giải thuật tìm kiếm cơ bản (Tìm kiếm tuyến tính - Linear Search, Tìm kiếm nhị phân - Binary Search) theo mã môn học và tên môn học.
- Triển khai các thuật toán sắp xếp kinh điển (Shaker Sort, Selection Sort, Interchange Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort) dựa trên các khóa tìm kiếm/sắp xếp khác nhau như Mã môn học, Tên môn học, Số tín chỉ.
Đối tượng nghiên cứu của đồ án là cấu trúc dữ liệu môn học và các giải thuật thao tác trên bộ nhớ trong. Phạm vi nghiên cứu giới hạn ở môi trường lập trình C++ dạng màn hình dòng lệnh (console), sử dụng tập dữ liệu thực nghiệm mẫu gồm 10 môn học với các chỉ số thực tế về thời lượng học phần.
Cơ sở lý thuyết và phương pháp
Đồ án vận dụng các khái niệm và nguyên lý nền tảng trong khoa học máy tính:
- Cấu trúc dữ liệu mảng cấu trúc (Array of Structures): Tổ chức dữ liệu dưới dạng các vùng nhớ liên tiếp, cho phép truy xuất ngẫu nhiên tới từng phần tử thông qua chỉ số mảng với độ phức tạp $O(1)$, phù hợp với các tập dữ liệu có kích thước cố định.
- Cấu trúc danh sách liên kết đơn (Singly Linked List - DSLK): Tổ chức dữ liệu động thông qua các nút (Node) liên kết tuần tự qua con trỏ, cho phép cấp phát bộ nhớ linh hoạt tại thời điểm thực thi.
- Các giải thuật tìm kiếm:
- Linear Search (Tìm kiếm tuyến tính): Duyệt tuần tự từ đầu đến cuối tập dữ liệu, áp dụng được cho cả dữ liệu chưa sắp xếp và dữ liệu đã sắp xếp.
- Binary Search (Tìm kiếm nhị phân): Thuật toán chia để trị, yêu cầu dữ liệu đầu vào phải được sắp xếp theo thứ tự của trường khóa cần tìm, giúp thu hẹp phạm vi tìm kiếm sau mỗi bước lặp.
- Các giải thuật sắp xếp:
- Nhóm thuật toán sắp xếp dựa trên so sánh và đổi chỗ cơ bản: Interchange Sort (Đổi chỗ trực tiếp), Selection Sort (Chọn trực tiếp), Bubble Sort (Nổi bọt), Shaker Sort (Nổi bọt hai chiều), Insertion Sort (Chèn trực tiếp).
- Nhóm thuật toán sắp xếp nâng cao phân chia: Quick Sort (Sắp xếp nhanh theo chốt pivot), Merge Sort (Sắp xếp trộn).
Phương pháp nghiên cứu được tác giả áp dụng là phương pháp thực nghiệm lập trình (Implementation & Testing):
- Thiết kế các module chương trình con (functions) độc lập tương ứng với từng thao tác và từng thuật toán.
- Thiết kế các hàm kiểm thử
main() với số lượng phần tử xác định (spt = 3 trong các phép thử nghiệm nhanh và danh sách 10 phần tử mẫu) để kiểm tra tính đúng đắn của logic xử lý.
- Thu thập và đối soát kết quả đầu ra trực tiếp qua màn hình console.
Nguồn dữ liệu thực nghiệm được xây dựng theo bảng dữ liệu mẫu chuẩn gồm 10 môn học với đầy đủ 6 thuộc tính:
| Mã môn học |
Tên môn học |
Số tín chỉ |
Giờ lý thuyết |
Giờ thực hành |
Tự học |
| 1 |
Toán |
12 |
5 |
5 |
2 |
| 2 |
Văn |
11 |
4 |
3 |
1 |
| 3 |
Anh |
10 |
6 |
2 |
6 |
| 4 |
Sử |
9 |
4 |
3 |
4 |
| 5 |
Địa |
7 |
5 |
4 |
3 |
| 6 |
Tin |
15 |
3 |
1 |
5 |
| 7 |
Lí |
6 |
6 |
2 |
6 |
| 8 |
Hóa |
8 |
4 |
5 |
2 |
| 9 |
Sinh |
13 |
5 |
4 |
4 |
| 10 |
Thể dục |
4 |
7 |
2 |
1 |
Thiết kế và triển khai
Cấu trúc bản ghi MONHOC được tác giả định nghĩa bằng ngôn ngữ C++ với các trường dữ liệu và kiểu dữ liệu tương ứng:
struct MONHOC {
char MaMH[10]; // Mã môn học: chuỗi ký tự số dài 10 ký tự
char TenMH[15]; // Tên môn học: chuỗi tiếng Việt dài 15 ký tự
int SoTC; // Số tín chỉ: số nguyên không âm
float GioLT; // Giờ lý thuyết: số thực dương
float GioTH; // Giờ thực hành: số thực dương
float Tuhoc; // Giờ tự học: số thực dương
};
Hệ thống các chương trình con được chia thành hai nhánh triển khai độc lập: nhánh thao tác trên mảng cấu trúc tĩnh và nhánh thao tác trên danh sách liên kết đơn.
| Cấu trúc dữ liệu |
Thao tác nhập / xuất / phụ trợ |
Thao tác tìm kiếm |
Thao tác sắp xếp |
| Mảng cấu trúc |
nhap_o, nhap_Mang, xuat_o, xuat_Mang, hoanvi |
- LinearSearch (theo MaMH)
- BinarySearch (theo MaMH)
- LinerSearch2 (theo TenMH)
- BinarySearch2 (theo TenMH) |
- ShakerSort (theo MaMH)
- SelectionSort (theo MaMH)
- InterchangeSort (theo TenMH)
- BubbleSort (theo MaMH)
- InsertionSort (theo TenMH)
- QuickSort / QuickSort1 (theo SoTC)
- MergeSort (theo MaMH) |
| Danh sách liên kết (DSLK) |
Khởi tạo nút, nhap DSLK, xuat DSLK, đếm phần tử, hoanvi |
- Linear Search (theo MaMH)
- Linear Search (theo TenMH) |
- SelectionSort (theo MaMH)
- InterchangeSort (theo MaMH)
- BubbleSort (theo MaMH/SoTC)
- InsertionSort (theo MaMH/TenMH)
- QuickSort (theo MaMH) |
Nội dung chính theo từng chương
CHƯƠNG I: GIỚI THIỆU
Chương I trình bày cơ sở bài toán quản lý danh mục môn học, đặc tả yêu cầu cấu trúc dữ liệu và xác định danh sách các chức năng cần thực hiện.
Tác giả định nghĩa chi tiết kiểu dữ liệu cấu trúc struct MONHOC bao gồm 6 trường thông tin (MaMH, TenMH, SoTC, GioLT, GioTH, Tuhoc). Bên cạnh việc đưa ra bảng dữ liệu mẫu gồm 10 phần tử đại diện từ môn Toán đến Thể dục, chương này liệt kê toàn bộ danh mục 13 chức năng trên mảng cấu trúc và 9 chức năng trên danh sách liên kết. Đây là phần khung định hướng cho toàn bộ mã nguồn và các ca kiểm thử trong hai chương tiếp theo.
CHƯƠNG II: TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU TRÚC
Chương II là phần trọng tâm về cài đặt các giải thuật trên mảng tĩnh chứa các phần tử có kiểu MONHOC. Nội dung mỗi mục được chuẩn hóa gồm ba phần: chương trình con xử lý, hàm kiểm tra main(), và hình ảnh kết quả chạy thực tế.
- Nhập và xuất danh sách môn học: Tác giả xây dựng hàm
nhap_o(MONHOC& a) để nhập tuần tự 6 trường thông tin cho một phần tử và hàm nhap_Mang(MONHOC a[], int n) để lặp nhập cho toàn bộ danh sách $n$ phần tử. Tương tự, hai hàm xuat_o(MONHOC a) và xuat_Mang(MONHOC a[], int n) định dạng dữ liệu đầu ra hiển thị trên màn hình console.
- Tìm kiếm thông tin môn học:
- Tìm kiếm theo Mã môn học (
MaMH): Hàm LinearSearch duyệt tuyến tính từ chỉ số 0 đến n-1, so sánh chuỗi bằng hàm strcmp. Hàm BinarySearch áp dụng thuật toán chia đôi đoạn tìm kiếm [left, right] với điểm giữa mid = (left + right) / 2.
- Tìm kiếm theo Tên môn học (
TenMH): Hàm LinerSearch2 và hàm BinarySearch2 thực hiện tìm kiếm trên trường chuỗi tên môn học.
- Hàm bổ trợ hoán vị: Hàm
void hoanvi(MONHOC& a, MONHOC& b) sử dụng biến tạm temp kiểu MONHOC để đổi chỗ hai bản ghi trong mảng.
- Sắp xếp mảng cấu trúc:
- Shaker Sort (
ShakerSort): Sắp xếp theo MaMH bằng cách duyệt hai chiều liên tiếp để đưa phần tử lớn nhất về cuối và nhỏ nhất về đầu mảng.
- Selection Sort (
SelectionSort): Sắp xếp theo MaMH bằng cách tìm vị trí phần tử có khóa nhỏ nhất (min) trong đoạn chưa sắp xếp để hoán vị với vị trí hiện tại i.
- Interchange Sort (
InterchangeSort): So sánh trực tiếp từng cặp phần tử $(i, j)$ với $i < j$ và hoán vị nếu $a[i].TenMH > a[j].TenMH$.
- Bubble Sort (
BubbleSort): Duyệt từ cuối mảng lên đầu mảng để đẩy phần tử có mã môn học nhỏ hơn lên phía trên.
- Insertion Sort (
InsertionSort): Chèn phần tử hiện tại $x$ vào đúng vị trí trong đoạn con đã được sắp xếp phía trước.
- Quick Sort (
QuickSort, QuickSort1): Phân hoạch mảng theo đoạn [left, right] dựa trên giá trị trường Số tín chỉ (SoTC), sau đó gọi đệ quy trên hai nửa mảng con.
- Merge Sort (
MergeSort): Chia mảng thành các mảng con, sắp xếp và trộn lại theo thứ tự trường MaMH.
Mỗi giải thuật đều đi kèm với giao diện dòng lệnh hiển thị thông báo kết quả kiểm tra trước và sau khi thực hiện sắp xếp hoặc tìm kiếm.
CHƯƠNG III: TÌM KIẾM VÀ SẮP XẾP TRÊN DSLK
Chương III mở rộng bài toán sang cấu trúc dữ liệu động – Danh sách liên kết đơn. Tác giả xây dựng cấu trúc nút chứa thành phần dữ liệu là MONHOC và một con trỏ trỏ tới phần tử kế tiếp (next).
Nội dung chương triển khai các chương trình con chuyên biệt:
- Khởi tạo và nhập/xuất DSLK: Khởi tạo danh sách rỗng (
pHead = NULL), cấp phát động từng nút mới khi nhập thông tin môn học và chèn vào danh sách; duyệt qua từng liên kết để xuất dữ liệu ra màn hình.
- Đếm số lượng phần tử: Hàm duyệt từ đầu đến cuối danh sách để xác định chính xác số lượng môn học hiện có.
- Tìm kiếm trên DSLK: Do danh sách liên kết đơn không hỗ trợ truy xuất ngẫu nhiên theo chỉ số, tác giả chỉ triển khai tìm kiếm tuyến tính (Linear Search) cho cả hai trường khóa
MaMH và TenMH.
- Sắp xếp trên DSLK: Triển khai các giải thuật Selection Sort, Interchange Sort, Bubble Sort, Insertion Sort và Quick Sort trên danh sách liên kết. Các thuật toán này thực hiện so sánh trường khóa giữa các nút và gọi hàm hoán vị nội dung dữ liệu bên trong nút để đạt được thứ tự mong muốn.
Kết quả và đóng góp
Đồ án hoàn thành việc xây dựng và kiểm thử các giải thuật xử lý dữ liệu môn học với những kết quả cụ thể:
- Cài đặt thành công 13 module chức năng trên mảng cấu trúc và 9 module chức năng trên danh sách liên kết đơn.
- Minh họa chi tiết quy trình xử lý của các giải thuật tìm kiếm tuyến tính, tìm kiếm nhị phân và 7 thuật toán sắp xếp khác nhau trên dữ liệu bản ghi nhiều trường.
- Cung cấp bộ dữ liệu kiểm thử mẫu gồm 10 môn học với cấu trúc thực tế và các ca kiểm thử nhanh (
spt = 3) có ảnh chụp màn hình minh chứng kết quả chạy chương trình.
Về mặt học thuật và thực hành, tài liệu đóng góp một tài liệu tham khảo chi tiết về việc chuyển đổi các thuật toán sắp xếp kinh điển từ kiểu dữ liệu nguyên thủy (số nguyên, số thực) sang kiểu dữ liệu cấu trúc tự định nghĩa (struct) có chứa cả chuỗi ký tự và số liệu.
Hạn chế và hướng nghiên cứu tiếp
Dựa trên nội dung văn bản, đồ án tồn tại một số hạn chế:
- Phạm vi kiểm thử trong các hàm
main() còn ở quy mô nhỏ (chủ yếu thiết lập const int spt = 3 để test nhanh từng hàm riêng lẻ thay vì chạy toàn bộ bảng dữ liệu 10 môn học).
- Chương trình chưa tích hợp menu điều khiển tổng thể để người dùng có thể thực hiện liên hoàn các thao tác nhập, xuất, tìm kiếm và sắp xếp trên cùng một phiên làm việc.
- Việc sắp xếp trên danh sách liên kết đơn được thực hiện thông qua hoán đổi vùng dữ liệu (
data) giữa các nút thay vì hoán đổi các con trỏ liên kết (pointer).
- Trong văn bản còn xuất hiện một số lỗi cú pháp in ấn ở phần mã nguồn mẫu (ví dụ:
cin.MaMH, điều kiện trong vòng lặp nhị phân).
Hướng phát triển tiếp theo được gợi ý từ phạm vi nghiên cứu gồm:
- Xây dựng hệ thống menu chọn chức năng dạng switch-case hoàn chỉnh trên console.
- Cải tiến các giải thuật sắp xếp trên DSLK bằng kỹ thuật thay đổi liên kết con trỏ để tối ưu hiệu năng khi kích thước bản ghi dữ liệu lớn.
- Bổ sung cơ chế lưu trữ và đọc dữ liệu từ tệp tin (file I/O) để duy trì tính bền vững của dữ liệu danh mục môn học.
Giá trị tham khảo
Tài liệu là nguồn tham khảo hữu ích cho:
- Sinh viê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 môn Cấu trúc dữ liệu và Giải thuật hoặc Lập trình C/C++.
- Người học cần tài liệu mẫu về cách tổ chức mã nguồn, cách viết chương trình con tách biệt và cách kiểm thử từng giải thuật sắp xếp/tìm kiếm trên kiểu dữ liệu bản ghi
struct.
- Phần đáng tham khảo nhất là bảng tổng hợp dữ liệu mẫu và mã nguồn cài đặt các thuật toán sắp xếp phức tạp như Shaker Sort, Quick Sort và Merge Sort áp dụng trực tiếp trên mảng cấu trúc.
Câu hỏi thường gặp
1. Đồ án quản lý đối tượng nào và gồm các trường thông tin gì?
Đồ án quản lý đối tượng môn học thông qua cấu trúc struct MONHOC gồm 6 trường: MaMH (chuỗi ký tự số dài 10 ký tự), TenMH (chuỗi tiếng Việt dài 15 ký tự), SoTC (số nguyên không âm), GioLT (số thực dương), GioTH (số thực dương), và Tuhoc (số thực dương).
2. Bảng dữ liệu mẫu trong đồ án có bao nhiêu môn học và môn nào có số tín chỉ cao nhất?
Bảng dữ liệu mẫu (Bảng 1.1) gồm 10 môn học. Môn học có số tín chỉ cao nhất trong bảng dữ liệu mẫu là môn Tin với 15 tín chỉ (giờ lý thuyết: 3, thực hành: 1, tự học: 5).
3. Trên cấu trúc mảng, những thuật toán sắp xếp nào đã được cài đặt?
Đồ án đã cài đặt 7 thuật toán sắp xếp trên mảng cấu trúc bao gồm: Shaker Sort (theo mã môn học), Selection Sort (theo mã môn học), Interchange Sort (theo tên môn học), Bubble Sort (theo mã môn học), Insertion Sort (theo tên môn học), Quick Sort (theo số tín chỉ) và Merge Sort (theo mã môn học).
4. Tại sao trên Danh sách liên kết đơn (DSLK) đồ án chỉ sử dụng Linear Search mà không sử dụng Binary Search?
Do danh sách liên kết đơn chỉ cho phép duyệt tuần tự qua các con trỏ next mà không thể truy xuất ngẫu nhiên phần tử ở vị trí giữa (mid) trong thời gian $O(1)$ như mảng, nên tác giả chỉ triển khai tìm kiếm tuyến tính (Linear Search) cho cả mã môn học và tên môn học trên DSLK.
5. Các ca kiểm thử chương trình con trong đồ án được thiết lập với số lượng phần tử là bao nhiêu?
Trong các đoạn mã nguồn hàm kiểm thử main(), tác giả sử dụng hằng số const int spt = 3 để kiểm tra nhanh từng chức năng nhập, xuất, tìm kiếm và sắp xếp trước khi đối chiếu với bảng dữ liệu mẫu đầy đủ.
Kết luận
Bài tập đồ án "Cấu trúc dữ liệu và giải thuật" của sinh viên Nguyễn Xuân Tính đã hệ thống hóa và cài đặt đầy đủ các thao tác tìm kiếm, sắp xếp trên hai cấu trúc dữ liệu cơ bản là mảng tĩnh và danh sách liên kết đơn. Nghiên cứu giải quyết bài toán quản lý danh mục môn học với kiểu dữ liệu struct MONHOC đa trường thông tin. Đồ án cung cấp minh chứng thực nghiệm rõ ràng qua từng chương trình con và kết quả chạy chương trình, tạo nền tảng vững chắc cho việc tiếp cận các cấu trúc dữ liệu nâng cao.
