Thuật toán sử dụng danh sách liên kết đơn - Bài tập lớn môn Cấu trúc dữ liệu và giải thuật | Đại học Công nghệ Đông Á

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ÊN BÀI TẬP LỚN:
THUẬT TOÁN SỬ DỤNG DANH SÁCH LIÊN KẾT ĐƠN
Sinh viên thực hiện Khóa Lớp Mã sinh viên Đỗ Trọng Hiếu 12 DC.CNTT9 20212668 Tạ Hiếu Thắng 12 DC.CNTT9 20212335 Đỗ Duy Hoàng 12 DC.CNTT9 20212433
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: 22
TÊN (BÀI TẬP LỚN):
THUẬT TOÁN SỬ DỤNG DANH SÁCH LIÊN KẾT ĐƠN ST Sinh viên Khóa Lớp Mã sinh Điểm Điểm Ký tên T thực hiện viên bằng bằng SV số chữ 1 Đỗ Trọng 12 CNTT 20212668 Hiếu 9 2 Tạ Hiếu 12 CNTT 20212335 Thắng 9 3 Đỗ Duy 12 CNTT 20212433 Hoàng 9 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) MỤC LỤC
Chương 1. Tổng quan về đề tài....................................................................7
1.1 Giới thiệu.........................................................................................................7
1.2 Phân công công việc........................................................................................7
Chương 2. Thuật toán. (vẽ sơ đồ, các bước của thuật toán và ví dụ.)..............8
2.1 Lưu đồ thuật toán.............................................................................................8
2.2 Bộ dữ liệu mẫu.(khoảng 10 bộ mẫu)...............................................................8
Chương 3 .Cài đặt.......................................................................................9
Module 1:...............................................................................................................9
Module 2................................................................................................................9
Kết luận...................................................................................................10
Kết quả đạt được..................................................................................................10
Hướng phát triển..................................................................................................10
Danh mục sách tham khảo.........................................................................11
Chương I : Tổng quan đề tài
1.1 Giới thiệu môn học :
Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy
tính sao cho nó có thể được sử dụng một cách hiệu quả.
Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan
trọng. Kinh nghiệm trong việc xây dựng các hệ thống lớn cho thấy khó khăn của
việc triển khai chương trình, chất lượng và hiệu năng của kết quả cuối cùng phụ
thuộc rất nhiều vào việc chọn cấu trúc dữ liệu tốt nhất.
Mỗi loại cấu trúc dữ liệu phù hợp với một vài loại ứng dụng khác nhau, một số cấu
trúc dữ liệu dành cho những công việc đặc biệt. Ví dụ, các B-tree đặc biệt phù hợp
trong việc thiết kế cơ sở dữ liệu. Sau khi cấu trúc dữ liệu được chọn, người ta
thường dễ nhận thấy thuật toán cần sử dụng. Đôi khi trình tự công việc diễn ra theo
thứ tự ngược lại: cấu trúc dữ liệu được chọn do những bài toán quan trọng nhất
định có thuật toán chạy tốt nhất với một số cấu trúc dữ liệu cụ thể. Trong cả hai
trường hợp, việc lựa chọn cấu trúc dữ liệu là rất quan trọng. Tổng quan
Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực
hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn
một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép
thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không
gian bộ nhớ càng tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng
các kiểu dữ liệu, các tham chiếu và các phép toán trên đó được cung cấp bởi
một ngôn ngữ lập trình.
Tri thức đó đã dẫn đến sự nổi lên của nhiều ngôn ngữ lập trình và phương pháp
thiết kế được hình thức hóa, mà trong đó, nhân tố tổ chức quan trọng là các cấu
trúc dữ liệu chứ không phải các thuật toán. Đa số ngôn ngữ có một tính năng thuộc
dạng hệ thống module cho phép các cấu trúc dữ liệu được tái sử dụng an toàn trong
các ứng dụng khác nhau, bằng cách dùng các giao diện có điều khiển để che các
chi tiết cài đặt đã được kiểm thử. Đặc biệt, các ngôn ngữ lập trình hướng đối tượng C++ như
và Java sử dụng lớp (class) cho mục đích này.
Vì cấu trúc dữ liệu có tính chất quyết định đối với các chương trình chuyên nghiệp
nên có rất nhiều hỗ trợ về cấu trúc dữ liệu trong các thư viện chuẩn của các ngôn
ngữ lập trình hiện đại, ví dụ thư viện mẫu chuẩn của C++, Java API, và Microsoft .NET Framework.
Các cấu trúc xây dựng căn bản của hầu hết các cấu trúc dữ liệu
là mảng (array), bản gh
i (record), tổ hợp phân biệt và tham chiếu
Giới thiệu đề tài : (giải thuật toán sử dụng danh sách liên kết đơn)
Cho một danh sách lưu trữ các số nguyên. Viết chương trình tạo một Menu thực hiện các công việc sau:
5.1. Khởi tạo danh sách, quá trình nhập sẽ dừng lại khi nhập dấu “#”.
5.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.
5.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).
5.4. Sắp xếp danh sách theo thứ tự tăng dần.
Cho một danh sách lưu trữ các số nguyên. Viết chương trình tạo một Menu thực hiện các công việc sau:
5.1. Khởi tạo danh sách, quá trình nhập sẽ dừng lại khi nhập dấu “#”.
5.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.
5.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).
5.4. Sắp xếp danh sách theo thứ tự tăng dần.
6. Viết chương trình tạo một Menu để quản lý danh sách sinh viên, mỗi sinh viên là
Bảng 1 Bảng phân công công việc Công việc STT Thành viên Đánh giá Kết luận chia Tạ Hiếu 1 Code thắng Đỗ Trọng 2 Word Hiếu Lưu đồ giải Đỗ Duy 3 thuật Hoàng
Chương 1. Thuật toán. (vẽ sơ đồ, các bước của thuật toán và ví dụ.)
2.1 Lưu đồ thuật toán.
Hình 1 Lưu đồ thuật toán khoier danh sách
Hình 2: Lưu đồ thuật toán tạo node
Hình 3: Lưu đồ thuật toán thêm đầu danh sách
Hình 4: thuật toán scan input
2.2 Bộ dữ liệu mẫu
Bảng 2 Bảng dữ liệu mẫu Kếốt quả Mong muốốn Tính Bộ a b c hiển thị chương đúng MAX trình 1 2 3 6 6 6 Đúng 2 8 8 9 9 7 Sai Chương 3 .Cài đặt. Module 1: #include #include #include struct Node { int data; Node *next; }; typedef Node *List; void Init(List &L) { L = NULL; } Node *CreateNode(int x) { Node *node = new Node; node->data = x; node->next = NULL; return node; } struct LinkedList { Node *head; Node *tail; };
void CreateList(LinkedList &l) { l.head = NULL; l.tail = NULL; }
void AddHead(LinkedList &l, Node *node) { if (l.head == NULL) { l.head = node; l.tail = node; } else { node->next = l.head; l.head = node; } }
void AddTail(LinkedList &l, Node *node) { if (l.head == NULL) { l.head = node; l.tail = node; } else { l.tail->next = node; l.tail = node; } }
Node *GetNode(LinkedList &l, int index) { Node *node = l.head; int i = 1;
while (node != NULL && i != index) { node = node->next; i++; }
if (i == index && node != NULL) return node; return NULL; }
void ModifyNode(LinkedList &l, Node *node, int x) { GetNode(l, 5)->data = x; } void PrintList(LinkedList l) { if (l.head != NULL) { Node *node = l.head; while (node != NULL) {
printf("%d\t", node->data); node = node->next; } } printf("\n"); }
bool IsPrime(int x) //bool:ham tra ve true or false { int i = 2; for (i; i < sqrt(x); i++) if (x % i == 0) return false; return true; } float count(LinkedList l) { float i = 1; float s = 1; Node *node = l.head; while (node != NULL) {
if (node->data != 0 && node->data % 10 == 0 && node->data > 0) { s *= node->data; i++; } node = node->next; } // double mau = 1/i; return pow(s,(1/i)); }
void SortList(LinkedList &l) {
for (Node *p1 = l.head; p1 != NULL; p1 = p1->next) {
for (Node *p2 = p1->next; p2 != NULL; p2 = p2->next) {
if (p1->data > p2->data) { int tmp = p1->data; p1->data = p2->data; p2->data = tmp; } } } } int main() { LinkedList list; CreateList(list); Node *node; char n; int x; while (1) {
printf("Nhap du lieu? Nhap '#' de dung lai: "); scanf("%c", &n); if (n == '#') break;
printf("Nhap gia tri muon them vao: "); scanf("%d", &x); fflush(stdin); node = CreateNode(x); AddTail(list, node); } printf("IN DANH SACH\n"); PrintList(list);
if (IsPrime(GetNode(list, 5)->data)) ModifyNode(list, node, 10); printf("IN DANH SACH\n"); PrintList(list);
printf("Trung binh nhan: %f\n", count(list));
printf("Sap xep theo thu tu tang dan:\n"); SortList(list); PrintList(list); return 0; }
Kết quả đạt được : Kết luận Hướng phát triển:
- Tạo ra một trang web có thể quản lý cán bộ một cách tối ưu và hiệu quả nhất.
- Giảm tối ưu sự sai sót và tăng tối ưu kết quả đúng.
- Phân chia một cách hiệu quả phù hợp nhất.
- Tối ưu hóa công việc và tính toán lương chính xác nhất.
- Thống kê và sao lưu thông tin của cán bộ.
- Lưu ngày, tháng, năm, giờ, phút làm việc của cán bộ.
- Tăng hiệu quả và đơn giản trong việc thêm cán bộ. - Tính bảo mật cao.
Danh mục sách tham khảo
https://topdev.vn/blog/danh-sach-lien-ket-don-trong-c/
https://blog.luyencode.net/danh-sach-lien-ket-don/