Най-добрите структури от данни и алгоритми в Java, които трябва да знаете

Ако трябваше да избера най-важната тема в разработването на софтуер, това биха били структурите от данни и алгоритмите. Можете да го възприемате като основен инструмент, достъпен за всеки компютърен програмист. Докато програмираме, ние използваме структури от данни за съхраняване и организиране на данни и алгоритми за манипулиране на данните в тези структури. Тази статия съдържа подробен преглед на всички често срещани структури от данни и алгоритми в за да се даде възможност на читателите да станат добре оборудвани.

По-долу са изброени темите, обсъдени в тази статия:

управлявана от данни рамка в селен webdriver

• Структури на данни в Java
  • Линейни структури от данни
  • Йерархични структури от данни
• Алгоритми в Java
  • Алгоритми за сортиране
  • Търсене на алгоритми

Структури на данни в Java

Структурата на данните е начин за съхраняване и организиране на данни в компютър, така че да може да се използва ефективно. Той осигурява средство за ефективно управление на големи количества данни. А ефективните структури от данни са ключови за проектирането на ефективни алгоритми.

Втази статия „Структури на данни и алгоритми в Java“ ще разгледаме основни структури от данни като:

• Линейни структури от данни
  • Свързан списък
  • Стекове
  • Опашки

• Йерархични структури от данни
  • Двоични дървета
  • Купчини
  • Хеш таблици

Нека проверим всеки от тях.

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

Линейни структури от данни в са тези, чиито елементи са последователни и подредени по начин, така че: има само един първи елемент и има само един следващ елемент , има само един последен елемент и има само един предишен елемент , докато всички останали елементи имат a следващия и а предишен елемент.

Масиви

An масив е линейна структура от даннипредставляваща група от подобни елементи, достъпни чрез индекс. Преди съхраняване на данни трябва да се предостави размер на масив. По-долу са изброени свойствата на масив:

• Всеки елемент в масив е от същия тип данни и има еднакъв размер
• Елементите на масива се съхраняват в съседни места с памет, като първият елемент започва от най-малкото място в паметта
• Елементите на масива могат да бъдат достъпни произволно
• Структурата на данните от масива не е напълно динамична

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

Свързан списък

ДА СЕ е линейна структура от данни със събирането на множество възли, където each елемент съхранява свои собствени данни и указател за местоположението на следващия елемент. Последната връзка в свързан списък сочи към нула, указвайки края на веригата. Елемент в свързан списък се нарича a възел . Първият възел се нарича глава .Извиква се последният възелна опашка .

Видове свързан списък

Единично свързан списък (еднопосочен)

Двойно свързан списък (двупосочен)

Кръгово свързан списък

Ето един прост пример: Представете си свързан списък като верига кламери, които са свързани помежду си. Можете лесно да добавите още една кламер в горната или долната част. Дори е бързо да вмъкнете такъв в средата. Всичко, което трябва да направите, е просто да изключите веригата в средата, да добавите новата кламер, след което да свържете отново половината. Свързаният списък е подобен.

Стекове

Стек, абстрактна структура от данни, е колекция от обекти които се вмъкват и изваждат според последен-първи-излязъл (LIFO) принцип. Обектите могат да бъдат вмъкнати в стека по всяко време, но само последно вмъкнатият (т.е. „последният“) обект може да бъде премахнат по всяко време.По-долу са изброени свойствата на стека:

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

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

Опашки

също са друг тип абстрактна структура на данните. За разлика от стека, опашката е колекция от обекти, които се вмъкват и премахват според първо в първото излизане (FIFO) принцип. Тоест, елементите могат да бъдат вмъкнати по всяко време, но само елементът, който е бил в опашката най-дълго, може да бъде премахнат по всяко време.По-долу са изброени свойствата на опашката:

• Често наричан първо в първото излизане списък
• Поддържа два най-фундаментални метода
  • enqueue (e): Вмъкнете елемент e в отзад на опашката
  • dequeue (): Премахнете и върнете елемента от отпред на опашката

Опашките се използват васинхронен трансфер на данни между два процеса, планиране на процесора, дисково планиране и други ситуации, при които ресурсите се споделят между множество потребители и се обслужват на база първи дошъл сървър. След това в тази статия „Структури на данни и алгоритми в Java“ имаме йерархични структури от данни.

Йерархични структури от данни в Java

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

Бинарното дърво ейерархични дървовидни структури от данни, в които всеки възел има най-много две деца , които са посочени като ляво дете и правилно дете . Всяко двоично дърво има следните групи възли:

• Root Node: Това е най-горният възел и често се нарича главен възелзащото всички останали възли могат да бъдат достигнати от корена
• Ляво поддърво, което също е двоично дърво
• Право поддърво, което също е двоично дърво

По-долу са изброени свойствата на двоично дърво:

• Двоично дърво може да бъде пресечено по два начина:
  • Дълбочина Първо обръщане : По ред (ляво-корен-дясно), предварително подреждане (корен-ляво-дясно) и след поръчка (ляво-дясно-корен)
  • Широчина Първо обръщане : Обръщане на ред на ниво
• Сложност във времето на обхождане на дърво: O (n)
• Максималният брой възли на ниво ‘l’ = 2^l-1.

Приложенията на двоичните дървета включват:

• Използва се в много приложения за търсене, където данните постоянно влизат / излизат
• Като работен процес за композиране на цифрови изображения за визуални ефекти
• Използва се в почти всеки рутер с висока честотна лента за съхранение на рутер-маси
• Използва се и при безжични мрежи и разпределение на паметта
• Използва се в алгоритми за компресия и много други

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

Binary Heap е пълнадвоично дърво, който отговаря на свойството на купчината. С прости думи товае вариант на двоично дърво със следните свойства:

• Heap е пълно двоично дърво: Казва се, че едно дърво е пълно, ако всички негови нива, с изключение на евентуално най-дълбоките, са завършени. тнеговото свойство на Binary Heap го прави подходящо да се съхранява в .
• Следва свойството на купчината: Двоична купчина е или Min-Heap или а Max-Heap .
  • Минимална купчина: Fили всеки възел в купчина, стойността на възела е по-малко или равно на ценности на децата
  • Макс двоична купчина: Fили всеки възел в купчина, стойността на възела е по-голямо или равно на ценности на децата

Популярните приложения на двоичната купчина включватвнедряване на ефективни приоритетни опашки, ефективно намиране на k-малките (или най-големите) елементи в масив и много други.

Хеш таблици

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

При хеширане големите ключове се преобразуват в малки ключове чрез използване хеш функции . След това стойностите се съхраняват в структура с данни, нареченада се хеш таблица. Хеш таблицата е структура от данни, която прилага речник ADT, структура, която може да съпоставя уникални ключове към стойности.

Като цяло хеш таблицата има два основни компонента:

1. Кофа масив: Кошерен масив за хеш таблица е масив A с размер N, където всяка клетка от A се смята за „кофа“, тоест колекция от двойки ключ-стойност. Цялото число N определя капацитета на масива.
2. Хеш функция: Всяка функция е, която картографира всеки ключ k в нашата карта на цяло число в диапазона [0, N и минус 1], където N е капацитетът на масива от сегменти за тази таблица.

Когато поставяме обекти в хеш-таблица, възможно е различните обекти да имат един и същ хеш-код. Това се нарича a сблъсък . За справяне със сблъсъка има техники като верижно обвързване и открито адресиране.

И така, това са някои основни и най-често използвани структури от данни в Java. Сега, когато сте наясно с всяко едно от тях, можете да започнете да ги прилагате във вашия . С това завършихме първата част на тази статия „Структури на данни и алгоритми в Java“. В следващата част ще научим повечеосновни алгоритми и как да ги използваме в практически приложения като сортиране и търсене, разделяне и завладяване, алчни алгоритми, динамично програмиране.

Алгоритми в Java

Исторически използвани като инструмент за решаване на сложни математически изчисления, алгоритмите са дълбоко свързани с компютърните науки и по-специално със структурите на данни. Алгоритъмът е последователност от инструкции, която описва начин за решаване на конкретен проблем за ограничен период от време. Те са представени по два начина:

• Блок-схеми - Това евизуално представяне на контролния поток на алгоритъма
• Псевдокод - Тое текстово представяне на алгоритъм, който приближава крайния изходен код

Забележка: Ефективността на алгоритъма се измерва въз основа на сложността на времето и сложността на пространството. Най-вече сложността на всеки алгоритъм зависи от проблема и от самия алгоритъм.

Нека разгледаме двете основни категории алгоритми в Java, които са:

• Сортиране на алгоритми в Java
• Търсене на алгоритми в Java

Сортиране на алгоритми в Java

Алгоритмите за сортиране са алгоритми, които поставят елементи от списък в определен ред. Най-често използваните нареждания са числов и лексикографски ред. В тази статия „Структури на данни и алгоритми“ можете да разгледате няколко алгоритми за сортиране.

Сортиране на балончета в Java

Bubble Sort, често наричан потъващо сортиране, е най-простият алгоритъм за сортиране. Той многократно преминава през списъка, за да бъде сортиран, сравнява всяка двойка съседни елементи и ги разменя, ако са в грешен ред.Bubble sort получава името си, тъй като филтрира елементите в горната част на масива, като мехурчета, които се носят върху вода.

Етопсевдокод, представляващ алгоритъм за сортиране на балончета (възходящ контекст на сортиране).

a [] е масив с размер N начало 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 преминава през масива. Всеки проход използва вътрешен цикъл за обмен на елементи от данни, така че следващият най-малък елемент от данни да „балонче“ към началото на масива. Но проблемът е, че алгоритъмът се нуждае от един цял проход без никакъв суап, за да знае, че списъкът е сортиран.

Най-лошата и средна сложност на времето на делото: O (n * n). Най-лошият случай възниква, когато масивът е сортиран обратно.

Най-добрата сложност във времето: На). Най-добрият случай се случва, когато масив вече е сортиран.

Сортиране на селекция в Java

Сортирането по селекция е комбинация както от търсене, така и от сортиране. Алгоритъмът сортира масив, като многократно намира минималния елемент (като се разглежда възходящ ред) от несортираната част и го поставя на подходящо място в масива.

Ето псевдокод, представляващ алгоритъм за сортиране на избора (възходящ контекст на сортиране).

a [] е масив с размер N begin SelectionSort (a []) за i = 0 до n - 1 / * задайте текущия елемент като минимум * / min = i / * намерете минималния елемент * / за j = i + 1 до n ако списък [j]
Както можете да разберете от кода, броят пъти, когато сортирането преминава през масива, е един по-малък от броя на елементите в масива. Вътрешният цикъл намира следващата най-малка стойност, а външният цикъл поставя тази стойност на правилното й място. Сортирането на селекция никога не прави повече от O (n) суапове и може да бъде полезно, когато записването в паметта е скъпа операция.
 Сложност във времето: На2), тъй като има два вложени цикъла.
 Спомагателно пространство: Или (1).
 Сортиране на вмъкване в Java 
Insertion Sort е прост алгоритъм за сортиране, който прелиства списъка, като консумира по един входен елемент наведнъж и изгражда окончателния сортиран масив. Това е много просто и по-ефективно за по-малки масиви от данни. Това е стабилна и на място техника за сортиране.
Ето псевдокод, представляващ алгоритъм за сортиране при вмъкване (възходящ контекст на сортиране).
a [] е масив с размер N begin InsertionSort (a []) за i = 1 до N ключ = a [i] j = i - 1 докато (j> = 0 и a [j]> key0 a [j + 1] = x [j] j = j - 1 край, докато [j + 1] = ключ за край InsertionSort
Както можете да разберете от кода, алгоритъмът за сортиране на вмъкванетопремахва един елемент от входните данни, намира местоположението, което му принадлежи, в сортирания списък и го вмъква там. Повтаря се, докато нито един входен елемент не остане несортиран.
 Най-добрият случай: Най-добрият случай е, когато входът е масив, който вече е сортиран. В този случай сортирането за вмъкване има линейно време на работа (т.е. & Theta (n)).
 Най-лошия случай:  Най-простият вход в най-лошия случай е масив, сортиран в обратен ред.
 QuickSort в Java 
Алгоритъмът за бързо сортиране е бърз, рекурсивен, нестабилен алгоритъм за сортиране, който работи по принципа на разделяне и завладяване. Той избира елемент като пивот и разделя дадения масив около този избран пивот.
 Стъпки за внедряване на бързо сортиране:  
 
Изберете подходяща „точка на въртене“.
Разделете списъците на два списъкавъз основа на този опорен елемент. Всеки елемент, който е по-малък от основния елемент, се поставя в левия списък, а всеки по-голям елемент се поставя в десния списък. Ако даден елемент е равен на основния елемент, той може да влезе във всеки списък. Това се нарича операция за разделяне.
Рекурсивно сортирайте всеки от по-малките списъци. 
Ето псевдокод, представляващ алгоритъм Quicksort.
QuickSort (A като масив, нисък като int, висок като int) {if (нисък
В горния псевдокод, дял () функция изпълнява операция на дял и Quicksort () функция многократно извиква функция за разделяне за всеки генериран по-малък списък. Сложността на бързата сортировка в средния случай е & Theta (n log (n)), а в най-лошия случай е & Theta (n2).
 Сливане на сортиране в Java 
Mergesort е бърз, рекурсивен, стабилен алгоритъм за сортиране, който също работи по принципа на разделяне и завладяване. Подобно на бързата сортировка, сортирането чрез сливане разделя списъка с елементи на два списъка. Тези списъци се сортират независимо и след това се комбинират. По време на комбинирането на списъците елементите се вмъкват (или обединяват) на правилното място в списъка.
Ето псевдокод, представляващ алгоритъм за сортиране на обединяване.
сортиращ масив c ++
процедура MergeSort (a като масив), ако (n == 1) връща var l1 като масив = a [0] ... a [n / 2] var l2 като масив = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) end procedure процедура merge (a като масив, b като масив) var c като масив, докато (a и b имат елементи) if ( a [0]> b [0]) добавете b [0] в края на c премахнете b [0] от b иначе добавете [0] в края на c премахнете [0] от края, ако край докато (a има елементи) добавете a [0] в края на c премахнете a [0] от край, докато (b има елементи) добавете b [0] в края на c премахнете b [0] от b край, докато връщате c крайна процедура
 сливане () функция разделя списъка на две, повиквания сливане () в тези списъци поотделно и след това ги комбинира, като ги изпраща като параметри за функция merge ().Алгоритъмът има сложност на O (n log (n)) и има широк спектър от приложения.
 Сортиране на купчина в Java 
Heapsort е базиран на сравнение алгоритъм за сортиранеСтруктура на данните на двоична купчина. Можете да го мислите като подобрена версия f сортиране на селекция, къдетой разделя входа си на сортиран и несортиран регион и итеративно свива несортирания регион, като извлича най-големия елемент и го премества в сортирания регион.
 Стъпки за внедряване на Quicksort (в нарастващ ред): 
Изградете максимална купчина с масива за сортиране
В тази точкаt, най-големият елемент се съхранява в основата на купчината. Заменете го с последния елемент от купчината и намалете размера на купчината с 1. И накрая, нагрейте корена на дървото
Повторете горните стъпки, докато размерът на купчината е по-голям от 1
Ето псевдокод, представляващ алгоритъм за сортиране на купчини.
Хепсорт (a като масив) за (i = n / 2 - 1) до i> = 0 heapify (a, n, i) за i = n-1 до 0 суап (a [0], a [i]) heapify (a, i, 0) край за край за heapify (a като масив, n като int, i като int) най-голям = i // Инициализиране на най-големия като корен int l eft = 2 * i + 1 // вляво = 2 * i + 1 int вдясно = 2 * i + 2 // вдясно = 2 * i + 2 if (ляво [най-голямо]) най-голямо = ляво ако (вдясно [най-голямо]) най-голямо = дясно ако (най-голямо! = I) суап ( a [i], A [най-голям]) Heapify (a, n, най-голям) край heapify
Освен тях има и други алгоритми за сортиране, които не са толкова известни като Introsort, Counting Sort и др. Преминавайки към следващия набор от алгоритми в тази статия „Структури на данни и алгоритми“, нека разгледаме алгоритмите за търсене.
 Търсене на алгоритми в Java 
Търсенето е едно от най-често срещаните и често извършвани действия в обикновените бизнес приложения. Алгоритмите за търсене са алгоритми за намиране на елемент с определени свойства сред колекция от елементи. Нека разгледаме два от най-често използваните алгоритми за търсене.
 Алгоритъм за линейно търсене в Java 
Линейното търсене или последователното търсене е най-простият алгоритъм за търсене. Той включва последователно търсене на елемент в дадената структура от данни, докато или елементът бъде намерен, или до края на структурата. Ако елементът бъде намерен, тогава се връща местоположението на елемента, в противен случай алгоритъмът връща NULL.
Ето псевдокод, представляващ линейно търсене в Java:
процедура linear_search (a [], стойност) за i = 0 до n-1, ако a [i] = стойност след това отпечатва 'Found' return i end if print 'Not found' end за край linear_search
Това еалгоритъм за груба сила.Въпреки че със сигурност е най-простият, определено не е най-често срещаният поради неговата неефективност. Сложността във времето на линейното търсене е НА) .
 Алгоритъм на двоично търсене в Java 
Бинарното търсене, известно още като логаритмично търсене, е алгоритъм за търсене, който намира позицията на целева стойност във вече сортиран масив. Той разделя входящата колекция на равни половини и елементът се сравнява със средния елемент на списъка. Ако елементът бъде намерен, търсенето завършва там. В противен случай продължаваме да търсим елемента, като разделяме и избираме подходящия дял на масива, въз основа на това дали целевият елемент е по-малък или по-голям от средния елемент.
Ето псевдокод, представляващ двоично търсене в Java:
Процедура binary_search сортиран масив n размер на масива x стойност, която трябва да се търси lowerBound = 1 upperBound = n, докато x не е намерен, ако upperBound
Търсенето приключва, когато upperBound (нашият указател) минава покрай lowerBound (последния елемент), което означава, че сме търсили целия масив и елементът не присъства.Това е най-често използваните алгоритми за търсене главно поради бързото си време за търсене. Сложността във времето на бинарното търсене е НА) което е значително подобрение на НА) сложност във времето на линейно търсене.
Това ни води до края на тази статия „Структури на данни и алгоритми в Java“. Покрих една от най-фундаменталните и важни теми на Java.Надявам се, че сте наясно с всичко споделено с вас в тази статия.
  Уверете се, че практикувате възможно най-много и връщате опита си.   
 Вижте    от Edureka, доверена компания за онлайн обучение с мрежа от над 250 000 доволни учащи, разпространени по целия свят. Ние сме тук, за да ви помогнем във всяка стъпка по вашето пътуване, за да станете освен тези въпроси за интервю за Java, измислим учебна програма, предназначена за студенти и професионалисти, които искат да бъдат Java Developer. 
 Имате въпрос към нас? Моля, споменете го в раздела за коментари на този „Структури на данни и алгоритми в Java“  статия и ние ще се свържем с вас възможно най-скоро.