Unidad_6_-_Cola_-_Lista

Vista previa del material en texto

UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 1 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
6.1. Implementación de Colas 
 
Es una estructura de datos especial en donde la inserción se realiza por el frente y 
el borrado de los nuevos elementos se realiza por fondo de la estructura. Esta estructura 
posee numerosas analogías en la vida real, por ejemplo la cola que se realiza en un 
banco, en un supermercado, en una estación de servicio. 
 
 Dado que las operaciones de insertar y eliminar se realizan por distintos extremos 
(frente y fondo) en esta estructura se deben manejar dos punteros. El primer elemento 
que se pone en la cola es el primero en sacar y está apuntado por frente, el último 
elemento está apuntado por fondo. 
 
A esta estructura se la conoce con el nombre de FIFO (First Input First Output). 
 
 Las operaciones que se pueden realizar con una cola son: 
 INICIALIZAR (frente, fondo): Crea la estructura de cola asignando el valor NULL a 
ambos punteros. 
 INSERTAR (frente, fondo, elemento): Introduce un elemento en la cola. 
 ELIMINAR (frente, fondo): Elimina un elemento de la cola. 
 RECORRER (frente): Permite recorrer la estructura de cola para ver o trabajar con 
sus elementos. 
 
 
 
 
/*CREA UNA COLA CON ESTRUCTURA DINAMICA Y ALMACENAR RN LA MISMA NUMEROS 
ENTEROS*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
 
struct nodo 
{ 
 int info; 
 nodo *sig; 
}; 
 
void inicializar(nodo *&frente,nodo *&fondo); 
void insertar(nodo *&frente,nodo *&fondo, int x); 
int borrar(nodo *&frente,nodo *&fondo); 
void recorrer(nodo *frente); 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 2 
 
 
main() 
{ 
 nodo *frente,*fondo; 
 int i,x; 
 
 inicializar(frente,fondo); 
 
 for (i=0;i<3;i++) 
 { 
 printf("Ingrese el valor de x: "); 
 scanf("%d",&x); 
 insertar(frente,fondo,x); 
 } 
 
 printf("\n\nSE BORRA EL VALOR: %d\n\n",borrar(frente,fondo)); 
 getch(); 
 
 recorrer(frente); 
 getch(); 
} 
 
 
void inicializar(nodo *&frente,nodo *&fondo) 
{ 
 frente=NULL;fondo=NULL; 
} 
 
void insertar(nodo *&frente, nodo *&fondo,int x) 
{ 
 nodo *p; 
 p=new nodo; 
 if (p!=NULL) 
 { 
 p->info=x; 
 p->sig=NULL; 
 if (frente==NULL) 
 frente=p; 
 else 
 fondo->sig=p; 
 fondo=p; 
 } 
 else 
 printf("ERROR - COLA LLENA"); 
} 
 
int borrar(nodo *&frente,nodo *&fondo) 
{ 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 3 
 
 if (frente!=NULL) 
 { nodo *p; int x; 
 p=frente; 
 x=frente->info; 
 frente=frente->sig; 
 delete p; 
 if (frente==NULL) 
 fondo=NULL; 
 return x; 
 } 
 else 
 { 
 printf("ERROR - COLA VACIA"); 
 return 0; 
 } 
} 
 
void recorrer(nodo *frente) 
{ 
 nodo *p; 
 
 p=frente; 
 while (p!=NULL) 
 { 
 printf("%d\n",p->info); 
 p=p->sig; 
 } 
 getch(); 
} 
 
 
6.2. Implementación de Listas Simples Encadenadas Ordenadas 
 
Es una estructura de datos que no posee restricciones para la inserción o 
eliminación de elementos. 
 
 Dado que las operaciones de insertar y eliminar se pueden realizar en frente, en el 
medio o al final de la estructura, manejando un solo puntero, siendo las inserciones de tal 
forma que los nodos vayan quedando ordenados de acuerdo a su información. 
 
Las operaciones que se pueden realizar con una lista son: 
 INICIALIZAR (frente): Crea la estructura de lista asignando el valor NULL al 
puntero. 
 INSERTAR (frente, elemento): Introduce un elemento en la lista. 
 ELIMINAR (frente): Elimina un elemento de la lista. 
 RECORRER (frente): Permite recorrer la estructura de lista para ver o trabajar con 
sus elementos. 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 4 
 
 
 
/*CREA UNA LISTA SIMPLE ORDENADA CON ESTRUCTURA DINAMICA Y ALMACENAR RN LA MISMA 
NUMEROS ENTEROS*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
 
struct nodo 
{ 
 int info; 
 nodo *sig; 
}; 
 
void inicializar(nodo *&frente) 
{ 
 frente=NULL; 
} 
 
void insertar(nodo *&frente, int x) 
{ 
 nodo *act, *p, *ant; 
 p=new nodo; 
 act=frente; 
 ant=frente; 
 if (p!=NULL) 
 { 
 p->info=x; 
 while ((act!=NULL) && (act->info < p->info)) 
 { 
 ant=act; 
 act=act->sig; 
 } 
 if (act!=ant) 
 { 
 if (act!=NULL) 
 { printf("Nodo intermedio:\n"); 
 p->sig=ant->sig; 
 ant->sig=p; 
 } 
 else 
 { 
 printf("Ultimo nodo:\n "); 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 5 
 
 p->sig=NULL; 
 ant->sig=p; 
 } 
 } 
 else 
 { 
 printf("Primer nodo:\n"); 
 p->sig=frente; 
 frente=p; 
 } 
 } 
 else 
 printf("Error fatal en el HEAP no se puede insertar un nodo"); 
 getch(); 
 } 
 
void eliminar(nodo *&frente) 
{ 
 int buscar; 
 nodo *act, *ant; 
 
 if (frente!=NULL) 
 { 
 printf("Introducir el numero a eliminar:\n"); 
 scanf("%d", &buscar); 
 act=frente; 
 ant=frente; 
 while ((act!=NULL) && (act->info < buscar)) 
 { 
 ant=act; 
 act=act->sig; 
 } 
 if ((act!=NULL) && (act->info == buscar)) 
 { 
 if (ant!=act) 
 { 
 //elimina nodo del medio o el del final 
 ant->sig=act->sig; 
 } 
 else 
 { //elimina el primer nodo 
 frente=act->sig; 
 } 
 delete(act); 
 printf("\nNodo eliminado\n"); 
 } 
 else 
 printf("\nNo existe un nodo con ese numero\n\n"); 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 6 
 
 } 
 else printf("LISTA VACIA"); 
 } 
 
void recorrer(nodo *frente) 
{ 
 nodo *p; 
 p=frente; 
 while (p != NULL) 
 { 
 printf("%d\n",p->info); 
 p=p->sig; 
 } 
} 
 
main() 
{ 
 nodo *frente; 
 int i,x; 
 
 inicializar(frente); 
 
 for (i=0;i<3;i++) 
 { 
 printf("Introducir numero:\n"); 
 scanf("%d", &x); 
 insertar(frente,x); 
 } 
 
 recorrer(frente); 
 
 eliminar(frente); 
 
 recorrer(frente); 
 getch(); 
}