Cho trước một danh sách liên kết L. Viết một hàm đếm số lượng phần tử của danh sách liên kết này

Trả lời câu hỏi SGK Tin 11 Kết nối tri thức trang 142: Cho trước một danh sách liên kết L. Viết một hàm đếm số lượng phần tử của danh sách liên kết này (Bài 30: Thiết lập thư viện cho chương trình)

Câu hỏi: Cho trước một danh sách liên kết L. Viết một hàm đếm số lượng phần tử của danh sách liên kết này

Trả lời ngắn gọn: 

Để đếm số lượng phần tử trong danh sách liên kết ta có thể sử dụng một hàm đệ qui để duyệt qua từng nút của danh sách và đếm số lượng nút đó. Cụ thể hàm này sẽ kiểm tra xem danh sách có rỗng không, nếu rỗng thì trả về 0, nếu không rỗng thì đệ qui gọi lại hàm để đếm số lượng nút kế tiếp và trả về giá trị này cộng với 1 (do nút hiện tại là một phần tử của danh sách). Ta có thể sử dụng hàm này để đếm số lượng phần tử trong danh sách liên kết.

Trả lời chi tiết:

Để đếm số lượng phần tử trong danh sách liên kết ta có thể sử dụng một hàm đệ qui để duyệt qua từng nút của danh sách và đếm số lượng nút đó. Mã nguồn Python cho hàm này như sau:

def dem_phan_tu(danh_sach):
   # Nếu danh sách là rỗng, trả về 0
   if danh_sach is None:
       return 0
   
   # Nếu danh sách không rỗng, đệ qui để đếm số lượng nút
   # Đệ qui đến khi nút cuối cùng được đạt được
   return 1 + dem_phan_tu(danh_sach.next)

Giải thích:

- Nếu danh sách là rỗng (tức là None), ta trả về 0 vì không có phần tử nào trong danh sách.

- Nếu danh sách không rỗng, ta đệ qui gọi lại hàm dem_phan_tu() với đối số là nút kế tiếp của nút hiện tại. Hàm đệ qui này sẽ đếm số lượng phần tử của danh sách con bắt đầu từ nút kế tiếp và trả về giá trị này cộng với 1 (do nút hiện tại là một phần tử của danh sách).

- Khi hàm đệ qui đến nút cuối cùng, ta sẽ trả về giá trị 1, và các giá trị trả về từ các lần đệ qui trước đó sẽ được tính toán và cộng dồn lại để đưa ra kết quả cuối cùng.

>> Xem toàn bộ: Soạn Tin 11 Kết nối tri thức