Estructura de datos

Clasificado en Informática

Escrito el en español con un tamaño de 8,61 KB

ESPECIFICACION  Listas

PARAMETROS GENERICOS

      TIPOS TipoElemento  

FIN PARAMETROS GENERICOS

TIPOS TipoLista

OPERACIONES

        (*CONSTRUCTORAS GENERADORAS*)

CrearVacia : -> TipoLista

Construir : TipoElemento x TipoLista -> TipoLista

      (*OBSERVADORAS SELECTORAS*)

       parcial Primero : TipoLista -> TipoElemento

       parcial Resto : TipoLista -> TipoLista

       (*OBSERVADORAS NO SELECTORAS*)

        EsVacia : TipoLista -> Booleano

        Longitud : TipoLista -> Entero

        parcial Ultimo : TipoLista -> TipoElemento

        Pertenece : TipoElemento x TipoLista -> Booleano

        (*CONSTRUCTORAS NO GENERADORAS*)

InsertarFinal: TipoElemento x TipoLista -> TipoLista

BorrarElemento : TipoElemento x TipoLista -> TipoLista

Concatenar : TipoLista x TipoLista -> TipoLista

VARIABLES:

lista: TipoLista;

el, e : TipoElemento;

ECUACIONES DE DEFINITUD

      Def (Primero (Construir (el, lista)))

      Def (Resto (Construir (el, lista)))

      Def (Ultimo (Construir (el, lista)))

ECUACIONES:

      Primero (Construir (el,lista)) = el

      Resto (Construir (el,lista)) = lista


----------------------------------------------

       EsVacia (CrearVacia) = CIERTO

       EsVacia (Construir (el,lista)) = FALSO

       Longitud (CrearVacia) = 0

       Longitud (Construir (el,lista)) = 1 + Longitud (lista)

       Ultimo (Construir (el,lista)) =

             SI EsVacia (lista) -> el

             | Ultimo (lista)

        Pertenece (e, CrearVacia) = FALSO

        Pertenece (e, Construir(el,lista)) =

               SI e = el -> CIERTO

               | Pertenece (e,lista)

------------------------------------------------

      InsertarFinal (e, CrearVacia) = Construir (e, CrearVacia) 

      InsertarFinal (e, Construir (el, lista)) = Construir (el, InsertarFinal (e, lista))

      BorrarElemento (e, CrearVacia) = CrearVacia

      BorrarElemento (e, Construir (el,lista)) =

            SI (e = el) -> lista

         | Construir (el, BorrarElemento (e,lista))

      Concatenar (CrearVacia,CrearVacia) = CrearVacia

      Concatenar (CrearVacia,Construir(el,lista)) =

                 Construir(el,lista)

      Concatenar (Construir(el,lista),CrearVacia) =

                  Construir(el,lista)

      Concatenar (Construir (elA,lista), listaA,Construir (elB,listaB)=

         Concatenar (InsertarFinal(elB,Construir (elA,lista)), listaB)

UNIT Listas;

INTERFACE

      TYPE

          TipoElemento=Integer;     

          TipoLista = ^TipoNodo;

          TipoNodo = RECORD

               info : TipoElemento;

               sig : TipoLista

           END;

(PONER LAS CABECERAS DE LOS SUBPROGRAMAS)


IMPLEMENTATION

PROCEDURE CrearVacia (VAR lista: TipoLista);

BEGIN

      lista := NIL

END;

PROCEDURE Construir (elemento: TipoElemento; VAR lista: TipoLista);

VAR

   pAux : TipoLista;

BEGIN

   New(pAux);

   pAux^.info := el;

   pAux^.sig := lista;

   lista := pAux;

END;

FUNCTION Primero (lista: TipoLista; VAR el: TipoElemento);

BEGIN

IF (NOT EsVacia (lista)) THEN

      el := lista^.info;

END;

FUNCTION SiguienteNodo (lista:TipoLista):TipoLista;

BEGIN

   IF (NOT (EsVacia(lista))) THEN

   BEGIN

      SiguienteNodo:=lista^.sig;

   END

   ELSE

   BEGIN

   SiguienteNodo:=NIL;

   END;

END;

PROCEDURE Copiar (listaO:TipoLista;VAR listaF:TipoLista);

VAR

   el:TipoElemento;

BEGIN

   CreaVacia(listaF);

   WHILE (NOT EsVacia(listaO)) DO

   BEGIN

      Primero(listaO,el);

      InsertarFinal(el,listaF);

      listaO:=SiguienteNodo(listaO);

   END;

END;

FUNCTION Resto (lista: TipoLista;VAR listaR:TipoLista);

VAR

    pAux:TipoLista;

BEGIN

      IF (NOT EsVacia (lista)) THEN

      BEGIN

         Copiar(lista,listaR);

         pAux:=listaR;

         listaR:=lista^.sig;

        dispose(pAux);

      END;

END;

FUNCTION EsVacia (lista: TipoLista): BOOLEAN;

BEGIN

   EsVacia := (lista = NIL);

END;



FUNCTION Longitud (lista: TipoLista): INTEGER;

VAR

   lon : Integer;

BEGIN

   lon := 0;

   WHILE (NOT EsVacia(lista)) DO

   BEGIN

      long := succ(lon);

      lista := SiguienteNodo(lista);

   END;

   Longitud := lon;

END;

NOTA: Función Longitud recursiva:

FUNCTION Longitud (lista: TipoLista): INTEGER;

BEGIN

   IF (EsVacia(lista)) THEN

   BEGIN

      Longitud := 0;

   END 

   ELSE

   BEGIN

      Longitud := 1 + Longitud(SiguienteNodo(lista));

   END;

END;

PROCEDURE Ultimo (lista: TipoLista; VAR el:TipoElemento); 

BEGIN

   WHILE (NOT EsVacia(SiguienteNodo(lista)) DO

   BEGIN

      lista:=SiguienteNodo(lista);

   END;

   Primero(lista,el);

END;

FUNCTION Pertenece (el: TipoElemento; lista: TipoLista): BOOLEAN;

VAR

   elAux : TipoLista;

   iguales : BOOLEAN;

BEGIN

   iguales := FALSE;

   WHILE (NOT EsVacia(lista)) AND (NOT iguales) DO

   BEGIN

      Primero(lista,elaux);

      IF (el<>elaux) THEN

      BEGIN

         lista:=SiguienteNodo(lista);

      END

      ELSE

      BEGIN

         iguales.=TRUE;

      END;

   END;

   Pertenece:=iguales;

END;

FORMA RECURSIVA:

FUNCTION Pertenece (el.TipoElemento;lista:TipoLista):Boolean;

VAR

   elaux:TipoElemento;

BEGIN

   IF (EsVacia(lista)) THEN

   BEGIN

      Pertenece:=FALSE;

   END;

   ELSE

   BEGIN

      Primero(lista,elaux);

      Resto(lista,lista);

      Perteneces:=(Iguales(el,elaux)) OR Pertenece(el,lista);

   END;

END;

 PROCEDURE Borrar Elemento (el: TipoElemento;VAR lista:TipoLista);

VAR

   encontrado: Boolean;

   laux,lant,lsig:TipoLista;

BEGIN

   encontrado:=FALSE;

   laux:=lista;

   IF (NOT EsVacia(lista)) THEN

   BEGIN

      IF (Iguales(el,lista^.info)) THEN

      BEGIN

         lista:=SiguienteNodo(lista);

         dispose(laux);

      END

      ELSE

      BEGIN

         lant:=lista;

         lsig:=SiguienteNodo(lista);

         WHILE ((NOT EsVacia(lsig)) AND (NOT encontrado)) DO

         BEGIN

            IF (Iguales(el,lsig^.info)) THEN

            BEGIN

               encontrado:=TRUE;

            END

            ELSE

            BEGIN

               lsig:=SiguienteNodo(lsig);

               lant:=SiguienteNodo(lant);

            END;

         END;

         IF (encontrado) THEN

         BEGIN

            lant^.sig:=SiguienteNodo(lsig);

            dispose(lsig);

        END;

      END;

   END;

END;

Entradas relacionadas: