lOMoAR cPSD| 27879799
ĐẠ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: Giảng viên:
Downloaded by VietJack TV Official (vietjackvideos@gmail.com) lOMoAR cPSD| 27879799
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 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 1 lOMoAR cPSD| 27879799
• 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 Họ và tên MSSV Nhiệm vụ Mức độ hoàn thành Trần Đình Vương 20214154 Tìm hiểu đề tài Đã hoàn thành Lên ý tưởng
Triển khai và cài đặt chương trình- Coder phụ Phát triển sản phẩm
Làm báo cáo phần I,II,II 2 lOMoAR cPSD| 27879799 Cao Danh Khang 20213967 Tìm hiểu đề tài Đã hoàn thành Lên ý tưởng
Triển khai và cài đặt chương trình-Coder chí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 Ngô Thái Bình 20213820 Tìm hiểu đề tài Đã hoàn thành Tìm hiểu CSDL LinkedList Tìm hiểu thư viện Theo dõi tiến trình Làm báo cáo phần IV,V Cao Việt Bình 20213818 Tìm hiểu đề tài Đã hoàn thành Tìm hiểu giải thuật Binary Search và QuickSort 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 •
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 3 lOMoAR cPSD| 27879799
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 hiện đơn giản bằng một quá trình duyệt 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ử x khỏi một linked list cho trước. 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 •
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: 4 lOMoAR cPSD| 27879799 • Xóa sinh viên: • Thêm sinh viên: 5 lOMoAR cPSD| 27879799 •
Thêm học phần Xóa học phần Điểm danh: 6 lOMoAR cPSD| 27879799 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.
+ 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. 7 lOMoAR cPSD| 27879799
+ 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)
• Áp dụng giải thuật Binary Search trong chương trình: 8 lOMoAR cPSD| 27879799
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ầntử
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.
• 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. 9 lOMoAR cPSD| 27879799
- Áp dụng QuickSort trong chương trình: III.
Triển khai cài đặt
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++ 10 lOMoAR cPSD| 27879799
• 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 IV.
Kết quả thực nghiệm 11 lOMoAR cPSD| 27879799 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 lOMoAR cPSD| 27879799 + Sau:
- Tính năng 2: Xóa sinh viên 13 lOMoAR cPSD| 27879799
Ví dụ: Xóa sinh viên có MSSV=2021007 + Trước: + Sau: 14 lOMoAR cPSD| 27879799
- 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: + Sau: 15 lOMoAR cPSD| 27879799
- 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: + 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 16 lOMoAR cPSD| 27879799
- 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
- Chức năng 9: In ra danh sách sinh viên theo thứ tự tăng dần của điểm trungbình giữa kì 17 lOMoAR cPSD| 27879799 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
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ù 18 lOMoAR cPSD| 27879799 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
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: 19