Listas Simplemente Enlazadas

OBJETIVOS
Definir el tipo abstracto lista y sus operaciones básicas. Clasificar los tipos de listas, indicando sus características, propiedades y operaciones. Utilizar la representación de listas con nodo cabeza. Implementar los métodos de ordenamiento y búsqueda para las listas.

BIBLIOGRAFÍA
Guardati S. 2007. Estructura de datos orientada a objetos: Algoritmos con C++. Editorial PearsonEducación. Joyanes Luis. 2003. Fundamentos de Programación. Algoritmos, estructuras de datos y objetos. Editorial McGraw-Hill. Tercera Edición. Joyanes L, Sánchez L, Zahonero I. 2007. Estructuras de datos en C++. Editorial McGraw-Hill. Aho A, Hopcrof J, Ullman J. 1998. Estructuras de datos y algoritmos. Editorial Adisson Wesley Iberoamericana, S.A.

LISTAS

TAD: LISTAS
Una lista es unaestructura lineal de datos conformada por ninguno, uno o varios elementos que tienen una relación de adyacencia ordenada donde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último. El tipo de dato de los elementos puede ser cualquiera, pero debe ser el mismo tipo para todos.

LISTAS ENLAZADAS
Una lista enlazada es una estructura de datos lineal,dinámica, formada por una colección de elementos (llamados nodos), donde cada uno de ellos se conecta al siguiente a través de un enlace.

CLASIFICACIÓN DE LAS LISTAS ENLAZADAS Las listas se pueden dividir en cuatro categorías:
Simplemente enlazada Doblemente enlazada Circular simplemente enlazada Circular doblemente enlazada Cada nodo contiene un único enlace que conecta ese nodo al nodo siguiente onodo sucesor. Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. Una lista simplemente enlazada en la que el último elemento se enlaza al primero.

Una lista doblemente enlazada en la que el último elemento se enlaza al primero y viceversa.

REPRESENTACIÓN GRÁFICA
Nodo simple dato enlace

Lista simplemente enlazada primero

REPRESENTACIÓN GRÁFICANodo doble Dato atrás adelante

Lista doblemente enlazada primero último
NULL NULL

REPRESENTACIÓN GRÁFICA
Nodo circular dato

enlace

Lista circular simplemente enlazada lc

REPRESENTACIÓN GRÁFICA
Nodo circular doble

Dato

atrás Lista circular doblemente enlazada lc

adelante

IMPLEMENTACIÓN DEL TAD LISTA SIMPLE
La implementación del TAD Lista simple requiere, en primerlugar, declarar la clase Nodo en la cual se encierra el dato y el enlace. Como el dato de la clase Nodo puede ser cualquier tipo, se usarán plantillas para dar mayor generalidad a la solución.

Nodo(T) dato: T enlace:*Nodo(T) //Métodos de acceso y modificación a los miembros de la clase

IMPLEMENTACIÓN DEL TAD LISTA SIMPLE

Seguidamente se define la clase Lista con el atributo primero querepresenta la dirección del primer elemento de la lista, y las operaciones para manejar una lista (creación, inserción, eliminación, …)

Lista(T) primero:*Nodo(T) //Métodos de acceso y modificación a los miembros de la clase

CLASE NODO SIMPLE
template class Nodo { T dato; Nodo * enlace; public: Nodo(T d) { dato = d; enlace = NULL; } Nodo(T d, Nodo * n) { dato = d; enlace = n; } T datoNodo()const { return dato; } Nodo * enlaceNodo() const { return enlace; } void ponerEnlace(Nodo * sgte) { enlace=sgte; } };

CLASE LISTA SIMPLE
template class Lista { Nodo * primero; public: Lista() { primero = NULL; } void crearLista(); //demás operaciones };

El constructor inicializa primero a NULL con lo cual se crea una Lista Vacía

OPERACIONES DE LISTAS SIMPLE
CREACIÓN: Esta operaciónconsiste en ir construyendo iterativamente los elementos de una lista, comenzando con el primer elemento. Se pueden considerar métodos que permitan crear la lista agregando cada nuevo elemento al inicio (crearInicio()) o al final (crearFinal()) de la misma.

OPERACIONES DE LISTAS SIMPLE
Creación (al inicio):
template void Lista::crearInicio() { T d; Nodo * nuevo; char resp; do{ coutd; nuevo...