Llistes
Ara veiem les llistes. Fins ara hem vist que en una pila podem insertar només a dalt, i en una cua només al final. En un vector també podem insertar al final en temps constant amortitzat. Ara, què passa si necessitem insertar molts cops i que no sigui al final? Amb el vector, hauríem de desplaçar els elements per fer espai pel nou, cosa que té temps lineal. Massa temps, si n'hem de fer moltes. Per això apareixen les llistes
Insercions i eliminacions en temps constant
Una llista té una implementació interna que permet insertar i eliminar en temps constant, a la posició que sigui. Principi, final, o qualsevol, totes en temps constant. Tingui un element o un milió, trigarem similar en insertar un element. Podem veure com funcionen
Iteradors
Un iterador és una classe que utilitzem per recórrer una estructura de dades. No és una cosa nova del tot, ja que els vectors també en tenien, però en els vectors podíem obviar la seva existència i recorre'ls per l'índex. Aquí no podem, ja que els elements d'una llista no s'emmagatzemen en posicions contínues. Així que anem pas a pas
Què és un iterador?
Un iterador és una classe que fa referència a un element d'una estructura de dades i, en la majoria de casos, s'utilitza per recórrer aquesta estructura
Com es declara?
Si volem declarar un iterador d'una llista d'enters, seria fent list<int>::iterator o list<int>::const_iterator. Si el volem declarar d'un vector de char, seria fent vector<char>::iterator o vector<char>::const_iterator
Diferències entre iterator i const_iterator?
iterator permet modificar el contingut de l'objecte. const_iterator no, podem recórrer l'objecte, però es queda com estava
Iteradors importants?
Bàsicament hi ha dos. Són begin() i end(). Begin apunta al primer element de l'estructura, i end apunta a fora de l'estructura. És a dir, l'estructura està al rang d'iteradors [begin,end).
Com ens movem per l'estructura?
Amb els operadors ++ i --. ++it fa que apunti al següent element, mentre que --it fa que apunti a l'anterior. Els vectors, per exemple, permeten sumar-hi números, però les llistes no.
Com consultem l'element?
Amb l'operador de desreferència *. Si tenim que it apunta a un element, fent *it consultem aquest element
Funcions de la classe list:
Un cop sabem com recórrer una llista, necessitem saber com treballar-hi. I, en aquest cas, tenim bastantes més funcions que als anteriors. Posaré les que em semblin més necessàries, si en voleu més, estan aquí. Són les següents:
begin:
Retorna un iterador que apunta al primer element de la llista
end:
Retorna un iterador que apunta a l'end, és a dir, passat l'últim element.
size:
Retorna la mida de la llista
front i back:
Retornen el primer i l'últim element, respectivament
push_front i push_back:
Afegeixen un element al principi i al final, respectivament.
pop_front i pop_back:
Eliminen el primer i l'últim element, respectivament
insert:
Inserta un element. La versió més utilitzada rep un iterador indicant la posició on volem insertar, i l'element que insertem, i retorna un iterador que apunta a l'element insertat.
erase:
Elimina un element. Rep un iterador apuntant a l'element que volem eliminar, i retorna un iterador apuntant al següent del que hem eliminat. Compte! L'iterador que li hem passat ja no és vàlid. Una cosa típica és recórrer la llista eliminant sota certes condicions. En aquest cas, hauríem de fer
...
if(*it==n) it=erase(it);
...
Així l'iterador que estem utilitzant segueix sent vàlid (ja que la funció retorna un iterador a l'element de després de l'eliminat.
splice:
Hi ha diverses versions, la més utilitzada és la que transfereix una llista a l'altra. És a dir, si féssim
l.splice(l.begin(),llista2);
El que estaríem fent és transferir els elements de llista2 al principi de l. La llista2 quedaría buida
Tenim més funcions, i les que he posat són molt més extenses. Com sempre, Google i aquesta pàgina tenen les respostes que volem. Nosaltres encara tenim estructures per conèixer
Arbre binari:
NOTA: la classe explicada aquí ha quedat obsoleta. Han creat una nova classe, de la que parlo aquí. Malgrat tot, tot el que he explicat aquí es pot aplicar amb la nova classe, simplement canviant les funcions que utilitzem
Espera espera, arbres binaris? Això no sortia a la llista d'estructures de dades que vas fer, no? Realment no. És una estructura de dades no estàndard, que ens donen els professors de PRO2.
La definició de l'arbre binari és recursiva. Un arbre binari pot ser:
-Buit
-Un node (pare), i dos arbres binaris com a fills.
No ens preocuparem (per ara) de com s'implementa internament. Només hem de saber això, que un arbre pot ser buit, o un node i dos arbres com a fills.
Un detall que podem observar és que al fitxer Arbre.hh tenim tota la implementació. No acostuma a ser bona idea implementar coses al fitxer hh, però quan utilitzem templates, ens hi veiem obligats (per raons que no venen al cas).
Node: Un arbre no deixa de ser un graf (si feu o heu fet M1, perfecte, si no... Bé, busca a Google, tampoc cal saber-ne gaire). Els elements de l'arbre, per tant, són nodes
Arrel: El node pare d'un arbre
Subarbre: El fill de l'arbre. En els arbres binaris, en tenim dos
Fulla: Un node que no té fills (normalment fem que siguin fills buits)
Glossari:
Això no és res més que una sèrie de termes sobre els arbres (de moment, binaris) bastant utilitzats.Node: Un arbre no deixa de ser un graf (si feu o heu fet M1, perfecte, si no... Bé, busca a Google, tampoc cal saber-ne gaire). Els elements de l'arbre, per tant, són nodes
Arrel: El node pare d'un arbre
Subarbre: El fill de l'arbre. En els arbres binaris, en tenim dos
Fulla: Un node que no té fills (normalment fem que siguin fills buits)
Funcions:
a_buit: Converteix el paràmetre implícit en un arbre buit
swap: Intercanvia els dos arbres
plantar: Rep un valor i dos arbres. El paràmetre implícit es transforma en un arbre tal que el pare té el valor, i els fills són els arbres que li hem passat
fills: Rep dos arbres buits. El primer es converteix en el fill esquerre del paràmetre implícit, i el segon en el dret. El paràmetre implícit deixa de ser vàlid, per altra banda
arrel: Retorna l'arrel de l'arbre
es_buit: Retorna true si l'arbre és buit, false si no
I ja està. No hi ha més funcions, i tampoc calen. La recursivitat farà la màgia
Iterar és màgic, recursivar és diví
Anem a fer uns quants exemples de coses que podem fer amb arbres.
Llegir en preordre:
La idea és anar llegint com si ens recorreguéssim l'arbre amb una cerca en profunditat. La lectura en preordre es defineix recursivament (sí, sóc un pesat) de la següent manera:
-llegim el pare
-llegim el fill esquerre
-llegim el fill dret
Es pot fer de moltes maneres, però hem de trobar una manera d'indicar que ja ha acabat aquella branca. Per exemple, jo ho faré amb el 0, de manera que en el meu arbre no hi ha 0. Per llegir-ho, seria una cosa així:
void llegir(Arbre<int>& A) {
int n;
cin >>n;
if (n!=0) {
Arbre<int> fe, fd;
llegir(fe);
llegir(fd);
A.plantar(n,fe,fd);
}
}
És a dir, llegim l'element que serà el pare de l'arbre actual. Si és diferent de 0, vol dir que hem de llegir els fills esquerre i dreta, i plantar-ho. Si és 0, vol dir que aquest arbre ha de ser nul, per tant no fem res.
Comprovar si un element hi és
bool hi_es (int x, Arbre<int>& A) {
if (A.es_buit()) return false;
Arbre<int> fe, fd;
if(A.arrel()==x) return true;
A.fills(fe,fd);
bool r=hi_es(x,fe) or hi_es(x,fd);
A.plantar(fe,fd);
return r;
}
Anem a fer algun problema
Podem fer l'exercici 1 de l'examen del 14/11/2016. Aquest ens demana calcular la mitjana i la desviació dels elements d'un arbre binari. Ens demana implementar dues funcions, i en una d'elles hem de triar els paràmetres que passem. Aquesta és la funció d'immersió, que és la que entra dins de l'arbre. Podem dir que és la que fa i desfà.
Com ho fem?
Tant per calcular la mitjana com per calcular la desviació necessitem conèixer la suma dels elements, i la quantitat d'elements. Per tant, farem que la capçalera d'immersió sigui
void i_estadist(Arbre<double>& a, double& suma, int& n)
Aleshores, volem calcular tant la suma com la quantitat d'elements, no? Podem fer que quedi una cosa així:
// Pre: a=A, suma=0 i n=0
// Post: suma representa la suma dels elements de l'arbre A
// n representa la quantitat d'elements de l'arbre A
void i_estadist(Arbre<double>& a, double& suma, int& n) {
if (a.es_buit()) return;
double valor=a.arrel();
Arbre<double> fe, fd;
a.fills(fe,fd);
double suma_e=0, suma_d=0;
int ne=0, nd=0;
i_estadist(fe,suma_e,ne);
i_estadist(fd,suma_d,nd);
a.plantar(valor,fe,fd);
suma=suma_e+suma_d+valor;
n=ne+nd+1;
}
// Pre: a = A és un arbre no buit
// Post: mitjana representa la mitjana dels elements de l’arbre A,
// desviacio representa la desviaci´o dels elements de l’arbre A
void estadist(Arbre<double>& a, double& mitjana, double& desviacio) {
double suma=0;
int n=0;
i_estadist(a,suma,n);
mitjana=suma/n;
desviacio=suma*suma/(n*n);
}
Si a és buit, no hem de sumar res, ni comptar cap element. Si no és buit, calculem la suma i la quantitat d'elements de cada fill. La suma de l'arbre serà la suma del fill esquerre més la del fill dret més el valor de l'arrel. La quantitat d'elements de l'arbre serà la quantitat d'elements del fill esquerre més la del dret més 1.
Per últim, ens demanen demostrar que això funciona. I, per fer-ho, utilitzarem un mètode que als informàtics ens encanta, i és la inducció. La meva serà de pa sucat amb oli, però a un examen s'ha de fer bé.
Cas base: En el cas buit, com que no modifiquem res, tenim que suma=0 i n=0. No hi ha elements, i per tant, no sumen res. Correcte
Inducció: Suposarem que la funció funciona. En aquest cas, la suma dels elements d'un arbre no buit serà la suma dels del fill esquerre més la dels del fill dret més l'arrel (Correcte). La quantitat d'elements serà la quantitat del fill esquerre més la del fill dret més 1. Correctes els dos.
Apunts importants sobre els arbres
Hi ha una sèrie de coses importants a tenir en compte a l'hora de programar utilitzant arbres. Actualment no sabem com funcionen els arbres per dins, però sí que penso que és important conèixer alguna cosa. Si més no, el cost de les funcions. En essència m'interessen unes funcions concretes
Plantar: Aquesta té cost constant en la majoria dels casos. L'únic cas on el cost no és constant és quan els dos arbres són el mateix (no que siguin iguals, compte, que siguin el mateix objecte exactament). En aquest cas, té cost lineal respecte als elements d'aquest arbre.
Fills: Aquesta sempre té cost constant
Arrel: Aquesta té cost constant respecte la quantitat d'elements de l'arbre. Òbviament, si és un arbre de vectors, el temps dependrà de la quantitat d'elements del vector
Per què em sembla important remarcar aquests 3 costos? Fàcil. Quan no sabem com funciona la classe internament, podem pensar que les dues primeres tenen cost lineal respecte a la mida. Al cap i a la fi, sembla que copia els elements dels fills al pare, o del pare als fills. No obstant, funciona diferent. Si no ho sabem, podem trobar-nos que intentem utilitzar-los molt poc, però l'alternativa utilitzada tingui un cost més elevat. Sabent això, sabem que utilitzar-les no és un drama
Cap comentari:
Publica un comentari a l'entrada