Линейная структура данных

В этой главе мы представим один из самых базовых и часто используемых типов структур данных —линейную структуру данных。

Линейная структура данныхТочно так же, как ряд людей, выстроившихся в линию:

  • У каждого человека (элемента) есть четкое отношение «до и после»
  • За исключением первого и последнего, у каждого человека есть один предшественник и один последователь
  • Элементы данных имеют линейное отношение «один к одному»

Представьте, что вы стоите в очереди за кофе или расставляете книги на полке.

В этих сценариях есть общая черта: элементы расположены один за другим, образуя линию.

В информатике такая упорядоченная коллекция данных называется линейной структурой данных.

Характерная особенность линейной структуры данных: за исключением первого и последнего элементов, каждый элемент имеет ровно одногопредшественникаи одногопоследователя。

Распространённые линейные структуры данных:

  1. массив: как ряд пронумерованных шкафчиков, каждый шкафчик имеет фиксированное положение
  2. Связный список: как цепочка людей, держащихся за руки, каждый человек помнит только людей впереди и позади
  3. Стек:Как стопка тарелок, предметы можно брать и класть только сверху
  4. ОчередьКак очередь за билетами, кто первым пришёл, того первым обслуживают

На рисунке ниже показана классификация линейных структур данных. Каждая структура имеет свои конкретные сценарии применения и характеристики производительности:

На рисунке ниже показан базовый процесс работы стека, который следует принципу LIFO (последним пришёл — первым вышел):

Массив

Статический массив

Особенности Описание Временная сложность
Доступ к элементам Прямой доступ по индексу O(1)
Вставка элемента Нужно сдвинуть последующие элементы O(n)
Удаление элемента Нужно сдвинуть последующие элементы O(n)
Выделение памяти Фиксированный размер, память выделена заранее O(1)

Динамический массив

Особенности Описание Временная сложность
Доступ к элементам Прямой доступ по индексу O(1)
Вставка элемента Может потребоваться изменение размера и копирование В среднем O(1), в худшем случае O(n)
Удаление элемента Нужно сдвинуть последующие элементы O(n)
Выделение памяти Автоматическое изменение размера O(n) (при изменении размера)

Связный список

Односвязный список

Действие Описание Временная сложность
Доступ к элементам Нужно пройти от начала O(n)
Вставка в начало Прямая вставка O(1)
Вставка в хвост Нужно пройти до хвоста O(n)
Вставка в середину Сначала нужно найти позицию O(n)
Удаление элемента Сначала нужно найти позицию O(n)

Двусвязный список

Действие Описание Временная сложность
Доступ к элементам Нужно пройти от головы или хвоста O(n)
Вставка в начало Прямая вставка O(1)
Вставка в хвост Прямая вставка (если есть указатель на хвост) O(1)
Вставка в середину Сначала нужно найти позицию O(n)
Удаление элемента Сначала нужно найти позицию O(n)

Стек

Действие Описание Временная сложность
push Добавить элемент на вершину стека O(1)
pop Удалить верхний элемент стека O(1)
peek(просмотр) Просмотреть верхний элемент стека O(1)
isEmpty(проверка на пустоту) Проверить, пуст ли стек O(1)

Очередь

Действие Описание Временная сложность
enqueue Добавить элемент в хвост очереди O(1)
dequeue Удалить головной элемент очереди O(1)
front (просмотр начала очереди) Просмотреть головной элемент очереди O(1)
isEmpty(проверка на пустоту) Проверить, пуста ли очередь O(1)

Диаграмма сравнения линейных структур данных


Массив: фиксированный многоквартирный дом для данных

Массивы — это простейшая и наиболее понятная линейная структура данных.

Мы можем представить его как зданиеМногоквартирный дом с фиксированным числом этажей。

Основные понятия и характеристики

  • Непрерывное хранениеМассив занимает непрерывный блок в памятиНепрерывныйПространство похоже на комнаты в многоквартирном доме, расположенные вплотную друг к другу.
  • Фиксированный размер: Вместимость (длина) массива должна быть определена при создании и обычно не может быть изменена после этого, так же как число комнат в многоквартирном доме фиксировано после его постройки.
  • Доступ по индексу: Каждый элемент (комната) имеет уникальный номер, называемыйиндексомВ большинстве языков программирования индексация начинается с0Начиная с. Вы можете напрямую и быстро обращаться к любому элементу по его индексу, с временной сложностьюO(1)。

Основные операции и примеры кода

Давайте продемонстрируем массивы на Python (в Python мы обычно используемlistдля имитации, но учтите, что в Pythonlistкоторый является динамическим) основные операции.

Пример

# 1. Создание массива
apartment_building = ['Комната 101 - Чжан Сань', 'Комната 102 - Ли Сы', 'Комната 103 - Ван У', 'Комната 104 - свободна', 'Комната 105 - свободна']
print("Жильцы многоквартирного дома:", apartment_building)

# 2. Доступ к элементам (по индексу)
# Доступ к комнате 102
tenant = apartment_building[1] # Индекс начинается с 0, поэтому 1 соответствует второму элементу
print(f"Жилец комнаты 102: {tenant}")

# 3. Обновление элементов
# Новый жилец Чжао Лю заселился в комнату 104
apartment_building[3] = 'Комната 104 - Чжао Лю'
print("После заселения Чжао Лю:", apartment_building)

# 4. Вставка элементов (добавление в конец относительно эффективно, имитируя "расширение")
# Предположим, что нам разрешено добавить комнату 106 в конец
apartment_building.append('Комната 106 - Сунь Ци')
print("После добавления комнаты 106:", apartment_building)

# 5. Удаление элементов
# Ван У съехал из комнаты 103
# Способ 1: пометить как свободную (логическое удаление)
# apartment_building[2] = 'Комната 103 - свободна'

# Способ 2: удалить элемент; последующие элементы нужно сдвинуть вперёд (физическое удаление, относительно неэффективно)
removed_tenant = apartment_building.pop(2) # Удалить элемент с индексом 2
print(f"{removed_tenant} съехал.")
print("После того как Ван У съехал:", apartment_building)

Вывод:

寓楼住户情况: ['101室-张三', '102室-李四', '103室-王五', '104室-空置', '105室-空置']
102室的住户是:102室-李四
赵六入住后: ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置']
加盖106室后: ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置', '106室-孙七']
103室-王五 已搬走。
王五搬走后: ['101室-张三', '102室-李四', '104室-赵六', '105室-空置', '106室-孙七']

Преимущества и недостатки

Преимущества Недостатки
Быстрый произвольный доступ: Любой элемент можно получить за постоянное время по его индексу. Фиксированный размер: После создания статического массива его вместимость трудно изменить.
Высокая эффективность использования памяти: Непрерывное хранение, не требуется дополнительное пространство для хранения связей между элементами. Высокая стоимость вставки/удаления: Вставка или удаление элементов в середине требует сдвига многих последующих элементов для сохранения непрерывности.

Связный список: поезд-кладоискатель для данных

Когда фиксированный размер массивов и неэффективность вставки/удаления становятся проблемой, на сцену выходят связные списки. Связный список похож на поездПоезд, каждый вагон (узел) перевозит груз (данные) и соединён со следующим вагоном через сцепку (указатель).

Основные понятия и типы

Каждый узел связного спискаузелСодержит как минимум две части:

  1. Поле данныхХранит фактическое значение данных.
  2. Поле указателя: хранит адрес следующего узла в памяти.

На рисунке выше показана структураодносвязного списка. Указатель head указывает на первый узел, и у каждого узлаNextуказатель указывает на следующий узел, а у последнего узлаNextУказывает наNULLОбозначает конец связного списка.

Основные типы связных списков:

  • Односвязный списокУзел указывает только на следующий узел.
  • Двусвязный список: Узлы указывают как на предыдущий, так и на следующий узел, что позволяет выполнять двунаправленный обход.
  • Циклический связный список: Хвостовой узел указывает на головной узел, образуя кольцо.

Основные операции и примеры кода

Давайте реализуем простой односвязный список.

Пример

class ListNode:
    """Определяет класс узла связного списка"""
    def __init__(self, data):
        self.data = data  # Поле данных
        self.next = None  # Поле указателя, изначально указывает на null

class LinkedList:
    """Определяет класс односвязного списка"""
    def __init__(self):
        self.head = None  # Указатель на голову связного списка

    def append(self, data):
        """Добавляет узел в конец связного списка"""
        new_node = ListNode(data)
        if not self.head:  # Если связный список пуст, новый узел становится головным узлом
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:  # Пройти до последнего узла
            last_node = last_node.next
        last_node.next = new_node  # Присоединить новый узел в конец

    def prepend(self, data):
        """Добавить узел в начало связного списка"""
        new_node = ListNode(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, key):
        """Удалить первый узел со значением key"""
        current_node = self.head

        # Если удаляемый узел является головным
        if current_node and current_node.data == key:
            self.head = current_node.next
            current_node = None
            return

        prev_node = None
        # Обход для поиска удаляемого узла
        while current_node and current_node.data != key:
            prev_node = current_node
            current_node = current_node.next

        if current_node is None:  # Не найдено
            return

        # После обнаружения обходим узел, чтобы соединить
        prev_node.next = current_node.next
        current_node = None

    def print_list(self):
        """Вывести все элементы связного списка"""
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("NULL")

# Проверка связного списка
print("=== Демонстрация операций односвязного списка ===")
train = LinkedList()
train.append("Вагон 1 - Уголь")
train.append("Вагон 2 - Древесина")
train.prepend("Локомотив")  # Добавить в начало
train.append("Вагон 3 - Сталь")
print("Начальный поезд:")
train.print_list()  # Вывод: Локомотив -> Вагон 1 - Уголь -> Вагон 2 - Древесина -> Вагон 3 - Сталь -> NULL

train.delete("Вагон 2 - Древесина")
print("После разгрузки древесины:")
train.print_list()  # Вывод: locomotive -> carriage1-coal -> carriage3-steel -> NULL

Вывод:

=== 单向链表操作演示 ===
初始列车:
车头 -> 车厢1-煤炭 -> 车厢2-木材 -> 车厢3-钢材 -> NULL
卸下木材后:
车头 -> 车厢1-煤炭 -> 车厢3-钢材 -> NULL

Преимущества и недостатки

Преимущества Недостатки
Динамический размер: Не нужно заранее выделять фиксированное пространство; он может гибко увеличиваться и уменьшаться. Накладные расходы памяти: Каждый узел требует дополнительного места для хранения указателя.
Эффективная вставка/удаление: Когда позиция узла известна, нужно только изменить указатели, не перемещая множество элементов. Последовательный доступ: В отличие от массивов, элементы нельзя получить напрямую по индексу; нужно проходить от головы.
Неудобный для кэша: Узлы разбросаны в памяти, что не способствует предварительной выборке в кэш CPU.

Стек: стопка тарелок для данных

Стек — этоLIFO (последним пришёл — первым вышел)структура данных, как стопка тарелок в ресторане: вы всегда берёте верхнюю (последнюю положенную).

Основные понятия и операции

Стек допускает операции только на одном конце (называемомвершиной стека) для вставки (Push) и удаления (Pop) операции. Другой конец называетсядном стека。

Основные операции:

  • push(data)Поместить данные на вершину стека.
  • pop()Извлечь и вернуть верхний элемент стека.
  • peek() / top()Просмотреть верхний элемент стека, не извлекая его.
  • is_empty()Проверить, пуст ли стек.

Сценарии применения и примеры кода

Стеки чрезвычайно широко используются в информатике, например, стек вызовов функций, навигация вперёд/назад в браузере, вычисление выражений, проверка соответствия скобок и т. д.

Пример

class Stack:
    """Использовать список для реализации стека"""
    def __init__(self):
        self.items = []

    def push(self, item):
        """Поместить"""
        self.items.append(item)  # Использовать конец списка как вершину стека

    def pop(self):
        """Извлечь; вернуть None, если стек пуст"""
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        """Посмотреть верхний элемент"""
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        """Проверить, пуст ли стек"""
        return len(self.items) == 0

    def size(self):
        """Вернуть размер стека"""
        return len(self.items)

# Пример применения: проверка соответствия скобок
def is_balanced_parentheses(expression):
    """
Проверить, совпадают ли скобки в выражении
Например: (()) сбалансировано, (() несбалансировано
    """

    stack = Stack()
    # Сопоставление пар скобок
    matching_bracket = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':  # Если это левая скобка, поместить в стек
            stack.push(char)
        elif char in ')]}':  # Если это правая скобка
            if stack.is_empty():
                return False  # Стек пуст, поэтому слишком много закрывающих скобок
            top_char = stack.pop()
            if matching_bracket[char] != top_char:  # Проверить, совпадают ли они
                return False
    # После цикла стек должен быть пустым
    return stack.is_empty()

# Тест стека и сопоставления скобок
print("\n=== Демонстрация стека и сопоставления скобок ===")
plate_stack = Stack()
plate_stack.push("Тарелка 1")
plate_stack.push("Тарелка 2")
plate_stack.push("Тарелка 3")
print(f"Достаньте верхнюю тарелку: {plate_stack.pop()}")  # Вывод: Тарелка 3
print(f"Теперь верхняя тарелка: {plate_stack.peek()}")  # Вывод: Тарелка 2

# Проверка соответствия скобок
test_cases = ["((1+2)*3)", "({[ ]})", "((())", ")( )"]
for test in test_cases:
    result = сбалансированы if is_balanced_parentheses(test) else не сбалансированы
    print(fСкобки в выражении '{test}' {result}.)

Вывод:

=== 栈与括号匹配演示 ===
取出最上面的盘子: 盘子3
现在最上面的盘子是: 盘子2
表达式 '((1+2)*3)' 的括号是 平衡 的。
表达式 '({[ ]})' 的括号是 平衡 的。
表达式 '((())' 的括号是 不平衡 的。
表达式 ')( )' 的括号是 不平衡 的。

Очередь: канал для данных, работающий по принципу очереди

Очередь — этопервым пришёл — первым вышелструктура данных; как и в любом месте в жизни, где нужно стоять в очереди (например, на кассе в супермаркете), первыми обслуживают тех, кто пришёл первым.

Основные понятия и операции

Очередь позволяет выполнять операции на одном конце (называемомхвост) для вставки (Enqueue) операций, а на другом конце (называемомголова) для операции удаления (Dequeue).

Основные операции:

  • enqueue(data)Добавляет данные в хвост очереди.
  • dequeue()Удаляет и возвращает данные из головы очереди.
  • front() / peek()Просмотреть головной элемент очереди, не удаляя его.
  • is_empty()Проверить, пуста ли очередь.

Сценарии применения и примеры кода

Очереди часто используются в сценариях, где задачи должны обрабатываться по порядку, например: очереди заданий на печать, очереди сообщений, поиск в ширину и т. д.

Пример

from collections import deque  # Использовать deque из Python, который обеспечивает эффективные операции с головой и хвостом

class Queue:
    """Реализовать очередь с использованием collections.deque"""
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        """Поставить в очередь"""
        self.items.append(item)  # Добавить справа (в хвост)

    def dequeue(self):
        """Извлечь из очереди, вернуть None, если очередь пуста"""
        if not self.is_empty():
            return self.items.popleft()  # Удалить слева (из головы)
        return None

    def front(self):
        """Посмотреть на головной элемент"""
        if not self.is_empty():
            return self.items[0]
        return None

    def is_empty(self):
        """Проверить, пуста ли очередь"""
        return len(self.items) == 0

    def size(self):
        """Вернуть размер очереди"""
        return len(self.items)

# Пример применения: имитация задач печати
print("\n=== Очередь и имитация задач печати ===)
printer_queue = Queue()

# Смоделировать поступление трёх задач печати
tasks = ["Резюме Алисы.pdf", "Отчёт Боба.doc", "Диаграмма Чарли.png"]
for task in tasks:
    printer_queue.enqueue(task)
    print(f"Задача '{task}' добавлена в очередь печати.")

# Обработка задач печати
print("\nНачало печати...)
while not printer_queue.is_empty():
    current_task = printer_queue.dequeue()
    print(f"Печать: {current_task}")
    # Имитация времени печати
print("Все задачи печати выполнены.")

Вывод:

=== 队列与打印任务模拟 ===
任务 'Alice的简历.pdf' 已加入打印队列。
任务 'Bob的报告.doc' 已加入打印队列。
任务 'Charlie的图表.png' 已加入打印队列。

开始打印...
正在打印: Alice的简历.pdf
正在打印: Bob的报告.doc
正在打印: Charlie的图表.png
所有打印任务已完成。

Итоги и сравнение

Мы изучили четыре основные линейные структуры данных. Таблица ниже поможет вам быстро просмотреть и сравнить их ключевые характеристики:

Особенности array Связный список Стек Очередь
Способ хранения Непрерывная память Разрозненная память, связанная через указатели Реализовано на основе массивов или связанных списков Реализовано на основе массивов или связанных списков
Способ доступа Произвольный доступ (по индексу) Последовательный доступ (необходимо пройти по элементам) Ограничен вершиной стека (LIFO) Ограничен головой очереди (FIFO)
Эффективность вставки/удаления Быстро в конце, медленно в середине/в начале (требуется сдвиг элементов) Быстро, когда позиция известна (нужно только изменить указатели) Операции на вершине стека, O(1) Постановка в очередь в хвост, извлечение из очереди из головы, O(1)
Size Фиксированный (статический массив) Динамический Динамический Динамический
Основные применения Быстрый поиск, фиксированная коллекция Частая вставка/удаление, неопределённый размер Вызовы функций, перебор с возвратом, сопоставление скобок Планирование задач, буферизация, BFS

Как выбрать?

  • требуетсяБыстрый произвольный доступи, когда объём данных известен, выбирайтемассив。
  • требуетсяЧасто вставлять или удалять в произвольных позицияхэлементы, и когда объём данных сильно меняется, выбирайтесвязный список。
  • Нужно реализовать"Отмена"функцию илиобратную обработкупри работе с последовательностью, рассмотритестек。
  • Нужно соблюдать"Первым пришёл — первым обслужен"при обработке задач по порядку, используйтеочередь。
Другие расширения