10 cấu trúc dữ liệu trong Python [Explained With Examples]

Bạn có muốn thêm cấu trúc dữ liệu vào bộ công cụ phát triển của mình không? Hãy thực hiện những bước đầu tiên trong việc học cấu trúc dữ liệu Python ngay hôm nay.

Khi bạn học một ngôn ngữ lập trình mới, điều quan trọng là phải hiểu các kiểu dữ liệu cơ bản và cấu trúc dữ liệu tích hợp mà ngôn ngữ đó hỗ trợ. Trong hướng dẫn về cấu trúc dữ liệu Python này, chúng tôi sẽ đề cập đến các chủ đề sau:

• ưu điểm của cấu trúc dữ liệu
• Các cấu trúc dữ liệu tích hợp của Python như danh sách, bộ dữ liệu, từ điển và bộ sưu tập
• triển khai các kiểu dữ liệu trừu tượng như ngăn xếp và hàng đợi.

Hãy bắt đầu!

Tại sao cấu trúc dữ liệu lại hữu ích?

Trước khi đi vào các cấu trúc dữ liệu khác nhau, hãy xem việc sử dụng cấu trúc dữ liệu có thể hữu ích như thế nào:

• Xử lý dữ liệu hiệu quả: Việc chọn cấu trúc dữ liệu phù hợp giúp bạn xử lý dữ liệu hiệu quả hơn. Ví dụ: nếu bạn muốn lưu trữ một tập hợp các mục có cùng kiểu dữ liệu – với thời gian tra cứu liên tục và liên kết chặt chẽ – bạn có thể chọn một mảng.
• Quản lý bộ nhớ tốt hơn: Trong các dự án lớn hơn để lưu trữ cùng một dữ liệu, một cấu trúc dữ liệu có thể có hiệu quả bộ nhớ cao hơn cấu trúc dữ liệu khác. Ví dụ: trong Python, cả danh sách và bộ dữ liệu đều có thể được sử dụng để lưu trữ các tập hợp dữ liệu cùng loại hoặc khác loại. Tuy nhiên, nếu bạn biết mình không cần sửa đổi bộ sưu tập, bạn có thể chọn một bộ chiếm ít bộ nhớ hơn so với một danh sách.
• Mã có tổ chức hơn: Việc sử dụng cấu trúc dữ liệu phù hợp cho một chức năng cụ thể sẽ giúp mã của bạn có tổ chức hơn. Các lập trình viên khác đọc mã của bạn sẽ mong đợi bạn sử dụng các cấu trúc dữ liệu cụ thể tùy thuộc vào hành vi mong muốn. Ví dụ: nếu bạn cần ánh xạ khóa-giá trị với thời gian tra cứu và chèn cố định, bạn có thể lưu trữ dữ liệu trong từ điển.

Bức thư

Khi chúng ta cần tạo mảng động trong Python—từ các cuộc phỏng vấn mã hóa đến các trường hợp sử dụng phổ biến—danh sách là cấu trúc dữ liệu cơ bản.

Danh sách Python là các kiểu dữ liệu vùng chứa có thể thay đổi và linh hoạt, vì vậy bạn có thể thêm và xóa các mục khỏi danh sách tại chỗ – không cần tạo bản sao.

Khi sử dụng danh sách python:

• Lập chỉ mục vào một danh sách và truy cập một mục ở một chỉ mục cụ thể là một hoạt động liên tục.
• Việc thêm một mục vào cuối danh sách là một thao tác liên tục.
• Chèn một mục vào một chỉ mục cụ thể là một thao tác theo thời gian tuyến tính.

Có một tập hợp các phương pháp liệt kê giúp chúng ta thực hiện các tác vụ thông thường một cách hiệu quả. Đoạn mã sau đây cho biết cách thực hiện các thao tác này trên danh sách mẫu:

>>> nums = [5,4,3,2]

>>> nums.append(7)
>>> nums
[5, 4, 3, 2, 7]

>>> nums.pop()
7
>>> nums
[5, 4, 3, 2]

>>> nums.insert(0,9)
>>> nums
[9, 5, 4, 3, 2]

Danh sách Python cũng hỗ trợ cắt và kiểm tra tư cách thành viên bằng toán tử in :

>>> nums[1:4]
[5, 4, 3]

>>> 3 in nums
True

Cấu trúc dữ liệu danh sách không chỉ linh hoạt và đơn giản mà còn cho phép chúng ta lưu trữ các mục thuộc nhiều loại dữ liệu khác nhau. Python cũng có cấu trúc dữ liệu mảng chuyên dụng cho các phần tử lưu trữ dữ liệu cùng loại hiệu quả. Chúng ta sẽ tìm hiểu về điều này sau trong hướng dẫn này.

Ngắn

Trong Python, bộ dữ liệu là một cấu trúc dữ liệu tích hợp phổ biến khác. Chúng giống như các danh sách trong python ở chỗ chúng có thể được lập chỉ mục theo thời gian không đổi và được cắt lát. Nhưng chúng không thể thay đổi được nên bạn không thể sửa đổi chúng tại chỗ. Đoạn mã sau đây giải thích điều trên bằng một bộ dữ liệu ví dụ:

>>> nums = (5,4,3,2)

>>> nums[0]
5

>>> nums[0:2]
(5, 4)

>>> 5 in nums
True

>>> nums[0] = 7 # not a valid operation!
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Vì vậy, nếu bạn muốn tạo một bộ sưu tập bất biến và có thể xử lý nó một cách hiệu quả, bạn nên cân nhắc việc sử dụng bộ dữ liệu. Nếu bạn muốn bộ sưu tập có thể thay đổi được, thay vào đó hãy sử dụng danh sách.

📋 Tìm hiểu thêm về những điểm tương đồng và khác biệt giữa danh sách và bộ dữ liệu trong Python.

Những cái bàn

Mảng là cấu trúc dữ liệu ít được biết đến hơn trong Python. Chúng tương tự như danh sách python trong các hoạt động mà chúng hỗ trợ, chẳng hạn như lập chỉ mục theo thời gian không đổi và chèn một mục vào một chỉ mục cụ thể theo thời gian tuyến tính.

Tuy nhiên, điểm khác biệt chính giữa danh sách và mảng là mảng chứa các phần tử của một loại dữ liệu. Vì vậy, chúng có liên quan chặt chẽ và hiệu quả hơn về mặt trí nhớ.

Để tạo một mảng, chúng ta có thể sử dụng hàm tạo array() từ mô-đun mảng tích hợp sẵn. Hàm tạo array() lấy một chuỗi xác định kiểu dữ liệu của các phần tử và phần tử. Ở đây chúng ta tạo nums_f, một mảng các số dấu phẩy động:

>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])

Bạn có thể lập chỉ mục thành một mảng (giống như danh sách trong python):

>>> nums_f[0]
1.5

Mảng có thể thay đổi nên bạn có thể sửa đổi chúng:

>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])

Nhưng bạn không thể sửa đổi mục thành loại dữ liệu khác:

>>> nums_f[0]='zero'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str

Dây

Trong Python, chuỗi là bộ ký tự Unicode bất biến. Không giống như các ngôn ngữ lập trình như C, Python không có kiểu dữ liệu ký tự chuyên dụng. Vì vậy, một ký tự cũng là một chuỗi có độ dài bằng một.

Như đã đề cập, chuỗi là bất biến:

>>> str_1 = 'python'
>>> str_1[0] = 'c'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Chuỗi Python hỗ trợ cắt chuỗi và một tập hợp các phương thức định dạng chuỗi. Dưới đây là một số ví dụ:

>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
'PYTHON'
>>> str_1.swapcase()
'PYTHON'

⚠ Lưu ý rằng tất cả các thao tác trên đều trả về bản sao của chuỗi và không sửa đổi chuỗi gốc. Nếu bạn quan tâm, hãy xem hướng dẫn về chương trình Python để thực hiện các thao tác chuỗi.

bộ

Trong Python, tập hợp là tập hợp các mục duy nhất và có thể băm được. Bạn có thể thực hiện các thao tác tập hợp phổ biến như hợp, giao và hiệu:

>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}

>>> set_1.union(set_2)
{3, 4, 5, 6, 7}

>>> set_1.intersection(set_2)
{4, 7}

>>> set_1.difference(set_2)
{3, 5}

Các bộ có thể thay đổi theo mặc định, vì vậy bạn có thể thêm các mục mới và sửa đổi chúng:

>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}

📚 Đọc Gói Python: Hướng dẫn đầy đủ với các ví dụ về mã

Bộ đông lạnh

Nếu bạn muốn một bộ bất biến, bạn có thể sử dụng một bộ đông lạnh. Bạn có thể tạo một tập hợp cố định từ các tập hợp hiện có hoặc các tập hợp có thể lặp lại khác.

>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})

Vì set Frozen_1 là tập hợp đã được cố định nên chúng tôi sẽ gặp lỗi nếu cố gắng thêm các phần tử (hoặc sửa đổi chúng):

>>> frozenset_1.add(15)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

Từ điển

Từ điển của Python có chức năng tương tự như bản đồ băm. Từ điển được sử dụng để lưu trữ các cặp khóa-giá trị. Khóa từ điển phải có thể băm được. Điều này có nghĩa là giá trị băm của đối tượng không thay đổi.

Bạn có thể truy cập các giá trị bằng khóa, chèn các mục mới và xóa các mục hiện có trong thời gian không đổi. Có các phương pháp từ điển để thực hiện các thao tác này.

>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}

>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}

>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}

Đã đặt hàngDict

Mặc dù từ điển của Python cung cấp ánh xạ khóa-giá trị nhưng nó vốn là một cấu trúc dữ liệu không có thứ tự. Từ Python 3.7 thứ tự chèn các phần tử được giữ nguyên. Nhưng bạn có thể làm cho nó rõ ràng hơn bằng cách sử dụng OrderedDict từ mô-đun bộ sưu tập.

Như được hiển thị, OrderedDict giữ nguyên thứ tự của các phím:

>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])

Lệnh mặc định

Lỗi key khá phổ biến khi làm việc với từ điển Python. Bất cứ khi nào bạn cố gắng truy cập một khóa chưa được thêm vào từ điển, bạn sẽ gặp phải ngoại lệ KeyError.

Nhưng bằng cách sử dụng defaultdict từ mô-đun bộ sưu tập, bạn có thể xử lý trường hợp này một cách nguyên bản. Khi chúng tôi cố gắng truy cập một khóa không có trong từ điển, khóa đó sẽ được thêm và khởi tạo với các giá trị mặc định do nhà sản xuất mặc định chỉ định.

>>> from collections import defaultdict
>>> prices = defaultdict(int)
>>> prices['carrots']
0

Kệ sách

Ngăn xếp là cấu trúc dữ liệu vào trước ra trước (LIFO). Chúng ta có thể thực hiện các thao tác sau trên ngăn xếp:

• Thêm các mục vào đầu ngăn xếp: thao tác đẩy
• Xóa các mục khỏi đầu ngăn xếp: thao tác pop

Một ví dụ cho thấy cách hoạt động của các thao tác đẩy và bật ngăn xếp:

Cách triển khai ngăn xếp bằng danh sách

Trong python, chúng ta có thể triển khai cấu trúc dữ liệu ngăn xếp bằng danh sách python.

Thao tác trên StackEquivalent List OperationPush để xếp chồng topAppend vào cuối danh sách bằng phương thức add() Lấy phần trên cùng của stackXóa và trả về phần tử cuối cùng bằng phương thức pop()

Đoạn mã sau đây cho thấy cách chúng ta có thể bắt chước hành vi ngăn xếp bằng danh sách python:

>>> l_stk = []
>>> l_stk.append(4)
>>> l_stk.append(3)
>>> l_stk.append(7)
>>> l_stk.append(2)
>>> l_stk.append(9)
>>> l_stk
[4, 3, 7, 2, 9]
>>> l_stk.pop()
9

Cách triển khai ngăn xếp bằng Deque

Một phương pháp khác để triển khai ngăn xếp là sử dụng deque từ mô-đun bộ sưu tập. Deque là viết tắt của hàng đợi hai mặt và xử lý việc thêm và xóa các mục từ cả hai đầu.

Để mô phỏng một ngăn xếp, chúng ta có thể:

• nối vào cuối deque bằng cách sử dụngappend() và
• mục được thêm lần cuối trong cửa sổ bật lên bằng pop().

>>> from collections import deque
>>> stk = deque()
>>> stk.append(4)
>>> stk.append(3)
>>> stk.append(7)
>>> stk.append(2)
>>> stk.append(9)
>>> stk
deque([4, 3, 7, 2,9])
>>> stk.pop()
9

Hàng đợi

Hàng đợi là cấu trúc dữ liệu FIFO (nhập trước xuất trước). Các mục được thêm vào cuối hàng đợi và bị xóa khỏi đầu hàng đợi (đầu hàng đợi), như trong hình:

Chúng ta có thể triển khai cấu trúc dữ liệu hàng đợi bằng deque:

• thêm các mục vào cuối hàng đợi bằng cách thêm()
• sử dụng phương thức popleft() để xóa phần tử khỏi đầu hàng đợi

>>> from collections import deque
>>> q = deque()
>>> q.append(4)
>>> q.append(3)
>>> q.append(7)
>>> q.append(2)
>>> q.append(9)
>>> q.popleft()
4

cọc

Trong phần này, chúng ta sẽ thảo luận về ngăn xếp nhị phân. Chúng ta sẽ tập trung vào đống mìn.

Đống mỏ là một cây nhị phân hoàn chỉnh. Chúng ta hãy xem cây nhị phân đầy đủ có nghĩa là gì:

• Cây nhị phân là một cấu trúc dữ liệu dạng cây, trong đó mỗi nút có tối đa hai nút con, sao cho mỗi nút nhỏ hơn nút con của nó.
• Thuật ngữ hoàn chỉnh có nghĩa là cây đã được lấp đầy hoàn toàn, có lẽ ngoại trừ cấp độ cuối cùng. Nếu mức cuối cùng được lấp đầy một phần, nó sẽ được lấp đầy từ trái sang phải.

Bởi vì mỗi nút có tối đa hai nút con. Và nó cũng thỏa mãn tính chất nhỏ hơn con của nó, nghiệm là phần tử nhỏ nhất trong gò nhỏ nhất.

Đây là một ví dụ về đống mìn:

Trong Python, mô-đun heapq giúp chúng ta xây dựng và thao tác các vùng heap. Hãy nhập các hàm cần thiết từ heapq:

>>> from heapq import heapify, heappush, heappop

Nếu bạn có một danh sách hoặc có thể lặp lại khác, bạn có thể tạo một đống từ danh sách đó bằng cách gọi heapify():

>>> nums = [11,8,12,3,7,9,10]
>>> heapify(nums)

Bạn có thể lập chỉ mục mục đầu tiên để xem đó có phải là mục tối thiểu không:

>>> nums[0]
3

Bây giờ, nếu bạn đặt một mục vào heap, các nút sẽ được sắp xếp lại để đáp ứng thuộc tính min heap.

>>> heappush(nums,1)

Khi chúng tôi đặt 1 (1 < 3), chúng ta thấy số đó[0] trả lại 1hiện là phần tử tối thiểu (và nút gốc).

>>> nums[0]
1

Bạn có thể xóa các mục khỏi vùng khai thác bằng cách gọi hàm heappop(), như được hiển thị:

>>> while nums:
...     print(heappop(nums))
...

# Output
1
3
7
8
9
10
11
12

Số đống tối đa trong python

Bây giờ bạn đã biết về vùng heap tối thiểu, bạn có thể đoán cách chúng ta có thể triển khai vùng heap tối đa không?

Chà, chúng ta có thể chuyển đổi việc triển khai vùng heap tối thiểu thành vùng heap tối đa bằng cách nhân mỗi số với -1. Các số phủ định được xếp chồng lên nhau trong heap tối thiểu tương đương với các số ban đầu được xếp chồng lên nhau trong heap tối đa.

Trong quá trình triển khai python, chúng ta có thể nhân các phần tử với -1 khi thêm một mục vào heap bằng heappush():

>>> maxHeap = []
>>> heappush(maxHeap,-2)
>>> heappush(maxHeap,-5)
>>> heappush(maxHeap,-7)

Nút gốc – nhân với -1 – sẽ là phần tử tối đại.

>>> -1*maxHeap[0]
7

Khi xóa các mục khỏi heap, hãy sử dụng heappop() và nhân với -1để khôi phục giá trị ban đầu:

>>> while maxHeap:
...     print(-1*heappop(maxHeap))
...

# Output
7
5
2

Hàng đợi ưu tiên

Hãy kết thúc cuộc thảo luận bằng cách xem cấu trúc dữ liệu hàng đợi ưu tiên trong Python.

Chúng tôi biết: Trong hàng đợi, các mục sẽ bị xóa theo đúng thứ tự chúng vào hàng đợi. Nhưng hàng đợi ưu tiên xử lý các mục theo mức độ ưu tiên – rất hữu ích cho các ứng dụng như lập lịch trình. Vì vậy, bất cứ lúc nào mục có mức độ ưu tiên cao nhất sẽ được trả về.

Chúng ta có thể sử dụng các phím để xác định mức độ ưu tiên. Ở đây chúng ta sẽ sử dụng trọng số bằng số cho các phím.

Cách triển khai hàng đợi ưu tiên với Heapq

Đây là cách triển khai hàng đợi ưu tiên bằng danh sách heapq và python:

>>> from heapq import heappush,heappop
>>> pq = []
>>> heappush(pq,(2,'write'))
>>> heappush(pq,(1,'read'))
>>> heappush(pq,(3,'code'))
>>> while pq:
...     print(heappop(pq))
...

Khi xóa các mục, hàng đợi sẽ xử lý mục có mức ưu tiên cao nhất trước tiên (1″đọc”), sau đó (2″viết”) và sau đó (3″mã số”).

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Cách triển khai hàng đợi ưu tiên bằng PriorityQueue

Chúng ta cũng có thể sử dụng lớp PriorityQueue từ mô-đun Queue để triển khai hàng đợi ưu tiên. Điều này cũng sử dụng vùng heap trong nội bộ.

Đây là cách triển khai hàng đợi ưu tiên tương đương bằng cách sử dụng PriorityQueue:

>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1,'read'))
>>> pq.put((3,'code'))
>>> pq
<queue.PriorityQueue object at 0x00BDE730>
>>> while not pq.empty():
...     print(pq.get())
...

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Tóm lại

Trong hướng dẫn này, bạn đã tìm hiểu về các cấu trúc dữ liệu tích hợp khác nhau trong Python. Chúng tôi cũng đã đề cập đến các hoạt động khác nhau được hỗ trợ bởi các cấu trúc dữ liệu này – và các phương thức tích hợp sẵn có thể thực hiện điều tương tự.

Sau đó, chúng tôi đề cập đến các cấu trúc dữ liệu khác như ngăn xếp, hàng đợi và hàng đợi ưu tiên—và cách triển khai chúng trong Python bằng cách sử dụng chức năng của mô-đun bộ sưu tập.

Sau đó, hãy xem danh sách các dự án Python thân thiện với người mới bắt đầu.