Врхунске структуре података и алгоритми у Јави које треба да знате



Овај блог о Структурама података и алгоритмима на Јави помоћи ће вам да разумете све главне структуре података и алгоритме на Јави.

Ако бих морао да изаберем најважнију тему у развоју софтвера, то би биле структуре података и алгоритми. Можете га сматрати основним алатом доступним сваком рачунарском програмеру. Током програмирања користимо структуре података за чување и организовање података и алгоритми за манипулисање подацима у тим структурама. Овај чланак садржи детаљан преглед свих уобичајених структура података и алгоритама у како би се читаоцима омогућило да се добро опреме.

У наставку су наведене теме о којима се говори у овом чланку:





Структуре података у Јави

Структура података је начин чувања и организовања података у рачунару тако да се могу ефикасно користити. Пружа средство за ефикасно управљање великим количинама података. А ефикасне структуре података су кључне за дизајнирање ефикасних алгоритама.

Уу овом чланку „Структуре података и алгоритми у Јави“ покрићемо основне структуре података као што су:



Проверимо сваки од њих.

Линеарне структуре података у Јави

Линеарне структуре података у су они чији су елементи секвенцијални и поредани на начин да: постоји само један први елемент и има само један следећи елемент , постоји само једна последњи елемент и има само један претходни елемент , док сви остали елементи имају а следећи и а Претходна елемент.

Низови

Ан низ је линеарна структура податакапредставља групу сличних елемената којима се приступа индексом. Пре складиштења података мора се навести величина низа. Доље су наведена својства низа:



  • Сваки елемент у низу је истог типа података и исте је величине
  • Елементи низа чувају се на суседним меморијским локацијама, а први елемент почиње на најмањој меморијској локацији
  • Елементима низа може се насумично приступити
  • Структура података низа није потпуно динамична

Низови - Едурека

На пример , можда ћемо желети да видео игра прати првих десет резултата за ту игру. Уместо да користите десет различитих Променљиве за овај задатак бисмо могли да користимо једно име за целу групу и да се индексним бројевима позивамо на високе оцене у тој групи.

Повезана листа

ДО је линеарна структура података са колекцијом више чворова, где еацх елемент чува сопствене податке и показивач на локацију следећег елемента. Последња карика на повезаној листи показује на нулу, што указује на крај ланца. Елемент на повезаној листи назива се а чвор . Први чвор се назива глава .Позива се последњи чвортхе Реп .

Врсте повезане листе

Појединачно повезана листа (једносмерна)

Двоструко повезана листа (двосмерна)

Кружно повезана листа

Ево једноставног примера: Замислите повезану листу попут ланца спајалица повезаних заједно. Можете лако додати још једну спајалицу на врх или на дно. Чак је и брзо уметнути један у средину. Потребно је само да искључите ланац у средини, додате нову спајалицу, а затим поново повежете другу половину. Повезана листа је слична.

Стацкс

Гомила, апстрактна структура података, је збирка предмета који се убацују и уклањају према задњи-у-првом-изашао (ЛИФО) принцип. Објекти се могу уметнути у стог у било ком тренутку, али у последње време може се уклонити само последњи уметнути (односно „последњи“) објекат.Испод су наведена својства стека:

  • То је поредана листа у којојуметање и брисање може се извршити само на једном крају који се назива врх
  • Рекурзивна структура података са показивачем на горњи елемент
  • Следи задњи-у-првом-изашао (ЛИФО) принцип
  • Подржава две најосновније методе
    • пусх (е): Уметните елемент е, на врх стека
    • поп (): Уклоните и вратите горњи елемент на стеку

Практични примери стека укључују преокретање речи,да провери исправност заградениз,применом бацк функционалности у прегледачима и многим другим.

Редови

су такође друга врста апстрактне структуре података. За разлику од стека, ред је колекција објеката који се убацују и уклањају према први у првом (ФИФО) принцип. Односно, елементи се могу уметнути у било ком тренутку, али у сваком тренутку може се уклонити само онај елемент који је најдуже био у реду.Испод су наведена својства реда:

  • Често се назива и први улази - први излази листа
  • Подржава две најосновније методе
    • ред (е): Уметните елемент е, на задњи реда
    • декуеуе (): Уклоните и вратите елемент из предњи реда

Редови се користе уасинхрони пренос података између два процеса, заказивање ЦПУ-а, заказивање диска и друге ситуације у којима се ресурси деле између више корисника и послужују по принципу „први дође први“. Следеће у овом чланку „Структуре података и алгоритми у Јави“ имамо хијерархијске структуре података.

Хијерархијске структуре података у Јави

Бинарно дрво

Бинарно дрво јехијерархијске структуре података стабла у којима сваки чвор има највише двоје деце , који се називају лево дете и право дете . Свако бинарно стабло има следеће групе чворова:

  • Коријенски чвор: То је највиши чвор и често се назива главним чворомјер се до свих осталих чворова може доћи из корена
  • Лево подстабло, које је такође бинарно стабло
  • Десно подстабло, које је такође бинарно стабло

Доље су наведена својства бинарног стабла:

  • Бинарно стабло се може прећи на два начина:
    • Дубина Прво прелажење : Редослед (лево-коријен-десно), преднаруџба (коријен-лијево-десно) и редослед (лево-десно-корен)
    • Ширина прво прелазак : Прелазак редоследа нивоа
  • Сложеност времена преласка дрвета: О (н)
  • Максималан број чворова на нивоу „л“ = 2л-1.

Примене бинарних стабала укључују:

Водич за Мицрософт СКЛ за почетнике
  • Користи се у многим апликацијама за претрагу где подаци непрекидно улазе / излазе
  • Као ток рада за компоновање дигиталних слика за визуелне ефекте
  • Користи се у скоро сваком рутеру широке пропусности за чување столова рутера
  • Такође се користи у бежичном умрежавању и алокацији меморије
  • Користи се у алгоритмима компресије и многим другим

Бинарна гомила

Бинари Хеап је комплетанбинарно стабло, који одговара својству гомиле. Једноставно реченоје варијација бинарног стабла са следећим својствима:

  • Хеап је комплетно бинарно стабло: За дрво се каже да је потпуно ако су сви његови нивои, осим вероватно најдубљег, комплетни. Т.његово својство Бинари Хеап чини погодним за чување у .
  • Прати својство гомиле: Бинарна гомила је или а Мин-Хеап или а Мак-Хеап .
    • Мин бинарна гомила: Ф.или сваки чвор у гомили, вредност чвора је мање или једнако вредности деце
    • Максимална бинарна гомила: Ф.или сваки чвор у гомили, вредност чвора је већи или једнак вредности деце

Популарне примене бинарне хрпе укључујупримена ефикасних редова приоритета, ефикасно проналажење к најмањих (или највећих) елемената у низу и још много тога.

Хасх табеле

Замислите да имате објект и желите да му доделите кључ да би претраживање било врло лако. Да бисте сачували тај пар кључ / вредност, можете користити једноставан низ попут структуре података где се кључеви (цели бројеви) могу директно користити као индекс за чување вредности података. Међутим, у случајевима када су тастери превелики и не могу се директно користити као индекс, користи се техника која се назива хеширање.

У хеширању се велики кључеви претварају у мале кључеве помоћу хеш функције . Вредности се затим чувају у структури података која се називадо хеш сто. Табела хеширања је структура података која примењује речник АДТ, структуру која може мапирати јединствене кључеве у вредности.

Генерално, хеш табела има две главне компоненте:

  1. Низ канта: Поље сегмента за хеш таблицу је низ А величине Н, где се свака ћелија А сматра „сефом“, односно колекцијом парова кључ / вредност. Цели број Н дефинише капацитет низа.
  2. Хасх функција: Било која функција је која пресликава сваки кључ к на нашој мапи на цео број у опсегу [0, Н & минус 1], где је Н капацитет сеф-низа за ову табелу.

Када ставимо објекте у хештабле, могуће је да различити објекти могу имати исти хасхцоде. Ово се назива а судар . Да би се решили судар, постоје технике попут ланчаног и отвореног адресирања.

Ово су неке основне и најчешће коришћене структуре података у Јави. Сада када сте свесни сваког од њих, можете почети да их примените у свом . Овим смо завршили први део овог чланка „Структуре података и алгоритми у Јави“. У следећем делу ћемо научити о томеосновни алгоритми и како их користити у практичним апликацијама попут сортирања и претраживања, подели и освоји, похлепни алгоритми, динамичко програмирање.

Алгоритми у Јави

Историјски коришћени као алат за решавање сложених математичких прорачуна, алгоритми су дубоко повезани са рачунарством, а посебно са структурама података. Алгоритам је низ упутстава који описује начин решавања одређеног проблема у ограниченом временском периоду. Они су представљени на два начина:

  • Графикони токова - То јевизуелни приказ тока управљања алгоритма
  • Псеудоцоде - Тоје текстуални приказ алгоритма који апроксимира коначни изворни код

Белешка: Перформансе алгоритма мере се на основу временске сложености и сложености простора. Сложеност било ког алгоритма углавном зависи од проблема и од самог алгоритма.

Истражимо две главне категорије алгоритама у Јави, а то су:

Сортирање алгоритама у Јави

Алгоритми за сортирање су алгоритми који стављају елементе листе у одређени редослед. Најчешће коришћени редови су нумерички и лексикографски редослед. У овом чланку „Структуре података и алгоритми“ омогућава се истраживање неколико алгоритама за сортирање.

Сортирање облачића на Јави

Сортирање мехурића, које се често назива сортирањем које тоне, најједноставнији је алгоритам сортирања. Узастопно корача кроз листу да би се сортирала, упоређује сваки пар суседних елемената и замењује их ако су у погрешном редоследу.Име мехурића добило је јер филтрира елементе на врху низа, попут мехурића који плутају по води.

Евопсеудокод који представља алгоритам сортирања мехурића (растући контекст сортирања).

а [] је низ величине Н бегин БубблеСорт (а []) декларише цео број и, ј за и = 0 до Н - 1 за ј = 0 до Н - и - 1 ако је а [ј]> а [ј + 1 ] затим замените [ј], [ј + 1] крај ако крај за повратак а крај БубблеСорт

Овај код наручује једнодимензионални низ од Н података у узлазном редоследу. Спољна петља чини да Н-1 пролази преко низа. Сваки пролаз користи унутрашњу петљу за размену ставки података тако да се следећа најмања ставка података „облачи“ према почетку низа. Али проблем је у томе што алгоритму треба један читав пролаз без икакве замјене да би знао да је листа сортирана.

Најгора и просечна сложеност случаја: О (н * н). Најгори случај се јавља када се низ сортира уназад.

Временска сложеност најбољег случаја: На). Најбољи случај се дешава када је низ већ сортиран.

Сортирање избора на Јави

Сортирање по избору је комбинација претраживања и сортирања. Алгоритам сортира низ поновним проналажењем минималног елемента (узимајући у обзир узлазни поредак) из несортираног дела и постављањем на одговарајући положај у низу.

Ево псеудокода који представља алгоритам сортирања избора (растући контекст сортирања).

а [] је низ величине Н бегин СелецтионСорт (а []) за и = 0 до н - 1 / * постави тренутни елемент као минимум * / мин = и / * пронађи минимални елемент * / за ј = и + 1 до н ако листа [ј]

Као што можете да схватите из кода, број пута проласка сортирања кроз низ је један мањи од броја ставки у низу. Унутрашња петља проналази следећу најмању вредност, а спољна петља поставља ту вредност на њено правилно место. Сортирање избора никада не врши више од замене од О (н) и може бити корисно када је уписивање у меморију скупа операција.

Сложеност времена: На2) пошто постоје две угнежђене петље.

Помоћни простор: Или (1).

Сортирање уметања на Јави

Сортирање уметања је једноставан алгоритам за сортирање који се креће кроз листу трошећи по један улазни елемент и гради коначни сортирани низ. Веома је једноставно и ефикасније на мањим скуповима података. То је стабилна техника сортирања на месту.

Ево псеудокода који представља алгоритам сортирања уметања (растући контекст сортирања).

а [] је низ величине Н бегин ИнсертионСорт (а []) за и = 1 до Н кључ = а [и] ј = и - 1 док (ј> = 0 и а [ј]> тастер0 а [ј + 1] = к [ј] ј = ј - 1 крај док је [ј + 1] = кључни крај за крај ИнсертионСорт

Као што можете да разумете из кода, алгоритам сортирања уметањауклања један елемент из улазних података, проналази локацију којој припада унутар сортиране листе и тамо је убацује. Понавља се све док ниједан елемент уноса не остане несортиран.

Најбољи случај: Најбољи случај је када је улаз низ који је већ сортиран. У овом случају сортирање уметања има линеарно време извођења (тј. & Тхета (н)).

Најгори случај: Најједноставнији унос у најгорем случају је низ сортиран обрнутим редоследом.

именски простори у ц ++

КуицкСорт у Јави

Куицксорт алгоритам је брз, рекурзиван, нестабилан алгоритам сортирања који ради по принципу подели и освоји. Одабире елемент као стожер и раздваја дати низ око тог изабраног пивота.

Кораци за примену брзог сортирања:

  1. Изаберите одговарајућу „тачку вешања“.
  2. Поделите листе на две листена основу овог стожног елемента. Сваки елемент који је мањи од пивот елемента налази се на левој листи, а сваки већи елемент налази се на десној листи. Ако је елемент једнак осовинском елементу, онда може ићи на било коју листу. То се назива операција партиције.
  3. Рекурзивно сортирајте сваку мању листу.

Ево псеудокода који представља алгоритам Куицксорт.

КуицкСорт (А као низ, низак као инт, висок као инт) {иф (низак

У горњем псеудокоду, подела() функција врши операцију партиције и Куицксорт () функција више пута позива партицијску функцију за сваку мању генерисану листу. Сложеност брзог сортирања у просечном случају је & Тхета (н лог (н)), а у најгорем случају је & Тхета (н2).

Споји сортирање у Јави

Мергесорт је брз, рекурзиван, стабилан алгоритам сортирања који такође ради по принципу подели и освоји. Слично као брзи сортирање, сортирање спајањем дели листу елемената на две листе. Ове листе се сортирају независно и затим комбинују. Током комбинације листа, елементи се убацују (или спајају) на право место на листи.

Ево псеудокода који представља алгоритам сортирања стапања.

поступак МергеСорт (а као низ) ако (н == 1) врати вар л1 као низ = а [0] ... а [н / 2] вар л2 као низ = а [н / 2 + 1] ... а [н] л1 = мергесорт (л1) л2 = мергесорт (л2) ретурн мерге (л1, л2) поступак завршетка поступка спајање (а као низ, б као низ) вар ц као низ док (а и б имају елементе) иф ( а [0]> б [0]) додај б [0] на крај ц уклони б [0] из б елсе додај а [0] на крај ц уклони [0] са краја иф енд вхиле вхиле (а има елементе) додајте а [0] на крај ц уклоните а [0] са краја док док (б има елементе) додајте б [0] на крај ц уклоните б [0] са б краја док се враћа ц завршни поступак

сортирање спајањем() функција дели листу на два позива сортирање спајањем() на овим листама одвојено, а затим их комбинује слањем као параметре у функцију мерге ().Алгоритам има сложеност О (н лог (н)) и има широк спектар примена.

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

Хеапсорт је алгоритам сортирања заснован на поређењуСтруктура података бинарне хрпе. Можете то сматрати побољшаном верзијом избора, гдедели свој улаз на сортирани и несортирани регион и итеративно смањује несортирани регион извлачењем највећег елемента и премештањем у сортирани регион.

Кораци за примену Куицксорт-а (у порасту):

  1. Направите максималну гомилу помоћу низа за сортирање
  2. На овом местут, највећи предмет се чува у корену гомиле. Замените је последњом ставком гомиле и смањите величину гомиле за 1. На крају, појачајте корен стабла
  3. Понављајте горње кораке док величина гомиле не буде већа од 1

Ево псеудокода који представља алгоритам сортирања гомиле.

Хеапсорт (а као низ) за (и = н / 2 - 1) до и> = 0 хеапифи (а, н, и) за и = н-1 до 0 свап (а [0], а [и]) хеапифи (а, и, 0) крај за крај за гомилање (а као низ, н као инт, и као инт) највећи = и // Покрени највећи као корен инт л ефт = 2 * и + 1 // лево = 2 * и + 1 инт десно = 2 * и + 2 // десно = 2 * и + 2 ако (лево [највеће]) највеће = лево ако (десно [највеће]) највеће = десно ако (највеће! = И) замените ( а [и], А [највећи]) Хеапифи (а, н, највећи) крај хеапифи

Осим њих, постоје и други алгоритми за сортирање који нису толико познати, попут Интросорт, Цоунтинг Сорт итд. Прелазећи на следећи скуп алгоритама у овом чланку „Структуре података и алгоритми“, истражимо алгоритме претраживања.

Претраживање алгоритама на Јави

Претраживање је једна од најчешћих и најчешће извођених радњи у редовним пословним апликацијама. Алгоритми претраге су алгоритми за проналажење предмета са одређеним својствима међу колекцијом предмета. Истражимо два најчешће коришћена алгоритма за претрагу.

Линеарни алгоритам претраживања на Јави

Линеарно претраживање или секвенцијално претраживање је најједноставнији алгоритам претраживања. Укључује секвенцијално тражење елемента у датој структури података све док се не пронађе елемент или не постигне крај структуре. Ако је елемент пронађен, тада се враћа локација ставке, у супротном алгоритам враћа НУЛЛ.

Ево псеудокода који представља Линеарно претраживање на Јави:

процедура линеар_сеарцх (а [], валуе) фор и = 0 то н-1 иф а [и] = валуе тхен принт 'Фоунд' ретурн и енд иф принт 'Нот фоунд' крај за крај линеар_сеарцх

То јеалгоритам грубе силе.Иако је свакако најједноставније, дефинитивно није најчешће због своје неефикасности. Сложеност времена линеарног претраживања је НА) .

Бинарни алгоритам претраживања на Јави

Бинарна претрага, позната и као логаритамска претрага, алгоритам је претраживања који проналази положај циљне вредности унутар већ сортираног низа. Збирку уноса дели на једнаке половине и ставка се упоређује са средњим елементом листе. Ако је елемент пронађен, претрага се тамо завршава. Иначе, настављамо да тражимо елемент дељењем и одабиром одговарајуће партиције низа, на основу тога да ли је циљни елемент мањи или већи од средњег елемента.

Ево псеудокода који представља бинарну претрагу на Јави:

Процедура бинари_сеарцх сортирани низ н величина низа к вредност за претрагу ловерБоунд = 1 упперБоунд = н док к није пронађен ако упперБоунд

Претрага се завршава када горња граница (наш показивач) пролази поред ловерБоунд (последњи елемент), што значи да смо претражили читав низ, а елемент није присутан.То је најчешће коришћени алгоритам претраживања првенствено због свог брзог времена претраживања. Временска сложеност бинарне претраге је НА) што је значајно побољшање на НА) временска сложеност линеарне претраге.

Ово нас доводи до краја овог чланка „Структуре података и алгоритми у Јави“. Обрадио сам једну од најважнијих и најважнијих тема Јаве.Надам се да вам је јасно све што је са вама подељено у овом чланку.

Обавезно вежбајте што је више могуће и вратите своје искуство.

Погледајте Едурека, поуздана компанија за учење на мрежи са мрежом од више од 250.000 задовољних ученика раширених широм света. Овде смо да вам помогнемо у сваком кораку на вашем путовању, јер поред тога што постављате питања о јава интервјуу, осмислили смо наставни план и програм који је дизајниран за студенте и професионалце који желе да буду Јава програмери.

Имате питање за нас? Молимо вас да га поменете у одељку за коментаре овог „Структуре података и алгоритми у Јави“ чланак и јавићемо вам се у најкраћем могућем року.