Bài 15. Cấu trúc dữ liệu danh sách liên kết và ứng dụng trang 146

Khởi động

Em hãy cho biết danh sách mảng có nhược điểm gì?

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

Danh sách mảng có nhược điểm sau: Không thể thay đổi kích thước của mảng khi chương trình đang thực hiện.

? mục 2 HĐ

Dịch vụ cung cấp bài hát trực tuyến thường đưa ra một danh sách N bài hát đứng đầu một tuần, một tháng, ... Sau đó, danh sách này được sử dụng theo nhiều các khác nhau: phát lại theo trình tự ngẫu nhiên, phát lại từ bài N-1 đến 0 hay ngược lại...Em hãy cho biết:

1. Kiểu danh sách này có những đặc điểm gì?

2. Có nên dùng cấu trúc danh sách liên kết để thực hiện kiểu danh sách này hay không?

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

1. Dịch vụ cung cấp bài hát trực tuyến với danh sách N bài hát đứng đầu có những đặc điểm sau:

• Thứ tự sắp xếp: Các bài hát được sắp xếp theo thứ tự từ bài số 1 đến bài số N dựa trên mức độ phổ biến, số lượt nghe, bình chọn, v.v.
• Dễ dàng truy cập và điều hướng: Người dùng có thể dễ dàng truy cập và di chuyển qua lại giữa các bài hát trong danh sách.
• Thay đổi thường xuyên: Danh sách này có thể thay đổi hàng tuần, hàng tháng, hoặc theo các khoảng thời gian khác tùy vào sự cập nhật của dịch vụ.
• Các chức năng phát lại: Danh sách có thể được phát lại theo nhiều cách khác nhau như:
  • Phát lại theo trình tự ngẫu nhiên (shuffle).
  • Phát lại từ bài hát cuối cùng đến bài hát đầu tiên (N-1 đến 0).
  • Phát lại theo thứ tự thông thường (từ 0 đến N-1).

2. Không nên dùng cấu trúc danh sách liên kết cho kiểu danh sách này. Vì việc sử dụng danh sách liên kết có một số hạn chế như:

• Truy cập chậm hơn: Việc truy cập một phần tử trong danh sách liên kết chậm hơn so với danh sách mảng (array) vì cần phải duyệt qua các nút.
• Không hỗ trợ truy cập ngẫu nhiên: Không thể truy cập trực tiếp đến một phần tử cụ thể, cần phải duyệt từ đầu danh sách.
• Tốn bộ nhớ hơn: Mỗi nút trong danh sách liên kết cần thêm bộ nhớ cho con trỏ (pointer) đến nút tiếp theo.

Vận dụng

 Dựa trên hình minh hoạ, mô tả các bước thực hiện các phép toán sau của danh sách liên kết để minh hoạ chúng đều có thời gian là O(1).

a) Thêm nút vào cuối danh sánh, thêm nút vào giữa danh sách.

b) Gỡ bỏ nút ở cuối danh sánh, ở đầu danh sách.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

Gợi ý: Mô tả các bước thực hiện các phép toán sau của danh sách liên kết để minh hoạ chúng đều có thời gian là O(1).

Luyện tập

Phân tích yêu cầu ứng dụng của một danh sách nhóm đứng đâu top X và cho biết, nếu dùng kiểu danh sách của Python để thực hiện thì:

a) Những thao tác cần làm với danh sách top X sẽ thực hiện qua các phép toán danh sách Python như thế nào?

b) Kể tên một vài phép toán danh sách của Python không cần dùng đến cho trường hợp này.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

a) Gợi ý:

Một số hàm thao tác với list thông dụng khác:

cmp(list1, list2): so sánh các phần tử của 2 list

len(list): lấy về chiều dài của list

sum(): Trả về tổng giá trị của các phần tử trong list. Hàm này chỉ làm việc với kiểu number.

max(list): Trả về phần tử có giá trị lớn nhất trong list

min(list): Trả về phần tử có giá trị nhỏ nhất trong list

list(seq): Chuyển đổi một tuple thành list

b) Gợi ý:

Phép toán số học: bao gồm phép cộng +, phép trừ -, phép nhân *, phép chia /, phép chia lấy phần dư %, phép lũy thừa **.

Phép so sánh: bao gồm phép so sánh bằng ==, phép so sánh khác !=, phép so sánh lớn hơn, phép so sánh nhỏ hơn, phép so sánh lớn hơn hoặc bằng và phép so sánh nhỏ hơn hoặc bằng.

Phép logic: bao gồm phép and logic and, phép or logic or và phép not logic not.

Phép gán giá trị: bao gồm phép gán giá trị =, phép gán giá trị tăng lên +=, phép gán giá trị giảm đi -= và phép gán giá trị nhân với *=.

Phép chuyển đổi kiểu dữ liệu: bao gồm các phép chuyển đổi kiểu số int, kiểu thập phân float, kiểu chuỗi str và kiểu boolean bool.

CH1

Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(1)

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

Phép toán danh sách liên kết là các thao tác trên các phần tử trong danh sách liên kết. Thời gian thực hiện của các phép toán này phụ thuộc vào cách triển khai danh sách liên kết và thường là O(1) hoặc O(n).

Các phép toán danh sách liên kết có thời gian thực hiện O(1) bao gồm:

- Truy cập phần tử đầu tiên (head) và phần tử cuối cùng (tail) của danh sách liên kết. Thao tác này được thực hiện bằng cách truy cập trực tiếp vào head hoặc tail của danh sách, không cần phải duyệt qua toàn bộ danh sách.

- Thêm phần tử vào đầu danh sách và cuối danh sách. Thao tác này được thực hiện bằng cách tạo một phần tử mới, gán con trỏ next của phần tử mới thành head hoặc tail của danh sách và cập nhật lại head hoặc tail.

- Xóa phần tử đầu danh sách và cuối danh sách. Thao tác này được thực hiện bằng cách giải phóng phần tử head hoặc tail của danh sách và cập nhật lại head hoặc tail.

CH2

Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(1)

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

Các phép toán danh sách liên kết có thời gian thực hiện O(n) bao gồm:

- Tìm kiếm một phần tử: Để tìm kiếm một phần tử trong danh sách liên kết, ta phải duyệt qua từng nút của danh sách một cách tuần tự để tìm kiếm phần tử cần tìm. Thời gian thực hiện của phép toán này là O(n).

- Chèn một phần tử vào cuối danh sách: Để chèn một phần tử vào cuối danh sách, ta phải duyệt qua từng nút của danh sách để đến cuối danh sách và thực hiện thêm phần tử vào cuối danh sách. Thời gian thực hiện của phép toán này cũng là O(n).

- Xóa một phần tử khỏi danh sách: Để xóa một phần tử khỏi danh sách, ta phải tìm kiếm phần tử đó trong danh sách, sau đó thực hiện xóa phần tử đó bằng cách điều chỉnh các liên kết giữa các nút trong danh sách. Tương tự như tìm kiếm một phần tử, thời gian thực hiện của phép toán này là O(n).

- Đảo ngược danh sách: Để đảo ngược danh sách, ta phải duyệt qua từng nút của danh sách, thay đổi liên kết giữa các nút để đảo ngược danh sách. Vì vậy, thời gian thực hiện của phép toán này là O(n).

CH3

Nếu muốn truy cập nút chứa dữ liệu X thì phải làm gì? Ước lượng thời gian thực hiện.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

Để truy cập nút chứa dữ liệu X trong danh sách liên kết, ta phải duyệt toàn bộ các nút của danh sách từ đầu đến cuối, kiểm tra giá trị của mỗi nút để tìm nút chứa dữ liệu X. Khi đã tìm được nút chứa dữ liệu X, ta có thể thực hiện các thao tác khác với nút đó, ví dụ như xoá nút đó khỏi danh sách.

Do phải duyệt toàn bộ danh sách, thời gian thực hiện của việc truy cập nút chứa dữ liệu X là O(n), với n là số lượng nút trong danh sách. Trong trường hợp danh sách là danh sách liên kết kép, thao tác truy cập cũng có thể được thực hiện theo chiều ngược lại với độ phức tạp tương tự.