Bài tập thực hành Danh sách liên kết - Cấu trúc dữ liệu và thuật toán môn Cơ sở dữ liệu | Đại học sư phạm Hà Nội

lOMoAR cPSD| 40551442 Data Structures and PKA — Fall 2022 Algorithms Assignment 4 Lecturer: Duc-Minh VU § Danh sách liên kết § Phần 1: Mục tiêu
• Nắm được định nghĩa, các thao tác, và độ phức tạp của cấu trúc danh sách liên kết phổ biến gồm danh sách liên
kết đơn, danh sách liên kết đôi, danh sách liên kết vòng.
• Đọc hiểu code mẫu và các ví dụ mẫu về danh sách liên kết.
• Làm được các bài tập lý thuyết về danh sách liên kết
• Triển khai được các thuật toán danh sách liên kết trên ngôn ngữ lập trình C/C++.
• Tìm hiểu/sử dụng cấu trúc dữ liệu danh sách liên kết của ngôn ngữ C++ (tùy chọn) Phần 2: Lý thuyết
• Hiểu lý thuyết, cách thực thi các thuật toán liên quan đến danh sách liên kết/
• Mục 3.3 [2], Chương 4 [1]
• Lý thuyết/Bài tập và code mẫu: https://www.geeksforgeeks.org/data-structures/linked-list/?ref=gcse Phần 3: Practice problems (1) Bài tập lý thuyết
1. Bài tập 1 - 14 - Chương 3 [2].
2. Bài tập 4.10 - 4.14, Chương 4 [1]. (2) Bài tập thực hành
1. Danh sách liên kết đơn
1. Bài tập 21 - 31 - https://codelearn.io/learning/cau-truc-du-lieu-va-giai-thuat
2. Bài tập 11 - 22 - https://codelearn.io/learning/thu-vien-chuan-cpp (Thực hành thư viện danh sách liên kết trong C++ - Tùy chọn)
3. Cài đặt danh sách liên kết đơn - https://leetcode.com/problems/design-linked-list/
• Thực hành các thao tác khai báo, khởi tạo danh sách liên kết đơn, các thao tác chèn, xóa.
4. Số phần tử trong danh sách liên kết - https://practice.geeksforgeeks.org/problems/count-nodes-of-linkedlist/1
This assignment is due xxx and the date of submission is Ngày 11 tháng 10 năm 2022. lOMoAR cPSD| 40551442
LATEX template for this assignment is SEU-ML-Assign open source at tvj.one/ml-tex under the MIT License. E-mail me@tvj.one for support.
• Ref: https://www.geeksforgeeks.org/find-length-of-a-linked-list-iterative-and-recursive/
• Duyệt danh sách liên kết và đếm số phần tử. 1 int getCount(struct Node* head) 2 { 3 4 int cnt = 0; 5
while (head != NULL) head = head->next, cnt++; return cnt; 6 }
5. Phần tử thứ N từ cuối danh sách liên kết - https://practice.geeksforgeeks.org/problems/nth-node-fromend-of-linked-list/1
• Ref: https://www.geeksforgeeks.org/nth-node-from-the-end-of-a-linked-list/
• Duyệt danh sách liên kết, đếm M là số phần tử, sau đó duyệt danh sách liên kết lần nữa để tìm đến phần tử thứ M−N+1. 1 int getCount(struct Node* head) 2 { 3 4 int N = getCount(head); 5
if (n < 0 || n > N ) return -1; 6 n = N - n + 1; 7
while(--n) head = head->next; return head->data; 8 }
6. Đếm số lần xuất hiện của một giá trị trong danh sách liên kết - https://practice.geeksforgeeks.org/problems/occurenceof- an-integer-in-a-linked-list/1
• Ref: https://www.geeksforgeeks.org/write-a-function-that-counts-the-number-of-times-a-given-int-occursin-a- linked-list/
• Duyệt danh sách liên kết cơ bản. 1 int
count(struct node* head, int search_for) 2 { 3 4
int cnt = 0; while(head){ if (head->data == search_for) cnt++; 5 head = head->next; 6 } 7 return cnt; 8 9 }
7. Tìm phần tử ở giữa danh sách liên kết - https://leetcode.com/problems/middle-of-the-linked-list/
• Ref: https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/
• Tương đương với tìm phần tử thứ N/2+1 với N là số phần tử của danh sách liên kết.
8. Kiểm tra danh sách liên kết có kết nối vòng - https://leetcode.com/problems/linked-list-cycle/
• Do số phần tử của danh sách liên kết không quá 104, nên nếu duyệt mà không gặp phần tử NULL sau 104 lần lặp
thì chắc chắn là danh sách liên kết vòng. 1
bool hasCycle(struct ListNode *head) { for(int i = 0; i < 2
10001; i++){ if (head) head = head -> next; 3 else return false; 4 } 5 return true; 6 } 7 lOMoAR cPSD| 40551442 Assignment 4 – 2
9. Thêm phần tử mới vào danh sách liên kết - https://practice.geeksforgeeks.org/problems/linked-list-insertion1587115620/1?
• Ref: https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/
10. Đảo ngược các phần tử trong danh sách liên kết - https://practice.geeksforgeeks.org/problems/reverse-alinked-list/1
• Ref - https://www.geeksforgeeks.org/reverse-a-linked-list/
• Ref - https://www.geeksforgeeks.org/print-reverse-of-a-linked-list-without-actually-reversing/
• Tương đương với việc tạo một danh sách liên kết mới thông qua duyệt danh sách liên kết hiện tại và thêm mỗi
phần tử của danh sách hiện tại vào đầu danh sách mới.
11. Kiểm tranh danh sách liên kết có là palindrome - https://leetcode.com/problems/palindrome-linked-list/
• Ref - https://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/
• Tương đương với việc tạo danh sách liên kết đảo ngược và sau đó duyệt đồng thời hai danh sách để kiểm tra hai
danh sách có chứa cùng nội dung.
12. Xóa phần tử ở giữa danh sách liên kết - https://practice.geeksforgeeks.org/problems/delete-middle-oflinked-list/1
• Ref: https://www.geeksforgeeks.org/delete-middle-of-linked-list/
13. Tráo đổi phần tử thứ k từ đầu danh sách với phần tử thứ k từ cuối danh sách - https://practice.geeksforgeeks.org/problem
kth-node-from-beginning-and-kth-node-from-end-in-a-singly-linked-list/1
• Ref: https://www.geeksforgeeks.org/swap-kth-node-from-beginning-with-kth-node-from-end-in-a-linkedlist/
14. Xóa phần tử thứ N từ cuối danh sách - https://leetcode.com/problems/remove-nth-node-from-end-of-list/
• Thực hiện duyệt và xóa trên danh sách liên kết đơn. Xác định vị trí phần tử trước phần tử cần xóa và thực hiện thao tác xóa.
15. Xóa các phần tử trùng nhau trong danh sách không giảm - https://leetcode.com/problems/removeduplicates-from-sorted- list/
• So sánh hai phần tử liên kết, nếu có cùng giá trị thì xóa phần tử đứng sau.
16. Xóa các phần tử có giá trị bằng một giá trị cho trước - https://leetcode.com/problems/remove-linkedlist-elements/
• Thực hiện duyệt và xóa trên danh sách liên kết đơn. Cần duy trì con trỏ trỏ đến trước phần tử cần xóa.
17. Dịch phải danh sách liên kết - https://leetcode.com/problems/rotate-list/
18. Chèn vào danh sách liên kết vòng đã sắp xếp https://practice.geeksforgeeks.org/problems/sorted-insert- for-circular-linked-list/1
19. Sắp xếp chèn trên danh sách liên kết - https://leetcode.com/problems/insertion-sort-list/
• Mô phỏng Insertion sort trên danh sách liên kết.
20. Sắp xếp danh sách liên kết - https://leetcode.com/problems/sort-list/
21. Trộn hai danh sách liên kết tăng dần - https://practice.geeksforgeeks.org/problems/merge-two-sortedlinked-lists/1
• Ref: https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/
• Mô phỏng thao tác trộn hai dãy tăng dần và thực hiện trên danh sách liên kết
22. Trộn xen kẽ hai danh sách liên kết - https://practice.geeksforgeeks.org/problems/merge-list-alternatingly/1
• Ref: https://www.geeksforgeeks.org/merge-a-linked-list-into-another-linked-list-at-alternate-positions/
23. Mergesort trên danh sách liên kết - https://practice.geeksforgeeks.org/problems/sort-a-linked-list/1
• Ref: https://www.geeksforgeeks.org/merge-sort-for-linked-list/
• Thực thi mergesort trên danh sách liên kết.
24. Quicksort trên danh sách liên kết - https://www.geeksforgeeks.org/quicksort-on-singly-linked-list/ lOMoAR cPSD| 40551442 Assignment 4 – 3
• Ref: https://practice.geeksforgeeks.org/problems/quick-sort-on-linked-list/1
25. Cộng hai đa thức được biểu diễn bằng danh sách liên kết -
https://practice.geeksforgeeks.org/problems/polynomialaddition/1
• Ref: https://www.geeksforgeeks.org/adding-two-polynomials-using-linked-list/
26. Nhân hai số được biểu diễn bằng danh sách liên kết - https://practice.geeksforgeeks.org/problems/multiplytwo-linked-lists/1
• Ref: https://www.geeksforgeeks.org/adding-two-polynomials-using-linked-list/
2. Danh sách liên kết đôi
1. Thêm phần tử mới trong danh sách liên kết đôi - https://practice.geeksforgeeks.org/problems/insert-anode-in-doubly-linked- list/1
• Ref: https://www.geeksforgeeks.org/doubly-linked-list/
2. Xóa phần tử trong danh sách liên kết đôi - https://practice.geeksforgeeks.org/problems/delete-node-indoubly-linked-list/1
• Ref:https://www.geeksforgeeks.org/delete-a-node-in-a-doubly-linked-list/
3. Chèn phần tử vào danh sách liên kết đôi tăng dần - https://practice.geeksforgeeks.org/problems/insertin-sorted-way-in-a- sorted-dll/1
• Ref: https://www.geeksforgeeks.org/insert-value-sorted-way-sorted-doubly-linked-list/
4. Quay danh sách liên kết đôi k lần - https://practice.geeksforgeeks.org/problems/rotate-doubly-linked-listby-p-nodes/1
• Ref: https://www.geeksforgeeks.org/rotate-doubly-linked-list-n-nodes/
5. Quicksort trên danh sách liên kết đôi - https://practice.geeksforgeeks.org/problems/quicksort-on-doublylinked-list/1
• Ref: https://www.geeksforgeeks.org/quicksort-for-linked-list/
3. Danh sách liên kết vòng
1. Duyệt danh sách liên kết vòng - https://practice.geeksforgeeks.org/problems/circular-linked-list-traversal/1
• Ref: https://www.geeksforgeeks.org/circular-linked-list-set-2-traversal/
2. Kiểm tra một danh sách có là danh sách liên kết vòng - https://practice.geeksforgeeks.org/problems/circularlinked-list/1
• Ref: https://www.geeksforgeeks.org/check-if-a-linked-list-is-circular-linked-list/
3. Tách danh sách liên kết vòng ra làm hai danh sách liên kết vòng - https://practice.geeksforgeeks.org/problems/splita-circular- linked-list-into-two-halves/1
• Ref: https://www.geeksforgeeks.org/split-a-circular-linked-list-into-two-halves/
4. Bổ sung phần tử vào danh sách liên kết vòng tăng dần - https://practice.geeksforgeeks.org/problems/sortedinsert-for- circular-linked-list/1
• Ref: https://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/
5. Xóa và đảo ngược danh sách liên kết vòng - https://practice.geeksforgeeks.org/problems/deletion-andreverse-in-linked-list/1
• Ref: https://www.geeksforgeeks.org/deletion-circular-linked-list/ Phần 4: Bổ trợ
• C++ cơ bản 1 - https://codelearn.io/learning/cpp-cho-nguoi-moi-bat-dau
• C++ cơ bản 2 - https://howkteam.vn/course/khoa-hoc-lap-trinh-c-can-ban-4 lOMoAR cPSD| 40551442 Assignment 4 – 4 Phần 5: Tự đánh giá
□ Giải thích được định nghĩa cấu trúc dữ liệu danh sách liên kết và các thao tác trên cấu trúc dữ liệu danh sách liên kết.
□ Có khả năng lựa chọn và triển khai cấu trúc dữ liệu danh sách liên kết đáp ứng nhu cầu bài toán.
□ Có khả năng sử dụng cấu trúc dữ liệu danh sách liên kết trong ngôn ngữ C++. Tài liệu
[1] Đỗ Xuân Lôi. Cấu trúc dữ liệu và giải thuật. Đại học Quốc Gia Hà nội, 2010.
[2] Nguyễn Đức Nghĩa. Cấu trúc dữ liệu và thuật toán. Nhà xuất bản Bách Khoa Hà nội, 2021.