Ứng dụng danh sách liên kết đơn trong quản lý danh sách số nguyê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 Á
KHOA: CÔNG NGHỆ THÔNG TIN BÀI TẬP LỚN
HỌC PHẦN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
ĐỀ TÀI 1: ỨNG DỤNG DANH SÁCH LIÊN KẾT ĐƠN
VÀO QUẢN LÝ DANH SÁCH SỐ NGUYÊN Sinh viên thực Lớp Khóa hiện Lê Khả Anh DCCNTT14.C.1 K14 Trần Thanh Thế DCCNTT14.C.1 K14 Phạm Tùng Dương DCCNTT14.C.1 K14 Nguyễn Văn Hiếu DCCNTT14.C.1 K14 DCCNTT14.C.1 K14 Bắc Ninh, năm 2024 lOMoAR cPSD| 60729183 MỤC LỤC
CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI.......................................................................2
1.1. Giới thiệu....................................................................................................................2
1.2. Phân công công việc...................................................................................................3
CHƯƠNG 2. LƯU ĐỒ THUẬT TOÁN VÀ BỘ MẪU DỮ LIỆU................................4
2.1. Lưu đồ thuật toán........................................................................................................4
2.1.1. Lưu đồ thuật toán nhập một danh sách cho đến khi nhập dấu "$"...........................4
2.1.2. Lưu đồ thuật toán sắp xếp danh sách theo chiều tăng dần của điểm Toán..............5
2.1.3. Lưu đồ thuật toán sắp xếp danh sách theo chiều tăng dần của điểm trung bình......6
2.1.4. Lưu đồ thuật toán tìm sinh viên có điểm trung bình Max/Min.................................7
2.1.5. Lưu đồ thuật toán in ra môn học có điểm trung bình Max/Min...............................8
2.2. Bộ dữ liệu mẫu............................................................................................................9
CHƯƠNG 3. CÀI ĐẶT..................................................................................................10
3.1. Module 1: Nhập 1 danh sách cho đến khi nhập dấu “$” vào tên đối tượng...............10
3.2. Module 2. Sắp xếp danh sách theo chiều tăng dần của điểm toán.............................12
3.3. Module 3. Sắp xếp danh sách theo chiều tăng dần của điểm trung bình...................13
3.4. Module 4. Tìm sinh viên có điểm trung bình Max/Min............................................15
3.5. Module 5 . In ra môn học có điểm trung bình Max/Min...........................................16
3.3. Kết quả......................................................................................................................18
KẾT LUẬN.....................................................................................................................22
1. Kết quả đạt được..........................................................................................................22
2. Hướng phát triển..........................................................................................................22
DANH MỤC TÀI LIỆU THAM KHẢO......................................................................24 lOMoAR cPSD| 60729183
CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI 1.1. Giới thiệu
- Yêu cầu của đề tài
Đề tài "Ứng dụng danh sách liên kết đơn vào quản lý danh sách số" đặt ra mục tiêu
áp dụng cấu trúc dữ liệu danh sách liên kết đơn để quản lý các số nguyên trong một hệ
thống. Đây là một phần của việc học và áp dụng cấu trúc dữ liệu trong lập trình, nơi mà
các sinh viên có cơ hội thực hành các khái niệm lý thuyết thành thạo và áp dụng chúng vào các bài toán thực tế.
Đầu tiên, trong đề tài này, quá trình bắt đầu bằng việc tạo ra một danh sách số từ dữ
liệu nhập vào từ người dùng. Quá trình nhập sẽ tiếp tục cho đến khi người dùng nhập ký
tự "#" để kết thúc việc nhập liệu. Mỗi số nguyên được nhập sẽ được thêm vào cuối danh
sách, tạo thành một cấu trúc dữ liệu đơn giản nhưng mạnh mẽ để quản lý dữ liệu.
Sau khi tạo danh sách ban đầu, người dùng có thể lựa chọn vị trí muốn thêm một số
nguyên mới vào. Điều này cho phép họ thực hiện các thao tác như chèn một số vào đầu
danh sách, cuối danh sách hoặc bất kỳ vị trí nào mà họ mong muốn, tăng tính linh hoạt và
sự kiểm soát của người dùng đối với dữ liệu.
Một yêu cầu quan trọng trong đề tài là đếm số lượng các phần tử trong danh sách
có giá trị bằng một số nguyên k cho trước (k khác 0). Đây là một thử thách không chỉ về
mặt thuật toán mà còn yêu cầu người thực hiện đảm bảo tính chính xác của kết quả và hiệu
suất của thuật toán đối với tập dữ liệu lớn.
Một trong những bài toán thú vị khác là kiểm tra xem trong danh sách có tồn tại ba
số chẵn dương liên tiếp hay không. Nếu có, chương trình sẽ xuất ra vị trí của các số này
trong danh sách. Đây là một ví dụ điển hình cho việc áp dụng các kỹ thuật duyệt danh sách
và kiểm tra điều kiện.
Đối với các số chẵn dương trong danh sách, yêu cầu là đếm số lượng chúng và tính
trung bình cộng giá trị của chúng. Đây là một phần của quá trình thống kê và phân tích dữ
liệu, nâng cao khả năng phân tích và xử lý thông tin của người lập trình. lOMoAR cPSD| 60729183
Cuối cùng, chương trình sẽ hiển thị một số thông tin đặc biệt về danh sách số như
số dương đầu tiên, số âm cuối cùng, dãy số dương tăng dần và dãy số âm giảm dần. Điều
này giúp người dùng có cái nhìn tổng quát và chi tiết về cấu trúc và nội dung của danh sách mà họ đang làm việc. .
1.2. Phân công công việc
Bảng 1: Bảng phân công công việc Công việc Tên đầu Người thực Kết STT chia đến nhỏ Đánh giá việc hiện luận nhất - Tạo danh sách số Nguyên Van 1 1.1 - quá trình A nhập sẽ dừng lại khi nhập dấu “#” 2 3 4 5
CHƯƠNG 2. LƯU ĐỒ THUẬT TOÁN VÀ BỘ MẪU DỮ LIỆU
2.1. Lưu đồ thuật toán
2.1.1. Lưu đồ thuật toán tạo danh sách số, quá trình nhập sẽ dừng lại khi
nhập dấu “#”. lOMoAR cPSD| 60729183
2.1.2. Lưu đồ thuật toán thêm môt phần tử vào danh sách, vị trí thêm vàọ
do ta lựa chọn. lOMoAR cPSD| 60729183
2.1.3. Lưu đồ thuật toán nhập vào môt số k (ḳ 0), đếm xem trong dãy có
bao nhiêu số có giá trị = k. Số lượng các số tìm được có chia hết cho 3 hay không? lOMoAR cPSD| 60729183
2.1.4. Lưu đồ thuật toán kiểm tra xem trong dãy có 3 số chẵn dương đứng
cạnh nhau hay không? Nếu có hãy in ra vị trí của các số này. lOMoAR cPSD| 60729183
2.1.5. Lưu đồ thuật toán đếm số các phần tử có giá trị là số chẵn dương. Tính
trung bình công các số.̣ lOMoAR cPSD| 60729183
2.1.6. Lưu đồ thuật toán đếm số các phần tử có giá trị là số chẵn dương. Tính
trung bình công các số.̣ lOMoAR cPSD| 60729183
2.2. Bộ dữ liệu mẫu
Bảng 2: Bảng dữ liệu mẫu Bộ Input 1 Input 2 Input 3 Mong muốn Kết quả Tính chương đúng trình 1 Nhap lua Nhap ma can Nhap Ma can bo: 1 Ma can bo: Đúng chon: 1 bo (<= 0 de ho Ho dem: 3 1 dung): 1 dem: Ten can bo: 2 Ho dem: 3 3 Ten can bo: 2 lOMoAR cPSD| 60729183 2 1,2,3,4,5 0 0 Kets qua hien thi 1,2,3,4,5 Đúng cau 1 mong muon la : 1,2,3,4,5 3 -5 -10 -3 -3 -3 Đúng 4 30 25 35 35 35 Đúng 5 12 18 15 18 18 Đúng 6 -8 -12 -6 -6 -6 Đúng 7 100 50 75 100 100 Đúng 8 7 7 7 7 7 Đúng 9 21 21 21 21 21 Đúng 10 -15 -20 -10 -10 -10 Đúng
CHƯƠNG 3. CÀI ĐẶT
3.1. Module 1: . Tạo danh sách số, quá trình nhập sẽ dừng lại khi nhập dấu “#”. lOMoAR cPSD| 60729183 case 1:
// 1.1. Tạo danh sách số, quá trình nhập sẽ dừng lại khi nhập dấu
“#”. printf("Nhap cac so nguyen (ket thuc bang #):\n");
while (1) { scanf("%s", nhap); if (nhap[0] == '#') { break; } giaTri = atoi(nhap);
Node* nutMoi = taoNutMoi(giaTri); if (head == NULL) { head = nutMoi; tail = nutMoi; } else { tail->next = nutMoi; tail = nutMoi; } } break;
3.2. Module 2 Thêm môt pḥ
ần tử vào danh sách, vị trí thêm vào do ta lựa chọn.
// Định nghĩa cấu trúc của một nút trong danh sách liên kết đơn typedef struct Node { lOMoAR cPSD| 60729183 int data; struct Node* next; } Node;
// Hàm tạo một nút mới Node* taoNutMoi(int giaTri) { Node* nutMoi =
(Node*)malloc(sizeof(Node)); nutMoi->data =
giaTri; nutMoi->next = NULL; return nutMoi; }
// Hàm thêm một phần tử vào vị trí bất kỳ trong danh
sách void themPhanTu(Node** head, int giaTri, int viTri)
{ Node* nutMoi = taoNutMoi(giaTri); if (viTri ==
0) { nutMoi->next = *head; *head = nutMoi; return; }
Node* hienTai = *head; for (int i = 0; i < viTri - 1
&& hienTai != NULL; i++) { hienTai = hienTai- >next; }
if (hienTai != NULL) { nutMoi-
>next = hienTai->next; hienTai- >next = nutMoi; } else { lOMoAR cPSD| 60729183
printf("Vi tri vuot qua danh sach.\n"); free(nutMoi); } }
3.3. Module 3. Nhập vào môt số k (ḳ 0), đếm xem trong dãy có bao nhiêu số
có giá trị = k. Số lượng các số tìm được có chia hết cho 3 hay không?
// Hàm sắp xếp danh sách liên kết kép sử dụng Bubble Sort
// Hàm nhận tham số là con trỏ hàm so sánh để sắp xếp theo tiêu chí khác nhau
void sap_xep(int (*compare)(SinhVien *, SinhVien *))
{ if (dau == NULL || dau->sau == NULL) return; int swapped; do { swapped = 0; SinhVien *ptr1 = dau; SinhVien *ptr2 = dau->sau; while (ptr2 != NULL) {
if (compare(ptr1, ptr2) > 0) { swap(ptr1, ptr2);
// Cập nhật con trỏ trước và sau sau khi swap if (ptr1->truoc != NULL) lOMoAR cPSD| 60729183 ptr1->truoc->sau = ptr1; else dau = ptr1; if (ptr2->sau != NULL)
ptr2->sau->truoc = ptr2; SinhVien *temp = ptr1; ptr1 = ptr2; ptr2 = temp; swapped = 1; } ptr1 = ptr1->sau; ptr2 = ptr2->sau; } } while (swapped); }
// Hàm so sánh điểm trung bình của hai sinh viên int
compare_diem_trung_binh(SinhVien *a, SinhVien *b)
{ return (lay_diem_trung_binh(a) > lay_diem_trung_binh(b)) ? 1 : - 1; }
3.4. Module 4. Kiểm tra xem trong dãy có 3 số chẵn dương đứng cạnh nhau
hay không? Nếu có hãy in ra vị trí của các số này.
// Hàm tìm sinh viên có điểm trung bình cao nhất và thấp nhất
void tim_sinh_vien_diem_max_min() lOMoAR cPSD| 60729183 { if (dau == NULL) return;
SinhVien *sv_max = dau, *sv_min = dau;
float max_tb = lay_diem_trung_binh(dau), min_tb = lay_diem_trung_binh(dau);
for (SinhVien *i = dau->sau; i != NULL; i = i->sau) {
float tb = lay_diem_trung_binh(i); if (tb > max_tb) { max_tb = tb; sv_max = i; } if (tb < min_tb) { min_tb = tb; sv_min = i; } }
printf("Sinh vien co diem trung binh cao nhat: %s (%.2f)\n", sv_max->ten,
max_tb); printf("Sinh vien co diem trung binh thap nhat: %s (%.2f)\n", sv_min->ten, min_tb); } lOMoAR cPSD| 60729183
3.5. Module 5 . Đếm số các phần tử có giá trị là số chẵn dương. Tính trung
bình công các số.̣
// Hàm tìm môn học có điểm trung bình cao nhất và thấp nhất
void tim_mon_hoc_diem_max_min() { if (dau == NULL) { return; }
float diem_mon_hoc[MAX_MONHOC] = {0}; // Mùng lưu tổng điểm của từng môn
int so_luong_sinh_vien_mon_hoc[MAX_MONHOC] = {0}; // Mảng lưu số lượng sinh viên học từng môn
// Duyệt qua danh sách sinh viên
for (SinhVien *sv = dau; sv != NULL; sv = sv->sau) {
// Duyệt qua các môn học của mỗi sinh viên
for (int i = 0; i < MAX_MONHOC; i++) {
diem_mon_hoc[i] += sv->monhoc[i].diem;
so_luong_sinh_vien_mon_hoc[i]++; } }
float max_tb = -1, min_tb = 101; int mon_max = 0, mon_min = 0;
// Tìm môn học có điểm trung bình cao nhất và thấp nhất
for (int i = 0; i < MAX_MONHOC; i++) {
if (so_luong_sinh_vien_mon_hoc[i] > 0) lOMoAR cPSD| 60729183 {
float tb = diem_mon_hoc[i] / so_luong_sinh_vien_mon_hoc[i]; if (tb > max_tb) { max_tb = tb; mon_max = i; } if (tb < min_tb) { min_tb = tb; mon_min = i; } } }
printf("Mon hoc co diem trung binh cao nhat: %s (%.2f)\n", dau-
>monhoc[mon_max].ten, max_tb);
printf("Mon hoc co diem trung binh thap nhat: %s (%.2f)\n",
dau>monhoc[mon_min].ten, min_tb); }
3.6. Module 6 Hiển thị số dương đầu danh sách, số âm cuối danh sách, dãy số
dương tăng dần, dãy số âm giảm dần.
// Hàm hiển thị danh sách void hienThiDanhSach(Node* head) {
printf("Danh sach: "); while (head != NULL) { printf("%d ", head-
>data); head = head->next; } printf("\n"); } lOMoAR cPSD| 60729183 3.3. Kết quả - Mebu lựa chọn - Lựa chọn 1 - Lựa chọn 2