Стеки, очереди, деревья, связанные списки, графики, хэш-карты
Что такое структуры данных?
Структуры данных - это строительные блоки языков программирования. Структура данных - это то, как компьютеры организуют связанные данные для выполнения определенных операций. При выборе правильной структуры данных данные преобразуются во что-то, что программа может эффективно использовать. В зависимости от проблемы вы захотите хранить данные по-разному, чтобы удовлетворить определенные потребности. Точно так же разные структуры данных лучше подходят для разных задач. Две структуры данных могут выполнять одну и ту же задачу, но одна может быть более эффективной. Это соображение более известно как временная сложность.
- 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).