Codigo Fuente de Lista Simple Con Cabecera

Tipo Lista Con Cabecera
/***********************************************************/
/* Ejemplo de programa para manejar una: */
/* LISTA SIMPLEMENTE ENLAZADA CON CABECERA, */
/* como Estructura de Datos Dinámica (con punteros). */
/* Incluye: Primitivas de la lista y programa de prueba. */
/* Todo en el mismo fichero. */
/***************************************/
#include
#include
#include

/*Declaración del tipo base de la lista*/
struct element {
long num;
};
/* Tipos de la lista: */
/* Tipo de cada celda de la lista */
struct celda{
struct element elem;
struct celda *sig;
};
/* Tipo lista: Puntero a celda */
typedef struct celda *lista;

/***************************************/
/* Inicializa una lista simplemente enlazada y CON cabecera. */
/* Devuelve -1 en caso de ERROR. */
int Inicializar_lista(lista *list){
if (((*list)=(struct celda *) malloc(sizeof(struct celda))) == NULL)
return -1;
(*list)->sig=NULL;
return 0;
}
/***************************************/
/*Devuelve TRUE si la lista está vacía.*/
int Lista_vacia(lista list){
if (list->sig) return 0;
return 1;
}
/***************************************/
/* Inserta el elemento e en la posición pos de la lista ant. */
/* Si pos<=1 inserta en la primera posición. */
/* Si pos>longitud_lista, inserta en la última posición. */
/* Devuelve -1 si no hay memoria suficiente para la inserción. */
int Insertar_pos (lista ant, struct element e, long pos){
lista p, L=ant->sig;
long i=1;
if ((p=(struct celda *) malloc(sizeof(struct celda))) == NULL)
return -1;
p->elem=e;
while (L && i
ant=L;
L=L->sig;
i++;
}
ant->sig=p; /* Insertar elemento apuntado por p, entre anterior y L */
p->sig=L;
return 0;
}
/***************************************/
/* Inserta el elemento e en la lista ant ordenadamente por */
/* el campo elem.num */
/* Devuelve -1 si no hay memoria suficiente para la inserción. */
int Insertar_orden (lista ant, struct element e){
lista p, L=ant->sig;
unsigned i=1;
if ((p=(struct celda *) malloc(sizeof(struct celda))) == NULL)
return -1;
p->elem=e;
while (L && e.num>L->elem.num){ /* Hallar posición en la que insertar */
ant=L;
L=L->sig;
i++;
}
ant->sig=p; /* Insertar elemento apuntado por p, entre anterior y L */
p->sig=L;
return 0;
}
/***************************************/
/* Borra el elemento en la posición pos de la lista ant. */
/* Si la pos=1 borra el primer elemento. */
/* Devuelve -1 si no existe la posición: */
/* pila vacía, pos<1>long */
int Borrar_elemento(lista ant, long pos){
lista aux, L=ant->sig;
long i=1;
if (Lista_vacia(ant) || pos<1)
return -1; /* Posición NO válida */
while (L && i
ant=L;
L=L->sig;
i++;
}
if (L){
/* Borrar elemento apuntado por L, teniendo un puntero al anterior */
ant->sig=L->sig;
free(L);
return 0;
}
return -1; /* La lista tiene menos de pos elementos */
}
/***************************************/
/* Devuelve la longitud de la lista list (núm. de elementos). */
long Long_lista(lista list){
long i=0;
list=list->sig;
while (list) {
list=list->sig;
i++;
}
return i;
}
/***************************************/
/* Vacía la lista totalmente, dejándola inicializada. */
/* Tras esta operación NO es necesario inicializarla. */
void Vaciar_lista(lista list){
while (Borrar_elemento (list,1) != -1);
}
/***************************************/
/* Destruye la lista totalmente, liberando toda la memoria. */
/* Tras esto ES necesario Inicializar la lista para reusarla. */
void Destruir_lista(lista *list){
Vaciar_lista(*list);
free(*list); /* Liberar la cabecera */
*list=NULL;
}
/***************************************/
/* Devuelve en e, el elemento que está en la posición pos */
/* de la lista list. */
/* Si no existe esa posición, devuelve -1. En otro caso 0. */
int Leer_element (lista list, long pos, struct element *e){
long i=1;
if (Lista_vacia(list) || pos<1)
return -1;
list=list->sig; /* Nos saltamos la cabecera */
while (list && i
list=list->sig;
i++;
}
if (list){
*e=list->elem;
return 0;
}
return -1;
}
/*************************************/
/* Devuelve la posición de la primera ocurrencia del elemento */
/* e en la lista list, a partir de la posición pos (inclusive).*/
/* Esta ocurrencia será considerada por el campo elem.num */
/* Devuelve 0 si no ha sido encontrada. */
/* Con esta función, cambiando pos, podremos encontrar TODAS */
/* las ocurrencias de un elemento en la lista. */
long Posic_lista(lista list, struct element e, long pos){
long i=1;
list=list->sig; /* Saltar cabecera */
while (list && i
list=list->sig;
i++;
}
if (!list) return 0; /* No existe posición pos, luego... */
while (list && e.num!=list->elem.num) { /* Intentar encontrar el
elemento */
list=list->sig;
i++;
}
if (!list) return 0; /* No encontrado */
return i; /* Encontrado en la posición i */
}
/***************************************/
/* Actualiza la posición pos de la lista list con el elemento e*/
/* Devuelve -1 si no existe esa posición. */
int Actualiza_lista(lista list, struct element e, long pos){
long i=1;
if (Lista_vacia(list) || pos<1)>
list=list->sig; /* Saltar cabecera */
while (list && i
list=list->sig;
i++;
}
if (!list) return -1; /* Posición no existe */
list->elem=e; /* Actualización */
return 0;
}
/* FIN de las PRIMITIVAS de la LISTA SIMPLEMENTE ENLAZADA CON CABECERA */
/***************************************/
/* Imprime un elemento e por la Salida estándar. */
void Imprimir_elemento (struct element e){
printf("%li",e.num);
}
/***************************************/
/* Muestra todos los elementos de la lista list por su orden. */
void mostrar_lista(lista list){
struct element e;
unsigned i=1,tama=Long_lista(list);
while (i<=tama) {
printf("\nElemento %u: ",i);
Leer_element(list,i++,&e);
Imprimir_elemento(e);
}
}
/***************************************/
/* Muestra un menu de opciones. */
void menu(void){
puts("\n\t\t***** MENU *****\n");
puts("\tS. Destruir lista y SALIR.");
puts("\t1. Inicializar lista.");
puts("\t2. Insertar por orden.");
puts("\t3. Insertar por posición.");
puts("\t4. Mostrar lista.");
puts("\t5. Borrar elemento.");
puts("\t6. Longitud lista");
puts("\t7. Ver si está vacía.");
puts("\t8. Ver elemento n-ésimo.");
puts("\t9. Posición de un elemento a partir de una dada.");
puts("\t0. Modificar un elemento en una posición.");
printf("\n\tOpcion: ");
}
/***************************************/
void main(){
lista list;
struct element e;
char opcion='x';
long pos;
Inicializar_lista(&list);

while (opcion!='S' && opcion!='s'){
menu();
opcion=getche();
switch (opcion) {
case 's':
case 'S':Destruir_lista(&list);
break;
case '1':Vaciar_lista(list);
break;
case '2':printf("\nDame número: ");
scanf("%li",&(e.num));
if (Insertar_orden(list,e))
puts("\n\aERROR: No existe memoria suficiente.");
break;
case '3':printf("\nDame número: ");
scanf("%li",&(e.num));
printf("\nDame la posición: ");
scanf("%li",&pos);
if (Insertar_pos(list,e,pos))
puts("\n\aERROR: No existe memoria suficiente.");
break;
case '4':printf("\n----------------");
mostrar_lista(list);
puts("\n----------------");
getch();
break;
case '5':printf("\nDame posición a borrar: ");
scanf("%li",&pos);
if (Borrar_elemento(list,pos))
puts("\n\aERROR: No existe esa posición.");
break;
case '6':printf("\n- Longitud: %u.",Long_lista(list));
break;
case '7':if (Lista_vacia(list))
puts("\n- Lista VACIA.");
else puts("\n- Lista NO VACIA.");
break;
case '8':printf("\nDame posición a leer: ");
scanf("%li",&pos);
if (Leer_element(list,pos,&e))
puts("\n\aERROR: No existe esa posición.");
else
printf("\n- Elemento %li: %li.\n",pos,e.num);
break;

case '9':printf("\nDame número para buscar su posición: ");
scanf("%li",&(e.num));
printf("\nDame la posición a partir de la que buscar: ");
scanf("%li",&pos);
if (!(pos=Posic_lista(list,e,pos)))
puts(
"\n\aERROR: No existe ese elemento a partir de esa posición.");
else
printf(
"\n-La primera posición encontrada de ese elemento es: %i",
pos);
break;
case '0':printf("\nDame número para actualizar: ");
scanf("%li",&(e.num));
printf("\nDame la posición a modificar: ");
scanf("%li",&pos);
if (Actualiza_lista(list,e,pos))
puts("\n\aERROR: No existe esa posición. No se ha
modificado.");
break;
}
}
puts("\n\t***** FIN *****");
}

Estructuras de Datos Dinámicas

Son aquellas cuyo tamaño (longitud, número de elementos...) varía en tiempo de ejecución. Las más famosas son: Listas simplemente enlazadas (con y sin cabecera), Listas doblemente enlazadas (con y sin cabecera), Pilas, Colas, Árboles y Grafos.

Las Listas
Las listas son estructuras de datos que son dinámicas, esto significa que adquieren espacio y liberan espacio a medida que se necesita. sin embargo, hay una advertencia. Como regla general siempre hay que tener cuidado al manejar direcciones de espacios de memoria, porque es posible que accedamos a una localidad de memoria de la cual no deseabamos cambiar su contenido.

Las listas son estructuras de datos que son dinámicas, esto significa que adquieren espacio y liberan espacio a medida que se necesita. sin embargo, hay una advertencia. Como regla general siempre hay que tener cuidado al manejar direcciones de espacios de memoria, porque es posible que accedamos a una localidad de memoria de la cual no deseabamos cambiar su contenido.

Una lista es un conjunto de nodos que están relacionados. Cada nodo consta de dos partes:
- una donde se almacena la información,
- otra donde se guarda una referencia al siguiente nodo.

La creación de los nodos es dinámica, es decir, se crean nodos (por tanto se reserva memoria para ellos) según se van necesitando. Estos nodos finalmente estarán relacionados por un puntero que los enlaza. Ventaja: como creamos los nodos según los necesitamos, no necesitamos saber a priori la cantidad de datos que se van a manejar.

Sintaxis de un nodo:
Un nodo es una estructura donde se almacena la información y que además tiene una referencia al siguiente nodo:
struct nodo
{
struct nombre_estructura información;
struct nodo *siguiente;
}

Si cada nodo tiene sólo una referencia al nodo siguiente, se dice que la lista está enlazada de forma simple. Si cada nodo tiene dos referencias, una al nodo siguiente y otra al nodo anterior, se dice que la lista está doblemente enlazada.

/*Lista simple*/
está formado por nodos como el siguiente:
struct nodo_articulo
{
art info_articulo;
struct nodo_articulo *sig;
}

/*Lista doble*/
está formado por nodos como el siguiente:
struct nodo_articulo
{
art info_articulo;
struct nodo_articulo *sig;
struct nodo_articulo *ant;
}

Lista Simple


Lista doblemente enlazada


Además si el puntero del último elemento de la lista apunta al principio de la lista, se dice que la lista es circular. Cuando esto no ocurre, el puntero del último elemento de la lista debe tener el valor NULL. Este valor concreto representa que el puntero no está apuntando a ninguna dirección válida.

Lista Circular



Ejemplo: Supongamos que tenemos una aplicación para un registro de estudiantes. En este caso el ejemplo de nodo corresponde al estudiante que va a contener como subcampos la cédula, el nombre, el apellido, la edad y el. indice académico.

Definimos la estructura estudiante:
struct estudiante
{
long cedula;
char *nombre;
char *apellido;
int edad;
float ia;
}

/*Definición de nodo en una lista simple*/
struct nodo_estudiante
{
struct estudiante info;
struct nodo_estudiante *sig;
}

/*Definición de nodo en una lista doblemente enlazada*/
struct nodo_estudiante
{
struct estudiante info;
struct nodo_estudiante *sig;
struct nodo_estudiante *ant;
}

Es importante tener siempre un puntero que referencie el principio de la lista, ya que si se pierde esa referencia se pierde el contenido de toda la lista.

Ejemplo para probar

#include
#include
void main() {
int a, *b;
b = (int *) malloc(sizeof(int)); /* Reserva Mm para UN entero */
if (b == NULL)
printf("No hay memoria suficiente.");
else {
a=5;
*b=6;
printf("Dirección de a: %p. Valor de a: %d\n",&a, a);
printf("Dirección b: %p. valor al que apunta: %d\n",b, *b);
free(b); /* Importante: Liberar la memoria */
}
}