Bài Tập Lớn: Ứng Dụng Danh Sách Liên Kết Vòng Đơn | Môn Cấu trúc dữ liệu và giải thuật - Đại học Công Nghệ Đông Á

lOMoAR cPSD| 60729183
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐÔNG Á BÀI TẬP LỚN
HỌC PHẦN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
ĐỀ TÀI 5: ỨNG DỤNG DANH SÁCH LIÊN KẾT VÒNG ĐƠN VÀO
QUẢN LÝ DANH SÁCH SỐ NGUYÊN
Sinh viên thực hiện Khóa Lớp Mã sinh viên Trịnh Thế Sơn K13 20222635 DCCNTT13.10.1 4 Bắc Ninh, năm 2023 lOMoAR cPSD| 60729183
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐÔNG Á BÀI TẬP LỚN
HỌC PHẦN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Nhóm: 5
ĐỀ TÀI 5: ỨNG DỤNG DANH SÁCH LIÊN KẾT VÒNG ĐƠN VÀO
QUẢN LÝ DANH SÁCH SỐ NGUYÊN Điểm Điểm STT
Sinh viên thực hiện Mã sinh viên bằng số bằng chữ 1 Trịnh Thế Sơn 20222635 CÁN BỘ CHẤM 1 CÁN BỘ CHẤM 2
(Ký và ghi rõ họ tên)
(Ký và ghi rõ họ tên) lOMoAR cPSD| 60729183 MỤC LỤC
DANH MỤC CÁC TỪ VIẾT TẮT .................................................................................. 4
DANH MỤC BẢNG BIỂU VÀ SƠ ĐỒ ........................................................................... 5
Chương 1. Tổng quan về đề tài ........................................................................................ 6
1.1 Giới thiệu .................................................................................................................. 6
1.2 Phân công công việc .................................................................................................. 7
Chương 2. Thuật toán ....................................................................................................... 8
2.1 Mô tả bài toán ............................................................................................................ 8
2.2 Lưu đồ thuật toán tổng quát ...................................................................................... 9
2.3 Các bước của thuật toán tổng quát ............................................................................ 9
2.4 Thiết kế giao diện .................................................................................................... 10
2.5 Thuật toán, các bước và lưu đồ chi tiết ................................................................... 12
Chương 3. Cài đặt ........................................................................................................... 30
3.1 Code toàn bài ........................................................................................................... 30
3.2 Bộ dữ liệu mẫu ........................................................................................................ 44
3.3 Kết quả .................................................................................................................... 45
Chương 4. Hướng phát triển và tài liệu tham khảo.....................................................52
4.1 Hướng phát triển....................................................................................................52
4.2 Tài liệu tham khảo..................................................................................................52 lOMoAR cPSD| 60729183
DANH MỤC CÁC TỪ VIẾT TẮT STT Chữ viết tắt Giải thích 1 Đ Đúng 2 S Sai lOMoAR cPSD| 60729183
DANH MỤC BẢNG BIỂU VÀ SƠ ĐỒ Số hiệu Tên Trang 1.1
Danh sách liên kết vòng đơn 6 1.2
Bảng phân công công việc 8 2.1 10
Lưu đồ tổng quát thuật toán ứng dụng danh sách liên kết vòng đơn
vào quản lý danh sách số nguyên 2.2
Lưu đồ thuật toán khởi tạo danh sách số nguyên 14 2.3 18
Lưu đồ thuật toán kiểm tra nếu phần tử thứ 5 là số nguyên tố thì thay bằng 10 2.4 22
Lưu đồ thuật toán tính trung bình nhân các số chẵn, dương, chia hết cho 5 2.5
Lưu đồ thuật toán sắp xếp danh sách theo thứ tự tăng dần 25 2.6
Lưu đồ thuật toán kiểm tra cấp số nhân 3 phần tử liên tiếp trong dãy 29 3 Bảng dữ liệu mẫu 31 lOMoAR cPSD| 60729183
Chương 1. Tổng quan về đề tài 1.1 Giới thiệu
Danh sách liên kết vòng đơn – Singly circular linked list là một danh sách liên kết
(linked list) trong đó tất cả các nodes được kết nối với nhau để tạo thành một vòng
tròn. Sẽ không có con trỏ NULL ở cuối danh sách liên kết vòng
Hình 1.1 Danh sách liên kết vòng đơn Ưu điểm:
1. Bất kỳ node nào cũng có thể là điểm bắt đầu (starting point). Chúng ta có thể
duyệttoàn bộ danh sách bằng cách bắt đầu tại bất kỳ điểm nào, tùy ý. Chúng ta chỉ
cần dừng lại khi node đầu tiên được duyệt, lại được duyệt tới một lần nữa.
2. Danh sách liên kết vòng rất hữu dụng trong việc triển khai queue – hàng đợi. Khi
sử dụng danh sách liên kết vòng để cài đặt queue, chúng ta sẽ không cần phải duy trì
hai điểm front (điểm đầu) và rear (điểm cuối) của queue. Chúng ta chỉ cần duy trì
một con trỏ dành cho note mới nhất được chèn vào (nằm ở cuối danh sách), lấy node
cuối cùng này làm mốc, ta có thể dễ dàng truy cập tới các nodes nằm ở phần đầu danh sách.
3. Danh sách liên kết dạng vòng còn hữu dụng trong các ứng dụng phần mềm, để lặp
đi lặp lại danh sách. Ví dụ, khi nhiều ứng dụng đang chạy trên một Máy tính, thông
thường hệ điều hành sẽ đặt các ứng dụng đang chạy vào một danh sách, và sau đó
duyệt qua chúng, mỗi lần duyệt tới ứng dụng nào thì lại cho ứng dụng đó một khoảng
thời gian để thực thi, và sau đó lại đưa chúng về trạng thái đợi trong khi CPU được
cấp cho một ứng dụng khác. Vì thế, sẽ rất lý tưởng khi hệ điều hành sử dụng một
danh sách liên kết vòng để khi duyệt đến cuối danh sách, nó có thể quay vòng lên
phía trước danh sách/phần đầu danh sách. Nhược điểm:
Có thể không biết khi nào đã duyệt qua toàn bộ phần tử cua danh sách. Điều này dẫn
đến qua trình duyệt vô hạn không điểm dừng. lOMoAR cPSD| 60729183 Thao tác cơ bản: 1. Tổ chức
2. Khởi tạo danh sách rỗng. 3. Tạo nút
4. Chèn vào đầu danh sách
5. Chèn vào cuối danh sách
6. Tìm kiếm paahnf tử trong danh sách\ 7. Chèn nút
8. Hủy phàn tử trong danh sách 9. Hủy danh sách Úng dụng:
Được sử dụng trong các ứng dụng trong đó toàn bộ danh sách được truy cập từng cái
một trong vòng lặp. Ứng dụng vào quản lý danh sách số nguyên.
1.2 Phân công công việc
Bảng 1.2 Bảng phân công công việc STT Tên đầu việc Công việc Thành viên Đánh giá Kết luận
chia đến nhỏ nhất 1 Viết chương Viết chương trình tạo Menu dễ sử dụng, trình ứng dụng Menu dễ hiểu danh sách liên Chương trình chạy kết vòng đơn nhanh, ổn định và đưa vào quản lý ra kết quả chính xác danh sách số giúp người dùng quản Viết chương trình khởi Dễ dàng khởi tạo nguyên lý danh sách số tạo danh sách danh sách theo ý
nguyên hiệu quả và tối muốn ưu Kiểm tra và thay
Kiểm tra vị trí thứ 5 có thế nhanh, chính phải số nguyên tố xác không, nếu đúng thay
thế phần tử bằng số 10 Tính toán nhanh Tính trung bình nhân tối ưu các số chắn dương chia hết cho 5 (không kể số 0) Trịnh Thế Sơn lOMoAR cPSD| 60729183 Sắp xếp danh sách theo Xắp xếp nhanh và thứ tự tăng dần chính xác Kiểm tra đưa ra Kiểm tra xem trong kết quả nhanh danh sách có 3 phần tử chính xác theo
liên tiếp là cấp số nhân yêu cầu hay không?, in ra 3 số đó 2 Làm báo cáo Chương 1 tổng quan về Hiểu về đề tài và Bản báo cáo Word Word đề tài phân công việc giúp người xem hiểu Chương 2 thuật toán Trịnh Thế Sơn
rõ về đề tài, cách phân Nắm bắt rõ lưu công việc và nắm bắt
dồ, các bộ mẫu và được thuật toán giao diện Chương 3 cài đặt Hiểu về cách cài đặt thuật toán và kết quả đạt được 3 Làm Slide Trịnh Thế Sơn Slide trình chiếu trước
Tóm gọn nội dung Slide ngắn gọn bao lớp đề tài, đầy đủ ý quát đề tài, dễ hiểu
Chương 2. Thuật toán
2.1 Mô tả bài toán
Chương trình được cài đặt bằng ngôn ngữ C ứng dụng danh sách liên kết vòng đơn
giúp người dùng quản lý danh sách số nguyên và thực hiện các thao tác yêu cầu một cách
thuận tiện, nhanh chóng và có độ chính xác cao, người dùng sẽ tiết kiệm được nhiều thời
gian mà vẫn đạt được kết quả mong muốn chính xác. Người dùng sẽ nhập một danh sách
các số nguyên, chương sẽ trình tạo một Menu thực hiện các công việc sau:
1. Khởi tạo danh sách, quá trình nhập sẽ dừng lại khi nhập dấu “#”.
2. Kiểm tra xem ở vị trí thứ 5 có phải là số nguyên tố hay không? Nếu đúng hãy thay thế
phần tử này bằng số 10.
3. Tính trung bình nhân các số chẵn, dương, chia hết cho 5 (không kể số 0).
4. Sắp xếp danh sách theo thứ tự tăng dần. lOMoAR cPSD| 60729183
5. Kiểm tra xem trong danh sách có 3 phần tử liên tiếp là cấp số nhân hay không?, in ra 3 số đó.
Khi đó người dùng sẽ nhập lựa chọn của mình mong muốn để chương trình thực hiện yêu cầu của mình.
2.2 Lưu đồ thuật toán tổng quát
Hình 2.1 Lưu đồ thuật toán ứng dụng danh sách liên kết vòng đơn vào quản lý danh sách số nguyên
2.3 Các bước của thuật toán tổng quát 1. Bắt đầu
In ra Menu các chức năng cho người dùng.
Đọc lựa chọn từ người dùng.
2. Nếu lựa chọn là 1: Khởi tạo danh sách:
Nhập khởi tạo danh sách số nguyên và nhập ‘#’ để dừng quá trình khởi tạo. lOMoAR cPSD| 60729183
Tạo danh sách liên kết vòng đơn từ các giá trị nhập vào.
3. Nếu lựa chọn là 2: Kiểm tra và thay thế phần tử thứ 5:
Nếu danh sách đã được khởi tạo di chuyển đến phần tử thứ 5 trong danh sách.
Kiểm tra xem giá trị của phần tử này có phải số nguyên tố không.
Nếu là số nguyên tố thì thay thế giá trị này bằng 10 và in ra danh sách.
Nếu không phải số nguyên tố thì in ra thông báo giá trị không là số nguyên tố.
4. Nếu lựa chọn là 3: Tính trung bình nhân các số chẵn, dương, chia hết cho 5:
Nếu danh sách đã dược khởi tạo, duyệt danh sách và tính trung bình nhân các phần
tử thỏa mãn điều kiện (số chẵn, dương, chia hết cho 5).
Nếu không có phần tử thỏa mãn điều kiện, in thông báo.
5. Nếu lựa chọn là 4: Sắp xếp danh sách theo thứ tự tăng dần:
Nếu danh sách đã được khởi tạo, sử dụng thuật toán sắp xếp để sắp xếp danh sách theo thứ tự tăng dần.
In danh sách sau khi đã được sắp xếp.
6. Nếu lựa chọn là 5: Kiểm tra cấp số nhân 3 phần tử liên tiếp trong dãy:
Nếu danh sách đã được khởi tạo, duyệt danh sách và kiểm tra bộ ba từng phần tử liên tiếp.
Nếu tìm thấy bộ ba phần tử là cấp số nhân in chúng ra.
Nếu không tìm thấy, in thông báo.
7. Nếu lựa chọn là 6: Thoát: Kết thúc chương trình.
2.4 Thiết kế giao diện Giao diện điều khiển: lOMoAR cPSD| 60729183 lOMoAR cPSD| 60729183
2.5 Thuật toán, các bước và lưu đồ chi tiết
Yêu cầu 1: Khởi tạo danh sách số nguyên.
1. Khởi tạo danh sách mới:
• head được đặt thành NULL, làm cho danh sách liên kết rỗng.
2. Nhập danh sách mới từ người dùng:
• In ra thông báo "Nhap danh sach :" để hướng dẫn người dùng.
• Sử dụng vòng lặp vô hạn (while(1)) để liên tục đọc dữ liệu từ người dùng.
• Dữ liệu được đọc vào biến input dưới dạng chuỗi.
• Nếu chuỗi bắt đầu bằng dấu #, vòng lặp sẽ được kết thúc (break được gọi) và nhập danh sách sẽ kết thúc.
• Nếu không, chuỗi input được chuyển thành số nguyên (num = atoi(input)) và sau
đó được chèn vào danh sách liên kết sử dụng hàm insertNode().  Danh sách liên
kết mới được xây dựng trong quá trình lặp này. 3. Gán khoiTao thành 1:
• Sau khi danh sách mới đã được tạo, khoiTao được đặt thành 1 để chỉ đánh dấu
rằng danh sách đã được khởi tạo.
4. Kết thúc vòng lặp và kết thúc thuật toán:
• Vòng lặp nhập liệu sẽ kết thúc khi người dùng nhập dấu #. Sau đó, chương trình
sẽ kết thúc và tiếp tục thực hiện các lệnh tiếp theo nếu có. lOMoAR cPSD| 60729183
Hình 2.2 Lưu đồ thuật toán khởi tạo danh sách số nguyên Cài đặt: lOMoAR cPSD| 60729183
// ham de them mot phan tu vao danh sach lien ket don vong
struct Node* insertNode(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node)); newNode->data = data; newNode->next = NULL; if (head == NULL) { newNode- >next = newNode; return newNode; } else { struct Node* current = head;
while (current->next != head) { current = current->next; } current->next = newNode; newNode->next = head; return head; } } case 1: if (khoiTao) {
deleteList(head); // xoa danh sach lien ket don vong cu } lOMoAR cPSD| 60729183
head = NULL; // khoi tao danh sach moi printf("Nhap danh sach :\n"); while (1) { scanf("%s", input); if (input[0] == '#') { break; } num = atoi(input);
head = insertNode(head, num); } khoiTao = 1; break; Kết quả:
Yêu cầu 2: Kiểm tra nếu phần tử thứ 5 là số nguyên tố thì thay bằng 10
1.Kiểm tra xem biến khoiTao có giá trị là true (khác 0) không:
• Nếu khoiTao là true, tiếp tục thực hiện bước tiếp theo.
• Nếu không, in ra thông báo "Danh sach chua duoc khoi tao." và kết thúc lệnh. lOMoAR cPSD| 60729183
2. Tìm phần tử thứ 5 trong danh sách:
• Sử dụng một vòng lặp để đi đến phần tử thứ 5 trong danh sách liên kết đơn. Biến
fifth sẽ trỏ đến phần tử này.
• Kiểm tra xem phần tử thứ 5 có phải là số nguyên tố không:
3. Gọi hàm isPrime(fifth->data) để kiểm tra xem giá trị của phần tử thứ 5 (fifth->data) có
phải là số nguyên tố không.
• Nếu phần tử thứ 5 là số nguyên tố, thay đổi giá trị của nó thành 10.
• Nếu phần tử thứ 5 không phải là số nguyên tố, in ra thông báo "Phan tu thu 5 khong la so nguyen to.".
• Xuất danh sách liên kết sau khi thay thế (nếu cần):
4. Nếu phần tử thứ 5 là số nguyên tố và được thay thế, in ra thông báo "So o vi tri thu 5
laso nguyen to, danh sach sau khi duoc thay the :" và sau đó gọi hàm printList(head)
để xuất danh sách liên kết. lOMoAR cPSD| 60729183
Hình 2.3 Lưu đồ thuật toán kiểm tra nếu phần tử thứ 5 là số nguyên tố thì thay bằng 10 Cài đặt: lOMoAR cPSD| 60729183
// ham kiem tra 1 so co phai la so nguyen to khong int
isPrime(int num) { if (num <= 1) return 0; if (num <= 3) return 1;
if (num % 2 == 0 || num % 3 == 0) return 0; for
(int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) return 0; } return 1; } case 2: if (khoiTao) { struct Node* fifth = head; int count = 1; while (count < 5) { fifth = fifth->next; count++; }
if (isPrime(fifth->data)) { fifth->data = 10;
printf("So o vi tri thu 5 la so nguyen to, danh sach sau khi duoc thay the :\n"); lOMoAR cPSD| 60729183 printList(head); } else {
printf("Phan tu thu 5 khong la so nguyen to.\n"); } } else {
printf("Danh sach chua duoc khoi tao.\n"); } break; Kết quả:
Yêu cầu 3: Tính trung bình nhân các số chẵn, dương, chia hết cho 5.
1. Kiểm tra xem biến khoiTao có giá trị true (khác 0) không:
• Nếu khoiTao là true, tiếp tục thực hiện bước tiếp theo.
• Nếu không, in ra thông báo "Danh sach chua duoc khoi tao." và kết thúc lệnh.
2.Tính tích của các số chẵn dương chia hết cho 5 và trung bình của chúng:
• Sử dụng vòng lặp do-while để duyệt qua danh sách liên kết vòng.
• Trong mỗi lần lặp, kiểm tra xem giá trị của nút hiện tại có phải là số chẵn dương và chia hết cho 5 không.
• Nếu có, nhân giá trị của nút với biến product và tăng giá trị của count lên 1.
• Sau khi vòng lặp kết thúc, kiểm tra xem có số nào thỏa mãn điều kiện không:
• Nếu có ít nhất một số thỏa mãn điều kiện, tính trung bình của chúng và in ra kết quả. lOMoAR cPSD| 60729183
• Nếu không có số nào thỏa mãn điều kiện, in ra thông báo "Khong co so thoa man dieu kien.".