Busqueda...

Tipos Recursivos y Estructuras Enlazadas


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
//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_*/

No hay comentarios:

Publicar un comentario