Lista, Cola, Pila- Algoritmo

Definición de lista
Una lista es una estructura de datos secuencial.
Una manera de clasificarlas es por la forma de acceder al siguiente elemento:
- lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array.
- lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos laposición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.
Una lista enlazada se puede definir recursivamente de la siguiente manera:
- una lista enlazada es una estructura vacía o
- un elemento de información y un enlace hacia una lista (un nodo).
Gráficamente se suele representar así:
[pic]
Como se ha dicho anteriormente, puedencambiar de tamaño, pero su ventaja fundamental es que son flexibles a la hora de reorganizar sus elementos; a cambio se ha de pagar una mayor lentitud a la hora de acceder a cualquier elemento.
En la lista de la figura anterior se puede observar que hay dos elementos de información, x e y. Supongamos que queremos añadir un nuevo nodo, con la información p, al comienzo de la lista. Para hacerlobasta con crear ese nodo, introducir la información p, y hacer un enlace hacia el siguiente nodo, que en este caso contiene la información x.
¿Qué ocurre si quisiéramos hacer lo mismo sobre un array?. En ese caso sería necesario desplazar todos los elementos de información "hacia la derecha", para poder introducir el nuevo elemento, una operación muy engorrosa.

Implementación
Para representaren lenguaje C esta estructura de datos se utilizarán punteros, un tipo de datos que suministra el lenguaje. Se representará una lista vacía con la constante NULL. Se puede definir la lista enlazada de la siguiente manera:
struct lista
{
int clave;
struct lista *sig;
};
Como se puede observar, en este caso el elemento de información es simplemente un número entero. Además se trata de unadefinición autorreferencial. Pueden hacerse definiciones más complejas. Ejemplo:
struct cl
{
char nombre[20];
int edad;
};

struct lista
{
struct cl datos;
int clave;
struct lista *sig;
};
Cuando se crea una lista debe estar vacía. Por tanto para crearla se hace lo siguiente:
struct lista *L;
L = NULL;
 
Operaciones básicas sobre listas
- Inserción al comienzo de unalista:
Es necesario utilizar una variable auxiliar, que se utiliza para crear el nuevo nodo mediante la reserva de memoria y asignación de la clave. Posteriormente es necesario reorganizar los enlaces, es decir, el nuevo nodo debe apuntar al que era el primer elemento de la lista y a su vez debe pasar a ser el primer elemento.
En el siguiente ejemplo se muestra un programa que crea una lista concuatro números. Notar que al introducir al comienzo de la lista, los elementos quedan ordenados en sentido inverso al de su llegada. Notar también que se ha utilizado un puntero auxiliar p para mantener correctamente los enlaces dentro de la lista.
#include

struct lista
{
int clave;
struct lista *sig;
};

int main(void)
{
struct lista *L;
struct lista *p;
int i;
L =NULL; /* Crea una lista vacia */

for (i = 4; i >= 1; i--)
{
/* Reserva memoria para un nodo */
p = (struct lista *) malloc(sizeof(struct lista));
p->clave = i; /* Introduce la informacion */

p->sig = L; /* reorganiza */
L = p; /* los enlaces */
}
return 0;
}
- Recorrido de una lista.
La idea es ir avanzando desde el primer elemento hasta encontrar lalista vacía. Antes de acceder a la estructura lista es fundamental saber si esa estructura existe, es decir, que no está vacía. En el caso de estarlo o de no estar inicializada es posible que el programa falle y sea difícil detectar donde, y en algunos casos puede abortarse inmediatamente la ejecución del programa, lo cual suele ser de gran ayuda para la depuración.
Como se ha dicho antes, la...