Báo cáo đồ án giữa kì lần 2 | Môn Cấu trúc dữ liệu và thuật toán - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58583460
Báo cáo đồ án giữa kì lần 2 --- Bài 1:
Báo cáo Chương trình Quản lý Sách
1. Khởi tạo cấu trúc dữ liệu và hàm khởi tạo
- Cấu trúc dữ liệu `sach`: Định nghĩa các thuộc tính `name`,
`code`, và `rate` để lưu trữ thông tin của sách.
- Cấu trúc dữ liệu `LIST`: Sử dụng mảng tĩnh `arr` với kích
thước cố định `Length` để lưu trữ các sách, và biến `size` để
theo dõi số lượng sách hiện có.
- Hàm `Init`: Đặt `size` của danh sách là 0, khởi tạo danh sách trống.
2. Các hàm kiểm tra trạng thái danh sách
- Hàm `Empty`: Kiểm tra xem danh sách có rỗng không.
- Hàm `Full`: Kiểm tra xem danh sách có đầy không.
3. Các thao tác với danh sách
- Hàm `Input`:Nhập thông tin cho `size` sách trong danh sách từ người dùng.
- Hàm `addLast`:Thêm sách vào cuối danh sách nếu danh sách chưa đầy. lOMoAR cPSD| 58583460
- Hàm `addFirst`: Thêm sách vào đầu danh sách nếu danh sách chưa đầy.
- Hàm `desFirst`: Xóa sách đầu tiên của danh sách nếu danh sách không rỗng.
- Hàm `desLast`: Xóa sách cuối cùng của danh sách nếu danh sáchkhông rỗng.
4. Các thao tác tìm kiếm và hiển thị
- Hàm `findname`: Tìm kiếm sách theo tên trong danh sách.
Trả về`true` nếu tìm thấy sách, ngược lại trả về `false`.
- Hàm `display`: Hiển thị thông tin toàn bộ sách trong danh sách.
5. Các hàm sắp xếp
- Hàm `selectionSort`:Sắp xếp danh sách theo `rate` của sách
bằngthuật toán Selection Sort.
- Hàm `quickSort`: Sắp xếp danh sách theo `rate` của sách
bằng thuật toán Quick Sort. Sử dụng hàm `partition` để xác định chỉ số pivot.
6. Các hàm thao tác đặc biệt
- Hàm `reverse`: Đảo ngược thứ tự các sách trong danh sách.
- Hàm `deleteAllByrate`: Xóa toàn bộ sách có `rate` bằng với giá trị đầu vào. lOMoAR cPSD| 58583460
- Hàm `sumValues`: Tính tổng các `rate` của tất cả sách trong danh sách.
7. Hàm `main` và menu điều khiển
- Menu điều khiển: Hiển thị danh sách các chức năng, cho
phép người dùng chọn và thực hiện các thao tác như thêm,
xóa, tìm kiếm, sắp xếp, hiển thị, đảo ngược, kiểm tra trạng thái danh sách.
- Các tùy chọn từ 1 đến 13: Bao gồm các thao tác đã định nghĩa trong các hàm trên. Bài 2:
Báo cáo chương trình quản lý sách danh sách liên kết đơn
1. Cấu trúc Dữ liệu:
- `sach`: Cấu trúc này định nghĩa thông tin của một cuốn sách
bao gồm tên sách (`name`), mã sách (`code`), và mức độ hài lòng (`rate`).
- `Node`: Cấu trúc này định nghĩa một nút trong danh sách liên
kết, bao gồm dữ liệu sách và con trỏ đến nút tiếp theo (`next`).
- `LIST`: Cấu trúc này định nghĩa danh sách liên kết, bao gồm
contrỏ đến đầu danh sách (`head`) và kích thước của danh sách (`size`).
2. Khởi tạo Danh sách:
- `Init(LIST &lst)`: Hàm khởi tạo danh sách liên kết, thiết lập
`head` là `nullptr` và `size` là 0. lOMoAR cPSD| 58583460 3. Tạo Nút Mới:
- createNode(const sach &value)`: Hàm tạo và trả về một nút
mới chứa thông tin sách.
4. Kiểm tra Tính Rỗng:
- `Empty(const LIST &lst)`: Hàm kiểm tra xem danh sách có rỗng hay không. 5. Thêm Sách:
- `addFirst(LIST &lst, sach value)`: Thêm một cuốn sách mới vào đầu danh sách.
- `addLast(LIST &lst, sach value)`: Thêm một cuốn sách mới vào cuối danh sách. 6. Xóa Sách:
- `desFirst(LIST &lst)`: Xóa cuốn sách đầu tiên trong danh sách.
- desLast(LIST &lst)`: Xóa cuốn sách cuối cùng trong danh sách. 7. Tìm Kiếm Sách:
- `findname(const LIST &lst, const string &name)`: Kiểm tra
xem một cuốn sách với tên nhất định có trong danh sách hay không. lOMoAR cPSD| 58583460
8. Hiển Thị Danh Sách:
- `display(const LIST &lst)`: Hiển thị tất cả thông tin sách trong danh sách. 9. Sắp Xếp Sách:
- `selectionSort(LIST &lst)`: Sắp xếp danh sách sách theo mức
độ hài lòng bằng thuật toán sắp xếp chọn (Selection Sort).
- `quickSort(LIST &lst)`: Sắp xếp danh sách sách theo mức độ
hàilòng bằng thuật toán QuickSort.
10. Đảo Ngược Danh Sách:
- `reverse(LIST &lst)`: Đảo ngược thứ tự các cuốn sách trong danh sách.
11. Xóa Tất Cả Sách Theo Mức Độ Hài Lòng:
- `deleteAllByrate(LIST &lst, int rate)`: Xóa tất cả cuốn sách
có mức độ hài lòng nhất định khỏi danh sách.
12. Tính Tổng Mức Độ Hài Lòng:
- `sumValues(const LIST &lst)`: Tính tổng mức độ hài lòng
của tất cả cuốn sách trong danh sách.
13. Giao Diện Người Dùng:
- `main()`: Phần này cung cấp giao diện người dùng cho phép
người dùng thực hiện các thao tác như thêm, xóa, tìm kiếm, lOMoAR cPSD| 58583460
sắp xếp, và hiển thị sách trong danh sách thông qua menu tương tác. Kết luận Bài 3.1: ---
Báo cáo Chương trình Quản lý Sách Sử Dụng Danh Sách Liên Kết Đôi
1. Khởi tạo cấu trúc dữ liệu và hàm khởi tạo
- Cấu trúc dữ liệu `sach`: Định nghĩa các thuộc tính `name`,
`code`, và `rate` để lưu trữ thông tin sách.
- Cấu trúc dữ liệu `Node`: Chứa thông tin sách và con trỏ tới
nút kế tiếp (`next`) và nút trước đó (`prev`) trong danh sách liên kết đôi.
- Cấu trúc dữ liệu `DLIST`: Bao gồm con trỏ tới nút đầu
(`head`), nút cuối (`tail`), và biến `size` để theo dõi số lượng sách hiện có.
- Hàm `Init`: Khởi tạo danh sách liên kết đôi với `head` và
`tail` bằng `nullptr` và kích thước là 0.
2. Các hàm kiểm tra trạng thái danh sách
- Hàm `Empty`: Kiểm tra xem danh sách có rỗng không. lOMoAR cPSD| 58583460
3. Các thao tác với danh sách
- Hàm `addFirst`: Thêm sách vào đầu danh sách. Nếu danh
sách rỗng, sách sẽ trở thành cả đầu và cuối.
- Hàm `addLast`: Thêm sách vào cuối danh sách. Nếu danh
sách rỗng, sách sẽ trở thành cả đầu và cuối.
- Hàm `desFirst`: Xóa sách đầu tiên của danh sách. Nếu danh
sách chỉ có một sách, cả `head` và `tail` sẽ trở thành `nullptr`.
- Hàm `desLast`: Xóa sách cuối cùng của danh sách. Tương tự
nhưhàm `desFirst`, nếu danh sách chỉ có một sách, cả `head`
và `tail` sẽ trở thành `nullptr`.
4. Các thao tác tìm kiếm và hiển thị
- Hàm `findname`: Tìm kiếm sách theo tên trong danh sách.
Trả về`true` nếu tìm thấy sách, ngược lại trả về `false`.
- Hàm `displayForward`: Hiển thị thông tin toàn bộ sách từ đầu đến cuối danh sách.
- Hàm `displayBackward`: Hiển thị thông tin toàn bộ sách từ
cuối đến đầu danh sách.
5. Các hàm sắp xếp
- Hàm `selectionSort`:Sắp xếp danh sách theo `rate` của sách
bằngthuật toán Selection Sort.
6. Các hàm thao tác đặc biệt lOMoAR cPSD| 58583460
- Hàm `reverse`: Đảo ngược thứ tự các nút trong danh sách.
- Hàm `deleteAllByrate`: Xóa toàn bộ sách có `rate` bằng với giá trị đầu vào.
- Hàm `sumValues`: Tính tổng các `rate` của tất cả sách trong danh sách. 7. Hàm QuickSort
- Hàm `partition`: Định nghĩa phân vùng cho thuật toán
QuickSort. Phân vùng danh sách dựa trên giá trị `rate`.
- Hàm `quickSortRecur`: Hàm đệ quy để thực hiện QuickSort trên danh sách.
- Hàm `quickSort`:Hàm khởi động QuickSort cho danh sách.
8. Hàm `main` và menu điều khiển
- Menu điều khiển:Hiển thị danh sách các chức năng, cho phép
người dùng chọn và thực hiện các thao tác như thêm, xóa, tìm
kiếm, sắp xếp, hiển thị, đảo ngược, kiểm tra trạng thái danh sách.
- Các tùy chọn từ 1 đến 13: Bao gồm các thao tác đã định nghĩa trong các hàm trên. .