En éste capitulo hablaremos de una esructura muy utilizada e importante en el área de la programación, nos referimos a las estructuras de datos tipo Colas.

Por ejemplo cuando mandamos a impresión un documento, éste actúa en forma de cola, es decir; primera en entrar, primera en salir, o por sus siglas en inglés (First in, first out), ya que el primer documento que llega a la "Cola de Impresión", es el primer documento que es impreso.

Pero las colas, no sólo son usadas por las impresoras, sino también en la vida cotidiana tienen otras muchas aplicaciones, por ejemploel celular, cuando recibimos un mensaje de texto, éste es almacenado en un "lugar" (dentro del chip) que se comporta como cola; otro ejemplo son las colas de tareas en la pc, las colas de prioridades,etc.

Claro, estos ejemplosson muy complejos y exigen que tengamos conocimientos de sistemas operativos (uso y creación), por tanto y para resguardar nuestra salud mental, no vamos a entrar en tanto detalle respecto a las aplicaciones complejas de las colas, sin embargo trataremos algunas abstracciones que nos ayudarán a comprender el funcionamiento de ésta estructura.

Una cola, es una estructura en la cual se almacenan elementos (en orden de llegada), es decir que, se ingresan los elementos por la parte final de la estructura y se eliminan (o se sirven) por la parte del frente.

Como puede observarse, ésta estructura cuenta con dos apuntadores, uno que apunta al último elemento y otro que apunta hacia el primer elemeto (o el elemento del frente).

Se debe tener en cuenta que, una cola, almacena los datos en ella, manteniendo cierto orden, ya que sus elementos se añaden por el final de la cola y se extraen o se eliminan por la parte de frente.

El lector dispernsará el por que la insistencia de ello, pero cuando uno inicia este estudio, al momento de programar, se cunfe fácilmente, por que las sentencias de las funciones son muy parecidas a la de una pila, y en algunas ocaciones me pasaba que empezaba programando una cola, pero terminaba funcionando como pila.

-insert (q, x)à Inserta el elemento x en la parte posterior de la cola q

-remove(q)à Suprime el elemento delantero de la cola q

-empty(q)à Retorna True o false, si la cola tiene elementos o no.

Las colas pueden implementarse, al igual que las pilas, mediante dos formas:

• Arrays
• Memoria Dinámica

La figuara de arriba, muestra la forma de implementar una cola, como arreglo, en la que cada casilla, representa una estructura compuesta por el tipo de dato a guardar (o bien otra estructura).

Las variables q.rear y q.front, se van modificando cada vez que añadimos o eliminamos datos de nuestra cola.

Para determinar la cantidad de elementos en cualquier momento es:

Cant=q.rear-q.front+1

Ahora vemos un ejemplo del funcionamiento de las colas, implementadas como arreglos:

Supongamos que en una cola vamos a almacenar elementos de tipo carácter.

Insert(&q, ‘A’);

q.rear=0, q.front=0

insert (&q, ‘B’)

q.rear=1

q.front=0

insert (&q, ‘C’);

q.rear=2

q.front=0

remove(&q);

q.rear=2

q.front=1

remove(&q);

q.rear=2

q.front=2

insert(&q, ‘D’);

0 1 2 3 4

q.rear=3

q.front=2

insert(&q, ‘E’);

q.rear=4

q.front=2

Como se puede ver, al manejar una cola en forma de arreglolineal, resulta complicado y poco eficiente, por que al eliminar elementos quedan nodos vacíos y cuando se llega al último elemento de la cola, aparecerá un mensaje de error, (o al menos debería aparecer), que indioque que ya no hay más espacios, sin embargo, eso sería una total mentira, ya que tenemos elementos sin utilizar; una solución para ello podría ser que cada vez que se eliminen un elemento mover todos los datos hacia la izquierda, pero, te imaginas la cantidad de código para realizar esa acción???... eso es muy complejo (y no resuelve el problema de la eficiencia), entonces es donde surge, el considerar la cola, como un arreglo circular.

Pero como puede verse, el manero de los subíndices, resulta bastante complejo, poco accesible y, tampoco se resuelve el problema de la eficiencia; es decir que ésta solución tampoco resulta eficiente para el problema que se intenta resolver, por esas consideraciones no trataremos acerca de esta estructura, en forme de arreglo, por que no nos resulta viable, nos concentraremos en la implementación, usando memoria dinámica, la cual, si resulta más eficiente y hasta cierto punto menos compleja.

Para hacer uso de las colas, debemos declarar el nodo y los apuntadores de la cola, así:

typedef struct _nodo {

int dato;

struct _nodo *siguiente;

} tipoNodo;

typedef tipoNodo *pNodo;

typedef tipoNodo *Cola;

Donde, es evidente que, tipoNodo es el tipo de los nodos que compondrán la cola.

pNodo es el tipo para declarar punteros a un nodo.

Cola es el tipo para declarar colas

Las operaciones, siguen siendo las mismas:

Añadir

Eliminar

Si la cola está vacía:

1. Puntero primero y puntero último deben apuntar a NULL
2. Creamos el nuevo nodo (con ayuda de malloc() )
3. Luego la parte siguiente del nuevo nodo, debe apuntar a NULL
4. Tanto, primero y ultimo deben apuntar, al nuevo nodo.

Si la cola, tiene elementos:

1. Creamos el nuevo nodo, ya sea en la misma función o con ayuda de otra función
2. Hacemos que la parte siguiente del nodo apunte a NULL
3. Luego, la parte siguiente de ultimo, deba apuntar al nodo
4. Y ultimo, ahora debe apuntar al nodo.

1. Guardar el elemento dato nodo en una variable temporal
2. colocar un apuntador temporal hacia el nodo primero de la cola
3. cambiar el puntero (hacia el nodo) primero, hacia el nodo hacia el cual apunta el nodo, que estaba al frente de la cola
4. si después de eso el apuntador primero es NULL entonces no hay más datos en la cola y el apuntador ultimo también debe apuntar a NULL
5. Liberar memoria apuntada por el apuntador temporal
6. devolver el valor guardado en la variable temporal

Ejemplo 11.1

Se desea almacenar cierto número de enteros en una estructura de tipo Cola, diseñe una solución que permita, leer, eliminar datos de la cola.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

/*declaracion de la cola*/

struct nodo

{

int elemento;

struct nodo *siguiente;

};

typedef struct nodo Nodo;

typedef struct

{

Nodo *frente;

Nodo *final;

}Cola;

/*declaracion de las funciones*/

void CrearCola(Cola *cola);

void insert (Cola *cola, int x);

int remover(Cola *cola);

int empty(Cola cola);

main()

{

int x, opc=8, j=0;

Cola cola;

CrearCola(&cola);

clrscr();

while(opc!=3)

{

printf("\t\t\tMENU PRINCIPAL\n\n\n");

printf("\t 1. Insertar\n");

printf("\t 2. Eliminar\n");

printf("\t 3. Salir\n");

scanf("%d", &opc);

switch(opc)

{

case 1: printf("Ingrese el numero a introducir:\n");

scanf("%d", &x);

insert(&cola, x);

++j;

break;

case 2: printf("%d fue eliminado de la cola\n", remover(&cola));

--j;

getch();

break;

}

clrscr();

}

getch();

return 0;

}

/*definicion de las funciones*/

void CrearCola(Cola *cola)

{

cola->frente=cola->final=NULL;

}

/*funcion que inserta el dato en la parte final de la cola*/

void insert (Cola *cola, int x)

{

Nodo *nuevo;

nuevo=(Nodo*)malloc(sizeof(Nodo));

nuevo->elemento=x;

nuevo->siguiente=NULL;

if(empty(*cola))

{

cola->frente=nuevo;

}

else

cola->final->siguiente=nuevo;

cola->final=nuevo;

}

/*elimina el elemento que esta aL frente de la cola*/

int remover (Cola *cola)

{

int temp=NULL;

if(!empty(*cola))

{

Nodo *nuevo;

nuevo=cola->frente;

temp=cola->frente->elemento;

cola->frente=cola->frente->siguiente;

free(nuevo);

}

else

printf("ERROR, cola vacia, se puede eliminar\a\n");

return (temp);

}

int empty(Cola cola)

{

return (cola.frente==NULL);

}

Como puede notarse, hemos implementado, de una manera muy sencilla, los algoritmos para ingresar y eliminar datos en una cola, note que hemos declarado dos estructuras para la cola, es decir que, una de ellas contiene la parte entera de los datos que vamos a guardar y el apuntador hacia el siguiente nodo; mientras que la otra estructura, cuenta con los apuntadores del frente y del final.

Algo importante que hay que resaltar es el hecho que, en la zona de declaración de variables, debemos declarar la varible de tipo Cola que es el parámetro que le pasaremos a las diferentes funciones; muchas veces se nos olvida hacer eso y por lo cual, intentamos, erradamente, mandarle la dirección del tipo de dato, es decir; que en vez de mandarle la dirección de la variable cola (&cola), le mandamos la dirección del TAD Cola (&Cola), lo cual no sería correcto.

Apartir de ello, creamos la cola, como lo explicamos, haciendo que cola->frente=cola->final=NULL; con lo cual nos aseguramos que la cola esté vacía, y lista para agregar valores. Las demás funciones, sólo son la implementación rigurosa de los algoritmos planteados con anterioridad.

No es importante aprenderse al pié de la letra, cada una de las funciones, ya sea para la pila o para las colas, si no que, es importante, aprenderse lo que hace cada función, tener presente el algoritmo e implementarlo según convenga al problema que estamos resolviendo.

Ejemplo 11.2

Cree una cola en C, que permita introducir y realizar un suceso por el usuario, el cual debe ser una arreglo unidimensional; sin embargo, la cola debe ser implementada dinámicamente.

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

typedef struct datos elemento;

struct datos {

char suceso[81];

elemento *siguiente;

};

void error (void)

{

printf("Error, insufuciente espacio en memoria\n\a");

exit(1);

}

elemento *nuevoelemento (void)

{

elemento *q=(elemento*)malloc(sizeof(elemento));

if(!q)error();

return q;

}

void menu (void);

void introducir (elemento**, elemento**, char[]);

char *realizar (elemento**, elemento**);

main()

{

elemento *principio, *final;

char opcion, suceso[81];

principio=final=NULL;

while(1){

do{

clrscr();

menu();

opcion=toupper(getche());

}while(opcion!='I' && opcion !='R' && opcion != 'S');

clrscr();

switch(opcion){

case 'I': printf("\nIntroduzca un suceso:\n");

gets(suceso);

introducir(&principio, &final, suceso);

break;

case 'R': strcpy(suceso, realizar(&principio, &final));

if(*suceso)

printf("\realizando el suceso %s", suceso);

printf("Pulse una tecla para continuar:\n");

getch();

break;

case 'S': exit(0);

}

}

}

void menu(void)

{

printf("\n\tIntroducir suceso");

printf("\n\t realizar el suceso");

printf("\n\t salir");

printf("\n\t elija la opcion deseada (I, R, S)");

}

/*A$adir a la cola */

void introducir (elemento **p, elemento **f, char suceso[])

{

elemento *pc, *fc, *q;

pc=*p; /*principio de la cola */

fc=*f; /*final de la cola */

q=nuevoelemento();

strcpy(q->suceso, suceso);

q->siguiente=NULL;

if(fc==NULL)

pc=fc=q;

else

fc=fc->siguiente=q;

*p=pc;

*f=fc;

}

/*Recuperar dato de la cola */

char *realizar (elemento **p, elemento **f)

{

elemento *pc, *fc, *q;

char *suceso;

pc=*p; /*principio de la cola */

fc=*f; /*final de la cola*/

if(pc!=NULL)

{

q=pc;

suceso=(char*)malloc(strlen(q->suceso)+1);

strcpy(suceso, q->suceso);

pc=pc->siguiente;

if(pc==NULL)

fc=NULL;

free(q);

*p=pc;

*f=fc;

}

else

{

printf("no hay sucesos\n\n\a");

suceso[0]='\0';

}

return suceso;

}

Cuestionario

1. ¿Por qué las Colas se consideran estructuras del tipo FIFO?_____________________________________________________________________________________________________________________________________________
2. ¿Cuáles son las diferencias entre Pilas y Colas?_____________________________________________________________________________________________________________________________
3. ¿En informática, cuáles son las aplicaciones de las Colas?_____________________________________________________________________________________________________________________________
4. Mencione y explique las formas en las que podemos implementar las estructuras tipo Cola:________________________________________________________________________________________________________________________________________________________________________________________________
5. ¿Puede una cola, en algún momento comportarse como una Pila?¿Por qué? Mencione al menos un ejemplo:_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Ejercicios

1. Escribir un programa en C, que lea cierca cantidad de enteros y luego determine: Cuál es el valor mayor, el valor menor y el promedio de todos los datos.
2. Diseñe un programa que sea capaz de leer dos colas y mediante un mensaje indicar si son iguales. Nota: los elementos constitutivos de las colas son caracteres.
3. En un supermercado, se tiene sólo una caja habilitada para que los clientes puedan cancelar sus compras, se pide que, el sistema muestren la cantidad de productos comprados, el monto total de la venta.
4. Una tienda dispone de 10 repartidores, para las entregas a domicilio, genere un programa que simule: el despacho de cada repartidor, sabiendo que si la entrega se realiza después de 30 minutos de realizada la orden, al cliente se le aplica un 30% sobre la compra. El programa debe mostrar: el total de entregas por repartidor, el monto de la ganancia, y las pérdidas, en concepto de entregas tardías.
5. En la empresa "La Bodeguita", se lleva el control de los inventarios, por el método PEPS, (Primeros en entrar, Primeros en Salir). Y se desea mecanizar este proceso, para ello, se deben ingresar los productos, y para registrar la venta, se necesitan los siguientes datos: Código, correlativo de orden, descripción, cantidad y precio. El sistema debe generar: el informe de todas la ventas, el artículo que más se ha vendido, y el que menos, así como la ganancia de la empresa.

Identifique, y corriga, los posibles errores que están presentes en las siguientes funciones:

int empty(Cola cola)

{

return (cola.frente);

}

Nodo *CrearNodo(int x)

{

aux=(Nodo*)malloc(sizeof(Cola));

aux->elemento=x;

aux->siguiente=NULL;

return aux;

}

En muchos cursos, libros y Manuales, inician el estudio de las Estructuras de Datos Dinámicas, hablando acerca de las Listas, sin embargo, éste manual ha sido la excepción, ya que considero que, el estudio de las listas, posterior al conocimiento y manejo de las Pilas y Colas, se hace mucho más comprensible.

Es una colección de elementos dispuestos uno detrás del otro, en la que cada elemento se conecta al siguiente por un "Enlace" o "Puntero".

Como se observa en la imagen, los nodos de las listas al igual que las colas y pilas, está compuesta por una parte de información (que pude ser datos enteros, flotantes, caracteres, estructuras..) y el puntero que mantiene el enlace entre un nodo y otro.

Existen varios tipos de Listas, pero para efectos de comprensión y sintetización, hablaremos de cutro tipos esenciales de listas:

1. Lista simplemente enlazada: Cada nodo, contiene un único apuntador hacia el siguiente nodo, por lo cual hace de él una estructura muy eficiente, ya que el último de la lista apunta hacia null, por ello, es fácil hacer recorridos directos.



2. Listas Doblemente enlazada: Esta lista se caracteriza por que sus nodos contienen dos punteros, uno hacia el nodo siguiente y otro hacia el nodo anterior.



3. Listas Circulares: Este tipo de lista, es sólo una extención de las lista simplemente enlazada, con la diferencia que el último elemento se enlaza al primer elemento de la lista, lo cual permite el recorrido en forma de anillo



4. Lista Circular Doblemente enlazada: Quizá este tipo de lista, sea la más compleja, ya que es la combinación de las lista circular y las doblemente enlazadas, ya que es una lista doblemente enlazada donde el primer elemento se conecta con el último y viceversa.

1. Si P apunta a NULL, mostrar un mensaje de error y terminar la ejecución.
2. sino, genere otro puntero, q, en el cual guarde la información.
3. luego, la parte siguiente del nuevo nodo, debe apuntar a al siguiente nodo, del apuntado por P.
4. p->siguiente, debe apuntar al nuevo nodo .

el código, sería así:

void insafter (Lista p, char x)

{

Lista q;

If(p==NULL)

Printf("Error, lista vacía\a\n");

Else

{

q=getnode();

q->x=x;

q->sig=p->sig;

p->sig=q;

}

}

Ésta función es muy similar a la función de eliminar de las pilas y colas, con la diferencia que debemos enlazar el nodo anterior con el siguiente nodo:

Algoritmo:

1. Crear un nodo auxiliar apuntado por q.
2. si p, apunta a nullo p->sig apunta a NULL, imprima mensaje de error
3. sino; q, en suparte de siguiente, debe tener la dirección a la que apuntaba, p->sig.
4. p->sig debe apuntar a q en su parte de siguiente.
5. Liberar de memoria el nodo apuntado por q.

void delafter(Lista p, char *px)

{

Lista q;

If(p==NULL || p->sig==NULL)

Printf("ERROR, lista vacía\a\n");

Else

{

q->sig=p->sig;

p->sig=q->sig;

free(q);

}

}

Int empty(Lista p)

{

int r;

if(p==NULL)

r=1;

else

r=0;

return r;

}

/* Para limpiar la lista*/

void limpiar (Lista L)

{

L=NULL;

}

Con ésta función, lo que hacemos es inicializar la lista a NULL, por lo que se pierden los elementos que habíamos guardado en los nodos. Pero Ojo, eso no significa que hayamos liberado memoria que ocuparon, los nodos, esa memoria será liberada, cuando se deje de ejecutar el programa, o si hubiésemos, utilizado la función free(), para cada nodo.

Ésta función, nos devuelve, la dirección de memoria de un valor que deseamos buscar en la lista.

Lista buscar(Lista frente, char x)

{

/* frente: puntero que indica la cabeza de una lista.

X: carácter que deseamos buscar

*/

Lista dir;

For(dir=frente; dir!=NULL; dir=dir->sig)

If(x==dir->x)

Return dir;

Return NULL;

}

Ejemplo 12.1

Se pide que, cree una agenda, donde pueda almacenar el nombre, teléfono y correo electrónicode sus amigos; haciéndo uso de una lista enlazada. Dicha agenda, debe permitirle: añadir un nuevo registro, eliminar y Mostrar la lista de todos los registros.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

struct nodo{

int corre;

char nom[80];

char tel[9];

char email[50];

struct nodo *sig;

};

typedef struct nodo *Lista;

Lista p, cabeza;

Lista getnodo();

void insafter(Lista p, char nom[80], char tel[9], char email[50], int i);

void eliminar (Lista p, int k);

void imprimir(Lista p);

main()

{

char nom[80], tel[9], email[50];

int k, opc=8, i=0;

clrscr();

p=getnodo();

cabeza=p;

while(opc!=4)

{

printf("\t\t\nMENU PRINCIPAL\n\n\n");

printf("\t\t1. Registrar Nuevos Datos\n");

printf("\t\t2. Imprime todos los registros\n");

printf("\t\t3. Eliminar Datos\n");

printf("\t\t4.Salir\n");

scanf("%d", &opc);

switch(opc)

{

case 1: printf("Ingrese el Nombre:");

scanf("%s", &nom);

printf("Telefono:");

scanf("%s", &tel);

printf("e-mail:");

scanf("%s", email);

i++;

insafter(&p, nom, tel, email, i);

break;

case 2: printf("Listado de todos los registros\n\n");

imprimir(&p);

break;

case 3: printf("¨A quien desea eliminar?(ingrese el correlativo)\n");

scanf("%d", &k);

eliminar(&p, k);

break;

}

clrscr();

}

return 0;

}

Lista getnodo()

{

Lista p;

p=(Lista)malloc(sizeof(struct nodo));

if(p==NULL)

printf("Memoria Insuficiente\a\n");

return p;

}

void insafter(Lista p, char nom[80], char tel[9], char email[50], int i)

{

Lista q;

if(p==NULL)

printf("ERROR, lista vac¡a\n\a");

else

{

q=getnodo();

strcpy(q->nom, nom);

strcpy(q->tel, tel);

strcpy(q->email, email);

q->corre=i;

q->sig=p->sig;

p->sig=q;

p=p->sig;

}

}

void imprimir(Lista p)

{

Lista dir;

p=p->sig;

for(dir=p; dir!=NULL; dir=dir->sig)

{

printf("\n\t***********************************\n");

printf("\t correlativo: %d\n", dir->corre);

printf("\t Nombre %s\n", dir->nom);

printf("\t Telefono: %s\n", dir->tel);

printf("\t e-mail: %s\n", dir->email);

printf("\n\t***********************************\n");

getch();

}

}

void eliminar(Lista p, int k)

{

Lista indice;

cabeza=p;

for(indice=cabeza; indice!=NULL; indice=indice->sig)

{

if(indice->corre==k)

{

cabeza=cabeza->sig;

printf("%s est  hiciendo eliminado\n", indice->nom);

getch();

if(p==NULL || p->sig==NULL)

printf("ERROR, ya no hay m s datos\n");

else

{

cabeza->sig=indice->sig;

free(indice);

}

}

}

}

Hata ahora, los recorridos que hemos realizado en las listas; han sido en sentido directo, pero existen muchos casos en los que es necesario acceder a los elementos de las estructuras en ambos sentidos (adelante y por detrás), de ahí es donde se deriva la importancia de esta estructura.

La declaración de la estructura puede ser:

typedef struct nodo{

int elemento;

struct nodo *sig, *ant

}Lista;

/*Note la declaración de dos punteros, uno hacia el nodo siguiente

y el otro hacia el nodo anterio

*/

typedef Lista *tPosicion;

typedef Lista *tLista

Las operaciones básicas, siguen siendo las mismas; aunque clara con sus variantes, por que recordemos que, en éste tipo de estructuras estamos manejando dos punteros, en un solo nodo.

Para insertar en un lista, existen algunos mecanismos, casos, formas, etc.

Por ejemplo:

à INSERTAR AL FRENTE DE LA LISTA

1. si lista está vacía

1. Crear un nuevo nodo
2. Asignar el valor a la parte dato del nodo
3. Hacer que nuevo nodo, en su parte de anterior apunte a NULL
4. Y en su parte de siguiente a la lista
5. El puntero del elemento de l frente de la lista, debe apuntar al nuevo nodo.
2. si la lista No está vacía

1. Agregar un nuevo nodo
2. Asignar el valor a la parte dato del nodo
3. Hacer que nuevo nodo, en su parte de anterior apunte a NULL
4. El nuevo nodo en su parte de siguiente, debe apuntar al primer elemento de la lista
5. Si la Lista!=NULL, entonces Lista->ant=p
6. Luego el apuntador a la lista (Lista), debe apuntar al nuevo nodo.

Void inserfrente (tPosicion Lista, int x)

{

tPosicion p;

if(empty==1)

{

p=getnodo();

p->elemento=x;

p->ant=NULL;

p->sig=Lista;

Lista=p;

}

else

{

p=getnodo();

p->elemento=x;

p->ant=NULL;

p->sig=Lista;

if(Lista!=NULL)

Lista->ante=p;

Lista=p;

}

}

à INSERTAR AL FINAL DE LA LISTA

Para hacer este tipo de operación, necesitamos un puntero (q), que apunte al último elemento de la lista.

El algoritmo sería, entonces, el siguiente:

1. Crear el nuevo nodo
2. hacer que p->elemento, sea igual al valor
3. hacemos que p->ant apunte al ultimo nodo
4. p->sig será igual a lo que tenga q->sig
5. q->sig debe apuntar al nuevo nodo

void inserfinal (tPosicion q, int valor)

{

tPosicion p;

p=getnodo();

p->elemento=valor;

p->ant=q;

p->sig=q->sig;

q->sig=p;

}

tLista getnodo()

{

tLista nuevo;

nuevo=(tLista)malloc(sizeof(Lista));

if(nuevo==NULL)

printf("Memoria insuficiente\a\n");

nuevo->sig=nuevo->ant=NULL;

return nuevo;

}

1. Busque el nodo que contiene el dato que desea eliminar , teniendo el cuidado de guardar la dirección del nodo a eliminar y la dirección del nodo anterior a éste.
2. la parte siguiente del nodo anterior debe apuntar al puntero sifguiente del nodo a eliminar.
3. la parte anterior del nodo siguiente a eliminar debe apuntar a la parte a lo que apuntaba la parte anterior del nodo a eliminar.
4. en caso de que el nodo a eliminar sea el primero en la lista, se modifica la cabeza para que tenga la dirección del nodo siguiente.
5. finalmente liberamos la memoria ocupada.

Void eliminar (tPosicion Lista, int x)

{

tPosicion actual;

int encontrado=0;

actual=Lista;

/*empezamos a buscar el nodo*/

while((actual!=NULL) && (!econtrado))

{

encontrado=(actual->elemento==x);

if(!encontrado)

actual=actual->sig;

}

/*Enlazamos el nodo anterior con el diguiente nodo*/

if(actual!=NULL)

{

if(actual==Lista)

{

lista=actual->sig;

if(actual->sig!=NULL)

actual->sig->ant=NULL;

}

else if(actual->sig!=NULL) /*No es el ultimo nodo*/

{

actual->ant->sig=actual->sig;

actual->sig->ant=actual->ant;

}

else

actual->ant->sig=NULL;

free(actual);

}

}

Ejemplo 12.2

/*******************************************************************

* LISTA.C *

* Objetivo del programa: Realizar un programa que de de altas, *

* busque y liste una lista de tipo estructura dinamica *

* doblenmente ligada *

* Versi›n: 2.1 *

* Autor: JOSE LUIS SANCHEZ FERRUSCA *

* Fecha: 6/04/2005 *

*******************************************************************

/********************* Inclusi¢n de librer¡as **********************/

#include <stdio.h>

#include <malloc.h>

/********************* Prototipos **********************************/

void altas(void);

void busqueda(void);

void listado(void);

void baja(void);

/********************* Variables Globales **************************/

struct lista *nuevo,*primero,*recorre, *anterior;

int i,op,num,bus,opcion;

typedef struct lista;

struct lista /* Crea una lista de tipo struct con dos campos, numero (entero) y sig (apuntador de tipo struct lista)*/

{

int numero;

struct lista *sig, *ant;

};

void main()

{

op=1;

nuevo=NULL; /* El apuntador esta vacio */

primero=NULL; /* El apuntador esta vacio */

recorre=NULL; /* El apuntador esta vacio */

do

{

/* clrscr(); */

printf ("\n\n \t *********************************\n");

printf (" \t *** ***\n");

printf (" \t *** PROGRAMA DE ESTRUCTURAS ***\n");

printf (" \t *** ***\n");

printf (" \t *********************************\n");

printf (" \n\n\n \t 1.- ALTAS \n \t 2.- BUSQUEDA \n \t 3.- LISTADO \n\t 4.- Baja \n\t 5.- SALIR \n\n");

printf (" SELECCIONE UNA OPCION DEL MENU \n");

scanf ("%d",&opcion);

switch(opcion)

{

case 1: altas();

break;

/*case 2: busqueda();

break;*/

case 3: listado();

break;

case 4: baja();

break;

}

}while (opcion!=5);

scanf ("\n");

}

/********************* Declaracion de Funciones ********************/

/********************************************************************

* Funci¢n:Alta *

* Argumentos: void - No recibe argumentos *

* - * *

* Valor de Retorno: Void -> No regresa valores *

* Comentario: Esta función va a dar de alta los datos en la lista *

* *

********************************************************************/

void altas(void)

{

int flag;

nuevo=primero;

printf ("\n INGRESE EL NUMERO PARA DARLO DE ALTA\n ");

scanf ("%d",&num);

nuevo=malloc(sizeof(struct lista)); /* Busca un espacio de memoria del tamaño de struct lista */

nuevo->numero=num; /* Vuevo en su campo numero asignale el valor de num */

nuevo->sig=NULL; /* Ya no hay más espacios de memoria para ligar */

nuevo->ant=NULL;

recorre=primero;

if (primero==NULL)

{

primero=nuevo;

recorre=nuevo;

}

else

{

do

{

if (primero==recorre)

{

if (nuevo->numero<primero->numero)

{

primero=nuevo;

primero->sig=recorre;

recorre->ant=nuevo;

}

else

{

primero->sig=recorre;

recorre->ant=primero;

}

}

else if (recorre->sig!=NULL)

{

if (nuevo->numero<recorre->numero)

{

anterior=recorre->ant;

nuevo->ant=anterior;

nuevo->sig=recorre;

anterior->sig=nuevo;

recorre->ant=nuevo;

}

}

else

{

recorre->sig=nuevo;

nuevo->ant=recorre;

}

}while(recorre!=NULL);

}

}

/********************************************************************

* Funci¢n: Busqueda *

* Argumentos: void - No recibe argumentos *

* - * *

* Valor de Retorno: Void -> No regresa valores *

* Comentario: Esta función va a hacer una busqueda en la lista *

* *

********************************************************************/

void busqueda()

{

int bus;

recorre=primero;

printf ("\nINGRESE EL NUMERO A BUSCAR\n");

scanf ("%d",&bus);

do

{

if (bus==recorre->numero) /* El dato a buscar se encuentra en recorre en su campo numero ?*/

{

printf ("\n SE HA ENCONTRADO EL NUMERO %d\n ",bus);

recorre=recorre->sig;

}

else

recorre=recorre->sig;

}while (recorre!=NULL);

}

/********************************************************************

* Funci¢n: listado *

* Argumentos: void - No recibe argumentos *

* - * *

* Valor de Retorno: Void -> No regresa valores *

* Comentario: Esta función va a imprimir la lista *

* *

********************************************************************/

void listado()

{

recorre=primero;

while (recorre!=NULL)

{

printf ("\n NUMERO--> %d\n",recorre->numero);

recorre=recorre->sig;

}

}

/********************************************************************

* Funci¢n:Baja *

* Argumentos: void - No recibe argumentos *

* - * *

* Valor de Retorno: Void -> No regresa valores *

* Comentario: Esta función va a dar de baja los datos en la lista *

* *

********************************************************************/

void baja()

{

recorre=primero;

anterior=primero;

printf ("\nINGRESE EL NUMERO A BUSCAR\n");

scanf ("%d",&bus);

do

{

if (bus==recorre->numero) /* El dato a buscar se encuentra en recorre en su campo numero ?*/

{

if (recorre==nuevo)

{

nuevo=nuevo->ant;

free(recorre);

nuevo->sig=NULL;

}

else if (primero!=recorre) /* Estan primero y recorre en la misma posición? */

{

anterior->sig=recorre->sig;

free(recorre);

recorre=anterior->sig;

recorre->ant=anterior;

else

{

anterior->sig=recorre->sig;

recorre=anterior->sig;

free(primero);

primero=recorre;

anterior=primero;

}

}

else

if (recorre==primero)

recorre=recorre->sig;

else

{

recorre=recorre->sig;

anterior=anterior->sig;

}

}while (recorre!=NULL);

}

NOTA: Este código ha sido elaborado por JOSE LUIS SANCHEZ FERRUSCA, aunque, por razones de didáctica, he hecho algunas modificaciones.

Se puede afirmar que, las listas circulares, son un caso especial de las listas simples, con la variante que el último nodo, en su parte de siguiente, apunta al primer nodo de la lista.

La parte de dato, de la lista circular, puede estar compuesta de enteros, punto flotante, caracteres, arreglos o estructuras.

Typedef struct elemento{

Int dato;

Struct nodo*sig;

}nodo;

typedef nodo* lc;

lc *Lista=NULL;

lc getnodo()

{

lc nuevo;

nuevo=(lc)malloc(sizeof(nodo));

nuevo->dato=x;

nuevo->sig=nuevo;

/* para que sea circular debe apuntar a sí mismo*/

return nuevo;

}

Void insertar (lc *Lista, int x)

{

lc p;

p=getnodo(x);

if(*Lista==NULL) /*si hay elementos en la lista*/

{

p->sig=(*Lista)->sig;

(*Lista)->sig=p;

}

*Lista=p;

}

Éste algoritmo es muy parecido al de una lista simple, ya que ésta estructura, como ya se ha dicho, es un caso especial de la lista lineal, sin embargo, existen unas pequeñas consideraciones a tener en cuenta.

Algotitmo

1. Se debe buscar el nodo que contiene el dato que desea eliminar
2. luego se debe enlazar el nodo anterior con el siguiente
3. si el nodo a eliminar está apuntado por "Lista", es decir el puntero de acceso, se modifica "Lista" para que contenga la dirección del nodo anterior a éste.
4. finalmente se libera el nodo de la memoria

void eliminar (lc *Lista, int x)

{

lc *actual;

int encontrado=0;

if((*Lista)==NULL)

printf("No hay elementos en la lista\n");

else

{

actual=*Lista;

/*empezamos a buscar*/

while((actual->sig!=Lista) && (!encontrado))

{

encontrado=(actual->sig->dato==x);

if(!encontrado)

actual=actual->sig;

encontrado=(actual->sig->dato==x);

/*enlazamos el nodo abterior con el nodo siguiente*/

if(encontrado)

{

lc=p;

p=actual->sig; /*nodo a eliminar*/

if(*Lista==(*Lista)->sig)

*Lista=NULL;

else

{

if(p==*Lista)

*Lista=actual;

actual->sig=p->sig;

}

free(p);

}

}

}

Ejemplo 12.3

Las reglas de la divisibilidad indican que, si un número termina en cero o cifra par, es divisible por dos; y si la suma de sus elementos es tres o múltiplo de tres, entonces, ese número es divisible por tres. Además que, si un núero es divisible por dos y por tres al mismo tiempo, entonces es divisible por seis. (ejemplo 12. Termina en cifra par, 2+1=3, es divisible por 2 y por tres, entonces también es divisible por 6), diseñe un programa que, que almacene en una lista circular, y muestre por cual de esos tres números (2 , 3 y 6) es divisible.

/*Ejemplo de listas *.C*/

#include <stdio.h>

#include <conio.h>

#include <ctype.h>

typedef struct elemento{

int x;

struct elemento *sig;

}nodo;

typedef nodo* lc;

lc *Lista;

int k=0;

void inser (lc *Lista, int x);

void divi(lc* Lista);

main()

{

int num[80], pos=0, i=0;

clrscr();

printf("\t\t\tINGRESE EL NUMERO:\n\n\n");

while((num[pos++]=getchar())!='\n');

num[--pos]='\0';

for(i=0; i<pos; i++)

inser(Lista, num[i]);

divi(Lista);

getch();

return 0;

}

void inser(lc *Lista, int x)

{

lc nuevo;

nuevo=(lc)malloc(sizeof(nodo));

nuevo->x=x;

nuevo->sig=nuevo;

if(*Lista!=NULL)

{

nuevo->sig=(*Lista)->sig;

(*Lista)->sig=nuevo;

}

*Lista=nuevo;

k++;

}

void divi (lc *Lista)

{

int div2=0, div3=0, sum=0, i=1;

lc aux;

aux=(*Lista)->sig;

while(i<=k)

{

sum=sum+aux->x;

aux=aux->sig;

i++;

}

if(sum%3==0)

{

div3=1;

printf("El numero es divisible entre tres\n");

}

aux=(*Lista);

if(aux->x%2==0)

{

div2=1;

printf("El numero es divisible entre Dos\n");

}

if(div2==1 && div3==1)

printf("Tambien es divisible entre 6\n");

getch();

}

Lo primero que hacemos, es almacenar el número en un arreglo, auxiliar, ya que cada elemento del número lo guardamos en una casilla del arreglo, luego, vamos pasando cada número como parámetro a la función insert(), ya que en ella creamos los nodos y en sí, la lista circular. Una vez que, hemos llenado la lista, pasamos el puntero de acceso a la función divi(), en la cual determinamos los núemeros por los cuales es divisible.

Éste tipo de listas, es una combinación de las listar cicular y la lista doblemente enlazada, puesto que cada nodo está conectado con el siguiente nodo y el anterior a él, además que el primer nodo está conectado al último, y el último al primero.

Es por esa razón que, particularmente consideto que, ésta estructura es una de las más complejas de manejar, por las consideraciones que debemos tener.

Typedef struct celda{

Int elemento;

Struct nodo*sig, ant;

}tipocelda;

typedef tipocelda *tPosicion;

typedef tipocelda* tLista;

tLista getnodo()

{

tLista L;

L=(tLista)malloc(sizeof(tipocelda));

If(L==NULL)

Printf("ERROR: Memoria Insuficiente\a\n");

L->sig=L->ant=L;

Return L;

}

Algoritmo:

1. Crear el nuevo nodo
2. Guardar el dato en el nuevo nodo
3. Hacer que el nuevo nodo, en su parte de siguiente apunte al nodo anterior (que está siendo apuntado por p)
4. Luego copiar en nuevo->ant, lo que hay en p->ant
5. hacer que en la parte de siguiente del nodo anterior apuntado por p, contenga la dirección del nuevo nodo
6. hacer que p->ant apunte anuevo
7. guardar la dirección de nuevo en p

void insertar (int x, tPosicion p)

{

tPosicion nuevo;

nuevo=(tPosicion)malloc(sizeof(tipocelda));

if(nuevo==NULL)

printf("ERROR: memoria insuficiente\a\n");

nuevo->elemento=x;

nuevo->sig=p;

nuevo->ant=p->ant;

p->ant->sig=nuevo;

p->ant=nuevo;

p=nuevo;

}

Esta función recibe como argumento un dato a buscar, dentro de la lista y devuelve el nodo que contenga dicho dato.

tPosicion buscar (int x, tLista L)

{

tPosicion p;

int ban=0;

p=L->sig;

while((p!=L) && (!ban))

if(p->elemento==x)

ban=1;

else

p=p->sig;

return p;

}

Ejemplo 12.4

Diseñe una lista circular doblemente enlazada, que gaurde enteros, y luego permita determinar cuantas veces se encuentra un número ingresado por el usuario.

#include <stdio.h>

#include <conio.h>

#include <string.h>

/*Version Circular doblememente enlazada*/

typedef struct tipoNodo{

int x;

struct tipoNodo *adelante;

struct tipoNodo *atras;

}Nodo;

/*Declaracion de los sinonimos para referirnos al tipo de dato*/

typedef Nodo *tLista;

typedef Nodo *tPosicion;

int cont=0;

/*Declaraci¢n de las funciones que utilizaremos*/

void insertarPrim (tLista cabeza, int entrada);

tLista CrearNodo();

void ImprimeLista(Nodo *ptr);

int buscar(int busca, Nodo *cabeza, Nodo *ptr);

main()

{

/*inicio del programa principal*/

Nodo *ptr;

tPosicion cabeza;

int entrada, opc, busca;

char ban;

/*cabeza contiene la direcci¢n del primer nodo creado*/

cabeza=CrearNodo();

ban='S';

clrscr();

printf("\n\n\n\n");

printf("\n\tÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ");

printf("\n\tÛÛ ÛÛ");

printf("\n\tÛÛ PROGRAMA QUE CALCULA LOS VALORES REPETIDOS EN UNA LISTA ÛÛ");

printf("\n\tÛÛ DOBLEMENTE ENLAZADA ÛÛ");

printf("\n\tÛÛ ÛÛ");

printf("\n\tÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ");

while(ban=='S' || ban=='s')

{

printf("\n\nIngrese un elemento para la lista:\n");

scanf("%d", &entrada);

cont++;

/*le enviamos a la funcion de insertar, le enviamos la direcci¢n del

primer nodo y el valor que vamos a introducir*/

insertarPrim(cabeza, entrada);

printf("¨Desea Introducir un nuevo elemento a la lista? (S/N)\n");

ban=getch();

}

printf("Los Valores Guardados en la Lista son:\n");

/*la funcion de imprimir, recibe un puntero hacia el primer

nodo para iniciar con la impresion*/

clrscr();

ImprimeLista(cabeza);

getch();

clrscr();

printf("\n\t\t¨Que desea Hacer?\n");

printf("\t\t1.Buscar un valor en la lista\n");

printf("\t\t2.Salir\n");

scanf("%d", &opc);

switch(opc)

{

case 1:clrscr();

printf("Ingrese el valor que desea buscar en la lista:\n");

scanf("%d", &busca);

printf("El valor %d se encuentra %d veces en la lista\n\n", busca,buscar(busca,cabeza, cabeza));

break;

case 2:exit(1);

default:printf("Error, el comando no es v lido\n");

break;

}

getch();

return 0;

}

/*definici¢n de las funciones*/

void insertarPrim(tPosicion cabeza, int entrada)

{

tPosicion nuevo;

/*creamos un nuevo nodo y le asignamos la direccion de memoria*/

nuevo=(tPosicion)malloc(sizeof(Nodo));

if(nuevo==NULL)

printf("ERROR\n");

nuevo->x=entrada;

/*la parte de adelante del nuevo nodo, apunta al primer nodo*/

nuevo->adelante=cabeza;

nuevo->atras=cabeza->atras;

cabeza->atras->adelante=nuevo;

cabeza->atras=nuevo;

}

tLista CrearNodo()

{

/*creamos un nuevo nodo, el cual sera la "cabeza" de la lista*/

tLista L;

L=(tLista)malloc(sizeof(Nodo));

if(L==NULL);

printf("Error, memoria Insuciente\n");

L->adelante=L->atras=L;

return L;

}

void ImprimeLista(Nodo *ptr)

{

Nodo *p;

int k=0;

if(ptr!=NULL)

{

printf("Lista de N£meros Guardados:\n");

p=ptr->adelante;

do{

k++;

if(k<=cont)

printf("\t\t\t* %d *\n", p->x);

p=p->adelante;

}while(p!=ptr->adelante);

}

else

{

printf("No Hay elementos en la Lista\n");

}

}

int buscar(int busca, Nodo *cabeza, Nodo *ptr)

{

int k=0;

if(ptr!=NULL)

{

cabeza=ptr->adelante;

do{

if(cabeza->x==busca)

k++;

cabeza=cabeza->adelante;

}while(cabeza!=ptr->adelante);

}

else

{

printf("No Hay elementos en la Lista\n");

}

return k;

}

Cuestionario

1. ¿Qué son y para que sirven las listas?_______________________________________________________________________________________________________________________________________________________________________________________
2. ¿Cuál es la diferencia entre una lista circular y una doblemente enlazada?__________________________________________________________________________________________________________________________________________________________________________________
3. Una lista, ¿Puede comportarse como una cola?_______________________________________________________________________________________________________________________________________________________________________________________
4. ¿Por qué se afirma que una lista circular, no tiene ni primer y último elemento?__________________________________________________________________________________________________________________________________________________________________________________
5. La función getnodo() e insertar(), se diferencian en:__________________________________________________________________________________________________________________________

Ejercicios

1. En una lista simple, que almacena enteros, mostrar cual es el dato mayor y cual es el dato menor.
2. Diseñe un registro para n alumnos de una Universidad, con sus respectivas notas de Programacion II y Estructuras de Datos, dichos datos, se deben guardar en una Lista lineal. Se sabe que, en ésta universidad, existe la política que si, un alumno ha reprodado estas dos materias, es dado de baja en la universidad. (Nota mínima 6.00)
3. Se desea guardar cierta cantidad de caracteres en una lista doble, y luego imprimir los caracteres de izquierda a derecha y viceversa.
4. Diseñe un programa que, le permita al usuario, almacenar en una lista doblemete enlazada, los registros de las personas que han adquirido un seguro de vida, además que permita eliminar registros, y adicionar nuevos datos.
5. En una lista circular se desean guardar, cadenas de caracteres, y luego imprimir la cadena de mayor longitud.
6. Diseñe un programa queopere con números complejos (tienen parte real e imaginaria), y permita, sumarlos, restarlos, multiplicarlos, y determinar la magnitud de cada uno de ellos.
7. Escribir un programa en C, que apartir de una lista doble circular, ordene alfabéticamente, los caracteres contenidos en ella y luego los imprima.
8. Diseñe un programa en C, que contenga una lista circular, cuyos elementos sean enteros largos, luego imprimir todos los elementos y la suma de ellos.
9. El aeropuerto internacional de El Salvador, desea controlar el flujo de pasajeros, y de aerolíneas que circulan por él. Diseñe un programa que de soporte a las salidas y entradas de los aviones, mediante una lista doblemente enlazada cuya información sería la siguiente: Destino, compañía, hora de salida y pasajeros. Luego, y apartir de ese último dato, es que se eliminarán los datos de la lista de pasajeros.
10. Un punto en el espacio, está compuesto por coordenadas x, y, z. Diseñe un programa que apartir de una lista circular doble, determine la distancia entre el primer punto y el último. (Nota: D²=(x1-x2)²+(y1-y2)²+(z1-z2)²).

Del lenguaje C, hace falta por hablar mucho, con estas insignificantes páginas, no he agotado el estudio de éste interesante y útil, lenguaje de programación. Sin embargo, yo concluyo hasta aquí, por que algunas cosas ya no me compete, hablarlas a mí.

No me queda mas que, desearte suerte, en ésta etapa como programador.

Y ánimo!!! Sigue siempre adelante....

Recuerda que puedes hacer cualquier comentario, sugerencia, observación, etc, a mi correo electrónico:

memeboi27[arroba]hotmail.com

-"Aprenda Lenguaje ANSI C Como si estuviera en Primero". De jalón de la Fuente, Javier García. Rodriguez Garrido, José Ignacio. Escuela Superior de Ingenieros Industriales, Universidad de Navarra. 1998

-"Curso de C". Urrutia, Gorka. http://www.elrincondelc.com

-"Introducción al Lenguaje de Programación C/C++". Pacho, Sergio.

-"Ejercicios de Practicas de C". Ledesma Muñoz, Fernando. http://ledesma.f2o.org

-"Curso de armado y reparación de PC en 10 clases. Primera Parte". Boselli, Gustavo. gb100m[arroba]yahoo.com

-"Tutorial sobre apuntadores y arreglos en C". Jensen, Ted. Año 2000. http://www. netcom.com/~tjensen/ptr/cpoint.htm

-"Algoritmos y Estructuras de Datos, una perspectiva en C". Joyanes Aguilar, Luis. Zahonero Martínez, Ignacio. Mc Graw Hill, año 2004. Madrid, España.

-"Estructuras dinámicas de datos algoritmos, acceso, propiedades, ejemplos". Pozo, Salvador. Julio de 2001. http://www.conclase.net/c/edd/

-"Guines de Clase: Introducción a la Informática, programación I y Programación II". González, César. Castillo, Milagro. Vázquez, Rodrigo, (Respectivamente). Universidad de El Salvador, Facultad de Ingeniería y Arquitectura, Escuela de Sistemas Informáticos.