From 66d8da173c875b1a62e08e36e0103bb9a3f692fc Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sun, 23 Mar 2003 07:10:16 +0000 Subject: [PATCH] =?utf8?q?Import=20inicial=20despu=C3=A9s=20del=20"/var=20?= =?utf8?q?incident".=20:(?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- arboles/apl_ab.pas | 169 ++++++ arboles/apl_abo.pas | 49 ++ arboles/arbol_bin.pas | 208 +++++++ arboles/arbol_bin_ord.pas | 286 ++++++++++ listas_pilas_colas/T_COLAC.pas | 248 +++++++++ listas_pilas_colas/T_LSC.pas | 305 +++++++++++ listas_pilas_colas/T_LSP.pas | 288 ++++++++++ listas_pilas_colas/T_PILAC.pas | 225 ++++++++ listas_pilas_colas/cola_c.pas | 248 +++++++++ listas_pilas_colas/eje_lista.pas | 139 +++++ listas_pilas_colas/lista_simple_c.pas | 300 ++++++++++ listas_pilas_colas/lista_simple_p.pas | 282 ++++++++++ listas_pilas_colas/pila_c.pas | 224 ++++++++ listas_pilas_colas/tda_almac.pas | 243 +++++++++ listas_pilas_colas/tda_gral.pas | 55 ++ tp_ejemplo/comandos.pas | 69 +++ tp_ejemplo/ldoblec.pas | 757 ++++++++++++++++++++++++++ tp_ejemplo/leeme.txt | 22 + tp_ejemplo/outfile.txt | 100 ++++ tp_ejemplo/pila_c.pas | 450 +++++++++++++++ tp_ejemplo/prueba | Bin 0 -> 1664 bytes tp_ejemplo/tabla.pas | 377 +++++++++++++ tp_ejemplo/tda_gral.pas | 115 ++++ tp_ejemplo/tp1.pas | 195 +++++++ 24 files changed, 5354 insertions(+) create mode 100644 arboles/apl_ab.pas create mode 100644 arboles/apl_abo.pas create mode 100644 arboles/arbol_bin.pas create mode 100644 arboles/arbol_bin_ord.pas create mode 100644 listas_pilas_colas/T_COLAC.pas create mode 100644 listas_pilas_colas/T_LSC.pas create mode 100644 listas_pilas_colas/T_LSP.pas create mode 100644 listas_pilas_colas/T_PILAC.pas create mode 100644 listas_pilas_colas/cola_c.pas create mode 100644 listas_pilas_colas/eje_lista.pas create mode 100644 listas_pilas_colas/lista_simple_c.pas create mode 100644 listas_pilas_colas/lista_simple_p.pas create mode 100644 listas_pilas_colas/pila_c.pas create mode 100644 listas_pilas_colas/tda_almac.pas create mode 100644 listas_pilas_colas/tda_gral.pas create mode 100644 tp_ejemplo/comandos.pas create mode 100644 tp_ejemplo/ldoblec.pas create mode 100644 tp_ejemplo/leeme.txt create mode 100644 tp_ejemplo/outfile.txt create mode 100644 tp_ejemplo/pila_c.pas create mode 100644 tp_ejemplo/prueba create mode 100644 tp_ejemplo/tabla.pas create mode 100644 tp_ejemplo/tda_gral.pas create mode 100644 tp_ejemplo/tp1.pas diff --git a/arboles/apl_ab.pas b/arboles/apl_ab.pas new file mode 100644 index 0000000..1104861 --- /dev/null +++ b/arboles/apl_ab.pas @@ -0,0 +1,169 @@ +unit apl_ab; + +{ + IMPLEMENTACION : APLICACIONES ARBOLES BINARIOS + +} +interface + +uses tda_gral, arbol_bin; + +{ procesa todos los nodos de un arbol recursivamente en INORDEN} +PROCEDURE APL_AB_recorrer_rec_in( a: AB_arbol); + +{ procesa todos los nodos de un arbol recursivamente en PREORDEN} +PROCEDURE APL_AB_recorrer_rec_pre( a: AB_arbol); + +{ procesa todos los nodos de un arbol recursivamente en POSORDEN} +PROCEDURE APL_AB_recorrer_rec_pos( a: AB_arbol); + +{ busca un elemento segun una clave determinada exhaustivamente (BUSQUEDA EXTERNA) RECURSIVO } +PROCEDURE APL_AB_buscar_externo( VAR a: AB_arbol; e: Tipo_Elem; VAR error: boolean ); + +implementation + +{ recorrer todos los nodos del arbol procesando todos los elementos } +{ ORDEN de recorrido: INORDEN, o sea, izquierda, nodo, derecha } +PROCEDURE APL_AB_recorrer_rec_in( a: AB_arbol); + PROCEDURE recorrer_rec( a: AB_arbol ); + VAR + error: boolean; + e: Tipo_Elem; + BEGIN + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_izquierda, error ); + IF not error + THEN BEGIN + recorrer_rec( a); + AB_mover_cte( a, AB_padre, error ); + END; + { proceso el nodo corriente } + AB_elem_cte( a, e); + Procesar_Elem_Recorrido( e ); + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_derecha, error ); + IF not error + THEN BEGIN + recorrer_rec( a); +{ AB_mover_cte( a, AB_padre, error ); no hace falta } + END; + END; +VAR + error: boolean; +BEGIN + { me voy a la raiz y desde allí proceso todo } + AB_mover_cte( a, AB_raiz, error ); + recorrer_rec( a ); +END; + +{ recorrer todos los nodos del arbol procesando todos los elementos } +{ ORDEN de recorrido: PREORDEN, o sea, nodo, izquierda, derecha } +PROCEDURE APL_AB_recorrer_rec_pre( a: AB_arbol); + PROCEDURE recorrer_rec( a: AB_arbol ); + VAR + error: boolean; + e: Tipo_Elem; + BEGIN + { proceso el nodo corriente } + AB_elem_cte( a, e); + Procesar_Elem_Recorrido( e ); + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_izquierda, error ); + IF not error + THEN BEGIN + recorrer_rec( a); + AB_mover_cte( a, AB_padre, error ); + END; + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_derecha, error ); + IF not error + THEN BEGIN + recorrer_rec( a); +{ AB_mover_cte( a, AB_padre, error ); no hace falta } + END; + END; +VAR + error: boolean; +BEGIN + { me voy a la raiz y desde allí proceso todo } + AB_mover_cte( a, AB_raiz, error ); + recorrer_rec( a ); +END; + +{ recorrer todos los nodos del arbol procesando todos los elementos } +{ ORDEN de recorrido: POSORDEN, o sea, izquierda, derecha, nodo } +PROCEDURE APL_AB_recorrer_rec_pos( a: AB_arbol); + PROCEDURE recorrer_rec( a: AB_arbol ); + VAR + error: boolean; + e: Tipo_Elem; + BEGIN + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_izquierda, error ); + IF not error + THEN BEGIN + recorrer_rec( a); + AB_mover_cte( a, AB_padre, error ); + END; + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_derecha, error ); + IF not error + THEN BEGIN + recorrer_rec( a); + AB_mover_cte( a, AB_padre, error ); + END; + { proceso el nodo corriente } + AB_elem_cte( a, e); + Procesar_Elem_Recorrido( e ); + END; +VAR + error: boolean; +BEGIN + { me voy a la raiz y desde allí proceso todo } + AB_mover_cte( a, AB_raiz, error ); + recorrer_rec( a ); +END; + +{ busca un elemento segun una clave determinada exhaustivamente (BUSQUEDA EXTERNA) } +PROCEDURE APL_AB_buscar_externo( VAR a: AB_arbol; e: Tipo_Elem; VAR error: boolean ); + FUNCTION buscar_rec( VAR a: AB_arbol; e: Tipo_Elem): boolean; + VAR + d: Tipo_Elem; + resultado: boolean; + BEGIN + { proceso el nodo corriente } + AB_elem_cte( a, e); + resultado := Comparar_Elementos( e, d ); + IF NOT resultado + THEN BEGIN + { no era el buscado } + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_izquierda, error ); + IF not error + THEN BEGIN + resultado := buscar_rec( a, e ); + IF NOT resultado + THEN BEGIN + { proceso el subarbol izquierdo } + AB_mover_cte( a, AB_padre, error ); + AB_mover_cte( a, AB_derecha, error ); + IF not error + THEN BEGIN + resultado := buscar_rec( a, e ); + IF NOT resultado + THEN + AB_mover_cte( a, AB_padre, error ); + END; + END; + END; + END; + buscar_rec := resultado; + END; +BEGIN + { me voy a la raiz y desde allí proceso todo } + AB_mover_cte( a, AB_raiz, error ); + error := buscar_rec( a, e ); +END; + +end. + diff --git a/arboles/apl_abo.pas b/arboles/apl_abo.pas new file mode 100644 index 0000000..1383f62 --- /dev/null +++ b/arboles/apl_abo.pas @@ -0,0 +1,49 @@ +unit apl_abo; + +{ + IMPLEMENTACION : APLICACIONES ARBOLES BINARIOS ORDENADOS + +} +interface + +uses tda_gral, arbol_bin_ord; + +{ procesa todos los nodos de un arbol recursivamente } +PROCEDURE APL_ABO_recorrer_rec( a: ABO_arbol); + +implementation + +{ recorrer todos los nodos del arbol procesando todos los elementos } +{ ORDEN de recorrido: como el contenedor ya esta ordenado se recorre en el orden definido para el orden } +PROCEDURE APL_ABO_recorrer_rec( a: ABO_arbol); + PROCEDURE recorrer_rec( a: ABO_arbol ); + VAR + error: boolean; + e: Tipo_Elem; + BEGIN + { proceso el subarbol izquierdo } + ABO_mover_cte( a, ABO_izquierda, error ); + IF not error + THEN BEGIN + recorrer_rec( a); + ABO_mover_cte( a, ABO_padre, error ); + END; + { proceso el nodo corriente } + ABO_elem_cte( a, e); + Procesar_Elem_Recorrido( e ); + { proceso el subarbol izquierdo } + ABO_mover_cte( a, ABO_derecha, error ); + IF not error + THEN BEGIN + recorrer_rec( a); +{ ABO_mover_cte( a, ABO_padre, error ); no hace falta } + END; + END; +VAR + error: boolean; +BEGIN + { me voy a la raiz y desde allí proceso todo } + ABO_mover_cte( a, ABO_raiz, error ); + recorrer_rec( a ); +END; + diff --git a/arboles/arbol_bin.pas b/arboles/arbol_bin.pas new file mode 100644 index 0000000..c0f0be0 --- /dev/null +++ b/arboles/arbol_bin.pas @@ -0,0 +1,208 @@ +unit arbol_bin; + +{ + IMPLEMENTACION : ARBOLES BINARIOS + ALMACENAMIENTO : PUNTEROS + +} +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ tipos propios del arbol binario } +TYPE + AB_movimiento = ( AB_raiz, AB_izquierda, AB_derecha, AB_padre ); + + AB_puntero = ^AB_nodo; + + AB_nodo = RECORD + Elem : Tipo_Elem; + Izquierda, + Derecha : AB_puntero; + END; + + AB_arbol = RECORD + Raiz, + Corriente: AB_puntero; + END; + +PROCEDURE AB_crear( VAR a: AB_arbol ); +FUNCTION AB_vacio( a: AB_arbol): BOOLEAN; +PROCEDURE AB_elem_cte( a: AB_arbol; VAR e: Tipo_Elem); +PROCEDURE AB_modif_cte( VAR a: AB_arbol; e: Tipo_Elem); +PROCEDURE AB_mover_cte( VAR a: AB_arbol; m: AB_movimiento; VAR error: BOOLEAN ); +PROCEDURE AB_borrar_sub( VAR a: AB_arbol; m: AB_movimiento ); +PROCEDURE AB_insertar( VAR a: AB_arbol; m: AB_movimiento; e: Tipo_Elem; VAR error: BOOLEAN ); +PROCEDURE AB_vaciar( VAR a: AB_arbol ); +PROCEDURE AB_copiar( a: AB_arbol; VAR b: AB_arbol ); + +implementation + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE AB_crear( VAR a: AB_arbol ); +BEGIN + a.Raiz := NIL; + a.Corriente := NIL; +END; + +FUNCTION AB_vacio( a: AB_arbol): BOOLEAN; +BEGIN + AB_vacio := ( a.Raiz = NIL); +END; + +PROCEDURE AB_elem_cte( a: AB_arbol; VAR e: Tipo_Elem); +BEGIN + e := a.Corriente^.Elem; +END; + +PROCEDURE AB_modif_cte( VAR a: AB_arbol; e: Tipo_Elem); +BEGIN + a.Corriente^.Elem := e; +END; + +PROCEDURE AB_mover_cte( VAR a: AB_arbol; m: AB_movimiento; VAR error: BOOLEAN ); + FUNCTION buscar_padre( p: AB_puntero; h: AB_puntero ) : AB_puntero; + VAR + ret : AB_puntero; + BEGIN + ret := NIL; + IF ( p^.Izquierda = h ) OR ( p^.Derecha = h ) + THEN + ret := p; + IF ( ret = NIL ) AND ( p^.Izquierda <> NIL ) + THEN + ret := buscar_padre ( p^.Izquierda, h ); + IF ( ret = NIL ) AND ( p^.Derecha <> NIL ) + THEN + ret := buscar_padre ( p^.Derecha, h ); + buscar_padre := ret; + END; +BEGIN + error := FALSE; + CASE m OF + AB_raiz: + A.Corriente := a.Raiz; + AB_izquierda: + IF a.Corriente^.Izquierda = NIL + THEN + error := TRUE + ELSE + a.Corriente := A.Corriente^.Izquierda; + AB_derecha: + IF A.Corriente^.Derecha = NIL + THEN + error := TRUE + ELSE + a.Corriente := A.Corriente^.Derecha; + AB_padre: + IF a.Corriente = A.Raiz + THEN + error := TRUE + ELSE + a.Corriente := buscar_padre( a.Raiz, a.Corriente ); + END; +END; + +PROCEDURE AB_borrar_sub( VAR a: AB_arbol; m: AB_movimiento ); + PROCEDURE liberar_subarbol( VAR p : AB_puntero ); + BEGIN + IF p <> NIL + THEN BEGIN + liberar_subarbol( p^.Izquierda ); + liberar_subarbol( p^.Izquierda ); + DISPOSE ( p ); + p := NIL; + END; + END; +BEGIN + CASE m OF + AB_izquierda: + liberar_subarbol( a.Corriente^.Izquierda ); + AB_derecha: + liberar_subarbol( a.Corriente^.Derecha ); + END; +END; + +PROCEDURE AB_insertar( VAR a: AB_arbol; m: AB_movimiento; e: Tipo_Elem; VAR error: BOOLEAN ); +VAR + p : AB_puntero; +BEGIN + error := FALSE; + NEW( p ); + p^.Izquierda := NIL; + p^.Derecha := NIL; + p^.Elem := e; + CASE m OF + AB_raiz: + IF a.Raiz = NIL + THEN + a.Raiz := p + ELSE + error := TRUE; + AB_izquierda: + IF a.Corriente^.Izquierda = NIL + THEN + a.Corriente^.Izquierda := p + ELSE + error := TRUE; + AB_derecha: + IF a.Corriente^.Derecha = NIL + THEN + a.Corriente^.Derecha := p + ELSE + error := TRUE; + AB_padre: + error := TRUE + END; + + IF error = FALSE + THEN + a.Corriente := p + ELSE + dispose( p ); + +END; + +PROCEDURE AB_vaciar( VAR a: AB_arbol ); + PROCEDURE liberar_subarbol( VAR p : AB_puntero ); + BEGIN + IF p <> NIL + THEN BEGIN + liberar_subarbol( p^.Izquierda ); + liberar_subarbol( p^.Derecha ); + DISPOSE ( p ); + p := NIL; + END; + END; +BEGIN + liberar_subarbol( a.Raiz ); + a.Corriente := NIL; +END; + +PROCEDURE AB_copiar( a : AB_arbol; VAR b : AB_arbol ); + PROCEDURE copiar_subarbol( o : AB_puntero; VAR d : AB_puntero ); + BEGIN + IF o <> NIL + THEN BEGIN + { tengo que copiar el nodo y llamar a la copia de los hijos } + { el procedimiento va modificando el d como viene por referencia } + NEW ( d ); + d^.Elem := o^.Elem; + d^.Izquierda := NIL; + d^.Derecha := NIL; + copiar_subarbol( o^.Izquierda, d^.Izquierda ); + copiar_subarbol( o^.Derecha , d^.Derecha ); + END; + END; +BEGIN + { tenemos que vaciar primero el arbol b (destino) } + AB_vaciar( b ); + { ahora copiamos todo el arbol origen } + copiar_subarbol( a.Raiz, b.Raiz ); + a.Corriente := a.Raiz; +END; + +end. \ No newline at end of file diff --git a/arboles/arbol_bin_ord.pas b/arboles/arbol_bin_ord.pas new file mode 100644 index 0000000..8b01eb7 --- /dev/null +++ b/arboles/arbol_bin_ord.pas @@ -0,0 +1,286 @@ +unit arbol_bin_ord; + +{ + IMPLEMENTACION : ARBOLES BINARIOS ORDENADOS + ALMACENAMIENTO : PUNTEROS + RECORRIDOS : RECURSIVOS + +} +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ tipos propios del arbol binario } +type + ABO_movimiento = ( ABO_raiz, ABO_izquierda, ABO_derecha, ABO_padre ); + + ABO_puntero = ^ABO_nodo; + + ABO_nodo = record + Elem : Tipo_Elem; + Izquierda, + Derecha : ABO_puntero; + end; + + ABO_arbol = record + Raiz, + Corriente: ABO_puntero; + end; + +PROCEDURE ABO_crear( VAR a: ABO_arbol ); +FUNCTION ABO_vacio( a: ABO_arbol): boolean; +PROCEDURE ABO_elem_cte( a: ABO_arbol; VAR e: Tipo_Elem ); +PROCEDURE ABO_modif_cte( VAR a: ABO_arbol; e: Tipo_Elem ); +PROCEDURE ABO_mover_cte( VAR a: ABO_arbol; m: ABO_movimiento; VAR error: boolean ); +PROCEDURE ABO_borrar_cte( VAR a: ABO_arbol ); +PROCEDURE ABO_insertar( VAR a: ABO_arbol; e: Tipo_Elem; VAR error: boolean ); +PROCEDURE ABO_buscar( VAR a: ABO_arbol; c: Tipo_Clave; VAR error: boolean ); +PROCEDURE ABO_vaciar( VAR a: ABO_arbol ); +PROCEDURE ABO_copiar( a : ABO_arbol; VAR b : ABO_arbol ); + +implementation + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE ABO_crear( VAR a: ABO_arbol ); + begin + a.Raiz := nil; + a.Corriente := nil; + end; + +FUNCTION ABO_vacio( a: ABO_arbol): boolean; + begin + ABO_vacio := ( a.Raiz = nil ); + end; + +PROCEDURE ABO_elem_cte( a: ABO_arbol; VAR e: Tipo_Elem); + begin + e := a.Corriente^.Elem; + end; + +PROCEDURE ABO_modif_cte( VAR a: ABO_arbol; e: Tipo_Elem); + begin + a.Corriente^.Elem := e; + end; + +PROCEDURE ABO_mover_cte( VAR a: ABO_arbol; m: ABO_movimiento; VAR error: BOOLEAN ); + FUNCTION buscar_padre( p: ABO_puntero; h: ABO_puntero ) : ABO_puntero; + var + ret : ABO_puntero; + begin + ret := nil; + if ( p^.Izquierda = h ) or ( p^.Derecha = h ) then + ret := p; + { busco ordenado, por eso pregunto por la clave } + if ( ret = nil ) and ( p^.Izquierda <> nil ) and + ( Devolver_Clave_Elem( h^.Elem ) < Devolver_Clave_Elem( p^.Elem ) ) + then + ret := buscar_padre ( p^.Izquierda, h ); + if ( ret = nil ) and ( p^.Derecha <> nil ) and + ( Devolver_Clave_Elem( h^.Elem ) > Devolver_Clave_Elem( p^.Elem ) ) + then + ret := buscar_padre ( p^.Derecha, h ); + buscar_padre := ret; + end; + begin + error := false; + case m of + ABO_raiz: + A.Corriente := a.Raiz; + ABO_izquierda: + if a.Corriente^.Izquierda = nil then + error := true + else + a.Corriente := A.Corriente^.Izquierda; + ABO_derecha: + if a.Corriente^.Derecha = nil then + error := true + else + a.Corriente := A.Corriente^.Derecha; + ABO_padre: + if a.Corriente = A.Raiz then + error := true + else + a.Corriente := buscar_padre( a.Raiz, a.Corriente ); + end; + end; + +PROCEDURE ABO_borrar_cte( VAR a: ABO_arbol ); + FUNCTION buscar_padre( p: ABO_puntero; h: ABO_puntero ) : ABO_puntero; + var + ret : ABO_puntero; + begin + ret := nil; + if ( p^.Izquierda = h ) or ( p^.Derecha = h ) then + ret := p; + { busco ordenado, por eso pregunto por la clave } + if ( ret = nil ) and ( p^.Izquierda <> nil ) and + ( Devolver_Clave_Elem( h^.Elem ) < Devolver_Clave_Elem( p^.Elem ) ) + then + ret := buscar_padre( p^.Izquierda, h ); + if ( ret = nil ) and ( p^.Derecha <> nil ) and + ( Devolver_Clave_Elem( h^.Elem ) > Devolver_Clave_Elem( p^.Elem ) ) + then + ret := buscar_padre( p^.Derecha, h ); + buscar_padre := ret; + end; + var + p : ABO_puntero; + h : ABO_puntero; + n : ABO_puntero; + begin + + if a.Corriente^.Izquierda <> nil then begin + h := a.Corriente^.Izquierda; + if a.Corriente^.Derecha <> nil then begin + { busco el nodo mas a la derecha del subarbol izquierdo } + n := a.Corriente^.Izquierda; + while n^.Derecha <> nil do begin + n := n^.Derecha; + end; + { aca asigno el subarbol derecho a donde corresponde } + n^.Derecha := a.Corriente^.Derecha; + end; + end + else + h := a.Corriente^.Derecha; + + p := buscar_padre( a.Raiz, a.Corriente ); + if p <> nil then + { no soy la raiz } + if Devolver_Clave_Elem( p^.Elem ) > Devolver_Clave_Elem( h^.Elem ) then + p^.Izquierda := h + else + p^.Derecha := h + else + { soy la raiz, la tengo que cambiar al nuevo nodo } + a.Raiz := h; + + dispose( a.Corriente ); + + if h <> nil then + a.Corriente := h + else + a.Corriente := p; + end; + +PROCEDURE ABO_insertar( VAR a: ABO_arbol; e: Tipo_Elem; VAR error: BOOLEAN ); + PROCEDURE buscar_lugar( p: ABO_puntero; e: Tipo_Elem; VAR d: ABO_puntero); + begin + { devuelve NIL si el elemento ya existe en el arbol } + if Devolver_Clave_Elem( e ) = Devolver_Clave_Elem( p^.Elem ) then + d := nil + else + if Devolver_Clave_Elem( e ) < Devolver_Clave_Elem( p^.Elem ) then + if p^.Izquierda <> nil then + buscar_lugar( p^.Izquierda, e, d ) + else + d := p + else + if p^.Derecha <> nil then + buscar_lugar( p^.Derecha, e, d ) + else + d := p + end; + var + p : ABO_puntero; + x : ABO_puntero; + begin + error := false; + new( p ); + p^.Izquierda := nil; + p^.Derecha := nil; + p^.Elem := e; + + { si el arbol esta vacio inserto directamente } + if a.Raiz = nil then + a.Raiz := p + else begin + buscar_lugar( a.Raiz, e, x ); + if x = nil then + error := true + else + if Devolver_Clave_Elem( e ) < Devolver_Clave_Elem( x^.Elem ) then + x^.Izquierda := p + else + x^.Derecha := p; + end; + + if error = false then + a.Corriente := p + else + dispose( p ); + + end; + +PROCEDURE ABO_buscar( VAR a: ABO_arbol; c: Tipo_Clave; VAR error: BOOLEAN ); + PROCEDURE buscar_lugar( p: ABO_puntero; c: Tipo_Clave; VAR d: ABO_puntero); + begin + { devuelve NIL si el elemento NO existe en el arbol } + if c = Devolver_Clave_Elem( p^.Elem ) then + d := p + else + if c < Devolver_Clave_Elem( p^.Elem ) then + if p^.Izquierda <> nil then + buscar_lugar( p^.Izquierda, c, d ) + else + d := nil + else + if p^.Derecha <> nil then + buscar_lugar( p^.Derecha, c, d ) + else + d := nil + end; + var + x : ABO_puntero; + + begin + error := false; + buscar_lugar( a.Raiz, c, x ); + if x = nil then + { no encontro el elemento en el arbol } + error := true + else + a.Corriente := x; + end; + +PROCEDURE ABO_vaciar( VAR a: ABO_arbol ); + PROCEDURE liberar_subarbol( VAR p : ABO_puntero ); + begin + if p <> nil then begin + liberar_subarbol( p^.Izquierda ); + liberar_subarbol( p^.Derecha ); + dispose( p ); + p := nil; + end; + end; + begin + liberar_subarbol( a.Raiz ); + a.Corriente := nil; + end; + +PROCEDURE ABO_copiar( a : ABO_arbol; VAR b : ABO_arbol ); + PROCEDURE copiar_subarbol( o : ABO_puntero; VAR d : ABO_puntero ); + begin + if o <> nil then begin + { tengo que copiar el nodo y llamar a la copia de los hijos } + { el procedimiento va modificando el d como viene por referencia } + new( d ); + d^.Elem := o^.Elem; + d^.Izquierda := nil; + d^.Derecha := nil; + copiar_subarbol( o^.Izquierda, d^.Izquierda ); + copiar_subarbol( o^.Derecha , d^.Derecha ); + end; + end; + begin + { tenemos que vaciar primero el arbol b (destino) } + ABO_vaciar( b ); + { ahora copiamos todo el arbol origen } + copiar_subarbol( a.Raiz, b.Raiz ); + a.Corriente := a.Raiz; + end; + +end. diff --git a/listas_pilas_colas/T_COLAC.pas b/listas_pilas_colas/T_COLAC.pas new file mode 100644 index 0000000..0cfe0de --- /dev/null +++ b/listas_pilas_colas/T_COLAC.pas @@ -0,0 +1,248 @@ +unit T_COLAC; + +{ + IMPLEMENTACION : colas + ALMACENAMIENTO : CURSORES + +} + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const COLAC_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el cursor } +TYPE + COLAC_puntero = integer; + +const + COLAC_nulo : COLAC_puntero = 0; + +type + + COLAC_nodo = RECORD + Elem : Tipo_Elem; + Sig : COLAC_puntero; + END; + + + { ahora le toca definir el cursor } + COLAC_Almac = record + almacenamiento : array [ 1 .. COLAC_MAX_CURSOR ] of COLAC_Nodo; + disponibles : array [ 1 .. COLAC_MAX_CURSOR ] of COLAC_Puntero; + primero_dispo : COLAC_Puntero; + end; + + + COLAC_Cola = RECORD + almac : COLAC_Almac; + primero: COLAC_puntero; + ultimo : COLAC_puntero; + END; + + +{ ========= } +{ INTERFASE } + + +PROCEDURE COLAC_Inicializar( VAR l: COLAC_Cola ); +FUNCTION COLAC_vacio( l: COLAC_Cola): BOOLEAN; +FUNCTION COLAC_lleno( l: COLAC_Cola): BOOLEAN; + +PROCEDURE COLAC_poner( VAR l: COLAC_Cola; e: Tipo_Elem ); +PROCEDURE COLAC_sacar( VAR l: COLAC_Cola; VAR e: Tipo_Elem); +PROCEDURE COLAC_vaciar( VAR l: COLAC_Cola ); +PROCEDURE COLAC_copiar( a: COLAC_Cola; VAR b: COLAC_Cola ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure COLAC_Almac_Inicializar( VAR almac : COLAC_Almac ); +var i : COLAC_Puntero; +begin + almac.primero_dispo := 1; + for i := 1 to COLAC_MAX_CURSOR - 1 do + begin + almac.disponibles[i] := i + 1; + end; + almac.disponibles[COLAC_MAX_CURSOR] := COLAC_Nulo; +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function COLAC_Almac_HayLugar( almac : COLAC_Almac ): boolean; +begin + COLAC_Almac_HayLugar := almac.primero_dispo <> COLAC_Nulo; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure COLAC_Almac_Reservar( VAR almac : COLAC_Almac; VAR puntero : COLAC_Puntero ); +begin + if not COLAC_Almac_HayLugar( almac ) + then + puntero := COLAC_Nulo + else begin + puntero := almac.primero_dispo; + almac.primero_dispo := almac.disponibles[ puntero ]; + end; +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure COLAC_Almac_Liberar( VAR almac : COLAC_Almac; VAR puntero : COLAC_Puntero ); +begin + almac.disponibles[ puntero ] := almac.primero_dispo; + almac.primero_dispo := puntero; + puntero := COLAC_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure COLAC_Almac_Acceder( almac : COLAC_Almac; puntero : COLAC_Puntero; VAR elemento : COLAC_Nodo ); +begin + elemento := almac.almacenamiento[ puntero ]; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure COLAC_Almac_Modificar( VAR almac : COLAC_Almac; puntero : COLAC_Puntero; elemento : COLAC_Nodo ); +begin + almac.almacenamiento[ puntero ] := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE COLAC_Inicializar( VAR l: COLAC_Cola ); +BEGIN + COLAC_Almac_Inicializar( l.almac ); + l.primero := COLAC_Nulo; + l.ultimo := COLAC_Nulo; +END; + +FUNCTION COLAC_vacio( l: COLAC_Cola): BOOLEAN; +BEGIN + COLAC_vacio := ( l.Primero = COLAC_Nulo); +END; + +FUNCTION COLAC_lleno( l: COLAC_Cola): BOOLEAN; +BEGIN + COLAC_lleno := not COLAC_Almac_HayLugar( l.almac ); +END; + +PROCEDURE COLAC_poner( VAR l: COLAC_Cola; e: Tipo_Elem); +VAR + p : COLAC_puntero; + n : COLAC_Nodo; + np: COLAC_Puntero; + m : COLAC_Nodo; +BEGIN + COLAC_Almac_Reservar( l.almac, np ); + n.Elem := e; + n.sig := COLAC_Nulo; + COLAC_Almac_Modificar( l.almac, np, n ); + + if l.ultimo <> COLAC_Nulo then begin + { la cola no esta vacia, entonces tengo que modificar el ultimo } + + { accedo al almacenamiento por el ultimo } + COLAC_Almac_Acceder( l.almac, l.ultimo, m ); + m.sig := np; + COLAC_Almac_Modificar( l.almac, l.ultimo, m ); + end + else + { si el ultimo es nulo significa que la cola esta vacia } + { pongo el primero al ultimo tambien } + l.primero := np; + l.ultimo := np; +END; + +{ pre: no esta vacia } +PROCEDURE COLAC_sacar( VAR l: COLAC_Cola; VAR e: Tipo_Elem); +VAR n : COLAC_Nodo; + tmp : COLAC_Nodo; + tmpp: COLAC_Puntero; +BEGIN + COLAC_Almac_Acceder( l.almac, l.primero, n ); + COLAC_Almac_Liberar( l.almac, l.primero ); + l.primero := n.Sig; + + { y se lo asigno al parametro } + e := n.Elem; + + if n.sig = COLAC_Nulo then + { la cola quedo vacia } + { el ultimo pasa a nulo, y el primero ya es nulo porque el siguiente de n era nulo } + l.ultimo := COLAC_Nulo; +END; + +PROCEDURE COLAC_vaciar( VAR l: COLAC_Cola ); +VAR np : COLAC_Puntero; + n : COLAC_Nodo; +BEGIN + np := l.primero; + while( np <> COLAC_Nulo ) do begin + COLAC_Almac_Acceder( l.almac, np, n ); + COLAC_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := COLAC_Nulo; + l.ultimo := COLAC_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE COLAC_copiar( a : COLAC_Cola; VAR b : COLAC_Cola ); +VAR np, mp, tmpp : COLAC_Puntero; + n, m : COLAC_Nodo; +BEGIN + if a.primero = COLAC_Nulo then exit; + np := a.primero; + COLAC_Almac_Acceder( a.almac, np, n ); + + COLAC_Almac_Reservar( b.almac, mp ); + b.primero := mp; + m.elem := n.elem; + + while( n.sig <> COLAC_Nulo ) do begin + + COLAC_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + COLAC_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + COLAC_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := COLAC_Nulo; + b.ultimo := mp; + COLAC_Almac_Modificar( b.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/T_LSC.pas b/listas_pilas_colas/T_LSC.pas new file mode 100644 index 0000000..1ef8dcc --- /dev/null +++ b/listas_pilas_colas/T_LSC.pas @@ -0,0 +1,305 @@ +unit T_LSC; + +{ + IMPLEMENTACION : LISTAS SIMPLES + ALMACENAMIENTO : CURSORES + +} + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const LSC_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el cursor } +TYPE + LSC_puntero = integer; + +const + LSC_nulo : LSC_puntero = 0; + +type + + LSC_nodo = RECORD + Elem : Tipo_Elem; + Sig : LSC_puntero; + END; + + + { ahora le toca definir el cursor } + LSC_Almac = record + almacenamiento : array [ 1 .. LSC_MAX_CURSOR ] of LSC_Nodo; + disponibles : array [ 1 .. LSC_MAX_CURSOR ] of LSC_Puntero; + primero_dispo : LSC_Puntero; + end; + + + LSC_Lista = RECORD + almac : LSC_Almac; + primero: LSC_puntero; + corriente : LSC_puntero; + END; + + LSC_movimiento = ( LSC_primero, LSC_siguiente ); + + +{ ========= } +{ INTERFASE } + + +PROCEDURE LSC_Inicializar( VAR l: LSC_Lista ); +FUNCTION LSC_vacio( l: LSC_Lista): BOOLEAN; +FUNCTION LSC_lleno( l: LSC_Lista): BOOLEAN; + +PROCEDURE LSC_elem_cte( l: LSC_Lista; VAR e: Tipo_Elem); +PROCEDURE LSC_modif_cte( VAR l: LSC_Lista; e: Tipo_Elem); +PROCEDURE LSC_mover_cte( VAR l: LSC_Lista; m: LSC_movimiento; VAR error: BOOLEAN ); +PROCEDURE LSC_borrar_cte( VAR l: LSC_Lista ); +PROCEDURE LSC_insertar( VAR l: LSC_Lista; m: LSC_movimiento; e: Tipo_Elem ); +PROCEDURE LSC_vaciar( VAR l: LSC_Lista ); +PROCEDURE LSC_copiar( a: LSC_Lista; VAR b: LSC_Lista ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure LSC_Almac_Inicializar( VAR almac : LSC_Almac ); +var i : LSC_Puntero; +begin + almac.primero_dispo := 1; + for i := 1 to LSC_MAX_CURSOR - 1 do + begin + almac.disponibles[i] := i + 1; + end; + almac.disponibles[LSC_MAX_CURSOR] := LSC_Nulo; +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function LSC_Almac_HayLugar( almac : LSC_Almac ): boolean; +begin + LSC_Almac_HayLugar := almac.primero_dispo <> LSC_Nulo; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure LSC_Almac_Reservar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); +begin + if not LSC_Almac_HayLugar( almac ) + then + puntero := LSC_Nulo + else begin + puntero := almac.primero_dispo; + almac.primero_dispo := almac.disponibles[ puntero ]; + end; +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure LSC_Almac_Liberar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); +begin + almac.disponibles[ puntero ] := almac.primero_dispo; + almac.primero_dispo := puntero; + puntero := LSC_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure LSC_Almac_Acceder( almac : LSC_Almac; puntero : LSC_Puntero; VAR elemento : LSC_Nodo ); +begin + elemento := almac.almacenamiento[ puntero ]; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure LSC_Almac_Modificar( VAR almac : LSC_Almac; puntero : LSC_Puntero; elemento : LSC_Nodo ); +begin + almac.almacenamiento[ puntero ] := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE LSC_Inicializar( VAR l: LSC_Lista ); +BEGIN + LSC_Almac_Inicializar( l.almac ); + l.primero := LSC_Nulo; + l.corriente := LSC_Nulo; +END; + +FUNCTION LSC_vacio( l: LSC_Lista): BOOLEAN; +BEGIN + LSC_vacio := ( l.Primero = LSC_Nulo); +END; + +FUNCTION LSC_lleno( l: LSC_Lista): BOOLEAN; +BEGIN + LSC_lleno := not LSC_Almac_HayLugar( l.almac ); +END; + +PROCEDURE LSC_elem_cte( l: LSC_Lista; VAR e: Tipo_Elem); +var n : LSC_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l.almac, l.Corriente, n ); + + { y se lo asigno al parametro } + e := n.Elem; +END; + +PROCEDURE LSC_modif_cte( VAR l: LSC_Lista; e: Tipo_Elem); +var n : LSC_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l.almac, l.Corriente, n ); + + { y la asigno al parametro } + n.Elem := e; + + { y modifico el almacenamiento } + LSC_Almac_Modificar( l.almac, l.Corriente, n ); + +END; + +PROCEDURE LSC_mover_cte( VAR l: LSC_Lista; m: LSC_movimiento; VAR error: BOOLEAN ); +VAR n : LSC_Nodo; +BEGIN + error := FALSE; + CASE m OF + LSC_primero: + l.Corriente := l.Primero; + LSC_siguiente: begin + + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l.almac, l.Corriente, n ); + + IF n.sig = LSC_Nulo + THEN + error := TRUE + ELSE + l.corriente := n.sig; + end; + END; +END; + +PROCEDURE LSC_borrar_cte( VAR l: LSC_Lista ); +VAR n : LSC_Nodo; + tmp : LSC_Nodo; + tmpp: LSC_Puntero; +BEGIN + if l.corriente = l.primero then begin + LSC_Almac_Acceder( l.almac, l.primero, n ); + l.primero := n.Sig; + LSC_Almac_Liberar( l.almac, l.corriente ); + l.corriente := l.primero; + end + else begin + tmpp := l.primero; + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + while( tmp.sig <> l.corriente ) do begin + tmpp := tmp.sig; + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + end; + LSC_Almac_Acceder( l.almac, l.corriente, n ); + tmp.sig := n.Sig; + LSC_Almac_Liberar( l.almac, l.corriente ); + l.corriente := tmpp; + end; +END; + +PROCEDURE LSC_insertar( VAR l: LSC_Lista; m: LSC_movimiento; e: Tipo_Elem ); +VAR + p : LSC_puntero; + n : LSC_Nodo; + np: LSC_Puntero; + an: LSC_Nodo; +BEGIN + LSC_Almac_Reservar( l.almac, np ); + n.Elem := e; + CASE m OF + LSC_primero: begin + n.sig := l.primero; + LSC_Almac_Modificar( l.almac, np, n ); + l.primero := np; + end; + LSC_siguiente: begin + LSC_Almac_Acceder( l.almac, l.corriente, an ); + n.sig := an.sig; + an.sig := np; + LSC_Almac_Modificar( l.almac, np, n ); + LSC_Almac_Modificar( l.almac, l.corriente, an ); + end; + END; + + l.Corriente := np; + +END; + +PROCEDURE LSC_vaciar( VAR l: LSC_Lista ); +VAR np : LSC_Puntero; + n : LSC_Nodo; +BEGIN + np := l.primero; + while( np <> LSC_Nulo ) do begin + LSC_Almac_Acceder( l.almac, np, n ); + LSC_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := LSC_Nulo; + l.corriente := LSC_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE LSC_copiar( a : LSC_Lista; VAR b : LSC_Lista ); +VAR np, mp, tmpp : LSC_Puntero; + n, m : LSC_Nodo; +BEGIN + if a.primero = LSC_Nulo then exit; + np := a.primero; + LSC_Almac_Acceder( a.almac, np, n ); + + LSC_Almac_Reservar( b.almac, mp ); + b.primero := mp; + b.corriente := mp; + m.elem := n.elem; + + while( n.sig <> LSC_Nulo ) do begin + + LSC_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + LSC_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + LSC_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := LSC_Nulo; + LSC_Almac_Modificar( b.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/T_LSP.pas b/listas_pilas_colas/T_LSP.pas new file mode 100644 index 0000000..2be356f --- /dev/null +++ b/listas_pilas_colas/T_LSP.pas @@ -0,0 +1,288 @@ +unit T_LSP; + +{ + IMPLEMENTACION : LISTAS SIMPLES + ALMACENAMIENTO : PUNTERO + +} + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const LSP_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el cursor } +type + + LSP_puntero = ^LSP_nodo; + + LSP_nodo = RECORD + Elem : Tipo_Elem; + Sig : LSP_puntero; + END; + + + + { ahora le toca definir el cursor } + LSP_Almac = record + end; + + + LSP_Lista = RECORD + almac : LSP_Almac; + primero: LSP_puntero; + corriente : LSP_puntero; + END; + + LSP_movimiento = ( LSP_primero, LSP_siguiente ); + +const + LSP_nulo : LSP_puntero = nil; + + +{ ========= } +{ INTERFASE } + + +PROCEDURE LSP_Inicializar( VAR l: LSP_Lista ); +FUNCTION LSP_vacio( l: LSP_Lista): BOOLEAN; +FUNCTION LSP_lleno( l: LSP_Lista): BOOLEAN; + +PROCEDURE LSP_elem_cte( l: LSP_Lista; VAR e: Tipo_Elem); +PROCEDURE LSP_modif_cte( VAR l: LSP_Lista; e: Tipo_Elem); +PROCEDURE LSP_mover_cte( VAR l: LSP_Lista; m: LSP_movimiento; VAR error: BOOLEAN ); +PROCEDURE LSP_borrar_cte( VAR l: LSP_Lista ); +PROCEDURE LSP_insertar( VAR l: LSP_Lista; m: LSP_movimiento; e: Tipo_Elem ); +PROCEDURE LSP_vaciar( VAR l: LSP_Lista ); +PROCEDURE LSP_copiar( a: LSP_Lista; VAR b: LSP_Lista ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure LSP_Almac_Inicializar( VAR almac : LSP_Almac ); +begin +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function LSP_Almac_HayLugar( almac : LSP_Almac ): boolean; +begin + LSP_Almac_HayLugar := true; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure LSP_Almac_Reservar( VAR almac : LSP_Almac; VAR puntero : LSP_Puntero ); +begin + puntero := new( LSP_puntero ); +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure LSP_Almac_Liberar( VAR almac : LSP_Almac; VAR puntero : LSP_Puntero ); +begin + dispose( puntero ); + puntero := LSP_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure LSP_Almac_Acceder( almac : LSP_Almac; puntero : LSP_Puntero; VAR elemento : LSP_Nodo ); +begin + elemento := puntero^; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure LSP_Almac_Modificar( VAR almac : LSP_Almac; puntero : LSP_Puntero; elemento : LSP_Nodo ); +begin + puntero^ := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE LSP_Inicializar( VAR l: LSP_Lista ); +BEGIN + LSP_Almac_Inicializar( l.almac ); + l.primero := LSP_Nulo; + l.corriente := LSP_Nulo; +END; + +FUNCTION LSP_vacio( l: LSP_Lista): BOOLEAN; +BEGIN + LSP_vacio := ( l.Primero = LSP_Nulo); +END; + +FUNCTION LSP_lleno( l: LSP_Lista): BOOLEAN; +BEGIN + LSP_lleno := not LSP_Almac_HayLugar( l.almac ); +END; + +PROCEDURE LSP_elem_cte( l: LSP_Lista; VAR e: Tipo_Elem); +var n : LSP_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSP_Almac_Acceder( l.almac, l.Corriente, n ); + + { y se lo asigno al parametro } + e := n.Elem; +END; + +PROCEDURE LSP_modif_cte( VAR l: LSP_Lista; e: Tipo_Elem); +var n : LSP_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSP_Almac_Acceder( l.almac, l.Corriente, n ); + + { y la asigno al parametro } + n.Elem := e; + + { y modifico el almacenamiento } + LSP_Almac_Modificar( l.almac, l.Corriente, n ); + +END; + +PROCEDURE LSP_mover_cte( VAR l: LSP_Lista; m: LSP_movimiento; VAR error: BOOLEAN ); +VAR n : LSP_Nodo; +BEGIN + error := FALSE; + CASE m OF + LSP_primero: + l.Corriente := l.Primero; + LSP_siguiente: begin + + { accedo al almacenamiento por el nodo corriente } + LSP_Almac_Acceder( l.almac, l.Corriente, n ); + + IF n.sig = LSP_Nulo + THEN + error := TRUE + ELSE + l.corriente := n.sig; + end; + END; +END; + +PROCEDURE LSP_borrar_cte( VAR l: LSP_Lista ); +VAR n : LSP_Nodo; + tmp : LSP_Nodo; + tmpp: LSP_Puntero; +BEGIN + if l.corriente = l.primero then begin + LSP_Almac_Acceder( l.almac, l.primero, n ); + l.primero := n.Sig; + LSP_Almac_Liberar( l.almac, l.corriente ); + l.corriente := l.primero; + end + else begin + tmpp := l.primero; + LSP_Almac_Acceder( l.almac, tmpp, tmp ); + while( tmp.sig <> l.corriente ) do begin + tmpp := tmp.sig; + LSP_Almac_Acceder( l.almac, tmpp, tmp ); + end; + LSP_Almac_Acceder( l.almac, l.corriente, n ); + tmp.sig := n.Sig; + LSP_Almac_Liberar( l.almac, l.corriente ); + l.corriente := tmpp; + end; +END; + +PROCEDURE LSP_insertar( VAR l: LSP_Lista; m: LSP_movimiento; e: Tipo_Elem ); +VAR + p : LSP_puntero; + n : LSP_Nodo; + np: LSP_Puntero; + an: LSP_Nodo; +BEGIN + LSP_Almac_Reservar( l.almac, np ); + n.Elem := e; + CASE m OF + LSP_primero: begin + n.sig := l.primero; + LSP_Almac_Modificar( l.almac, np, n ); + l.primero := np; + end; + LSP_siguiente: begin + LSP_Almac_Acceder( l.almac, l.corriente, an ); + n.sig := an.sig; + an.sig := np; + LSP_Almac_Modificar( l.almac, np, n ); + LSP_Almac_Modificar( l.almac, l.corriente, an ); + end; + END; + + l.Corriente := np; + +END; + +PROCEDURE LSP_vaciar( VAR l: LSP_Lista ); +VAR np : LSP_Puntero; + n : LSP_Nodo; +BEGIN + np := l.primero; + while( np <> LSP_Nulo ) do begin + LSP_Almac_Acceder( l.almac, np, n ); + LSP_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := LSP_Nulo; + l.corriente := LSP_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE LSP_copiar( a : LSP_Lista; VAR b : LSP_Lista ); +VAR np, mp, tmpp : LSP_Puntero; + n, m : LSP_Nodo; +BEGIN + if a.primero = LSP_Nulo then exit; + np := a.primero; + LSP_Almac_Acceder( a.almac, np, n ); + + LSP_Almac_Reservar( b.almac, mp ); + b.primero := mp; + b.corriente := mp; + m.elem := n.elem; + + while( n.sig <> LSP_Nulo ) do begin + + LSP_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + LSP_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + LSP_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := LSP_Nulo; + LSP_Almac_Modificar( b.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/T_PILAC.pas b/listas_pilas_colas/T_PILAC.pas new file mode 100644 index 0000000..50cbe0a --- /dev/null +++ b/listas_pilas_colas/T_PILAC.pas @@ -0,0 +1,225 @@ +unit T_PILAC; + +{ + IMPLEMENTACION : pilas + ALMACENAMIENTO : CURSORES + +} + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const PILAC_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el cursor } +TYPE + PILAC_puntero = integer; + +const + PILAC_nulo : PILAC_puntero = 0; + +type + + PILAC_nodo = RECORD + Elem : Tipo_Elem; + Sig : PILAC_puntero; + END; + + + { ahora le toca definir el cursor } + PILAC_Almac = record + almacenamiento : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Nodo; + disponibles : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Puntero; + primero_dispo : PILAC_Puntero; + end; + + + PILAC_Pila = RECORD + almac : PILAC_Almac; + primero: PILAC_puntero; + END; + + +{ ========= } +{ INTERFASE } + + +PROCEDURE PILAC_Inicializar( VAR l: PILAC_Pila ); +FUNCTION PILAC_vacio( l: PILAC_Pila): BOOLEAN; +FUNCTION PILAC_lleno( l: PILAC_Pila): BOOLEAN; + +PROCEDURE PILAC_poner( VAR l: PILAC_Pila; e: Tipo_Elem ); +PROCEDURE PILAC_sacar( VAR l: PILAC_Pila; VAR e: Tipo_Elem); +PROCEDURE PILAC_vaciar( VAR l: PILAC_Pila ); +PROCEDURE PILAC_copiar( a: PILAC_Pila; VAR b: PILAC_Pila ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure PILAC_Almac_Inicializar( VAR almac : PILAC_Almac ); +var i : PILAC_Puntero; +begin + almac.primero_dispo := 1; + for i := 1 to PILAC_MAX_CURSOR - 1 do + begin + almac.disponibles[i] := i + 1; + end; + almac.disponibles[PILAC_MAX_CURSOR] := PILAC_Nulo; +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function PILAC_Almac_HayLugar( almac : PILAC_Almac ): boolean; +begin + PILAC_Almac_HayLugar := almac.primero_dispo <> PILAC_Nulo; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure PILAC_Almac_Reservar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero ); +begin + if not PILAC_Almac_HayLugar( almac ) + then + puntero := PILAC_Nulo + else begin + puntero := almac.primero_dispo; + almac.primero_dispo := almac.disponibles[ puntero ]; + end; +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure PILAC_Almac_Liberar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero ); +begin + almac.disponibles[ puntero ] := almac.primero_dispo; + almac.primero_dispo := puntero; + puntero := PILAC_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure PILAC_Almac_Acceder( almac : PILAC_Almac; puntero : PILAC_Puntero; VAR elemento : PILAC_Nodo ); +begin + elemento := almac.almacenamiento[ puntero ]; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure PILAC_Almac_Modificar( VAR almac : PILAC_Almac; puntero : PILAC_Puntero; elemento : PILAC_Nodo ); +begin + almac.almacenamiento[ puntero ] := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE PILAC_Inicializar( VAR l: PILAC_Pila ); +BEGIN + PILAC_Almac_Inicializar( l.almac ); + l.primero := PILAC_Nulo; +END; + +FUNCTION PILAC_vacio( l: PILAC_Pila): BOOLEAN; +BEGIN + PILAC_vacio := ( l.Primero = PILAC_Nulo); +END; + +FUNCTION PILAC_lleno( l: PILAC_Pila): BOOLEAN; +BEGIN + PILAC_lleno := not PILAC_Almac_HayLugar( l.almac ); +END; + +PROCEDURE PILAC_poner( VAR l: PILAC_Pila; e: Tipo_Elem); +VAR + n : PILAC_Nodo; + np: PILAC_Puntero; +BEGIN + n.Elem := e; + n.sig := l.primero; + PILAC_Almac_Reservar( l.almac, np ); + PILAC_Almac_Modificar( l.almac, np, n ); + l.primero := np; +END; + +{ pre: no esta vacia } +PROCEDURE PILAC_sacar( VAR l: PILAC_Pila; VAR e: Tipo_Elem); +VAR n : PILAC_Nodo; + tmp : PILAC_Nodo; + tmpp: PILAC_Puntero; +BEGIN + PILAC_Almac_Acceder( l.almac, l.primero, n ); + PILAC_Almac_Liberar( l.almac, l.primero ); + l.primero := n.Sig; + + { y se lo asigno al parametro } + e := n.Elem; +END; + +PROCEDURE PILAC_vaciar( VAR l: PILAC_Pila ); +VAR np : PILAC_Puntero; + n : PILAC_Nodo; +BEGIN + np := l.primero; + while( np <> PILAC_Nulo ) do begin + PILAC_Almac_Acceder( l.almac, np, n ); + PILAC_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := PILAC_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE PILAC_copiar( a : PILAC_Pila; VAR b : PILAC_Pila ); +VAR np, mp, tmpp : PILAC_Puntero; + n, m : PILAC_Nodo; + +BEGIN + if a.primero = PILAC_Nulo then exit; + np := a.primero; + PILAC_Almac_Acceder( a.almac, np, n ); + + PILAC_Almac_Reservar( b.almac, mp ); + b.primero := mp; + m.elem := n.elem; + + while( n.sig <> PILAC_Nulo ) do begin + + PILAC_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + PILAC_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + PILAC_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := PILAC_Nulo; + PILAC_Almac_Modificar( b.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/cola_c.pas b/listas_pilas_colas/cola_c.pas new file mode 100644 index 0000000..8035f95 --- /dev/null +++ b/listas_pilas_colas/cola_c.pas @@ -0,0 +1,248 @@ +unit cola_C; + +{ + IMPLEMENTACION : colas + ALMACENAMIENTO : CURSORES + +} + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const COLA_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el cursor } +TYPE + COLAC_puntero = integer; + +const + COLAC_nulo : COLAC_puntero = 0; + +type + + COLAC_nodo = RECORD + Elem : Tipo_Elem; + Sig : COLAC_puntero; + END; + + + { ahora le toca definir el cursor } + COLAC_Almac = record + almacenamiento : array [ 1 .. COLAC_MAX_CURSOR ] of COLAC_Nodo; + siguientes : array [ 1 .. COLAC_MAX_CURSOR ] of COLAC_Puntero; + primero_dispo : TTDA_Puntero; + end; + + + COLAC_Cola = RECORD + almac : COLAC_Almac; + primero: COLAC_puntero; + ultimo : COLAC_puntero; + END; + + +{ ========= } +{ INTERFASE } + + +PROCEDURE COLAC_Inicializar( VAR l: COLAC_Cola ); +FUNCTION COLAC_vacio( l: COLAC_Cola): BOOLEAN; +FUNCTION COLAC_lleno( l: COLAC_Cola): BOOLEAN; + +PROCEDURE COLAC_poner( VAR l: COLAC_Cola; e: Tipo_Elem ); +PROCEDURE COLAC_sacar( VAR l: COLAC_Cola; VAR e: Tipo_Elem); +PROCEDURE COLAC_vaciar( VAR l: COLAC_Cola ); +PROCEDURE COLAC_copiar( l: COLAC_Cola; VAR b: COLAC_Cola ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure COLAC_Almac_Inicializar( VAR almac : COLAC_Almac ); +var i : COLAC_Puntero; +begin + almac.primero_dispo := 1; + for i := 1 to COLAC_CURSOR_MAX - 1 do + begin + siguientes[i] := i + 1; + end; + siguientes[COLAC_CURSOR_MAX] := COLAC_Nulo; +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function COLAC_Almac_HayLugar( almac : COLAC_Almac ): boolean; +begin + COLAC_Almac_HayLugar := almac.primero_dispo = COLAC_Nulo; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure COLAC_Almac_Reservar( VAR almac : COLAC_Almac; VAR puntero : COLAC_Puntero ); +begin + if not COLAC_Almac_HayLugar( almac ) + then + puntero := COLAC_Nulo + else begin + puntero := almac.primero_dispo; + almac.primero_dispo := almac.siguientes[ puntero ]; + end; +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure COLAC_Almac_Liberar( VAR almac : COLAC_Almac; VAR puntero : COLAC_Puntero ); +begin + almac.siguientes[ puntero ] := almac.primero_dispo; + almac.primero_dispo := puntero; + puntero := COLAC_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure COLAC_Almac_Acceder( almac : TTDA_Almac; puntero : COLAC_Puntero; VAR elemento : COLAC_Nodo ); +begin + elemento := almac.almacenamiento[ puntero ]; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure COLAC_Almac_Modificar( VAR almac : COLAC_Almac; puntero : COLAC_Puntero; elemento : COLAC_Nodo ); +begin + almac.almacenamiento[ puntero ] := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE COLAC_Inicializar( VAR l: COLAC_Cola ); +BEGIN + COLAC_Almac_Inicializar( l.almac ); + primero := COLAC_Nulo; + ultimo := COLAC_Nulo; +END; + +FUNCTION COLAC_vacio( l: COLAC_Cola): BOOLEAN; +BEGIN + COLAC_vacio := ( l.Primero = COLAC_Nulo); +END; + +FUNCTION COLAC_lleno( l: COLAC_Cola): BOOLEAN; +BEGIN + COLAC_lleno := not COLAC_Almac_HayLugar( l.almac ); +END; + +PROCEDURE COLAC_poner( VAR l: COLAC_Cola; e: Tipo_Elem); +VAR + p : COLAC_puntero; + n : COLAC_Nodo; + np: COLAC_Puntero; + m : COLAC_Nodo; +BEGIN + COLAC_Almac_Reservar( l.almac, np ); + n.Elem := e; + n.sig := COLAC_Nulo; + COLAC_Almac_Modificar( l.almac, np, n ); + + if l.ultimo <> COLAC_Nulo then begin + { la cola no esta vacia, entonces tengo que modificar el ultimo } + + { accedo al almacenamiento por el ultimo } + COLAC_Almac_Acceder( l, l.ultimo, m ); + m.sig := np; + COLAC_Almac_Modificar( l.almac, l.ultimo, m ); + end; + else + { si el ultimo es nulo significa que la cola esta vacia } + { pongo el primero al ultimo tambien } + l.primero := np; + l.ultimo := np; +END; + +{ pre: no esta vacia } +PROCEDURE COLAC_sacar( l: COLAC_Cola; VAR e: Tipo_Elem); +VAR n : COLAC_Nodo; + tmp : COLAC_Nodo; + tmpp: COLAC_Puntero; +BEGIN + COLAC_Almac_Acceder( l.almac, l.primero, n ); + COLAC_Almac_Liberar( l.almac, l.primero ); + l.primero := n.Sig; + + { y se lo asigno al parametro } + e := n.Elem; + + if n.sig = COLAC_Nulo then + { la cola quedo vacia } + { el ultimo pasa a nulo, y el primero ya es nulo porque el siguiente de n era nulo } + l.ultimo := COLAC_Nulo; +END; + +PROCEDURE COLAC_vaciar( VAR a: COLAC_Cola ); +VAR np : COLAC_Puntero; + n : COLAC_Nodo; +BEGIN + np := l.primero; + while( np <> COLAC_Nulo ) do begin + COLAC_Almac_Acceder( l.almac, np, n ); + COLAC_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := COLAC_Nulo; + l.ultimo := COLAC_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE COLAC_copiar( a : COLAC_Cola; VAR b : COLAC_Cola ); +VAR np : COLAC_Puntero; + n : COLAC_Nodo; +BEGIN + if a.primero = COLAC_Nulo then return; + np := a.primero; + COLAC_Almac_Acceder( a.almac, np, n ); + + COLAC_Almac_Reservar( b.almac, mp ); + b.primero := mp; + m.elem := n.elem; + + while( n.sig <> COLAC_Nulo ) do begin + + COLAC_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + COLAC_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + COLAC_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := COLAC_Nulo; + b.ultimo := mp; + COLAC_Almac_Modificar( b.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/eje_lista.pas b/listas_pilas_colas/eje_lista.pas new file mode 100644 index 0000000..032a70c --- /dev/null +++ b/listas_pilas_colas/eje_lista.pas @@ -0,0 +1,139 @@ +program eje_lista; + +{ + IMPLEMENTACION : EJERCICIOS DE ARBOLES + +} +uses tda_gral, t_lSC; + + +{ =========================================================================== } +{ =========================================================================== } +{ =========================================================================== } +{ + Este procedimiento elimina los duplicados de una lista +} +PROCEDURE eliminar_dupes( VAR l: LSC_lista); + + { + buscar a partir del corriente el proximo con un clave determinada + } + FUNCTION buscar( VAR l: LSC_lista; c: Tipo_Clave ): boolean; + VAR + enc, error: boolean; + e: Tipo_Elem; + BEGIN + { paso al siguiente de entrada } + LSC_mover_cte( l, LSC_siguiente, error ); + + enc := false; + WHILE(not error) and( not enc ) DO BEGIN + LSC_elem_cte( l, e ); + + IF Devolver_Clave_Elem( e ) = c + THEN { lo encontre } + enc := true + ELSE + { voy al siguiente } + LSC_mover_cte( l, LSC_siguiente, error ); + END; + + END; + +VAR + error: boolean; + e: Tipo_Elem; +BEGIN + { si esta vacia no tengo nada que hacer } + if LSC_Vacio( l ) THEN EXIT; + + LSC_mover_cte( l, LSC_primero, error ); + + WHILE not error DO BEGIN + + { obtengo el elemento que voy a usar como pivote, para borrar sus duplicados } + LSC_elem_cte( l, e ); + + { itero borrando dupes } + WHILE buscar( l, Devolver_Clave_Elem( e ) ) DO + LSC_borrar_cte( l ); + + { vuelvo al primero para buscar el original } + LSC_mover_cte( l, LSC_primero, error ); + error := buscar( l, Devolver_Clave_Elem( e )); + { paso al siguiente } + LSC_mover_cte( l, LSC_siguiente, error ); + + end; +END; + +{ + Insertar ordenado en una lista doblemente enlazada +} +PROCEDURE insertar_ordenado( VAR l: LDC_lista, e: Tipo_elem ); + + { + buscar a partir del corriente el proximo con un clave determinada + } + FUNCTION buscar( VAR l: LDC_lista; c: Tipo_Clave ): boolean; + VAR + enc, error: boolean; + e: Tipo_Elem; + BEGIN + { paso al siguiente de entrada } + LDC_mover_cte( l, LDC_siguiente, error ); + + enc := false; + WHILE(not error) and( not enc ) DO BEGIN + LDC_elem_cte( l, e ); + + IF Devolver_Clave_Elem( e ) = c + THEN { lo encontre } + enc := true + ELSE + { voy al siguiente } + LDC_mover_cte( l, LDC_siguiente, error ); + END; + + END; + +VAR + error: boolean; + n: Tipo_Elem; +BEGIN + { si esta vacia no tengo nada que hacer } + if LDC_Vacio( l ) + THEN BEGIN + LDC_insertar( l, primero, error ); + exit; + END; + + LDC_mover_cte( l, LDC_primero, error ); + + { busco donde corresponde insertar el elem } + error := buscar( l, Devolver_Clave_Elem( e )); + + { obtengo el elemento pivote } + LDC_elem_cte( l, n ); + + if error + THEN BEGIN + { aca se deberia manejar la insercion de duplicados } + LDC_insertar( l, LDC_siguiente, error ); + END + ELSE BEGIN + IF Devolver_Clave_Elem( e ) > Devolver_Clave_Elem( n ) + THEN + LDC_insertar( l, LDC_siguiente, error ) + ELSE + LDC_insertar( l, LDC_anterior, error ); + +END; + + +{ procedimiento principal } +VAR + a: integer; +BEGIN + +END. diff --git a/listas_pilas_colas/lista_simple_c.pas b/listas_pilas_colas/lista_simple_c.pas new file mode 100644 index 0000000..9ed0599 --- /dev/null +++ b/listas_pilas_colas/lista_simple_c.pas @@ -0,0 +1,300 @@ +unit lista_simple_C; + +{ + IMPLEMENTACION : LISTAS SIMPLES + ALMACENAMIENTO : CURSORES + +} + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const LSC_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el cursor } +TYPE + LSC_puntero = integer; + +const + LSC_nulo : LSC_puntero = 0; + +type + + LSC_nodo = RECORD + Elem : Tipo_Elem; + Sig : LSC_puntero; + END; + + + { ahora le toca definir el cursor } + LSC_Almac = record + almacenamiento : array [ 1 .. LSC_MAX_CURSOR ] of LSC_Nodo; + siguientes : array [ 1 .. LSC_MAX_CURSOR ] of LSC_Puntero; + primero_dispo : TTDA_Puntero; + end; + + + LSC_Lista_Simple_C = RECORD + almac : LSC_Almac; + primero: LSC_puntero; + corriente : LSC_puntero; + END; + + LSC_movimiento = ( LSC_primero, LSC_siguiente ); + + +{ ========= } +{ INTERFASE } + + +PROCEDURE LSC_Inicializar( VAR l: LSC_Lista_Simple_C ); +FUNCTION LSC_vacio( l: LSC_Lista_Simple_C): BOOLEAN; +FUNCTION LSC_lleno( l: LSC_Lista_Simple_C): BOOLEAN; + +PROCEDURE LSC_elem_cte( l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); +PROCEDURE LSC_modif_cte( VAR l: LSC_Lista_Simple_C; e: Tipo_Elem); +PROCEDURE LSC_mover_cte( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; VAR error: BOOLEAN ); +PROCEDURE LSC_borrar_cte( VAR l: LSC_Lista_Simple_C ); +PROCEDURE LSC_insertar( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; e: Tipo_Elem ); +PROCEDURE LSC_vaciar( VAR l: LSC_Lista_Simple_C ); +PROCEDURE LSC_copiar( l: LSC_Lista_Simple_C; VAR b: LSC_Lista_Simple_C ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure LSC_Almac_Inicializar( VAR almac : LSC_Almac ); +var i : LSC_Puntero; +begin + almac.primero_dispo := 1; + for i := 1 to LSC_CURSOR_MAX - 1 do + begin + siguientes[i] := i + 1; + end; + siguientes[LSC_CURSOR_MAX] := LSC_Nulo; +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function LSC_Almac_HayLugar( almac : LSC_Almac ): boolean; +begin + LSC_Almac_HayLugar := almac.primero_dispo = LSC_Nulo; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure LSC_Almac_Reservar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); +begin + if not LSC_Almac_HayLugar( almac ) + then + puntero := LSC_Nulo + else begin + puntero := almac.primero_dispo; + almac.primero_dispo := almac.siguientes[ puntero ]; + end; +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure LSC_Almac_Liberar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); +begin + almac.siguientes[ puntero ] := almac.primero_dispo; + almac.primero_dispo := puntero; + puntero := LSC_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure LSC_Almac_Acceder( almac : TTDA_Almac; puntero : LSC_Puntero; VAR elemento : LSC_Nodo ); +begin + elemento := almac.almacenamiento[ puntero ]; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure LSC_Almac_Modificar( VAR almac : LSC_Almac; puntero : LSC_Puntero; elemento : LSC_Nodo ); +begin + almac.almacenamiento[ puntero ] := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE LSC_Inicializar( VAR l: LSC_Lista_Simple_C ); +BEGIN + LSC_Almac_Inicializar( l.almac ); + primero := LSC_Nulo; + corriente := LSC_Nulo; +END; + +FUNCTION LSC_vacio( l: LSC_Lista_Simple_C): BOOLEAN; +BEGIN + LSC_vacio := ( l.Primero = LSC_Nulo); +END; + +FUNCTION LSC_lleno( l: LSC_Lista_Simple_C): BOOLEAN; +BEGIN + LSC_lleno := not LSC_Almac_HayLugar( l.almac ); +END; + +PROCEDURE LSC_elem_cte( l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); +var n : LSC_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l, l.Corriente, n ); + + { y se lo asigno al parametro } + e := n.Elem; +END; + +PROCEDURE LSC_modif_cte( VAR l: LSC_Lista_Simple_C; e: Tipo_Elem); +var n : LSC_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l, l.Corriente, n ); + + { y la asigno al parametro } + n.Elem := e; + + { y modifico el almacenamiento } + LSC_Almac_Modificar( l, l.Corriente, n ); + +END; + +PROCEDURE LSC_mover_cte( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; VAR error: BOOLEAN ); +VAR n : LSC_Nodo; +BEGIN + error := FALSE; + CASE m OF + LSC_primero: + l.Corriente := l.Primero; + LSC_siguiente: + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l, l.Corriente, n ); + + IF n.siguiente = LSC_Nulo + THEN + error := TRUE + ELSE + l.corriente := n.siguiente; + END; +END; + +PROCEDURE LSC_borrar_cte( VAR l: LSC_Lista_Simple_C ); +VAR n : LSC_Nodo; + tmp : LSC_Nodo; + tmpp: LSC_Puntero; +BEGIN + if l.corriente = l.primero then begin + LSC_Almac_Acceder( l.almac, l.primero, n ); + l.primero := n.Sig; + LSC_Almac_Liberar( l.almac, l.corriente ); + l.corriente := l.primero; + end; + else begin + tmpp := l.primero; + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + while( tmp.sig <> l.corriente ) do begin + tmpp := tmp.sig; + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + end; + LSC_Almac_Acceder( l.almac, l.corriente, n ); + tmp.sig := n.Sig; + LSC_Almac_Liberar( l.almac, l.corriente ); + l.corriente := tmpp; + end; +END; + +PROCEDURE LSC_insertar( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; e: Tipo_Elem ); +VAR + p : LSC_puntero; + n : LSC_Nodo; + np: LSC_Puntero; +BEGIN + LSC_Almac_Reservar( l.almac, np ); + n.Elem := e; + CASE m OF + LSC_primero: + n.sig := l.primero; + LSC_Almac_Modificar( l.almac, np, n ); + l.primero := np; + LSC_siguiente: + LSC_Almac_Acceder( l.almac, l.corriente, ant ); + n.sig := ant.sig; + ant.sig := np; + LSC_Almac_Modificar( l.almac, np, n ); + LSC_Almac_Modificar( l.almac, l.corriente, ant ); + END; + + l.Corriente := np; + +END; + +PROCEDURE LSC_vaciar( VAR a: LSC_Lista_Simple_C ); +VAR np : LSC_Puntero; + n : LSC_Nodo; +BEGIN + np := l.primero; + while( np <> LSC_Nulo ) do begin + LSC_Almac_Acceder( l.almac, np, n ); + LSC_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := LSC_Nulo; + l.corriente := LSC_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE LSC_copiar( a : LSC_Lista_Simple_C; VAR b : LSC_Lista_Simple_C ); +VAR np : LSC_Puntero; + n : LSC_Nodo; +BEGIN + if a.primero = LSC_Nulo then return; + np := a.primero; + LSC_Almac_Acceder( a.almac, np, n ); + + LSC_Almac_Reservar( b.almac, mp ); + b.primero := mp; + b.corriente := mp; + m.elem := n.elem; + + while( n.sig <> LSC_Nulo ) do begin + + LSC_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + LSC_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + LSC_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := LSC_Nulo; + LSC_Almac_Modificar( l.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/lista_simple_p.pas b/listas_pilas_colas/lista_simple_p.pas new file mode 100644 index 0000000..093ca5f --- /dev/null +++ b/listas_pilas_colas/lista_simple_p.pas @@ -0,0 +1,282 @@ +unit lista_simple_P; + +{ + IMPLEMENTACION : LISTAS SIMPLES + ALMACENAMIENTO : PUNTERO + +} + +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const LSC_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el almacenamiento } +TYPE + LSC_puntero = ^LSC_Nodo; + +const + LSC_nulo : LSC_puntero = nil; + +type + + LSC_nodo = RECORD + Elem : Tipo_Elem; + Sig : LSC_puntero; + END; + + + { ahora le toca definir el cursor } + LSC_Almac = record + end; + + + LSC_Lista_Simple_C = RECORD + almac : LSC_Almac; + primero: LSC_puntero; + corriente : LSC_puntero; + END; + + LSC_movimiento = ( LSC_primero, LSC_siguiente ); + + +{ ========= } +{ INTERFASE } + + +PROCEDURE LSC_Inicializar( VAR l: LSC_Lista_Simple_C ); +FUNCTION LSC_vacio( l: LSC_Lista_Simple_C): BOOLEAN; +FUNCTION LSC_lleno( l: LSC_Lista_Simple_C): BOOLEAN; + +PROCEDURE LSC_elem_cte( l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); +PROCEDURE LSC_modif_cte( VAR l: LSC_Lista_Simple_C; e: Tipo_Elem); +PROCEDURE LSC_mover_cte( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; VAR error: BOOLEAN ); +PROCEDURE LSC_borrar_cte( VAR l: LSC_Lista_Simple_C ); +PROCEDURE LSC_insertar( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; e: Tipo_Elem ); +PROCEDURE LSC_vaciar( VAR l: LSC_Lista_Simple_C ); +PROCEDURE LSC_copiar( l: LSC_Lista_Simple_C; VAR b: LSC_Lista_Simple_C ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure LSC_Almac_Inicializar( VAR almac : LSC_Almac ); +begin +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function LSC_Almac_HayLugar( almac : LSC_Almac ): boolean; +begin + LSC_Almac_HayLugar := true; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure LSC_Almac_Reservar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); +begin + puntero := new( LSC_Nodo ); +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure LSC_Almac_Liberar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); +begin + dispose( puntero ); + puntero := LSC_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure LSC_Almac_Acceder( almac : TTDA_Almac; puntero : LSC_Puntero; VAR elemento : LSC_Nodo ); +begin + elemento := puntero^; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure LSC_Almac_Modificar( VAR almac : LSC_Almac; puntero : LSC_Puntero; elemento : LSC_Nodo ); +begin + puntero^ := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE LSC_Inicializar( VAR l: LSC_Lista_Simple_C ); +BEGIN + LSC_Almac_Inicializar( l.almac ); + primero := LSC_Nulo; + corriente := LSC_Nulo; +END; + +FUNCTION LSC_vacio( l: LSC_Lista_Simple_C): BOOLEAN; +BEGIN + LSC_vacio := ( l.Primero = LSC_Nulo); +END; + +FUNCTION LSC_lleno( l: LSC_Lista_Simple_C): BOOLEAN; +BEGIN + LSC_lleno := not LSC_Almac_HayLugar( l.almac ); +END; + +PROCEDURE LSC_elem_cte( l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); +var n : LSC_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l, l.Corriente, n ); + + { y se lo asigno al parametro } + e := n.Elem; +END; + +PROCEDURE LSC_modif_cte( VAR l: LSC_Lista_Simple_C; e: Tipo_Elem); +var n : LSC_Nodo; +BEGIN + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l, l.Corriente, n ); + + { y la asigno al parametro } + n.Elem := e; + + { y modifico el almacenamiento } + LSC_Almac_Modificar( l, l.Corriente, n ); + +END; + +PROCEDURE LSC_mover_cte( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; VAR error: BOOLEAN ); +VAR n : LSC_Nodo; +BEGIN + error := FALSE; + CASE m OF + LSC_primero: + l.Corriente := l.Primero; + LSC_siguiente: + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder( l, l.Corriente, n ); + + IF n.siguiente = LSC_Nulo + THEN + error := TRUE + ELSE + l.corriente := n.siguiente; + END; +END; + +PROCEDURE LSC_borrar_cte( VAR l: LSC_Lista_Simple_C ); +VAR n : LSC_Nodo; + tmp : LSC_Nodo; + tmpp: LSC_Puntero; +BEGIN + if l.corriente = l.primero then begin + LSC_Almac_Acceder( l.almac, l.primero, n ); + l.primero := n.Sig; + LSC_Almac_Liberar( l.almac, l.corriente ); + l.corriente := l.primero; + end; + else begin + tmpp := l.primero; + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + while( tmp.sig <> l.corriente ) do begin + tmpp := tmp.sig; + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + end; + LSC_Almac_Acceder( l.almac, l.corriente, n ); + tmp.sig := n.Sig; + LSC_Almac_Liberar( l.almac, l.corriente ); + l.corriente := tmpp; + end; +END; + +PROCEDURE LSC_insertar( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; e: Tipo_Elem ); +VAR + p : LSC_puntero; + n : LSC_Nodo; + np: LSC_Puntero; +BEGIN + LSC_Almac_Reservar( l.almac, np ); + n.Elem := e; + CASE m OF + LSC_primero: + n.sig := l.primero; + LSC_Almac_Modificar( l.almac, np, n ); + l.primero := np; + LSC_siguiente: + LSC_Almac_Acceder( l.almac, l.corriente, ant ); + n.sig := ant.sig; + ant.sig := np; + LSC_Almac_Modificar( l.almac, np, n ); + LSC_Almac_Modificar( l.almac, l.corriente, ant ); + END; + + l.Corriente := np; + +END; + +PROCEDURE LSC_vaciar( VAR a: LSC_Lista_Simple_C ); +VAR np : LSC_Puntero; + n : LSC_Nodo; +BEGIN + np := l.primero; + while( np <> LSC_Nulo ) do begin + LSC_Almac_Acceder( l.almac, np, n ); + LSC_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := LSC_Nulo; + l.corriente := LSC_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE LSC_copiar( a : LSC_Lista_Simple_C; VAR b : LSC_Lista_Simple_C ); +VAR np : LSC_Puntero; + n : LSC_Nodo; +BEGIN + if a.primero = LSC_Nulo then return; + np := a.primero; + LSC_Almac_Acceder( a.almac, np, n ); + + LSC_Almac_Reservar( b.almac, mp ); + b.primero := mp; + b.corriente := mp; + m.elem := n.elem; + + while( n.sig <> LSC_Nulo ) do begin + + LSC_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + LSC_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + LSC_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := LSC_Nulo; + LSC_Almac_Modificar( l.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/pila_c.pas b/listas_pilas_colas/pila_c.pas new file mode 100644 index 0000000..02539b9 --- /dev/null +++ b/listas_pilas_colas/pila_c.pas @@ -0,0 +1,224 @@ +unit pila_C; + +{ + IMPLEMENTACION : pilas + ALMACENAMIENTO : CURSORES + +} + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +interface + +{ usa las funciones generales de TDAs } +uses tda_gral; + +{ maximo tamano del cursor } +const COLA_MAX_CURSOR = 100; + +{ tipos propios de la lista para definir el cursor } +TYPE + PILAC_puntero = integer; + +const + PILAC_nulo : PILAC_puntero = 0; + +type + + PILAC_nodo = RECORD + Elem : Tipo_Elem; + Sig : PILAC_puntero; + END; + + + { ahora le toca definir el cursor } + PILAC_Almac = record + almacenamiento : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Nodo; + siguientes : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Puntero; + primero_dispo : TTDA_Puntero; + end; + + + PILAC_Pila = RECORD + almac : PILAC_Almac; + primero: PILAC_puntero; + END; + + +{ ========= } +{ INTERFASE } + + +PROCEDURE PILAC_Inicializar( VAR l: PILAC_Pila ); +FUNCTION PILAC_vacio( l: PILAC_Pila): BOOLEAN; +FUNCTION PILAC_lleno( l: PILAC_Pila): BOOLEAN; + +PROCEDURE PILAC_poner( VAR l: PILAC_Pila; e: Tipo_Elem ); +PROCEDURE PILAC_sacar( VAR l: PILAC_Pila; VAR e: Tipo_Elem); +PROCEDURE PILAC_vaciar( VAR l: PILAC_Pila ); +PROCEDURE PILAC_copiar( l: PILAC_Pila; VAR b: PILAC_Pila ); + +implementation + +{ CURSORES DE ESTA IMPLEMENTACION } +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure PILAC_Almac_Inicializar( VAR almac : PILAC_Almac ); +var i : PILAC_Puntero; +begin + almac.primero_dispo := 1; + for i := 1 to PILAC_CURSOR_MAX - 1 do + begin + siguientes[i] := i + 1; + end; + siguientes[PILAC_CURSOR_MAX] := PILAC_Nulo; +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function PILAC_Almac_HayLugar( almac : PILAC_Almac ): boolean; +begin + PILAC_Almac_HayLugar := almac.primero_dispo = PILAC_Nulo; +end; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure PILAC_Almac_Reservar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero ); +begin + if not PILAC_Almac_HayLugar( almac ) + then + puntero := PILAC_Nulo + else begin + puntero := almac.primero_dispo; + almac.primero_dispo := almac.siguientes[ puntero ]; + end; +end; + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure PILAC_Almac_Liberar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero ); +begin + almac.siguientes[ puntero ] := almac.primero_dispo; + almac.primero_dispo := puntero; + puntero := PILAC_Nulo; +end; + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure PILAC_Almac_Acceder( almac : TTDA_Almac; puntero : PILAC_Puntero; VAR elemento : PILAC_Nodo ); +begin + elemento := almac.almacenamiento[ puntero ]; +end; + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure PILAC_Almac_Modificar( VAR almac : PILAC_Almac; puntero : PILAC_Puntero; elemento : PILAC_Nodo ); +begin + almac.almacenamiento[ puntero ] := elemento; +end; + + + +{ Estas son los dos procedimientos principales de la aplicación } + +PROCEDURE PILAC_Inicializar( VAR l: PILAC_Pila ); +BEGIN + PILAC_Almac_Inicializar( l.almac ); + primero := PILAC_Nulo; +END; + +FUNCTION PILAC_vacio( l: PILAC_Pila): BOOLEAN; +BEGIN + PILAC_vacio := ( l.Primero = PILAC_Nulo); +END; + +FUNCTION PILAC_lleno( l: PILAC_Pila): BOOLEAN; +BEGIN + PILAC_lleno := not PILAC_Almac_HayLugar( l.almac ); +END; + +PROCEDURE PILAC_poner( VAR l: PILAC_Pila; e: Tipo_Elem); +VAR + n : PILAC_Nodo; + np: PILAC_Puntero; +BEGIN + n.Elem := e; + n.sig := l.primero; + PILAC_Almac_Reservar( l.almac, np ); + PILAC_Almac_Modificar( l.almac, np, n ); + l.primero := np; +END; + +{ pre: no esta vacia } +PROCEDURE PILAC_sacar( l: PILAC_Pila; VAR e: Tipo_Elem); +VAR n : PILAC_Nodo; + tmp : PILAC_Nodo; + tmpp: PILAC_Puntero; +BEGIN + PILAC_Almac_Acceder( l.almac, l.primero, n ); + PILAC_Almac_Liberar( l.almac, l.primero ); + l.primero := n.Sig; + + { y se lo asigno al parametro } + e := n.Elem; +END; + +PROCEDURE PILAC_vaciar( VAR a: PILAC_Pila ); +VAR np : PILAC_Puntero; + n : PILAC_Nodo; +BEGIN + np := l.primero; + while( np <> PILAC_Nulo ) do begin + PILAC_Almac_Acceder( l.almac, np, n ); + PILAC_Almac_Liberar( l.almac, np ); + np := n.sig; + end; + l.primero := PILAC_Nulo; +END; + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } +PROCEDURE PILAC_copiar( a : PILAC_Pila; VAR b : PILAC_Pila ); +VAR np : PILAC_Puntero; + n : PILAC_Nodo; +BEGIN + if a.primero = PILAC_Nulo then return; + np := a.primero; + PILAC_Almac_Acceder( a.almac, np, n ); + + PILAC_Almac_Reservar( b.almac, mp ); + b.primero := mp; + m.elem := n.elem; + + while( n.sig <> PILAC_Nulo ) do begin + + PILAC_Almac_Reservar( b.almac, tmpp ); + m.sig := tmpp; + PILAC_Almac_Modificar( b.almac, mp, m ); + + np := n.sig; + PILAC_Almac_Acceder( a.almac, np, n ); + + mp := tmpp; + m.elem := n.elem; + + end; + m.sig := PILAC_Nulo; + PILAC_Almac_Modificar( b.almac, mp, m ); +END; + +end. diff --git a/listas_pilas_colas/tda_almac.pas b/listas_pilas_colas/tda_almac.pas new file mode 100644 index 0000000..c2febea --- /dev/null +++ b/listas_pilas_colas/tda_almac.pas @@ -0,0 +1,243 @@ +unit tda_almac; +{ + unidad basica de almacenamiento de elementos en los tipos de dato abstractos + + en esta unidad pretendemos definir como se almacenan los elementos en las listas, pilas, etc... + vamos a definir una base sobre la cual ellas van a pedir y liberar elemntos. + esta base no es necesariamente general para todos los TDAs que se definan, + simplemente demuestra como se puede hacer una interface unica, y que luego se implemente de + distintas maneras, por ejemplo cursores, punteros, etc, sin cambiar la implementacion del tipo. +} + +{ + ACLARACION RESPECTO A LA INTERFASE + ++++++++++++++++++++++++++++++++++ + + por razones que no vienen al caso explicar en este comentario, se deben definir e implementar estas + primitivas para cada tipo que se vaya a usar, obviamente con nombres distintos. + Asi que vamos a definir como notacion poner un prefijo que indique el tipo que se esta refiriendo + + + ACLARACION 2 + ============ + + este codigo no compila, porque su intencion es mostrar ambas interfases juntas, para cada implementacion + se debe codificar la que corresponda + +} + +interface + +uses tda_gral; + +{ + esta es la interfase comun para el almacenamiento de elementos + usando esta interfase se pueden hacer todas lo necesario con los datos + y se puede implementar de la forma mas conveniente. + Vamos a implementar esta interfase con cursores y punteros, + ambas al mismo tiempo, asi se pueden ver las diferencias entre una y otra +} +const +{ ================================================================= } +{ para cursores debo definir primero cuanto es el tamano del cursor } +TTDA_MAX_CURSOR = 100; + + +type +{ =================================== } +{ defino el puntero de almacenamiento } + +{ CURSORES } +TTDA_Puntero = int; + +{ PUNTEROS } +TTDA_Puntero = ^TTDA_Nodo; + + +const +{ ======================================= } +{ debemos definir un tipo de puntero nulo } + +{ CURSORES } +TTDA_Nulo : TTDA_Puntero = 0; + +{ PUNTEROS } +TTDA_Nulo : TTDA_Puntero = nil; + + +type +{ ====================================== } +{ defino la estructura de almacenamiento } + +{ CURSORES } +TTDA_Almac = record + almacenamiento : array [ 1 .. TTDA_MAX_CURSOR ] of TTDA_Nodo; + siguientes : array [ 1 .. TTDA_MAX_CURSOR ] of TTDA_Puntero; + primero_dispo : TTDA_Puntero; +end; + +{ PUNTEROS } +TTDA_Almac = record + { esta vacia porque logicamente esta administracion la hace el lenguaje } +end; + + +{ ========= } +{ INTERFASE } + +{ ========================================================================== } +{ inicializar el almacenamiento } +{ PRE : 'almac' no esta inicializado } +{ POST: 'almac' esta inicializado y vacio } +procedure TTDA_Almac_Inicializar( VAR almac : TTDA_Almac ); + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces retorna TRUE y sino FALSE } +function TTDA_Almac_HayLugar( almac : TTDA_Almac ): boolean; + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +{ PRE : 'almac' esta inicializado } +{ POST: si hay lugar en 'almac' para un nuevo elemento, + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + sino 'puntero' tiene el valor TTDA_Nulo } +procedure TTDA_Almac_Reservar( VAR almac : TTDA_Almac; VAR puntero : TTDA_Puntero ); + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } +procedure TTDA_Almac_Liberar( VAR almac : TTDA_Almac; VAR puntero : TTDA_Puntero ); + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } +procedure TTDA_Almac_Acceder( almac : TTDA_Almac; puntero : TTDA_Puntero; VAR elemento : TTDA_Nodo ); + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } +procedure TTDA_Almac_Modificar( VAR almac : TTDA_Almac; puntero : TTDA_Puntero; elemento : TTDA_Nodo ); + + +implementation + +{ CURSORES } +{ ========================================================================== } +{ inicializar el almacenamiento } +procedure TTDA_Almac_Inicializar( VAR almac : TTDA_Almac ); +var i : TTDA_Puntero; +begin + almac.primero_dispo := 1; + for i := 1 to TTDA_CURSOR_MAX - 1 do + begin + siguientes[i] := i + 1; + end; + siguientes[TTDA_CURSOR_MAX] := TTDA_Nulo; +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +function TTDA_Almac_HayLugar( almac : TTDA_Almac ): boolean; +begin + TTDA_Almac_HayLugar := almac.primero_dispo = TTDA_Nulo; +end; + + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +procedure TTDA_Almac_Reservar( VAR almac : TTDA_Almac; VAR puntero : TTDA_Puntero ); +begin + if not TTDA_Almac_HayLugar( almac ) + then + puntero := TTDA_Nulo + else begin + puntero := almac.primero_dispo; + almac.primero_dispo := almac.siguientes[ puntero ]; + end; +end; + + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +procedure TTDA_Almac_Liberar( VAR almac : TTDA_Almac; VAR puntero : TTDA_Puntero ); +begin + almac.siguientes[ puntero ] := almac.primero_dispo; + almac.primero_dispo := puntero; + puntero := TTDA_Nulo; +end; + + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +procedure TTDA_Almac_Acceder( almac : TTDA_Almac; puntero : TTDA_Puntero; VAR elemento : TTDA_Nodo ); +begin + elemento := almac.almacenamiento[ puntero ]; +end; + + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +procedure TTDA_Almac_Modificar( VAR almac : TTDA_Almac; puntero : TTDA_Puntero; elemento : TTDA_Nodo ); +begin + almac.almacenamiento[ puntero ] := elemento; +end; + + + +{ PUNTEROS } +{ ========================================================================== } +{ inicializar el almacenamiento } +procedure TTDA_Almac_Inicializar( VAR almac : TTDA_Almac ); +begin +end; + +{ ========================================================================== } +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } +function TTDA_Almac_HayLugar( almac : TTDA_Almac ): boolean; +begin + { aca habria que hacer alguna consulta a la memoria libre } + TTDA_Almac_HayLugar := true; +end; + + +{ ========================================================================== } +{ el pedido de un nuevo elemento al almacenamiento } +procedure TTDA_Almac_Reservar( VAR almac : TTDA_Almac; VAR puntero : TTDA_Puntero ); +begin + puntero := new( TTDA_Nodo ); +end; + + +{ ========================================================================== } +{ liberar un elemento del almacenamiento } +procedure TTDA_Almac_Liberar( VAR almac : TTDA_Almac; VAR puntero : TTDA_Puntero ); +begin + dispose( puntero ); + puntero := TTDA_Nulo; +end; + + +{ ========================================================================== } +{ acceder al elemento del almacenamiento apuntado por un puntero } +procedure TTDA_Almac_Acceder( almac : TTDA_Almac; puntero : TTDA_Puntero; VAR elemento : TTDA_Nodo ); +begin + elemento := puntero^; +end; + + +{ ========================================================================== } +{ modificar el elemento del almacenamiento apuntado por un puntero } +procedure TTDA_Almac_Modificar( VAR almac : TTDA_Almac; puntero : TTDA_Puntero; elemento : TTDA_Nodo ); +begin + puntero^ := elemento; +end; + + +{ fin de la unidad } +end. diff --git a/listas_pilas_colas/tda_gral.pas b/listas_pilas_colas/tda_gral.pas new file mode 100644 index 0000000..dadd909 --- /dev/null +++ b/listas_pilas_colas/tda_gral.pas @@ -0,0 +1,55 @@ +unit tda_gral; +{ funciones y datos y tipo generales de los TDA de almacenamiento } + +interface + +{ aca se define el famoso tipo_elem } +type + TipoDNI = 1000000..50000000; + Persona = record + DNI : TipoDNI; + Nombre : String; + Apellido : String; + end; + + Tipo_Clave = TipoDNI; + Tipo_Elem = Persona; + +{ esta funcion devuelve la clave de un elemento almacenado } +{ PRE : ninguna } +{ POST: devuelve la clave de un elemento E } +function Devolver_Clave_Elem( E: Tipo_Elem): Tipo_Clave; + +{ este procedimiento se usa en recorridos e imprime los datos del elemento } +{ PRE : ninguna } +{ POST: se imprimieron los datos } +procedure Procesar_Elem_Recorrido( var e: Tipo_Elem); + +{ compara dos elementos completos para ver si cumplen con el criterio o no } +FUNCTION Comparar_Elementos( a: Tipo_Elem; b: Tipo_Elem ): boolean; + +implementation + +{ esta funcion devuelve la clave de un elemento almacenado } +function Devolver_Clave_Elem( E: Tipo_Elem): Tipo_Clave; +begin + Devolver_Clave_Elem := E.DNI; +end; + +{ este procedimiento se usa en recorridos e imprime los datos del elemento } +procedure Procesar_Elem_Recorrido( var e: Tipo_Elem); +BEGIN + +END; + +{ compara dos elementos completos para ver si cumplen con el criterio o no } +FUNCTION Comparar_elementos( a: Tipo_Elem; b: Tipo_Elem ): boolean; +BEGIN + IF a.DNI = b.DNI + THEN + Comparar_Elementos := true + ELSE + Comparar_Elementos := false; +END; + +end. diff --git a/tp_ejemplo/comandos.pas b/tp_ejemplo/comandos.pas new file mode 100644 index 0000000..b526fe3 --- /dev/null +++ b/tp_ejemplo/comandos.pas @@ -0,0 +1,69 @@ +program comandos; +{ + TRABAJO PRACTICO NUMERO 1 + 1er Cuatrimestre 2000 + Este programa sirve para generar los archivos binarios de entrada + para el programa del TP nro 1, ya que en clase se acordo hacerlos + binarios. Hubiera sido mas comodo que fueran de texto, pero que le + vamos a hacer. + Parametros: archivo de salida + +} + +Type + T_registro_entrada = record + Comando: string[2]; + DNI: string[8]; + Nombre: string[40]; + Movimiento: string[1]; + DNI_hasta: string[8]; + End; + + +Var outfile: file of T_registro_entrada; + r: T_registro_entrada; + +begin + + If paramcount >= 1 then begin + Writeln('Archivo de Salida :',ParamStr(1)); + + Assign(outfile, ParamStr(1)); + + Rewrite (outfile); + + { readln(r.comando);{, r.dni, r.nombre);} + + while true do begin + + write('COMANDO :'); + readln(r.comando); + if r.comando = '' then exit; + + write('DNI :'); + readln(r.dni); + if r.dni = '' then r.dni := '*'; + + write('NOMBRE :'); + readln(r.nombre); + if r.nombre = '' then r.nombre := '*'; + + write('MOVIMIENTO p/a/s/u:'); + readln(r.movimiento); + if r.movimiento = '' then r.movimiento := '*'; + + write('DNI_HASTA :'); + readln(r.dni_hasta); + if r.dni_hasta = '' then r.dni_hasta := '*'; + + + write(outfile, r); + + end; + + end + else writeln ('Numero de parametros incorrecto. Uso comandos '); + + +end. + diff --git a/tp_ejemplo/ldoblec.pas b/tp_ejemplo/ldoblec.pas new file mode 100644 index 0000000..a283f17 --- /dev/null +++ b/tp_ejemplo/ldoblec.pas @@ -0,0 +1,757 @@ +unit ldoblec; + + + +{ + + IMPLEMENTACION : LISTAS DOBLEMENTE ENLAZADAS + + ALMACENAMIENTO : CURSORES + + + +} + + + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } +(* +Este c¢digo esta basado en la implementacion de listas simples dada +por la c tedra. +*) + +interface + + + +{ usa las funciones generales de TDAs } + +uses tda_gral; + + + +{ maximo tamano del cursor } + +const LSC_MAX_CURSOR = 100; + + + +{ tipos propios de la lista para definir el cursor } + +TYPE + + LSC_puntero = Integer; + + + +const + + LSC_nulo : LSC_puntero = 0; + + + +type + + + + LSC_nodo = RECORD + + Elem : Tipo_Elem; {definido en TDA_GRAL} + + Sig,Ant : LSC_puntero; + + END; + + + + { ahora le toca definir el cursor } + + LSC_Almac = record + + almacenamiento : array [ 1 .. LSC_MAX_CURSOR ] of LSC_Nodo; + + siguientes : array [ 1 .. LSC_MAX_CURSOR ] of LSC_Puntero; + + anteriores : array [ 1 .. LSC_MAX_CURSOR ] of LSC_Puntero; + + {decia: primero_dispo : TTDA_Puntero;} + primero_dispo: LSC_puntero; + + end; + + + + + + LSC_Lista_Simple_C = RECORD + + almac : LSC_Almac; + + primero: LSC_puntero; + + corriente : LSC_puntero; + + END; + + + + LSC_movimiento = (LSC_primero, LSC_ultimo, LSC_siguiente,LSC_anterior ); + + + + + +{ ========= } + +{ INTERFACE } + + + + + +PROCEDURE LSC_Inicializar ( VAR l: LSC_Lista_Simple_C ); + +FUNCTION LSC_vacio( l: LSC_Lista_Simple_C): BOOLEAN; + +FUNCTION LSC_lleno( l: LSC_Lista_Simple_C): BOOLEAN; + + + +PROCEDURE LSC_elem_cte ( l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); + +PROCEDURE LSC_modif_cte ( VAR l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); + +PROCEDURE LSC_mover_cte ( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; VAR error: BOOLEAN ); + +PROCEDURE LSC_borrar_cte ( VAR l: LSC_Lista_Simple_C ); + +PROCEDURE LSC_insertar ( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; var e: Tipo_Elem ); + +PROCEDURE LSC_vaciar ( VAR l: LSC_Lista_Simple_C ); + +PROCEDURE LSC_copiar ( a: LSC_Lista_Simple_C; VAR b: LSC_Lista_Simple_C ); + + + +implementation + + + +{ CURSORES DE ESTA IMPLEMENTACION } + +{ ========================================================================== } + +{ inicializar el almacenamiento } + +{ PRE : 'almac' no esta inicializado } + +{ POST: 'almac' esta inicializado y vacio } + +procedure LSC_Almac_Inicializar( VAR almac : LSC_Almac ); + +var i : LSC_Puntero; + +begin + + almac.primero_dispo := 1; + +{ almac.anteriores[1] := LSC_Nulo;} + + for i := 1 to LSC_MAX_CURSOR - 1 do + + begin + + almac.siguientes[i] := i + 1; +{ almac.anteriores[i+1] := i;} + + end; + + almac.siguientes[LSC_MAX_CURSOR] := LSC_Nulo; + +end; + + + +{ ========================================================================== } + +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } + +{ PRE : 'almac' esta inicializado } + +{ POST: si hay lugar en 'almac' para un nuevo elemento, + + entonces retorna TRUE y sino FALSE } +{MODIFICACION: Retornaba false si NO habia lugar. Ademas el +parametro ahora viene por referencia.} + +function LSC_Almac_HayLugar( var almac : LSC_Almac ): boolean; + +begin + + LSC_Almac_HayLugar := NOT (almac.primero_dispo = LSC_Nulo); + +end; + + + +{ ========================================================================== } + +{ el pedido de un nuevo elemento al almacenamiento } + +{ PRE : 'almac' esta inicializado } + +{ POST: si hay lugar en 'almac' para un nuevo elemento, + + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + + sino 'puntero' tiene el valor TTDA_Nulo } + +procedure LSC_Almac_Reservar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); + +begin + + if not LSC_Almac_HayLugar( almac ) + + then + + puntero := LSC_Nulo + + else begin + + puntero := almac.primero_dispo; + + almac.primero_dispo := almac.siguientes[ puntero ]; + + end; + +end; + + + +{ ========================================================================== } + +{ liberar un elemento del almacenamiento } + +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } + +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } + +procedure LSC_Almac_Liberar( VAR almac : LSC_Almac; VAR puntero : LSC_Puntero ); + +begin + + almac.siguientes[ puntero ] := almac.primero_dispo; + + almac.primero_dispo := puntero; + + puntero := LSC_Nulo; + +end; + + + +{ ========================================================================== } + +{ acceder al elemento del almacenamiento apuntado por un puntero } + +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } + +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } + +procedure LSC_Almac_Acceder( almac : LSC_Almac; puntero : LSC_Puntero; VAR elemento : LSC_Nodo ); + +begin + + elemento := almac.almacenamiento[ puntero ]; + +end; + + + +{ ========================================================================== } + +{ modificar el elemento del almacenamiento apuntado por un puntero } + +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } + +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } + +procedure LSC_Almac_Modificar( VAR almac : LSC_Almac; puntero : LSC_Puntero; elemento : LSC_Nodo ); + +begin + + almac.almacenamiento[ puntero ] := elemento; + +end; + + + + + + + +{ Estas son los dos procedimientos principales de la aplicación } + + + +PROCEDURE LSC_Inicializar ( VAR l: LSC_Lista_Simple_C ); + +BEGIN + + LSC_Almac_Inicializar( l.almac ); + + l.primero := LSC_Nulo; + + l.corriente := LSC_Nulo; + +END; + + + +FUNCTION LSC_vacio( l: LSC_Lista_Simple_C): BOOLEAN; + +BEGIN + + LSC_vacio := ( l.Primero = LSC_Nulo); + +END; + + + +FUNCTION LSC_lleno( l: LSC_Lista_Simple_C): BOOLEAN; + +BEGIN + + LSC_lleno := not LSC_Almac_HayLugar( l.almac ); + +END; + + + +PROCEDURE LSC_elem_cte ( l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); + +var n : LSC_Nodo; + +BEGIN + + { accedo al almacenamiento por el nodo corriente } + + LSC_Almac_Acceder ( l.almac, l.Corriente, n ); + + + + { y se lo asigno al parametro } + + e := n.Elem; + +END; + + + +PROCEDURE LSC_modif_cte ( VAR l: LSC_Lista_Simple_C; VAR e: Tipo_Elem); + +var n : LSC_Nodo; + +BEGIN + + { accedo al almacenamiento por el nodo corriente } + + LSC_Almac_Acceder ( l.almac, l.Corriente, n ); + + + + { y la asigno al parametro } + + n.Elem := e; + + + + { y modifico el almacenamiento } + + LSC_Almac_Modificar ( l.almac, l.Corriente, n ); + + + +END; + + + +PROCEDURE LSC_mover_cte ( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; VAR error: BOOLEAN ); + +VAR n : LSC_Nodo; prueba: integer ; + +BEGIN + + error := FALSE; + + CASE m OF + + LSC_primero: + + l.Corriente := l.Primero; + + LSC_anterior: + + BEGIN + { accedo al almacenamiento por el nodo corriente } + + LSC_Almac_Acceder ( l.almac, l.Corriente, n ); + + + + {modificado, decia n.siguiente} + IF n.ant = LSC_Nulo + + + THEN + + error := TRUE + + ELSE + + l.corriente := n.ant; + + + END; {BEGIN} + + LSC_siguiente: + BEGIN + { accedo al almacenamiento por el nodo corriente } + LSC_Almac_Acceder ( l.almac, l.Corriente, n ); + + + + {modificado, decia n.siguiente} + IF n.sig = LSC_Nulo + + + THEN + + error := TRUE + + ELSE + +{decia: l.corriente := n.siguiente;} + l.corriente := n.sig; + + END; {BEGIN} + + {Implementacion recursiva de mover al ultimo,para listas + doblemente enlazadas.} + + LSC_ultimo: + BEGIN + { accedo al almacenamiento por el nodo corriente } + + + LSC_mover_cte ( l, lsc_siguiente, error); + + IF error <> true then + + LSC_mover_cte ( l, lsc_ultimo, error); + + error:= false + + END; {BEGIN} + + END;{CASE} + +END; {PROCEDURE} + + + +PROCEDURE LSC_borrar_cte ( VAR l: LSC_Lista_Simple_C ); + +VAR n : LSC_Nodo; + + tmp,tmp2 : LSC_Nodo; + + tmpp : LSC_Puntero; + +BEGIN + + if l.corriente = l.primero then begin + + LSC_Almac_Acceder( l.almac, l.primero, n ); + + l.primero := n.Sig; + + LSC_Almac_Liberar( l.almac, l.corriente ); + + l.corriente := l.primero; + + {Asigno a l.primero^.ant un valor LSC_Nulo, en las siguientes 3 lineas} + + LSC_Almac_Acceder( l.almac, l.primero, tmp ); + + tmp.ant:= LSC_Nulo; + + LSC_Almac_Modificar( l.almac, l.primero, tmp ); + + end + + else begin + + tmpp := l.primero; + + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + + while( tmp.sig <> l.corriente ) do begin + + tmpp := tmp.sig; + + LSC_Almac_Acceder( l.almac, tmpp, tmp ); + + end; + + LSC_Almac_Acceder( l.almac, l.corriente, n ); + + tmp.sig := n.Sig; + + LSC_Almac_Modificar( l.almac, tmpp, tmp ); {creo que esto faltaba} + + {Agregado: este IF modifica el anterior del siguiente, siempre + que corriente no sea el ultimo} + + IF n.sig <> LSC_Nulo THEN + BEGIN + + LSC_Almac_Acceder( l.almac, n.sig, tmp2 ); + + tmp2.ant:= tmpp; + + LSC_Almac_Modificar( l.almac, tmp.sig, tmp2 ); + END; + + LSC_Almac_Liberar( l.almac, l.corriente ); + + l.corriente := tmpp; + + end; + +END; + + + +PROCEDURE LSC_insertar ( VAR l: LSC_Lista_Simple_C; m: LSC_movimiento; var e: Tipo_Elem ); + +VAR + + p : LSC_puntero; + + n : LSC_Nodo; + + ant,sig : LSC_Nodo; + + np: LSC_Puntero; + +BEGIN + + n.ant:= lsc_nulo; + + LSC_Almac_Reservar( l.almac, np ); + + n.Elem := e; + + CASE m OF + + LSC_primero: + + BEGIN + + {Agregado: cambiar l.primero^.ant a el nuevo nodo} + IF l.primero <> LSC_NULO THEN + BEGIN + LSC_Almac_Acceder( l.almac, l.primero, ant ); + + ant.ant := np; + + LSC_Almac_Modificar( l.almac, l.primero, ant ); + END; + + n.sig := l.primero; + + LSC_Almac_Modificar ( l.almac, np, n ); + + l.primero := np; + + END; + + LSC_anterior: + + BEGIN + + + LSC_Almac_Acceder( l.almac, l.corriente, sig ); + + n.sig := l.corriente; + n.ant := sig.ant; + + sig.ant := np; + + + IF n.ant <> lsc_nulo then begin + + LSC_Almac_Acceder( l.almac, n.ant, ant ); + + ant.sig := np; + + LSC_Almac_Modificar( l.almac, n.ant, ant ); + + end; + + LSC_Almac_Modificar( l.almac, np, n ); + + LSC_Almac_Modificar( l.almac, l.corriente, sig ); + + If l.corriente = L.primero then l.primero:= np; + + + END;{BEGIN} + + LSC_siguiente: + + BEGIN + + + LSC_Almac_Acceder( l.almac, l.corriente, ant ); + + n.sig := ant.sig; + n.ant := l.corriente; + + ant.sig := np; + + {Agregado: cambia n.sig^.ant a el nuevo nodo} + + IF n.sig <> lsc_nulo then begin + + LSC_Almac_Acceder( l.almac, n.sig, sig ); + + sig.ant := np; + + LSC_Almac_Modificar( l.almac, n.sig, sig ); + + end; + + LSC_Almac_Modificar( l.almac, np, n ); + + LSC_Almac_Modificar( l.almac, l.corriente, ant ); + + + + END;{BEGIN} + END;{CASE} + + + + l.Corriente := np; + + + +END; + + + +PROCEDURE LSC_vaciar ( VAR l: LSC_Lista_Simple_C ); + +VAR np : LSC_Puntero; + + n : LSC_Nodo; + +BEGIN + + LSC_Inicializar(l); {esta es otra forma de vaciar una lista, ya que la + original no estoy seguro de que funciona} + + +(* np := l.primero; + + while( np <> LSC_Nulo ) do begin + + LSC_Almac_Acceder( l.almac, np, n ); + + LSC_Almac_Liberar( l.almac, np ); + + np := n.sig; + + end; + + l.primero := LSC_Nulo; + + l.corriente := LSC_Nulo; +*) + +END; + + + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } + +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } + +PROCEDURE LSC_copiar ( a : LSC_Lista_Simple_C; VAR b : LSC_Lista_Simple_C ); + +VAR np,mp,tmpp : LSC_Puntero; + + n,m : LSC_Nodo; + +BEGIN + +{ if a.primero = LSC_Nulo then return; {return no existe} + + if a.primero = LSC_Nulo then exit; + + + np := a.primero; + + LSC_Almac_Acceder( a.almac, np, n ); + + + + LSC_Almac_Reservar( b.almac, mp ); + + b.primero := mp; + + b.corriente := mp; + + m.elem := n.elem; + + m.ant := n.ant; {agregado para listas dobles} + + + while( n.sig <> LSC_Nulo ) do begin + + + + LSC_Almac_Reservar( b.almac, tmpp ); + + m.sig := tmpp; + + LSC_Almac_Modificar( b.almac, mp, m ); + + + np := n.sig; + + LSC_Almac_Acceder( a.almac, np, n ); + + + + mp := tmpp; + + m.elem := n.elem; + + m.ant:= n.ant + + + end; + + m.sig := LSC_Nulo; + + LSC_Almac_Modificar( b.almac, mp, m ); + +END; + + + +end. + diff --git a/tp_ejemplo/leeme.txt b/tp_ejemplo/leeme.txt new file mode 100644 index 0000000..58c607a --- /dev/null +++ b/tp_ejemplo/leeme.txt @@ -0,0 +1,22 @@ +El Programa primcipal es TP1.PAS + +Para generar un archivo de entrada se usa el Programa comandos. +Los comandos introducidos deben estar en MAYUSCULAS. +Se incluye en este disco un archivo de entrada llamado prueba, +y el archivo outfile.txt, que fue generado por este. Los registros que +se insertan al usar prueba tienen como clave letras en vez de numeros de +dni, porque el campo es de caracteres y esto sirve para ver el resultado +de la order OR (ordenar). + +Uso del programa: + + TP1.exe + + Ejemplo: TP1 in.bin outfile.txt + +Uso de comandos: + + comandos + donde es el nombre del archivo de entrada para TP1.exe + que será creado. + diff --git a/tp_ejemplo/outfile.txt b/tp_ejemplo/outfile.txt new file mode 100644 index 0000000..030b9db --- /dev/null +++ b/tp_ejemplo/outfile.txt @@ -0,0 +1,100 @@ +Archivo de Entrada:prueba +Archivo de Salida :outfile.txt + + +>IN V MARIANO P * + +>IN L PEPE S * + +>IN K JUAN P * + +>IN B HERNAN U * + +>IN A PEDRO U * + +>LS * * * * + K - JUAN + V - MARIANO + L - PEPE + B - HERNAN + A - PEDRO + +>LC * * * * + A - PEDRO + +>IN F FEDERICO S * + +>LS * * * * + K - JUAN + V - MARIANO + L - PEPE + B - HERNAN + A - PEDRO + F - FEDERICO + +>LC * * * * + F - FEDERICO + +>OR * * * * + +>LC * * * * + F - FEDERICO + +>LS * * * * + A - PEDRO + B - HERNAN + F - FEDERICO + K - JUAN + L - PEPE + V - MARIANO + +>IO G GASTON * * + +>LC * * * * + G - GASTON + +>LS * * * * + A - PEDRO + B - HERNAN + F - FEDERICO + G - GASTON + K - JUAN + L - PEPE + V - MARIANO + +>MO T TOMAS * * + +>LC * * * * + T - TOMAS + +>LS * * * * + A - PEDRO + B - HERNAN + F - FEDERICO + G - GASTON + K - JUAN + L - PEPE + T - TOMAS + +>OR * * * * + +>LC * * * * + T - TOMAS + +>BO * * * * + +>LS * * * * + A - PEDRO + B - HERNAN + F - FEDERICO + G - GASTON + K - JUAN + L - PEPE + +>LC * * * * + L - PEPE + +>LI * * * * + +>LS * * * * +TABLA VACIA diff --git a/tp_ejemplo/pila_c.pas b/tp_ejemplo/pila_c.pas new file mode 100644 index 0000000..1a9dbd9 --- /dev/null +++ b/tp_ejemplo/pila_c.pas @@ -0,0 +1,450 @@ +unit pila_C; + + + +{ + + IMPLEMENTACION : pilas + + ALMACENAMIENTO : CURSORES + + MODIFICADO PARA QUE COMPILE, y un par de errores que tenia (estan marcados) + +} + + + +{ ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular } + +interface + + + +{ usa las funciones generales de TDAs } + +uses tda_gral; + + + +{ maximo tamano del cursor } + +const PILAC_MAX_CURSOR = 100; + + + +{ tipos propios de la lista para definir el cursor } + +TYPE + + PILAC_puntero = integer; + + + +const + + PILAC_nulo : PILAC_puntero = 0; + + + +type + + + + PILAC_nodo = RECORD + + Elem : Tipo_Elem; + + Sig : PILAC_puntero; + + END; + + + + + + { ahora le toca definir el cursor } + + PILAC_Almac = record + + almacenamiento : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Nodo; + + siguientes : array [ 1 .. PILAC_MAX_CURSOR ] of PILAC_Puntero; + + primero_dispo : PILAC_puntero; + + end; + + + + + + PILAC_Pila = RECORD + + almac : PILAC_Almac; + + primero: PILAC_puntero; + + END; + + + + + +{ ========= } + +{ INTERFASE } + + + + + +PROCEDURE PILAC_Inicializar ( VAR l: PILAC_Pila ); + +FUNCTION PILAC_vacio( l: PILAC_Pila): BOOLEAN; + +FUNCTION PILAC_lleno( l: PILAC_Pila): BOOLEAN; + + + +PROCEDURE PILAC_poner ( VAR l: PILAC_Pila; VAR e: Tipo_Elem ); + +PROCEDURE PILAC_sacar ( VAR l: PILAC_Pila; VAR e: Tipo_Elem); + +PROCEDURE PILAC_vaciar ( VAR l: PILAC_Pila ); + +PROCEDURE PILAC_copiar ( a: PILAC_Pila; VAR b: PILAC_Pila ); + + + +implementation + + + +{ CURSORES DE ESTA IMPLEMENTACION } + +{ ========================================================================== } + +{ inicializar el almacenamiento } + +{ PRE : 'almac' no esta inicializado } + +{ POST: 'almac' esta inicializado y vacio } + +procedure PILAC_Almac_Inicializar( VAR almac : PILAC_Almac ); + +var i : PILAC_Puntero; + +begin + + almac.primero_dispo := 1; + + for i := 1 to PILAC_MAX_CURSOR - 1 do + + begin + + almac.siguientes[i] := i + 1; + + end; + + almac.siguientes[PILAC_MAX_CURSOR] := PILAC_Nulo; + +end; + + + +{ ========================================================================== } + +{ saber si hay lugar para reservar un nuevo elemento en el almacenamiento } + +{ PRE : 'almac' esta inicializado } + +{ POST: si hay lugar en 'almac' para un nuevo elemento, + + entonces retorna TRUE y sino FALSE } +{ANDABA AL REVES, CORREGIDO} + + +function PILAC_Almac_HayLugar( almac : PILAC_Almac ): boolean; + +begin + + PILAC_Almac_HayLugar := NOT (almac.primero_dispo = PILAC_Nulo); + +end; + + + +{ ========================================================================== } + +{ el pedido de un nuevo elemento al almacenamiento } + +{ PRE : 'almac' esta inicializado } + +{ POST: si hay lugar en 'almac' para un nuevo elemento, + + entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento + + sino 'puntero' tiene el valor TTDA_Nulo } + +procedure PILAC_Almac_Reservar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero ); + +begin + + if not PILAC_Almac_HayLugar( almac ) + + then + + puntero := PILAC_Nulo + + else begin + + puntero := almac.primero_dispo; + + almac.primero_dispo := almac.siguientes[ puntero ]; + + end; + +end; + + + +{ ========================================================================== } + +{ liberar un elemento del almacenamiento } + +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } + +{ POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo } + +procedure PILAC_Almac_Liberar( VAR almac : PILAC_Almac; VAR puntero : PILAC_Puntero ); + +begin + + almac.siguientes[ puntero ] := almac.primero_dispo; + + almac.primero_dispo := puntero; + + puntero := PILAC_Nulo; + +end; + + + +{ ========================================================================== } + +{ acceder al elemento del almacenamiento apuntado por un puntero } + +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } + +{ POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' } + +procedure PILAC_Almac_Acceder( almac : PilaC_Almac; puntero : PILAC_Puntero; VAR elemento : PILAC_Nodo ); + +begin + + elemento := almac.almacenamiento[ puntero ]; + +end; + + + +{ ========================================================================== } + +{ modificar el elemento del almacenamiento apuntado por un puntero } + +{ PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento } + +{ POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' } + +procedure PILAC_Almac_Modificar( VAR almac : PILAC_Almac; puntero : PILAC_Puntero; elemento : PILAC_Nodo ); + +begin + + almac.almacenamiento[ puntero ] := elemento; + +end; + + + + + + + +{ Estas son los dos procedimientos principales de la aplicación } + + + +PROCEDURE PILAC_Inicializar ( VAR l: PILAC_Pila ); + +BEGIN + + PILAC_Almac_Inicializar( l.almac ); + + l.primero := PILAC_Nulo; + +END; + + + +FUNCTION PILAC_vacio( l: PILAC_Pila): BOOLEAN; + +BEGIN + + PILAC_vacio := ( l.Primero = PILAC_Nulo); + +END; + + + +FUNCTION PILAC_lleno( l: PILAC_Pila): BOOLEAN; + +BEGIN + + PILAC_lleno := not PILAC_Almac_HayLugar( l.almac ); + +END; + + + +PROCEDURE PILAC_poner ( VAR l: PILAC_Pila; var e: Tipo_Elem); + +VAR + + n : PILAC_Nodo; + + np: PILAC_Puntero; + +BEGIN + + n.Elem := e; + + n.sig := l.primero; + + PILAC_Almac_Reservar( l.almac, np ); + + PILAC_Almac_Modificar( l.almac, np, n ); + + l.primero := np; + +END; + + + +{ pre: no esta vacia } + +PROCEDURE PILAC_sacar ( VAR l: PILAC_Pila; VAR e: Tipo_Elem); + +VAR n : PILAC_Nodo; + + tmp : PILAC_Nodo; + + tmpp: PILAC_Puntero; + +BEGIN + + PILAC_Almac_Acceder( l.almac, l.primero, n ); + + PILAC_Almac_Liberar( l.almac, l.primero ); + + l.primero := n.Sig; + + + + { y se lo asigno al parametro } + + e := n.Elem; + +END; + + + +PROCEDURE PILAC_vaciar ( VAR l: PILAC_Pila ); + +VAR np : PILAC_Puntero; + + n : PILAC_Nodo; + +BEGIN + + np := l.primero; + + while( np <> PILAC_Nulo ) do begin + + PILAC_Almac_Acceder( l.almac, np, n ); + + PILAC_Almac_Liberar( l.almac, np ); + + np := n.sig; + + end; + + l.primero := PILAC_Nulo; + +END; + + + +{ pre: 'a' y 'b' estan creadas y 'b' esta vacia } + +{ POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero } + +PROCEDURE PILAC_copiar ( a : PILAC_Pila; VAR b : PILAC_Pila ); + +VAR np, mp, tmpp : PILAC_Puntero; + + n,m : PILAC_Nodo; + +BEGIN + + if a.primero = PILAC_Nulo then exit; + + np := a.primero; + + PILAC_Almac_Acceder( a.almac, np, n ); + + + + PILAC_Almac_Reservar( b.almac, mp ); + + b.primero := mp; + + m.elem := n.elem; + + + + while( n.sig <> PILAC_Nulo ) do begin + + + + PILAC_Almac_Reservar( b.almac, tmpp ); + + m.sig := tmpp; + + PILAC_Almac_Modificar( b.almac, mp, m ); + + + + np := n.sig; + + PILAC_Almac_Acceder( a.almac, np, n ); + + + + mp := tmpp; + + m.elem := n.elem; + + + + end; + + m.sig := PILAC_Nulo; + + PILAC_Almac_Modificar( b.almac, mp, m ); + +END; + + + +end. + diff --git a/tp_ejemplo/prueba b/tp_ejemplo/prueba new file mode 100644 index 0000000000000000000000000000000000000000..d791870ec98fd193013819fdbb9a60f49cd2e34b GIT binary patch literal 1664 zcmc)KZ4QDk3oUOmA4QDAtt7;*{*XUxAy4+U6bfVEv3p;qUU{P| zhVAwZ9F*Z{G5ap8_f9*_@&obr#os1nS)QI>1%JG1&+`*GUj=_~y79=VKk;3x1xl_j z-XOHg{IzNr z(K7nK)jx?(^9y{BFfQ{yVy}i@@=JW0U*O672t1h|fv+%`Ux6pzpTwvC4~aK_&Hn^K CuUAq4 literal 0 HcmV?d00001 diff --git a/tp_ejemplo/tabla.pas b/tp_ejemplo/tabla.pas new file mode 100644 index 0000000..ef19efa --- /dev/null +++ b/tp_ejemplo/tabla.pas @@ -0,0 +1,377 @@ +unit tabla; + + + +{ + + IMPLEMENTACION : TDA_TABLA + + +} +{ +POR AHORA COMPILA +} + +interface + +uses TDA_GRAL, ldoblec, pila_C; + +TYPE + + T_MOVIM = LSC_movimiento; + + T_CLAVE = Tipo_Clave; + + T_REGISTRO = Tipo_Elem; + + T_TABLA = record + + lista : LSC_Lista_Simple_C; {si bien el nombre dice simple, es una lista doble + no lo cambie aun para evitar mas errores} + ordenada: boolean; + + end; {record} + + + +Procedure T_TABLA_Crear ( var T: T_TABLA); + +Function T_TABLA_Vacia ( T: T_TABLA ) : boolean; + +Function T_TABLA_Llena ( T: T_TABLA ) : boolean; + +Function T_TABLA_Ordenada ( T: T_TABLA ) : boolean; + +Procedure T_TABLA_Elem_Cte ( T: T_TABLA ; var R: T_REGISTRO ); + +Procedure T_TABLA_Mover_Cte ( var T: T_TABLA ; M: T_MOVIM; var error: boolean ); + +Procedure T_TABLA_Insertar ( var T: T_TABLA ; var R: T_REGISTRO; M: T_MOVIM ); + +Procedure T_TABLA_Insertar_O ( var T: T_TABLA ; var R: T_REGISTRO); + +Procedure T_TABLA_Limpiar ( var T: T_TABLA ); + +Procedure T_TABLA_Borrar_Cte ( var T: T_TABLA ); + +Procedure T_TABLA_Modif_Cte ( var T: T_TABLA ; var R: T_REGISTRO ); + +Procedure T_TABLA_Ordenar ( var T: T_TABLA ); + +Procedure T_TABLA_Buscar_Clave ( var T: T_TABLA ; C: T_CLAVE; var error :boolean); + +PROCEDURE Buscar_por_Rango(var T: T_TABLA; D, H: T_CLAVE; var L: PILAC_Pila); + +{-------------------------------------} +IMPLEMENTATION + + +Procedure T_TABLA_Crear ( var T: T_TABLA); +{ + PRE :T nunca fue creada. + POST: T creada y vac¡a. +} + +BEGIN + + LSC_Inicializar ( t.lista ); + + {una lista vacia esta ordenada} + t.ordenada := true; + +END; +Function T_TABLA_Vacia ( T: T_TABLA ) : boolean; +{ + PRE :T creada. + POST: Si T tiene elementos, entonces es FALSE, sino es TRUE. +} +BEGIN + + T_TABLA_Vacia := LSC_vacio( t.lista ); + +END; + + +Function T_TABLA_Llena ( T: T_TABLA ) : boolean; +{ + PRE :T creada. + POST: Si T tiene lugar para insertar nuevos elementos, entonces es FALSE, sino es TRUE. +} +BEGIN + + T_TABLA_Llena := LSC_lleno( t.lista ); + +END; + +Function T_TABLA_Ordenada ( T: T_TABLA ) : boolean; +{ + PRE :T no vac¡a. + POST: Si T est  ordenada, entonces es verdadero, sino es falso. +} + +BEGIN + + T_TABLA_Ordenada:= t.ordenada; + +END; + +Procedure T_TABLA_Elem_Cte ( T: T_TABLA ; var R: T_REGISTRO ); +{ + PRE :T no vac¡a. + POST: R contiene el registro corriente. +} + +BEGIN + + LSC_elem_cte ( t.lista, r); + +END; + +Procedure T_TABLA_Mover_Cte ( var T: T_TABLA ; M: T_MOVIM; var error: boolean ); +{ + PRE :T no vac¡a. + POST: Si M = primero, el nuevo corriente es el primer registro y error es falso. + Si M = ultimo, el nuevo corriente es el £ltimo registro y error es falso. + Si M = siguiente, el nuevo corriente es el siguiente registro del actual + corriente y error es falso. Si el corriente era el £ltimo registro, entonces + error es verdadero y el corriente sigue siendo el £ltimo registro. + Si M = anterior, el nuevo corriente es el anterior registro del actual + corriente y error es falso. Si el corriente era el primer registro, entonces + error es verdadero y el corriente sigue siendo el primer registro. + + (Los valores para M son de tipo t_movim) +} + +BEGIN + +LSC_mover_cte ( t.lista, m, error ); + +END; + +Procedure T_TABLA_Insertar ( var T: T_TABLA ; var R: T_REGISTRO; M: T_MOVIM ); +{ + PRE : T no est  llena. + POST: Si M = primero, R se agreg¢, es el primer registro y el nuevo corriente. + Si M = ultimo, R se agreg¢, es el £ltimo registro y el nuevo corriente. + Si M = siguiente, R se agreg¢, es el siguiente registro del corriente, y es el nuevo corriente + Si M = anterior, R se agreg¢, es el anterior registro del corriente, y es el nuevo corriente. + + Para no complicar mas la implementacion de la lista doble, + el insertar al final esta implementado aca +} + +VAR error: boolean; + +BEGIN + + IF m = LSC_ULTIMO then begin + + LSC_mover_cte ( t.lista, m, error ); + + {insertar al final no es mas que insertar despues de el ultimo:} + m:= LSC_siguiente + + end; + + LSC_insertar ( t.lista, m, r); + + t.ordenada:= false + +END; + +Procedure T_TABLA_Insertar_O ( var T: T_TABLA ; var R: T_REGISTRO); + +VAR error: boolean; + e: t_registro; + +BEGIN + + IF t.ordenada = true then begin + + T_TABLA_Buscar_Clave(t, r.dni, error); {no importa si lo encuentra o no} + + T_TABLA_Elem_Cte( t, e); + + IF e.dni > r.dni then + T_TABLA_INSERTAR(t, r, lsc_anterior) + ELSE + T_TABLA_INSERTAR(t, r, lsc_siguiente); +{*1*} + + t.ordenada:= true {insertar lo deja en false} + END; + +END; + +Procedure T_TABLA_Limpiar ( var T: T_TABLA ); +{ PRE : T creada. + POST: T vac¡a. +} + + +BEGIN + + LSC_vaciar (t.lista); + t.ordenada:= true; + +END; + +Procedure T_TABLA_Borrar_Cte ( var T: T_TABLA ); +{ + PRE : T no vac¡a. + POST: Se elimin¢ el registro corriente. + El nuevo registro corriente es el siguiente del borrado, si el borrado + era el £ltimo, entonces el nuevo corriente es el primero. +} + +BEGIN + + LSC_borrar_cte ( t.lista ); + +END; + +Procedure T_TABLA_Modif_Cte ( var T: T_TABLA ; var R: T_REGISTRO ); +{ + PRE : T no vac¡a. + POST: El contenido del actual corriente fue actualizado con R. + Si T estaba ordenada y no se modificaron los datos de la clave del + corriente, entonces T sigue ordenada. Si T estaba ordenada y se + modificaron los datos de la clave del corriente, entonces si la + nueva clave rompe el orden de T, T no est  m s ordenada. +} +VAR e: T_REGISTRO; + +BEGIN + + T_TABLA_Elem_Cte (t, e); + + if Devolver_Clave_Elem( e ) <> Devolver_Clave_Elem( r ) then + t.ordenada:= false; + + LSC_modif_cte (t.lista, r); + +END; + +Procedure T_TABLA_Ordenar ( var T: T_TABLA ); +{ + PRE : T no vac¡a. + POST: T se encuentra ordenada por la clave de sus registros. +} +VAR t_aux: T_TABLA; + + e: T_REGISTRO; + + error: boolean; + +BEGIN + + error:= false; + + T_TABLA_Crear( t_aux); + + LSC_COPIAR(t.lista, t_aux.lista); + + T_TABLA_Limpiar(t); + +(* {tengo que mover en corriente al primero porque esta en nulo (0)} + T_TABLA_Mover_Cte ( t, lsc_primero, error ); +Era un bolazo +*) + + T_TABLA_Elem_cte(t_aux, e); + + T_TABLA_Insertar (t, e, lsc_primero); + + T_TABLA_Mover_Cte ( t_aux, lsc_siguiente, error ); + + t.ordenada:= true; {si tiene un solo elemento no veo porque no} + + while error <> true do begin + + T_TABLA_Elem_cte(t_aux, e); + + T_TABLA_Insertar_O (t, e); + + T_TABLA_Mover_Cte ( t_aux, lsc_siguiente, error ); + + end; + + t.ordenada:= true; + +END; + +Procedure T_TABLA_Buscar_Clave ( var T: T_TABLA ; C: T_CLAVE; var error :boolean); +{ + PRE : T no vac¡a. + POST: Si C es una clave que existe en T, entonces el nuevo corriente es el + registro con clave C y error es falso, sino error es verdadero y + el corriente es el registro donde termino la busqueda (modificacion + hecha para facilitar la operacion insertar ordenado). +} +VAR e: T_REGISTRO; + +BEGIN + + error:= false; + +{ IF not T_TABLA_Vacia(t) then begin +} + T_TABLA_Mover_Cte ( t, lsc_primero, error ); + + T_TABLA_Elem_cte(t, e); + + While (e.DNI < c ) AND not error do begin + + T_TABLA_Mover_Cte ( t, lsc_siguiente, error ); + + T_TABLA_Elem_cte(t, e); + + END; + + IF e.dni <> c then error := true; + +{ END + ELSE error:= true; +} +END; + +PROCEDURE Buscar_por_Rango(var T: T_TABLA; D, H: T_CLAVE; var L: PILAC_Pila); +{ + BUSCA LOS REGISTROS COMPRENDIDOS ENTRE LAS CLAVES D y H + Y LOS ALMACENA EN LA PILA L. +} +VAR + error: boolean; + e: T_REGISTRO; + +BEGIN + error:= false; + + T_TABLA_Buscar_Clave(t,d,error); + +{ if error = false then begin} + + T_TABLA_Elem_cte(t, e); + + PILAC_poner ( l,e ); + + T_TABLA_Mover_Cte ( t, lsc_siguiente, error ); + + T_TABLA_Elem_cte(t, e); + + + While (e.DNI <= h ) AND (error = false) do begin + + PILAC_poner ( l,e ); + + T_TABLA_Mover_Cte ( t, lsc_siguiente, error ); + + T_TABLA_Elem_cte(t, e); + + END; {WHILE} + +{ END; {IF} + +END; + +END. \ No newline at end of file diff --git a/tp_ejemplo/tda_gral.pas b/tp_ejemplo/tda_gral.pas new file mode 100644 index 0000000..06f4886 --- /dev/null +++ b/tp_ejemplo/tda_gral.pas @@ -0,0 +1,115 @@ +unit tda_gral; + +{ funciones y datos y tipo generales de los TDA de almacenamiento + Basado en el codigo de la catedra, modificado para que compile. + Los tipos de datos de los elementos de Persona fueron reemplazados + por los que se usan en el TP. +} + + + +interface + + + +{ aca se define el famoso tipo_elem } + +type + + TipoDNI = string[8]; + + Persona = record + + DNI : TipoDNI; + + Nombre : string[40]; + +{Apellido no es necesario para el TP} +{ Apellido : ShortString; } + + end; + + + + Tipo_Clave = TipoDNI; + + Tipo_Elem = Persona; + + + +{ esta funcion devuelve la clave de un elemento almacenado } + +{ PRE : ninguna } + +{ POST: devuelve la clave de un elemento E } + +function Devolver_Clave_Elem( E: Tipo_Elem): Tipo_Clave; + + + +{ este procedimiento se usa en recorridos e imprime los datos del elemento } + +{ PRE : ninguna } + +{ POST: se imprimieron los datos } + +procedure Procesar_Elem_Recorrido ( var e: Tipo_Elem); + + + +{ compara dos elementos completos para ver si cumplen con el criterio o no } + +FUNCTION Comparar_Elementos( a: Tipo_Elem; b: Tipo_Elem ): boolean; + + + +implementation + + + +{ esta funcion devuelve la clave de un elemento almacenado } + +function Devolver_Clave_Elem( E: Tipo_Elem): Tipo_Clave; + +begin + + Devolver_Clave_Elem := E.DNI; + +end; + + + +{ este procedimiento se usa en recorridos e imprime los datos del elemento } + +procedure Procesar_Elem_Recorrido ( var e: Tipo_Elem); + +BEGIN + + + +END; + + + +{ compara dos elementos completos para ver si cumplen con el criterio o no } + +FUNCTION Comparar_elementos( a: Tipo_Elem; b: Tipo_Elem ): boolean; + +BEGIN + + IF a.DNI = b.DNI + + THEN + + Comparar_Elementos := true + + ELSE + + Comparar_Elementos := false; + +END; + + + +end. + diff --git a/tp_ejemplo/tp1.pas b/tp_ejemplo/tp1.pas new file mode 100644 index 0000000..eaa9697 --- /dev/null +++ b/tp_ejemplo/tp1.pas @@ -0,0 +1,195 @@ +program tp1; +{ + TRABAJO PRACTICO NUMERO 1 + 1er Cuatrimestre 2000 + +} + +uses TDA_GRAL, ldoblec, tabla, pila_C, crt; + +Type + T_registro_entrada = record + Comando: string[2]; + DNI: string[8]; + Nombre: string[40]; + Movimiento: string[1]; + DNI_hasta: string[8]; + End; + comando = ( OTRO, INS, IO, ORD, BC, BR, LS, LC, BO, MO, LI); + + +Var mitabla: T_TABLA; + pila: PILAC_Pila; + infile: file of T_registro_entrada; + cmd: comando; + mov: t_movim; + o: text; + r: T_registro_entrada; + e: t_registro; + error: boolean; + aux: string; + + +{------- Aca empieza el programa -------} + +begin + + WriteLn; + Writeln('Archivo de Entrada:', ParamStr(1)); + Writeln('Archivo de Salida :', ParamStr(2)); + + Assign(infile, ParamStr(1)); + Reset (infile); + + Assign(o, ParamStr(2)); + rewrite (o); + + Writeln(o,'Archivo de Entrada:', ParamStr(1)); + Writeln(o,'Archivo de Salida :', ParamStr(2)); + Writeln(o); + + T_TABLA_Crear(mitabla); + PILAC_Inicializar (pila); + + while not eof(infile) do begin + + read(infile, r); + +{ r.comando:= UpCase (r.comando);} + + writeln(o); + write(o,'>',r.comando); + write(o,' ',r.dni); + write(o,' ',r.nombre); + write(o,' ',r.movimiento); + write(o,' ',r.dni_hasta); + writeln(o); + + e.dni:= r.dni; + e.nombre:= r.nombre; + +{Estos bloques son para interpretar los strings y ponerlos en un enumerado} + + IF r.comando = 'IN' then cmd:= INS + ELSE IF r.comando = 'IO' then cmd:= IO + ELSE IF r.comando = 'OR' then cmd:= ORD + ELSE IF r.comando = 'BC' then cmd:= BC + ELSE IF r.comando = 'BR' then cmd:= BR + ELSE IF r.comando = 'LS' then cmd:= LS + ELSE IF r.comando = 'LC' then cmd:= LC + ELSE IF r.comando = 'BO' then cmd:= BO + ELSE IF r.comando = 'MO' then cmd:= MO + ELSE IF r.comando = 'LI' then cmd:= LI; + + IF r.movimiento= 'P' then mov:=lsc_primero + ELSE IF r.movimiento= 'A' then mov:=lsc_anterior + ELSE IF r.movimiento= 'S' then mov:=lsc_siguiente + ELSE IF r.movimiento= 'U' then mov:=lsc_ultimo; + + CASE cmd of + + INS: begin + + T_TABLA_Insertar(mitabla, e, mov) + + end; + + IO: begin + + T_TABLA_Insertar_O(mitabla, e) + + end; + + ORD: begin + + T_TABLA_Ordenar(mitabla) + + end; + + BC: begin + + T_TABLA_Buscar_Clave (mitabla, r.dni, error ); + + IF Error then + writeln(o,'Error buscando la clave: ',r.dni) + Else + begin + + T_TABLA_Elem_Cte (mitabla, e); + + writeln('Encontrado: ', e.nombre); + + end; + + end; + + BR: begin + + Buscar_por_Rango(mitabla, r.dni, r.dni_hasta, pila); + + Writeln(o,'RESULTADOS DE LA BUSQUEDA:'); + + Writeln(o,'--------------------------'); + + while not PILAC_vacio(pila) do begin + + PILAC_sacar(pila, e); + + writeln(o,' ',e.dni,' - ', e.nombre); + + end; + + Writeln(o,'----- FIN BUSQUEDA ------'); + + end; + + LS: begin + + If NOT T_TABLA_Vacia (mitabla) then begin + + T_TABLA_Mover_Cte (mitabla, lsc_primero, error); + + error:= false; + + while NOT error do begin + + T_TABLA_Elem_Cte (mitabla, e); + + writeln(o,' ',e.dni,' - ', e.nombre); + + T_TABLA_Mover_Cte (mitabla, lsc_siguiente, error); + + end; + end + + Else + + Writeln(o, 'TABLA VACIA'); + + end; + + LC: begin + + T_TABLA_Elem_Cte (mitabla, e); + + writeln(o,' ',e.dni,' - ', e.nombre); + + end; + + BO: T_TABLA_Borrar_Cte ( mitabla ); + + MO: T_TABLA_Modif_Cte (mitabla, e); + + LI: T_TABLA_Limpiar (mitabla); + + ELSE + writeln(o,' ERROR. Comando desconocido :', r.comando ); + + end; {case} + + end; {while} + + close(o); + +end. + -- 2.43.0