Principals estructures de dades i algorismes de Java que heu de conèixer

Si hagués de triar el tema més important en el desenvolupament de programari, serien estructures de dades i algorismes. Podeu pensar-ho com l’eina fonamental disponible per a tots els programadors d’ordinadors. Mentre programem, fem servir estructures de dades per emmagatzemar i organitzar dades, i algoritmes per manipular les dades en aquestes estructures. Aquest article conté una revisió detallada de totes les estructures de dades i algorismes comuns a per permetre que els lectors estiguin ben equipats.

A continuació s’enumeren els temes tractats en aquest article:

• Estructures de dades a Java
  • Estructures de dades lineals
  • Estructures de dades jeràrquiques
• Algorismes a Java
  • Algorismes d'ordenació
  • Cerca d'algorismes

Estructures de dades a Java

Una estructura de dades és una forma d’emmagatzemar i organitzar les dades en un ordinador perquè es puguin utilitzar de manera eficient. Proporciona un mitjà per gestionar grans quantitats de dades de manera eficient. I les estructures de dades eficients són claus per dissenyar algoritmes eficients.

Enen aquest article 'Estructures de dades i algorismes a Java', anem a tractar estructures bàsiques de dades com ara:

• Estructures de dades lineals
  • Llista enllaçada
  • Piles
  • Cues

• Estructures de dades jeràrquiques
  • Arbres binaris
  • Cúmuls
  • Taules de hash

Vegem cadascun d’ells.

Estructures de dades lineals a Java

Estructures de dades lineals a són aquells els elements dels quals són seqüencials i ordenats de manera que: només n’hi hagi un primer element i només en té un següent element , només n'hi ha un darrer element i només en té un element anterior , mentre que la resta d’elements tenen un Pròxim i a anterior element.

Matrius

An matriu és una estructura de dades linealque representa un grup d'elements similars, als quals s'accedeix per índex. Cal proporcionar la mida d’una matriu abans d’emmagatzemar les dades. A continuació s’enumeren les propietats d’una matriu:

• Cada element d'una matriu té el mateix tipus de dades i té la mateixa mida
• Els elements de la matriu s’emmagatzemen a ubicacions de memòria contigües i el primer element comença a la ubicació de memòria més petita
• Es pot accedir de manera aleatòria als elements de la matriu
• L'estructura de dades de la matriu no és completament dinàmica

Per exemple , és possible que vulguem que un videojoc faci un seguiment de les deu millors puntuacions d’aquest joc. En lloc d’utilitzar deu diferents variables per a aquesta tasca, podríem utilitzar un nom únic per a tot el grup i utilitzar números d'índex per referir-nos a les puntuacions més altes d'aquest grup.

Llista enllaçada

A és una estructura de dades lineal amb la col·lecció de múltiples nodes, on eL'element ach emmagatzema les seves pròpies dades i un punter a la ubicació de l'element següent. L'últim enllaç d'una llista enllaçada apunta a nul, indicant el final de la cadena. Un element d’una llista enllaçada s’anomena a node . El primer node es diu cap .Es diu l’últim nodeel cua .

Tipus de llista enllaçada

Llista enllaçada individualment (unidireccional)

Llista doblement enllaçada (bidireccional)

Llista enllaçada circular

Aquí teniu un exemple senzill: Imagineu-vos una llista enllaçada com una cadena de clips que s’uneixen entre si. Podeu afegir fàcilment un altre clip a la part superior o inferior. Fins i tot és ràpid inserir-ne un al mig. Tot el que heu de fer és desconnectar la cadena del centre, afegir el nou clip i tornar a connectar l’altra meitat. Una llista enllaçada és similar.

Piles

Pila, una estructura de dades abstracta, és una col · lecció de objectes que s'insereixen i s'eliminen segons el fitxer darrera entrada-primera sortida (LIFO) principi. Els objectes es poden inserir en una pila en qualsevol moment del temps, però només es pot eliminar l’objecte inserit més recentment (és a dir, “darrer”) en qualsevol moment.A continuació s’enumeren les propietats d’una pila:

• És una llista ordenada en quèla inserció i la supressió només es poden realitzar en un extrem que s'anomena superior
• Estructura de dades recursives amb un punter al seu element superior
• Segueix el darrera entrada-primera sortida (LIFO) principi
• Admet dos mètodes fonamentals
  • push (e): Inseriu l'element e, a la part superior de la pila
  • pop (): traieu i torneu l'element superior de la pila

Els exemples pràctics de la pila inclouen quan inverteix una paraula,per comprovar la correcció de parèntesisseqüència,implementant la funcionalitat de retorn als navegadors i molts més.

Cues

també són un altre tipus d’estructura de dades abstractes. A diferència d’una pila, la cua és una col·lecció d’objectes que s’insereixen i s’eliminen segons el fitxer primer-en-primer-sortida (FIFO) principi. És a dir, es poden inserir elements en qualsevol moment del temps, però només es pot eliminar en qualsevol moment l’element que ha estat més temps a la cua.A continuació s’enumeren les propietats d’una cua:

java doble a int ronda

• Sovint anomenat primer a entrar, primer a sortir llista
• Admet dos mètodes fonamentals
  • enqueue (e): Inseriu l'element e al fitxer posterior de la cua
  • dequeue (): traieu i torneu a l'element de frontal de la cua

Les cues s'utilitzen al fitxertransferència asíncrona de dades entre dos processos, programació de CPU, programació de discs i altres situacions en què els recursos es comparteixen entre diversos usuaris i es serveixen segons el servidor primer per arribar. A continuació, en aquest article 'Estructures de dades i algorismes a Java', tenim estructures de dades jeràrquiques.

Estructures de dades jeràrquiques a Java

Arbre binari

Binary Tree és un fitxerestructures de dades de l'arbre jeràrquic en què cada node té com a màxim dos fills , que es coneixen com a nen esquerre i la nen correcte . Cada arbre binari té els grups de nodes següents:

• Node arrel: és el node superior i sovint es coneix com el node principalperquè es pot accedir a la resta de nodes des de l'arrel
• Subarbre esquerre, que també és un arbre binari
• Subarbre dret, que també és un arbre binari

A continuació s’enumeren les propietats d’un arbre binari:

• Un arbre binari es pot recórrer de dues maneres:
  • Primera travessia de profunditat : Per ordre (esquerra-arrel-dreta), preordenació (arrel-esquerra-dreta) i postordre (esquerra-dreta-arrel)
  • Amplada Primera Traversal : Traversal d’ordre de nivell
• Complexitat temporal de la travessia d'arbres: O (n)
• El nombre màxim de nodes al nivell ‘l’ = 2^l-1.

Les aplicacions dels arbres binaris inclouen:

• S'utilitza en moltes aplicacions de cerca on les dades entren o surten constantment
• Com a flux de treball per a la composició d'imatges digitals per a efectes visuals
• S’utilitza en gairebé tots els encaminadors d’alt ample de banda per emmagatzemar taules d’encaminadors
• També s'utilitza en xarxes sense fils i assignació de memòria
• S'utilitza en algorismes de compressió i molts més

Munt binari

Binary Heap és un completarbre binari, que respon a la propietat del munt. En termes simplesés una variació d'un arbre binari amb les propietats següents:

• Heap és un arbre binari complet: Es diu que un arbre està complet si tots els seus nivells, excepte possiblement els més profunds, són complets. Tla seva propietat de Binary Heap el fa adequat per emmagatzemar-lo en un fitxer .
• Segueix la propietat de l'emmagatzematge dinàmic: Un munt binari és un Min-Heap o a Max-Heap .
  • Munt binari mínim: Fo cada node d’un munt, el valor del node és menor o igual a valors dels nens
  • Munt binari màxim: Fo cada node d’un munt, el valor del node és superior o igual a valors dels nens

Entre les aplicacions més populars de l'emmagatzematge binari s'inclouenimplementant cues de prioritat eficients, trobant els k elements més petits (o més grans) d'una matriu i molts més.

Taules de hash

Imagineu-vos que en teniu objecte i voleu assignar-hi una clau perquè la cerca sigui molt fàcil. Per emmagatzemar aquest parell clau / valor, podeu utilitzar una matriu simple com una estructura de dades on les claus (enters) es poden utilitzar directament com a índex per emmagatzemar valors de dades. Tanmateix, en els casos en què les tecles són massa grans i no es poden utilitzar directament com a índex, s’utilitza una tècnica anomenada hash.

En el hash, les tecles grans es converteixen en tecles petites mitjançant l'ús funcions de hash . Els valors s'emmagatzemen en una estructura de dades anomenadaa taula de hash. Una taula de hash és una estructura de dades que implementa un diccionari ADT, una estructura que pot assignar claus úniques a valors.

En general, una taula de hash té dos components principals:

1. Matriu de cubells: Una matriu de dipòsit per a una taula de hash és una matriu A de mida N, on es considera que cada cel·la d'A és un 'dipòsit', és a dir, una col·lecció de parells clau-valor. L'enter N defineix la capacitat de la matriu.
2. Funció Hash: És qualsevol funció que assigna cada tecla k del nostre mapa a un nombre enter de l'interval [0, N i menys 1], on N és la capacitat de la matriu de dipòsit per a aquesta taula.

Quan posem objectes a una taula d’etiquetes, és possible que diferents objectes tinguin el mateix codi de hash. Això s’anomena a col·lisió . Per fer front a la col·lisió, hi ha tècniques com l’encadenament i l’adreçament obert.

Per tant, aquestes són algunes de les estructures de dades bàsiques i les que s’utilitzen amb més freqüència a Java. Ara que ja sou conscients de cadascun d’ells, podeu començar a implementar-los al vostre . Amb això, hem completat la primera part d’aquest article sobre ‘Estructures de dades i algoritmes a Java’. A la següent part, coneixeremalgorismes bàsics i com utilitzar-los en aplicacions pràctiques com ara classificar i buscar, dividir i conquerir, algorismes codiciosos, programació dinàmica.

Algorismes a Java

Històricament utilitzat com a eina per resoldre càlculs matemàtics complexos, els algoritmes estan profundament connectats amb la informàtica i, en particular, amb les estructures de dades. Un algorisme és una seqüència d’instruccions que descriu una manera de resoldre un problema específic en un període de temps finit. Es representen de dues maneres:

• Organigrames - És unrepresentació visual del flux de control d’un algorisme
• Pseudocodi - Ésés una representació textual d'un algorisme que s'aproxima al codi font final

Nota: El rendiment de l'algorisme es mesura en funció de la complexitat del temps i la complexitat de l'espai. Majoritàriament, la complexitat de qualsevol algorisme depèn del problema i del mateix algorisme.

Explorem les dues categories principals d’algoritmes a Java, que són:

• Classificació d’algorismes a Java
• Cerca d'algorismes a Java

Classificació d’algorismes a Java

Els algorismes d’ordenació són algorismes que posen els elements d’una llista en un ordre determinat. Els ordres més utilitzats són l’ordre numèric i l’ordre lexicogràfic. En aquest article sobre 'Estructures i algoritmes de dades', podeu explorar alguns algorismes d'ordenació.

com utilitzar l'àtom per a Python

Sort de bombolles a Java

Bubble Sort, sovint conegut com a sorting sinking, és l'algorisme d'ordenació més senzill. Recorre repetidament la llista per ordenar, compara cada parell d'elements adjacents i els canvia si estan en un ordre incorrecte.El tipus de bombolla rep el seu nom perquè filtra els elements a la part superior de la matriu, com les bombolles que suren a l’aigua.

Aquí hi hapseudocodi que representa l’algorisme de classificació de bombolles (context de classificació ascendent).

a [] és una matriu de mida N començar BubbleSort (a []) declarar enter i, j per i = 0 a N - 1 per a j = 0 a N - i - 1 si a [j]> a [j + 1 ] canvieu un [j], un [j + 1] final si final per retornar un final BubbleSort

Aquest codi ordena una matriu unidimensional de N elements de dades en ordre ascendent. Un bucle exterior fa que N-1 passi per sobre de la matriu. Cada passada utilitza un bucle intern per intercanviar ítems de dades de manera que el següent ítem de dades més petit 'bombolla' cap al començament de la matriu. Però el problema és que l'algorisme necessita una passada sencera sense cap intercanvi per saber que la llista està ordenada.

La pitjor i mitjana complexitat del cas: O (n * n). El pitjor dels casos es produeix quan una matriu està ordenada inversament.

Millor complexitat de casos: O (n). El millor cas es dóna quan una matriu ja està ordenada.

Selecció Ordena a Java

L’ordenació per selecció és una combinació tant de cerca com d’ordenació. L'algorisme ordena una matriu trobant repetidament l'element mínim (tenint en compte l'ordre ascendent) de la part no classificada i posant-lo en una posició adequada a la matriu.

Aquí hi ha un pseudocodi que representa l’algorisme d’ordenació de selecció (context de classificació ascendent).

a [] és una matriu de mida N begin SelectionSort (a []) per a i = 0 a n - 1 / * defineix l'element actual com a mínim * / min = i / * troba l'element mínim * / per a j = i + 1 a n si llista [j]
Com podeu entendre pel codi, el nombre de vegades que l'ordenació passa per la matriu és inferior al nombre d'elements de la matriu. El bucle intern troba el següent valor més petit i el bucle exterior situa aquest valor a la seva ubicació correcta. La selecció no fa mai més que O (n) swaps i pot ser útil quan l'escriptura de memòria és una operació costosa.
 Complexitat temporal: O (n2) ja que hi ha dos bucles imbricats.
 Espai auxiliar: O (1).
 Ordre d'inserció a Java 
Insertion Sort és un simple algorisme d'ordenació que recorre la llista consumint un element d'entrada a la vegada i crea la matriu ordenada final. És molt senzill i més eficaç en conjunts de dades més petits. És una tècnica de classificació estable i al seu lloc.
Aquí hi ha un pseudocodi que representa l’algorisme d’ordenació per inserció (context de classificació ascendent).
a [] és una matriu de mida N begin InsertionSort (a []) per a i = 1 a N clau = a [i] j = i - 1 mentre (j> = 0 i a [j]> clau0 a [j + 1] = x [j] j = j - 1 extrem mentre que un [j + 1] = final clau per al final InsertionSort
Com podeu entendre pel codi, l'algorisme d'ordenació per insercióelimina un element de les dades d'entrada, troba la ubicació que pertany a la llista ordenada i hi insereix. Es repeteix fins que no queden elements d'entrada sense classificar.
 Millor cas: El millor cas és quan l’entrada és una matriu que ja està ordenada. En aquest cas, l’ordenació per inserció té un temps d’execució lineal (és a dir, & Theta (n)).
 Pitjor dels casos:  L'entrada de pitjor cas més simple és una matriu ordenada en ordre invers.
 QuickSort a Java 
L’algorisme Quicksort és un algorisme de classificació ràpid, recursiu i no estable que funciona segons el principi divideix i conquesta. Tria un element com a pivot i particiona la matriu donada al voltant del pivot seleccionat.
 Passos per implementar la classificació ràpida:  
 
Trieu un 'punt de pivot' adequat.
Dividiu les llistes en dues llistesbasat en aquest element pivot. Tots els elements més petits que l’element pivot es col·loquen a la llista esquerra i tots els elements més grans es col·loquen a la llista dreta. Si un element és igual a l’element pivot, pot entrar a qualsevol llista. Això s’anomena operació de partició.
Ordeneu recursivament cadascuna de les llistes més petites. 
Aquí teniu un pseudocodi que representa l’algorisme de Quicksort.
QuickSort (A com a matriu, baix com int, alt com int) {if (baix
Al pseudocodi anterior, partició () la funció realitza una operació de partició i Quicksort () La funció crida repetidament la funció de partició per a cada llista més petita generada. La complexitat de quicksort en el cas mitjà és & Theta (n log (n)) i, en el pitjor dels casos, és & Theta (n2).
 Combina la classificació a Java 
Mergesort és un algorisme de classificació ràpid, recursiu i estable que també funciona segons el principi divideix i conquesta. De manera similar a quicksort, l’ordenació de fusió divideix la llista d’elements en dues llistes. Aquestes llistes s’ordenen de manera independent i després es combinen. Durant la combinació de les llistes, els elements s’insereixen (o combinen) al lloc adequat de la llista.
Aquí teniu un pseudocodi que representa l’algorisme de classificació de combinació.
procedure MergeSort (a as array) if (n == 1) return a var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) retorn merge (l1, l2) procediment final procediment merge (a com a matriu, b com a matriu) var c com a matriu mentre que (a i b tenen elements) si ( a [0]> b [0]) afegiu b [0] al final de c elimineu b [0] de b en cas contrari afegiu a [0] al final de c elimineu a [0] d’un extrem si final mentre està mentre (a té elements) afegiu a [0] al final de c elimineu a [0] d'un extrem mentre que (b té elements) afegiu b [0] al final de c elimineu b [0] de b final mentre torneu c finalitzar el procediment
 mergesort () La funció divideix la llista en dues trucades mergesort () en aquestes llistes per separat i després les combina enviant-les com a paràmetres per a la funció merge ().L’algorisme té una complexitat d’O (n log (n)) i té una àmplia gamma d’aplicacions.
 Ordena en pila a Java 
Heapsort és un algorisme d’ordenació basat en la comparacióEstructura de dades de Heap binari. Podeu pensar-ho en una versió millorada de la selecció de tipus, ondivideix la seva entrada en una regió ordenada i una regió no classificada i, de manera iterativa, redueix la regió no classificada en extreure l'element més gran i traslladar-lo a la regió ordenada.
 Passos per implementar Quicksort (en ordre creixent): 
Creeu un munt màxim amb la matriu d'ordenació
En aquest puntt, l'element més gran s'emmagatzema a l'arrel del munt. Substituïu-lo per l'últim element del munt i reduïu la mida del munt per 1. Finalment, amuntegeu l'arrel de l'arbre
Repetiu els passos anteriors fins que la mida del munt sigui superior a 1
Aquí hi ha un pseudocodi que representa l’algorisme d’ordenació en pila.
Heapsort (a com a matriu) per (i = n / 2 - 1) a i> = 0 heapify (a, n, i) per a i = n-1 a 0 swap (a [0], a [i]) heapify (a, i, 0) extrem per extrem per a heapify (a com a matriu, n com a int, i com a int) més gran = i // Inicialitza més gran com a arrel int l eft = 2 * i + 1 // left = 2 * i + 1 int a la dreta = 2 * i + 2 // a la dreta = 2 * i + 2 si (a l'esquerra un [més gran]) més gran = a l'esquerra si (a la dreta un [més gran]) més gran = a la dreta si (més gran! = I) swap a [i], A [més gran]) Heapify (a, n, més gran) final heapify
A part d’aquests, hi ha altres algoritmes d’ordenació que no són tan coneguts com, per exemple, Introsort, Counting Sort, etc. Passant al següent conjunt d’algoritmes d’aquest article sobre “Estructures i algoritmes de dades”, explorem algorismes de cerca.
 Cerca d'algorismes a Java 
La cerca és una de les accions més freqüents i que es realitzen amb més freqüència en aplicacions comercials habituals. Els algorismes de cerca són algorismes per trobar un element amb propietats especificades entre una col·lecció d’elements. Explorem dos dels algorismes de cerca més utilitzats.
 Algorisme de cerca lineal a Java 
La cerca lineal o cerca seqüencial és l'algorisme de cerca més senzill. Implica la cerca seqüencial d'un element a l'estructura de dades donada fins que es troba l'element o s'arriba al final de l'estructura. Si es troba l'element, es torna la ubicació de l'element, en cas contrari l'algoritme retorna NULL.
Aquí teniu un pseudocodi que representa la cerca lineal a Java:
procedure linear_search (a [], value) for i = 0 to n-1 if a [i] = value then print 'Found' return i end if print 'No trobat' final per al final linear_search
És unalgorisme de força bruta.Tot i que certament és el més senzill, definitivament no és el més comú, a causa de la seva ineficiència. La complexitat temporal de la cerca lineal és O (N) .
 Algorisme de cerca binària a Java 
La cerca binària, també coneguda com a cerca logarítmica, és un algorisme de cerca que troba la posició d’un valor objectiu dins d’una matriu ja ordenada. Divideix la col·lecció d'entrada en meitats iguals i es compara l'element amb l'element central de la llista. Si es troba l'element, la cerca s'acaba aquí. Altrament, continuem buscant l'element dividint i seleccionant la partició adequada de la matriu, en funció de si l'element objectiu és més petit o més gran que l'element mitjà.
Aquí hi ha un pseudocodi que representa la cerca binària a Java:
Procediment binary_search una matriu ordenada n mida de la matriu x valor que cal cercar lowerBound = 1 upperBound = n mentre que x no es troba si upperBound
La cerca finalitza quan upperBound (el nostre punter) passa per lowerBound (últim element), la qual cosa implica que hem cercat tota la matriu i que l'element no està present.Són els algoritmes de cerca més utilitzats principalment pel seu temps de cerca ràpida. La complexitat temporal de la cerca binària és O (N) la qual cosa suposa una notable millora en el O (N) complexitat temporal de la cerca lineal.
sèrie Fibonacci c ++
Això ens porta al final d’aquest article sobre ‘Estructures de dades i algorismes a Java’. He tractat un dels temes més fonamentals i importants de Java.Espero que tingueu clar tot el que us ha estat compartit en aquest article.
  Assegureu-vos de practicar el màxim possible i de recuperar la vostra experiència.   
 Consulteu el    per Edureka, una empresa d'aprenentatge en línia de confiança amb una xarxa de més de 250.000 estudiants satisfets repartits per tot el món. Estem aquí per ajudar-vos en cada pas del vostre viatge, per convertir-vos en una pregunta a part d’aquestes entrevistes java, oferim un pla d’estudis dissenyat per a estudiants i professionals que vulguin ser desenvolupador de Java. 
 Tens alguna pregunta? Si us plau, mencioneu-lo a la secció de comentaris d’aquest ‘Algoritmes i estructures de dades a Java’.  article i ens posarem en contacte amb vostè el més aviat possible.