Python đã được sử dụng trên toàn thế giới cho các lĩnh vực khác nhau như làm trang web, trí tuệ nhân tạo và nhiều hơn nữa. Nhưng để có thể làm được tất cả những điều này, dữ liệu đóng một vai trò rất quan trọng, điều đó có nghĩa là dữ liệu này cần được lưu trữ hiệu quả và việc truy cập nó phải kịp thời. Vậy làm thế nào để bạn đạt được điều này? Và đó chính là Cấu trúc dữ liệu. Chúng ta hãy tìm hiểu Cấu trúc dữ liệu trong Python thông qua các chủ đề sẽ được đề cập dưới đây.
Bạn đang xem: Cấu trúc dữ liệu và giải thuật python
Để tiện cho việc tìm hiểu ta sẽ đi qua các đề mục sau:
Cấu trúc dữ liệu là gì?Các kiểu cấu trúc dữ liệu trong Python
Cấu trúc dữ liệu tích hợp
Danh sách (List)Từ điển (Dictionary)Tuple
Sets
Cấu trúc dữ liệu do người dùng xác định
Arrays vs. List
Stack
Queue
Trees
Linked Lists
Graphs
Hash
Maps
< Ẩn >
Cấu trúc dữ liệu là gì?
Các kiểu cấu trúc dữ liệu trong Python
Cấu trúc dữ liệu tích hợp (Built-in Data Structures)
Lists
Dictionary
Tuple (các bộ dữ liệu)
Sets
User-Defined Data Structures (Cấu trúc dữ liệu do người dùng xác định)
Arrays vs. Lists
Stack
Queue
Tree
Danh sách liên kết (Linked List)
Đồ thị (Graph)
Hash
Maps
Tuyển gấp Backend Developer (C++, Python, Java) - 4 YOEHOT
Vi
Lik So
Ci
AL Med
IA
Fullstack Developer (Java
Script, Python)
Công ty Cổ phần Chứng khoán KIS Việt Nam
Fullstack Developer (HTML5, Python, Node
JS)
FPLand
Cấu trúc dữ liệu là gì?
Việc tổ chức, quản lý và lưu trữ dữ liệu rất quan trọng vì nó cho phép truy cập dễ dàng hơn và sửa đổi hiệu quả. Cấu trúc dữ liệu (Data Structure) cho phép bạn sắp xếp dữ liệu của mình theo cách cho phép bạn lưu trữ các bộ dữ liệu được thu thập, liên quan đến chúng và theo đó mà thực hiện các thao tác trên chúng.
Có thể bạn quan tâm: Top 10 tài liệu lập trình Python cơ bản và nâng cao
Các kiểu cấu trúc dữ liệu trong Python
Python có hỗ trợ ngầm cho Cấu trúc dữ liệu cho phép bạn lưu trữ và truy cập dữ liệu. Các cấu trúc này được gọi là List, Dictionary, Tuple và Set.
Python cho phép người dùng tạo Cấu trúc dữ liệu của riêng họ, cho phép toàn quyền kiểm soát chức năng. Các cấu trúc dữ liệu nổi bật nhất là Stack, Queue, Tree, Linked List, v.v. đồng thời cũng có sẵn trong các ngôn ngữ lập trình khác. Vì vậy, bây giờ bạn đã biết các loại có sẵn bao gồm những gì, vậy còn ngại gì việc dùng Cấu trúc dữ liệu và triển khai chúng bằng Python.
Cấu trúc dữ liệu tích hợp (Built-in Data Structures)
Về cấu trúc dữ liệu trong Python, các Cấu trúc dữ liệu này được tích hợp sẵn với Python giúp lập trình dễ dàng hơn và giúp các lập trình viên sử dụng chúng để có được các giải pháp nhanh hơn. Hãy cùng tìm hiểu chi tiết hơn từng phần trong cấu trúc dữ liệu.
Lists
Lists được sử dụng để lưu trữ dữ liệu của các loại dữ liệu khác nhau một cách tuần tự. Có các địa chỉ được gán cho mọi thành phần của danh sách, được gọi là Index. Giá trị chỉ mục bắt đầu từ 0 và tiếp tục cho đến khi phần tử cuối cùng được gọi là chỉ số dương. Ngoài ra còn có lập chỉ mục tiêu cực bắt đầu từ -1 cho phép bạn truy cập các phần tử từ cuối đến trước. Xem qua ví dụ bên dưới để hiểu rõ hơnTạo một Lists:Để tạo danh sách, bạn sử dụng dấu ngoặc vuông và thêm các yếu tố vào đó. Nếu bạn không vượt qua bất kỳ yếu tố nào trong dấu ngoặc vuông, bạn sẽ nhận được một danh sách trống làm đầu ra.
| 1 | my_list = <> #create empty list |
| 2 | print(my_list) |
| 3 | my_list = <1, 2, 3, 'example', 3.132> #creating list with data |
| 4 | print(my_list) |
Output: <><1, 2, 3, ‘example’, 3.132>
Thêm các yếu tố:
Thêm các yếu tố trong danh sách có thể đạt được bằng cách sử dụng các hàm append (), extend () và insert ().
Hàm append () thêm tất cả các phần tử được truyền vào nó dưới dạng một phần tử.Hàm extend () thêm từng phần tử vào danh sách.Hàm insert () thêm phần tử được truyền vào giá trị chỉ mục và tăng kích thước của danh sách.| 1 | my_list = <1, 2, 3> |
| 2 | print(my_list) |
| 3 | my_list.append(<555, 12>) #add as a single element |
| 4 | print(my_list) |
| 5 | my_list.extend(<234, 'more_example'>) #add as different elements |
| 6 | print(my_list) |
| 7 | my_list.insert(1, 'insert_example') #add element i |
| 8 | print(my_list) |
Output:<1, 2, 3><1, 2, 3, <555, 12>><1, 2, 3, <555, 12>, 234, ‘more_example’><1, ‘insert_example’, 2, 3, <555, 12>, 234, ‘more_example’>Xóa các yếu tố:
Để xóa các thành phần, hãy sử dụng từ khóa del được tích hợp sẵn trong Python nhưng điều này không trả lại bất cứ điều gì cho chúng tôi.Nếu bạn muốn phần tử quay lại, bạn sử dụng hàm pop () lấy giá trị chỉ mục.Để loại bỏ một phần tử theo giá trị của nó, bạn sử dụng hàm remove ().Ví dụ:
| 1 | my_list = <1, 2, 3, 'example', 3.132, 10, 30> |
| 2 | del my_list<5> #delete element at index 5 |
| 3 | print(my_list) |
| 4 | my_list.remove('example') #remove element with value |
| 5 | a = my_list.pop(1) #pop element from list |
| 6 | a = my_list.pop(1) #pop element from list |
| 7 | print('Popped Element: ', a, ' List remaining: ', my_list) |
| 8 | my_list.clear() #empty the list |
| 9 | print(my_list) |
Output:<1, 2, 3, ‘example’, 3.132, 30><1, 2, 3, 3.132, 30>Popped Element: 2 List remaining: <1, 3, 3.132, 30><>Yếu tố truy cập:Truy cập các phần tử giống như truy cập Chuỗi (Strings) trong Python. Bạn vượt qua các giá trị index và do đó có thể có được các giá trị khi cần thiết.
| 1 | my_list = <1, 2, 3, 'example', 3.132, 10, 30> |
| 2 | for element in my_list: #access elements one by one |
| 3 | print(element) |
| 4 | print(my_list) #access all elements |
| 5 | print(my_list<3>) #access index 3 element |
| 6 | print(my_list<0:2>) #access elements from 0 to 1 and exclude 2 |
| 7 | print(my_list<::-1>) #access elements in reverse |
Output:123example3.1321030<1, 2, 3, ‘example’, 3.132, 10, 30>example<1, 2><30, 10, 3.132, ‘example’, 3, 2, 1>Các chức năng khác:Bạn có một số chức năng khác có thể được sử dụng khi làm việc với cấu trúc dữ liệu trong Python này.
Hàm len () trả về cho chúng ta độ dài của list.Hàm index () tìm giá trị chỉ mục của giá trị được truyền vào nơi nó đã gặp lần đầu tiên.Hàm Count () tìm số đếm của giá trị được truyền cho nó.Các hàm được sắp xếp () và sort () thực hiện cùng một việc, đó là sắp xếp các giá trị của danh sách. Sắp xếp () có kiểu trả về trong khi sort () sửa đổi list ban đầu.| 1 | my_list = <1, 2, 3, 10, 30, 10> |
| 2 | print(len(my_list)) #find length of list |
| 3 | print(my_list.index(10)) #find index of element that occurs first |
| 4 | print(my_list.count(10)) #find count of the element |
| 5 | print(sorted(my_list)) #print sorted list but not change original |
| 6 | my_list.sort(reverse=True) #sort original list |
| 7 | print(my_list) |
Output:632<1, 2, 3, 10, 10, 30><30, 10, 10, 3, 2, 1>
Dictionary
Trong các cấu trúc dữ liệu trong Python, Dictionary được sử dụng để lưu trữ các cặp key-value. Để hiểu rõ hơn, hãy nghĩ đến một thư mục điện thoại nơi hàng trăm và hàng ngàn tên và số tương ứng của chúng đã được thêm vào. Bây giờ các giá trị không đổi ở đây là Tên và Số điện thoại được gọi là các phím. Và các tên và số điện thoại khác nhau là các giá trị đã được đưa vào các phím. Nếu bạn truy cập các giá trị của các phím, bạn sẽ nhận được tất cả tên và số điện thoại. Vì vậy, đó là những gì một cặp key-value. Và trong Python, cấu trúc này được lưu trữ bằng Dictionary. Để dễ hiểu hơn chúng ta cùng xét ví dụ.Tạo một từ điểnTừ điển có thể được tạo bằng cách sử dụng dấu ngoặc hoa hoặc sử dụng hàm dict (). Bạn cần thêm các cặp khóa-giá trị bất cứ khi nào bạn làm việc với từ điển.
| 1 | my_dict = {} #empty dictionary |
| 2 | print(my_dict) |
| 3 | my_dict = {1: 'Python', 2: 'Java'} #dictionary with elements |
| 4 | print(my_dict) |
Output:{}{1: ‘Python’, 2: ‘Java’}Thay đổi và thêm khóa, cặp giá trịĐể thay đổi các giá trị của từ điển, bạn cần phải làm điều đó bằng cách sử dụng các phím. Vì vậy, trước tiên bạn truy cập khóa và sau đó thay đổi giá trị cho phù hợp. Để thêm giá trị, bạn chỉ cần thêm một cặp key-value khác như hiển thị bên dưới:
| 1 | my_dict = {'First': 'Python', 'Second': 'Java'} |
| 2 | print(my_dict) |
| 3 | my_dict<'Second'> = 'C++' #changing element |
| 4 | print(my_dict) |
| 5 | my_dict<'Third'> = 'Ruby' #adding key-value pair |
| 6 | print(my_dict) |
Output:{‘First’: ‘Python’, ‘Second’: ‘Java’}{‘First’: ‘Python’, ‘Second’: ‘C++’}{‘First’: ‘Python’, ‘Second’: ‘C++’, ‘Third’: ‘Ruby’}
Xóa khóa, cặp giá trịĐể xóa các giá trị, bạn sử dụng hàm pop () trả về giá trị đã bị xóa.Để truy xuất cặp khóa-giá trị, bạn sử dụng hàm popitem () trả về một bộ khóa và giá trị.Để xóa toàn bộ Dictionary, bạn sử dụng hàm clear ().Output:Value: Ruby
Dictionary: {‘First’: ‘Python’, ‘Second’: ‘Java’}
Key, value pair: (‘Second’, ‘Java’)Dictionary {‘First’: ‘Python’}
{}Yếu tố truy cậpBạn chỉ có thể truy cập các yếu tố bằng cách sử dụng các phím. Bạn có thể sử dụng hàm get () hoặc chỉ truyền các giá trị chính và bạn sẽ truy xuất các giá trị.
| 1 | my_dict = {'First': 'Python', 'Second': 'Java'} |
| 2 | print(my_dict<'First'>) #access elements using keys |
| 3 | print(my_dict.get('Second')) |
Output:Python
JavaCác chức năng khácTrong chức năng của cấu trúc dữ liệu trong Python này, bạn có các hàm khác nhau trả về cho chúng ta các khóa hoặc các giá trị của cặp key-value tương ứng với các hàm khóa (), giá trị (), vật phẩm () tương ứng.
| 1 | my_dict = {'First': 'Python', 'Second': 'Java', 'Third': 'Ruby'} |
| 2 | print(my_dict.keys()) #get keys |
| 3 | print(my_dict.values()) #get values |
| 4 | print(my_dict.items()) #get key-value pairs |
| 5 | print(my_dict.get('First')) |
Output:dict_keys(<‘First’, ‘Second’, ‘Third’>)dict_values(<‘Python’, ‘Java’, ‘Ruby’>)dict_items(<(‘First’, ‘Python’), (‘Second’, ‘Java’), (‘Third’, ‘Ruby’)>)Python
Tuple (các bộ dữ liệu)
Dưới đây là so sánh 2 cấu trúc dữ liệu trong Python Tuple vs List
Để biết rõ hơn các phương thức trên hoạt động ra sao, mình dùng help() để xem tài liệu về chúng.
Bạn có thấy đối số đặt biệt / bên dưới chứ, hi vọng bạn biết chúng dùng để làm gì ^^(nếu chưa rõ mời bạn ghé đọc phần Function trong bài này nhé)
Một vài cách tiếp cận tương đương:
list.append(x) tương đương với a
list.extend(iterable) tương đương a
list.clear() tương đương với del a<:>
list.copy() tương đương với a<:>
list.pop(x) sẽ xoá một giá trị có index là x ra khỏi list và trả về giá trị đó
còn del(a
Những phương thức gọi có thể gây lỗi như list.remove(x), list.index(x) raise Value
Error nếu x không tồn tại.
Những phương thức như insert(), remove(), sort() trả về None(vì làm thay đổi các dữ liệu gốc)
Với list, ta có thể sử dụng nó như là một ngăn xếp(stack), thêm giá trị vào ngăn xếp với append(), lấy giá trị mới nhất được thêm vào ra ngoài ngăn xếp bằng pop().
Với list, cũng có thể dùng như một hàng đợi(queue), thêm giá trị vào hàng đợi với append(), lấy bạn đợi lâu nhất ra trước với popleft().
Ngoài ra, list comprehension là cách tạo list đơn ngắn gọn, ví dụ: numbers =
numbers = <>
for x in range(10):
number.append(x)
Tuples
Tuple cũng là một kiểu dữ kiệu chuỗi và các giá trị được bọc bên trong hai dấu ngoặc đơn ngăn cách bằng dấu phẩy, ví dụ: a = (‘hi’, ‘there’)Tuple tương tự như list, chỉ khác là tuple là kiểu dữ liệu immutable(không thay đổi được), còn list thì mutable(có thể thay đối).
Là kiểu dữ liệu immutable nhưng tuple có thể chứa các dữ liệu mutable được, ví dụ: b = (<1,2>, <3,4>)
Tuple có khả năng packing(tự nối lại được), như sau: a = ‘hi’, ‘there‘ hay c = ‘hi’
(chú ý dấu phẩy ở cuối trong trường hợp tuple chỉ chứa một phần tử con)
Và ngược lại, nó cũng có khả năng unpacking(tự tách ra được)
tuple là kiểu dữ liệu không thay đổi được nên nó chỉ có phương thức count() và index()
Sets
Set là bộ sưu tập không theo thứ tự các phần tử không trùng nhau, được bọc bởi hai dấu ngoặc nhọn {} hoặc khởi tạo bằng set().
Set có hỗ trợ các phương thức của tổ hợp như là phép toán giao, phép toán hợp, phép đối xứng, phép loại trừ.
Set có hỗ trợ set comprehensions.
Lưu ý không khởi tạo set rỗng bằng {} được, phải dùng set(), vì {} thể hiện cho kiểu dữ liệu dict
Dictionary(từ điển)
Nếu như list, tuple, set là các kiểu dữ liệu có thứ tự là các chữ số thì dict là kiểu dữ liệu có thứ tự là các từ khoá, và từ khoá là kiểu dữ liệu immutable như strings, numbers, tuples(không chứa giá trị mutable).
Có thể hiểu đơn giản dictionary là một bộ sưu tập của các giá trị key: value, với điều kiện key là không trùng nhau.
Xem thêm: Bộ máy tạo kiểu tóc dyson airwrap complete, dyson airwrap complete
Dict khai báo với dict() hoặc {}, ví dụ: dict(name=’Thanh’) hay {‘name’: ‘Thanh’}
Kỹ thuật lặp qua các loại dữ liệu có trình tự
Ta thường làm việc với các loại dữ liệu có trình tự bằng cách duyệt qua tất cả các phần tử của nó với for và kết hợp:
→ dùng .items() để lặp qua key, value của một dictionary
→ dùng enumerate(<‘a’, ‘b’, ‘c’>) để lặp qua chỉ số index và giá trị của chỉ số đó trong một list
→ dùng zip() có thể lặp qua nhiều loại dữ liệu trình tự, ví dụ: zip(<1, 2, 3>, <‘a’, ‘b’, ‘c’>)
→ dùng reversed() có thể lặp theo thứ tự ngược lại
→ dùng sorted() có thể tạo list mới theo thứ tự mà không làm thay đổi mảng ban đầu.
Các dạng so sánh
Trong các câu lệnh điều kiện, thường đi cùng với các dạng so sánh: