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

Bối cảnh thực tiễn của đề tài

Trong môi trường giáo dục phổ thông, công tác quản lý thông tin học tập và theo dõi điểm số của học sinh là một nghiệp vụ trọng yếu, diễn ra thường xuyên trong suốt năm học. Quá trình này đòi hỏi việc lưu trữ, cập nhật và xử lý một lượng lớn dữ liệu liên quan đến hồ sơ cá nhân của học sinh, thông tin các môn học trong chương trình giảng dạy, cũng như kết quả đánh giá qua từng bài kiểm tra. Việc quản lý điểm không chỉ phục vụ trực tiếp cho người học trong việc nắm bắt kết quả học tập sau mỗi kỳ học mà còn là cơ sở dữ liệu quan trọng để nhà trường, giáo viên chủ nhiệm và ban giám hiệu theo dõi sát sao quá trình rèn luyện của từng cá nhân. Qua đó, nhà trường có thể kịp thời đưa ra các quyết định khen thưởng đối với học sinh đạt thành tích tốt hoặc áp dụng biện pháp đôn đốc, cảnh cáo đối với những học sinh có kết quả học tập chưa đạt yêu cầu.

Nhằm giải quyết bài toán quản lý trên phương diện kỹ thuật phần mềm cơ sở, đề tài "Bài toán Quản lý học tập của học sinh phổ thông" (Đề số 6) được thực hiện dưới dạng báo cáo bài tập lớn môn Cấu trúc dữ liệu và giải thuật tại Khoa Công nghệ Thông tin – Trường Đại học Mở Hà Nội (năm 2021), dưới sự hướng dẫn của ThS. Trịnh Thị Xuân.

Mục tiêu và nhiệm vụ nghiên cứu

Mục tiêu cốt lõi của báo cáo là vận dụng các cấu trúc dữ liệu trừu tượng và giải thuật kinh điển để tin học hóa quy trình quản lý học sinh, môn học và bảng điểm. Báo cáo phân chia các nhiệm vụ cụ thể thành các bước logic:

  1. Xác định và mô hình hóa bài toán: Phân tích ngữ cảnh thực tế của công tác quản lý điểm tại trường phổ thông; nhận diện các thực thể cần quản lý và xác định các thuộc tính cấu thành.
  2. Thiết kế cấu trúc dữ liệu: Xây dựng mô hình dữ liệu biểu diễn ba đối tượng cốt lõi: Học sinh, Môn học và Bảng điểm; lựa chọn các kiểu cấu trúc dữ liệu phù hợp để tổ chức các tập dữ liệu động.
  3. Đặc tả các chức năng hệ thống: Xây dựng danh mục các chức năng nghiệp vụ chi tiết cho từng phân hệ (quản lý học sinh, quản lý môn học, quản lý bảng điểm) bao gồm các thao tác nhập, xuất, tìm kiếm, lọc, sửa đổi, sắp xếp, thống kê và lưu trữ tệp.
  4. Lập trình và cài đặt: Cài đặt toàn bộ chương trình trên ngôn ngữ lập trình C++, hiện thực hóa các chức năng thông qua ba cấu trúc dữ liệu chuyên biệt: Danh sách liên kết đơn (Singly Linked List), Danh sách liên kết đôi (Doubly Linked List) và Ngăn xếp (Stack).
  5. Lập bộ kiểm thử (Testing): Thiết kế và thực thi các kịch bản kiểm thử (bộ test) nhằm đánh giá tính chính xác, tính ổn định và khả năng xử lý của các thuật toán đã cài đặt.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Cấu trúc dữ liệu và giải thuật trong xử lý thông tin; cụ thể là danh sách liên kết đơn, danh sách liên kết đôi, ngăn xếp, cùng các thuật toán thêm, xóa, tìm kiếm, duyệt, sắp xếp và đọc/ghi tệp nhị phân.
  • Phạm vi nghiệp vụ: Nghiệp vụ quản lý học tập cấp trung học phổ thông, tập trung vào ba thực thể: Hồ sơ học sinh, Danh mục môn học và Kết quả bảng điểm (điểm miệng, điểm 15 phút, điểm 1 tiết và điểm trung bình).
  • Phạm vi kỹ thuật và môi trường: Chương trình giao diện dòng lệnh (CLI/Console) viết bằng C++, thực hiện lưu trữ dữ liệu bền vững thông qua tệp dữ liệu nhị phân (.dat).

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

Khung lý thuyết và mô hình cấu trúc dữ liệu

Đề tài dựa trên nền tảng lý thuyết của môn học Cấu trúc dữ liệu và giải thuật, tập trung vào việc quản lý bộ nhớ động và xử lý danh sách tuyến tính:

  • Danh sách liên kết đơn (Singly Linked List): Cấu trúc dữ liệu gồm các nút (Node), mỗi nút chứa dữ liệu thực thể (info) và một con trỏ (next) trỏ tới nút kế tiếp trong bộ nhớ heap. Thao tác chèn đầu danh sách (addFirst) được sử dụng để tối ưu hóa thời gian chèn $O(1)$.
  • Danh sách liên kết đôi (Doubly Linked List): Cấu trúc mở rộng với hai con trỏ tại mỗi nút (next và prev), cho phép duyệt dữ liệu hai chiều thuận - nghịch linh hoạt.
  • Ngăn xếp (Stack): Cấu trúc dữ liệu trừu tượng hoạt động theo nguyên tắc LIFO (Last In, First Out), hỗ trợ các thao tác lưu trữ và truy xuất thông tin theo thứ tự đảo ngược.
  • Xử lý tệp nhị phân (Binary File I/O): Sử dụng thư viện chuẩn stdio.h với các hàm fopen, fwrite, fread, feof, fclose để lưu trữ trực tiếp các struct dữ liệu dạng nhị phân xuống đĩa cứng (Bangdiem.dat).

Phương pháp nghiên cứu và phân công thực hiện

Báo cáo sử dụng phương pháp phân tích thiết kế hướng cấu trúc kết hợp lập trình thủ tục (Procedural Programming) trong C++. Đề tài tổ chức triển khai thông qua việc phân chia module độc lập cho từng thành viên trong nhóm nghiên cứu.

Họ và tên Mã sinh viên Nội dung công việc phân công Tình trạng thực hiện
Nguyễn Huy Hải 2010A01 Cài đặt Danh sách liên kết đơn (DSLK Đơn) Hoàn thành
Đặng Quang Huy 2010A04 Cài đặt Danh sách liên kết đơn (DSLK Đơn) Hoàn thành
Nguyễn Quốc Hiếu 2010A04 Cài đặt Danh sách liên kết đôi (DSLK Đôi) Hoàn thành
Hoàng Trọng Mạnh 2010A03 Cài đặt Cấu trúc Ngăn xếp (Stack) Hoàn thành

Thiết kế và triển khai hệ thống

Mô hình hóa các thực thể dữ liệu

Báo cáo xác định ba thực thể cấu thành hệ thống quản lý học tập và mô hình hóa thành các cấu trúc dữ liệu (struct) trong C++:

struct HOCSINH {
    int maHs;
    string hoTen, gioiTinh, ngaySinh, diaChi;
};

struct Monhoc {
    int maMh, soTiet, soBuoi;
    string tenMonhoc;
};

struct BangDiem {
    int maDiem, maHocSinh, maMonHoc, sohocsinh, somonhoc;
    float diemMieng, diem15p, diem1tiet, diemTB;
    Monhoc dsmh[20];
    HOCSINH ds[20];
};

Đặc tả kiến trúc chức năng hệ thống

Chương trình được thiết kế theo cấu trúc phân cấp thông qua hệ thống menu tương tác console:

Phân hệ quản lý Mã chức năng Chi tiết thao tác nghiệp vụ
1. Quản lý học sinh 1.1 Nhập danh sách học sinh từ bàn phím
1.2 In danh sách học sinh ra màn hình có định dạng cột
1.3 Lưu danh sách học sinh vào file
1.4 Đọc danh sách học sinh từ file
1.5 Tìm kiếm học sinh theo mã học sinh
1.6 Tìm kiếm học sinh theo lớp
1.7 Sắp xếp danh sách học sinh tăng dần theo mã học sinh
1.8 Thêm một học sinh mới vào danh sách
1.9 Xóa một học sinh khỏi danh sách
2. Quản lý môn học 2.1 Nhập và hiện danh sách môn học, ghi dữ liệu vào file
2.2 Hiện danh sách môn học lên màn hình
2.3 Lọc và in tên các môn học có số tiết lớn hơn $x$
2.4 Sắp xếp danh sách theo thứ tự giảm dần của số buổi học
2.5 Đếm tổng số lượng môn học hiện có
2.6 Lọc và hiển thị các môn học có số buổi học lớn hơn 10
2.7 Tính tổng số buổi học của toàn bộ môn học trong danh sách
2.8 Đọc dữ liệu môn học từ file
3. Quản lý bảng điểm 3.1 Nhập danh sách điểm và ghi dữ liệu ra file
3.2 Hiển thị toàn bộ bảng điểm lên màn hình
3.3 Tìm kiếm bảng điểm chi tiết theo mã học sinh
3.4 Tìm và hiển thị bảng điểm có điểm trung bình cao nhất (bangMax)
3.5 Xóa thông tin bảng điểm ở đầu danh sách (removeBang)
3.6 Sắp xếp danh sách bảng điểm tăng dần theo điểm trung bình (sapxepTang)
3.7 Lọc và hiển thị bảng điểm có điểm trung bình lớn hơn ngưỡng $x$ (hienTT)
3.8 Chỉnh sửa thông tin bảng điểm theo mã học sinh (suaBangDiem)
3.9 Đọc dữ liệu bảng điểm từ file nhị phân Bangdiem.dat

Chi tiết giải thuật cài đặt

  • Thuật toán tính điểm trung bình: Điểm trung bình môn được tính toán tự động dựa trên trọng số các bài kiểm tra theo công thức: $$\text{diemTB} = \frac{\text{diemMieng} + \text{diem15p} + \text{diem1tiet} \times 3}{6}$$
  • Thuật toán sắp xếp đổi chỗ (Interchange Sort trên danh sách liên kết): Sử dụng hai con trỏ lồng nhau $p$ và $q$ ($q = p \rightarrow \text{next}$) để duyệt qua danh sách, so sánh trường diemTB và tráo đổi vùng thông tin info giữa hai nút.
  • Thuật toán tìm giá trị cực đại (bangMax): Duyệt qua toàn bộ danh sách liên kết để tìm giá trị diemTB lớn nhất, sau đó duyệt lại danh sách để in ra tất cả các bản ghi có điểm trung bình bằng giá trị cực đại này.
  • Thuật toán quản lý bộ nhớ: Cấp phát động từng nút bằng toán tử new Node..., kiểm tra lỗi tràn bộ nhớ (p == NULL), và giải phóng bộ nhớ khi xóa phần tử đầu bằng toán tử delete.

Nội dung chính theo từng phần của báo cáo

Phần I: Xác định bài toán

Nội dung phần I tập trung vào việc mô tả bối cảnh bài toán thực tế trong các trường phổ thông. Tác giả chỉ rõ tầm quan trọng của việc tin học hóa hồ sơ học sinh và điểm số nhằm giảm thiểu sai sót thủ công, hỗ trợ nhà trường đánh giá năng lực học sinh định kỳ. Phần này đồng thời đưa ra danh mục các trường thông tin cần quản lý cho từng thực thể (Học sinh, Môn học, Bảng điểm) và xây dựng sơ đồ chức năng hệ thống thông qua các menu điều khiển.

Phần IV: Lập trình – cài đặt

Đây là nội dung trọng tâm của báo cáo (từ trang 6 đến trang 78), trình bày toàn bộ mã nguồn C++ được chia thành ba phương án cấu trúc dữ liệu:

1. Cài đặt bằng Danh sách liên kết đơn (trang 6 - 29)

Tác giả định nghĩa các kiểu dữ liệu NodeHocSinh, List, NodeMonhoc, ListMonhoc, NodeDiem, ListDiem. Toàn bộ các thao tác cơ bản và nâng cao đều được hiện thực:

  • Khởi tạo danh sách rỗng (initHs, initMh, initBd).
  • Tạo nút mới (getNode, getNodem, getNodeD).
  • Thêm phần tử vào đầu danh sách (addFirst, addFirstMonhoc, addFirstBang).
  • Nhập/xuất dữ liệu có định dạng bằng thư viện iomanip (setw).
  • Tìm kiếm tuyến tính trên danh sách liên kết theo khóa chính (timKiembangtheoMa).
  • Xóa phần tử đầu danh sách (removeBang) kèm giải phóng bộ nhớ.
  • Sắp xếp danh sách bảng điểm tăng dần theo điểm trung bình (sapxepTang).
  • Ghi dữ liệu dạng khối nhị phân vào tệp Bangdiem.dat bằng fwrite và nạp dữ liệu từ tệp vào danh sách bằng fread.
  • Hàm điều khiển menuBangDiem() và hàm chính main() chứa vòng lặp do...while điều hướng tương tác người dùng.

2. Cài đặt bằng Danh sách liên kết đôi (trang 30 trở đi)

Trình bày phương án cấu trúc dữ liệu mở rộng với các nút chứa hai liên kết next và prev. Các hàm tạo nút getNode và getNodem được bổ sung việc gán giá trị khởi tạo p->prev = NULL; p->next = NULL;. Phương án này giúp tăng tính linh hoạt khi duyệt danh sách từ cả hai phía và tối ưu hóa thao tác xóa nút trung gian.

3. Cài đặt bằng Ngăn xếp (Stack)

Tác giả cài đặt giải thuật quản lý dữ liệu dựa trên nguyên lý vào sau - ra trước (LIFO), phục vụ việc lưu trữ tạm thời các thao tác xử lý hoặc danh sách điểm cần truy xuất ngược thời gian nhập.

Phần Lập bộ test (trang 79)

Phần cuối của báo cáo xây dựng các bộ dữ liệu kiểm thử (test case) nhằm xác minh tính đúng đắn của toàn bộ các hàm chức năng. Các trường hợp kiểm thử bao gồm:

  • Kiểm thử nhập/xuất dữ liệu thông thường với nhiều bản ghi.
  • Kiểm thử tìm kiếm với mã học sinh tồn tại và không tồn tại.
  • Kiểm thử tìm điểm trung bình cao nhất khi có một hoặc nhiều học sinh đồng điểm cao nhất.
  • Kiểm thử sắp xếp trên danh sách có dữ liệu đảo lộn.
  • Kiểm thử tính toàn vẹn dữ liệu khi ghi ra file Bangdiem.dat và đọc lại sau khi khởi động lại chương trình.

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

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

Báo cáo hoàn thành đầy đủ các mục tiêu thiết kế và cài đặt theo đúng yêu cầu của môn học Cấu trúc dữ liệu và giải thuật:

  • Xây dựng thành công hệ thống chương trình C++ hoàn chỉnh quản lý đồng thời ba thực thể: Học sinh, Môn học, Bảng điểm.
  • Triển khai thành công 9 chức năng quản lý học sinh, 8 chức năng quản lý môn học và 9 chức năng quản lý bảng điểm trên giao diện dòng lệnh.
  • Cài đặt và đối sánh thành công ba cấu trúc dữ liệu kinh điển: Danh sách liên kết đơn, Danh sách liên kết đôi và Ngăn xếp.
  • Hiện thực hóa cơ chế lưu trữ dữ liệu bền vững bằng tệp nhị phân Bangdiem.dat, đảm bảo dữ liệu không bị mất sau khi kết thúc phiên làm việc của chương trình.
  • Cả 4 thành viên trong nhóm nghiên cứu hoàn thành 100% khối lượng công việc được giao theo bảng phân công kế hoạch.

Đóng góp thực tiễn và học thuật

  • Về mặt kỹ thuật: Cung cấp mã nguồn mẫu chuẩn mực cho bài toán quản lý trên C++, thể hiện rõ ràng các thao tác cấp phát bộ nhớ động, quản lý con trỏ, giải phóng bộ nhớ tránh rò rỉ (memory leak), và định dạng xuất dữ liệu dạng bảng bằng iomanip.
  • Về mặt phương pháp: Minh họa phương pháp tiếp cận từ bài toán thực tế -> mô hình hóa dữ liệu -> thiết kế thuật toán -> cài đặt mã nguồn đa cấu trúc dữ liệu -> kiểm thử hệ thống.

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

Hạn chế của đề tài

Dựa trên phạm vi nội dung được trình bày trong báo cáo bài tập lớn:

  • Giao diện người dùng vẫn ở dạng dòng lệnh (Console/CLI), việc nhập liệu và điều hướng menu qua các phím số có thể gây bất tiện khi số lượng bản ghi lớn.
  • Kích thước mảng tĩnh phụ trợ trong cấu trúc BangDiem còn bị giới hạn cố định (Monhoc dsmh[20]; HOCSINH ds[20];).
  • Hệ thống tệp sử dụng định dạng nhị phân nguyên thủy của C (stdio.h), chưa áp dụng các hệ quản trị cơ sở dữ liệu quan hệ (RDBMS) để xử lý ràng buộc khóa ngoại chặt chẽ giữa mã học sinh trong bảng điểm và mã học sinh trong danh sách học sinh.

Hướng phát triển

  • Mở rộng xây dựng giao diện đồ họa người dùng (GUI) hoặc chuyển đổi sang nền tảng ứng dụng web.
  • Nâng cấp cơ chế lưu trữ sang các hệ quản trị cơ sở dữ liệu như MySQL hoặc SQLite.
  • Bổ sung các giải thuật tìm kiếm nâng cao (như tìm kiếm nhị phân trên danh sách đã sắp xếp) và các giải thuật sắp xếp nâng cao (Quick Sort, Merge Sort) để tối ưu hiệu năng xử lý với tập dữ liệu quy mô lớn.

Giá trị tham khảo

Tài liệu này là nguồn tài liệu 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 và Khoa học Máy tính: Đặc biệt là sinh viên đang học tập các học phần Cấu trúc dữ liệu và giải thuật, Lập trình C/C++, và Nhập môn Kỹ thuật phần mềm.
  • Người học cần tài liệu mẫu về cấu trúc dữ liệu: Cung cấp cách cài đặt chi tiết từng bước của danh sách liên kết đơn, danh sách liên kết đôi, ngăn xếp, kèm các thao tác xử lý tệp nhị phân trong C++.
  • Các nhóm sinh viên làm bài tập lớn/đồ án môn học: Cung cấp khung cấu trúc chuẩn của một báo cáo bài tập lớn kỹ thuật, từ phân tích bài toán, phân chia công việc, thiết kế thực thể đến lập bộ kiểm thử.

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

1. Đề tài sử dụng những cấu trúc dữ liệu nào để cài đặt bài toán?

Đề tài sử dụng ba cấu trúc dữ liệu chính để cài đặt chương trình:

  1. Danh sách liên kết đơn (Singly Linked List): Được cài đặt cho cả ba thực thể Học sinh, Môn học và Bảng điểm.
  2. Danh sách liên kết đôi (Doubly Linked List): Được mở rộng với hai con trỏ next và prev cho các thực thể.
  3. Ngăn xếp (Stack): Được cài đặt để xử lý dữ liệu theo cơ chế LIFO.

2. Công thức tính điểm trung bình (diemTB) của học sinh được quy định như thế nào trong mã nguồn?

Điểm trung bình được tính toán tự động trong hàm nhapBang theo công thức tính điểm có hệ số: $$\text{diemTB} = \frac{\text{diemMieng} + \text{diem15p} + \text{diem1tiet} \times 3}{6}$$ Trong đó, điểm miệng và điểm 15 phút tính hệ số 1, điểm 1 tiết tính hệ số 3, tổng hệ số chia là 6.

3. Phân hệ Quản lý bảng điểm cung cấp những chức năng cụ thể nào?

Phân hệ bảng điểm gồm 9 chức năng:

  • Nhập danh sách điểm và ghi dữ liệu ra file.
  • Hiện danh sách bảng điểm lên màn hình.
  • Tìm kiếm bảng điểm theo mã học sinh.
  • Hiển thị bảng điểm có điểm trung bình cao nhất.
  • Xóa thông tin bảng điểm ở đầu danh sách.
  • Sắp xếp danh sách bảng điểm theo thứ tự tăng dần của điểm trung bình.
  • Lọc và hiển thị các bảng điểm có điểm trung bình lớn hơn ngưỡng $x$.
  • Sửa thông tin bảng điểm theo mã học sinh.
  • Đọc dữ liệu bảng điểm từ file nhị phân Bangdiem.dat.

4. Dữ liệu bảng điểm được lưu trữ xuống đĩa cứng bằng cơ chế nào?

Chương trình sử dụng các hàm xử lý tệp nhị phân trong thư viện stdio.h:

  • Hàm ghiFile2: Mở tệp Bangdiem.dat ở chế độ ghi nhị phân ("wb"), duyệt qua danh sách liên kết và ghi từng khối sizeof(BangDiem) bằng hàm fwrite.
  • Hàm docFile2: Khởi tạo lại danh sách rỗng, mở tệp Bangdiem.dat ở chế độ đọc nhị phân ("rb"), sử dụng vòng lặp fread kết hợp kiểm tra kết thúc tệp feof(f) để nạp từng bản ghi vào danh sách liên kết qua hàm addFirstBang.

5. Sự phân công nhiệm vụ giữa các thành viên trong nhóm được tổ chức ra sao?

Nhóm gồm 4 sinh viên, mỗi thành viên đảm nhận một nội dung kỹ thuật độc lập:

  • Nguyễn Huy Hải (2010A01): Phụ trách cài đặt Danh sách liên kết đơn.
  • Đặng Quang Huy (2010A04): Phụ trách cài đặt Danh sách liên kết đơn.
  • Nguyễn Quốc Hiếu (2010A04): Phụ trách cài đặt Danh sách liên kết đôi.
  • Hoàng Trọng Mạnh (2010A03): Phụ trách cài đặt Ngăn xếp (Stack). Tất cả các thành viên đều được ghi nhận trạng thái "Hoàn thành" công việc trong báo cáo.

Kết luận

Báo cáo bài tập lớn "Bài toán Quản lý học tập của học sinh phổ thông" của nhóm sinh viên Khoa Công nghệ Thông tin – Trường Đại học Mở Hà Nội đã giải quyết trọn vẹn yêu cầu nghiệp vụ quản lý học sinh, môn học và bảng điểm ở mức độ cơ sở dữ liệu bộ nhớ trong. Đề tài thể hiện năng lực vận dụng vững chắc các cấu trúc dữ liệu tuyến tính (danh sách liên kết đơn, danh sách liên kết đôi, ngăn xếp) và các giải thuật xử lý mảng/con trỏ trên ngôn ngữ C++. Toàn bộ hệ thống được cài đặt hoàn chỉnh, có cơ chế lưu trữ tệp nhị phân bền vững và được kiểm thử qua các bộ dữ liệu cụ thể, tạo nên một tài liệu tham khảo thực hành có giá trị cho sinh viên chuyên ngành công nghệ thông tin.