Các thuật ngữ và định nghĩa cơ bản

3.1 Thao tác trên dữ liệu: chèn, xóa, tìm kiếm

Chèn (Insert):

Thao tác thêm phần tử mới vào cấu trúc dữ liệu. Chèn có thể xảy ra ở đầu, cuối hoặc tại một vị trí tùy ý trong cấu trúc dữ liệu.

Xóa (Delete):

Thao tác loại bỏ phần tử khỏi cấu trúc dữ liệu. Xóa có thể được thực hiện theo giá trị phần tử, theo chỉ mục hoặc vị trí của phần tử trong cấu trúc dữ liệu.

Tìm kiếm (Search):

Thao tác tìm phần tử trong cấu trúc dữ liệu. Tìm kiếm có thể được thực hiện theo giá trị hoặc theo các tiêu chí khác.

Ví dụ về các thao tác:

• Mảng: Chèn và xóa yêu cầu di chuyển các phần tử, có thể tốn nhiều thời gian — O(n).
• Danh sách liên kết: Chèn và xóa có thể xảy ra ở khoảng thời gian O(1), nếu biết vị trí nút.
• Bảng băm: Tìm kiếm, chèn và xóa thường được thực hiện trong thời gian trung bình O(1).
• Cây: Các thao tác tìm kiếm, chèn và xóa có thể được thực hiện trong O(log n) trong cây cân bằng.

3.2 Khái niệm cơ bản: mảng, danh sách, ngăn xếp, hàng đợi

Mảng

Mảng — là một dãy các phần tử cùng loại mà có thể truy cập bằng chỉ số.

Độ phức tạp của các thao tác: Truy cập theo chỉ số — O(1), chèn và xóa — O(n).

Ví dụ: Tạo mảng, chỉnh sửa phần tử và xuất kết quả

# Tạo mảng số
arr = [1, 2, 3, 4, 5]

# Chỉnh sửa phần tử có chỉ số 2 (phần tử thứ ba, vì chỉ số bắt đầu từ 0)
arr[2] = 10

# Xuất mảng đã chỉnh sửa
print(arr)  # Xuất: [1, 2, 10, 4, 5]

# Thêm phần tử mới vào cuối mảng
arr.append(6)
print(arr)  # Xuất: [1, 2, 10, 4, 5, 6]

# Xóa phần tử theo chỉ số
del arr[1]
print(arr)  # Xuất: [1, 10, 4, 5, 6]

Danh sách

Danh sách — là một tập hợp các phần tử, trong đó mỗi phần tử chứa một tham chiếu đến phần tử tiếp theo (danh sách liên kết đơn) hoặc đến phần tử tiếp theo và trước đó (danh sách liên kết kép).

Độ phức tạp của các thao tác: Chèn và xóa — O(1) khi biết vị trí, tìm kiếm — O(n).

Ví dụ: Tạo một danh sách liên kết đơn giản và duyệt qua nó

# Định nghĩa cấu trúc nút danh sách
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Tạo danh sách liên kết đơn
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")

# Kết nối các nút
node1.next = node2
node2.next = node3

# Thiết lập đầu danh sách
list_head = node1

# Duyệt qua danh sách và xuất dữ liệu
current = list_head
while current:
    print(current.data)
    current = current.next

# Xuất:
# 101
# 102
# 103

Ngăn xếp (Stack)

Ngăn xếp — là một tập hợp các phần tử với nguyên tắc LIFO (Last In, First Out): vào sau ra trước.

Độ phức tạp của các thao tác: Chèn (push) và xóa (pop) — O(1).

Ví dụ: Triển khai và sử dụng ngăn xếp để kiểm tra độ cân bằng của dấu ngoặc

def is_balanced(expression):
    stack = []
    opening = "({["
    closing = ")}]"
    pairs = {")": "(", "}": "{", "]": "["}
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or stack.pop() != pairs[char]:
                return False
    
    return len(stack) == 0

# Kiểm tra các biểu thức khác nhau
print(is_balanced("({[]})"))  # Xuất: True
print(is_balanced("([)]"))    # Xuất: False
print(is_balanced("(("))      # Xuất: False

Hàng đợi (Queue)

Hàng đợi — là một tập hợp các phần tử với nguyên tắc FIFO (First In, First Out): vào trước ra trước.

Độ phức tạp của các thao tác: Chèn (enqueue) và xóa (dequeue) — O(1).

Ví dụ: Triển khai và sử dụng hàng đợi để mô phỏng xử lý tác vụ

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"Nhiệm vụ '{task}' đã được thêm vào hàng đợi")

    def process_task(self):
        if self.queue:
            task = self.queue.popleft()
            print(f"Xử lý nhiệm vụ: '{task}'")
        else:
            print("Hàng đợi trống")

    def display_queue(self):
        print("Hàng đợi nhiệm vụ hiện tại:", list(self.queue))

# Tạo và sử dụng hàng đợi nhiệm vụ
task_queue = TaskQueue()

task_queue.add_task("Gửi email")
task_queue.add_task("Cập nhật cơ sở dữ liệu")
task_queue.add_task("Tạo báo cáo")

task_queue.display_queue()

task_queue.process_task()
task_queue.process_task()

task_queue.display_queue()

# Xuất:
# Nhiệm vụ 'Gửi email' đã được thêm vào hàng đợi
# Nhiệm vụ 'Cập nhật cơ sở dữ liệu' đã được thêm vào hàng đợi
# Nhiệm vụ 'Tạo báo cáo' đã được thêm vào hàng đợi
# Hàng đợi nhiệm vụ hiện tại: ['Gửi email', 'Cập nhật cơ sở dữ liệu', 'Tạo báo cáo']
# Xử lý nhiệm vụ: 'Gửi email'
# Xử lý nhiệm vụ: 'Cập nhật cơ sở dữ liệu'
# Hàng đợi nhiệm vụ hiện tại: ['Tạo báo cáo']

3.3 Sự khác biệt giữa các loại cấu trúc dữ liệu

Dưới đây là những điểm khác biệt chính giữa các loại cấu trúc dữ liệu:

Mảng:

• Truy cập: Truy cập nhanh theo chỉ số — O(1).
• Thay đổi kích thước: Kích thước cố định, việc tăng kích thước yêu cầu sao chép tất cả các phần tử — O(n).
• Phù hợp cho: Truy cập ngẫu nhiên các phần tử, khi kích thước dữ liệu đã được biết trước.

Danh sách liên kết:

• Truy cập: Truy cập chậm theo chỉ số — O(n).
• Thay đổi kích thước: Thay đổi kích thước dễ dàng, thêm và xóa mất O(1).
• Phù hợp cho: Thêm và xóa các phần tử thường xuyên.

Ngăn xếp:

• Nguyên tắc hoạt động: LIFO.
• Thao tác: Chèn và xóa chỉ ở một đầu — O(1).
• Phù hợp cho: Thứ tự thực hiện nhiệm vụ ngược, quản lý các lời gọi hàm.

Hàng đợi:

• Nguyên tắc hoạt động: FIFO.
• Thao tác: Chèn và xóa ở các đầu khác nhau — O(1).
• Phù hợp cho: Quản lý nhiệm vụ theo thứ tự xuất hiện.

3.4 Ứng dụng của các cấu trúc dữ liệu khác nhau

Ví dụ ứng dụng của các cấu trúc dữ liệu khác nhau trong thực tế:

Mảng

Lưu trữ dữ liệu có độ dài cố định, như các ngày trong tuần hoặc các tháng trong năm.

Ví dụ: Sử dụng mảng để làm việc với các ngày trong tuần

# Tạo mảng với các ngày trong tuần
days = ["Thứ hai", "Thứ ba", "Thứ tư", "Thứ năm", "Thứ sáu", "Thứ bảy", "Chủ nhật"]

# Lấy ngày trong tuần theo chỉ số (ví dụ, ngày thứ ba)
print(days[2])  # Xuất: Thứ tư

# Thay đổi tên ngày
days[0] = "Thứ hai (đầu tuần)"
print(days[0])  # Xuất: Thứ hai (đầu tuần)

# Duyệt qua tất cả các ngày trong tuần
for day in days:
    print(day)

# Xuất:
# Thứ hai (đầu tuần)
# Thứ ba
# Thứ tư
# Thứ năm
# Thứ sáu
# Thứ bảy
# Chủ nhật

Danh sách liên kết

Triển khai các bộ sưu tập động, nơi các phần tử có thể thêm hoặc xóa từ giữa bộ sưu tập.

Ví dụ: Triển khai và sử dụng danh sách liên kết để lưu trữ danh sách việc cần làm

class TodoItem:
    def __init__(self, task):
        self.task = task
        self.next = None

class TodoList:
    def __init__(self):
        self.head = None

    def add_task(self, task):
        new_item = TodoItem(task)
        if not self.head:
            self.head = new_item
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_item

    def display_tasks(self):
        current = self.head
        if not current:
            print("Danh sách việc cần làm trống")
        else:
            while current:
                print(f"- {current.task}")
                current = current.next

# Tạo và sử dụng danh sách việc cần làm
todo = TodoList()
todo.add_task("Mua hàng hóa")
todo.add_task("Gọi điện cho mẹ")
todo.add_task("Chuẩn bị bài thuyết trình")

print("Danh sách việc cần làm của tôi:")
todo.display_tasks()

# Xuất:
# Danh sách việc cần làm của tôi:
# - Mua hàng hóa
# - Gọi điện cho mẹ
# - Chuẩn bị bài thuyết trình

Ngăn xếp

Thứ tự thực hiện nhiệm vụ ngược, ví dụ như xử lý các lời gọi hàm trong đệ quy, hoàn tác (undo) hành động.

Ví dụ: Sử dụng ngăn xếp để đảo ngược chuỗi

def reverse_string(s):
    stack = []
    # Đẩy từng ký tự của chuỗi vào ngăn xếp
    for char in s:
        stack.append(char)
    
    reversed_s = ''
    # Lấy các ký tự từ ngăn xếp, tạo thành chuỗi đảo ngược
    while stack:
        reversed_s += stack.pop()
    
    return reversed_s

# Ví dụ sử dụng
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Chuỗi gốc: {original}")
print(f"Chuỗi đảo ngược: {reversed_str}")

# Xuất:
# Chuỗi gốc: Hello, World!
# Chuỗi đảo ngược: !dlroW ,olleH

Hàng đợi

Quản lý các nhiệm vụ theo thứ tự xuất hiện, ví dụ, các nhiệm vụ tại máy in, hàng đợi trong dịch vụ khách hàng.

Ví dụ: Mô phỏng hàng đợi in tài liệu

from collections import deque

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_document(self, document):
        self.queue.append(document)
        print(f"Tài liệu '{document}' đã được thêm vào hàng đợi in")

    def print_document(self):
        if self.queue:
            document = self.queue.popleft()
            print(f"In tài liệu: '{document}'")
        else:
            print("Hàng đợi in trống")

    def display_queue(self):
        print("Hàng đợi in hiện tại:", list(self.queue))

# Tạo và sử dụng hàng đợi in
printer = PrinterQueue()
printer.add_document("Báo cáo")
printer.add_document("Thuyết trình")
printer.add_document("Hợp đồng")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()

# Xuất:
# Tài liệu 'Báo cáo' đã được thêm vào hàng đợi in
# Tài liệu 'Thuyết trình' đã được thêm vào hàng đợi in
# Tài liệu 'Hợp đồng' đã được thêm vào hàng đợi in
# Hàng đợi in hiện tại: ['Báo cáo', 'Thuyết trình', 'Hợp đồng']
# In tài liệu: 'Báo cáo'
# In tài liệu: 'Thuyết trình'
# Hàng đợi in hiện tại: ['Hợp đồng']

Trong ví dụ này, chúng ta đã tạo một mô phỏng đơn giản của hàng đợi in. Tài liệu được thêm vào cuối hàng đợi và được in theo thứ tự xuất hiện, điều này minh họa nguyên tắc FIFO (First In, First Out).