Способы представления данных

Размещено на http://www.allbest.ru/

Содержание

• Что такое структура данных?
• Массивы
• Связанный список (Linked List)
• Стек
• Очередь
• Граф
• Дерево
• Хэш-таблица
• Что такое структура данных?
• Независимо от профессии, ежедневная работа связана с данными. Шеф-повар, инженер-программист или даже рыбак ?--? все они работают с теми или иными формами данных.
• Структуры данных ?--? это контейнеры, которые хранят данные в определенном формате. Этот специфический формат придает структуре данных определенные качества, которые отличают ее от других структур и делают ее пригодной (или напротив, неподходящей) для тех или иных сценариев использования.
• Рассмотрим некоторые из наиболее важных структур данных, которые помогут создавать эффективные решения.
• Массивы
• Массивы ?--? одна из самых простых и часто применяемых структур данных. Такие структуры данных, как очереди и стеки, основаны на массивах и связанных списках (которые мы рассмотрим чуть позже).
• Каждому элементу в массиве присваивается положительное целое число, которое обозначает положение элемента. Это число называется индексом. В большинстве языков программирования индексы начинаются с нуля. Эта концепция называется нумерацией на основе нуля.
• Существует два типа массивов: одномерные и многомерные. Первые представляют собой простейшие линейные структуры, а вторые ?--? вложенные и включают другие массивы.
• Основные операции с массивами
• · Get ?--? получить элемент массива по заданному индексу.
• · Insert ?--? вставить элемент массива по заданному индексу.
• · Length ?--? получить количество элементов в заданном массиве.
• · Delete ?--? удалить элемент массива по заданному индексу. Может быть выполнено либо путем установки значения undefined, либо путем копирования элементов массива, за исключением удаляемого, в новый массив.
• · Update ?--? обновление значения элемента массива по заданному индексу.
• · Traverse?--? проход цикла через массив для выполнения функций над элементами массива.
• · Search ?--? поиск определенного элемента в заданном массиве с помощью выбранного алгоритма.
• Применение массивов
• · Представляют собой строительные блоки более сложных структур данных, таких как стеки, очереди и т.д.
• · Подходят для хранения несложных связанных данных благодаря простоте использования.
• · Используются для различных алгоритмов сортировки, таких как сортировка вставок, сортировка пузырьком и т.д.
• Одномерный массив

• Многомерный массив
• Связанный список (Linked List)
• Связанный список ?--? это набор элементов, называемых узлами, в линейной последовательной структуре. Узел ?--? простой объект с двумя свойствами. Это переменные для хранения данных и адреса памяти следующего узла в списке. Поэтому узел знает только о том, какие данные он содержит и кто его сосед. Это позволяет создавать связанные списки, в которых каждый узел связан с другим.
• Существует несколько типов связанных списков.
• · Односвязный. Обход элементов может выполняться только в прямом направлении.
• · Двусвязный. Обход элементов может выполняться как в прямом, так и в обратном направлениях. Узлы включают дополнительный указатель, известный как prev, указывающий на предыдущий узел.
• · Круговые связанные. Это связанные списки, в которых предыдущий (prev) указатель “головы” указывает на “хвост”, а следующий указатель “хвоста” указывает на “голову”.
• Основные операции со связанными списками
• · Insertion?--? добавление узла в список. Это может быть сделано на основе требуемого местоположения, такого как голова, хвост или где-то посередине.
• · Delete?--? удаление узла в начале списка или на основе заданного ключа.
• · Display ?--? отображение полного списка.
• · Search ?--? поиск узла в данном связанном списке.
• · Update ?--? обновление значения узла в заданном ключе.
• Применение связанных списков
• · В качестве строительных блоков сложных структур данных, таких как очереди, стеки и некоторые типы графиков.
• · В слайд-шоу изображений, поскольку изображения идут строго друг за другом.
• · В динамических структурах для выделения памяти.
• · В операционных системах для легкого переключения вкладок.
• Стек
• Стек ?--? линейная структура данных, которая создается на основе массивов или связанных списков. Стек следует принципу Last-In-First-Out (LIFO, “первым на вход ?--? последним на выход”), т.е. последний элемент, вошедший в стек, будет первым, кто покинет его. Причина, по которой эта структура называется стеком, в том, что ее можно визуализировать как стопку книг на столе (по-английски stack).
• Основные операции со стеком
• · Push ?--? вставка элемента в верхнюю часть стека.
• · Pop ?--? удаление элемента из верхней части стека с возвращением элемента.
• · Peek ?--? просмотр элемента в верхней части стека.
• · isEmpty ?--? проверка пустоты стека.
• Применение стеков
• · В истории навигации браузера.
• · Для реализации рекурсии.
• · При выделении памяти на основе стека.
• Очередь
• Как и стек, очередь ?--? это еще один тип линейной структуры данных, основанной либо на массивах, либо на связанных списках. Очереди отличаются от стеков тем, что они основаны на принципе First-In-First-Out (FIFO, “первым на вход ?--? первым на выход”), где элемент, который входит в очередь первым, и покинет ее первым.
• Реальная аналогия структуры данных “очереди” ?--? это очередь людей, ожидающих покупки билета в кино.
• Основные операции с очередями
• · Enqueue ?--? вставка элемента в конец очереди.
• · Dequeue ?--? удаление элемента из передней части очереди.
• · Top/Peek ?--? возвращает элемент из передней части очереди без удаления.
• · isEmpty ?--? проверка содержимого очереди.
• Применение очередей
• · Обслуживание нескольких запросов на одном общем ресурсе.
• · Управление потоками в многопоточных средах.
• · Балансировка нагрузки.
• Граф
• Граф ?--? это структура данных, представляющая собой взаимосвязь узлов, которые также называются вершинами. Пара (x,y) называется ребром. Это указывает на то, что вершина x соединена с вершиной y. Ребро может указывать на вес/стоимость, то есть стоимость прохождения по пути между двумя вершинами.
• Ключевые термины
• · Размер ?--? количество ребер в графике.
• · Порядок ?--? количество вершин в графе.
• · Смежность ?--? случай, когда два узла соединены одним и тем же ребром.
• · Петля ?--? вершина, соединенная ребром сама с собой.
• · Изолированная вершина ?--? вершина, которая не связана с другими вершинами.
• Графы делятся на два типа. Они различаются главным образом по направлениям пути между двумя вершинами.
• · Ориентированные графы: все ребра имеют направления, указывающие начальную и конечную точки (вершины).
• · Неориентированные графы: ребра не имеют направлений, которые позволяют обходам происходить с любого направления.
• Распространенные алгоритмы обхода графов
• · Поиск в ширину (BFS) ?--? метод поиска кратчайшего пути в графе, основанный на вершинах.
• · Поиск в глубину (DFS) ?--? метод, основанный на ребрах.
• Основные операции с графами
• · Addvertex: добавить вершину в граф.
• · Addedge: добавить ребро между двумя вершинами.
• · Display: отобразить вершину.
• · Total costoftraversal: найти общую стоимость пути обхода.
• Применение графов
• · Для представления потоковых вычислений.
• · При распределении ресурсов операционной системой.
• · Реализация алгоритмов поиска друзей в Facebook.
• · Расчет кратчайшего пути между двумя локациями (Google Maps).

• Ориентированный граф со стоимостью
• Дерево
• Дерево ?--? это иерархическая структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Деревья часто используются в системах искусственного интеллекта и сложных алгоритмах, поскольку обеспечивают эффективный подход к решению проблем. Дерево ?--? это особый тип графа, который не содержит циклов. Некоторые утверждают, что деревья полностью отличаются от графов, но эти аргументы субъективны.
• массивы данные стек очередь граф хэш таблица
• Существует несколько типов деревьев.
• · N-арное дерево.
• · Сбалансированное дерево.
• · Бинарное дерево.
• · Бинарное дерево поиска (BST).
• · Дерево AVL.
• · Красно-черное дерево.
• · 2-3-дерево.
• BST ?--? самые распространенные типы деревьев.
• Простое дерево
• Основные операции с BST
• · Insert ?--? вставка элемента в дерево.
• · Search ?--? поиск элемента в дереве.
• · PreorderTraversal ?--? обход дерева прямым способом.
• · InorderTraversal ?--? обход дерева центрированным способом.
• · PostorderTraversal ?--? обход дерева обратным способом.
• Применение деревьев
• · Представление организации.
• · Представление компьютерной файловой системы.
• · Представление химической формулы.
• · В деревьях принятия решений.
• · Внутри JVM (Java Virtual Machine) для хранения объектов Java.
• Хэш-таблица
• Хэш-таблица хранит данные в парах ключ-значение. Это означает, что каждый ключ в хэш-таблице имеет некое значение, связанное с ним. Такая простая компоновка обеспечивает эффективность хэш-таблиц, независимо от их размера, при работе с данными.
• Хэш-таблицы похожи на обычное хранилище данных с парой ключ-значение, однако их отличает способ генерации ключей. Они создаются с помощью специального процесса, называемого хэшированием.
• Хеширование (хэш-функция)
• Хэширование ?--? это процесс, который с помощью хэш-функции преобразует ключ для получения хэшированного ключа. Эта хэш-функция определяет индекс таблицы или структуры, в которых должно храниться значение.
• h(k) = k % m
• · h ?--? хэш-функция.
• · k ?--? ключ, из которого должно быть определено хэш-значение.
• · m ?--? размер хэш-таблицы.
• Например, рассмотрим использование хэш-функции k%17. Если исходный ключ равен 20, то хэшированный будет 20%17=3. Значение будет храниться в хэш-таблице под индексом 3.
• Хэш-функция для ключей
• Зачем нужен хэш?
• Некоторые задаются вопросом, зачем проходить через дополнительный процесс хэширования, когда можно просто сопоставить значения непосредственно с ключом. Хотя прямое сопоставление несложно, оно может оказаться неэффективным при работе с большим набором данных. С помощью хеширования можно достичь почти постоянного времени O(1).
• Коллизии
• Поскольку для преобразования ключей используется общая хэш-функция, существует вероятность коллизий. Рассмотрим приведенный ниже пример с учетом хэш-функции k%17.
• · Когда k = 18, h(18) = 18%17 = 1.
• · При k = 20, h(20) = 20%17 = 3.
• · При k = 35, h(35) = 35%17 = 1.
• Когда ключи равняются 18 и 35, происходит коллизия, поскольку они направляются к индексу 1.
• Коллизии можно разрешить с помощью таких стратегий, как раздельная цепочка и открытая адресация.
• Основные операции с хэш-таблицами
• · Search ?--? поиск элемента в хэш-таблице.
• · Insert ?--? вставка элемента в хэш-таблицу.
• · Delete ?--? удаление элемента из хэш-таблицы.
• Применение хэш -таблиц
• · В индексации баз данных.
• · При проверке орфографии.
• · При реализации заданной структуры данных.
• · В кэше.
• Размещено на Allbest.ru