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 Á

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 Á. Tài liệu được biên soạn dưới dạng file PDF gồm 19 trang, giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem!

Trường:

Đại học Công Nghệ Đông Á 73 tài liệu

Thông tin:
19 trang 6 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

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 Á

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 Á. Tài liệu được biên soạn dưới dạng file PDF gồm 19 trang, giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem!

205 103 lượt tải Tải xuố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
T
Sinh viên
thực hiện
Khóa Lớp Mã sinh
viên
Điểm
bằng
số
Điểm
bằng
chữ
Ký tên
SV
1
Đỗ Trọng
Hiếu
12 CNTT
9
20212668
2
Tạ Hiếu
Thắng
12 CNTT
9
20212335
3
Đỗ Duy
Hoàng
12 CNTT
9
20212433
CÁN BỘ CHẤM 1
(Ký và ghi rõ họ tên)
CÁN BỘ CHẤM 2
(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.1Giới thiệu môn học :
Trong , là một cách lưu trong khoa học máy tính cấu trúc dữ liệu dữ liệu 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 đặc biệt phù hợp B-tree
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 cần sử dụng. Đôi khi trình tự công việc diễn ra theothuật toán
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 hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn thuật toán
một . Một cấu trúc dữ liệu được thiết kế tốt cho phép cấu trúc dữ liệu trừu tượng
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 , các và các phép toán trên đó được cung cấp bởi kiểu dữ liệu tham chiếu
một .ngôn ngữ lập trình
Tri thức đó đã dẫn đến sự nổi lên của nhiều và phương pháp ngôn ngữ lập trình
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 cho phép các cấu trúc dữ liệu được tái sử dụng an toàn tronghệ thống module
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++ Java lớp như sử dụng (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++, API, và Java
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
), 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
STT
Công việc
chia
Thành viên Đánh giá Kết luận
1 Code
Tạ Hiếu
thắng
2 Word
Đỗ Trọng
Hiếu
3
Lưu đồ giải
thuật
Đỗ Duy
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
B a b c
Mong muốốn
hi n th
MAX
Kếốt qu
ch ngươ
trình
Tính
đúng
1 2 3 6 6 6 Đúng
2 8 8 9 9 7 Sai
Chương 3 .Cài đặt.
Module 1:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
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/
| 1/19

Preview text:

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/