Tipos
Recursivos y Estructuras Enlazadas
Los tipos recursivos son tipos de datos
basados en apuntadores que permiten la creación de estructuras enlazadas como
las listas enlazadas dinámicas. Un ejemplo de estos tipos son los nodos, que
conforman las bases contenedoras de las listas, pilas y colas.
Apuntador:
un
apuntador es una dirección de memoria cuyo contenido es otra dirección de
memoria de una variable de un cierto tipo.
Sintaxis:
Tipo
<identificador
del apuntador> = apuntador a tipo_elemento
O bajo su declaración directa
Var
<identificador del apuntador> :
apuntador a tipo_elemento
Operaciones:
Referenciación (β):
permite obtener la referencia de una variable, es decir la dirección de memoria
donde esa variable se encuentra almacenada.
Ejempo:
X : entero
Ptr: apuntador a entero
Ptr = β(X) //Ptr apunta a la dirección
de memoria donde se encuentra X.
Desreferenciacion (i):
permite obtener la dirección de memoria apuntada por el apuntador
desreferenciado.
Ejemplo:
X : entero
Ptr : apuntador a entero
X = 20
Ptr = β(X)
si (
Ptr (i) = 20) entonces
escribir
(“Cierto”)
sino
escribir(“Falso”)
fsi
//La salida arrojada es “Cierto”
Los apuntadores permiten la construcción
de tipos recursivos en lenguajes que no lo proveen.
Estructuras
Enlazadas
Listas:
Las
listas representan colecciones de datos con ocupación en memoria dinámica. Se
construyen en base a tipos recursivos. Útiles para el almacenamiento eficiente
de datos. Tiene ventaja con respecto a la eficiencia en almacenamiento con
respecto al vector, puesto que el tamaño de la lista (espacio en memoria)
incrementa conforme se van añadiendo elementos a ella. Se encuentra en
desventaja con respecto al tiempo de acceso con respecto al vector, puesto que
requiere procesamiento para la localización, inserción, eliminación y
determinar longitud de la lista, que se vuelve mayor conforme el tamaño de la
lista crece. En contraste el vector provee acceso directo independientemente
del tamaño del mismo, lo cual minimiza el procesamiento. Determinar la longitud
de la lista puede optimizarse si la clase lista implementa un espacio reservado
en memoria para la longitud, que va incrementando o decrementando según el
tamaño de la lista cambia.
Las listas hacen uso de un tipo
recursivo conocido como “nodo”. Una lista es una composición de nodos, donde
cada nodo está compuesto por el elemento que almacena y un apuntador que apunta
al siguiente nodo de la lista. El último nodo de la lista apunta al apuntador
nulo.
Existen diversos tipos de listas
enlazas. Cada tipo varía por la estructura de su tipo nodo. Los tipos de lista
principales según sus nodos son:
Lista
simplemente enlazada con nodo cabecera: el
tipo nodo de esta lista está compuesto por un registro con dos campos: “info”
que representa el campo donde se almacena el elemento y “prox” que es un
apuntador a nodo (apunta al siguiente nodo). Este tipo de lista contiene un
nodo sin datos, que sirve como cabecera de la lista. El primer elemento de la
lista inicia en el nodo número dos.
Lista
simplemente enlazada sin nodo cabecera: el tipo nodo de esta
lista está compuesto por un registro con dos campos: “info” que representa el
campo donde se almacena el elemento y “prox” que es un apuntador a nodo (apunta
al siguiente nodo).
El primer elemento de la lista se
encuentra en el nodo numero uno.
Lista
doblemente enlazada con nodo cabecera: el tipo nodo de esta
lista está compuesto por un registro con tres campos: “info” que representa el
campo donde se almacena el elemento, “prox” que es un apuntador a nodo (apunta
al siguiente nodo), y “ant” que es un apuntador a nodo (apunta al nodo
anterior). Este tipo de lista contiene un nodo sin datos, que sirve como
cabecera de la lista. El primer elemento de la lista inicia en el nodo número
dos.
Lista
doblemente enlazada sin nodo cabecera: el tipo nodo de esta
lista está compuesto por un registro con tres campos: “info” que representa el
campo donde se almacena el elemento, “prox” que es un apuntador a nodo (apunta
al siguiente nodo), y “ant” que es un apuntador a nodo (apunta al nodo
anterior). El primer elemento de la lista se encuentra en el nodo numero uno.
Los tipos de lista principales según su
semántica son:
Lista
básica: implementada con nodos del tipo “simplemente
enlazados”. Permite almacenar datos con la semántica de un arreglo estatico.
Lista
doble: implementada con nodos del tipo “doblemente enlazados”.
Permite representar o emular carretes o cintas con principio y fin, permitiendo
detenerse en un punto de la lista, avanzar o retroceder.
Lista
circular (ronda) básica: con nodos simplemente
enlazados. Permite emular rondas o estructuras circulares. El último nodo de la
lista apunta al primer nodo de la lista. Se recorre de izquierda a derecha.
Lista
circular (ronda) doble: con nodos doblemente enlazados. Permite
emular rondas o estructuras circulares. El último nodo de la lista apunta al
penúltimo y al primero. El primer nodo apunta al siguiente y al último. Se
recorre de izquierda a derecha o de derecha a izquierda.
Se pueden construir nuevos tipos de
lista en base a los ya mencionados, así como también diferentes tipos de nodos
para emular listas de cualquier clase.
Definición
de la clase nodo para la lista básica:
Clase
Nodo
Privado:
info:
tipo_elemento
prox:
apuntador a Nodo
Público:
Nodo()
//constructor
Nodo(e:
tipo_elemento, p: apuntador a Nodo) //constructor
~Nodo()
//destructor
Func
getInfo () : tipo_elemento //observador
Func
getProx () : apuntador a Nodo //observador
Proc
setInfo (e: tipo_elemento) //modificador
Proc
setProx (p: apuntador a Nodo) //modificador
Finclase
Definición e implantación de la clase
lista básica.
Clase
Lista
Privado:
L:
apuntador a nodo
Long:
entero
Público:
Lista()
~Lista()
Func
Es_vacia(): booleano
Func
Longitud(): entero
Func
Esta_elemento_en_lista (e: tipo_elemento): booleano
Func
consultar_posicion_en_lista (e: elemento): entero
Func
consultar_elemento (posición: entero): tipo_elemento
Proc
insertar (e: tipo_elemento, pos: entero)
Proc
eliminar (pos: entero)
Proc
vaciar ()
Finclase
//esta elemento en lista retorna verdadero si
el elemento fue encontrado.
//consultar posición en lista retorna la
posición en la que ese elemento se encuentra.
//consultar elemento retorna el elemento
en la posición dada.
//insertar inserta el elemento en la
posición especificada.
//eliminar elimina el elemento en la
posición dada.
//Vaciar elimina todos los elementos de
la lista (los libera en memoria)
Implantación de la clase lista
Lista::Lista()
Inicio
L
= nulo
Long
= 0
Fin
Func Lista::Es_vacia(): booleano
Inicio
Si
(L = nulo) entonces
Retornar
(verdadero)
Sino
Retornar
(falso)
Finsi
Finfunc
Func Lista::longitud(): entero
Inicio
Retornar
(Long)
Finfunc
Func Lista::esta_elemento_en_lista(e:
tipo_elemento): booleano
Inicio
Banbera:
booleano
I:
entero
Aux:
apuntador a nodo
Bandera
= falso
I =
1
Aux =
L
Si
(long = 0) entonces
Retornar
(falso)
Sino
Mientras
( (i <= long) ^ (bandera = falso) ) hacer
Si (aux↑.getInfo = e) entonces
Bandera
= verdadero
Sino
Aux
= aux↑.getProx()
I = i + 1
finsi
Finmientras
Retornar (bandera)
finsi
finfunc
Func Lista::consultar_posicion_en_lista
(e: elemento): entero
Inicio
Banbera:
booleano
I:
entero
Aux:
apuntador a nodo
Bandera
= falso
I =
1
Aux =
L
Si
(long = 0) entonces
Retornar
(-1)
Sino
Mientras
( (i <= long) ^ (bandera = falso) ) hacer
Si
(aux↑.getInfo = e) entonces
Bandera
= verdadero
Sino
Aux
= aux↑.getProx()
I = i + 1
finsi
Finmientras
Si (bandera = verdadero) entonces
Retornar
(i)
Sino
Retornar(-1)
finsi
finsi
finfunc
Func Lista::consultar_elemento
(posición: entero): tipo_elemento
Inicio
I:
entero
Aux:
apuntador a nodo
Aux =
L
I =
1
Si
(posición = 1) entonces
Retornar
( aux↑.getInfo() )
sino
mientras ( i < posición) hacer
Aux = aux↑.getProx()
Finmientras
Retornar
( aux↑.getInfo() )
finsi
finfunc
Proc Lista::insertar (e: tipo_elemento,
pos: entero)
Inicio
finproc
Proc Lista::eliminar (pos: entero)
Inicio
finproc
Proc Lista::vaciar ()
Inicio
Finproc
~Lista::Lista()
Inicio
fin
Recursos Programados (Clase Nodo y Lista en C++)
//Clase Nodo.h
//Implementación del tipo recursivo nodo en C++
#ifndef NODO_H_
#define NODO_H_
#include <iostream>
template <class T>
class Nodo
{
protected:
T info;
Nodo<T> *prox;
public:
Nodo(T e, Nodo<T> *p);
Nodo(Nodo<T> *p);
~Nodo();
void setInfo(T e);
void setProx(Nodo<T> *p);
T getInfo();
Nodo<T> *getProx();
};
template <class T>
Nodo<T>::Nodo(T e, Nodo<T> *p)
{
info=e;
prox=p;
}
template <class T>
Nodo<T>::Nodo(Nodo<T> *p)
{
prox=p;
}
template <class T>
Nodo<T>::~Nodo()
{
}
template <class T>
void Nodo<T>::setInfo(T e)
{
info =e;
}
template <class T>
void Nodo<T>::setProx(Nodo<T> *p)
{
prox=p;
}
template <class T>
T Nodo<T>::getInfo()
{
return info;
}
template <class T>
Nodo<T> *Nodo<T>::getProx()
{
return prox;
}
#endif
#define NODO_H_
#include <iostream>
template <class T>
class Nodo
{
protected:
T info;
Nodo<T> *prox;
public:
Nodo(T e, Nodo<T> *p);
Nodo(Nodo<T> *p);
~Nodo();
void setInfo(T e);
void setProx(Nodo<T> *p);
T getInfo();
Nodo<T> *getProx();
};
template <class T>
Nodo<T>::Nodo(T e, Nodo<T> *p)
{
info=e;
prox=p;
}
template <class T>
Nodo<T>::Nodo(Nodo<T> *p)
{
prox=p;
}
template <class T>
Nodo<T>::~Nodo()
{
}
template <class T>
void Nodo<T>::setInfo(T e)
{
info =e;
}
template <class T>
void Nodo<T>::setProx(Nodo<T> *p)
{
prox=p;
}
template <class T>
T Nodo<T>::getInfo()
{
return info;
}
template <class T>
Nodo<T> *Nodo<T>::getProx()
{
return prox;
}
#endif
//Clase Lista.h
//Implementación de la clase lista.h en C++
#ifndef LISTA_H_
#define LISTA_H_
#include "Nodo.h"
template <class T>
class Lista
{
protected:
Nodo<T> *l;
public:
Lista();
~Lista();
bool esvacia();
void insertar(int pos, T e);
void eliminar(int pos);
T consultar(int pos);
int localizar(T e);
int longitud();
void vaciar();
};
template <class T>
Lista<T>::Lista()
{
l = new Nodo<T>(NULL);
}
template <class T>
Lista<T>::~Lista()
{
Nodo<T> *aux;
while(l != NULL)
{
aux = l;
l = l->getProx();
delete aux;
}
}
template <class T>
bool Lista<T>::esvacia()
{
return l->getProx() == NULL;
}
template <class T>
void Lista<T>::insertar(int pos, T e)
{
int i;
Nodo<T> *aux, *act;
aux = new Nodo<T>(e, NULL);
act = l;
i = 1;
while(i < pos)
{
act = act->getProx();
i++;
}
aux->setProx(act->getProx());
act->setProx(aux);
}
template <class T>
void Lista<T>::eliminar(int pos)
{
int i;
Nodo<T> *aux, *act;
act = l;
i = 1;
while(i < pos)
{
act = act->getProx();
i++;
}
aux = act->getProx();
act->setProx(aux->getProx());
delete aux;
}
template <class T>
T Lista<T>::consultar(int pos)
{
int i;
Nodo<T> *act;
act = l;
i = 1;
while(i <= pos)
{
act = act->getProx();
i++;
}
return act->getInfo();
}
template <class T>
int Lista<T>::localizar(T e)
{
int i;
Nodo<T> *act;
act = l->getProx();
i = 1;
while(act != NULL && act->getInfo() != e)
{
act = act->getProx();
i++;
}
if(act == NULL)
return 0;
else
return i;
}
template <class T>
int Lista<T>::longitud()
{
int i;
Nodo<T> *act;
act = l->getProx();
i = 0;
while(act != NULL)
{
act = act->getProx();
i++;
}
return i;
}
template <class T>
void Lista<T>::vaciar()
{
Nodo<T> *aux, *act;
act = l->getProx();
while(act != NULL)
{
aux = act;
act = act->getProx();
delete aux;
}
l->setProx(NULL);
}
#endif /*LISTA_H_*/
#define LISTA_H_
#include "Nodo.h"
template <class T>
class Lista
{
protected:
Nodo<T> *l;
public:
Lista();
~Lista();
bool esvacia();
void insertar(int pos, T e);
void eliminar(int pos);
T consultar(int pos);
int localizar(T e);
int longitud();
void vaciar();
};
template <class T>
Lista<T>::Lista()
{
l = new Nodo<T>(NULL);
}
template <class T>
Lista<T>::~Lista()
{
Nodo<T> *aux;
while(l != NULL)
{
aux = l;
l = l->getProx();
delete aux;
}
}
template <class T>
bool Lista<T>::esvacia()
{
return l->getProx() == NULL;
}
template <class T>
void Lista<T>::insertar(int pos, T e)
{
int i;
Nodo<T> *aux, *act;
aux = new Nodo<T>(e, NULL);
act = l;
i = 1;
while(i < pos)
{
act = act->getProx();
i++;
}
aux->setProx(act->getProx());
act->setProx(aux);
}
template <class T>
void Lista<T>::eliminar(int pos)
{
int i;
Nodo<T> *aux, *act;
act = l;
i = 1;
while(i < pos)
{
act = act->getProx();
i++;
}
aux = act->getProx();
act->setProx(aux->getProx());
delete aux;
}
template <class T>
T Lista<T>::consultar(int pos)
{
int i;
Nodo<T> *act;
act = l;
i = 1;
while(i <= pos)
{
act = act->getProx();
i++;
}
return act->getInfo();
}
template <class T>
int Lista<T>::localizar(T e)
{
int i;
Nodo<T> *act;
act = l->getProx();
i = 1;
while(act != NULL && act->getInfo() != e)
{
act = act->getProx();
i++;
}
if(act == NULL)
return 0;
else
return i;
}
template <class T>
int Lista<T>::longitud()
{
int i;
Nodo<T> *act;
act = l->getProx();
i = 0;
while(act != NULL)
{
act = act->getProx();
i++;
}
return i;
}
template <class T>
void Lista<T>::vaciar()
{
Nodo<T> *aux, *act;
act = l->getProx();
while(act != NULL)
{
aux = act;
act = act->getProx();
delete aux;
}
l->setProx(NULL);
}
#endif /*LISTA_H_*/
No hay comentarios:
Publicar un comentario