Estructuras de datos y algoritmos en C/C++: Listas y Colas
Posted: octubre 13th, 2008 | Author: admin | Filed under: Algoritmos, C/C++, Estructuras de datos, Software, TAD | Tags: Estructuras de datos y algoritmos en C/C++: Listas y Co | 2 Comments »Cambiando un poco el objetivo del sitio vamos a investigar un poco sobre las estructuras de datos y algoritmos en C/C++. Para esto vamos a comenzar trabajando con estructuras de datos simples como listas y colas, para luego pasar a estructuras como árboles, árboles binarios de búsqueda, AVLs, Hash y algoritmos complejos.
Para poder seguir los ejemplos les recomiendo utilizar Cygwin si usan Windows para tener todas las herramientas de compilado (g++, archivo make, librerias, etc). Si tienen Linux simplemente instalen los paquetes devel.
Trabajaremos construyendo los tipos abstractos de datos (TADs) que nos permitirán abstraernos de la estructura de punteros y trabajar con operaciones que se encargan de hacer el trabajo sucio =). Esto nos libera de estar revisando detalles de la estructura para poder concentrarnos en como resolver problemas.
Comenzaremos trabajando con las dos estructuras más simples, listas y colas. En las dos estructuras de datos encadenamos elementos en forma simple, la diferencia está en la forma en que una vez que ingresamos los mismos, luego podemos sacarlos. En la lista insertamos en la cabeza y sacamos elementos desde la misma cabeza, este orden es conocido como último en entrar, primero en salir (LIFO siglas en inglés). En el caso de la cola utilizamos el otro orden, primero en entrar primero en salir (FIFO siglas en inglés).
Veamos la definición del tipo de datos para la lista:
typedef struct lista {
int valor;
lista * sig;
};
Con esta definición podemos ir enlazando los nodos de la lista, poniendo en el último el valor NULL en el puntero a sig indicando que termina la lista.
El siguiente paso es definir la lista de operaciones con las cuales vamos a poder trabajar sobre este tipo de datos. Definiremos las siguientes funciones:
lista * ListaCrearVacia();
// Crear una lista de nodos vacia.bool ListaEsVacia(lista * l);
// Devuelve true si la lista es vacia y false en caso contrario.void ListaAgregar (lista *& l, int n);
// Agrega el elemento n al comienzo de la lista.int ListaPrimero(lista * l);
// Devuelve el primer elemento de la lista.lista * ListaResto(lista * l);
// Devuelve un alias al resto de la lista.void ListaDestruir(lista * l);
// Libera la memoria asociada a la lista.
Dadas estas operaciones podremos trabajar sobre el tipo de datos con comodidad, creando, insertando, recorriendo y eliminando la estructura sin necesidad de preocuparnos por los punteros que la componen. Por ejemplo si queremos recorrer una lista que tiene elementos podríamos hacer lo siguiente (debemos verificar que no sea vacia primero):
while (!ListaEsVacia(listaDatos)) {
int valor = ListaPrimero(listaDatos);
printf(«\nDato: %d»,valor);
listaDatos= ListaResto(listaDatos);
}
Noten que deberíamos guardar una copia del puntero inicial de la lista para poder volver a recorrerla o bien poder eliminar la memoria de la misma. Si no tenemos este puntero habremos perdido el comienzo de la lista =P.
Entrando un poco en la construcción del TAD, en el caso de la lista tendremos que insertar el elemento al principio de la misma, mientras que en la cola insertamos al final. Esto nos lleva a ver en el caso de la lista si insertamos al comienzo podremos hacerlo rápidamente aunque la lista sea muy grande. Simplemente modificaremos la cabeza de la lista y pondremos el nuevo dato como comienzo. Veamos un ejemplo:
void ListaAgregar (lista *& l, int n) {
lista* nuevoNodo = new lista;
nuevoNodo->valor = n;
nuevoNodo->sig = l;
l = nuevoNodo;
return;
}
Lo que hacemos es crear el nuevo nodo, asignar el valor de entero y luego encadenamos la lista «vieja» como siguiente elemento del nuevo nodo. Esto nos deja la lista l con el nuevo nodo al comienzo.
La definición de las otras funciones es simple, veamos algunas:
lista * ListaCrearVacia() {
lista* l = NULL;
return l;
}bool ListaEsVacia(lista * l) {
return l == NULL;
}int ListaPrimero(lista * l) {
return l->valor;
}lista * ListaResto(lista * l) {
return l->sig;
}
Pero pensemos por un momento en el caso de la cola, para insertar al final tendremos que ir hasta el final de la misma, por lo cual en caso de que tengamos una gran cantidad de datos tendremos que recorrer muchos nodos. Esto no es bueno, como veremos más adelante buscaremos que nuestras estructuras de datos sean eficientes y sean «más lentas» cuantos más datos tengamos en las mismas. Si nuestra estructura se vuelve más lenta a medida que tenemos más datos sufriremos consecuencias a largo plazo, nuestro programa será cada vez más lento.
Para solucionar este problema lo que haremos será tener un puntero al comienzo y otro al final de la cola, lo cual nos permitirá insertar al final de la misma y acceder al comienzo en forma directa, sin tener que recorrer la misma.
typedef struct cola {
lista * inicio;
lista * fin;
};
Noten que utilizaremos la lista, pero con un nodo especial que nos permita acceder al comienzo y al fin de la misma para remover e insertar respectivamente. Las funciones del TAD nos darán las operaciones que podremos utilizar para trabajar sobre este tipo de datos sin preocuparnos de punteros y demás:
cola * ColaCrearVacia();
// Crea una cola vacia.bool ColaEsVacia(cola * c);
// Devuelve true si la cola es vacia y false en caso contrario.void ColaEncolar (cola * c, int n);
// Agrega el elemento n a la cola.int ColaPrimero(cola * c);
// Devuelve el primer elemento de la cola.void ColaDesencolar(cola * c);
// Elimina el primer elemento de la cola.void ColaDestruir(cola * c);
// Libera la memoria asociada a la cola.
Para estas operaciones utilizaremos prácticamente el mismo código que para la lista, únicamente teniendo cuidado de utilizar los «accesos directos» según el caso que corresponda, para evitar tener que recorrer toda la cola.
En la próxima entrada veremos árboles binarios de búsqueda, los cuales permiten ordenar la información para encontrar en forma más rapida la misma =)
Hola, muy xvr tu pag, pero
hola m perdonaras pero esq necesito un favor….
bueno en fin esq tengo que hacer un inventario q utilice listas colas y pilas y pues necesito saber como pasar un dato de una cola antiga a una nueva,,,,, me ayudarias… bueno hay va el codigo para ver q se puede hacer… gracias
#include «iostream»
#include «stdlib.h»
#include «stdio.h»
#include «string»
#include «conio.h»
using namespace std;
int opc;
typedef struct _nodo{
int identificacion;
char nombre[40];
int cantidad;
int costo;
char fecha[40];
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo; /*prueba siguiente apunta a Null*/
typedef tipoNodo *Lista;
Lista lista=NULL; /*Lista a punta a prueba*/
pNodo p;
//funciones
int listavacia(Lista l);
void Insertar(Lista *l, int pidentificacion , char pnombre[40],int pcantidad, int pcosto, char pfecha[40]);
void Insertar2(Lista *l, int pidentificacion , char pnombre[40],int pcantidad, int pcosto, char pfecha[40]);
void insertarproducto();
void insertarproducto2();
void MostrarLista(Lista l);
void buscar(Lista *lista, int aux);
typedef struct nodo {
int identificacion;
char nombre[40];
int cantidad;
int costo;
char fecha[40];
struct nodo *siguiente;
} tipoNodop;
typedef tipoNodop *pNodop;
typedef tipoNodop *Pila;
Pila pila = NULL;
void Insertar(Pila *p, int pcantidad, int pcosto, char pfecha[40]);
void Insertar2(Pila *p, int pcantidad, int pcosto, char pfecha[40]);
int pilavacia(Pila p);
void Mostrarpila(Pila p);
int main()
{
int op,pcodigo,n,aux;
int dato,pago;
do{
op=0;
system(«cls»);
cout<<«\t\tMENU»<<endl;
cout<<«\t2.Comprar PRODUCTO»<<endl;
cout<<«\t3.mostrar informe PRODUCTO»<<endl;
cout<<«\t2.MOSTRAR INFORME»<<endl;
cout<<«\t4.mostrar pila»<<endl;
cout<>op;
system(«cls»);
switch(op){
case 1:
cout<<«\t\t____________________________________»<<endl;
cout<<«\t\t\tCREAR PRODUCTO»<<endl;
cout<<«\t\t____________________________________»<<endl;
insertarproducto();
break;
case 2:
cout<<«\t\t\tCOMPRAR PRODUCTO»<<endl;
cout<>aux;
buscar(&lista,aux);
insertarproducto2();
break;
break;
case 3:
cout<<«\t\t\t MOSTRAR INFORME»<<endl;
MostrarLista(lista);
break;
case 4:
cout<<«GRACIAS POR UTILIZAR NUESTROS SERVICIOS»<<endl;
Mostrarpila(pila);
system(«pause»);
break;
}
}while(op!=5);
system(«cls»);
getch();
}
void insertarproducto(){
int aidentificacion;
char anombre[40];
int acantidad;
char afecha[40];
int acosto;
cout<>aidentificacion;
cout<>anombre;
cout<>acantidad;
cout<>afecha;
cout<>acosto;
Insertar(&lista, aidentificacion,anombre,acantidad,acosto,afecha);
}
void Insertar(Lista *lista, int pidentificacion, char pnombre[40], int pcantidad,int pcosto, char pfecha[40]){
pNodo nuevo, anterior;
//crear un nuevo nodo
nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo->identificacion = pidentificacion;
strcpy(nuevo->nombre,pnombre);
nuevo->cantidad=pcantidad;
strcpy(nuevo->fecha,pfecha);
nuevo->costo = pcosto;
/*si lista esta vacia*/
if(listavacia(*lista) || (*lista)->identificacion>pidentificacion){
/*añadimos el nuevo nodo*/
nuevo->siguiente = *lista;
/*ahora el comienzo de nuestra lista es un nuevo nodo*/
*lista = nuevo;
}
else {
anterior = *lista;
while(anterior->siguiente && anterior->siguiente->identificacion siguiente;
nuevo->siguiente = anterior->siguiente;
anterior->siguiente = nuevo;
}
}
void insertarproducto2(){
char anombre[40];
int aidentificacion;
int acantidad;
char afecha[40];
int acosto;
cout<>acantidad;
cout<>afecha;
cout<>acosto;
Insertar(&lista, aidentificacion,anombre,acantidad,acosto,afecha);
}
void Insertar2(Lista *lista, int pidentificacion, char pnombre[40], int pcantidad,int pcosto, char pfecha[40]){
pNodo nuevo, anterior;
//crear un nuevo nodo
nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo->identificacion = pidentificacion;
strcpy(nuevo->nombre,pnombre);
nuevo->cantidad=pcantidad;
strcpy(nuevo->fecha,pfecha);
nuevo->costo = pcosto;
/*si lista esta vacia*/
if(listavacia(*lista) || (*lista)->identificacion>pidentificacion){
/*añadimos el nuevo nodo*/
nuevo->siguiente = *lista;
/*ahora el comienzo de nuestra lista es un nuevo nodo*/
*lista = nuevo;
}
else {
anterior = *lista;
while(anterior->siguiente && anterior->siguiente->identificacion siguiente;
nuevo->siguiente = anterior->siguiente;
anterior->siguiente = nuevo;
}
}
int listavacia(Lista lista) {
return (lista == NULL);
}
void MostrarLista(Lista lista) {
int pago;
pNodo nodo = lista;
if(listavacia(lista)) cout<<«Lista vacía \n»;
else {
while(nodo) {
cout<<«\tCodigo\tNombre\tfecha\tCantidad\tprecio»<<endl;
cout<<«\t «<identificacion<<«\t «<nombre<<«\t «<cantidad<<«\t «<fecha<<«\t\t «<costo<<endl;
cout<siguiente;
}
cout<identificacion siguiente;
}
if(!nodo || nodo->identificacion !=aux){
cout<<«\tNO HAY COINCIDENCIAS»<<endl;
cout<<«\tO ES POSIBLE QUE NO HAYA DATOS»<<endl;
}
else{
cout<<«\tNOMBRE DE EL PRODUCTO:»<nombre<cantidad=pcantidad;
nuevo->costo = pcosto;
strcpy(nuevo->fecha,pfecha);
/*si lista esta vacia*/
if(pilavacia(*p) || (*p)->cantidad>pcantidad){
/*añadimos el nuevo nodo*/
nuevo->siguiente = *p;
/*ahora el comienzo de nuestra lista es un nuevo nodo*/
*p = nuevo;
}
else {
anterior = *p;
while(anterior->siguiente && anterior->siguiente->cantidad siguiente;
nuevo->siguiente = anterior->siguiente;
anterior->siguiente = nuevo;
}
}
void Mostrarpila(Pila p) {
pNodop nodo = p;
if(pilavacia(p)) cout<<«Lista vacía \n»;
else {
while(nodo) {
cout<<«\tDIRRECCION DEL ESTUDIANTE: «<cantidad<<endl;
cout<<«\tTELEFONO DEL ESTUDIANTE: «<fecha<<endl;
cout<<«\tCARRERA DEL ESTUDIANTE: «<costo<<endl;
cout<siguiente;
system(«pause»);
}
cout<<«\n»;
system(«pause»);
}
}