Bài 30. Thiết lập thư viện cho chương trình

Chủ đề 6. Kĩ thuật lập trình – Bài 30. Thiết lập thư viện cho chương trình – sách giáo khoa trang 137 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.

Chủ đề 6. Kĩ thuật lập trình – Bài 30. Thiết lập thư viện cho chương trình

Khởi động

Em đã học về cấu trúc mảng (một chiều hoặc hai chiều). Cấu trúc mảng là một danh sách các phần tử được đánh chỉ số và quan hệ với nhau thông qua hệ thống chỉ số này. Giả sử A[0], A[1], …, A[n – 1] là mảng n phần tử, nếu thực hiện lệnh, ví dụ del A[1], xoá một phần tử của dãy trên, thì các phần tử còn lại sẽ tự động điều chỉnh lại chỉ số đề đối tượng vẫn là mảng (nhưng có n − 1 phần tử ). –

Cấu trúc danh sách liên kết (hay danh sách móc nối, linked list) là đối tượng có cấu trúc gần giống với mảng nhưng có liên kết không chặt chẽ như mảng. Một ví dụ của cấu trúc danh sách liên kết là mô hình các trang web. Khi duyệt web, em không thể đánh chỉ số cho từng trang web đã duyệt, mà chỉ có thể di chuyển đến các trang trước và trang sau.

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.

Lời giải:

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ạ điện thoại: Mỗi liên hệ (contact) sẽ là một nút trong danh sách liên kết và chứa thông tin như tên, số điện thoại, địa chỉ email, v.v.

Lịch hẹn: Một ứng dụng lịch hẹn có thể sử dụng danh sách liên kết để lưu trữ các sự kiện và thông tin liên quan. Mỗi sự kiện có thể được biểu diễn bằng một nút trong danh sách.

Quản lý tệp và thư mục: Hệ thống quản lý tệp và thư mục trên máy tính thường sử dụng cấu trúc danh sách liên kết để biểu diễn cấu trúc cây của thư mục và tệp tin. Mỗi thư mục có thể được coi như một nút trong danh sách liên kết.

Trình phát media: Mỗi bài hát hoặc tập tin media có thể là một nút trong danh sách, và danh sách này có thể được sắp xếp theo thứ tự chơi.

Trình duyệt web: Trình duyệt web sử dụng danh sách liên kết để theo dõi lịch sử duyệt web. Mỗi trang web trước và sau đều được biểu diễn bằng các nút trong danh sách.

Chương trình chat: Ứng dụng chat hoặc tin nhắn có thể sử dụng danh sách liên kết để theo dõi các cuộc trò chuyện. Mỗi cuộc trò chuyện có thể được biểu diễn bằng một nút trong danh sách và các tin nhắn trong cuộc trò chuyện có thể là các phần tử của danh sách con.

1. Thiết lập thư viện cho chương trình

Hoạt động 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ì?

Lời giải:

Thư viện chương trình là tập hợp các hàm được đặt trong các mô đun độc lập để dùng chung cho nhiều chương trình khác nhau. 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 giúp tiết kiệm thời gian và dễ dàng tích hợp giúp cho việc mở rộng và bảo trì dự án dễ dàng hơn.
Các hàm trong thư viện chương trình có ý nghĩa là cung cấp các đoạn mã đã được đóng gói lại để thực hiện một chức năng hoặc tính năng cụ thể. Các hàm trong thư viện chương trình thường được thiết kế và cài đặt để hoạt động trong một môi trường cụ thể.

Câu hỏi

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.

Lời giải:

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

Đây là một khẳng định SAI, vì việc sử dụng thư viện chương trình không nhất thiết đồng nghĩa với việc chương trình sẽ chạy nhanh hơn. Tốc độ thực thi của chương trình phụ thuộc vào cách thức xử lý của thư viện chương trình, cách thức tích hợp vào chương trình chính, cấu hình của hệ thống, và các yếu tố khác. Có thể có những trường hợp thư viện chương trình gây ra độ trễ hoặc ảnh hưởng đến hiệu suất của chương trình. Việc tối ưu hóa hiệu suất là một công việc riêng biệt và phải được thực hiện cẩn thận trong quá trình phát triển phần mềm.

2. Cấu trúc danh sách liên kết

Hoạt động 2

Đọ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.

Lời giải:

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. Mỗi node sẽ có dữ liệu khóa (key) là thông tin chính và thông tin next để kết nối sang phần tử tiếp theo của danh sách.

Cấu trúc head là đầu của mỗi danh sách liên kết. Head luôn chỉ vào node đầu tiên của danh sách.

Node cuối cùng của danh sách sẽ có thông tin next=None (dữ liệu rỗng). Có thể thiết lập các hàm tìm kiếm, bổ sung hoặc xóa thông tin trên danh sách liên kết.

Câu hỏi

Câu 1. Đoạn chương trình sau thực hiện công việc gì?

Lời giải:

Chương trình thực hiện các công việc sau:

Đoạn mã trên sử dụng thư viện LinkedList và tạo một đối tượng danh sách liên kết mới (gọi là L) bằng cách gọi hàm khởi tạo LL().
Sau đó, thực hiện hai lần gọi hàm insert(L,10) và insert(L,20) để chèn các giá trị 10 và 20 vào danh sách liên kết L.
Cuối cùng, gọi hàm show(L) để hiển thị nội dung của danh sách liên kết L sau khi đã chèn các giá trị 10 và 20 vào trong đó.

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.

Lời giải:

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.

Lời giải:

Thư viện có tên sapxep.py có thể thiết lập như sau:

# Tạo thư viện có tên sapxep.py

def nhapDL():
    xau = input("Nhập dãy số nguyên cách nhau bởi dấu cách: ")
    A = [int(x) for x in xau.split()]
    return A
    
def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = value

def SelectionSort(A):
    n = len(A)
    for i in range(n - 1):
        iMin = i
        for j in range(i + 1, n):
            if A[j] < A[iMin]:
                iMin = j
                A[i], A[iMin] = A[iMin], A[i]

def BubbleSort(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

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?

Lời giải:

Dùng lệnh value = L.head.key sẽ lấy khóa node đầu tiên của danh sách( nếu L không rỗng).

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.

Lời giải:

# Hàm đếm số phần tử của danh sách liên kết L
def len(L):
    k = 0
    x = L.head
    while x != None:
        x = x.next
        k = k + 1
    return k

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.

Lời giải:

# Hàm xóa phần tử cuối cùng của danh sách L
def delete_last(L):
    if L.head != Node:
        y = L.head
        x = L.head
        while x.next != None:
            y = x
            x = x.next
        y.next = None

Xem các bài giải khác: Giải bài tập SGK lớp 11 định hướng Khoa học máy tính – NXB Kết nối tri thức với cuộc sống

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech