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;