Chương 6: Danh sách liên kết

Bài tập 1:

Cài đặt danh sách liên kết đơn với mỗi node có kiểu dữ liệu là số nguyên. Viết các hàm/phương thức thực hiện các thao tác cơ bản trên danh sách liên kết này:

1. Thêm vào đầu danh sách.
2. Thêm vào cuối danh sách.
3. Thêm vào sau một node có giá trị là val.
4. Xóa đầu danh sách.
5. Xóa một node có giá trị là val.
6. Xóa một node nằm sau node có giá trị là val.
7. Xóa toàn bộ danh sách.
8. Tìm node có giá trị là val.
9. Đếm số phần tử tận cùng là 7 và chia hết cho 7 trong danh sách.
10. Tính trung bình cộng các số nguyên tố hiện có trong danh sách.
11. In ra số nguyên tố lớn nhất (nếu có) trong danh sách.
12. Cho biết trong danh sách có bao nhiêu số nguyên tố phân biệt.
13. Tách danh sách con gồm những phần tử không phải số nguyên tố trong danh sách.
14. Đảo ngược danh sách liên kết.
15. Kiểm tra xem danh sách có tăng dần hay giảm dần không.
16. Lấy/xóa/gán giá trị của phần tử thứ i trong danh sách.
17. Xóa k phần tử liên tiếp bắt đầu từ vị trí thứ i.
18. (*) In dãy con tăng dần (liên tiếp) dài nhất xuất hiện trong danh sách. Nếu có nhiều dãy cùng dài nhất chỉ cần in ra dãy đầu tiên.
19. (*) In ra tất cả các dãy con tăng (liên tiếp) của danh sách.
20. Xóa bỏ danh sách phần tử trùng lặp (chỉ giữ lại phần tử đầu tiên).

Bài tập 2:

Sử dụng danh sách liên kết để biểu diễn 2 tập hợp A, B gồm m,n phần tử:

1. Xuất ra những phần tử có trong A mà không có trong B.
2. Tìm C = A U B (ghép A, B thành C sao cho C không có phầntử trùng nhau).
3. Tìm tập giao của 2 tập hợp D = A giao B

Bài tập 3:

Viết chương trình tổng, hiệu của 2 số nguyên lớn tối đa 32 chữ số, trong đó sử dụng danh sách liên kết để biểu diễn 2 số nguyên này.

Bài tập 4:

Khai báo danh sách liên kết đơn để biểu diễn đa thức.

Cài đặt các thao tác sau trên đa thức:

1. In đa thức
2. Tính giá trị đa thức
3. Chuẩn hóa đa thức (bao gồm loại bỏ những xi trùng nhau, sắp giảm dần theo số mũ).
4. Cộng (trừ) hai đa thức
5. Nhân hai đa thức.