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, học phần Cấu trúc dữ liệu và Giải thuật đóng vai trò nền tảng nhằm rèn luyện tư duy lập trình, kỹ năng tổ chức dữ liệu bộ nhớ và tối ưu hóa hiệu năng xử lý. Đồ án môn học với đề tài "Đề 2214: Xây dựng cấu trúc quản lý thông tin các khoa" do sinh viên Nguyễn Bùi Quốc Thiện thực hiện dưới sự hướng dẫn của ThS. Nguyễn Quốc Thanh (năm 2022) xuất phát từ yêu cầu thực tiễn trong việc mô hình hóa, lưu trữ và thao tác dữ liệu quản lý các đơn vị đào tạo trực thuộc nhà trường.

Mục tiêu và nhiệm vụ nghiên cứu của đề tài bao gồm:

  1. Thiết kế và định nghĩa cấu trúc dữ liệu chuẩn để lưu trữ đầy đủ các thông tin đặc trưng của một khoa.
  2. Cài đặt các chức năng nhập, xuất, tìm kiếm và sắp xếp danh sách các khoa trên cấu trúc mảng tĩnh.
  3. Chuyển đổi và hiện thực hóa các cấu trúc dữ liệu động thông qua danh sách liên kết đơn (DSLK), bao gồm việc định nghĩa nút (Node), danh sách và các thao tác quản lý tương ứng.
  4. Xây dựng giao diện menu tương tác trên màn hình điều khiển (Console) nhằm hỗ trợ việc kiểm thử và vận hành các giải thuật.

Đối tượng nghiên cứu của đồ án là tập dữ liệu thông tin quản lý của 10 khoa thực tế thuộc Trường Đại học Tài chính – Marketing, bao gồm 6 trường thuộc tính: Mã khoa, Tên khoa, Trưởng khoa, Năm thành lập, Số lượng sinh viên và Tỷ lệ sinh viên/giảng viên. Phạm vi nghiên cứu giới hạn trong việc cài đặt và đánh giá thực nghiệm các giải thuật sắp xếp, tìm kiếm kinh điển trên hai mô hình lưu trữ bộ nhớ cơ bản trong môi trường lập trình C/C++.

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

Đề tài áp dụng các khối kiến thức lý thuyết cốt lõi về tổ chức dữ liệu và thiết kế giải thuật:

  • Cấu trúc mảng tĩnh (Static Array): Lưu trữ tập hợp các phần tử kiểu cấu trúc (struct Khoa) liên tiếp nhau trong bộ nhớ với kích thước cố định.
  • Cấu trúc danh sách liên kết đơn (Singly Linked List): Cấu trúc dữ liệu động tổ chức dưới dạng các nút (Node), mỗi nút gồm hai thành phần: trường dữ liệu chứa thông tin một khoa và con trỏ liên kết trỏ tới nút kế tiếp trong bộ nhớ.
  • Hệ thống giải thuật sắp xếp:
    • Nhóm giải thuật có độ phức tạp trung bình $O(N^2)$: Sắp xếp nổi bọt (Bubble Sort), Sắp xếp rung lắc (Shaker Sort), Sắp xếp đổi chỗ trực tiếp (Interchange Sort), Sắp xếp chọn trực tiếp (Selection Sort), Sắp xếp chèn trực tiếp (Insertion Sort).
    • Nhóm giải thuật nâng cao có độ phức tạp $O(N \log N)$: Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort).
  • Hệ thống giải thuật tìm kiếm: Tìm kiếm tuyến tính (Linear Search) áp dụng trên tập dữ liệu chưa sắp xếp và Tìm kiếm nhị phân (Binary Search) áp dụng trên tập dữ liệu mảng đã được sắp xếp theo khóa.

Phương pháp nghiên cứu thực nghiệm được thực hiện qua các bước:

  1. Mô hình hóa dữ liệu: Định nghĩa cấu trúc bản ghi và xác lập tập dữ liệu thử nghiệm.
  2. Cài đặt chương trình: Xây dựng các hàm con chuyên biệt cho từng thao tác dữ liệu và ghép nối vào hàm điều khiển chính (main).
  3. Kiểm thử và đối soát: Chạy thử nghiệm trên tập dữ liệu 10 khoa, chụp lại màn hình thực thi (Console Output) để xác nhận tính đúng đắn của từng giải thuật trong cả hai trường hợp: tìm thấy và không tìm thấy kết quả.

Nguồn dữ liệu thực nghiệm được chuẩn hóa từ danh sách các khoa của Trường Đại học Tài chính – Marketing.

Thiết kế và triển khai

Mô hình dữ liệu khoa

Cấu trúc đối tượng quản lý thông tin khoa (Khoa) được định nghĩa với các thuộc tính cụ thể:

Tên trường dữ liệu Kiểu dữ liệu / Ràng buộc Diễn giải ý nghĩa
MaKhoa Chuỗi ký tự (String) Mã định danh duy nhất cho từng khoa
TenKhoa Chuỗi ký tự, chiều dài < 40 Tên đầy đủ của khoa
TruongKhoa Chuỗi ký tự, chiều dài < 40 Học vị và họ tên Trưởng khoa
NamTL Số nguyên Năm thành lập khoa
SoSV Số nguyên Tổng số sinh viên hiện đang theo học tại khoa
TyLe (SV_GV) Số thực Tỷ lệ số sinh viên trên một giảng viên

Dữ liệu mẫu gồm 10 bản ghi được sử dụng trong suốt quá trình chạy kiểm thử:

STT Mã khoa Tên khoa Trưởng khoa Năm TL Số SV Tỷ lệ SV/GV
1 THQ01 Thuế - Hải quan TS. Hồ Thủy Tiên 2004 360 15.0
2 TNH02 Tài chính - Ngân hàng PGS. TS. Nguyễn Xuân Trường 2004 340 12.6
3 KTT03 Kế toán - Kiểm toán TS. Trần Hồng Vân 2004 340 12.6
4 MKT04 Marketing TS. Nguyễn Xuân Trường 1992 300 11.5
5 BSA05 Quản trị kinh doanh TS. Huỳnh Thị Thu Sương 2004 370 14.2
6 BDS06 Thẩm định giá - Kinh doanh Bất động sản TS. Nguyễn Thanh Nhã 1999 290 1.3
7 CME07 Thương mại TS. Nguyễn Xuân Hiệp 2002 300 10.3
8 TV008 Du lịch TS. Đoàn Liêng Diễm 2010 270 11.3
9 ELH09 Ngoại ngữ TS. Nguyễn Ngọc Trân Châu 2004 210 7.8
10 IT010 Công nghệ thông tin TS. Trương Thành Công 2009 320 11.9

Cài đặt trên cấu trúc mảng tĩnh

Hệ thống quản lý bằng mảng tĩnh sử dụng mảng một chiều các phần tử Khoa a[] cùng biến số lượng phần tử nguyên int n. Các chương trình con cốt lõi bao gồm:

  • Hàm nhập dữ liệu cho một khoa: void Nhap_Khoa(Khoa& k)
  • Hàm nhập danh sách $n$ khoa: void Nhap_DSKhoa(Khoa a[], int& n)
  • Hàm xuất danh sách $n$ khoa ra màn hình: void Xuat_DsKhoa(Khoa a[], int& n)
  • Hệ thống hàm sắp xếp mảng theo trường MaKhoa gồm 7 giải thuật riêng biệt.
  • Hệ thống hàm tìm kiếm theo MaKhoa sử dụng tìm kiếm tuyến tính và tìm kiếm nhị phân.
  • Hàm khởi tạo menu chính đa chức năng để người dùng lựa chọn thao tác từ bàn phím.

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

Cấu trúc danh sách liên kết được tổ chức gồm:

  • Định nghĩa thành phần dữ liệu một nút chứa thông tin cấu trúc Khoa.
  • Định nghĩa nút liên kết (Node) gồm dữ liệu khoa và con trỏ pNext.
  • Cấu trúc quản lý danh sách liên kết (DSLK) lưu trữ con trỏ đầu danh sách (pHead) và cuối danh sách (pTail).
  • Quy trình 4 bước nhập dữ liệu vào danh sách liên kết:
    1. Nhập thông tin cho một đối tượng khoa mới (Nhap_Khoa).
    2. Cấp phát bộ nhớ động và tạo nút mới (CreateNode).
    3. Chèn nút vào danh sách liên kết (AddTail hoặc AddHead).
    4. Thực hiện lặp lại để nhập danh sách nhiều khoa vào DSLK.
  • Quy trình xuất dữ liệu: Duyệt tuần tự từ đầu danh sách đến cuối danh sách, gọi chương trình con in thông tin từng nút ra màn hình.
  • Các giải thuật sắp xếp và tìm kiếm thao tác trực tiếp trên các liên kết con trỏ hoặc hoán đổi vùng dữ liệu của các nút.

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 tổng thể cho bài toán quản lý danh mục các khoa. Tác giả trình bày chi tiết định nghĩa cấu trúc dữ liệu Khoa, giải thích ý nghĩa và miền giá trị của từng trường dữ liệu (Hình 1). Đồng thời, tác giả công bố bảng dữ liệu mẫu chuẩn (Bảng 1) gồm 10 đơn vị quản lý thuộc trường cùng toàn bộ danh mục chức năng dự kiến xây dựng trên hai mô hình mảng tĩnh và danh sách liên kết đơn. Các chức năng bao gồm nhập/xuất cơ bản, 7 thuật toán sắp xếp trên mảng tĩnh, 4 thuật toán sắp xếp trên DSLK, cùng các giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân theo mã định danh khoa.

Chương 2: Tạo và quản lý bảng thông tin của khoa sử dụng mảng tĩnh

Chương 2 tập trung hiện thực hóa toàn bộ logic xử lý dữ liệu trên mảng tĩnh.

  • Nhập/xuất dữ liệu: Trình bày chi tiết mã nguồn hai chương trình con Nhap_Khoa(Khoa& k) và Nhap_DSKhoa(Khoa a[], int& n) (Hình 2, Hình 3), kèm hàm main kiểm tra (Hình 4) và kết quả chạy chương trình (Hình 5, Hình 6). Chương trình con Xuat_DsKhoa(Khoa a[], int& n) cùng kết quả in bảng thông tin được minh họa tại Hình 7, Hình 8 và Hình 9.
  • Các giải thuật sắp xếp danh sách theo MaKhoa:
    • Bubble Sort: Cài đặt chương trình con duyệt mảng và đổi chỗ phần tử liền kề (Hình 10, 11, 12).
    • Shaker Sort: Cải tiến nổi bọt hai chiều nhằm giảm số lần quét mảng (Hình 13, 14, 15, 16).
    • Interchange Sort: Cài đặt thuật toán đổi chỗ trực tiếp (Hình 17, 18, 19).
    • Selection Sort: Tìm phần tử nhỏ nhất để đưa về vị trí đầu dãy (Hình 20, 21, 22).
    • Insertion Sort: Chèn từng phần tử vào vị trí thích hợp trong dãy con đã sắp xếp (Hình 23, 24, 25, 26).
    • Quick Sort: Phân hoạch mảng dựa trên phần tử chốt (Pivot) và đệ quy sắp xếp hai nửa (Hình 27, 28, 29).
    • Merge Sort: Chia đôi mảng và trộn các dãy con đã sắp xếp (Hình 30, 31, 32, 33, 34).
  • Các giải thuật tìm kiếm theo MaKhoa:
    • Linear Search: Cài đặt duyệt tuần tự từ vị trí đầu đến cuối mảng (Hình 35, 36); kiểm thử thành công cả trường hợp tìm thấy (Hình 37) và không tìm thấy (Hình 38).
    • Binary Search: Cài đặt tìm kiếm nhị phân chia đôi phạm vi trên mảng đã sắp xếp (Hình 39, 40, 41); kiểm thử kết quả tìm thấy (Hình 42) và không tìm thấy (Hình 43).
  • Hệ thống Menu: Thiết kế giao diện menu điều khiển tích hợp đầy đủ các chức năng trên mảng tĩnh (Hình 44 đến Hình 50).

Chương 3: Tạo và quản lý danh sách thông tin của khoa sử dụng danh sách liên kết

Chương 3 chuyển dịch toàn bộ bài toán sang mô hình lưu trữ động với danh sách liên kết đơn.

  • Định nghĩa cấu trúc: Định nghĩa cấu trúc Khoa, định nghĩa Node và định nghĩa cấu trúc quản lý DSLK (Hình 51, 52, 53).
  • Các thao tác cơ bản:
    • Khởi tạo danh sách rỗng (Hình 54).
    • Quy trình nhập 4 bước: Nhập thông tin một khoa (Hình 55), Tạo Node (Hình 56), Chèn Node vào DSLK (Hình 57), Nhập danh sách thông tin (Hình 58, 59) và kết quả kiểm thử thực thi (Hình 60, 61).
    • Quy trình xuất danh sách 3 bước: Xuất thông tin một khoa (Hình 62), In Node (Hình 63), In toàn bộ DSLK ra màn hình (Hình 64, 65) và kết quả chạy (Hình 66).
  • Sắp xếp trên danh sách liên kết theo MaKhoa:
    • Cài đặt và thực nghiệm Bubble Sort trên DSLK (Hình 67, 68, 69, 70).
    • Cài đặt và thực nghiệm Selection Sort trên DSLK (Hình 71, 72, 73).
    • Cài đặt và thực nghiệm Interchange Sort trên DSLK (Hình 74, 75, 76).
  • Tìm kiếm trên danh sách liên kết theo MaKhoa:
    • Cài đặt giải thuật Linear Search duyệt qua các con trỏ liên kết (Hình 77, 78) và hiển thị kết quả kiểm thử thành công (Hình 79).

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

Đồ án đã hiện thực hóa trọn vẹn chương trình quản lý thông tin các khoa với đầy đủ các cấu trúc dữ liệu và giải thuật theo yêu cầu:

Tiêu chí Cấu trúc Mảng tĩnh Cấu trúc Danh sách liên kết đơn
Cơ chế cấp phát bộ nhớ Bộ nhớ tĩnh, kích thước cố định Bộ nhớ động, cấp phát theo từng Node
Thao tác Nhập / Xuất Nhap_DSKhoa, Xuat_DsKhoa Quy trình 4 bước tạo/chèn Node, in DSLK
Các thuật toán Sắp xếp 7 thuật toán: Bubble, Shaker, Interchange, Selection, Insertion, Quick, Merge Sort 3 thuật toán: Bubble, Selection, Interchange Sort
Các thuật toán Tìm kiếm 2 thuật toán: Linear Search và Binary Search 1 thuật toán: Linear Search
Giao diện điều khiển Menu điều hướng console phân nhánh chức năng Thực thi theo luồng các hàm kiểm thử độc lập

Đóng góp chính của đồ án gồm:

  • Xây dựng thành công bộ mã nguồn hoàn chỉnh trong việc cài đặt đối chiếu giữa hai dạng cấu trúc dữ liệu cơ bản (mảng tĩnh và danh sách liên kết đơn) cho cùng một bài toán quản lý đối tượng.
  • Minh họa rõ ràng cơ chế vận hành của 7 giải thuật sắp xếp và 2 giải thuật tìm kiếm thông qua các ca kiểm thử có hình ảnh chụp màn hình kết quả chạy thực tế.
  • Khẳng định tầm quan trọng của việc lựa chọn cấu trúc dữ liệu phù hợp nhằm tiết kiệm tài nguyên hệ thống và tối ưu hóa xử lý.

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

Dựa trên tự đánh giá của tác giả trong phần kết luận của báo cáo:

  • Hạn chế:
    • Độ phức tạp của chương trình còn ở mức cơ bản, chủ yếu cài đặt trực tiếp các giải thuật kinh điển mà chưa có các cơ chế tối ưu sâu.
    • Tiêu chí sắp xếp và tìm kiếm mới chỉ cố định dựa trên một trường khóa duy nhất là Mã khoa (MaKhoa), chưa đáp ứng linh hoạt theo nhu cầu đa dạng của người dùng (như sắp xếp theo Tên khoa, Số sinh viên hoặc Năm thành lập).
    • Các thao tác cập nhật danh sách (chỉnh sửa thông tin khoa, xóa một khoa bất kỳ) vẫn còn một số khuyết điểm và chưa được hoàn thiện toàn diện.
  • Hướng phát triển:
    • Tối ưu hóa hiệu năng và giảm thiểu độ phức tạp tính toán cho các thao tác trên danh sách.
    • Bổ sung chức năng sắp xếp và lọc dữ liệu đa tiêu chí theo yêu cầu tùy biến của người sử dụng.
    • Hoàn thiện module cập nhật dữ liệu (thêm, sửa, xóa vị trí bất kỳ) trên cả mảng tĩnh và danh sách liên kết.

Giá trị tham khảo

Đồ án là tài liệu tham khảo có giá trị thực tiễn đối với:

  • Sinh viên ngành Công nghệ Thông tin: Là tài liệu học tập trực quan cho học phần Cấu trúc dữ liệu và Giải thuật, giúp nắm vững cú pháp cài đặt con trỏ, cấp phát động, định nghĩa cấu trúc và thuật toán sắp xếp/tìm kiếm.
  • Người học lập trình C/C++: Tham khảo phương pháp xây dựng hệ thống menu trên màn hình Console và kỹ thuật module hóa chương trình thành các hàm con chuyên biệt (Nhap_Khoa, Nhap_DSKhoa, CreateNode, AddTail).
  • Nghiên cứu ứng dụng: Phần so sánh giữa mảng tĩnh và danh sách liên kết đơn là mẫu tham khảo hữu ích cho các bài toán quản lý danh mục quy mô nhỏ trong môi trường học thuật.

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

1. Cấu trúc dữ liệu Khoa trong đồ án bao gồm những trường thông tin nào?

Cấu trúc quản lý đối tượng khoa bao gồm 6 trường dữ liệu: Mã khoa (MaKhoa - xâu ký tự), Tên khoa (TenKhoa - chuỗi ký tự < 40), Trưởng khoa (TruongKhoa - chuỗi ký tự < 40), Năm thành lập (NamTL - số nguyên), Số sinh viên (SoSV - số nguyên), và Tỷ lệ sinh viên/giảng viên (TyLe hoặc SV_GV - số thực).

2. Có bao nhiêu thuật toán sắp xếp đã được cài đặt trên cấu trúc mảng tĩnh?

Trên cấu trúc mảng tĩnh, đồ án đã cài đặt và thực nghiệm 7 thuật toán sắp xếp theo khóa MaKhoa, bao gồm: Bubble Sort, Shaker Sort, Interchange Sort, Selection Sort, Insertion Sort, Quick Sort và Merge Sort.

3. Quy trình 4 bước nhập dữ liệu cho danh sách liên kết đơn được thực hiện như thế nào?

Quy trình nhập dữ liệu vào DSLK gồm 4 bước:

  1. Nhập thông tin cho một đối tượng khoa thông qua hàm Nhap_Khoa.
  2. Tạo nút mới và gán dữ liệu khoa vào nút thông qua hàm tạo Node.
  3. Chèn nút vừa tạo vào danh sách liên kết (sử dụng hàm chèn nút).
  4. Thực hiện lặp lại quá trình để đưa toàn bộ danh sách các khoa vào danh sách liên kết.

4. Thuật toán tìm kiếm nhị phân (Binary Search) được áp dụng trên cấu trúc dữ liệu nào và dựa trên điều kiện gì?

Thuật toán tìm kiếm nhị phân được áp dụng riêng cho cấu trúc mảng tĩnh (Chương 2). Thuật toán này hoạt động dựa trên trường khóa MaKhoa và đòi hỏi mảng dữ liệu các khoa phải được sắp xếp theo thứ tự trước khi thực hiện tìm kiếm.

5. Dữ liệu mẫu thực nghiệm trong đề tài gồm những đơn vị nào?

Tập dữ liệu mẫu gồm 10 khoa thuộc Trường Đại học Tài chính – Marketing: Thuế - Hải quan (THQ01), Tài chính - Ngân hàng (TNH02), Kế toán - Kiểm toán (KTT03), Marketing (MKT04), Quản trị kinh doanh (BSA05), Thẩm định giá - Kinh doanh Bất động sản (BDS06), Thương mại (CME07), Du lịch (TV008), Ngoại ngữ (ELH09) và Công nghệ thông tin (IT010).

Kết luận

Báo cáo đồ án môn học "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 thành công bài toán mô hình hóa và xử lý dữ liệu quản lý các khoa đào tạo bằng ngôn ngữ lập trình C/C++. Tác giả đã hoàn thành việc thiết kế, cài đặt và kiểm thử 7 thuật toán sắp xếp cùng 2 thuật toán tìm kiếm trên cấu trúc mảng tĩnh, đồng thời chuyển đổi thành công sang cấu trúc danh sách liên kết đơn. Mặc dù vẫn còn hạn chế về tính tùy biến tiêu chí sắp xếp và các thao tác cập nhật dữ liệu, công trình đã thể hiện rõ ràng phương pháp tư duy giải thuật và là tài liệu tham khảo thiết thực cho sinh viên theo học bộ môn Cấu trúc dữ liệu và Giải thuật.