ESTRUCTURAS DINÁMICAS DE DATOS.
Son aquellas en las que el
espacio que ocupan en memoria se determinan en tiempo de ejecución a diferencia
de las estáticas, en las que el espacio que ocupaban se establecían en tiempo
de compilación. Una variable dinámica se crea en tiempo de ejecución, y
necesita para su creación del uso de punteros.
Las variables de tipo puntero
se representan
y almacenan la dirección de memoria donde se encuentra la variable dinámica
apuntada.
Declaración :
Type
puntero=ìnteger ; {se reserva en memoria espacio para enteros}
Var
p, q : puntero ;
a.
Asignación :
p :=NIL ; {valor
nulo, para inicialización}
p :=q ; {p apuntará a donde apunte q }
b.
Crear la variable dinámica :
New(p) ; {Reserva
espacio para la variable dinámica. Con New(p) se crea la variable dinámica
apuntada. }
{ Ésta no tiene nombre
porque no está declarada, por lo que nos referiremos a ella como :
{
p^ {p apuntada}
}
{almacena
en p una dirección de memoria donde se pueden guardar datos de tipo entero }
Dispose(p) ; {Libera ese
espacio de memoria ocupado por la variable dinámica apuntada }
c.
Comparación :
Sólo acepta < > y =
(nunca > o < ).Ej : If p < > q then
Los punteros no pueden ser
leidos de teclado ni verlos en pantalla.
Las variables dinámicas
admiten cualquiera de las operaciones que admitiría una variable de ese tipo.
Si se puede :
ReadLn(p^) ; { porque p^ es un entero }
WriteLn(p^) ;
Nunca :
ReadLn(p) ; { porque p es un puntero }
Las variables dinámicas
(apuntadas) pueden ser de cualquier tipo :
Type
puntero=^integer ;
^real ;
^char ;
^string ;
^array ;
^Registro ; {Registro se debe declarar ántes que el puntero :
Registro=RECORD
c1 :char ;
c2 :integer ;
end ;
}
Si es puntero a variable de
tipo registro :
Var p :puntero
Begin
New(p) ;
{ p
char
integer creada en}
{en tiempo de ejecución}
ReadLn(p^.c1) ;
ReadLn(p^.c2) ;
Otro caso : {estructura
de datos enlazada}
Registro=RECORD
c1 :char ;
c2 :puntero ;{que no está declarado, se declarará después}
end ;
puntero=^Registro ;
Var p :puntero ;
Begin
New(p) ;
New(p^.c2) ;
ReadLn(p^.c1) ;{ no se puede leer p^.c2
porque es puntero}
ReadLn(p^.c2^.c1) ;
Como no es práctico se maneja de otra manera :
Type
puntero=^nodo ;{àRegistro especial y uno de sus campos es
puntero}
nodo=RECORD
c1 :char ;
p :puntero ;
end ;
Variable p :puntero ;
Las estructuras dinámicas de
datos pueden ser :
a.
Lineales (Listas, Pilas y Colas) {Las pilas y
colas son tipos especiales de listas}
En una estructura dinámica lineal, cada elemento tiene un único
elemento sucesor o siguiente y
cada elemento y un único elemento predecesor o anterior.
b.
No Lineales (Árboles y Grafos)
Las estructuras no lineales se caracterizan porque sus elementos pueden
tener más de un
elemento sucesor o siguiente (Árboles : un
sólo predecesor y varios posibles sucesores). Los Grafos pueden tener más de
un elemento predecesor (varios predecesores y varios sucesores).
Hay muchas variantes porque
cada nodo puede tener más punteros.
Una Lista es una colección o
serie de datos del mismo tipo que se almacenan en la memoria del ordenador. En
una lista cada elemento podrá tener un único sucesor o siguiente y un único
antecesor. Además la inserción y elimminación de elementos se podrá efectuar
en cualquier lugar de la lista. Como casos especiales de listas son las pilas y
las colas, en las que la inserción o eliminación de elementos está
restringida a efectuarse por un determinado lugar.
Las Listas pueden ser de
varios tipos :
a.
Listas Contiguas :
en
ellas, los elementos que las constituyen ocupan posiciones consecutivas en
memoria. Se suelen implementar por medio de arrays.
b.
Listas Enlazadas :
Son las ‘verdaderas listas’. Tienen la ventaja de que la inserción y
eliminación de un elemento en cualquier lugar nunca obliga al desplazamiento de
los restantes elementos de la lista. En las listas enlazadas, los elementos no
ocupan posiciones consecutivas de memoria, por lo que cada uno de ellos se ve
obligado a almacenar la posición o dirección de memoria donde se encuentra el
siguiente elemento de la lista. Para recorrer una lista enlazada hay que hacerlo
siempre desde el principio de la lista (para seguir los punteros). Estas listas
se representan con punteros en general, lo que consigue que la compilación en
memoria pueda variar en la ejecución del programa.
Las listas, sin punteros, se simulan mediante arrays, lo que provoca el
inconveniente de que el espacio reservado en memoria es constante (deja de ser
una estructura dinámica para convertirse en estática).
ediante arrays sería :
(por ejemplo la inserción del elemento B)
(memoria)
1 A
4
2 D
3
3
F
0
A
4
D
3
F
0
4
B
2
5
1
6
inicio
B
2
...
(con
punteros enteros)
Se inserta en su sitio (el
hueco) sin despazar elementos.
Para borrar hacemos que inicio apunte al siguiente.
Para simular New y Dispose :
En principio toda la memoria del ordenador es una lista con posiciones
vacías. Con New(p) lo quitamos de la lista de vacío.
Type
puntero=^nodo ;
nodo=RECORD
elem :TipoElemento ;
SIG :puntero ;
end ;
Var
inicio,
anterior, posición :puntero ;
elemento :Tipoelemento ;
encontrado :boolean ;
Procedure
Inicializar(variable inicio :puntero) ;
begin
inicio :=NIL ;
end ;
Function Vacía(inicio :puntero ;encontrado :boolean) ;
begin
vacía :=inicio=NIL ;
end ;
Procedure Insertar(elemento :Tipoelemento ;anterior :puntero ;variable
inicio :boolean) ;
{distinguir entre :insertar1º lista o cualquier otro}
Var
auxi :puntero ;
begin
New(auxi) ;
auxi^.elem :=elemento ;
If
anterior=NIL then
begin
auxi^.sig :=inicio ;
inicio :=auxi
end
else
begin
auxi^.sig :=anterior^.sig ;
anterior^.sig :=auxi
end
end ;
En un array :
Reservar(auxi) en lugar
de New(auxi).
a[auxi].sig en
lugar de auxi^.sig.
Elementos ordenados en una
lista :
Ana Jose Pedro
Bea
Procedure Consultar (variable
anterior, posicion,inicio :puntero ; elemento :
Tipoelemento ;variableencontrado :boolean) ;
Var
Salir :boolean ;
Begin
anterior :=NIL ;
salir :=false ;
posicion :=inicio ;
While (posicion<>NIL) AND (NOT salir) do
If
posicion^.elemento<elemento then
Begin
anterior :=posición ;
posicion :=posicion^.sig ;
end
Else
salir :=true ;
If (posicion<>NIL) AND (posicion^.elemento=elemento) then
encontrado :=true
Else
encontrado :=false ;
End ;
posicion
1º
Ant
Inicio
n
Suprimir :
·
1º de la lista.
·
Cualquier otro.
If ant = NIL then
inicio :=posic^.Sig ;
{
liberar posición }
If ant <> NIL then {
consulta da anterior y posicion del que vaya a eliminar }
ant^.sig := posic^.sig
{ liberar posicion }
Si es el último da igual (no hay que considerarlos).
{-------------------------------------------------------------------------------}
Procedure Suprimir (ant,
posicion: puntero ;var inicio : puntero) ;
Begin
If ant
= NIL then
inicio :=posicion^.Sig
else {
consulta da anterior y posicion del que vaya a eliminar }
ant^.sig := posicion^.Sig ;
Dispose
(posicion) ; { libera posicion}
end ;
n
Recorrer una Lista :
Procedure Recorrer(inicio :puntero) ;
Var
posicion :puntero ;
Begin
posicion :=inicio ;
While posicion<>NIL do
Begin
WriteLn(posicion^.elemento) ;
posicion :=posicion^.Sig ;
end ;
End ;
{------------------------------------------------------------------}
n
Simulación de una Lista
Enlazada con Arrays :
elemento
sig(dirección del siguiente elemento de la lista)
1
Pepe
9
Inicio1
2
Carolina
7
5
3
4
a[1].elemento
5
Ana
2
a[1].Sig
Inicio2
6
(libres)
7
Federico
1
8
9
Susana
0
Inicialmente no es así,
porque de las 2 listas inicio hay un alista de vacío :
elemento
sig(dirección del siguiente elemento de la lista)
1
Pepe
9
Inicio1
2
xxxxxxxxx 1
5
3
4
a[1].elemento
5
Ana
2
a[1].Sig
Inicio2
6
(libres)
7
8
9
Susana
0
2
Para insertar :
·
con punteros : New(auxi) ;
·
con arrays : Reservar
(auxi) ;
El procedimiento Insertar de
una estructura dinámica simulada por un array es igual que el de la estructura
dinámica sin simular.
Procedure Insertar (var a :arr ;
elemento :Tipoelemento ;ant :integer ; var inicio, vacio :integer) ;
Var
auxi :integer ;
Begin
Reservar(auxi^) ;
{ equivale a New(auxi) en punteros}
a[auxi].elemento :=elemento ;
If ant=0 then
begin
a[auxi].sig :=inicio ; {a[auxi].sig
equivale a auxi^.sig en punteros}
inicio :=auxi ;
End
Else
begin
a[auxi].sig :=a[ant].sig ;
a[ant].sig :=auxi ;
end ;
End ;
n
Gestión de libres :
Al introducir el primer libre :
(Reservar (auxi))
auxi
ß vacío {1}
vacío
ß a[vacío].sig {2}
Para insertar otro :
(Reservar
(auxi))
auxiß vacío {2}
vacíoß a[vacío].sig {3}...
Procedure Reservar (variable
auxi :integer ;a :arr ;variable vacío :integer) ;
Begin
auxi :=vacío ;
vacío :=a[vacío].sig ;
End ;
n
Borrado de un elemento :
Primer caso (ant = 0) :
inicioß a[posicion].sig
Liberar
posición.
Otros casos (ant<>0) :
a[anterior].sig :=a[posicion].sig
Liberar
posición.
{---------------------------------------------------------------------------------------}
Procedure Suprimir(var ant,
inicio :integer {puntero} ;elemento :Tipoelemento ; var a :arr ;
Begin
variable vacio :integer ;variable posicion :integer) ;
If ant=0 then {ant =NIL}
inicio :=a[posicion].sig
Else
a[ant].sig :=a[posicion].sig ; {ant^.sig :=posicion^.sig}
Liberar
(posicion,a,vacio) ; {Dispose
(posicion) }
(ant :=0 ;posicion :=inicio) ;
{para poder hacer estas llamadas sin consultar}
End ;
{--------------------------------------------------------------------------------------}
Procedure Liberar (posicion :integer ;var
a :arr ;var vacio :integer) ;
Begin
a[posicion].sig :=vacio ;
vacio :=posicion ;
End ;
Procedure InicializarListas (variable inicio :integer {puntero}) ;
Begin
inicio :=0 ;
{inicio :=NIL en punteros}
End ;
{-------------------------------------------------------------------------------------}
Procedure Iniciar (variable
vacio :integer ;variable a :arr) ;
Var
i :integer ;
Begin
vacio :=1 ;
For i :=1
to max-1 do
a[i].sig :=i+1 ;
a[max].sig :=0 ;
End ;
{----------------------------------------------------------------------------------}
n
Insertar de forma ordenada :
Para borrar necesitamos
conocer el anterior y la posicion : ant y a[ant].sig
Procedure Consultar (var
encontrado :boolean ; variable ant, posic :integer ;elem :Tipoelemento ;a :arr ) ;
Var
salir :boolean ;
Begin
ant :=0 ;
salir :=false ;
posic :=inicio ;
While
(posic<>0) AND (NOT salir) do
begin
ant :=posic ;
posic :=a[posic].sig ;
end
Else
Salir :=true ;
If
(posic<>0) AND (a[posic].elem=elem) then
encontrado :=true
else
encontrado :=false ;
End ;
Son un caso especial de
listas, en las que la inserción y borrado de nuevos elementos ha de hacerse por
un mismo lugar (cima de la pila). Se dice que son estructuras LIFO (Last In,
First Out). Para manipularlas hay que crear los procedimientos : MeterDatos
e InicializarPila.
Type
puntero=^nodo ;
nodo=RECORD
elemento : Tipoelemento ;
sig :puntero ;
end ;
Var
cima :puntero ;
{apunta a la cima de la pila}
elemento :Tipoelemento ;
Procedure InicializarPila(var
cima :puntero) ;
Begin
cima :=NIL ;
{no NIL porque no hay que crearla aquí}
End ;
{---------------------------------------------------------------------------------}
Function Vacia (cima :puntero) :boolean ;
Begin
vacia :=cima=NIL ;
end ;
{---------------------------------------------------------------------------------}
Procedure MeterDatos(var cima :puntero ;
elemento :Tipoelemento) ;
Var
auxi :puntero ;
Begin
New(auxi) ;
auxi^.elemento :=elemento ;
auxi^.sig :=cima ;
cima :=auxi ;
end ;
{--------------------------------------------------------------------------------}
Procedure Sacar (variable
cima :puntero ;variable elemento :Tipoelemento) ;
Variable
auxi :puntero ;
Begin
auxi :=cima ;
elemento :=cima^.elemento ;
{ para mostrar si quiero}
cima :=cima^.sig ;
Dispose(auxi) ;
end ;
n
Simulación de Pilas con
Arrays :
Type
arr=array[1..Max]
of Tipoelemento ; {Ya está la pila en array}
Variable
cima :integer ;
a :arr ;
{--------------------------------------------------------------------------------}
Procedure Inicializar
(variable cima :integer) ;
Begin
cima :=0 ;
end ;
{------------------------------------------------------------------------------}
Function
Vacia (cima :integer) :boolean ;
Begin
vacia :=cima=0;
end ;
{-------------------------------------------------------------------------------}
Procedure Poner (var cima :integer ;elemento :Tipoelemento ;
var a :arr) ;
Variable
auxi :integer ;
Begin
auxi :=cima+1;
a[auxi].elem :=elemento ;
cima :=cima+1 ;
end ;
Procedure Sacar (variable
cima :integer ;variable elemento :Tipoelemento ;a :arr) ;
Begin
elemento :=a[cima].elemento ;
cima :=cima-1 ;
end ;
{-----------------------------------------------------------------------------}
Function Llena (cima :integer) :boolean ;
Begin
Llena :=cima=maxend ;
{-----------------------------------------------------------------------------}