Listas en programacion en c

Listas simplemente encadenadas

La diferencia entre una lista y una cola o pila es que los elementos de la lista pueden insertarse en cualquier lugar , logrando de esta forma que la lista quede ordenada.
Solamente trabajaremos con listas simplemente encadenadas que son aquellas que tienen una referencia al elemento siguiente.
Cada elemento de la lista será una estructura autoreferenciada ,la cuál esta formada por los datos y un puntero a la estructura del mismo tipo.
La estructura que utilizaremos es la siguiente:

typedef struct lista {
int dato;
struct lista *prox;
}Nodo;

como se puede ver la estructura contiene datos (este ejemplo solo trata un entero) y un puntero a struct lista.


Cada elemento de la lista lo representaremos por medio deldiagrama de la Figura 1

Donde aux es el puntero al comienzo de la estructura , el 8 representa el dato cargado y la flecha que sale es el punero que va a apuntar al próximo elemento de la lista.

La lista comleta quedaría representada por la Figura 2
La única forma de poder recorrer una lista simplemente encadenada es accediendo por el primer elemento (que nunca debe perderse) . El final de lalista se encuentra por que el puntero al próximo elemento apunta a NULL.
Básicamente existen 3 casos distintos para insertar un elemento en una lista. Para el análisis trataremos cada uno por separado para luego generar una función que permita insertar un elemento en la lista.
Los 3 casos básicos son:
Insertar un elemento al comienzo de la lista
Insertar un elemento al final de la listaInsertar un elemento en algun lugar intermedio.

Antes de empezar a analizar cada caso en particular conviene ponernos de acuerdo en cuanto al significado y nomenclatura de los punteros a usar.
Siempre , en algún lugar del programa , normalmente en main se debe llevar actualizado el puntero al comienzo de la lista.
Vamos a utilizar 4 punteros a saber
Inicio Contiene la dirección de comienzo de lalista. Cuando la lista esta vacía vale NULL.
aux Contiene la dirección de comienzo del nuevo elemento
p,w Son 2 punteros que sirven para recorrer la lista.

Para agregar un elemento a la lista se deben seguir los pasos que a continuación se enumeran:
Realizar la solicitud de memoria dinámica por medio del operador new
Cargar los datos en la estructura.
Enlazar el nuevo elemento con los queexistan en la lista
Actualizar el puntero al primer elemento.

Primer elemento de la lista - Lista Vacia
Inicialmente no existen elementos en la lista. Para identificar fácilmente esta condición asignamos a NULL el puntero al primer elemento (Inicio=NULL)



El primer ingreso se representa en la Figura 3
p=Inicio como es el primer elemento p apunta a NULL
SI ( p==NULL) Si esverdadero entonces es el único elemento de la lista
{ Inicio=aux El inicio de la lista es la dirección del nuevo elemento
aux->prox=NULL
}

Insertar al final de la lista


Para saber donde se va a insertar el nuevo elemento se debe comparar el valor del dato del nuevo elemento contra cada uno de los elementos de la lista.
Inicialmente se apunta p al comienzo de la lista y w alproximo elemento.

p=Inicio
w=p->prox
---------------
---------------
SI (w==NULL)
{ p->prox=aux
aux->prox=w
}
Insertar al comienzo de la lista
La representación gráfica de este caso se observa en la Figura 5



p=Inicio
w=Inicio
SI (aux->dato < w->dato )
{ Inicio=aux
aux->prox=w
}
Insertar en una posición intermedia
Para saber en que posición dela lista se debe insertar el elemento se debe recorrer la lista y detenerse cuando el valor del dato nuevo sea menor al valor del dato del próximo elemento.
La figura 6 representa esta condición.



p=Inicio
w=Inicio
MIENTRAS (w !=NULL )
{
SI (aux->dato < w->dato )
{
p->prox=aux
aux->prox=w
BREAK
}
p=w
w=p->prox
}
Función para insertar un elemento en una lista
La...