introduction data structures c
Un tutorial introductori sobre les estructures de dades en C ++.
“L’estructura de dades es pot definir com una col·lecció organitzada de dades que ajuda un programa a accedir a les dades de manera eficient i ràpida perquè tot el programa pugui funcionar d’una manera eficient. '
Sabem que al món de la programació, les dades són el centre i tot gira al voltant de les dades. Hem de fer totes les operacions de dades, inclòs l’emmagatzematge, la cerca, l’ordenació, l’organització i l’accés a les dades de manera eficient, i només així el nostre programa pot tenir èxit.
=> Vegeu aquí per explorar la llista completa de tutorials de C ++.
Què aprendreu:
- Visió general
- Necessitat d’estructura de dades en la programació
- Classificació de l'estructura de dades
- Operacions sobre l'estructura de dades
- Avantatges de l'estructura de dades
- Conclusió
- Lectura recomanada
Visió general
Hem de trobar la forma més eficaç d’emmagatzemar dades que ens ajudi a construir solucions dinàmiques. L’estructura de dades ens ajuda a construir aquestes solucions.
Mentre organitzem o organitzem les dades en estructures, hem d’assegurar-nos que l’arranjament representa gairebé un objecte del món real. En segon lloc, aquest acord hauria de ser prou senzill perquè tothom pugui accedir-hi fàcilment i processar-lo sempre que sigui necessari.
En aquesta sèrie, aprendrem detalladament sobre una estructura de dades bàsica i avançada. També coneixerem detalladament diverses tècniques de cerca i classificació que es poden realitzar en estructures de dades.
Després d’aprendre aquesta sèrie de tutorials, el lector hauria de conèixer bé cada estructura de dades i la seva programació.
Anem a revisar alguns dels termes que fem servir per tractar les estructures de dades:
Per exemple,agafar un alumne en particular. Un estudiant pot tenir els detalls següents tal com es representa pictòricament.
- Dades: És el valor elemental. A la figura anterior, el número de rotlle de l’alumne pot ser dades.
- Element del grup: Aquest és l'element de dades que té més d'un subelement. A la figura anterior, Student_name té nom i cognom.
- Rècord: És una col·lecció d’elements de dades. A l'exemple anterior, les dades, com ara el número de registre de l'estudiant, el nom, la classe, l'edat, el grau, etc. formen un registre junts.
- Entitat: És una classe de registres. Al diagrama anterior, l'estudiant és una entitat.
- Atribut o camp: Les propietats d’una entitat s’anomenen atributs i cada camp representa un atribut.
- Dossier: Un fitxer és una col·lecció de registres. A l'exemple anterior, una entitat estudiantil pot tenir milers de registres. Així, un fitxer contindrà tots aquests registres.
El lector ha de ser conscient de tots aquests termes, ja que els fem servir de tant en tant quan fem servir diverses estructures de dades.
Les estructures de dades són el principal element bàsic del programa i, com a programadors, hauríem de tenir cura de quina estructura de dades hem d’utilitzar. L’estructura de dades exacta que s’ha d’utilitzar és la decisió més difícil de prendre pel que fa a la programació.
Analitzem la necessitat d’estructurar les dades a Programació.
Necessitat d’estructura de dades en la programació
A mesura que la quantitat de dades continua creixent, les aplicacions són cada vegada més complexes, per la qual cosa és difícil per al programador gestionar aquestes dades i el programari.
Normalment, en qualsevol moment, l'aplicació pot afrontar els següents obstacles:
# 1) Cerqueu grans quantitats de dades: Amb una gran quantitat de dades processades i emmagatzemades, és possible que en qualsevol moment es demani al nostre programa que cerqui dades concretes. Si les dades són massa grans i no s’organitzen correctament, trigarà molt a obtenir les dades necessàries.
Quan fem servir estructures de dades per emmagatzemar i organitzar dades, la recuperació de dades es fa més ràpida i senzilla.
# 2) Velocitat de processament: Les dades desorganitzades poden provocar una velocitat de processament lenta, ja que es perdrà molt de temps en recuperar i accedir a les dades.
Si organitzem les dades correctament en una estructura de dades mentre s’emmagatzemen, no perdrem el temps en activitats com la recuperació, organitzant-les cada vegada. En canvi, ens podem concentrar en el processament de dades per produir la sortida desitjada.
# 3) Múltiples sol·licituds simultànies: Actualment, moltes aplicacions necessiten fer una sol·licitud simultània de dades. Aquestes sol·licituds s'han de processar de manera eficient perquè les aplicacions funcionin sense problemes.
Si les nostres dades s’emmagatzemen aleatòriament, no podrem processar totes les sol·licituds simultànies simultàniament. Per tant, és una decisió encertada organitzar les dades en una estructura de dades adequada per minimitzar el temps de resposta de les sol·licituds simultànies.
Classificació de l'estructura de dades
Les estructures de dades utilitzades en C ++ es poden classificar de la següent manera.
Una estructura de dades és una forma d’organitzar les dades. Per tant, podem classificar les estructures de dades tal com es mostra en estructures de dades primitives o estàndard i estructures de dades no primitives o definides per l’usuari.
Hem vist tots els tipus de dades admesos a C ++. Com que també és una forma d’organitzar les dades, diem que és una estructura de dades estàndard.
La resta d’estructures de dades no són primitives i l’usuari les ha de definir abans d’utilitzar-les en un programa. Aquestes estructures de dades definides per l'usuari es classifiquen en estructures de dades lineals i no lineals.
Estructura de dades lineals
Les estructures de dades lineals tenen tots els seus elements ordenats de manera lineal o seqüencial. Cada element d'una estructura de dades lineal té un predecessor (element anterior) i un successor (element següent)
Les estructures de dades lineals es divideixen en estructures de dades estàtiques i dinàmiques. Les estructures de dades estàtiques solen tenir una mida fixa i, un cop declarada la seva mida en el moment de la compilació, no es poden canviar. Les estructures de dades dinàmiques poden canviar la seva mida dinàmicament i adaptar-se a elles mateixes.
L'exemple més popular d'estructura de dades estàtiques lineals és una matriu.
Matriu
Una matriu és una col·lecció seqüencial d'elements del mateix tipus. Es pot accedir a cada element de la matriu mitjançant la seva posició a la matriu anomenada índex o subíndex de la matriu. El nom de la matriu apunta al primer element de la matriu.
El que es mostra anteriorment és una matriu 'a' de n elements. Els elements estan numerats de 0 a n-1. La mida de la matriu (n en aquest cas) també s’anomena dimensió de la matriu. Com es mostra a la figura anterior, el nom de la matriu apunta al primer element de la matriu.
La matriu és l'estructura de dades més senzilla i és eficient ja que es pot accedir als elements mitjançant subíndexs directament. Si volem accedir al tercer element de la matriu, només hem de dir un (2).
Però afegir o eliminar els elements de la matriu és difícil. Per tant, utilitzem matrius només en aplicacions simples o en aplicacions on no és necessària l'addició / supressió d'elements.
Les estructures de dades dinàmiques lineals populars són la llista, la pila i la cua enllaçades.
Llista enllaçada
Una llista enllaçada és una col·lecció de nodes. Cada node conté l'element de dades i un punter al següent node. Els nodes es poden afegir i suprimir dinàmicament. Una llista enllaçada pot ser una llista enllaçada individualment en què cada node només té un punter cap al següent element. Per a l'últim element, el següent punter està definit com a nul.
A la llista doblement enllaçada, cada node té dos indicadors un al node anterior i el segon al node següent. Per al primer node, el punter anterior és nul i per a l'últim node, el següent és nul.
Com es mostra a la figura anterior, el començament de la llista s’anomena cap mentre que el final de la llista enllaçada s’anomena cua. Com es mostra més amunt, cada node té un punter cap a l’element següent. Podem afegir o eliminar elements fàcilment canviant el punter al següent node.
Pila
La pila és una estructura de dades lineal en què els elements només es poden afegir o eliminar d'un extrem conegut com a 'Part superior' de la pila. D’aquesta manera, la pila exhibeix un accés a memòria tipus LIFO (Last In, First Out).
Com es mostra més amunt, els elements de la pila sempre s’afegeixen en un extrem i també s’eliminen del mateix extrem. Això s'anomena la 'part superior' de la pila. Quan s’afegeix un element, s’empeny cap avall la pila i la part superior de la pila s’incrementa en una posició.
De la mateixa manera, quan s’elimina un element, la part superior de la pila es decrementa. Quan una pila està buida, la part superior de la pila s'estableix en -1. Hi ha dues operacions principals 'Push' i 'Pop' que es realitzen a la pila.
Cua
La cua és una altra estructura de dades lineal en què els elements s'afegeixen en un extrem anomenat 'posterior' i se suprimeixen d'un altre extrem anomenat 'frontal'. La cua demostra FIFO (First In, First Out) el tipus de metodologia d'accés a la memòria.
El diagrama anterior mostra una cua amb els extrems posteriors i anteriors. Quan la cua està buida, els indicadors posterior i frontal coincideixen entre si.
Estructura de dades no lineal
En les estructures de dades no lineals, les dades no s’ordenen seqüencialment, sinó que s’ordenen de manera no lineal. Els elements estan connectats entre si en una disposició no lineal.
Les estructures de dades no lineals són arbres i gràfics.
preguntes i respostes d’entrevistes d’arquitectura d’ordinadors pdf
Arbres
Els arbres són estructures de dades multinivell no lineals que tenen una relació jeràrquica entre els elements. Els elements de l’arbre s’anomenen Nodes.
El node de la part superior s’anomena arrel de l’arbre. L'arrel pot tenir un o més nodes fills. Els nodes posteriors també poden tenir un o més nodes fills. Els nodes que no tenen nodes fills s’anomenen nodes fulla.
Al diagrama anterior, hem mostrat un arbre amb 6 nodes. D’aquests tres nodes hi ha els nodes fulla, un node superior és l’arrel i els altres són nodes fills. En funció del nombre de nodes, nodes fills, etc. o de la relació entre els nodes, tenim diferents tipus d’arbres.
Gràfics
El gràfic és un conjunt de nodes anomenats vèrtexs connectats entre si mitjançant els enllaços anomenats Vores . Els gràfics poden tenir un cicle al seu interior, és a dir, el mateix vèrtex pot ser un punt de partida i també el punt final d’un camí concret. Els arbres mai no poden tenir un cicle.
El diagrama anterior és un gràfic sense direcció. També podem tenir gràfics dirigits on representem les vores mitjançant fletxes dirigides.
Operacions sobre l'estructura de dades
Totes les estructures de dades realitzen diverses operacions sobre els seus elements.
Aquests són comuns a totes les estructures de dades i es detallen de la manera següent:
- Cercant: Aquesta operació es realitza per cercar un element concret o una clau. Els algorismes de cerca més comuns són la cerca seqüencial / lineal i la cerca binària.
- Classificació: L’operació d’ordenació consisteix a ordenar els elements en una estructura de dades en un ordre determinat ascendent o descendent. Hi ha diversos algorismes d’ordenació disponibles per a les estructures de dades. Els més populars són Quicksort, Selection sort, Merge sort, etc.
- Inserció: L'operació d'inserció tracta d'afegir un element a l'estructura de dades. Aquesta és l'operació més important i, com a resultat de l'addició d'un element, la disposició canvia i hem de tenir cura que l'estructura de dades es mantingui intacta.
- Supressió: L'operació de supressió elimina un element de l'estructura de dades. Les mateixes condicions que s'han de considerar per a la inserció s'han de complir també en cas de l'operació de supressió.
- Recorregut: Diem que travessem una estructura de dades quan visitem tots i cadascun dels elements de l’estructura. Es requereix recorregut per realitzar determinades operacions específiques sobre l'estructura de dades.
En els nostres temes posteriors, primer aprendrem les diverses tècniques de cerca i classificació que s’han de realitzar en estructures de dades.
Avantatges de l'estructura de dades
- Abstracció: Les estructures de dades sovint s’implementen com a tipus de dades abstractes. Els usuaris només accedeixen a la seva interfície externa sense preocupar-se de la implementació subjacent. Per tant, l'estructura de dades proporciona una capa d'abstracció.
- Eficiència: Una correcta organització de les dades resulta en un accés eficient de les dades, cosa que fa que els programes siguin més eficients. En segon lloc, podem seleccionar l’estructura de dades adequada en funció dels nostres requisits.
- Reutilització: Podem reutilitzar les estructures de dades que hem dissenyat. També es poden compilar en una biblioteca i distribuir-los al client.
Conclusió
Amb això, concloguem aquest tutorial sobre introducció a les estructures de dades. Hem introduït breument cadascuna de les estructures de dades en aquest tutorial.
En els nostres tutorials posteriors, explorarem més sobre les estructures de dades juntament amb les diverses tècniques de cerca i classificació.
=> Feu clic aquí per obtenir la sèrie de formació Absolute C ++.
Lectura recomanada
- Tipus de dades C ++
- Estructura de dades de la cua en C ++ amb il·lustració
- Top 10 de les eines de ciència de dades el 2021 per eliminar la programació
- Parametrizació de dades de JMeter mitjançant variables definides per l'usuari
- 10+ millors eines de recopilació de dades amb estratègies de recopilació de dades
- 10+ millors eines de governança de dades per satisfer les vostres necessitats de dades el 2021
- Funció de grup de dades a IBM Rational Quality Manager per a la gestió de dades de prova
- Estructura de dades de pila en C ++ amb il·lustració