Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Phần mềm mô phỏng các thuật toán trong môn học cấu trúc dữ liệu
Nội dung xem thử
Mô tả chi tiết
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC MỞ TP. HỒ CHÍ MINH
BÁO CÁO TỔNG KẾT
ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ CẤP TRƯỜNG
PHẦN MỀM MÔ PHỎNG CÁC THUẬT TOÁN
TRONG MÔN HỌC CẤU TRÚC DỮ LIỆU
Mã số: T2015.13.192
Chủ nhiệm đề tài: ThS. Nguyễn Thị Mai Trang
TP. HCM, <08>/<2016>
1
MỤC LỤC
THÔNG TIN KẾT QUẢ NGHIÊN CỨU..................................................................................6
MỞ ĐẦU .......................................................................................................................10
CHƯƠNG 1. TỔNG QUAN............................................................................................. 14
I. Đặt vấn đề ............................................................................................................... 14
II. Mô phỏng máy tính và ứng dụng trong giảng dạy: ................................................ 14
1. Mô phỏng máy tính: ................................................................................................ 14
2. Vì sao cần sử dụng phương pháp mô phỏng trong dạy học .................................... 15
3. Phương pháp dạy học với mô phỏng:[2]
................................................................... 16
4. Ứng dụng mô phỏng trong giảng dạy môn “Cấu trúc dữ liệu”. .............................. 18
CHƯƠNG 2. CƠ SỞ LÝ THUYẾT ................................................................................. 23
I. Mục tiêu thiết kế phần mềm ................................................................................... 23
II. Các thuật toán được áp dụng trong đề tài............................................................... 23
1. Thuật toán sắp xếp:.................................................................................................. 23
2. Các thuật toán tìm kiếm........................................................................................... 30
3. Các thao tác trên danh sách đặc............................................................................... 32
4. Các thao tác trên danh sách liên kết: ....................................................................... 34
5. Ngăn xếp(Stack): ..................................................................................................... 39
6. Hàng đợi (Queue): ................................................................................................... 39
7. Cây nhị phân............................................................................................................ 40
8. Các thao tác trên bảng băm ..................................................................................... 47
9. B-cây........................................................................................................................ 53
CHƯƠNG 3. PHẦN MỀM SIMULATION PROGRAM ................................................ 61
I. Giới thiệu ................................................................................................................ 61
II. Yêu cầu của phần mềm........................................................................................... 61
III. Thiết kế phần mềm ................................................................................................. 62
1. Yêu cầu cấu hình hệ thống ...................................................................................... 62
2. Yêu cầu sử dụng phần mềm .................................................................................... 62
3. Tổ chức lưu trữ dữ liệu............................................................................................ 63
IV. Các chức năng đã cài đặt ........................................................................................ 65
1. Thuật toán tìm kiếm, sắp xếp: ................................................................................. 65
2
2. Các thuật toán tìm kiếm........................................................................................... 65
3. Các thuật toán thao tác trên danh sách đặc.............................................................. 65
4. Các thuật toán thao tác trên danh sách liên kết ....................................................... 66
5. Các thuật toán thao tác trên ngăn xếp (Stack)......................................................... 66
6. Các thuật toán thao tác trên hàng đợi (Queue)........................................................ 66
7. Các thuật toán thao tác trên cây nhị phân................................................................ 66
8. Bảng băm................................................................................................................. 66
9. B cây........................................................................................................................ 66
V. Giao diện phần mềm............................................................................................... 66
1. Giao diện chính:....................................................................................................... 66
2. Giao diện một số thuật toán trong chương trình...................................................... 67
3. Hộp thoại tùy chọn .................................................................................................. 73
4. Hướng dẫn sử dụng chương trình............................................................................ 74
CHƯƠNG 4. KẾT LUẬN – KIẾN NGHỊ........................................................................ 75
3
DANH MỤC CÁC HÌNH
Hình I.1. Hiệu quả của mô phỏng.............................................................................................17
Hình I.2. Demo thuật toán sắp xếp Bubble-Sort[6]
...................................................................21
Hình II.1. Thuật toán SelectionSort [6]
......................................................................................24
Hình II.2. Thuật toán sắp xếp chèn trực tiếp (Straight Insertion Sort) [6]
.................................25
Hình II.3. Thuật toán sắp xếp nổi bọt (Bubble sort) [6]
.............................................................26
Hình II.4. Thuật toán sắp xếp nổi bọt (Bubble sort) [6]
.............................................................27
Hình II.5. Thuật toán sắp xếp Merge Sort [3]
............................................................................30
Hình II.6. Thuật toán tìm kiếm tuần tự
[6]
.................................................................................31
Hình II.7. Thuật toán tìm kiếm nhị phân [6]
..............................................................................32
Hình II.8. Tìm kiếm phần tử trong danh sách [6]
......................................................................33
Hình II.9. Chèn phần tử vào danh sách [6]
................................................................................33
Hình II.10. Xóa phần tử trong danh sách theo vị trí [6]
.............................................................34
Hình II.11. Danh sách liên kết đơn [3]
.......................................................................................34
Hình II.12. Hình ảnh một node trong danh sách liên kết đơn [3]
..............................................35
Hình II.13. Thêm một node vào danh sách liên kết đơn [3]
......................................................35
Hình II.14. Thêm một node vào đầu danh sách liên kết đơn [3]
...............................................36
Hình II.15. Xóa một node trong danh sách liên kết đơn [3]
......................................................36
Hình II.16. Xóa node đầu trong danh sách liên kết đơn [3]
.......................................................36
Hình II.17. Danh sách liên kết kép [63
.......................................................................................37
Hình II.18. Danh sách liên kết vòng [3]
.....................................................................................37
Hình II.19. Stack.......................................................................................................................39
Hình II.20. Queue .....................................................................................................................39
Hình II.22. Cấu trúc một nút trong cây nhị phân [3]
.................................................................41
Hình II.23. Cây nhị phân tìm kiếm [5]
.......................................................................................43
Hình II.24. Thứ tự thêm các nút vào cây nhị phân...................................................................44
Hình II.25. Cây cân bằng..........................................................................................................44
Hình II.26. Thêm nút 50 vào cây cân bằng làm cây bị lệch.....................................................45
Hình II.27. Cây cân bằng sau khi thực hiện phép quay............................................................46
Hình II.28. Cấu trúc bảng băm nối kết trực tiếp.......................................................................47
Hình II.29. Khởi tạo bảng băm rỗng ........................................................................................48
4
Hình II.30. Thêm một phần tử vào bảng băm nối kết trực tiếp................................................48
Hình II.31. Tìm phần tử trong bảng băm nối kết trực tiếp .......................................................49
Hình II.32. Cấu trúc bảng băm nối kết hợp nhất......................................................................50
Hình II.33. Khởi tạo bảng băm rỗng ........................................................................................51
Hình II.34. Tìm một phần tử trong bảng băm nối kết hợp nhất ...............................................51
Hình II.35. Thêm phần tử vào bảng băm nối kết hợp nhất.......................................................52
Hình II.36. B-cây cấp 2 [6]
........................................................................................................53
Hình II.37. Khai báo cấu trúc B cây [4]
.....................................................................................54
Hình II.38. Hàm NodeSearch [4]
...............................................................................................54
Hình II.39. Hàm Search [4]
........................................................................................................55
Hình II.40. Duyệt B cây [4]
.......................................................................................................56
Hình II.41. Hàm Insert - Thêm khóa vào B-cây [4]
...................................................................57
Hình II.42. Hàm Split – Tách node đầy trong B cây [4]
............................................................58
Hình II.43. Hàm InsNode – Chèn khóa vào B cây tại vị trí đã biết [4]
.....................................59
Hình II.44. Hàm Copy – Sao chép khóa và nhánh con trong B cây [4]
....................................60
Hình III.1. Thư mục lưu trữ dữ liệu..........................................................................................63
Hình III.2. Thuật toán Selection Sort, ngôn ngữ C#, có thể sửa thành các ngôn ngữ khác .....64
Hình III.3. Thuật toán Selection Sort ngôn ngữ C, C++ .........................................................65
Hình III.4. Giao diện phần mềm...............................................................................................66
Hình III.5. Thuật toán sắp xếp Selection Sort ..........................................................................67
Hình III.6. Thuật toán sắp xếp Insertion Sort...........................................................................67
Hình III.7. Thuật toán sắp xếp Interchange Sort ......................................................................68
Hình III.8. Thuật toán sắp xếp Merge Sort...............................................................................68
Hình III.9. Thuật toán tìm kiếm nhị phân.................................................................................69
Hình III.10 Bảng băm nối kết trực tiếp ....................................................................................69
Hình III.11. Bảng băm nối kết hợp nhất...................................................................................70
Hình III.12. Stack cài đặt bằng danh sách đặc .........................................................................70
Hình III.13. Stack cài đặt bằng danh sách liên kết...................................................................71
Hình III.14. Hàng đợi cài đặt bằng danh sách đặc ...................................................................71
Hình III.15. Hàng đợi cài đặt bằng danh sách liên kết.............................................................72
Hình III.16. Thêm một node vào cây cân bằng (đang đánh dấu các nút cần cân bằng).........72
5
Hình III.17. Cây sau khi cân bằng............................................................................................73
Hình III.18. B cây.....................................................................................................................73
Hình III.19. Hộp thoại Options.................................................................................................74
Hình III.20. Hướng dẫn sử dụng ..............................................................................................74