Chọn đến phần học sinh cần nhanh chóng thông qua mục lục bằng cách click đến phần đó
I. Lý thuyết trọng tâm
1. Thiết lập thư viện cho chương trình
a) Tại sao cần thư viện?
Khi lập trình, có nhiều hàm được sử dụng lặp đi lặp lại trong các chương trình khác nhau (ví dụ: hàm sắp xếp, hàm nhập dữ liệu, hàm tính toán). Thay vì viết lại mỗi lần, ta có thể gom các hàm đó vào một tệp riêng gọi là thư viện. Khi cần dùng, chỉ việc import thư viện vào là có thể gọi các hàm ngay.
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. Thư viện có thể được dùng nhiều lần, cập nhật và nâng cấp bất cứ lúc nào.
b) Sử dụng thư viện có sẵn của Python
Python cung cấp nhiều thư viện chuẩn. Ví dụ, thư viện math chứa các hàm tính toán toán học.
Có hai cách đưa thư viện vào chương trình:
Cách 1: Import toàn bộ thư viện:
import math # đưa toàn bộ thư viện math vào bộ nhớ
Khi dùng cách này, gọi hàm phải kèm tên thư viện: math.sqrt(5).
Cách 2: Import chỉ những hàm cần dùng:
from math import sqrt, floor, ceil # chỉ đưa 3 hàm vào bộ nhớ
Khi dùng cách này, gọi hàm trực tiếp mà không cần tên thư viện: sqrt(5).
Minh hoạ:
>>> from math import sqrt, floor, ceil
>>> sqrt(5) # Căn bậc hai của 5
2.23606797749979
>>> floor(8.7) # Làm tròn xuống
8
>>> ceil(7.1) # Làm tròn lên
8
| Hàm | Chức năng | Ví dụ |
|---|---|---|
sqrt(x) |
Căn bậc hai của x | sqrt(9) → 3.0 |
floor(x) |
Làm tròn xuống (lấy phần nguyên nhỏ hơn hoặc bằng x) | floor(8.7) → 8 |
ceil(x) |
Làm tròn lên (lấy phần nguyên lớn hơn hoặc bằng x) | ceil(7.1) → 8 |
c) Tự tạo thư viện riêng
Cách tạo thư viện rất đơn giản: viết các hàm vào một tệp .py, đặt tên tệp chính là tên thư viện muốn tạo. Sau đó dùng import để sử dụng.
Ví dụ: Tạo thư viện lib.py chứa hai hàm – nhập dữ liệu và sắp xếp chèn:
Tệp lib.py (thư viện):
def NhapDL():
S = input("Nhập dãy số nguyên cách nhau bởi dấu cách: ")
A = [int(x) for x in S.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
Tệp main.py (chương trình chính, đặt cùng thư mục với lib.py):
from lib import * # Đưa tất cả các hàm của thư viện lib vào bộ nhớ
A = NhapDL()
InsertionSort(A)
print(A)
Giải thích: Lệnh from lib import * sẽ import tất cả các hàm trong tệp lib.py. Sau đó chương trình chính gọi NhapDL() và InsertionSort(A) như bình thường, mặc dù hai hàm này không được định nghĩa trong tệp main.py. Chương trình chính trở nên rất ngắn gọn.
Lưu ý quan trọng: Tệp chương trình chính phải nằm cùng thư mục với tệp thư viện, hoặc phải cấu hình đường dẫn (path) phù hợp.
2. Cấu trúc danh sách liên kết
a) So sánh mảng và danh sách liên kết
Trước khi tìm hiểu danh sách liên kết, hãy nhìn lại mảng (cấu trúc đã quen thuộc):
- Mảng lưu trữ các phần tử được đánh chỉ số liên tục: A[0], A[1], …, A[n−1].
- Truy cập phần tử qua chỉ số rất nhanh:
A[3]lấy được ngay phần tử thứ 4. - Khi xoá một phần tử (ví dụ
del A[1]), các phần tử sau nó tự động dịch lại để dãy vẫn liền mạch.
Danh sách liên kết (linked list) là cấu trúc dữ liệu khác, trong đó các phần tử không được đánh chỉ số mà liên kết với nhau bằng cách mỗi phần tử trỏ tới phần tử tiếp theo. Ví dụ thực tế: khi duyệt web, ta không đánh số các trang đã xem mà chỉ có thể di chuyển đến trang trước/trang sau.
b) Cấu trúc của danh sách liên kết
Danh sách liên kết gồm hai thành phần:
Cấu trúc Node – mô tả từng phần tử trong danh sách. Mỗi node gồm:
- key (khoá): dữ liệu chính của node.
- next: con trỏ tới node tiếp theo. Node cuối cùng có
next = None(không trỏ đến đâu).
Cấu trúc LL (linked list) – mô tả toàn bộ danh sách. Chỉ cần lưu:
- head: con trỏ tới node đầu tiên của danh sách.
Trong Python, hai cấu trúc này được định nghĩa bằng class:
class Node:
def __init__(self, key):
self.key = key
self.next = None
class LL:
def __init__(self):
self.head = None
Giải thích:
class Nodetạo kiểu dữ liệu mới cho mỗi phần tử. Khi tạoNode(5), ta được một node cókey = 5vànext = None.class LLtạo kiểu dữ liệu cho danh sách. Khi tạoLL(), ta được danh sách rỗng vớihead = None.
c) Các thao tác cơ bản trên danh sách liên kết
1. Chèn node vào đầu danh sách – insert(L, k):
Tạo node mới với khoá k, cho node mới trỏ tới node đầu hiện tại, rồi cập nhật head thành node mới.
def insert(L, k):
node = Node(k)
node.next = L.head
L.head = node
Giải thích: Dòng 2 tạo node mới. Dòng 3 cho next của node mới trỏ tới node đầu cũ (nối node mới vào trước danh sách hiện tại). Dòng 4 cập nhật head thành node mới (node mới giờ là đầu danh sách).
2. Xoá node đầu tiên – delete_first(L):
Đơn giản chỉ cần chuyển head sang node tiếp theo. Node đầu cũ sẽ bị bỏ ra khỏi danh sách.
def delete_first(L):
if L.head != None:
L.head = L.head.next
Giải thích: Kiểm tra danh sách không rỗng (L.head != None), rồi gán head bằng head.next – tức node thứ hai trở thành node đầu, node cũ bị loại bỏ.
3. Tìm kiếm node có khoá k – search(L, k):
Duyệt từ đầu danh sách, kiểm tra từng node: nếu tìm thấy khoá k thì trả về node đó, nếu duyệt hết mà không thấy thì trả về None.
def search(L, k):
x = L.head
while x != None and x.key != k:
x = x.next
return x
Giải thích: Biến x bắt đầu từ node đầu. Vòng while dừng khi x đến cuối danh sách (None) hoặc tìm thấy node có key == k. Trả về x: nếu tìm thấy thì x là node cần tìm, nếu không thì x = None.
4. Xoá node có khoá k – delete(L, k):
Phức tạp hơn vì cần xét hai trường hợp:
- Nếu node cần xoá là node đầu → xoá giống
delete_first. - Nếu node cần xoá ở giữa hoặc cuối → duyệt tìm node đó, dùng biến
zluôn theo dõi node ngay trước node cần xoáy. Khi tìm thấy, choz.nexttrỏ thẳng tớiy.next(bỏ qua node y).
def delete(L, k):
if L.head != None:
if L.head.key == k:
L.head = L.head.next
else:
z = y = L.head
while y != None and y.key != k:
z = y
y = y.next
if y != None:
z.next = y.next
Giải thích: Dòng 3–4: nếu node đầu có khoá k → xoá bằng cách chuyển head. Dòng 6–9: duyệt danh sách, y là node đang xét, z là node ngay trước y (luôn đi sau y một bước). Dòng 10–11: nếu tìm thấy (y != None) thì bỏ node y ra bằng cách nối z thẳng tới node sau y.
5. Hiển thị danh sách – show(L):
Duyệt từ đầu đến cuối, in khoá của mỗi node.
def show(L):
x = L.head
while x != None:
print(x.key, end=" ")
x = x.next
print()
d) Thư viện LinkedList hoàn chỉnh
Gom tất cả cấu trúc và hàm trên vào tệp LinkedList.py, ta được một thư viện hoàn chỉnh cho danh sách liên kết:
# LinkedList.py
class Node:
def __init__(self, key):
self.key = key
self.next = None
class LL:
def __init__(self):
self.head = None
def insert(L, k):
node = Node(k)
node.next = L.head
L.head = node
def delete_first(L):
if L.head != None:
L.head = L.head.next
def search(L, k):
x = L.head
while x != None and x.key != k:
x = x.next
return x
def delete(L, k):
if L.head != None:
if L.head.key == k:
L.head = L.head.next
else:
z = y = L.head
while y != None and y.key != k:
z = y
y = y.next
if y != None:
z.next = y.next
def show(L):
x = L.head
while x != None:
print(x.key, end=" ")
x = x.next
print()
e) Ví dụ sử dụng thư viện LinkedList
Tạo danh sách rỗng:
L = LL()
Tạo danh sách có hai node khoá 5 và 2:
L = LL()
insert(L, 5)
insert(L, 2)
# Danh sách: 2 → 5 → None (vì insert chèn vào đầu)
Tạo danh sách từ mảng A:
A = [5, 2, 8, 10, 0, 3]
L = LL()
for k in A:
insert(L, k)
# Danh sách: 3 → 0 → 10 → 8 → 2 → 5 → None (thứ tự ngược)
Lưu ý: Vì insert luôn chèn vào đầu danh sách nên thứ tự trong linked list ngược so với thứ tự chèn.
II. Phương pháp giải các dạng bài tập
Dạng 1: Viết thư viện chương trình
Phương pháp: Gom các hàm liên quan vào một tệp .py, đảm bảo mỗi hàm hoạt động độc lập, đặt tên tệp có ý nghĩa.
Bài 1 (Luyện tập SGK). 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ố, 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:
Tạo tệp sapxep_lib.py:
# sapxep_lib.py
def NhapDL():
"""Nhập dãy số nguyên từ bàn phím"""
S = input("Nhập dãy số nguyên cách nhau bởi dấu cách: ")
A = [int(x) for x in S.split()]
return A
def InsertionSort(A):
"""Sắp xếp chèn – tăng dần"""
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):
"""Sắp xếp chọn – tăng dần"""
n = len(A)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if A[j] < A[min_idx]:
min_idx = j
A[i], A[min_idx] = A[min_idx], A[i]
def BubbleSort(A):
"""Sắp xếp nổi bọt – tăng dần"""
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]
Chương trình sử dụng thư viện:
from sapxep_lib import *
A = NhapDL()
B = A.copy() # Tạo bản sao để thử các thuật toán khác nhau
C = A.copy()
InsertionSort(A)
print("Sắp xếp chèn:", A)
SelectionSort(B)
print("Sắp xếp chọn:", B)
BubbleSort(C)
print("Sắp xếp nổi bọt:", C)
Giải thích: Thư viện sapxep_lib.py chứa 4 hàm độc lập. Chương trình chính import thư viện rồi gọi các hàm. Dùng A.copy() để tạo bản sao, vì mỗi hàm sắp xếp thay đổi mảng trực tiếp – nếu không copy thì sau lần sắp xếp đầu tiên, mảng đã thay đổi rồi.
Dạng 2: Thao tác trên danh sách liên kết
Phương pháp: Nắm rõ cấu trúc Node (key, next), cách duyệt danh sách (từ head, theo next đến None), và nguyên lí chèn/xoá (thay đổi con trỏ next).
Bài 2 (Luyện tập SGK). Cho trước danh sách liên kết L, muốn lấy ra khoá của node đầu tiên thì dùng lệnh nào?
Lời giải:
L.head.key
Giải thích: L.head trỏ tới node đầu tiên của danh sách. Mỗi node có thuộc tính key chứa giá trị dữ liệu. Vậy L.head.key cho ta khoá của node đầu tiên.
Lưu ý: Nếu danh sách rỗng (L.head == None) thì lệnh này sẽ gây lỗi. Nên kiểm tra trước:
if L.head != None:
print(L.head.key)
Dạng 3: Viết hàm mới cho danh sách liên kết
Bài 3 (Vận dụng SGK). Cho trước danh sách liên kết L. Viết hàm đếm số lượng phần tử của danh sách.
Lời giải:
def count(L):
dem = 0
x = L.head
while x != None:
dem = dem + 1
x = x.next
return dem
Giải thích: Duyệt danh sách từ node đầu (L.head) đến cuối (None). Mỗi lần gặp một node (x chưa phải None), tăng biến đếm lên 1 rồi chuyển sang node tiếp theo (x = x.next). Khi vòng lặp kết thúc (x = None, đã đi qua hết), trả về dem.
Minh hoạ với danh sách 5 → 2 → 8 → None:
| Bước | x | x != None? | dem |
|---|---|---|---|
| Bắt đầu | node(5) | Có | 0 → 1 |
| Sau bước 1 | node(2) | Có | 1 → 2 |
| Sau bước 2 | node(8) | Có | 2 → 3 |
| Sau bước 3 | None | Không → dừng | 3 |
Kết quả: count(L) = 3 ✓
Bài 4 (Vận dụng SGK). Viết hàm delete_last(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:
def delete_last(L):
if L.head == None:
return # Danh sách rỗng, không làm gì
if L.head.next == None:
L.head = None # Chỉ có 1 node, xoá thành rỗng
else:
x = L.head
while x.next.next != None: # Duyệt đến node áp chót
x = x.next
x.next = None # Cắt liên kết tới node cuối
Giải thích:
Xét 3 trường hợp:
Trường hợp 1 – Danh sách rỗng (L.head == None): Không có gì để xoá, thoát luôn.
Trường hợp 2 – Chỉ có 1 node (L.head.next == None): Xoá node duy nhất bằng cách gán L.head = None (danh sách trở thành rỗng).
Trường hợp 3 – Có 2 node trở lên: Cần tìm node áp chót (node ngay trước node cuối). Duyệt bằng cách kiểm tra x.next.next != None: khi x.next.next == None thì x.next là node cuối, tức x là node áp chót. Lúc này gán x.next = None để cắt liên kết tới node cuối.
Minh hoạ với danh sách 5 → 2 → 8 → None:
Ban đầu: head → 5 → 2 → 8 → None
Duyệt: x = node(5): x.next.next = node(8) ≠ None → tiếp
x = node(2): x.next.next = None → dừng
Xoá: node(2).next = None
Kết quả: head → 5 → 2 → None
Node chứa khoá 8 đã bị loại khỏi danh sách. ✓
III. Sơ đồ tư duy
┌─ Thư viện có sẵn (math, ...)
│ import math / from math import ...
│
THƯ VIỆN ┌───┤
CHƯƠNG TRÌNH ──┤ └─ Tự tạo thư viện
│ Viết hàm vào tệp .py
│ Import bằng: from lib import *
│
│ ┌─ Node (key + next)
DANH SÁCH │ ├─ LL (head)
LIÊN KẾT ──────┘ │
└─ Thao tác cơ bản:
├─ insert(L, k) – chèn vào đầu
├─ delete_first(L) – xoá node đầu
├─ search(L, k) – tìm kiếm theo khoá
├─ delete(L, k) – xoá node theo khoá
└─ show(L) – hiển thị danh sách
SO SÁNH MẢNG vs LINKED LIST:
┌──────────────┬──────────────────────────────────┐
│ Mảng │ Danh sách liên kết │
├──────────────┼──────────────────────────────────┤
│ Đánh chỉ số │ Không có chỉ số │
│ Truy cập A[i]│ Phải duyệt từ đầu │
│ Chèn/xoá chậm│ Chèn/xoá đầu rất nhanh │
└──────────────┴──────────────────────────────────┘
Thầy Phạm Thành Danh
(Người kiểm duyệt, ra đề)
Chức vụ: Trưởng ban biên soạn môn Tin Học THPT
Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1
Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa