Algorismes llistes
De franhpWiki
En les operacions següents farem servir els paràmetres: e (element), pos (posició), i p1r (punter al primer element de la llista).
estructura node{
enter element;
estructura node *p_seg;
}
punter<-p->p_seg
Contingut |
buidar
Buida la llista alliberant, a la vegada, l’espai ocupat (cal cridar a la funció alliberar repetidament). Quan acaba, p1r apunta a nul. Tindrà el següent format:
acció buidar (estructura node *p){
var
enter i;
estructura node *aux;
fvar
per(i<-0;*(p+i)!=NUL;i++)
aux<-p;
p->(p->p_seg)
alliberar(aux);
fper
}
facció
allistar
Posa un nou element a la llista en la posició indicada. Cal cridar a la funció nou abans d’afegir l’element. En l’exemple de la figura, afegeix un element a la segona posició de la llista.
allistar(e, pos, p1r) on e és l'element a allistar i pos la posició que ha d'ocupar
acció allistar(enter elem, enter posició)
estructura node *nou,*paux;
si((nou=(struct node *)malloc(sizeof(struct node)))==NULL) escriure("error");
sino
(nou->element)<-elem;
si(posicio=0)
(nou->p_seg) <- p1r;
p1r<-nou;
nou->element<-elem;
fsi
sino
//Apunto el punter de l'anterior posició al nou
paux<-p1r;
//Em moc
per(i=0;i<(posicio-1);i++)
paux<-(paux->p_seg);
fper
(nou->p_seg)<-(paux->p_seg);
//Apunto el punter seguent de nou a la posició especificada
(paux->p_seg)<-nou;
fsi
fsi
facció
desallistar
Treu l'element de la llista de la posició indicada. Cal cridar la funció alliberar. En l’exemple de la figura, treu l’element que ocupa la segona posició de la llista. A l’igual que amb piles i cues, podem implementar aquesta operació com a acció i com a funció. En aquest darrer cas, a més de treure l’element de la llista, retorna el valor de l’element.
desallistar(pos, p1r)on pos és indica l'element ha treure
enter desallistar( enter posicio)
estructura node *aux,*p;
enter elem;
p<-p1r;
//Deso el punter especificat en un auxiliar
per(i=0;i<posicio-1;i++)
p<-(p->p_seg);
fper
aux<-p->p_seg;
//Apuntar el punter anterior al següent
(p->p_seg)<-(aux->p_seg);
//Alliberar-lo i retornar-lo
elem<-aux->element;
alliberar(aux);
retorna elem;
ffunció
posició
Funció que torna la posició que ocupa l'element a la llista.
posició(e, p1r) on e és l'element
enter posicio(enter element)
enter i;
p<-p1r;
per(i=0;*(p->element)!=element;i++)
p->(p->p_seg);
fper
retorna i;
ffunció
valor
Funció que torna el valor de l'element que ocupa la posició indicada. El valor tornat és del tipus dels elements de la llista.
valor(pos, p1r) on pos és indica la posició
enter valor(enter posició)
enter i=0;
p1r<-p;
per(i=0;i!=posicio;i++)
p->(p->p_seg)
si (p->element=NUL) retorna NUL;
fper
i<-p->element;
retorna i;
ffunció
buida?
Ens diu si la llista està buida o no.
buida?(p1r)
enter buida?()
si(p1r=NUL) return 1;
else return 0;
p<-p1r;
per(i=0;*(p->element)!=NUL;i++) p->(p->element);
si(i=0) retorna 1;
sino retorna 0;
ffunció
