Стеки, очереди, деревья, связанные списки, графики, хэш-карты

Что такое структуры данных?

Структуры данных - это строительные блоки языков программирования. Структура данных - это то, как компьютеры организуют связанные данные для выполнения определенных операций. При выборе правильной структуры данных данные преобразуются во что-то, что программа может эффективно использовать. В зависимости от проблемы вы захотите хранить данные по-разному, чтобы удовлетворить определенные потребности. Точно так же разные структуры данных лучше подходят для разных задач. Две структуры данных могут выполнять одну и ту же задачу, но одна может быть более эффективной. Это соображение более известно как временная сложность.

  • Python имеет два набора структур данных: встроенные структуры данных и определяемые пользователем структуры данных. (Сегодня мы сосредоточимся на определяемых пользователем структурах данных .)

Что такое структура данных, определяемая пользователем?

  • Позволяет пользователям создавать свои собственные структуры данных, такие как стеки, очереди, деревья, связанные списки, графики, хэш-карты.

Как используются структуры данных?

Структуры данных выполняют для нас четыре основные функции:

  • Ввод информации
  • Обработка информации
  • Сохранение информации
  • Получение информации

Стеки:

Стек - это структура данных LIFO или FILO с двумя основными операциями: push и pop . (Доступен только первый элемент.)

  • LIFO = "последний пришел - первым ушел"
  • FILO = первым пришел последний ушел
  • Push: добавить элемент в верхнюю часть стопки.
  • Pop: удалить элемент из вершины стопки.

Чем полезны стеки?

  • Отслеживание назад для доступа к предыдущим элементам / операциям.
  • Соответствие рекурсивных элементов / операций.

Очереди:

Очередь - это структура данных FIFO или LILO с двумя основными операциями: поставить в очередь и удалить из очереди. (Доступны как голова, так и хвост.)

  • Enqueue: добавить элемент в конец очереди.
  • Dequeue: удалить элемент из заголовка очереди.
  • FIFO = первым пришел - первым ушел
  • LILO = Последний ушел Последний ушел

Чем полезны очереди?

  • Обработка материалов по мере их поступления. (Подумайте о загрузке изображений, печати документов или обработке запросов веб-сервера.)

Деревья двоичного поиска:

Двоичное дерево - это нелинейная структура данных, представленная узлами, соединенными ребрами. Каждое дерево начинается с корневого узла, также называемого родительским узлом, а левого и правого узлов - дочерних узлов. У каждого узла в двоичном дереве может быть только два дочерних элемента. Левый дочерний элемент узла должен быть меньше родительского значения, а правый дочерний элемент должен быть больше родительского значения.

Чем полезны деревья?

  • Деревья отражают структурные взаимосвязи данных.
  • Позволяет эффективно обходить все узлы в дереве.
  • Деревья эффективно вставляют, ищут, извлекают и удаляют данные.
  • Деревья - это гибкие структуры данных, позволяющие перемещать поддеревья с минимальными усилиями.

Связанные списки:

Связанный список - это структура данных узлов, в которой значения связаны указателями. Первый узел связанного списка называется заголовком. Последний узел связанного списка называется хвостом.

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

Чем полезны связанные списки?

  • В то время как массив является фиксированным, элементы связанного списка распределяются динамически. Связанный список экономит память, выделяя память, необходимую для хранения значений. В массиве вы устанавливаете размер массива перед заполнением его значениями, что потенциально может привести к потере памяти.
  • Узлы связанного списка могут находиться где угодно в памяти. В то время как массив требует инициирования последовательности памяти, пока ссылки обновляются, узел связанного списка может перемещаться по другому адресу.

Графики:

График - это структура данных в форме графического представления, в которой вершины (узлы) и ребра соединены ссылками. Графики используются для нахождения наиболее эффективного пути, то есть отношения стоимости к расстоянию между узлами.

Эти взаимосвязанные объекты представлены точками, известными как вершины, а связи, соединяющие вершины, называются ребрами. Вершины представлены как ключи словаря, а ребра представлены как значения в словаре.

*Chart of the above graph*
graph = { "0" : ["01", "04"]
          "1" : ["10", "13", "14"],
          "2" : ["21", "23"],
          "3" : ["31", "32", "34"]
          "4" : ["40", "41", "43"]
        }

Следующие элементы представляют собой основные операции, выполняемые с графиками.

  • Отображение вершин графа
  • Отображение ребер графика
  • Добавить вершину
  • Добавьте край
  • Создайте график

Чем полезны графики?

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

HashMaps:

Хеш-таблицы также известны как Хеш-карты.

Хеш-карта используется для хранения данных в парах "ключ-значение". Данные в хеш-таблице можно получить с помощью ключа в качестве ссылки. Ключи генерируются с помощью функции хеширования.

Хеширование используется для однозначной идентификации объекта из группы объектов. В хэш-таблице каждому элементу назначается пара "ключ-значение", где ключ преобразуется в hash_value с использованием хэш-функции, а затем эта хеш-функция указывает, где добавить / удалить / обновить значение. .

Эти виды структур данных могут использоваться для хранения информации о студентах, истории заказов, сведений о клиентах, идентификаторах сотрудников и т. Д.

Чем полезны графики?

  • Хеширование обеспечивает более надежный и гибкий метод извлечения данных, чем любая другая структура данных.
  • Помимо средней пространственной сложности O (n), хеш-таблицы имеют временную сложность O (1).