Des de la invenció dels ordinadors, la gent ha estat utilitzant el terme ' Dades ' per referir-se a la informació de l'ordinador, ja sigui transmesa o emmagatzemada. Tanmateix, també hi ha dades que existeixen en tipus d'ordre. Les dades poden ser números o textos escrits en un tros de paper, en forma de bits i bytes emmagatzemats a la memòria de dispositius electrònics, o fets emmagatzemats a la ment d'una persona. A mesura que el món es va començar a modernitzar, aquestes dades es van convertir en un aspecte important del dia a dia de tothom i diverses implementacions els van permetre emmagatzemar-les de manera diferent.

Dades és una col·lecció de fets i xifres o un conjunt de valors o valors d'un format específic que fa referència a un únic conjunt de valors d'element. A continuació, els elements de dades es classifiquen en subelements, que és el grup d'elements que no es coneixen com a forma primària simple de l'element.

Considerem un exemple en què el nom d'un empleat es pot dividir en tres subelements: primer, mig i darrer. No obstant això, una identificació assignada a un empleat generalment es considerarà un únic element.

Figura 1: Representació d'elements de dades

En l'exemple esmentat anteriorment, els elements com ID, Edat, Sexe, Primer, Mitjà, Darrer, Carrer, Localitat, etc., són elements de dades elementals. En canvi, el nom i l'adreça són elements de dades de grup.

Què és l'estructura de dades?

Estructura de dades és una branca de la informàtica. L'estudi de l'estructura de dades ens permet entendre l'organització de les dades i la gestió del flux de dades per tal d'augmentar l'eficiència de qualsevol procés o programa. L'estructura de dades és una forma particular d'emmagatzemar i organitzar dades a la memòria de l'ordinador perquè aquestes dades es puguin recuperar fàcilment i utilitzar-les de manera eficient en el futur quan sigui necessari. Les dades es poden gestionar de diverses maneres, com ara el model lògic o matemàtic per a una organització específica de dades es coneix com a estructura de dades.

L'abast d'un model de dades particular depèn de dos factors:

1. En primer lloc, s'ha de carregar prou a l'estructura per reflectir la correlació definitiva de les dades amb un objecte del món real.
2. En segon lloc, la formació ha de ser tan senzilla que es pugui adaptar per processar les dades de manera eficient sempre que sigui necessari.

Alguns exemples d'estructures de dades són matrius, llistes enllaçades, pila, cua, arbres, etc. Les estructures de dades s'utilitzen àmpliament en gairebé tots els aspectes de la informàtica, és a dir, disseny de compiladors, sistemes operatius, gràfics, intel·ligència artificial i molts més.

Les estructures de dades són la part principal de molts algorismes informàtics, ja que permeten als programadors gestionar les dades d'una manera eficaç. Té un paper crucial en la millora del rendiment d'un programa o programari, ja que l'objectiu principal del programari és emmagatzemar i recuperar les dades de l'usuari el més ràpid possible.

llista d'enllaços en java

Terminologies bàsiques relacionades amb les estructures de dades

Les estructures de dades són els components bàsics de qualsevol programari o programa. Seleccionar l'estructura de dades adequada per a un programa és una tasca extremadament difícil per a un programador.

A continuació es mostren algunes terminologies fonamentals utilitzades sempre que hi hagi estructures de dades implicades:

Dades:Podem definir les dades com un valor elemental o una col·lecció de valors. Per exemple, el nom i l'identificador de l'empleat són les dades relacionades amb l'empleat.Elements de dades:Una unitat de valor única es coneix com a element de dades.Elements del grup:Els elements de dades que tenen elements de dades subordinats es coneixen com a elements de grup. Per exemple, el nom d'un empleat pot tenir un nom, un segon i un cognom.Elements elementals:Els elements de dades que no es poden dividir en subelements es coneixen com a elements elementals. Per exemple, l'identificador d'un empleat.Entitat i atribut:Una classe de determinats objectes està representada per una entitat. Consta de diferents atributs. Cada atribut simbolitza la propietat específica d'aquesta entitat. Per exemple,

Les entitats amb atributs similars formen un Conjunt d'entitats . Cada atribut d'un conjunt d'entitats té un rang de valors, el conjunt de tots els valors possibles que es podrien assignar a l'atribut específic.

El terme 'informació' de vegades s'utilitza per a dades amb atributs determinats de dades significatives o processades.

Camp:Una única unitat elemental d'informació que simbolitza l'atribut d'una entitat es coneix com a camp.Registre:Una col·lecció de diferents elements de dades es coneix com a Registre. Per exemple, si parlem de l'entitat de l'empleat, el seu nom, identificador, adreça i títol de treball es poden agrupar per formar el registre de l'empleat.Dossier:Una col·lecció de diferents registres d'un tipus d'entitat es coneix com a fitxer. Per exemple, si hi ha 100 empleats, hi haurà 25 registres al fitxer relacionat que continguin dades sobre cada empleat.

Comprendre la necessitat d'estructures de dades

A mesura que les aplicacions són cada cop més complexes i la quantitat de dades augmenta cada dia, la qual cosa pot provocar problemes amb la cerca de dades, la velocitat de processament, la gestió de múltiples sol·licituds i molts més. Les estructures de dades admeten diferents mètodes per organitzar, gestionar i emmagatzemar dades de manera eficient. Amb l'ajuda de les estructures de dades, podem recórrer fàcilment els elements de dades. Les estructures de dades proporcionen eficiència, reutilització i abstracció.

Per què hem d'aprendre estructures de dades?

1. Les estructures de dades i els algorismes són dos dels aspectes clau de la informàtica.
2. Les estructures de dades ens permeten organitzar i emmagatzemar dades, mentre que els algorismes ens permeten processar aquestes dades de manera significativa.
3. Aprenentatge d'estructures i algorismes de dades ens ajudarà a ser millors programadors.
4. Podrem escriure codi que sigui més eficaç i fiable.
5. També podrem resoldre problemes de manera més ràpida i eficient.

Entendre els objectius de les estructures de dades

Les estructures de dades compleixen dos objectius complementaris:

Correcció:Les estructures de dades estan dissenyades per funcionar correctament per a tot tipus d'entrades en funció del domini d'interès. En paraules, la correcció és l'objectiu principal de l'estructura de dades, que sempre depèn dels problemes que l'estructura de dades pretén resoldre.Eficiència:Les estructures de dades també requereixen ser eficients. Hauria de processar les dades ràpidament sense utilitzar molts recursos informàtics com l'espai de memòria. En un estat en temps real, l'eficiència d'una estructura de dades és un factor clau per determinar l'èxit i el fracàs del procés.

Comprensió d'algunes característiques clau de les estructures de dades

Algunes de les característiques significatives de les estructures de dades són:

Robustesa:En general, tots els programadors d'ordinadors tenen com a objectiu produir programari que produeixi una sortida correcta per a cada entrada possible, juntament amb una execució eficient en totes les plataformes de maquinari. Aquest tipus de programari robust ha de gestionar entrades vàlides i no vàlides.Adaptabilitat:La creació d'aplicacions de programari com ara navegadors web, processadors de textos i motor de cerca d'Internet inclou sistemes de programari enormes que requereixen un funcionament o execució correctes i eficients durant molts anys. A més, el programari evoluciona a causa de les tecnologies emergents o de les condicions del mercat en constant canvi.Reutilitzabilitat:Les funcions com la reutilitzabilitat i l'adaptabilitat van de la mà. Se sap que el programador necessita molts recursos per construir qualsevol programari, per la qual cosa és una empresa costosa. Tanmateix, si el programari es desenvolupa de manera reutilitzable i adaptable, es pot aplicar a la majoria d'aplicacions futures. Així, mitjançant l'execució d'estructures de dades de qualitat, és possible crear programari reutilitzable, que sembla ser rendible i estalviant temps.

Classificació de les estructures de dades

Una estructura de dades ofereix un conjunt estructurat de variables relacionades entre si de diverses maneres. Constitueix la base d'una eina de programació que significa la relació entre els elements de dades i permet als programadors processar les dades de manera eficient.

Podem classificar les estructures de dades en dues categories:

1. Estructura de dades primitives
2. Estructura de dades no primitives

La figura següent mostra les diferents classificacions de les estructures de dades.

np zeros

Figura 2: Classificacions d'estructures de dades

Estructures de dades primitives

Estructures de dades primitivessón les estructures de dades formades pels números i els caràcters que vénen incorporat en programes.
1. Aquestes estructures de dades es poden manipular o operar directament mitjançant instruccions a nivell de màquina.
2. Tipus de dades bàsics com Enter, flotant, caràcter , i booleà es troben sota les estructures de dades primitives.
3. Aquests tipus de dades també s'anomenen Tipus de dades simples , ja que contenen caràcters que no es poden dividir més

Estructures de dades no primitives

Estructures de dades no primitivessón aquelles estructures de dades derivades de les estructures de dades primitives.
1. Aquestes estructures de dades no es poden manipular ni operar directament per instruccions a nivell de màquina.
2. El focus d'aquestes estructures de dades és formar un conjunt d'elements de dades que siguin homogeni (mateix tipus de dades) o heterogeni (diferents tipus de dades).
3. A partir de l'estructura i la disposició de les dades, podem dividir aquestes estructures de dades en dues subcategories:
   1. Estructures de dades lineals
   2. Estructures de dades no lineals

Estructures de dades lineals

Una estructura de dades que conserva una connexió lineal entre els seus elements de dades es coneix com a estructura de dades lineal. La disposició de les dades es fa de manera lineal, on cada element està format pels successors i predecessors excepte el primer i l'últim element de dades. Tanmateix, no és necessàriament cert en el cas de la memòria, ja que la disposició pot no ser seqüencial.

En funció de l'assignació de memòria, les estructures de dades lineals es classifiquen en dos tipus:

Estructures de dades estàtiques:Les estructures de dades que tenen una mida fixa es coneixen com a estructures de dades estàtiques. La memòria d'aquestes estructures de dades s'assigna en el moment del compilador i l'usuari no pot canviar la seva mida després de compilar-les; no obstant això, les dades emmagatzemades en ells es poden alterar.
El Matriu és el millor exemple de l'estructura de dades estàtiques ja que tenen una mida fixa i les seves dades es poden modificar més endavant.Estructures de dades dinàmiques:Les estructures de dades que tenen una mida dinàmica es coneixen com a estructures de dades dinàmiques. La memòria d'aquestes estructures de dades s'assigna en el temps d'execució i la seva mida varia durant el temps d'execució del codi. A més, l'usuari pot canviar la mida així com els elements de dades emmagatzemats en aquestes estructures de dades en el moment de l'execució del codi.
Llistes enllaçades, piles , i Cues són exemples habituals d'estructures de dades dinàmiques

Tipus d'estructures de dades lineals

La següent és la llista d'estructures de dades lineals que utilitzem generalment:

1. Arrays

An Matriu és una estructura de dades utilitzada per recollir diversos elements de dades del mateix tipus de dades en una variable. En lloc d'emmagatzemar diversos valors dels mateixos tipus de dades en noms de variables separats, podríem emmagatzemar-los tots junts en una sola variable. Aquesta declaració no implica que haurem d'unir tots els valors del mateix tipus de dades en qualsevol programa en una matriu d'aquest tipus de dades. Però sovint hi haurà moments en què algunes variables específiques dels mateixos tipus de dades estan relacionades entre si d'una manera adequada per a una matriu.

Una matriu és una llista d'elements on cada element té un lloc únic a la llista. Els elements de dades de la matriu comparteixen el mateix nom de variable; no obstant això, cadascun porta un número d'índex diferent anomenat subíndex. Podem accedir a qualsevol element de dades de la llista amb l'ajuda de la seva ubicació a la llista. Així, la característica clau de les matrius a entendre és que les dades s'emmagatzemen en ubicacions de memòria contigües, cosa que permet als usuaris recórrer els elements de dades de la matriu utilitzant els seus índexs respectius.

Figura 3. Una matriu

Les matrius es poden classificar en diferents tipus:

Matriu unidimensional:Una matriu amb només una fila d'elements de dades es coneix com a matriu unidimensional. S'emmagatzema en un lloc d'emmagatzematge ascendent.Matriu bidimensional:Una matriu que consta de diverses files i columnes d'elements de dades s'anomena matriu bidimensional. També es coneix com a Matrix.Matriu multidimensional:Podem definir una matriu multidimensional com una matriu de matrius. Les matrius multidimensionals no estan limitades a dos índexs o dues dimensions, ja que poden incloure tants índexs segons la necessitat.

Algunes aplicacions de Array:

1. Podem emmagatzemar una llista d'elements de dades pertanyents al mateix tipus de dades.
2. Array actua com a emmagatzematge auxiliar per a altres estructures de dades.
3. La matriu també ajuda a emmagatzemar elements de dades d'un arbre binari del recompte fix.
4. Array també actua com a emmagatzematge de matrius.

2. Llistes enllaçades

A Llista enllaçada és un altre exemple d'estructura de dades lineal utilitzada per emmagatzemar una col·lecció d'elements de dades de manera dinàmica. Els elements de dades d'aquesta estructura de dades estan representats pels nodes, connectats mitjançant enllaços o punters. Cada node conté dos camps, el camp d'informació està format per les dades reals i el camp del punter consisteix en l'adreça dels nodes següents de la llista. El punter de l'últim node de la llista enllaçada consta d'un punter nul, ja que no apunta a res. A diferència dels Arrays, l'usuari pot ajustar dinàmicament la mida d'una llista enllaçada segons els requisits.

Figura 4. Una llista enllaçada

bash si condició

Les llistes enllaçades es poden classificar en diferents tipus:

Llista enllaçada individualment:Una llista enllaçada individualment és el tipus més comú de llista enllaçada. Cada node té dades i un camp de punter que conté una adreça al següent node.Llista doblement enllaçada:Una llista doblement enllaçada consta d'un camp d'informació i dos camps de punter. El camp d'informació conté les dades. El primer camp de punter conté una adreça del node anterior, mentre que un altre camp de punter conté una referència al node següent. Així, podem anar en ambdues direccions (enrere i endavant).Llista enllaçada circular:La llista enllaçada circular és similar a la llista enllaçada individualment. L'única diferència clau és que l'últim node conté l'adreça del primer node, formant un bucle circular a la llista d'enllaços circulars.

Algunes aplicacions de llistes enllaçades:

1. Les llistes enllaçades ens ajuden a implementar piles, cues, arbres binaris i gràfics de mida predefinida.
2. També podem implementar la funció del sistema operatiu per a la gestió dinàmica de la memòria.
3. Les llistes enllaçades també permeten la implementació de polinomis per a operacions matemàtiques.
4. Podem utilitzar Circular Linked List per implementar sistemes operatius o funcions d'aplicació que Round Robin executin tasques.
5. La llista enllaçada circular també és útil en una presentació de diapositives on l'usuari necessita tornar a la primera diapositiva després de presentar l'última diapositiva.
6. La llista doblement enllaçada s'utilitza per implementar botons endavant i enrere en un navegador per avançar i retrocedir a les pàgines obertes d'un lloc web.

3. Piles

A Pila és una estructura de dades lineal que segueix la LIFO Principi (Last In, First Out) que permet operacions com la inserció i la supressió d'un extrem de la pila, és a dir, la part superior. Les piles es poden implementar amb l'ajuda de la memòria contigua, una matriu, i la memòria no contigua, una llista enllaçada. Exemples reals de Stacks són munts de llibres, una baralla de cartes, munts de diners i molts més.

Figura 5. Un exemple real de Stack

La figura anterior representa l'exemple real d'una pila on les operacions es realitzen només des d'un extrem, com ara la inserció i l'eliminació de llibres nous de la part superior de la pila. Implica que la inserció i la supressió a la pila només es poden fer des de la part superior de la pila. Només podem accedir a la part superior de la pila en un moment donat.

Les operacions principals a la pila són les següents:

Empènyer:L'operació per inserir un element nou a la pila s'anomena operació Push.Pop:L'operació per eliminar o eliminar elements de la pila s'anomena operació pop.

Figura 6. Una pila

Algunes aplicacions de les piles:

1. La pila s'utilitza com a estructura d'emmagatzematge temporal per a operacions recursives.
2. La pila també s'utilitza com a estructura d'emmagatzematge auxiliar per a les trucades de funcions, les operacions imbricades i les funcions ajornadas/ajornades.
3. Podem gestionar les trucades de funcions mitjançant Stacks.
4. També s'utilitzen piles per avaluar les expressions aritmètiques en diferents llenguatges de programació.
5. Les piles també són útils per convertir expressions infixes en expressions postfixes.
6. Les piles ens permeten comprovar la sintaxi de l'expressió a l'entorn de programació.
7. Podem emparellar els parèntesis mitjançant Stacks.
8. Les piles es poden utilitzar per invertir una cadena.
9. Les piles són útils per resoldre problemes basats en el retrocés.
10. Podem utilitzar Stacks en la cerca en profunditat en el recorregut de gràfics i arbres.
11. Les piles també s'utilitzen en funcions del sistema operatiu.
12. Les piles també s'utilitzen a les funcions UNDO i REDO en una edició.

4. Cues

A Cua és una estructura de dades lineal similar a una pila amb algunes limitacions en la inserció i eliminació dels elements. La inserció d'un element en una cua es fa en un extrem, i l'eliminació es fa en un altre extrem o oposat. Així, podem concloure que l'estructura de dades de la cua segueix el principi FIFO (First In, First Out) per manipular els elements de dades. La implementació de les cues es pot fer mitjançant matrius, llistes enllaçades o piles. Alguns exemples reals de cues són una línia al taulell de bitllets, una escala mecànica, un rentat de cotxes i molts més.

Figura 7. Un exemple real de la cua

La imatge de dalt és una il·lustració real d'un taulell d'entrades de pel·lícules que ens pot ajudar a entendre la cua on sempre s'atén el client que arriba primer. El client que arribi l'últim serà sens dubte atendre l'últim. Els dos extrems de la cua estan oberts i poden executar diferents operacions. Un altre exemple és una línia de menjador on el client s'insereix des de la part posterior mentre que el client s'elimina per la part davantera després de prestar el servei que demanava.

Les següents són les operacions principals de la cua:

commutador java

Cua:La inserció o l'addició d'alguns elements de dades a la cua s'anomena Enqueue. La inserció de l'element sempre es fa amb l'ajuda del punter posterior.Treu la cua:La supressió o eliminació d'elements de dades de la cua s'anomena Descua. L'eliminació de l'element sempre es fa amb l'ajuda del punter frontal.

Figura 8. A Queue

Algunes aplicacions de les cues:

1. Les cues s'utilitzen generalment en l'operació de cerca d'amplitud a Graphs.
2. Les cues també s'utilitzen a les operacions del programador de treballs dels sistemes operatius, com ara una cua de memòria intermèdia de teclat per emmagatzemar les tecles premudes pels usuaris i una cua de memòria intermèdia d'impressió per emmagatzemar els documents impresos per la impressora.
3. Les cues són responsables de la programació de la CPU, la programació de treballs i la programació del disc.
4. Les cues de prioritat s'utilitzen en les operacions de descàrrega de fitxers en un navegador.
5. Les cues també s'utilitzen per transferir dades entre dispositius perifèrics i la CPU.
6. Les cues també s'encarreguen de gestionar les interrupcions generades per les aplicacions d'usuari per a la CPU.

Estructures de dades no lineals

Les estructures de dades no lineals són estructures de dades on els elements de dades no estan disposats en ordre seqüencial. Aquí, la inserció i l'eliminació de dades no són factibles de manera lineal. Hi ha una relació jeràrquica entre les dades individuals.

Tipus d'estructures de dades no lineals

La següent és la llista d'estructures de dades no lineals que utilitzem generalment:

1. Arbres

Un arbre és una estructura de dades no lineal i una jerarquia que conté una col·lecció de nodes de manera que cada node de l'arbre emmagatzema un valor i una llista de referències a altres nodes (els 'fills').

L'estructura de dades de l'arbre és un mètode especialitzat per organitzar i recopilar dades a l'ordinador per utilitzar-les de manera més eficaç. Conté un node central, nodes estructurals i subnodes connectats mitjançant vores. També podem dir que l'estructura de dades de l'arbre consta d'arrels, branques i fulles connectades.

Figura 9. Un arbre

Els arbres es poden classificar en diferents tipus:

Arbre binari:Una estructura de dades d'arbre on cada node pare pot tenir com a màxim dos fills s'anomena arbre binari.Arbre de cerca binari:Un arbre de cerca binari és una estructura de dades d'arbre on podem mantenir fàcilment una llista ordenada de números.Arbre AVL:Un arbre AVL és un arbre de cerca binari d'autoequilibri on cada node manté informació addicional coneguda com a factor d'equilibri el valor del qual és -1, 0 o +1.B-Arbre:Un B-Tree és un tipus especial d'arbre de cerca binari d'autoequilibri on cada node consta de diverses claus i pot tenir més de dos fills.

Algunes aplicacions dels arbres:

1. Els arbres implementen estructures jeràrquiques en sistemes informàtics com directoris i sistemes de fitxers.
2. Els arbres també s'utilitzen per implementar l'estructura de navegació d'un lloc web.
3. Podem generar codi com el codi d'Huffman mitjançant Arbres.
4. Els arbres també són útils per a la presa de decisions a les aplicacions de jocs.
5. Els arbres són els responsables d'implementar cues de prioritats per a les funcions de programació del SO basades en prioritats.
6. Els arbres també s'encarreguen d'analitzar expressions i sentències en els compiladors de diferents llenguatges de programació.
7. Podem utilitzar els arbres per emmagatzemar claus de dades per a la indexació del sistema de gestió de bases de dades (DBMS).
8. Spanning Trees ens permet encaminar les decisions en xarxes informàtiques i de comunicacions.
9. Els arbres també s'utilitzen en l'algoritme de recerca de camins implementat a les aplicacions d'intel·ligència artificial (IA), robòtica i videojocs.

2. Gràfics

Un gràfic és un altre exemple d'estructura de dades no lineal que inclou un nombre finit de nodes o vèrtexs i les vores que els connecten. Els gràfics s'utilitzen per abordar problemes del món real en què denota l'àrea problemàtica com una xarxa com ara xarxes socials, xarxes de circuits i xarxes telefòniques. Per exemple, els nodes o vèrtexs d'un gràfic poden representar un sol usuari en una xarxa telefònica, mentre que les vores representen l'enllaç entre ells a través del telèfon.

L'estructura de dades del gràfic, G es considera una estructura matemàtica formada per un conjunt de vèrtexs, V i un conjunt d'arestes, E tal com es mostra a continuació:

G = (V,E)

Figura 10. Un gràfic

La figura anterior representa un gràfic que té set vèrtexs A, B, C, D, E, F, G i deu arestes [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] i [E, G].

Depenent de la posició dels vèrtexs i les arestes, els gràfics es poden classificar en diferents tipus:

Gràfic nul:Un gràfic amb un conjunt d'arestes buit s'anomena gràfic nul.Gràfic trivial:Un gràfic que només té un vèrtex s'anomena gràfic trivial.Gràfic simple:Un gràfic sense bucles propis ni múltiples arestes es coneix com a gràfic simple.Multigràfic:Es diu que un gràfic és múltiple si consta de múltiples arestes però sense auto-bucles.Pseudogràfic:Un gràfic amb bucles propis i múltiples arestes s'anomena pseudogràfic.Gràfic no dirigit:Un gràfic format per arestes no dirigides es coneix com a gràfic no dirigit.Gràfic dirigit:Un gràfic format per les arestes dirigides entre els vèrtexs es coneix com a gràfic dirigit.Gràfic connectat:Un gràfic amb almenys un sol camí entre cada parell de vèrtexs s'anomena gràfic connectat.Gràfic desconnectat:Un gràfic on no existeix cap camí entre almenys un parell de vèrtexs s'anomena gràfic desconnectat.Gràfic regular:Un gràfic on tots els vèrtexs tenen el mateix grau s'anomena gràfic regular.Gràfic complet:Un gràfic en què tots els vèrtexs tenen una aresta entre cada parell de vèrtexs es coneix com a gràfic complet.Gràfic de cicle:Es diu que un gràfic és un cicle si té almenys tres vèrtexs i arestes que formen un cicle.Gràfic cíclic:Es diu que un gràfic és cíclic si i només si existeix almenys un cicle.Gràfic acíclic:Un gràfic que té zero cicles s'anomena gràfic acíclic.Gràfic finit:Un gràfic amb un nombre finit de vèrtexs i arestes es coneix com a gràfic finit.Gràfic infinit:Un gràfic amb un nombre infinit de vèrtexs i arestes es coneix com a gràfic infinit.Gràfic bipartit:Un gràfic on els vèrtexs es poden dividir en conjunts independents A i B, i tots els vèrtexs del conjunt A només haurien d'estar connectats als vèrtexs presents al conjunt B amb algunes arestes s'anomena gràfic bipartit.Gràfic planar:Es diu que un gràfic és un pla si el podem dibuixar en un sol pla amb dues arestes que es tallen.Gràfic d'Euler:Es diu que un gràfic és Euler si i només si tots els vèrtexs són graus parells.Gràfic hamiltonià:Un gràfic connectat que consisteix en un circuit hamiltonià es coneix com a gràfic hamiltonià.

Algunes aplicacions dels gràfics:

1. Els gràfics ens ajuden a representar rutes i xarxes en aplicacions de transport, viatges i comunicacions.
2. Els gràfics s'utilitzen per mostrar rutes al GPS.
3. Els gràfics també ens ajuden a representar les interconnexions a les xarxes socials i altres aplicacions basades en xarxa.
4. Els gràfics s'utilitzen en aplicacions de mapes.
5. Els gràfics són els responsables de la representació de les preferències dels usuaris a les aplicacions de comerç electrònic.
6. També s'utilitzen gràfics a les xarxes de serveis públics per tal d'identificar els problemes plantejats a les corporacions locals o municipals.
7. Els gràfics també ajuden a gestionar la utilització i la disponibilitat dels recursos en una organització.
8. També s'utilitzen gràfics per fer mapes d'enllaços de documents dels llocs web per tal de mostrar la connectivitat entre les pàgines mitjançant hipervincles.
9. Els gràfics també s'utilitzen en moviments robòtics i xarxes neuronals.

Operacions bàsiques d'estructures de dades

A la secció següent, parlarem dels diferents tipus d'operacions que podem realitzar per manipular dades en cada estructura de dades:

Travessia:Travessar una estructura de dades significa accedir a cada element de dades exactament una vegada perquè es pugui administrar. Per exemple, cal fer un recorregut mentre s'imprimeixen els noms de tots els empleats d'un departament.Cerca:La cerca és una altra operació d'estructura de dades que significa trobar la ubicació d'un o més elements de dades que compleixen determinades restriccions. Aquest element de dades pot estar o no present en el conjunt d'elements de dades donat. Per exemple, podem utilitzar l'operació de cerca per trobar els noms de tots els empleats que tenen una experiència de més de 5 anys.Inserció:La inserció significa inserir o afegir nous elements de dades a la col·lecció. Per exemple, podem utilitzar l'operació d'inserció per afegir les dades d'un nou empleat que l'empresa ha contractat recentment.Supressió:La supressió significa eliminar o eliminar un element de dades específic de la llista d'elements de dades donada. Per exemple, podem utilitzar l'operació d'eliminació per eliminar el nom d'un empleat que ha deixat la feina.Classificació:Ordenar significa organitzar els elements de dades en ordre ascendent o descendent segons el tipus d'aplicació. Per exemple, podem utilitzar l'operació d'ordenació per ordenar els noms dels empleats d'un departament en ordre alfabètic o estimar els tres millors resultats del mes ordenant el rendiment dels empleats en ordre descendent i extreint els detalls dels tres primers.Fusionar:Fusionar significa combinar elements de dades de dues llistes ordenades per formar una única llista d'elements de dades ordenats.Crear:Crear és una operació utilitzada per reservar memòria per als elements de dades del programa. Podem realitzar aquesta operació mitjançant una declaració. La creació de l'estructura de dades pot tenir lloc durant els següents períodes:
1. Temps de compilació
2. Temps d'execució
   Per exemple, el malloc() La funció s'utilitza al llenguatge C per crear una estructura de dades.
Selecció:Selecció significa seleccionar una determinada dada entre les dades disponibles. Podem seleccionar qualsevol dada en particular especificant condicions dins del bucle.Actualització:L'operació d'actualització ens permet actualitzar o modificar les dades de l'estructura de dades. També podem actualitzar qualsevol dada en particular especificant algunes condicions dins del bucle, com l'operació de selecció.Divisió:L'operació de divisió ens permet dividir les dades en diverses subparts disminuint el temps total de finalització del procés.

Comprensió del tipus de dades abstractes

Segons el Institut Nacional d'Estàndards i Tecnologia (NIST) , una estructura de dades és una disposició d'informació, generalment a la memòria, per a una millor eficiència de l'algorisme. Les estructures de dades inclouen llistes enllaçades, piles, cues, arbres i diccionaris. També podrien ser una entitat teòrica, com el nom i l'adreça d'una persona.

A partir de la definició esmentada anteriorment, podem concloure que les operacions en l'estructura de dades inclouen:

1. Un alt nivell d'abstraccions com l'addició o la supressió d'un element d'una llista.
2. Cercar i ordenar un element en una llista.
3. Accés a l'element de màxima prioritat d'una llista.

Sempre que l'estructura de dades fa aquestes operacions, es coneix com a Tipus de dades abstractes (ADT) .

El podem definir com un conjunt d'elements de dades juntament amb les operacions sobre les dades. El terme 'abstracte' fa referència al fet que les dades i les operacions fonamentals que s'hi defineixen s'estudien independentment de la seva implementació. Inclou què podem fer amb les dades, no com ho podem fer.

Una implementació d'ADI conté una estructura d'emmagatzematge per emmagatzemar els elements de dades i els algorismes per al funcionament fonamental. Totes les estructures de dades, com ara una matriu, una llista enllaçada, una cua, una pila, etc., són exemples d'ADT.

java obtenint la data actual

Comprendre els avantatges de l'ús d'ADT

En el món real, els programes evolucionen com a conseqüència de noves restriccions o requisits, de manera que modificar un programa generalment requereix un canvi en una o múltiples estructures de dades. Per exemple, suposem que volem inserir un camp nou al registre d'un empleat per fer un seguiment de més detalls sobre cada empleat. En aquest cas, podem millorar l'eficiència del programa substituint una matriu per una estructura enllaçada. En aquesta situació, reescriure tots els procediments que utilitzin l'estructura modificada no és adequat. Per tant, una millor alternativa és separar una estructura de dades de la seva informació d'implementació. Aquest és el principi darrere de l'ús dels tipus de dades abstractes (ADT).

Algunes aplicacions de les estructures de dades

A continuació es mostren algunes aplicacions de les estructures de dades:

1. Les estructures de dades ajuden a organitzar les dades a la memòria d'un ordinador.
2. Les estructures de dades també ajuden a representar la informació a les bases de dades.
3. Data Structures permet la implementació d'algorismes per cercar a través de dades (Per exemple, motor de cerca).
4. Podem utilitzar les estructures de dades per implementar els algorismes per manipular dades (per exemple, processadors de textos).
5. També podem implementar els algorismes per analitzar dades mitjançant estructures de dades (per exemple, els miners de dades).
6. Les estructures de dades admeten algorismes per generar les dades (per exemple, un generador de números aleatoris).
7. Les estructures de dades també admeten algorismes per comprimir i descomprimir les dades (per exemple, una utilitat zip).
8. També podem utilitzar estructures de dades per implementar algorismes per xifrar i desxifrar les dades (per exemple, un sistema de seguretat).
9. Amb l'ajuda de Data Structures, podem crear programari que pugui gestionar fitxers i directoris (per exemple, un gestor de fitxers).
10. També podem desenvolupar programari que pugui renderitzar gràfics mitjançant estructures de dades. (Per exemple, un navegador web o programari de renderització 3D).

A part d'aquestes, com s'ha esmentat anteriorment, hi ha moltes altres aplicacions d'estructures de dades que ens poden ajudar a crear qualsevol programari desitjat.