Cấu trúc dữ liệu và giải thuật là gì? Học bằng Python
Bài 1/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 8 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Cấu trúc dữ liệu và giải thuật là hai nửa của một lời giải. Cấu trúc dữ liệu là cách cất dữ liệu (list, dict, class tự viết), giải thuật là các bước làm trên dữ liệu đó tới khi có câu trả lời. Bạn cần nhóm bài này khi chương trình phải trả lời nhanh trên dữ liệu lớn, như tìm tuyến xe đi qua một trạm hay gọi đúng người tiếp theo trong hàng chờ.
Cần biết trước: chọn list, tuple, dict hay set, lệnh return và __init__ và self.
Cùng câu hỏi, hai cách cất dữ liệu
Bản đồ xe buýt của Huế được cất theo tuyến: mỗi mã tuyến kèm list các trạm nó đi qua. Để biết tuyến nào dừng ở Chợ Đông Ba, hàm dưới đây phải mở từng tuyến và dò list trạm của tuyến đó.
ban_do = {
"01": ["Bến xe phía Bắc", "Ga Huế", "Đại Nội"],
"02": ["Ga Huế", "Chợ Đông Ba", "Thiên Mụ"],
"05": ["Đại Nội", "Chợ Đông Ba"],
}
def tuyen_qua(ban_do, tram):
ket_qua = []
for ma, cac_tram in ban_do.items():
if tram in cac_tram:
ket_qua.append(ma)
return ket_qua
print(tuyen_qua(ban_do, "Chợ Đông Ba"))KẾT QUẢ
['02', '05']Hàm đúng, nhưng mỗi lần hỏi nó dò lại từng tuyến và từng trạm. Với ba tuyến thì không sao. Với vài trăm tuyến và hàng nghìn câu hỏi mỗi phút, việc dò đó lặp lại liên tục.
Đổi cách cất: dict mới lấy tên trạm làm khóa, giá trị là list các tuyến dừng ở đó. Câu hỏi khi ấy chỉ còn một lần tra khóa.
theo_tram = {
"Ga Huế": ["01", "02"],
"Đại Nội": ["01", "05"],
"Chợ Đông Ba": ["02", "05"],
}
print(theo_tram.get("Chợ Đông Ba", []))
print(theo_tram.get("Bến Ngự", []))KẾT QUẢ
['02', '05']
[]Dữ liệu là một, nhưng cấu trúc đổi thì giải thuật đổi theo: từ "dò từng tuyến" thành "tra một khóa". Bạn đổi cấu trúc một lần, rồi các câu hỏi sau đều rẻ. Đổi "Bến Ngự" thành "Đại Nội" rồi chạy lại: dòng thứ hai in ['01', '05'].
Giải thuật là các bước có điểm dừng
Giải thuật là một dãy bước rõ ràng: nhận dữ liệu vào, làm từng bước, dừng lại với một kết quả. Hàm tuyen_qua() ở trên là một giải thuật: vào là bản đồ và tên trạm, các bước là vòng for cùng phép thử in, ra là list mã tuyến qua return. Nó chắc chắn dừng vì bản đồ có hữu hạn tuyến.
Hai giải thuật cho cùng một kết quả vẫn có thể khác nhau rất xa về số bước. Cách đếm số bước đó và ký hiệu O lớn đi kèm là việc của bài độ phức tạp Big O, bài đầu tiên của nhóm.
Gói cấu trúc và thao tác vào một class
Các bài sau của nhóm tự viết cấu trúc dữ liệu thành class: dữ liệu nằm trong thuộc tính, thao tác là phương thức. Nơi dùng class chỉ gọi phương thức, không cần biết bên trong là list hay dict.
class DanhBa:
def __init__(self):
self.ma_theo_ten = {}
def them(self, ten, ma):
self.ma_theo_ten[ten] = ma
def tra(self, ten):
return self.ma_theo_ten.get(ten)
danh_ba = DanhBa()
danh_ba.them("Lan", 101)
danh_ba.them("Ngọc", 103)
danh_ba.them("Ngọc", 106)
print(danh_ba.tra("Ngọc"), danh_ba.tra("Quân"))KẾT QUẢ
106 NoneDanh bạ khách giữ tên và mã khách. Thêm lại Ngọc với mã mới thì dict ghi đè mã cũ, nên tra() trả về 106. Tên chưa có thì get() trả về None. Mai kia bạn đổi ruột của DanhBa sang một bảng băm tự viết, các dòng them(), tra() ở dưới vẫn giữ nguyên.
Lộ trình 19 bài của nhóm
Thứ tự dưới đây đi từ cách đo, qua các cấu trúc tuyến tính, tới cây, đồ thị, tìm kiếm và sắp xếp. Mỗi bài dùng lại bài trước nó, nên đi đúng thứ tự thì dễ theo hơn.
Thứ tự | Bài | Học được gì |
|---|---|---|
1 | Đếm số bước, đọc O(1), O(n), O(n²), O(log n) | |
2 | Vào sau ra trước, lịch sử hoàn tác | |
3 | Vào trước ra trước, hàng chờ ở quầy | |
4 | Nút nối nút, thêm và xóa không dời phần tử | |
5 | Cách dict và set tra một khóa | |
6 | Nút có con trái, con phải, ba cách duyệt | |
7 | Chèn, tìm, xóa trên cây có thứ tự | |
8 | Phép xoay giữ cây cân bằng | |
9 | Duyệt đồ thị, bản đồ tuyến xe | |
10 | Dò từng phần tử | |
11 | Chia đôi dãy đã sắp xếp, module | |
12 | Bảng so sánh, ổn định, tại chỗ, Timsort | |
13 | Sắp xếp nổi bọt | Đổi chỗ hai phần tử kề nhau |
14 | Sắp xếp chọn | Chọn phần tử nhỏ nhất đưa lên đầu |
15 | Sắp xếp chèn | Chèn từng phần tử vào phần đã xếp |
16 | Sắp xếp trộn | Chia để trị, hai con trỏ |
17 | Sắp xếp nhanh | Chọn chốt rồi chia hai phía |
18 | Sắp xếp đếm | Đếm số lần xuất hiện thay cho so sánh |
19 | Sắp xếp theo cơ số | Xếp theo từng chữ số |
Bảy bài sắp xếp cuối có link từ bài thuật toán sắp xếp, bài mở cụm của chúng. Bài tập phỏng vấn như two sum hay kiểm tra dấu ngoặc nằm ở nhóm bài toán sau nhóm này và dùng lại đúng các cấu trúc trên.
Kiểm tra nhanh
Với
d = {"Ga Huế": ["01", "02"]},d.get("Thiên Mụ", [])trả về gì?[]None- Báo lỗi
KeyError
Với
theo_tram = {"Ga Huế": ["01", "02"]},theo_tram["Bến Ngự"]cho kết quả gì?[]None- Báo lỗi
KeyError
Những câu nào đúng về cấu trúc dữ liệu và giải thuật?
- Cùng một dữ liệu, đổi cách cất thì các bước tra cứu cũng đổi theo
- Giải thuật chỉ là một tên khác của hàm Python
- Một class có thể giấu cấu trúc bên trong, nơi dùng chỉ gọi phương thức
- Dict luôn tốt hơn list ở mọi việc
Trong khung bẫy danh bạ cất bằng list, sau khi thêm
("Ngọc", 106),tra("Ngọc")trả về số nào?- 106
- 103
- None
Bài tập
Đổi bản đồ tuyến xe sang dạng theo trạm
Bản đồ xe buýt cất theo tuyến: ban_do là dict từ mã tuyến sang list các trạm. Viết hàm doi_ban_do(ban_do) dựng dict mới từ tên trạm sang list các mã tuyến dừng ở trạm đó, để mỗi câu hỏi về một trạm chỉ cần một lần tra.
Mỗi mã tuyến chỉ có một lần trong list của một trạm, kể cả khi tuyến dừng ở trạm đó hai lần.
List mã tuyến của mỗi trạm xếp tăng dần.
Hàm không sửa
ban_do.
Ví dụ: doi_ban_do({"01": ["Ga Huế", "Đại Nội"], "05": ["Đại Nội"]}) trả về {"Ga Huế": ["01"], "Đại Nội": ["01", "05"]}.
Trả về: dict từ trạm sang mã tuyến, một dict mà mỗi giá trị là một list.
def doi_ban_do(ban_do):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Cấu trúc dữ liệu là cách cất dữ liệu, giải thuật là các bước có điểm dừng làm việc trên nó.
Đổi bản đồ từ theo tuyến sang theo trạm biến việc dò từng tuyến thành một lần tra dict.
Tra trạm có thể thiếu bằng
get(tram, []), ngoặc vuông với khóa không có báoKeyError.Danh bạ cất bằng list và dừng ở cặp khớp đầu tiên trả về mã cũ, dict thì ghi đè mã mới.
Một class gói dữ liệu vào thuộc tính và thao tác vào phương thức, nơi dùng không cần biết ruột bên trong.
Lộ trình đi từ Big O, ngăn xếp, hàng đợi, qua cây và đồ thị, tới tìm kiếm và sắp xếp.
Câu hỏi thường gặp
Cấu trúc dữ liệu và giải thuật là gì, nói ngắn gọn?
Cấu trúc dữ liệu là cách sắp xếp dữ liệu để các thao tác cần dùng được nhanh và đúng. Giải thuật là dãy bước rõ ràng biến dữ liệu vào thành kết quả. Hai thứ đi cùng nhau: chọn bảng băm thì tra khóa nhanh, chọn ngăn xếp thì hoàn tác tự nhiên.
Học cấu trúc dữ liệu bằng Python có thiệt gì so với C hay Java?
Python có sẵn list, dict, set và deque nên bạn ít khi phải tự viết chúng trong công việc. Tự viết lại trong bài học giúp bạn hiểu vì sao mỗi thao tác nhanh hay chậm, điều dùng được ở cả những ngôn ngữ khác. Phần quản lý bộ nhớ bằng con trỏ của C thì Python làm thay bạn.
Tài liệu cấu trúc dữ liệu và giải thuật nào nên đọc kèm?
Trang "Time complexity of operations on built-in types" trong tài liệu chính thức của Python (docs.python.org/3/builtins/time-complexity.html, xem ngày 15/11/2026) cho biết thao tác nào của list, dict, set tốn bao nhiêu bước. Mười chín bài của nhóm này đi theo đúng thứ tự trong bảng lộ trình, bắt đầu từ độ phức tạp Big O.
Cần giỏi toán mới học được giải thuật không?
Không cần. Phần lớn nhóm bài chỉ dùng phép cộng, phép nhân và việc đếm số lần một vòng lặp chạy. Ký hiệu như O(n²) chỉ là cách viết gọn câu "số bước tăng theo bình phương số phần tử". Phần chứng minh tính đúng thuộc giáo trình đại học.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.