Основные структуры данных и алгоритмы в Java, которые вам нужно знать

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

Ниже перечислены темы, обсуждаемые в этой статье:

• Структуры данных в Java
  • Линейные структуры данных
  • Иерархические структуры данных
• Алгоритмы на Java
  • Алгоритмы сортировки
  • Алгоритмы поиска

Структуры данных в Java

Структура данных - это способ хранения и организации данных на компьютере, чтобы их можно было эффективно использовать. Он предоставляет средства для эффективного управления большими объемами данных. А эффективные структуры данных являются ключом к разработке эффективных алгоритмов.

ВВ этой статье «Структуры данных и алгоритмы в Java» мы рассмотрим основные структуры данных, такие как:

• Линейные структуры данных
  • Связанный список
  • Стеки
  • Очереди

• Иерархические структуры данных
  • Бинарные деревья
  • Кучи
  • Хеш-таблицы

Давайте проверим каждую из них.

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

Линейные структуры данных в это те элементы, чьи элементы являются последовательными и упорядочены таким образом, что: есть только один первый элемент и имеет только один следующий элемент , здесь только один последний элемент и имеет только один предыдущий элемент , а все остальные элементы имеют Следующий и предыдущий элемент.

Массивы

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

• Каждый элемент в массиве имеет один и тот же тип данных и одинаковый размер.
• Элементы массива хранятся в смежных ячейках памяти, причем первый элемент начинается с наименьшей ячейки памяти.
• Доступ к элементам массива может быть произвольным
• Структура данных массива не является полностью динамической

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

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

К - линейная структура данных с набором нескольких узлов, где eКаждый элемент хранит свои собственные данные и указатель на расположение следующего элемента. Последняя ссылка в связанном списке указывает на нуль, указывая на конец цепочки. Элемент связного списка называется узел . Первый узел называется голова .Последний узел называетсято хвостик .

Типы связанных списков

Односвязный список (однонаправленный)

Двусвязный список (двунаправленный)

Циркулярный связанный список

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

Стеки

Стек абстрактная структура данных, представляет собой набор объекты которые вставляются и удаляются в соответствии с последний пришел - первый ушел (LIFO) принцип. Объекты могут быть вставлены в стек в любой момент, но только последний вставленный (то есть «последний») объект может быть удален в любой момент.Ниже перечислены свойства стека:

• Это упорядоченный список, в которомвставка и удаление могут выполняться только на одном конце, который называется верх
• Рекурсивная структура данных с указателем на ее верхний элемент
• Следует за последний пришел - первый ушел (LIFO) принцип
• Поддерживает два самых фундаментальных метода
  • push (e): вставить элемент e в начало стека
  • pop (): удалить и вернуть верхний элемент в стеке

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

Очереди

также являются еще одним типом абстрактной структуры данных. В отличие от стека, очередь представляет собой набор объектов, которые вставляются и удаляются в соответствии с первый пришел - первый ушел (FIFO) принцип. То есть элементы могут быть вставлены в любой момент времени, но только элемент, который находился в очереди дольше всех, может быть удален в любое время.Ниже перечислены свойства очереди:

• Часто упоминается как первым прибыл, первым обслужен список
• Поддерживает два самых фундаментальных метода
  • enqueue (e): Вставить элемент e в тыл очереди
  • dequeue (): удалить и вернуть элемент из фронт очереди

Очереди используются васинхронная передача данных между двумя процессами, планирование ЦП, планирование работы дисков и другие ситуации, когда ресурсы распределяются между несколькими пользователями и обслуживаются в порядке очереди. Далее в этой статье «Структуры данных и алгоритмы в Java» мы рассмотрим иерархические структуры данных.

Иерархические структуры данных в Java

Двоичное дерево

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

• Корневой узел: это самый верхний узел, который часто называют главным узлом.потому что все остальные узлы доступны из корня
• Левое поддерево, которое также является двоичным деревом
• Правое поддерево, которое также является двоичным деревом

Ниже перечислены свойства двоичного дерева:

• Бинарное дерево можно пройти двумя способами:
  • Обход в глубину : По порядку (левый-корневой-правый), предварительный (корневой-левый-правый) и последующий (левый-правый-корневой)
  • Первый обход в ширину : Обход порядка уровней
• Временная сложность обхода дерева: O (n)
• Максимальное количество узлов на уровне «l» = 2^л-1.

Применения бинарных деревьев включают:

• Используется во многих поисковых приложениях, где данные постоянно поступают / уходят.
• Как рабочий процесс для компоновки цифровых изображений для визуальных эффектов
• Используется почти в каждом маршрутизаторе с высокой пропускной способностью для хранения таблиц маршрутизатора.
• Также используется в беспроводных сетях и распределении памяти
• Используется в алгоритмах сжатия и многом другом

Двоичная куча

Двоичная куча - это полнаядвоичное дерево, который отвечает свойству heap. Проще говоря, этопредставляет собой разновидность двоичного дерева со следующими свойствами:

• Куча - это полное двоичное дерево: Дерево называется завершенным, если завершены все его уровни, кроме, возможно, самого глубокого. Тего свойство Binary Heap делает его пригодным для хранения в .
• Следует за свойством кучи: Двоичная куча - это либо Мин-куча или Макс-куча .
  • Мин. Двоичная куча: Fили каждый узел в куче, значение узла меньше или равно ценности детей
  • Максимальная двоичная куча: Fили каждый узел в куче, значение узла больше или равно ценности детей

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

Хеш-таблицы

Представьте, что у вас есть объект и вы хотите назначить ему ключ, чтобы упростить поиск. Чтобы сохранить эту пару ключ / значение, вы можете использовать простой массив, например структуру данных, где ключи (целые числа) могут использоваться непосредственно в качестве индекса для хранения значений данных. Однако в случаях, когда ключи слишком велики и не могут использоваться напрямую в качестве индекса, используется метод, называемый хешированием.

При хешировании большие ключи преобразуются в маленькие с помощью хэш-функции . Затем значения сохраняются в структуре данных, называемойк хеш-таблица. Хэш-таблица - это структура данных, которая реализует словарный ADT, структуру, которая может отображать уникальные ключи в значения.

В общем, хеш-таблица состоит из двух основных компонентов:

1. Массив ведра: Массив корзины для хеш-таблицы - это массив A размера N, где каждая ячейка A рассматривается как «корзина», то есть набор пар ключ-значение. Целое число N определяет емкость массива.
2. Хеш-функция: Это любая функция, которая сопоставляет каждый ключ k в нашей карте с целым числом в диапазоне [0, N & минус 1], где N - емкость массива сегментов для этой таблицы.

Когда мы помещаем объекты в хеш-таблицу, возможно, что разные объекты могут иметь один и тот же хэш-код. Это называется столкновение . Чтобы справиться с коллизией, существуют такие методы, как цепочка и открытая адресация.

Итак, это некоторые основные и наиболее часто используемые структуры данных в Java. Теперь, когда вы знаете о каждом из них, вы можете начать реализовывать их в своем . На этом мы завершили первую часть статьи «Структуры данных и алгоритмы в Java». В следующей части мы узнаем оосновные алгоритмы и способы их использования в практических приложениях, таких как сортировка и поиск, разделяй и властвуй, жадные алгоритмы, динамическое программирование.

что такое печатник в Java

Алгоритмы на Java

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

• Блок-схемы - Этовизуальное представление потока управления алгоритмом
• Псевдокод - Этотекстовое представление алгоритма, аппроксимирующего окончательный исходный код

Заметка: Производительность алгоритма измеряется на основе временной и пространственной сложности. В основном сложность любого алгоритма зависит от проблемы и от самого алгоритма.

Давайте рассмотрим две основные категории алгоритмов в Java, а именно:

• Алгоритмы сортировки в Java
• Алгоритмы поиска в Java

Алгоритмы сортировки в Java

Алгоритмы сортировки - это алгоритмы, которые размещают элементы списка в определенном порядке. Чаще всего используются порядковые номера и лексикографический порядок. В этой статье «Структуры данных и алгоритмы» мы рассмотрим несколько алгоритмов сортировки.

Пузырьковая сортировка в Java

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

Вотпсевдокод, представляющий алгоритм пузырьковой сортировки (контекст сортировки по возрастанию).

a [] - массив размера N begin BubbleSort (a []) объявляет целое число i, j для i = от 0 до N - 1 для j = 0 до N - i - 1, если a [j]> a [j + 1 ], затем поменяйте местами a [j], a [j + 1] end if end на return a end BubbleSort

Этот код упорядочивает одномерный массив из N элементов данных в порядке возрастания. Внешний цикл делает N-1 проходов по массиву. Каждый проход использует внутренний цикл для обмена элементами данных, так что следующий наименьший элемент данных «пузырится» в направлении начала массива. Но проблема в том, что алгоритму требуется один проход без какой-либо подкачки, чтобы знать, что список отсортирован.

Наихудший и средний период сложности: О (п * п). Наихудший случай возникает при обратной сортировке массива.

Лучшее время сложности: На). В лучшем случае это происходит, когда массив уже отсортирован.

Сортировка выделения в Java

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

Вот псевдокод, представляющий алгоритм сортировки выбора (контекст сортировки по возрастанию).

a [] - это массив размера N begin SelectionSort (a []) для i = от 0 до n - 1 / * установить текущий элемент как минимум * / min = i / * найти минимальный элемент * / для j = i + 1 к n, если список [j]
Как можно понять из кода, количество проходов сортировки через массив на единицу меньше количества элементов в массиве. Внутренний цикл находит следующее наименьшее значение, а внешний цикл помещает это значение в нужное место. Сортировка выбора никогда не делает более O (n) замен и может быть полезна, когда запись в память является дорогостоящей операцией.
 Сложность времени: На2), так как есть два вложенных цикла.
 Вспомогательное пространство: Или (1).
 Сортировка вставкой в ​​Java 
Сортировка вставкой - это простой алгоритм сортировки, который выполняет итерацию по списку, потребляя один входной элемент за раз, и создает окончательный отсортированный массив. Это очень просто и более эффективно для небольших наборов данных. Это стабильная техника сортировки на месте.
Вот псевдокод, представляющий алгоритм сортировки вставкой (контекст сортировки по возрастанию).
a [] - это массив размера N begin InsertionSort (a []) для i = от 1 до N key = a [i] j = i - 1 while (j> = 0 и a [j]> key0 a [j + 1] = x [j] j = j - 1 конец, а [j + 1] = конец ключа для конца InsertionSort
Как видно из кода, алгоритм сортировки вставкамиудаляет один элемент из входных данных, находит место, которому он принадлежит, в отсортированном списке и вставляет его туда. Он повторяется до тех пор, пока не останется несортированных элементов ввода.
 Лучший случай: В лучшем случае входные данные представляют собой уже отсортированный массив. В этом случае сортировка вставкой имеет линейное время выполнения (т.е. & Theta (n)).
 Худший случай:  Самый простой вход в худшем случае - это массив, отсортированный в обратном порядке.
 QuickSort в Java 
Алгоритм быстрой сортировки - это быстрый, рекурсивный, нестабильный алгоритм сортировки, который работает по принципу «разделяй и властвуй». Он выбирает элемент в качестве оси поворота и перегородок данного массива вокруг этой оси выбрала.
 Шаги по реализации быстрой сортировки:  
 
Выберите подходящую «точку поворота».
Разделите списки на два спискана основе этого стержневого элемента. Каждый элемент, который меньше, чем элемент поворота, помещается в левый список, а каждый элемент, который больше, помещается в правый список. Если элемент равен элемент поворота, то он может пойти в любом списке. Это называется операцией разделения.
Рекурсивно отсортируйте каждый из меньших списков. 
Вот псевдокод, представляющий алгоритм быстрой сортировки.
QuickSort (A as array, low as int, high as int) {if (low
В приведенном выше псевдокоде раздел () функция выполняет операцию разделения и Быстрая сортировка () функция многократно вызывает функцию разделения для каждого сгенерированного меньшего списка. Сложность быстрой сортировки в среднем составляет & Theta (n log (n)), а в худшем - & Theta (n2).
 Сортировка слиянием в Java 
Сортировка слиянием - это быстрый, рекурсивный и стабильный алгоритм сортировки, который также работает по принципу «разделяй и властвуй». Подобно быстрой сортировке, сортировка слиянием делит список элементов на два списка. Эти списки сортируются независимо, а затем объединяются. Во время объединения списков элементы вставляются (или объединяются) в нужное место в списке.
Вот псевдокод, представляющий алгоритм сортировки слиянием.
процедура MergeSort (a as array) if (n == 1) возвращает var l1 как array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) конец процедуры слияние процедуры (a как массив, b как массив) var c как массив while (a и b имеют элементы) if ( a [0]> b [0]) добавить b [0] в конец c удалить b [0] из b иначе добавить a [0] в конец c удалить a [0] с конца if end while while (a имеет элементы) добавить [0] в конец c удалить a [0] из конца, в то время как (b имеет элементы) добавить b [0] в конец c удалить b [0] из конца b, а return c конец процедуры
 Сортировка слиянием() функция делит список на два, вызывает Сортировка слиянием() в этих списках по отдельности, а затем объединяет их, отправляя их в качестве параметров функции merge ().Алгоритм имеет сложность O (n log (n)) и имеет широкий спектр приложений.
 Сортировка кучи в Java 
Heapsort - это алгоритм сортировки на основе сравненияСтруктура данных двоичной кучи. Вы можете думать об этом как об улучшенной версии f сортировки выбора, гдеон делит свой ввод на отсортированную и несортированную области и итеративно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область.
 Шаги по внедрению Quicksort (в порядке возрастания): 
Создайте максимальную кучу с помощью сортировочного массива
В этот моментt самый большой элемент хранится в корне кучи. Замените его последним элементом кучи и уменьшите размер кучи на 1. Наконец, добавьте кучу корень дерева.
Повторяйте вышеуказанные шаги, пока размер кучи не станет больше 1
Вот псевдокод, представляющий алгоритм сортировки кучи.
Heapsort (a as array) for (i = n / 2 - 1) to i> = 0 heapify (a, n, i) for i = n-1 to 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int) large = i // инициализировать наибольшее значение как root int l eft = 2 * i + 1 // left = 2 * i + 1 int right = 2 * i + 2 // right = 2 * i + 2 if (left a [наибольшее]) наибольшее = left if (право a [наибольшее]) наибольшее = право if (наибольшее! = I) swap ( a [i], A [наибольший]) Heapify (a, n, наибольший) end heapify
Помимо этого, существуют другие алгоритмы сортировки, которые не так хорошо известны, как Introsort, Counting Sort и т. Д. Перейдем к следующему набору алгоритмов в этой статье «Структуры данных и алгоритмы», давайте рассмотрим алгоритмы поиска.
 Алгоритмы поиска в Java 
Поиск - одно из самых распространенных и часто выполняемых действий в обычных бизнес-приложениях. Алгоритмы поиска - это алгоритмы поиска элемента с заданными свойствами среди набора элементов. Давайте рассмотрим два наиболее часто используемых алгоритма поиска.
 Алгоритм линейного поиска в Java 
Линейный поиск или последовательный поиск - самый простой алгоритм поиска. Он включает в себя последовательный поиск элемента в данной структуре данных до тех пор, пока либо элемент не будет найден, либо не будет достигнут конец структуры. Если элемент найден, то возвращается местоположение элемента, иначе алгоритм возвращает NULL.
Вот псевдокод, представляющий линейный поиск в Java:
процедура linear_search (a [], значение) для i = от 0 до n-1, если a [i] = value, затем вывести «Найдено», вернуть i end, если вывести «Not found», конец для конца linear_search
Этоалгоритм грубой силы.Хотя это, безусловно, самый простой, он определенно не самый распространенный из-за своей неэффективности. Временная сложность линейного поиска составляет НА) .
 Алгоритм двоичного поиска в Java 
Двоичный поиск, также известный как логарифмический поиск, представляет собой алгоритм поиска, который находит позицию целевого значения в уже отсортированном массиве. Он делит входную коллекцию на равные половины, и элемент сравнивается со средним элементом списка. Если элемент найден, поиск на этом заканчивается. В противном случае мы продолжаем поиск элемента, разделяя и выбирая соответствующий раздел массива, в зависимости от того, больше ли целевой элемент, чем средний элемент.
Вот псевдокод, представляющий двоичный поиск в Java:
Процедура binary_search для отсортированного массива n размер массива x значение для поиска lowerBound = 1 upperBound = n, а x не найден, если upperBound
Поиск прекращается, когда upperBound (наш указатель) проходит мимо lowerBound (последний элемент), что означает, что мы просмотрели весь массив, а элемент отсутствует.Это наиболее часто используемые алгоритмы поиска, прежде всего из-за быстрого времени поиска. Временная сложность двоичного поиска составляет НА) что является заметным улучшением НА) временная сложность линейного поиска.
На этом мы подошли к концу статьи «Структуры данных и алгоритмы в Java». Я затронул одну из самых фундаментальных и важных тем Java.Надеюсь, вы понимаете все, что было поделено с вами в этой статье.
  Убедитесь, что вы как можно больше тренируетесь и верните свой опыт.   
 Проверьте    от Edureka, надежной компании онлайн-обучения с сетью из более чем 250 000 довольных учащихся по всему миру. Мы здесь, чтобы помогать вам на каждом этапе вашего пути. Для того, чтобы стать интересным, помимо вопросов на Java-собеседовании, мы разработали учебную программу, предназначенную для студентов и профессионалов, которые хотят стать Java-разработчиками. 
 Есть вопрос к нам? Пожалуйста, укажите это в комментариях к этой статье «Структуры данных и алгоритмы в Java».  статья, и мы свяжемся с вами в ближайшее время.