Bỏ qua đến nội dung chính
Mục lục

Cấu trúc dữ liệu và giải thuật là gì? Học bằng Python

AIDev Team · duyệt: Nguyễn Việt Chung

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

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 đó.

python
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.

python
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.

python
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 None

Danh 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

Độ phức tạp Big O

Đếm số bước, đọc O(1), O(n), O(n²), O(log n)

2

Ngăn xếp

Vào sau ra trước, lịch sử hoàn tác

3

Hàng đợi

Vào trước ra trước, hàng chờ ở quầy

4

Danh sách liên kết

Nút nối nút, thêm và xóa không dời phần tử

5

Bảng băm

Cách dict và set tra một khóa

6

Cây nhị phân

Nút có con trái, con phải, ba cách duyệt

7

Cây nhị phân tìm kiếm

Chèn, tìm, xóa trên cây có thứ tự

8

Cây AVL

Phép xoay giữ cây cân bằng

9

BFS và DFS

Duyệt đồ thị, bản đồ tuyến xe

10

Tìm kiếm tuyến tính

Dò từng phần tử

11

Tìm kiếm nhị phân

Chia đôi dãy đã sắp xếp, module bisect

12

Thuật toán sắp xếp

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

  1. Với d = {"Ga Huế": ["01", "02"]}, d.get("Thiên Mụ", []) trả về gì?

    • []
    • None
    • Báo lỗi KeyError
  2. Với theo_tram = {"Ga Huế": ["01", "02"]}, theo_tram["Bến Ngự"] cho kết quả gì?

    • []
    • None
    • Báo lỗi KeyError
  3. 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
  4. 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
Đúng hết lần đầu +15 XP

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.

python
def doi_ban_do(ban_do):
    pass  # Viết thân hàm thay cho dòng này

Tó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áo KeyError.

  • 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ủ đề

cấu trúc dữ liệu và giải thuật

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập