Lists

Algorithms Lists

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

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ó

last updated on April 11, 2015, 7:43 p.m.
Back