BÀI 30 - THIẾT LẬP THƯ VIỆN CHO CHƯƠNG TRÌNH

MỞ ĐẦU

Câu 1: Em hãy tìm thêm các ví dụ thực tế của mô hình danh sách liên kết.

Giải nhanh:

Một số ví dụ thực tế của mô hình danh sách liên kết:

• Quản lý danh bạ.
• Trình quản lý tập tin.
• Quản lý bài đăng trên mạng xã hội.
• Duyệt web.

1. THIẾT LẬP LỆNH CHO CHƯƠNG TRÌNH

Hoạt động 1. Tìm hiểu ý nghĩa của thư viện chương trình

Câu 1: Em hãy đọc, thảo luận và trả lời các câu hỏi sau:

1. Vì sao lại cần thư viện chương trình?
2. Ý nghĩa của các hàm trong thư viện chương trình là gì?

Giải nhanh:

1. Các thư viện này có thể được dùng nhiều lần và có thể cập nhật, nâng cấp bất cứ lúc nào. 
2. Có chức năng đưa thư viện vào bộ nhớ để sẵn sàng sử dụng.

Câu hỏi 

Câu 1: Những câu nào sau đây là sai về ý nghĩa của việc sử dụng thư viện khi viết chương trình?

A. Chương trình sẽ ngắn hơn.

B. Các hàm thư viện được viết một lần và sử dụng nhiều lần.

C. Chương trình sẵn sàng, dễ hiểu hơn.

D. Chương trình sẽ chạy nhanh hơn.

Giải nhanh:

Đáp án D.

2. CẤU TRÚC DANH SÁCH LIÊN KẾT

Hoạt động 2: Tìm hiểu cấu trúc danh sách liên kết

Câu 1: Đọc, trao đổi và thảo luận để biết cấu trúc dữ liệu của danh sách liên kết và các thao tác dữ liệu cơ bản trên danh sách liên kết.

Giải nhanh:

Danh sách liên kết là cấu trúc dữ liệu bao gồm:

• Cấu trúc note mô tả các phần tử của danh sách. 
• Cấu trúc head là đầu của mỗi danh sách liên kết. 
• Node cuối cùng của danh sách sẽ có thông tin next=None. 

Câu hỏi 

Câu 1: Đoạn hàm sau thực hiện công việc gì?

Giải nhanh:

Vậy đoạn mã này thực hiện việc tạo danh sách liên kết mới, chèn các giá trị 10 và 20 vào danh sách, và hiển thị danh sách liên kết đó.

Câu 2: Viết đoạn chương trình ngắn sử dụng thư viện LinkedList đề thiết lập một danh sách liên kết L và bổ sung các tên "Bình", "Hoa", "Hà" vào danh sách này.

Giải nhanh:

from LinkedList import *

# Tạo danh sách liên kết mới

L = LL()

# Thêm các tên vào danh sách liên kết

insert(L, "Bình")

insert(L, "Hoa")

insert(L, "Hà")

# Hiển thị nội dung của danh sách liên kết

show(L)

LUYỆN TẬP

Câu 1: Viết một thư viện bao gồm các hàm nhập dữ liệu là một dãy só và các hàm thư viện bao gồm sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.

Giải nhanh:

def nhap_day_so():

   """Hàm nhập dãy số từ bàn phím"""

   n = int(input("Nhập số lượng phần tử của dãy: "))

   a = []

   for i in range(n):

       a.append(int(input(f"Nhập phần tử thứ {i+1}: ")))

   return a

def sap_xep_chen(a):

   """Hàm sắp xếp dãy số bằng phương pháp sắp xếp chèn"""

   for i in range(1, len(a)):

       key = a[i]

       j = i - 1

       while j >= 0 and key < a[j]:

           a[j+1] = a[j]

           j -= 1

       a[j+1] = key

   return a

def sap_xep_chon(a):

   """Hàm sắp xếp dãy số bằng phương pháp sắp xếp chọn"""

   for i in range(len(a)):

       min_idx = i

       for j in range(i+1, len(a)):

           if a[j] < a[min_idx]:

               min_idx = j

       a[i], a[min_idx] = a[min_idx], a[i]

   return a

def sap_xep_noi_bot(a):

   """Hàm sắp xếp dãy số bằng phương pháp sắp xếp nổi bọt"""

   for i in range(len(a)):

       for j in range(0, len(a)-i-1):

           if a[j] > a[j+1]:

               a[j], a[j+1] = a[j+1], a[j]

   return a

Câu 2: Cho trước danh sách liên kết L với cấu trúc như đã mô tả trong bài học, muốn lấy ra khoá của node đầu tiên của danh sách thì dùng lệnh nào?

Giải nhanh:

Để lấy ra khoá của node đầu tiên trong danh sách liên kết, bạn có thể sử dụng thuộc tính key của đối tượng node đầu tiên trong danh sách.

VẬN DỤNG

Câu 1: 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.

Giải nhanh:

class Node:

 def __init__(self, key=None):

  self.key = key

  self.next = None

def dem_so_luong_phan_tu(head):

 count = 0 # Khởi tạo biến đếm số lượng phần tử là 0

 current = head # Đặt con trỏ current trỏ đến node đầu tiên của danh sách liên kết

 while current is not None: # Duyệt qua từng node trong danh sách liên kết

  count += 1 # Tăng biến đếm lên 1

  current = current.next # Chuyển con trỏ current sang node kế tiếp trong danh sách liên kết

 return count # Trả về số lượng phần tử đếm được

so_luong_phan_tu = dem_so_luong_phan_tu(L)

Câu 2: Viết hàm delete_Jast(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L.

Giải nhanh:

class Node:

 def __init__(self, key=None):

  self.key = key

  self.next = None

def delete_Jast(L):

 if L is None or L.next is None: # Nếu danh sách liên kết rỗng hoặc chỉ có một phần tử

  return None # Không cần xoá, trả về None

 current = L # Đặt con trỏ current trỏ đến node đầu tiên của danh sách liên kết

 while current.next.next is not None: # Duyệt đến node trước node cuối cùng

  current = current.next # Chuyển con trỏ current sang node kế tiếp trong danh sách liên kết

 current.next = None # Thay đổi liên kết của node trước node cuối cùng để xoá node cuối cùng

 return L # Trả về đối tượng đầu tiên của danh sách liên kết sau khi xoá

L = delete_Jast(L)