Listas programacion

1.- Listas simples enlazadas.

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es
el último nodo.

*Cómo funciona una lista simple enlazada.

Para crear una lista necesitamos recordar nuestros conocimientos sobre estructuras y asignación dinámica de memoria.Vamos a desarrollar este tema creando una sencilla agenda que contiene el nombre y el número de teléfono.
Una lista enlazada simple necesita una estructura con varios campos, los campos que contienen los datos necesarios (nombre y teléfono) y otro campo que contiene un puntero a la propia estructura. Este puntero se usa para saber dónde está el siguiente elemento de la lista, para saber la posiciónen memoria del siguiente elemento.
Struct_agenda {
Char nombre [20];
Char teléfono [12];
Struct_agenda *siguiente;

* Construcción del modelo de un elemento de la lista.

Para definir un elemento de la lista, será utilizado el tipo struct.
El elemento de la lista contendrá un campo dato y un puntero siguiente.
El puntero siguiente debe ser del mismo tipo que el elemento, si no, nopodrá apuntar hacia el elemento.
El puntero siguiente permitirá el acceso al próximo elemento.

Typedef struct ElementoLista {
Char *dato;
Struct ElementoLista *siguiente;
} Elemento;

Para tener el control de la lista es preferible guardar ciertos elementos:
El primer elemento, el último elemento, el número de elementos.

Para ello será utilizado otra estructura (no esobligatorio, pueden ser utilizadas variables).
Typedef struct Lista Identificar {
Elemento *inicio;
Elemento *fin;
Int tamaño;
} Lista;

El puntero inicio contendrá la dirección del primer elemento de la lista.
El puntero fin contendrá la dirección del último elemento de la lista.
La variable tamaño contiene el número de elementos.

Cualquiera que sea la posición en la lista, los punterosinicio y fin apuntan siempre al primer y último elemento.
El campo tamaño contendrá el número de elementos de la lista cualquiera que sea la operación efectuada sobre la lista.

*Operaciones sobre las listas enlazadas

Para la inserción y la eliminación, una solo función bastará si está bien concebida de acuerdo a lo que se necesite.
Debo recordar que este artículo es puramentedidáctico.
Por esta razón he escrito una función para cada operación de inserción y eliminación.

A. Inicialización.

Modelo de la función:
Void inicialización (Lista *lista);

Esta operación debe ser hecha antes de cualquier otra operación sobre la lista.
Esta inicializa el puntero inicio y el puntero fin con el puntero NULL, y el tamaño con el valor 0.

*La función
Void inicialización(Lista *lista){
Lista->inicio = NULL;
Lista->fin = NULL;
Tamaño = 0;
}

B. Inserción de un elemento en la lista.

A continuación el algoritmo de inserción y registro de los elementos:
Declaración del elemento a insertar.
Asignación de la memoria para el nuevo elemento.
Rellenar el contenido del campo de datos.
Actualizar los punteros hacia el primer y último elemento si esnecesario.
Caso particular: en una lista con un solo elemento, el primero es al mismo tiempo el último.
Actualizar el tamaño de la lista.

Para añadir un elemento a la lista hay varios casos:
A. Inserción en una lista vacía
B. Inserción al inicio de la lista
C. Inserción al final de la lista
D. Inserción en otra parte de la lista.

a) Inserción en una lista vacía:

Ejemplo de lafunción:
Int ins_en_lista_vacia (Lista *lista, Char *dato);

La función devuelve 1 en caso de error, si no devuelve 0.

Etapas:
Asignación de memoria para el nuevo elemento.
Rellenar el campo de datos del nuevo elemento.
El puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero inicio que vale NULL) Los...