Quản lý sinh viên trong lớp học | Bài tập lớn Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội

ĐẠI HỌC BÁCH KHOA HÀ NỘI
TRƯỜNG ĐIỆN-ĐIỆN TỬ
----------------------------------------------------
BÁO CÁO MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ĐỀ TÀI:
QUẢN LÝ SINH VIÊN TRONG LỚP HỌC
Sinh viên thực hiện: Trần Đình Vương 20214154 Cao Danh Khang 20213967 Ngô Thái Bình 20213820 Cao Việt Bình 20213818
Giảng viên: Trần Thị Thanh Hải Hà N i-202 ộ 3 Mc lc I.
Giới thiệu........................................................................2 1. Lý do và động lực 2 2. Định nghĩa bài toán 2
3. Bảng phân công nhiệm vụ và đánh giá mức độ hoàn thành 3
II. Phương pháp lựa chọn..................................................4 1. Cấu trúc dữ liệu 4 2. Giải thuật 8
III. Triển khai cài đặt.........................................................11
1. Ngôn ngữ lập trình và thư viện 11
2. Tổ chức chương trình và đóng gói 11
IV. Kết quả thực nghiệm...................................................12 1. Dữ liệu 12 2.
Các kết quả thực nghiệm 12 V.
Kết luận.........................................................................18
1. Đánh giá về mức độ hoàn thành 18 2. Bài học rút ra 19
3. Khó khăn khi học tập môn học 19
VI. Tài liệu tham khảo.......................................................20
VII. Lời cảm ơn....................................................................20 1 I. Giới thiệu
1. Lý do và động lực
 Để đáp ứng yêu cầu môn học cũng như mong muốn tìm hiểu, mở rộng kiến
thức về ngôn ngữ lập trình nói chung và môn cấu trúc dữ liệu và giải thuật
nói riêng, nhóm chúng em đã cùng nhau hướng đến những đề tài hướng với những tiêu chí:  Hữu ích
 Có tính thực tế, khả thi
 Áp dụng được kiến thức đã học
 Học hỏi them kiến thức mới với tối đa khả năng của bản than
 Với những tiêu chí đó, nhóm chúng em đã lựa chọn chủ đề “Quản lý sinh
viên” để triển khai thực hiện.
Đây là một chủ đề mở, có rất nhiều hướng đi cũng như hướng phát triển
2. Định nghĩa bài toán
 Input: Dữ liệu của sinh viên:  Họ và tên  Mã số sinh viên  Thông tin môn học:  Tên môn học  Mã học phần  Số tín chỉ  Điểm giữa kì  Số buổi vắng
 Output: Những kết quả đã qua xử lý
 Danh sách các sinh viên xếp theo MSSV
 Điểm quá trình của sinh viên
 Sinh viên được tìm kiếm  File danh sách lớp
3. Bảng phân công nhiệm vụ và đánh giá mức độ hoàn thành 2 Họ và tên MSSV Nhiệm vụ Mức độ hoàn thành  Tìm hiểu đề tài  Lên ý tưởng Trần Đình Vương 20214154
 Triển khai và cài đặt chương Đã hoàn thành trình- Coder phụ  Phát triển sản phẩm
 Làm báo cáo phần I,II,II  Tìm hiểu đề tài  Lên ý tưởng
 Triển khai và cài đặt chương Cao Danh Khang 20213967 trình-Coder chính Đã hoàn thành
 Phổ biến kiến thức mới cho cả nhóm  Phát triển sản phẩm
 Làm báo cáo phần I,II,III  Tìm hiểu đề tài
 Tìm hiểu CSDL LinkedList Ngô Thái Bình 20213820  Tìm hiểu thư viện Đã hoàn thành  Theo dõi tiến trình  Làm báo cáo phần IV,V  Tìm hiểu đề tài  Tìm hiểu giải thuật Cao Việt Bình 20213818 Binary Search và QuickSort Đã hoàn thành  Tìm hiểu thư viện
 Làm PowerPoint giới thiệu
 Làm báo cáo phần IV,V,VI
II. Phương pháp lực chọn
1. Cấu trúc dữ liệu  Linked List
Linked list là một cấu trúc tuần tự bao gồm một chuỗi các item theo thứ tự tuyến
tính được liên kết với nhau. Do đó, ta chỉ có thể truy cập tuần tự vào linked list,
không thể thực hiện truy cập ngẫu nhiên. Linked list là cung cấp cho chúng ta một
cấu trúc dữ liệu đơn giản và linh hoạt cho các tập hợp động 3
 Các phần tử trong linked list được gọi là các node.
 Mỗi node sẽ chưa một key và một con trỏ trỏ tới node kế tiếp của nó, được gọi là next
 Thuộc tính tên là head trỏ tới phần tử đầu tiên của linked list.
 Phần tử cuối cùng của linked list có tên là tail
Một số loại linked list có thể kể tới bao gồm:
 Singly linked list: Duyệt qua các phẩn tử chỉ có thể thực hiện theo chiều hướng về phía trước.
 Doubly linked list: Duyệt qua các phẩn tử có thể thực hiện theo cả chiều tiến
và lùi. Các node sẽ bao gồm thêm một con trỏ được gọi là pre, trỏ tới node trước đó.
 Circular linked list: Là một doubly linked list đặc biệt, khi mà con trỏ prev
của head trỏ tới tail và con trỏ next của tail trỏ tới head.
Các phép toán trên linked list
 Tìm kiếm: Tìm phần tử đầu tiên với key là k trong một linked list được cho trước được thực h
đơn giản bằng một quá trình duyệt iện tuần tự và trả về
con trỏ trỏ tới phần tử đó.
 Thêm: Để thêm một key vào một linked list có sẵn, ta có thể thực hiện theo
3 cách: thêm vào đầu list, thêm vào giữa list hoặc thêm vào cuối của list.
 Xoá: Xoá một phần tử khỏi một linked list cho trước. x Ta không thể xoá
một node với chỉ một bước. Việc xoá một node có thể thực hiện theo 3 cách:
xoá từ đầu danh sách, xoá từ giữa danh sách hoặc xoá từ cuối danh sách. Ưu điểm:
 Tiết kiếm bộ nhớ và cấp phát động: Không như array cần 1 lượng chỉ định ô
nhớ trên bộ nhớ ngay khi khỏi tạo. Linked list chỉ sử dụng bộ nhớ để lưu trữ
khi dữ liệu thực sự được lưu vào linked list.
 Nó còn có thể lưu các phần tử ở bất cứ đâu được phép trên bộ nhớ mà không
cần các ô nhớ liền kề nhau như array 4
 Quick insertion (Thêm rất nhanh với complexity chỉ là O(1))
 Quick deletion (Xóa nhanh)
Một số áp dụng Linked List trong chương trình:  Xóa sinh viên:  Thêm sinh viên: 5  Thêm học phần  Xóa học phần  Điểm danh: 6 2. Giải thuật  Binary Search
 Thuật toán tìm kiếm nhị phân (Binary Search) hay còn được gọi là tìm
kiếm một nửa là thụât toán tiếp kiếm được sử dụng rất nhiều trong thực tế
cho phép tìm kiếm vị trí của một phần tử trong một mảng đã được sắp xếp.
 Thụât toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp
bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa.
+ Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. 7
+ Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa
khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và ngược lại.
+ Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.
 Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết
tính ở các mảng có độ dài lớn và đã được sắp xếp.
 Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai
trên các mảng nhỏ và chưa được sắp xếp.
 Ý tưởng triển khai thuật toán
Cho một mảng đã sắp xếp arr[] có n phần tử, viết một hàm tìm kiếm trả về
chỉ số của phần tử có giá trị x trong arr[].
+ Xét một đoạn trong mảng arr[left...right]. Lúc này giá trị của left và right
lần luợt là 0 và số phần tử của mảng - 1.
+ So sánh x với phần tử nằm ở vị trí chính giữa của mảng (mid = (left +
right) /2). Nếu x bằng arr[mid] thì trả về vị trí và thoát vòng lặp.
+ Nếu x < arr[mid] thì chắc chắn x sẽ nằm ở phía bên trái tức là
từ arr[left....mid-1].
+ Nếu x > arr[mid] thì chắc chắn x sẽ nằm ở phía bên phải mid tức là ở
khoảng arr[mid+1...right].
+ Tiếp tục thực hiện chia đôi các khoảng tìm kiếm tới khi nào tìm thấy được
vị trí của x trong mảng hoặc khi đã duyệt hết mảng.  Độ phức tạp:
+ Trường hợp tốt nhất là O(1)
+ Trường hợp xấu nhất là O(log2n)
+ Trung bình cũng là O(log2n) 8
 Áp dụng giải thuật Binary Search trong chương trình:
 Giải thuật sắp xếp nhanh QuickSort:
- Quick sort là thuật toán sắp xếp, hoạt động theo cách sau: Chọn một phần
tử trong mảng làm điểm đánh dấu và sau đó chia mảng thành hai mảng con
bằng cách so sánh các phần tử trong mảng với điểm đánh dấu. Mảng 1 sẽ
chứ các phần tử nhỏ hơn hoặc bằng điểm đánh dấu và mảng 2 sẽ gồm các
phần tử lớn hơn điểm đánh dấu. - Thực hiện:  Chọn phần tử chốt.
 Khai báo 2 biến con trỏ để trỏ để duyệt 2 phía của phần tử chốt.
 Biến bên trái trỏ đến từng phần tử mảng con bên trái của phần tử chốt.
 Biến bên phải trỏ đến từng phần tử mảng con bên phải của phần tử chốt.
 Khi biến bên trái nhỏ hơn phần tử chốt thì di chuyển sang phải.
 Khi biến bên phải nhỏ hơn phần tử chốt thì di chuyển sang trái. 9
 Nếu không xảy ra trưởng hợp 5 và 6 thì tráo đổi giá trị 2 biến trái và phải.
 Nếu trái lớn hơn phải thì đây là giá trị chốt mới.
- Áp dụng QuickSort trong chương trình:
III. Triển khai cài đặt 10
1. Ngôn ngữ lập trình và thư viện
 Ngôn ngữ lập trình: Ở đây nhóm chúng em sử dụng C++
 C ++ là một ngôn ngữ lập trình được phát triển bởi Bjarne Stroustrup vào năm 1979 tại Bell Labs.
 Tính phổ biến: C++ là một trong những ngôn ngữ lập trình phổ biến nhất trên thế giới.
 Tính thực thi nhanh: Nếu bạn đã sành sỏi về C++ thì bạn có thể lập trình
rất nhanh. Một trong những mục tiêu của C++ chính là khả năng thực thi. Và
nếu bạn cần thêm các tính năng cho chương trình, C++ cho phép bạn sử
dụng ngôn ngữ Assembly (Hợp ngữ) – Ngôn ngữ lập trình bậc thấp nhất
dùng để giao tiếp trực tiếp với phần cứng của máy tính.
 Thư viện đầy đủ: Có rất nhiều tài nguyên sử dụng cho người lập trình bằng
C++, bao gồm cả đồ hoạ API, 2D, 3D, vật lý các thiết bị âm thanh hỗ trợ
giúp cho lập trình viên dễ dàng thực thi.
 Đa mô hình: C++ cũng cho phép bạn lập trình theo cấu trúc tuyến tính,
hướng chức năng, hướng đối tượng đa dạng tuỳ theo yêu cầu của người lập trình.  Thư viện:
 Sử dụng thư viện trong c++
 Sử dụng MySQL: hệ thống quản trị cơ sở dữ liệu mã nguồn mở (Relational
Database Management System, viết tắt là RDBMS) hoạt động theo mô
hình client-server. RDBMS là một phần mềm hay dịch vụ dùng để tạo và
quản lý các cơ sở dữ liệu (Database) theo hình thức quản lý các mối liên hệ giữa chúng.
2. Tổ chức chương trình và đóng gói
 Tổ chức chương trình:
 Viết code chương trình trên C++ theo từng đoạn code, mỗi đoạn code xử lý 1 chức năng.
 Kết nối chương trình với MySQL để xử lý dữ liệu và lưu trữ  Đóng gói:
 Các phần code và liên quan đến chương trình đóng gói ở file Nhom_11_Code.zip
 Bài báo cáo: Nhom_11_Report.docx
 Video chạy thực nghiệm: Nhom_11_Demo.mp4 11 IV.
Kết quả thực nghiệm 1. Dữ liệu
 Dữ liệu được lưu trữ tại cơ sở dữ liệu là sinhvien với 2 bảng là sinhvien_1 và hocphan. - Bảng sinhvien_1: - Bảng hocphan:
2. Các kết quả thực nghiệm
 Các chức năng trong chương trình:
 Kết quả thực nghiệm
- Tính năng 1: Thêm sinh viên
Ví dụ: Thêm một sinh viên có MSSV = 2021007 + Trước: 12 + Sau: 13
- Tính năng 2: Xóa sinh viên
Ví dụ: Xóa sinh viên có MSSV=2021007 + Trước: 14 + Sau:
- Chức năng 3: Thêm học phần
Ví dụ: Thêm học phần GT1 cho sinh viên có MSSV = 2021007 + Trước: 15 + Sau:
- Chức năng 4: Xóa học phần
Ví dụ: Xóa học phần GT1 cho sinh viên có MSSV = 2021007 + Trước: + Sau:
- Chức năng 5 : Tăng số buổi vắng thuộc học phần CTDL của sinh viên có MSSV = 2021006 lên 1 buổi + Trước: 16 + Sau:
- Chức năng 6: Tìm kiếm sinh viên
Ví dụ: Tìm kiếm sinh viên có MSSV = 2021005
- Chức năng 7: In ra số sinh viên trong danh sách
- Chức năng 8: In ra danh sách 17
- Chức năng 9: In ra danh sách sinh viên theo thứ tự tăng dần của điểm trung bình giữa kì V. Kết luận
1. Đánh giá về mức độ hoàn thành  Mặt ưu điểm
 Project của nhóm đã hoàn thành đúng với mục tiêu ban đầu đề
ra và có thể hoạt động với lượng data tương đối lớn
 Các thành viên trong nhóm đã biết ứng dụng kiến thức để bắt tay vào làm 1 dự án nhỏ
 Đã ứng dụng được kiến thức đã học của môn học, kết hợp với
kiến thức tự tìm hiểu để làm sản phẩm
 Mặt khác, sản phẩm này của chúng em vẫn cần phát triển thêm một số phương diện như:
 Về mặt trình bày code: Cần rút ngắn, tối giản
 Về độ phức tạp thuật toán: Cần tối ưu thêm thời gian chạy để có
thể xử lý được lượng data vô cùng lớn 18
 Về các chức năng khác của sản phẩm: Cần nghiên cứu nhiều
kiến thức để tạo ra nhiều chức năng hữu ích hơn nữa
 Về mặt hình thức sản phẩm: Cần nghiên cứu kiến thức để hình
thức sản phẩm trở thành 1 web hay app đặc thù 2. Bài học rút ra
 Môn học Cấu trúc dữ liệu và giải thuật vô cùng quan trong, là phần
kiến thức không thể thiếu, gắn bó mãi mãi với sinh viên ngành Điện tử viễn thông chúng em
 Học đi đôi với hành, chúng ta cần sử dụng kiến thức đã học để áp
dụng vào 1 việc nào đó để giúp ta nắm vững kiến thức và tìm ra được những điều mới mẻ
 Khi bắt đầu làm một bài tập lớn, sản phẩm, dự án bất kỳ thì chúng ta
đều cần lên kế hoạch cụ thể
 Chọn đề tài vừa trong khả năng của bản thân, vừa có sự thử thách nhất định
 Sau khi hoàn thành sản phẩm, cần phải suy nghĩ thêm để phát triển
sản phẩm, khắc phục những hạn chế của sản phẩm
 Kỹ năng làm việc nhóm rất quan trọng, cần phải phân chia công việc
rõ ràng và giúp đỡ nhau trong quá trình làm việc, hiểu được điểm mạnh yếu của nhau
3. Khó khăn khi học tập môn học
 Để học tốt môn Cấu trúc dữ liệu và giải thuật, chúng em cần phải nắm
vững kiến thức môn Kỹ thuật lập trình C/C++
 Cần hiểu bản chất khi học vì thường xuyên phải code giấy, không
được phụ thuộc vào máy tính
 Lượng kiến thức lớn, cần phải đầu tư nhiều thời gian học và thực hành
để nắm được kiến thức
 Cần phải nắm vững từng phần kiến thức mới ứng dụng được vài một bài tập lớn 19
 Những khó khăn trên chỉ là những thử thách của môn học, nếu làm tốt
thì kiến thức đã học ở môn Cấu trúc dữ liệu và giải thuật sẽ giúp ích
rất nhiều cho bản thân sinh viên chúng em.
VI. Tài liệu tham khảo:
 Tài liệu trong teams lớp
 Tài liệu về MySQL: https://viblo.asia/p/mysql-tu-don-gian-den- phuc-tap-L4x5xamOKBM VII. Lời cảm ơn
 Cấu trúc dữ liệu và giải thuật là môn học quan trọng đối với sinh viên những
ngành liên quan CNTT nói chung và ngành Điện tử-Viễn thông nói riêng.
Chúng em đã hiểu rằng ngôn ngữ lập trình có thể thay đổi nhưng cốt lõi là
cấu trúc giữ liệu và giải thuật sẽ giúp chúng em học được ngôn ngữ mới nhanh chóng.
 Chúng em xin chân thành cảm ơn sự chỉ dạy nhiệt tình và những ví dụ minh
họa của cô giúp chúng em học tập. Cảm ơn cô vì đã giao một bài tập lớn để
chúng em được có cơ hội thử thách bản than vào một project không chỉ đơn
giản là code mà còn là tinh thần làm việc, tìm hiểu những thứ mới mẻ
 Cuối cùng, sản phẩm của chúng em vẫn còn nhiều thiếu sót do thiếu nhiều
kinh nghiệm cũng như kĩ năng, mong cô nhận xét, góp ý để chúng em hoàn thiện hơn. 20