Cap�tulo XI: Colas
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.
Concepto de Cola
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.
Las operaciones con las colas son:
-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
Tipo Cola Implementado como Arreglo
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�);
| C | 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.
Colas implementadas con Memoria Din�mica
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
Algoritmo Para A�adir elementos en la cola
Si la cola est� vac�a:
- Puntero primero y puntero �ltimo deben apuntar a NULL
- Creamos el nuevo nodo (con ayuda de malloc() )
- Luego la parte siguiente del nuevo nodo, debe apuntar a NULL
- Tanto, primero y ultimo deben apuntar, al nuevo nodo.
Si la cola, tiene elementos:
- Creamos el nuevo nodo, ya sea en la misma funci�n o con ayuda de
otra funci�n - Hacemos que la parte siguiente del nodo apunte a NULL
- Luego, la parte siguiente de ultimo, deba apuntar al nodo
- Y ultimo, ahora debe apuntar al nodo.
- Creamos el nuevo nodo, ya sea en la misma funci�n o con ayuda de
Algoritmo Para eliminar
- Guardar el elemento dato nodo en una variable temporal
- colocar un apuntador temporal hacia el nodo primero de la cola
- cambiar el puntero (hacia el nodo) primero, hacia el nodo hacia el cual
apunta el nodo, que estaba al frente de la cola - 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 - Liberar memoria apuntada por el apuntador temporal
- 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(“tttMENU PRINCIPALnnn”);
printf(“t 1. Insertarn”);
printf(“t 2. Eliminarn”);
printf(“t 3. Salirn”);
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 colan”, 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 eliminaran”);
return (temp);
}
int empty(Cola cola)
{
return (cola.frente==NULL);
}
Explicaci�n
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 memoriana”);
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(“ntIntroducir suceso”);
printf(“nt realizar el suceso”);
printf(“nt salir”);
printf(“nt 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 sucesosnna”);
suceso[0]=”;
}
return suceso;
}
Cuestionario
- �Por qu� las Colas se consideran estructuras del tipo FIFO?_____________________________________________________________________________________________________________________________________________
- �Cu�les son las diferencias entre Pilas y Colas?_____________________________________________________________________________________________________________________________
- �En inform�tica, cu�les son las aplicaciones de las Colas?_____________________________________________________________________________________________________________________________
- Mencione y explique las formas en las que podemos implementar las estructuras
tipo Cola:________________________________________________________________________________________________________________________________________________________________________________________________ - �Puede una cola, en alg�n momento comportarse como una Pila?�Por
qu�? Mencione al menos un ejemplo:_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Ejercicios
- 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. - 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. - 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. - 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. - 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.
- Escribir un programa en C, que lea cierca cantidad de enteros y luego
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;
}
Cap�tulo XII: Listas Enlazadas
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.
Concepto de Lista Enlazada
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:
Tipos De Listas
- 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.
- Lista simplemente enlazada: Cada nodo, contiene un �nico apuntador
- 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.
- Listas Doblemente enlazada: Esta lista se caracteriza por que sus nodos
- 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
- Listas Circulares: Este tipo de lista, es s�lo una extenci�n
- 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.
- Lista Circular Doblemente enlazada: Quiz� este tipo de lista, sea
Ahora el lector comprende, el por que, si hablamos de estos
t�picos al inicio, a lomejor, hubiera desistido de leer �ste
manual, y es que, al tener la experiencia de haber trabajado con estructuras
como pilas y colas, antes de listas, hace que uno comprenda mucho mejor,
los conceptos y algoritmos de �ste tipo de estructuras.
El TAD Lista
En una lista podemos almacenar datos del mismo tipo, con
la caracter�stica que puede contener un n�mero indeterminado
de elementos y que, mantienen un orden expl�cito, por que cada elemento,
se une a otro mediante un puntero, como ya se ha dicho anteriormente, los
elementos constitutivos de las listas se denominan nodos.
Las listas son estructuras de datos din�micos, por
tanto, pueden cambiar de tama�o durante la ejecuci�n del programa,
aumentando o disminuyendo el n�mero de nodos.
Un aspecto importante de las listas es que las inserciones,
las podemos hacer por el frente, al final, en medio, despu�s de…,
etc, etc, etc; es decir que, no existen reglamentos que nos restringan a�adir
datos a una lista, en la posici�n que nosotros querramos.
De igual manera, para las eliminaciones de nodos, podemos
hacerlo como nosotros lo querramos, si embagargo, se acostumbra ingresando
el campo de informaci�n o dato que se desea eliminar.
Operaciones con las listas
P: puntero a un nodo
L: puntero a la lista
à ListaVacia(L): Iniciliza
la lista L, como lista vac�a
à empty(L): determina
si la lista est� vac�a o no
à Insertar(L, x, p):
Inserta al dato x, en un nuevo nodo de la lista L, despu�s del nodo
apuntado por p
à eliminar(L, x): elimina,
de la lista L, el nodo que contiene a x
à Nodo(p): Hace referencia
la nodo que apunta p
à Info(p): hace referencia
al info del nodo
à next(p): siguiente
direcci�n si p no es NULL
à Info(next(p)): info
del nodo que sigue a nodo (p) en la lista
Se puede decir que, estas son las operaciones b�sicas
para una lista; sin embargo, como ya se ha insistido, eso depender�
del programador y de la complejidad del problema que se est� resolviendo,
adem�s del tipo de lista que se haya elegido.
Para ello, acontinuaci�n hablaremos, por separado,
de cada uno de los tipos de listas.
Listas Simplemente Enlazadas
Una estructura como �sta, requiere, que se tengan
en cuenta, las operaciones b�sicas que, se realizar�n:
Estructura del Nodo
Por ejemplo, la podemos definir as�:
struct nodo{
int x;
struct nodo *sig;
};
typedef struct nodo *Lista; /* Sin�nimo para el
tipo de dato*/
Lista p; /* Aqu� guardaremos la direcci�n
del primer nodo */
p=getnodo();
Funci�n getnodo()
Esta funci�n, se utiliza para pedirle memoria a
la computadora, lo cual puede realizarse en las misma funci�n de
insertar, pero para tener un mekor orden, es mejor hacerlo por aparte.
Por tanto, es evidente que, �sta funci�n
lo que devuelve es una direcci�n de memoria.
Lista getnodo()
{
Lista p;
p=(Lista)malloc(sizeof(struct nodo));
return p;
}
Lo que devuelve, es la direcci�n del nuevo nodo,
que se guard, en la variable p.
Funci�n Insertar despu�s del nodo apuntado
por p
Las inserciones en las Listas, no siempre se hacen al principio
(pila) o al final (como las colas), las listas nos permiten insertar, entre
dos nodos, por ejemplo en una lista, tenemos: B, Q, M, Y D. Y queremos insertar
el elemento E, entre Q y M:
El algoritmo ser�a el siguiente:
- Si P apunta a NULL, mostrar un mensaje de error y terminar la ejecuci�n.
- sino, genere otro puntero, q, en el cual guarde la informaci�n.
- luego, la parte siguiente del nuevo nodo, debe apuntar a al siguiente
nodo, del apuntado por P. - 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�aan”);
Else
{
q=getnode();
q->x=x;
q->sig=p->sig;
p->sig=q;
}
}
Funci�n Borrar despu�s de…
�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:
- Crear un nodo auxiliar apuntado por q.
- si p, apunta a nullo p->sig apunta a NULL, imprima mensaje de error
- sino; q, en suparte de siguiente, debe tener la direcci�n a la
que apuntaba, p->sig. - p->sig debe apuntar a q en su parte de siguiente.
- 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�aan”);
Else
{
q->sig=p->sig;
p->sig=q->sig;
free(q);
}
}
Funci�n de Lista Vac�a
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.
Funci�n Buscar
�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(“ttnMENU PRINCIPALnnn”);
printf(“tt1. Registrar Nuevos Datosn”);
printf(“tt2. Imprime todos los registrosn”);
printf(“tt3. Eliminar Datosn”);
printf(“tt4.Salirn”);
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 registrosnn”);
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 Insuficientean”);
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�ana”);
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(“nt***********************************n”);
printf(“t correlativo: %dn”, dir->corre);
printf(“t Nombre %sn”, dir->nom);
printf(“t Telefono: %sn”, dir->tel);
printf(“t e-mail: %sn”, dir->email);
printf(“nt***********************************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 eliminadon”, indice->nom);
getch();
if(p==NULL || p->sig==NULL)
printf(“ERROR, ya no hay m s datosn”);
else
{
cabeza->sig=indice->sig;
free(indice);
}
}
}
}
Listas Doblemente Enlazadas
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.
Insertar
Para insertar en un lista, existen algunos mecanismos, casos,
formas, etc.
Por ejemplo:
à INSERTAR AL FRENTE DE
LA LISTA
- si lista est� vac�a
- Crear un nuevo nodo
- Asignar el valor a la parte dato del nodo
- Hacer que nuevo nodo, en su parte de anterior apunte a NULL
- Y en su parte de siguiente a la lista
- El puntero del elemento de l frente de la lista, debe apuntar al nuevo
nodo.
- si la lista No est� vac�a
- Agregar un nuevo nodo
- Asignar el valor a la parte dato del nodo
- Hacer que nuevo nodo, en su parte de anterior apunte a NULL
- El nuevo nodo en su parte de siguiente, debe apuntar al primer elemento
de la lista - Si la Lista!=NULL, entonces Lista->ant=p
- Luego el apuntador a la lista (Lista), debe apuntar al nuevo nodo.
- si lista est� vac�a
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:
- Crear el nuevo nodo
- hacer que p->elemento, sea igual al valor
- hacemos que p->ant apunte al ultimo nodo
- p->sig ser� igual a lo que tenga q->sig
- 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;
}
Funci�n getnodo()
tLista getnodo()
{
tLista nuevo;
nuevo=(tLista)malloc(sizeof(Lista));
if(nuevo==NULL)
printf(“Memoria insuficientean”);
nuevo->sig=nuevo->ant=NULL;
return nuevo;
}
Funci�n Eliminar
Esta funci�n, se encarga de borrar, el nodo apuntado
por “p”, encontrado con la funci�n posici�n y considere
eliminaci�n al inicio, en medio y al final.
Algoritmo:
- 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. - la parte siguiente del nodo anterior debe apuntar al puntero sifguiente
del nodo a eliminar. - la parte anterior del nodo siguiente a eliminar debe apuntar a la parte
a lo que apuntaba la parte anterior del nodo a eliminar. - 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. - finalmente liberamos la memoria ocupada.
- Busque el nodo que contiene el dato que desea eliminar , teniendo el cuidado
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 (“nn t *********************************n”);
printf (” t *** ***n”);
printf (” t *** PROGRAMA DE ESTRUCTURAS ***n”);
printf (” t *** ***n”);
printf (” t *********************************n”);
printf (” nnn t 1.- ALTAS n t 2.- BUSQUEDA
n t 3.- LISTADO nt 4.- Baja nt 5.- SALIR nn”);
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 ALTAn “);
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 BUSCARn”);
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 %dn “,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–> %dn”,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 BUSCARn”);
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.
Listas Circulares
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.
Declaraci�n de la estructura
Typedef struct elemento{
Int dato;
Struct nodo*sig;
}nodo;
typedef nodo* lc;
lc *Lista=NULL;
Funci�n getnodo()
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;
}
Funci�n Ingresar
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;
}
Funci�n Eliminar
�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
- Se debe buscar el nodo que contiene el dato que desea eliminar
- luego se debe enlazar el nodo anterior con el siguiente
- 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. - 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 listan”);
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(“tttINGRESE EL NUMERO:nnn”);
while((num[pos++]=getchar())!=’n’);
num[–pos]=”;
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 tresn”);
}
aux=(*Lista);
if(aux->x%2==0)
{
div2=1;
printf(“El numero es divisible entre Dosn”);
}
if(div2==1 && div3==1)
printf(“Tambien es divisible entre 6n”);
getch();
}
Explicaci�n
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.
Listas Circulares Doblemente Enlazadas
�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.
Declaraci�n de la estructura
Typedef struct celda{
Int elemento;
Struct nodo*sig, ant;
}tipocelda;
typedef tipocelda *tPosicion;
typedef tipocelda* tLista;
Funci�n getnodo()
tLista getnodo()
{
tLista L;
L=(tLista)malloc(sizeof(tipocelda));
If(L==NULL)
Printf(“ERROR: Memoria Insuficientean”);
L->sig=L->ant=L;
Return L;
}
Funci�n Insertar
Algoritmo:
- Crear el nuevo nodo
- Guardar el dato en el nuevo nodo
- Hacer que el nuevo nodo, en su parte de siguiente apunte al nodo anterior
(que est� siendo apuntado por p) - Luego copiar en nuevo->ant, lo que hay en p->ant
- hacer que en la parte de siguiente del nodo anterior apuntado por p, contenga
la direcci�n del nuevo nodo - hacer que p->ant apunte anuevo
- 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 insuficientean”);
nuevo->elemento=x;
nuevo->sig=p;
nuevo->ant=p->ant;
p->ant->sig=nuevo;
p->ant=nuevo;
p=nuevo;
}
Funci�n Buscar
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(“nnnn”);
printf(“ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ”);
printf(“ntÛÛ ÛÛ”);
printf(“ntÛÛ PROGRAMA QUE CALCULA LOS VALORES
REPETIDOS EN UNA LISTA ÛÛ”);
printf(“ntÛÛ DOBLEMENTE ENLAZADA ÛÛ”);
printf(“ntÛÛ ÛÛ”);
printf(“ntÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛÛ”);
while(ban==’S’ || ban==’s’)
{
printf(“nnIngrese 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(“ntt�Que desea Hacer?n”);
printf(“tt1.Buscar un valor en la listan”);
printf(“tt2.Salirn”);
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 listann”,
busca,buscar(busca,cabeza, cabeza));
break;
case 2:exit(1);
default:printf(“Error, el comando no es v lidon”);
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(“ERRORn”);
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 Insucienten”);
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(“ttt* %d *n”, p->x);
p=p->adelante;
}while(p!=ptr->adelante);
}
else
{
printf(“No Hay elementos en la Listan”);
}
}
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 Listan”);
}
return k;
}
Cuestionario
- �Qu� son y para que sirven las listas?_______________________________________________________________________________________________________________________________________________________________________________________
- �Cu�l es la diferencia entre una lista circular y una doblemente
enlazada?__________________________________________________________________________________________________________________________________________________________________________________ - Una lista, �Puede comportarse como una cola?_______________________________________________________________________________________________________________________________________________________________________________________
- �Por qu� se afirma que una lista circular, no tiene ni primer y
�ltimo elemento?__________________________________________________________________________________________________________________________________________________________________________________ - La funci�n getnodo() e insertar(), se diferencian en:__________________________________________________________________________________________________________________________
Ejercicios
- En una lista simple, que almacena enteros, mostrar cual es el dato mayor
y cual es el dato menor. - 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) - Se desea guardar cierta cantidad de caracteres en una lista doble, y luego
imprimir los caracteres de izquierda a derecha y viceversa. - 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. - En una lista circular se desean guardar, cadenas de caracteres, y luego
imprimir la cadena de mayor longitud. - 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. - Escribir un programa en C, que apartir de una lista doble circular, ordene
alfab�ticamente, los caracteres contenidos en ella y luego los imprima. - 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. - 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. - 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: D2=(x1-x2)2+(y1-y2)2+(z1-z2)2).
- En una lista simple, que almacena enteros, mostrar cual es el dato mayor
Nota Final
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
Bibliograf�a
-“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.
Br. Manuel Antonio Ortez
 P�gina anterior | Volver al principio del trabajo | P�gina siguiente  |