Colas En C 2d5n2h

<string.h> <stdlib.h>

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <stdio.h> struct datos { int dato; datos *s; }*p,*aux,*u; void insertar (int dat); void borrar (); void listar (); main() { int opc,y; do { cout<<"\n1. Insertar"; cout<<"\t2. Borrar"; cout<<"\t3. Listar"; cout<<"\t4. Salir"; cout<<"\n Ingrese opcion: ";cin>>opc; switch(opc) { case 1: cout<<"Ingrese dato: "; cin>>y; insertar(y); cout<<"\nDato insertado!!"; break; case 2: borrar(); break; case 3: listar(); break; case 4: exit(1); default: cout<<"\n Opcion no valida!!"; break; } }while(opc); } void insertar (int dat) { aux=new(datos); aux->dato=dat; if(u) { u->s=aux; aux->s=NULL; u=aux; } else { p=u=aux; } } void borrar() { if(p) {

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

aux=p; cout<<"\nElimino a " < dato; p=aux->s; delete(aux); } else { cout<<"\n No hay datos"; } } void listar() { int i; if(!u) { cout<<"\n No hay datos en la cola"; return; } aux=p; while(aux) { cout<<"\n"<<++i<<" - "< dato; aux=aux->s; } }

Hola amigos, Resulta que tengo que hacer esto: Cita:

Escriba un programa para ejecutar el experimento siguiente: Genere 100 números aleatorios con valores en el rango entre 1 y 500. Conforme se genera cada número, insértelo en una cola inicialmente vacía. Si el número es de dos dígitos, tiene prioridad sobre números de tres dígitos. Después de insertar los 100 números, imprima en orden secuencial las posiciones de la cola donde se encuentra el número con mayor valor y el número con menor valor. Nunca hemos trabajado usando Colas, no entiendo cómo uno puede aprender de esta manera pero bueno, venga... He investigado cómo crear una Cola y crear los números aleatorios. Código: Código: #include #include <stdlib.h> #include

// Librería para usar la función srand() // Librería para usar la función time()

using namespace std; //Declaraciones de tipos para manejar colas en C++ typedef struct _nodo { int dato; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Cola; int main() { //Declaración de variables int i, Numero; srand(time(NULL)); //Procesamiento for(i = 1; i <= 100; i++) { Numero = 1 + rand() % (501 - 1); cout << Numero << endl; } return 0; }

…………………………………….

Problemas Resueltos de Punteros

1.- ENCUENTRA LOS ERRORES EN LA SIGUIENTE DECLARACIÓN DE PUNTEROS: Int x, *p, &y; Char* b= “cadena larga” ; Char* c= ‘C’ ; Float x; Void* r= &x; Es incorrecta sintácticamente al declaración int &y. no tiene ningún sentido en C. Cuando un carácter esta rodeado por comillas simples es considerado como una constante de tipo char no como una cadena, para lo cual debería estar rodeado de dobles comillas. Char* c= “C”; No se puede declarar un puntero a tipo void. 2.- DADA LA SIGUENTE DECLARACIÓN ESCRIBIR UNA FUNCIÓN QUE TENGA COMO ARGUMENTO UN PUNTERO AL TIPO DE DATO Y MUESTRE POR PANTALLA LOS CAMPOS. Struct botón { Char * rotulo; Int código; }; La función puede ser la siguiente

Void mostrarboton (struct botón *pb) { Printf (“rotulo del boton : %s \n” , pb ->rotulo ) ; Printf (“Codigo asociado al botón : %d\n” , pb->código ) ; } 3.- EN EL SIGUIENTE CÓDIGO SE ACCEDE A LOS ELEMENTOS DE UNA MATRIZ. ACCEDER A LOS MISMOS ELEMENTOS CON ARITMÉTICA DE PUNTEROS. #define N 4 #define N 5 Int f . c ; Double mt [N] [M] ; For ( f = 0; f
{ For ( c = 0 ; c<M; c++ ) Printf (“\n”) ; } Otra opción podría haber sido hacer que el puntero recorra la matriz sabiendo que la matriz esta almacenada en memoria fila a fila de forma lineal. #define N 4 #define M 5 Int f.c ; Doublé mt [N] [M] , *pmt=mt ; For ( f = 0 ; f
5.- DADAS LAS SIGUIENTES DECLARACIONES DE ESTRUCTURAS, ESCRIBE COMO ACCEDER AL CAMPO X DE LA VARIABLE ESTRUCTURA T. Struct fecha { Int d, m, a; Float x; }; Struct dato { Char* mes; Struct fecha* f; } t; Análisis del problema La variable t es una variable de tipo estructura, por lo que se usa el operador punto para acceder al miembro f. desde el dato miembro f es necesario usar el operador flecha para acceder al campo x de la estructura fecha a la que apunta. t.f -> x ; que problema habría en la siguiente sentencia gets (t. mes) ; El campo mes de la estructura fecha no apunta a ningún sitio , por lo cual dará problemas de asignación de memoria cuando la función gets ( ) intente colocar el resultado en el puntero que se le pasa como argumento. Para evitar esto sería necesario reservar memoria antes de llamar a gets ( ). Problemas Resueltos de Listas

1.- Escriba una función que devuelva cierto si la lista esta vacía y falso en otros caso, y otra que cree una lista vacía. Codificación Si se supone siguiente declaración: Typedef int Item; Typedef struct Registro { Item el; Struct Registro* sig;

} Nodo; La codificacion de la funcion Esvacia sera: Int Esvacia (Nodo _* Primero) { Return (Primero == NULL); } La codificacion de la funcion VaciaL sera: Void VaciaL (Nodo ** Primero) { *Primero == NULL; } 2.- Escriba una función entera que devuelva el numero de nodos de una lista enlazada. Codificación Si se supone la declaración de problema anterior se tiene: Int NumerNodos (Nodo *Primero) { Int k = 0; Nodo *p; P = Primero; While (p ¡= NULL) { K++; P = p->sig; } Return(k); } 3.- Escriba una función que elimine el nodo que ocupa la posición i de una lista enlazada ordenada Análisis del problema Para resolver el problema se necesita recorrer la lista contando el número de elementos que van pasando, y corte el recorrido, cuando la lista este vacía, o cuando se haya llegado a la posición que se busca. Una vez terminado el primer bucle de búsqueda en el caso de que haya que eliminar el elemento, se borra teniendo en cuenta si es o no el primer elemento de acuerdo con lo indicado en la teoría.

Codificación Si se supone la declaración realizada en el problema se tiene: Void EliminaPosicion (Nodo** Primero, Int i) { Int k = 0; Nodo *ptr, *ant; Ptr = *Primero; Ant = NULL: While ( (k < i) && (ptr != NULL)) { K++; Ant = ptr; Ptr = ptr->sig; } If(k == i) { If( ant == NULL) *Primero = ptr->sig; Else Ant->sig = ptr->sig; Free(ptr); } } 4.- Escriba una función que reciba como parámetro una lista enlazada apuntada por Primero, un dato cualquiera e inserte en la lista enlazada un nuevo nodo con la información almacenada en dato y de tal forma que sea el primer elemento de la lista. Análisis del problema Los pasos que se seguirán son: asignar memoria a un nuevo puntero nuevo; situar el nuevo dato en el campo el; mover el campo sig de nuevo puntero nuevo al puntero Primero y hacer que Primero apunte a nuevo. Esta función trabaja correctamente, aun cuando la lista este vacía, siempre que previamente se haya iniciado a NULL Codificación Si se supone la siguiente declaración: Typedef int Item; Typedef struct Registro {

Item el; Struct Registro * sig; } Nodo; La codificacion de la function sera: Void InsertarprimeroLista (Nodo** Primero, Item dato) { Nodo *nuevo; Nuevo = (Nodo*) malloc (sizeof(Nodo)); Nuevo -> el = dato; Nuevo -> sig = *Primero; *Primero = nuevo; } 5.- Escriba una función que reciba como parámetro un puntero ant que apunte a un nodo de una lista enlazada e inserte el valor recibido en el parámetro dato como un nuevo nodo que este inmediatamente después de ant (Inserción en el centro y final de una lista). Análisis del problema Se crea un nuevo nodo apuntado por nuevo, donde se almacena el dato, para posteriormente poner como siguiente del nuevo nodo nuevo el siguiente de ant, para por ultimo enlazar el siguiente de ant con nuevo. Codificación Si se supone la siguiente declaración: Typedef int Item; Typedef struct Registro { Item el; Struct Registro* sig; } Nodo; La codificación de la función será: Void InsertarLista (Nodo* ant, Item dato) { Nodo *nuevo; Nuevo = (Nodo*) malloc (sizeof(Nodo)); Nuevo -> el = dato; Nuevo -> sig = ant -> sig; Ant -> sig = nuevo;

}

Problemas Resueltos de Pila

1.- Escriba las primitivas de gestión de una pila implementada con un array. Análisis del problema Se define en primer lugar una constante MaxTamaPila de valor 100 valor máximo de los elementos que podrá contener la pila. Se define la pila como una estructura cuyos campos () serán el puntero cima que apuntara siempre al ultimo elemento añadido a la pila y un array A cuyos índices variaran entre 0 y MaxTamaPila-1. Posteriormente se implementan las primitivas • VaciaP. Crea la pila vacía poniendo la cima en el valor -1. • EsvaciaP. Decide si la pila esta vacia. En este caso ocurrira cuando su cima valga -1. • EstallenaP. Si bien no es una primitiva basica de gestion de una pila; la implementacion se realiza con un array conviene disponer de ella para prevenir posibles errores. En este caso la pila estara llena cuando la cima apunte al valor MazTamaPila-º. • AnadeP. Añade un elemento a la pila. Para hacerlo comprueba en primer lugar que la pila no este ellena, y en caso afirmativo. Incrementa la cima en unidad, para posteriormente poner en el array A en la posicion cima el elemento. • PrimeroP. Comprueba que la pila no este vacía, y en caso de que asi sea, dara el elemento del array A almacenado en la posición apuntada por la cima. • BorrarP. Se encarga de eliminar el último elemento que entro en la pila. En primer lugar comprueba que la pila no este vacia cuyo caso, disminuye la cima en una unidad. • Pop. Esta operación extrae el primer elemento de la pila y lo borra. Puede ser implementada directamente, o bien llamando a las primitivas PrimeroP y posteriormente a BorrarP. • Push. Esta primitiva coincide con AnadeP. Codificación Typedef int TipoDato; /* archivo pilaarray.h */ #include <stdio.h> #include <stdlib.h> #define MaxTamaPila 100 Typedef struct { TipoDato A[MaxTamaPila]; Int cima; }Pila;

Void VaciaP(Pila* P); Void AnadeP(Pila* P,TipoDato elemento); Void BorrarP(Pila* P); TipoDato Primero(Pila P); Int EsVaciaP(Pila P); Int EstallenaP(Pila P); Void Pop(Pila* P. TipoDato elemento); TipoDato Push(Pila *P); Void VaciaP(Pila* P) { P -> cima = -1; } Void AnadeP(Pila* P,TipoDato elemento) { If (EstallenaP(*P)) { Puts(“Desbordamiento pila”); Exit (1); } P->cima++; p->A[P->cima] = elemento; } Void Pop(Pila* P,TipoDato elemento) { AnadeP(P, elemento); } TipoDato Push(Pila *P) { TipoDato Aux; If (EsVaciaP(*P)) { Puts(“Se intenta sacar un elemento en pila vacia”); Exit (1); } Aux = P->A[P->cima]; P->cima-; Return Aux; } TipoDato PrimeroP(Pila P) { TipoDato Aux; If (EsVaciaP(P))

{ Puts(“Se intenta sacar un elemento en pila vacia”); Exit (1); } P->cima --; } Int EsVaciaP(Pila P) { Return P,cima == -º; } Int EstallenaP(Pila P) { Return P,cima == MaxTamaPila-1; } 2.- Escribir un programa que usando las primitivas de gestion de una pila, lea datos de la entrada (-1 fin de datos) los almacene en una pila y posteriormente visualice dicha la pila. Analisis del problema Si se supone que el archivo pilaarray.p contiene todas las primitivas de gestion de una pila, para resolver el problema bastara declarar TipoDato como un entero incluir el archivo pilaarray.p anterior, y mediante un programa principal en un primer bucle while se leen dato y se almacenan en una pila, para posteriormente en otro bucle extraer datos de la pila y presentarlos en pantalla. Codificación Typedef char TipoDato #Include Void main() { Pila P; Int X; VaciaP(&P); Do { Printf(“dame dato -1=fin \n”); Scanf(“%d”,&x); If (x != -1) AnadeP(&P, x); While (x != -1); } Printf(“escritura de la pila\n”);

While(¡EsVaciaP(P)) { Printf(“%d \n”,PrimeroP(P)); BorrarP( &P); } } 3.- escriba las primitivas de gestión de una pila implementada con una lista simple enlazada. Análisis del problema Se define como una lista simplemente enlazada. Posteriormente se implementan las primitivas: • VaciaP. Crea la pila vacia poniendo la pila P a NULL. • EsvaciaP. Decide si pila vacia. Esto ocurrira cuando P valga NULL. • AnadeP. Añade un elemento a la pila. Para hacerlo, lo unico que se debe hacer, es añadir un nuevo nodo que contenga como informacion el elemento que se quiera añadir y ponerlo como primero de la lista enlazada. • PrimeroP. En primer lugar se comprobara que la pila (lista) no este vacia, y en caso de que asi sea dara el campo el almacenado en el primer nodo de la lista enlazada. • BorrarP. Se encarga de eliminar el ultimo elemento que entro en la pila. En primer lugar se comprueba que la pila no este vacia en cuyo caso, se borra el primer nodo de la pila (lista enlazada). • Pop. Esta operación extrae el primer elemento de la pila y lo borra. Puede ser implementada directamente, o bien llamando a las primitivas PrimeroP y posteriormente a BorrarP. • Push. Esta primitiva coincide con AnadeP. • NuevoNodo. Es una función auxiliar de la implementación que se encarga de reserva de reservar memeoria para la operación AnadeP. • EstallenaP. En esta implementación no tiene ningún sentido, ya que se supone que la memoria dinámica es en principio inagotable. Codificación #include <stdio.h> #include <stdlib.h> Typedef int TipoDato; Typedef struct unnodo { TipoDato el; Struct unnodo *sig; }Nodo; Typedef Nodo Pila;

Nodo* NuevoNovo(TipoDato element); Void VaciaP(Pila** P); Void AnadeP(Pila** P,TipoDato element); Void BorrarP(Pila** P); TipoDato PrimeroP(Pila *P); Int EsVaciaP(Pila *P); Void Pop(Pila** P,TipoDato elemento); TipoDato Push(Pila **P); Nodo* NuevoNodo(TipoDato elemento) { Nodo *a; A = (Nodo*)malloc(sizeof(Nodo)); A -> el = elemento; A -> sig = NULL; Return a; } Void VaciaP(Pila** P) { *P = nn; } Void AnadeP(Pila** P, TipoDato elemento) { Nodo * nn; Nn = NuevoNodo(elemento); nn->sig = (*P); *P = nn; } TipoDato Pop(Pila** P, TipoDato elemento) { AnadeP(P, elemento); } TipoDato Push(Pila **P) { TipoDato Aux; Pila *nn; If (EsVaciaP(*P)); { Puts(“Se intenta sacar un elemento en pila vacia”); Exit (1); }

Aux = (*P)->el; Nn = *P; *P = nn->sig; Free(nn); Return Aux; } TipoDato PrimeroP(Pila *P) { TipoDato Aux; If (EsVaciaP(P)) { Puts(“Se intenta sacar un elemento en pila vacia”); Exit (1); } Nn =(*P); (*P)= nn->sig; Free(nn); } Int EsVaciaP(Pila *P) { Return P == NULL; } 4.- Usando las primitivas de gestión de una pila de enteros escriba las siguientes funciones: EscribePila que recibe como parámetro una pila y la escribe. CopiadPila que coia una pila en otra. DaVueltaPila que da la vuelta a una pila. Análisis del problema Usando el archivo pilalista.p en el que se tiene ya la implementacion de las primitivas de una pila, lo unico que se debe hacer es implementar las siguientes funciones: • EscribePila que recibe como parametro por valor una pila y mediante un bucle while, se van extrayendo, borrando y escribiendo los elementos de la pila. • CopiaPila que recibe como parametro por valor una pila p y devuelve en Pcop una copia exacta de la pila P. Par ello basta con volcar la pila P en una pila Paux auxiliar, para posteriormente volcar la pila Paux en la pila Pcop. • DaVueltaPila que recibe como parametro por valor la pila P y vuelva su contenido en la pila Pcop. Codificación Void CopiaPila (Pila *P, Pila**Pcop) {

Pila *Paux; TipoDato e; VaciaP(&Paux); While (! EsVaciaP(P)) { E = PrimeroP(P); BorrarP(&P); AnadeP(&Paux,e); } VaciaP(Pcop); While (! EsVaciaP(Paux); { E = PrimeroP(Paux)) BorrarP(&Paux); AnadeP(Pcop,e); } } Void DaVueltaPila (Pila *P, Pila**Pcop) { TipoDato e; VaciaP(Pcop); While (!EsVaciaP(P)) { E = PrimeroP(p); BorrarP(&P); AnadeP(Pcop,e); } } Void EscribePila(Pila *P) { TipoDato e; While (! EsVaciaP(P)) { E = PrimeroP(P); BorrarP(&P); Printf(“%d\n”, e); } } 5.- Escriba las funciones LiberarPila y SonIgualesPilas que respectivamente libera todos los nodos de una pila implementada con lista y decide si dos pilas son iguales.

Análisis del problema Al igual que en el ejercicio anterior se usa pilalista.p en el que se tiene ya la implementacion de las primitivas de una pila, lo unico que resta por hacer es implementar las siguientes funciones: • LiberarPila que mediante un bucle mientras se encarga de ir extrayendo los elementos de la pila y mediante la funcion BorrarP irlos eliminando. • SonIgualesPilas. Dos pilas son iguales si tienen el mismo numero de elementos y ademas coinciden en el orden de colocacion. Por lo tanto basta con un bucle mientras, controlado por haber datos en las dos pilas y haber sido todos los elementos extraido anteriormente iguale, extraer un elemento de cada una de las pilas y seguir decidiendo sobre su igualdad. Al final del bucle debe ocurrir que las dos pilas esten vacias y ademas que las variable logica que controla el bucle sea verdadera. Codificación Void LiberarPila(Pila**P) { While (!EsVaciaP(*P)) BorrarP(P); } Int SonIgualesPilas(Pila *P, Pila* P1) { Int sw = 1; TipoDato e,e1; While (! EsVaciaP(P) && !EsVaciaP(P1) && sw) { E = PrimeroP(P); BorrarP(&P); El = PrimeroP(P1); BorrarP(&P1); Sw = (e == el); } Return (sw && EsVaciaP(P)&& EsVaciaP(P1)); }

Problemas Resueltos de Colas

1.- Escriba las declaraciones necesarias y las primitivas de gestión de una cola implementada con listas enlazadas Análisis del problema

Se declaran en primer lugar todos los tipos de datos necesarios para una lista enlazada. Una cola será una estructura con dos punteros a la lista frente que apuntara al primer elemento de la cola y final que apuntara al último elemento. • VaciarC. Crea una cola vacia, para lo cual basta con poner en frente y el final a null. • EsvaciaC. Decide si la cola esta vacía. Es decir si frente y final valen null • EstallenaC. Esta función no es ahora necesaria ya que teóricamente no hay límite. • PrimeroC. Extrae el primer elemento de la cola que se encuentra en el nodo frente. Previamente a esta operación ha de comprobarse que la cola no este vacia. • AñadeC. Añade un elemento a la cola.este elemento se añade en un nuevo nodo que será el siguiente de final en el caso de que la cola no este vacia. Si la cola esta vacia el frente debe apuntar a este nuevo nodo. En todo caso el final siempre debe moverse al nuevo nodo. • BorrarC. Elimina el primer elemento de la cola. Para hacer esta operación la cola no debe estar vacia. El borrado se realiza avanzando frente al nodo siguiente y liberando la memoria correspondiente . • EliminarC. Esta primitiva libera toda la memoria que tenga una cola ya creada. Se realiza mediante un bucle controlado por el final de la lista. Liberando la memoria ocupada por cada nodo en cada una de las interacciones del bucle. Codificación #include<stdio.h> #include<stdlib.h> Typedef int tipodato; Struct nodo { Tipodato el; Struct nodo* sig; }; Typedef struct } Nodo* frente; Nodo * final; }cola; Void vaciaC(cola* C); Void añadeC(cola* C. tipodato el); Void eliminarC(cola*C); Void borrarC(cola* C); Tipodato primeroC (cola C); Int esvaciaC(cola C); Nodo* crearnodo(tipodato el); Void vaciarC(cola* C) { C->frente = null;

C->final = null; } Nodo*crearnodo(tipodato el) { Nodo* nn; Nn = (nodo*) malloc(sizeof(nodo)); nn->el = el; nn->sig = null; return nn;} int esvaciaC(Cola C) return (C.frente == null); } Voyd añadeC(cola* C,tipodato el) { Nodo* a; A = crearnodo(el); If (esvaciaC(*C)) C->frente = a; Else C->final->sig = a; C->final = a; } Void borrarC(cola*C) { Nodo *a; If (esvaciaC(*C)) { A = C->frente; C->frente = C->frente->sig; If(C->frente == null) C->final ==null; Free(a); } Else { Puts(“error eliminacion de una cola vacia”); Exit(-1); } } Topodato primeroC(cola C) { If (esvaciaC(C)) { Puts(“error: cola vacia”); Exit(-1); } Return (C.frente->el);

} Void eliminaC(Cola* C) { For (;C->frente;) { Nodo* n; N =C->frente; C->frente = C->frente->sig; Free(n); } } 2.- Escriba una función que tenga como argumento dos colas del mismo tipo. Devuelva cierto si las dos colas son idénticas Análisis del problema Se usan para resolver el problema las primitivas de gestión de colas implementando una función son igualescolas que dará el valor verdadero cuando las dos colas tengan igual numero de elementos y además estén colocada en el mismo orden. Codificación Int sonigualescolas(cola* C. cola* C1) { Int sw=1; Tipodato e,el; While(esvaciaC(C)&& esvaciaC(C1)&& sw) { E =primeroC(C); borrarC(&C); el =primeroC(C1); borrarP(&C1); sw =(e ==el); } Return (sw && esvaciaC(C)&& esvaciaC(C1)); }

3.- Escriba una función que reciba como parámetro una cola de números enteros y nos devuelva el mayor y el menor de la cola. Análisis del problema Se usan las primitivas de gestión de colas implementadas con listas, lo único que hay que hacer es inicializar mayor y menor al primer elemento de la cola, y mediante en bucle voraz controlado por si se vacía la cola, ir actualizando las

variables mayor y menor. Codificación Void mayormenor(cola*C.tipodato *mayor. Tipodato *menor) { Tipodato M.m.e; M=-32767; m =32367; while(esvadciaC(*C)) { E=primeroC(*C); borrarC(C); if(m<e) m=e; if(m>e) M=e; } *Mayor=M; *mrnor=m; }

4.- Problema de colas • Estallenac. Decide si la cola esta llena. Es decir, si (final+1)%maxtamc==frente. • Primeroc. Extrae el primer elemento de la cola que se encuentra en (frente+1) maxtamc. Previamente a esta operación a de comprobarse que la cola no este vacia. • Añadec. Añade un elemento a la cola. Este elemento se añade a la posición del array (final+1) %maxtamc. Final también debe ponerse en esa posición. Previamente a esta operación a de comprobarse si la cola esta llena. • Borrarc. Elimina el primer elemento de la cola. Para ello basta con hacer frente=(frente+1) %maxtamc. Previamente a esta operación ha de comprobarse que la cola no este vacia. Codificación #include<stdio.h> #include<stdlib.h> #definemaxtamc 100 Typedef int tipodato; Typedef struct { Int frente. Final; Tipodato A [maxtamc]; }cola; Void vaciaC(cola* C);

Void anade C (cola* C, tipodato E); Void borrarC(cola* C); Tipodato primeroC(cola C); Int esvaciaC(cola C); Int estallenaC(cola C); Void vaciaC (cola* C) { C->frente= 0; C->final=0; } Void anadeC(cola* C, tipodato E) { If (estallenaC( *C)) { Puts(“desbordamiento cola”); Exit (1); } c->final = (C-> final + 1)% maxtamc; C->A[C->final] =E; } Tipodato primeroC(cola C) { If (esvaciaC)) { Puts(“elemento drente de una cola vacia”); Exit (1); Return (C.A[(C.frente+1) % maxtamC]); } Int esvaciaC (cola C) { Return (C.frente==C. final); } Int estallenaC(cola C) { Return ( C.frente==(==(C.final+1) % maxtamC); } Void borrarC (cola* C) { If (esvaciaC(*C)) { Puts(“eliminacion de una cola vacia”); Exit (1); C->frente =(C->frente+1) % maxtamC; }

Problema resuelto de árbol

1.- se dispone de un árbol binario de elementos de tipo entero. Escriba funciones que calculen: a) La suma se sus elementos. b) La suma de sus elementos que son múltiplos de 3 Análisis del problema Para resolver el problema basta con implementar las dos funciones efectuando al hacer un recorrido del árbol las correspondientes operaciones. Codificación Int Suma (Nodo*a) { If(a) Return (a->el + Suma(a->hi) + Suma(a-<>hd)); Else Return(0); } Int SumaMultimpos (Nodo*a) { If(a) If (a->el%3) Return( a->el + SumaMultimpos(a->hi)+SumaMultimpos(a->hd); Else Return( sumaMultimpos(a->hi) + SumaMultimpos(a->hd) Else Return(0); }

Colas en C++ octubre 30, 2012

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Implementación /*

* C++ - Colas/Queue * Copyright 2014 Martin Cruz Otiniano * Description : Encola elemento, Desesencola elemento, Mostrar cola, Vaciar cola * Site

: martincruz.me

*/

#include

using namespace std;

/*

Estructura de los nodos de la cola

------------------------------------------------------------------------*/ struct nodo { int nro; struct nodo *sgte; };

/*

Estructura de la cola

------------------------------------------------------------------------*/ struct cola { nodo *delante; nodo *atras

;

};

/*

Encolar elemento

------------------------------------------------------------------------*/ void encolar( struct cola &q, int valor ) { struct nodo *aux = new(struct nodo);

aux->nro = valor;

aux->sgte = NULL;

if( q.delante == NULL) q.delante = aux;

// encola el primero elemento

else (q.atras)->sgte = aux;

q.atras = aux;

// puntero que siempre apunta al ultimo elemento

}

/*

Desencolar elemento

------------------------------------------------------------------------*/ int desencolar( struct cola &q ) { int num ; struct nodo *aux ;

aux = q.delante;

// aux apunta al inicio de la cola

num = aux->nro; q.delante = (q.delante)->sgte; delete(aux);

// libera memoria a donde apuntaba aux

return num; }

/*

Mostrar Cola

------------------------------------------------------------------------*/

void muestraCola( struct cola q ) { struct nodo *aux;

aux = q.delante;

while( aux != NULL ) { cout<<"

"<< aux->nro ;

aux = aux->sgte; } }

/*

Eliminar todos los elementos de la Cola

------------------------------------------------------------------------*/ void vaciaCola( struct cola &q) { struct nodo *aux;

while( q.delante != NULL) { aux = q.delante; q.delante = aux->sgte; delete(aux); } q.delante = NULL; q.atras

= NULL;

}

/*

Menu de opciones

------------------------------------------------------------------------*/ void menu() { cout<<"\n\t IMPLEMENTACION DE COLAS EN C++\n\n"; cout<<" 1. ENCOLAR

"<<endl;

cout<<" 2. DESENCOLAR

"<<endl;

cout<<" 3. MOSTRAR COLA

"<<endl;

cout<<" 4. VACIAR COLA

"<<endl;

cout<<" 5. SALIR

"<<endl;

cout<<"\n INGRESE OPCION: "; }

/*

Funcion Principal

------------------------------------------------------------------------*/ int main() { struct cola q;

q.delante = NULL; q.atras

= NULL;

int dato;

// numero a encolar

int op;

// opcion del menu

int x ;

// numero que devuelve la funcon pop

system("color 0b");

do { menu();

cin>> op;

switch(op) { case 1:

cout<< "\n NUMERO A ENCOLAR: "; cin>> dato; encolar( q, dato ); cout<<"\n\n\t\tNumero " << dato << " encolado...\n\n"; break;

case 2:

x = desencolar( q ); cout<<"\n\n\t\tNumero "<< x <<" desencolado...\n\n"; break;

case 3:

cout << "\n\n MOSTRANDO COLA\n\n";

if(q.delante!=NULL) muestraCola( q ); else

cout<<"\n\n\tCola vacia...!"<<endl;

break;

case 4:

vaciaCola( q ); cout<<"\n\n\t\tHecho...\n\n"; break;

}

cout<<endl<<endl; system("pause");

system("cls");

}while(op!=5);

return 0; }

Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir. El símil cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada. El nodo típico para construir pilas es el mismo que vimos en los capítulos anteriores para la construcción de listas y pilas: struct nodo { int dato; struct nodo *siguiente; };

3.2 Declaraciones de tipos para manejar colas en C ^

Los tipos que definiremos normalmente para manejar colas serán casi los mismos que para manejar listas y pilas, tan sólo cambiaremos algunos nombres: typedef struct _nodo { int dato; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Cola;

tipoNodo es el tipo para declarar nodos, evidentemente. pNodo es el tipo para declarar punteros a un nodo. Cola es el tipo para declarar colas.

Cola

Es evidente, a la vista del gráfico, que una cola es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Además, debido al funcionamiento de las colas, también deberemos mantener un puntero para el último elemento de la cola, que será el punto donde insertemos nuevos nodos. Teniendo en cuenta que las lecturas y escrituras en una cola se hacen siempre en extremos distintos, lo más fácil será insertar nodos por el final, a continuación del nodo que no tiene nodo siguiente, y leerlos desde el principio, hay que recordar que leer un nodo implica eliminarlo de la cola.

3.3 Operaciones básicas con colas ^

De nuevo nos encontramos ante una estructura con muy pocas operaciones disponibles. Las colas sólo permiten añadir y leer elementos: 

Añadir: Inserta un elemento al final de la cola.



Leer: Lee y elimina un elemento del principio de la cola.

3.4 Añadir un elemento ^

Las operaciones con colas son muy sencillas, prácticamente no hay casos especiales, salvo que la cola esté vacía. Añadir elemento en una cola vacía

Cola vacía

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además los punteros que definen la cola, primero y ultimo que valdrán NULL:

Elemento encolado

El proceso es muy simple, bastará con que: 1. Hacer que nodo->siguiente apunte a NULL. 2. Que el puntero primero apunte a nodo. 3. Y que el puntero último también apunte a nodo. Añadir elemento en una cola no vacía

Cola no vacía

De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una cola, en este caso, al no estar vacía, los punteros primero y ultimo no serán nulos:

Elemento encolado

El proceso sigue siendo muy sencillo: 1. Hacemos que nodo->siguiente apunte a NULL. 2. Después que ultimo->siguiente apunte a nodo. 3. Y actualizamos ultimo, haciendo que apunte a nodo. Añadir elemento en una cola, caso general

Para generalizar el caso anterior, sólo necesitamos añadir una operación: 1. Hacemos que nodo->siguiente apunte a NULL. 2. Si ultimo no es NULL, hacemos que ultimo->siguiente apunte a nodo. 3. Y actualizamos ultimo, haciendo que apunte a nodo. 4. Si primero es NULL, significa que la cola estaba vacía, así que haremos que primero apunte también a nodo.

3.5 Leer un elemento de una cola, implica eliminarlo ^

Ahora también existen dos casos, que la cola tenga un solo elemento o que tenga más de uno. Leer un elemento en una cola con más de un elemento

Usaremos un puntero a un nodo auxiliar:

Cola con más de un elemento

1. Hacemos que nodo apunte al primer elemento de la cola, es decir a primero. 2. Asignamos a primero la dirección del segundo nodo de la pila: primero>siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Elemento desencolado

Leer un elemento en una cola con un solo elemento

Cola con un elemento

También necesitamos un puntero a un nodo auxiliar: 1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.

Elemento desencolado

2. Asignamos NULL a primero, que es la dirección del segundo nodo teórico de la cola: primero->siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar. 5. Hacemos que ultimo apunte a NULL, ya que la lectura ha dejado la cola vacía. Leer un elemento en una cola caso general

1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero. 2. Asignamos a primero la dirección del segundo nodo de la pila: primero>siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar. 5. Si primero es NULL, hacemos que ultimo también apunte a NULL, ya que la lectura ha dejado la cola vacía.

3.6 Ejemplo de cola en C ^

Construiremos una cola para almacenar números enteros. Haremos pruebas insertando varios valores y leyéndolos alternativamente para comprobar el resultado. Algoritmo de la función "Anadir"

1. Creamos un nodo para el valor que colocaremos en la cola. 2. Hacemos que nodo->siguiente apunte a NULL. 3. Si "ultimo" no es NULL, hacemos que ultimo->>siguiente apunte a nodo.

4. Actualizamos "ultimo" haciendo que apunte a nodo. 5. Si "primero" es NULL, hacemos que apunte a nodo. void Anadir(pNodo *primero, pNodo *ultimo, int v) { pNodo nuevo; /* Crear un nodo nuevo */ nuevo = (pNodo)malloc(sizeof(tipoNodo)); nuevo->valor = v; /* Este será el último nodo, no debe tener siguiente */ nuevo->siguiente = NULL; /* Si la cola no estaba vacía, añadimos el nuevo a continuación de ultimo */ if(*ultimo) (*ultimo)->siguiente = nuevo; /* Ahora, el último elemento de la cola es el nuevo nodo */ *ultimo = nuevo; /* Si primero es NULL, la cola estaba vacía, ahora primero apuntará también al nuevo nodo */ if(!*primero) *primero = nuevo; } Algoritmo de la función "leer" Algoritmo de la función "leer"

1. Hacemos que nodo apunte al primer elemento de la cola, es decir a primero. 2. Asignamos a primero la dirección del segundo nodo de la cola: primero>siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura equivale a leer y borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar. 5. Si primero es NULL, haremos que último también apunte a NULL, ya que la cola habrá quedado vacía. int Leer(pNodo *primero, pNodo *ultimo) { pNodo nodo; /* variable auxiliar para manipular nodo */ int v; /* variable auxiliar para retorno */ /* Nodo apunta al primer elemento de la pila */ nodo = *primero; if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */ /* Asignamos a primero la dirección del segundo nodo */ *primero = nodo->siguiente; /* Guardamos el valor de retorno */ v = nodo->valor; /* Borrar el nodo */ free(nodo); /* Si la cola quedó vacía, ultimo debe ser NULL también*/

if(!*primero) *ultimo = NULL; return v; } Código del ejemplo completo

Tan sólo nos queda escribir una pequeña prueba para verificar el funcionamiento de las colas: #include <stdio.h> typedef struct _nodo { int valor; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; /* Funciones con colas: */ void Anadir(pNodo *primero, pNodo *ultimo, int v); int Leer(pNodo *primero, pNodo *ultimo); int main() { pNodo primero = NULL, ultimo = NULL; Anadir(&primero, &ultimo, 20); printf("Añadir(20)\n");

C++ Estándar Programación con el Estándar ISO y la Biblioteca de Plantillas (STL) © Paraninfo Thomson Learning 2001

Ejercicios resueltos por capítulos. Aquí encontrará los ejercicios resueltos por capítulos (También puede descargarse un fichero comprimido con todos los fuentes de los ejercicios)

PARTE I 1. Introducción No tiene ejercicios.

2. Conceptos básicos 2.1) Quedaría del siguiente modo: , hay otros tipos de comentarios como los de C++: empezar un comentario tipo C y ahora lo acabo. */ / * Que comentario más precioso * / / / Este es más precioso todavía.

main(), el programa no se podría enlazar. Si ponemos main() ocurre lo mismo, el compilador da un error de redefinición de una función.

2.2) Si en un programa no ponemos la función dos funciones

2.3) El programa puede parecer a primera vista muy sencillo. En primer lugar vamos a leer y escribir una cadena. La primera solución intuitiva: #include // USAMOS: cin, cout void main() { char s[20]; // Cadena de hasta 19 caracteres cin >> s; // Leer la primera palabra cout << endl << s // Escribir en nueva línea la cadena << endl; // Y pasar a la línea siguiente } El problema es que esto únicamente nos lee la primera palabra de una cadena (esto se explicará en el capítulo de entrada/salida). Aunque no se comprenda de momento, la solución se encuentra en el fichero EJ02_03.P 2.4) Aquí está el programa: #include // USAMOS: cin, cout void main() { double d1, d2;

out << "Introduce dos reales: "; cin >> d1 >> d2; cout << "La suma es: " << d1 + d2 << endl } 2.5) El programa correcto es éste: #include // USAMOS: cout void main() { cout << "Hola mundo"; } 2.6) Sí es correcta. 2.7) Este comentario es erróneo. Hemos dicho que los comentarios no se detectan en las cadenas. Pues no es completamente cierto. No se detecta su apertura pero sí su clausura. Por ello, las sentencias se convertirían en: "; */ La solución sería definir de nuevo las sentencias como: /* cout << "/* Me pillaste *""/"; // Concatenación de cadenas */

3. Tipos de datos 3.1) La función es: int Convierte(char c) { return int(c - '0'); } // Usando int() en vez de (int) se ahorra un par de paréntesis 3.2) Sí que es válido ya que en C++ todos los tipos integrales son compatibles. Aunque sería mucho mejor explicitar las conversiones: b= (byte)w; w= (word)l; d= (dword)w; 3.3) Su longitud es 9 tomando

sizeof(int) == 2.

3.4) La primera dará error ya que 8 no es un dígito octal y por tanto 08 es un error. La segunda dará 24 porque 014 está en octal que es 12 en decimal.

4. Control de Flujo 4.1) El listado es funcionalmente correcto pero sintácticamente no. Faltan los puntos y comas de las cuatro sentencias de asignación. if (a < b) if (a < c)

min=

a;

else min= c; else if (b > c) min= c; else min= b; 4.2) Programa que cuenta el número de ocurrencias en una cadena de las 5 vocales en 5 variables diferentes: a, e, i, o, u. Usaremos la función Leer_Cadena() del ejercicio 2.3. El programa está en EJ04_02.P 4.3) Una función que calcule el M.C.D. de dos números: int Mcd(int a, int b) { if (a <= 0 || b <= 0) return -1; // Código de error while (a != b) if (a < b) b= b - a; // b-= a; // Igual que la anterior. Ya se verá else a= a - b; // a-= b; // Igual que la anterior return a; // Al final el mcd está en a y en b (a == b) } Un ejemplo de uso de la función está en EJ04_03.P 4.4) Función que compara dos cadenas: int StrCmp(char *s1, char *s2) { int i= 0; while (s1[i] || s2[i]) { // Hasta terminar las dos if (s1[i] < s2[i]) return -1; // La cadena 1 es menor que la 2 else if (s1[i] > s2[i])

return 1; // La cadena 1 es mayor que la 2 i++; } return 0; // Las cadenas son iguales } Esta función es similar a strcmp() de la librería estándar del C++. Un ejemplo de uso de la función está en EJ04_04.P 4.5) Sólo la b) es correcta. Recordemos que la sentencia: for(a; b; c); se convierte en: { a; while(b) { d; c; } } Por tanto, las sentencias anteriores son: a) int i= 0, int j= 0; // Incorrecto // Dos declaraciones separadas por una coma while .. b) int i= 0, j= 0; // Correcto // Dos declaraciones de tipo entero while .. c) int i= 0, long j= 0; // Incorrecto while .. d) (int i = 0), (long j = 0) // Incorrecto // Lástima porque era una buena idea 4.6) La solución se encuentra en el fichero EJ04_06.P 4.7) En este ejercicio se ha pretendido aumentar la atención del lector en este error común y sutil pero difícil de detectar. La condición del bucle está formada por el operador de asignación (=) y no el operador de comparación (==), con lo que el resultado del programa es que sólo muestra un 0, ya que el resultado de la asignación i=10, además de asignar 10 a la variable i, es que devuelve el valor 10, que es un valor cierto, al ser no nulo. Si después lo negamos con el operador ! obtenemos falso, con lo que el bucle sale después de la primera iteración.

4.8) La solución se encuentra en el fichero EJ04_08.P 4.9) La solución se encuentra en el fichero EJ04_09.P 4.10) La solución se encuentra en el fichero EJ04_10.P 4.11) La solución se encuentra en el fichero EJ04_11.P

5. Operadores 5.1) Es simple: x & (x - 1) 5.3) Se supone que tenemos dos valores enteros almacenados en dos variables reales. Yo lo haría así: float Resto(float a, float b) { return float((long)a % (long)b); } 5.4) NO ES VÁLIDO PORQUE EL OPERADOR COMA NO SE PUEDE UTILIZAR EN ESE PARTE DEL FOR. Si cogemos uno de los dos incementos y lo ponemos al final del bucle sí que funciona. En este caso invierte el vector de caracteres s (no es una cadena porque no acaba en '\0'). El resultado en s será ACABATOR. 5.5) Con algo parecido a esto sería suficiente para que pareciera aleatorio. Si además hacemos coincidir la llamada a Rand() con un factor externo (tiempo, preferiblemente), esta función es casi impredecible. El programa se encuentra en EJ05_05.P

6. Funciones 6.1) La solución se encuentra en el fichero EJ06_01.P 6.2) La solución se encuentra en el fichero EJ06_02.P 6.3) Es sintácticamente correcto. El compilador crea variables temporales para almacenar estas constantes y así ya puede tomar la dirección. De todas formas no es un buen estilo de programación pasar constantes por referencia porque aunque la función modifique su valor no nos podemos dar cuenta.

f(25) es ambigua. El compilador no sabe si llamar a la función con un argumento o llamar a la segunda usando parámetros por defecto. La llamada f(17, 42) es completamente 6.4) La llamada

correcta ya que no hay ambigüedad. 6.5) Sí que es correcto y sería equivalente a: void f(int a= 1, int b= 2, int c= 3) { // .. }

6.6) La solución se encuentra en el fichero EJ06_06.P

7. Variables 7.1) Las variables estáticas se inicializan a 0. Las variables automáticas no. Por tanto a valdrá 0 y b tendrá un valor indefinido dependiendo del compilador. No se recomienda usar la declaración de 'a' de ese modo. Es mejor explicitar: int a= 0; 7.2) Este sería un programa que volvería loco al propio Bjarne Stroustrup: void Funcion(float f); // Decl1. Campo prototipo float f; // Decl 2. Campo global. Se almacena en el seg. de datos. f vale 0 void Funcion(float f) { // Decl. 2. Campo local automático. Se almacena en pila float f; // Error: parámetros y var. locales tienen el mismo campo auto float a; // Este auto es opcional // Decl.3.Campo local automático. Se almacena en pila. a vale ? static float f; // Error: mismo campo. static float s; // Decl.4.Campo local estático. Se almac. en el s. de datos. s vale 0 { float f; // Decl. 5. Campo de bloque. Se almacena en la pila f= 2; // Accedo a la 'f' de la decl. 5 ::f= 3; // Accedo a la 'f' de la decl. 1 s= 4; // Accedo a la 's' de la decl. 4 a= 5.5; // Accedo a la 'a' de la decl. 3 // No hay forma de acceder al parámetro 'f' de la función (Decl. 2) } } float f; // Error! Redefinimos la variable global.

7.3) Como hemos visto en el caso anterior, no es correcto ya que los dos tienen el mismo campo local automático. 7.4) Dará un error en la definición const int a ya que las constantes se deben inicializar en el momento de la definición. Las otras dos también darían error. 7.5) No sería equivalente a: const char * Var; sino a: char * const Var; porque

typedef no es una macro.

7.6) El programa A funciona correctamente. El programa B da error porque no sabemos cómo es la estructura, por tanto, no podemos definir una variable de ella. El programa C funcionaría si no se tratara de una estructura. Ya se vio que extern sólo es aplicable a variables de tipos no compuestos. 7.7) Este sería un programa que volvería loco al propio Bjarne Stroustrup: void Funcion(float f); // Decl1. Campo prototipo float f; // Decl 2. Campo global. Se almacena en el seg. de datos. f vale 0 void Funcion(float f) { // Decl. 2. Campo local automático. Se almacena en pila float f; // Error: parámetros y var. locales tienen el mismo campo auto float a; // Este auto es opcional // Decl.3.Campo local automático. Se almacena en pila. a vale ? static float f; // Error: mismo campo. static float s; // Decl.4.Campo local estático.Se almac. en el s. de datos. s vale 0 { float f; // Decl. 5. Campo de bloque. Se almacena en la pila f= 2; // Accedo a la 'f' de la decl. 5 ::f= 3; // Accedo a la 'f' de la decl. 1 s= 4; // Accedo a la 's' de la decl. 4

a= 5.5; // Accedo a la 'a' de la decl. 3 // No hay forma de acceder al parámetro 'f' de la función (Decl. 2) } } float f; // Error! Redefinimos la variable global.

8. Sobrecarga y conversiones 8.1) En C++, las constantes tienen tipo por lo que el compilador asignará: - la primera es un

int . Coincidencia exacta con Print(int ).

- la segunda es un double. No hay coincidencia exacta ni trivial. No hay promoción. Hay conversión estándar. Pero las conversiones estándar de un tipo aritmético puede ser a cualquier otro tipo aritmético. Por tanto, fallará porque hay una ambigüedad. Podríamos haberlo solventado poniendo 2.2F.

char. No hay coincidencia exacta ni trivial. Pero hay promoción con int; por tanto, Print(int ).

- la tercera es un se llama a

En general, las posibles soluciones a los problemas que aparecen (como el de la segunda llamada) son: a) Declarar variables auxiliares del tipo que se desee. b) Forzar que las constantes sean del tipo requerido. c) Utilizar conversiones explícitas (cast) 8.2) Sí, no hay coincidencia exacta o trivial, no hay promociones, pero hay conversión estándar aritmética. Por tanto, se llama sin ningún problema. 8.3) No porque tomará

f() como float y no como una función. Concretamente, dará un error de float como si

llamada a no-función ("call of non-function") ya que estamos intentando llamar a un fuera una función. 8.4) La solución se encuentra en el fichero EJ08_04.P 8.5) La solución se encuentra en el fichero EJ08_05.P 8.6) Daría error al haber conversión trivial entre

const T y T.

8.7) Como no hay conversión trivial, se podría definir perfectamente. 8.8) Las dos primeras llamadas invocan a sus funciones correspondientes sin ningún problema. La tercera sigue estos pasos: Primero: no hay coincidencia exacta. Segundo: no hay promoción. Tercero: conversión estándar, pero la hay a los dos, no le damos preferencia a la que no tiene signo. Por tanto daría error de ambigüedad.

8.9) La solución se encuentra en el fichero EJ08_09.P 8.10) La solución se encuentra en el fichero EJ08_10.P 8.11) Son correctas. Se trata de conversiones de línea. 8.12) En C++,

typedef no crea tipos nuevos distintos, sólo les da un nombre diferente.

8.13) Para las cinco llamadas, el proceso es bien diferente: 1.- El literal 0.0 es un llama a f(double ).

double. Pasos: Primero: coincidencia exacta. Por tanto se

0 es un int. Pasos: Primero: no hay coincidencia exacta. Segundo: no hay promoción posible. Tercero: hay conversión estándar de int a char y de int a double. Además, dijimos que la constante 0 tiene conversión estándar 2.- El literal

con cualquier puntero. Por tanto habrá error de ambigüedad al no poder elegir ninguna de las tres funciones. 3.- El literal

0F da error de sintaxis, ya que F sólo se puede aplicar a constantes reales.

0.0F es un float. Pasos: Primero: no hay coincidencia exacta. Segundo: hay promoción de float a double. Por tanto se llama a f(double ). 4.- El literal

char *. Pasos: Primero: no hay coincidencia exacta. Segundo: no hay promoción. Tercero: hay conversión estándar entre char * y void *. Por tanto se llama a f(void *). 5.- El literal cadena es un

8.14) Para la primera combinación, la segunda llamda es correcta (mismo tipo), pero la primera no, porque no hay conversión estándar desde int a enum. Como si está permitido lo contrario, la combinación dos es perfectamente correcta. La combinación tercera también lo es, llamando cada una a su correspondiente función. 8.15) El compilador da un error de ambigüedad, ya que no sabe si llamar a o

ff(fc) sin signo

ff(fc) con signo. ¡Qué complicados son los complicadores!

9. Punteros p la dirección de la variable a (p= &a), pero al cerrarse el bloque la a se destruye con lo que el posterior de (*p= 10) puede ser catastrófico.

9.1) El primero carga en variable

El segundo programa, en cambio, funciona correctamente ya que el carácter a tratar se almacena en el 'heap' y no en la pila, así al cerrar el bloque no destruimos ninguna variable ya que no hemos definido ninguna tampoco. El (*p= 10) será válido hasta que pongamos (delete p;).

Una mejor solución sería: void main() { char *p; int a; { p= &a; } *p= 10; } 9.2) Invierte una cadena. La solución se encuentra en el fichero EJ09_02.P 9.3) La solución se encuentra en el fichero EJ09_03.P 9.4) La solución se encuentra en el fichero EJ09_04.P 9.5) La solución se encuentra en el fichero EJ09_05.P 9.6) Ese programa es muy peligroso. Leemos una cadena en s, pero s apunta a una dirección indefinida; por ello, podemos estar estropeando código, datos de nuestro o de otro programa. Además no se puede asegurar que la salida sea igual que la entrada. En fin, que este es uno de los errores más graves y típicos del C++. Además, puede que en un primer momento funcione. Más tarde el error aparecerá inesperadamente de forma catastrófica. La solución es reservar la memoria que vamos a usar: #include void main() { char s[100]; // Suponemos que con 100 caracteres es suficiente cin >> s; cout << s; } También podríamos haber usado: #include void main() { char *s; s= new int[100]; cin >> s; cout << s; delete []s; }

9.7) No ocurre nada, al final del programa el compilador se encarga de hacer todos los delete que falten. De todas formas, es muy recomendable no olvidarse de ponerlo porque si es en una función que se llama 1000 veces acabaremos con el 'heap' lleno!. Tampoco es muy recomendable hacer lo que se ha hecho en el ejercicio 1, pero a veces como en ese ejercicio, es necesario. 9.8) Para hacer lo que se nos pide en el ejercicio habría que hacer uso de punteros: float f; int *pi= (int *)&f; char *pc= (char *)&f; Y con f, *pi, *pc accederíamos a lo mismo que con la unión: f, i, c. Claramente, usar una unión anónima es más limpio aunque con punteros se ve físicamente que comparten la misma memoria. En este caso, trabajar con punteros puede ser peligroso, ya que si tenemos: char c; int *pi= (int *)&c; float *pf= (float *)&c; un a (*pi) a (*pf) excedería del tamaño del carácter, estropeando lo que hay después en memoria, que en este caso es el puntero que accede. Aquí, se puede decir, que está casi asegurado que el sistema se quede bloqueado o lo que en el argot se conoce como "colgado". 9.9) El programa compara los punteros, no donde apuntan. Si lo sustituyéramos por(*s == *t) tampoco ya que sólo compararía el primer elemento. Queda como ejercicio hacer una función que compare cadenas. En el siguiente capítulo también se verán algunas funciones de comparación. 9.10) No es correcto porque hemos definido

delete. Además, const.

podemos hacer un que no fuera

p como un puntero a enteros constantes sobre los cuales nos delete p sólo borraría el primer elemento, en el caso de

9.11) Los dos son, obviamente, equivalentes y ninguno de ellos da error. El puntero retornado en p es indefinido y la dirección a la que apunte no está reservada. No retorna NULL como podríamos imaginar en un principio, del mismo modo que

delete no modifica el puntero, sino simplemente libera la memoria.

9.12) Intentar borrar sólo una parte del vector reservado es una barbaridad, no porque sea ilógico pensarlo, sino porque el C++ no lo detecta como error y dependiendo de la implementación, puede ser que no ocurra nada o se convierta en un desastre. Lo único que sabemos con seguridad es que si hacemos lo correcto, no tendremos ningún problema.

10. Eficiencia y Optimización 10.1) La solución se encuentra en el fichero EJ10_01.P 10.2) La solución se encuentra en el fichero EJ10_02.P 10.3) Tenemos un tipo

reloj y tres funciones:

reloj Start_Timer(); // Crea un reloj y lo pone en marcha double Get_Timer(reloj &); // Retorna el tiempo en segundos desde que se creo este reloj double Stop_Timer(reloj &); // Igual que Get_Timer() pero además destruye el reloj Además se ha implementado una función de retardo Delay(unsigned long ) que tarda tantos milisegundos como se le pasen en su parámetro. Además tenemos una función Calibrar(int ) para calibrar durante unos segundos la función Delay(). El listado de la implementación es EJ10_03.P 10.4) Usando las funciones necesarias del ejercicio anterior veamos EJ10_04.P. En muchas máquinas saldrá Fact3() la más rápida y Fact2() la más lenta, completamente al contrario de lo que podríamos pensar en un principio. Esto depende de cómo estén orientados los procesadores, si tienen antememorias (cachés), si son máquinas RISC o CISC, etc. 10.5) Se prueba en el siguiente ejercicio. 10.6) La solución se encuentra en el fichero EJ10_06.P 10.7) La función al ser sentido y eficiencia a

inline haría que cualquier aparición de alias(i) fuera equivalente en i.

10.8) La solución se encuentra en el fichero EJ10_08.P 10.9) Una forma de implementar el algoritmo quicksort() está en EJ10_09.P 10.10) La multiplicación por potencias de dos se puede realizar por medio de desplazamientos de bit. Ejemplos para 2, 4 y 8 serían: inline int Mult2(int a) { return a << 1; } inline int Mult4(int a) { return a << 2; } inline int Mult8(int a) { return a << 3 }

que por las pruebas que se han realizado son ligeramente más rápidas que la multiplicación normal. Esto depende mucho de la máquina. Las funciones para la divisiones son similares pero utilizando el operador >>. 10.11) Se trataría de lo siguiente: inline int Mult3(int a) { return Mult2(a) + a; } inline int Mult5(int a) { return Mult4(a) + a; } inline int Mult6(int a) { return Mult4(a) + Mult2(a); } inline int Mult7(int a) { return Mult(6) + a; } inline int Mult9(int a) { return Mult8(a) + a; } Según vamos aumentando iremos perdiendo en eficiencia. La reutilización de unas funciones en otras no ralentiza ya que son inline. En general: int Mult(int a, int b) { int r= 0; while (b) { if ((b | 1) == b) // bit es 1 r+= a; b >>= 1; a <<= 1; } return r; }

que ya no es eficiente. Esta solución y medidas de tiempo se encuentran en el fichero EJ10_11.P 10.12) Es correcto ya que en los macros los comentarios no son expandidos. Esto se verá mejor cuando se vea preprocesamiento. 10.13) El algoritmo se encuentra en EJ10_13.P. 10.14) La solución se encuentra en el fichero EJ10_14.P

PARTE II 11. Clases 11.1) Al hacer

delete this estamos liberando la memoria que ocupa el objeto actual por lo que el Ultimo puede haber perdido su valor.

siguiente this= Ultimo ya no es válido porque el Para la gente que empieza puede quedar más claro poniendo: delete this; this= this->Ultimo;

que es lo mismo que antes pero ahora se ve que el puntero this al que hemos hecho un delete, lo utilizamos como fuente en la siguiente sentencia. Por ello, se suele utilizar el puntero this para acceder a los atributos de una clase cuando queda comprometida la claridad. En segundo lugar como this es un puntero constante ni se puede hacer un delete sobre él ni se puede poner como destino en una asignación. 11.2) El programa es completamente correcto. El primer objeto

Obj1 llama al Pon de la

c1 con el parámetro 3. Por tanto Obj1.Valor se pone a 3. El segundo objeto Obj2 llama al Pon de la clase c2 sin parámetros por lo que se toma el parámetro 1 por defecto que es lo que se almacena en Obj2.Valor. Al hacer Obj3.Valor= 10 no modificamos ningún otro objeto ni de c1 y mucho menos de c2 que no tiene nada que ver. clase

11.3) Las dos son

inline.

11.5) La solución se encuentra en el fichero EJ11_05.P 11.6) La solución se encuentra en el fichero EJ11_06.P 11.7) La solución se encuentra en el fichero EJ11_07.P 11.9) En primer lugar no funcionaría porque hemos definido los métodos privados. Solventando este problema no funcionaría tampoco porque cuando se llama a una función inline debe tener su implementación ya definida. En este caso la solución sería cambiar de orden f1() y f2().

class clase { .. public: void f1(); void f2(); .. }; inline void clase::f2() { .. } void clase::f1() { .. f2(); .. } void main() { clase o; o.f1(); } Una curiosa solución es poner las dos funciones inline, así las funciones no son evaluadas hasta que se expanden, que en este caso ocurrirá cuando lleguemos a main(), pasadas ya las definiciones de

f1() y f2(). Otra solución, evidentemente, es no definir ninguna inline.

11.10) La solución se encuentra en el fichero EJ11_10.P 11.11) Si hacemos la implementación de los complejos en forma polar, no quita para que definamos exactamente los mismos métodos, incluso los constructores. Por tanto, si sólo viésemos las declaraciones de los métodos, no podemos saber si están implementados en forma rectangular o en forma polar.

c1. La segunda modifica el miembro c2. La tercera c3. La cuarta sentencia, modifica el miembro c1 al usar this. La quinta

11.12) La primera sentencia modifica el parámetro

modifica la variable global sentencia también al utilizar el operador de campo de clase. 11.13) No se puede. Deberemos hacer: class clase { static int Estatuto; .. }; int clase::Estatuto= 23; o definir un método estático para acceder a

Estatuto. De todas formas la sentencia:

int clase::Estatuto; se debe seguir poniendo. 11.14) Perfectamente. Aunque no tiene mucho sentido. 11.15) No podemos acceder a implícito

a porque f() es una función estática y por tanto no tenemos el parámetro

this para poder acceder a los .

11.16) La solución se encuentra en el fichero EJ11_16.P

12. Creación de objetos 12.1) Los métodos son: a) constructor normal b) constructor por defecto c) exactamente igual a lo anterior d) constructor copia e) constructor por defecto (todos los argumentos por defecto) y constructor de conversión de (int *) a c1 f) constructor de conversión de float a cl si se toma el último argumento por defecto, si no, constructor normal g) operador suma h) operador de conversión de cl a int. No se pone retorno i) operador de asignación j) destructor k) Error! Los destructores no tienen parámetros

punto(c.RE(), c.IM()) crea un objeto temporal en el cuerpo punto(complejo c) y no modifica 'x' e 'y'. La solución sería:

12.2) No es correcta ya que de la función

class punto { private: double x, y; public: void Pon(double xx, double yy) { x= xx; y= yy; } punto(double xx, double yy) { Pon(xx, yy); } punto(const complejo & c) { Pon(c.RE(), c.IM());

} }; 12.3) Tiene dos problemas, el primero es que como no hemos puesto ningún modificador de y se trata de 'class', el método f() será privado con lo que no lo podremos llamar. En segundo lugar, no podemos llamar a funciones no constantes desde objetos constantes. En este caso, esta última restricción es una garantía de seguridad de que el objeto si es constante no va a ser modificado. 12.4) Dependerá del orden en que están definidos dentro de una clase. Lo único que sabemos con seguridad es que x pasará a valer a antes de que y pase a valer b. Esto es debido a que los dos se construyen en la

'x' si que está en la lista se construye y toma su valor a la vez mientras 'y' tiene que esperar a valer 'b' al cuerpo de la función.

lista de inicialización, como que

12.5) Para la primera no, ya que al haber otro constructor, ya no está definido el constructor por defecto. En la segunda sí será posible (en la versión 2.0 no). Las dos últimas son perfectamente válidas. 12.6) Se creará un objeto temporal por lo que el objeto constante no puede ser modificado por mucha referencia de que se trate. 12.8) Ver EJ12_08.P 12.10) Sí se pueden definir (atributos y métodos) 12.11) El operador

volatile.

sizeof no puede sobrecargarse.

12.12) En primer lugar, falta el punto y coma final de la clase. En segundo lugar, nunca deberemos hacer una asignación a this y mucho menos un delete. 12.13) Es correcto aunque es más recomendable definir la unión dentro de una clase. 12.14) Genera ambigüedad. No sabemos si llamar a f(A(Objeto)); o a:

f(Objeto.operator A ()); 12.15) No funcionaría porque en C++ no se buscan conversiones multinivel. Y no hay ninguna conversión en un solo paso para hacer coincidir los parámetros. 12.16) Al llamarse a la función Nada() que parece que no hace nada, se crea un objeto temporal usando el constructor copia. El constructor copia que tenemos definido sólo copia los atributos. Al llegar al final del cuerpo de la función (en seguida porque no hace nada), se retornaría llamando al destructor del objeto temporal, que de la forma que tenemos definida la cadena haría un delete s; liberando la memoria. Cuando hiciéramos cout << c1; probablemente salga la cadena por pantalla, pero no se puede asegurar, ya que hemos liberado la memoria que ocupa y puede ser utilizada por cualquier otro. Lo peor no es esto, sino que al llegar al final de la función se destruiría c1 volviendo a llamar a delete s que ya

está borrado. Esto lo suele avisar el compilador por medio de un error al final del programa del tipo "Null pointer assignment" 12.17) La solución se encuentra en el fichero EJ12_17.P

13. Herencia y Polimorfismo 13.1) La asignación e) es incorrecta ya que no podemos asignar un clase derivada con una clase base. La asignación f) nos muestra que esto es imposible incluso utilizando casts. La asignación h) es incorrecta por el mismo motivo que la e). Pero la i) es correcta porque siempre podemos pasar de un puntero de un tipo a un puntero de otro tipo utilizando casts. 13.2) No, no tiene sentido heredar dos veces ya se virtual o no virtual. Si se quiere incluir dos veces una clase se hace precisamente eso, incluir (composición).

c1 que es un puntero cuadrilatero. La segunda sentencia es incorrecta ya que no se puede asignar un puntero a un cuadrilatero a un puntero a un cuadrado. En el segundo lugar podríamos usar un cast pero si los 13.3) La primera crea un objeto dinámico de la clase cuadrado y toma su dirección en a

métodos no son virtuales puede ser peligroso. cuadrado *c2= (cuadrado *)new cuadrilatero; 13.4) La longitud es 4 + 4 + 4 = 12 suponiendo 4 la longitud de int, 4 la longitud de float y 4 la longitud del puntero a la tabla de métodos virtuales (suponiendo punteros de 32 bits).

f() darán error ya que tienen los mismos parámetros y distinto tipo de retorno. En cambio las funciones g() son funciones totalmente diferentes ya que tienen parámetros distintos. Por tanto B heredará g(int, double) y tendrá además g(double, int). 13.5) Las funciones

13.6) Son los dos virtuales ya que si definimos un destructor como virtual en una clase base, los destructores en las clases heredadas también serán virtuales. En estos casos se recomienda poner la palabra virtual para dejarlo más claro. Se deja como ejercicio averiguar si teniendo dos clases A y B, una con destructor virtual y la otra normal, si heredamos las dos en una clase C, ¿el destructor de C será virtual? 13.7) La solución se encuentra en el fichero EJ13_07.P

14. Plantillas 14.1) Sí que podemos compilar ese programa, pero en el momento que usemos la función La solución es simplemente borrar la primera declaración ya que la segunda la incluye.

f() dará error.

14.2) Porque el tipo A no está incluido en los parámetros de la función. Ya sabemos que el retorno no cuenta. 14.3) Ver EJ14_03.P. Se han definido algunos métodos internos y otros externos para mostrar el a vector. Sería preferible todos externos. 14.4) Que no se puede hacer coincidir (C valdría

int.

*) con (int). Si hubiera sido (C) no habría problema, C

14.5) La solución vale para cualquier tipo: template int SizeOf_EnBits(T v) { return sizeof(T) * 8; //return sizeof v * 8; // También válido } 12.6) No, pero la solución es simple: typedef clase1 clase1_int; clase2 a;

15. Errores y Excepciones 16. Modularidad 16.1) Porque ya vienen provistas del método de protección contra redefiniciones que hemos explicado. 16.2) Funcionaría muy mal ya que no hemos definido el constructor copia y el operador de asignación. Al tratarse de una estructura dinámica, cada vez que llamemos implícitamente al constructor copia (por ejemplo con objetos temporales), deberíamos copiar toda la estructura y sólo copiamos la dirección. Pero cuando destruimos los objetos temporales, sí que destruimos toda la estructura. En resumidas cuentas, que vamos a destruir más veces que a construir. 16.3) Aquí viene la solución al ejercicio anterior. Se compone de tres ficheros EJ16_03.H, EJ16_03.H1, EJ16_03.H2. Además tenemos un fichero

EJ16_03.P que nos lo prueba todo.

El fichero EJ16_03.H como vemos, queda limpio de toda implementación. En primer lugar incluye EJ16_03.H1 en la parte privada de la clase y después incluye fuera a EJ16_03.H2. Como se observa lo único que ve el son los métodos de la lista. No se puede saber si está implementada dinámica o estáticamente, no se sabe nada de sus privados, ni estáticos, sólo lo imprescindible que debe conocer el que usa esta clase. La parte privada de la clase (los atributos) está en el fichero EJ16_03.H1. Aquí se definen los privados. Es de resaltar la presencia interna de

nodo. Se podría haber

definido como clase amiga de clista, pero como en este caso sólo la utilizamos aquí, la incluimos dentro del campo de la función. Pasemos ahora a la implementación de los métodos. Están en el fichero EJ16_03.H2. El último método (Alias) se suele incluir para hacer referencias. Esto sirve para que tengamos varias listas operando sobre los mismos datos. Esto suele ser peligroso por los objetos temporales y porque la destrucción de uno implica que se ha liberado el espacio al que apuntan todos. Por eso no lo vamos a usar. Por último, hay un fichero que lo prueba todo; este fichero sólo debe incluir la especificación. Es el fichero EJ16_03.P. COMENTARIOS: Los operadores de postincremento y postdecremento retornan por valor. Así, operaciones como la siguiente, estarían permitidas pero no funcionarían de manera correcta:

++l1++; Sólo incrementaría una vez l1, el otro operador actuaría sobre un objeto temporal retornado por el primero. En resumen, este artificio de estructura modular es un poco largo de realizar y difícil de entender para el que lo desarrolla. Pero nadie puede dudar que el fichero EJ16_03.H está claro como el agua. 16.5) Sí que compilaría y enlazaría. Al tener los dos el atributo const tienen privado al módulo, por lo que no son visibles externamente y no habría conflicto entre ellas. De todas formas, sería mucho más conveniente, poner una sola declaración en una cabecera e incluirla en los dos módulos.

PARTE III 17. Introducción a las Librerías Estándar No tiene ejercicios.

18. Entrada y salida 18.1) La solución se encuentra en el fichero EJ18_01.P 18.2) En cada caso saldría: a) 00103 b) 10 // Todavía no había hecho efecto c) a 18.3) El programa debe incluir algunos manipuladores y flags para que no se ignoren los caracteres blancos. #include #include void main() { cin >> resetiosflags(ios::skipws); while (1) { char c; cin >> c; if (!cin) break; cout << c; } }

También se podía haber hecho así: while (1) { char c; cin.get(c); if (cin.eof()) break; // Fin copia cout.put(c); } que no utiliza manipuladores. 18.4) No ya que el

setw(100) actúa sobre un stream (cin) y el setw(5) actúa sobre otro

(cout). Además, la salida sería: 00069 18.5) No ya que ya está sobrecargado en

en las

istream y ostream.

clases

18.6) Tenemos aquí un programa que produce un volcado hexadecimal de un fichero de entrada a otro de salida. Si se omiten estos ficheros se cogerán por defecto la entrada y salida por pantalla estándar. Ver EJ18_06.P 18.7) La solución es: int i= 42; const char *fn= "test.dat" const int Largo = 7; { fstream f(fn, ios::out | ios::binary); f.seekp(Largo, ios::beg); f.write((const char *)&i, 2); } // Al destruirse se cierra { fstream f(fn, ios::in | ios::binary); f.seekg(Largo, ios::beg); f.read((char *)&i, 2); } // Al destruirse se cierra También podíamos haber llamado a los destructores explícitamente. Ya que estamos con la programación orientada a objetos, es más lógico utilizar constructores y destructores. Principalmente, lo que no hay que hacer es mezclar los dos métodos. 18.8) Simplemente hay que saber el código del descriptor de la impresora (que suele ser 4). Utilizamos entonces el constructor ofstream(int fh):

fstream Stream_de_la_impresora(4); Si queremos utilizar buffer: char *Buffer= new char [1024]; ofstream Str_de_la_impr(4, Buffer, 1024); 18.9) La función

Leer_Cadena() la definimos así:

#include // resetiosflags void Leer_Cadena(char *s) { cin >> resetiosflags(ios::skipws); // No pasar los caracteres blancos for(int i= 0; cin >> s[i]; i++) // Leer hasta '\0' if (s[i] == '\n') // Se ha pulsado INTRO break; s[i]= '\0'; // Poner caracter nulo de terminación de cadena } En primer lugar hacemos que no se quiten los caracteres blancos. Luego leemos hasta encontrar uno de estos dos caracteres '\0', '\n'. Éste último se producirá cuando pulsemos la tecla de retorno. Al final deberemos poner el carácter nulo ya que el stream no lo inserta.

19. Cadenas y Numéricos 19.1) La solución se encuentra en el fichero EJ19_01.P 19.2) La solución se encuentra en el fichero EJ19_02.P 19.4) La solución se encuentra en el fichero EJ19_04.P 19.5) La solución se encuentra en el fichero EJ19_05.P

20. Introducción a la STL 20.1-2) La solución se encuentra en el fichero EJ20_01.P 20.3) La solución se encuentra en los ficheros EJ20_03a.P, EJ20_03b.P y EJ20_03c.P. 20.4) La solución se encuentra en el fichero EJ20_04.P 20.5) La solución se encuentra en el fichero EJ20_05.P

21. Contenedores y adaptadores 21.1) La solución se encuentra en el fichero EJ21_01.P

21.2) La solución se encuentra en el fichero EJ21_02.P 21.3) La solución se encuentra en los ficheros EJ21_03a.P y EJ21_03b.P. 21.4) La solución se encuentra en los ficheros EJ21_04a.P y EJ21_04b.P. 21.5) La solución se encuentra en el fichero EJ21_05.P 21.6) La solución se encuentra en el fichero EJ21_06.P 21.7) La solución se encuentra en el fichero EJ21_07.P 21.8) La solución se encuentra en el fichero EJ21_08.P 21.9) La solución se encuentra en el fichero EJ21_09.P

22. Objetos-funciones y algoritmos 22.1) La solución se encuentra en el fichero EJ22_01.P 22.2) La solución se encuentra en el fichero EJ22_02.P 22.3) La solución se encuentra en el fichero EJ22_03.P 22.4) La solución se encuentra en el fichero EJ22_04.P 22.5) La solución se encuentra en el fichero EJ22_05.P 22.6) La solución se encuentra en el fichero EJ22_06.P 22.7) La solución se encuentra en el fichero EJ22_07.P

23. El Proceso de Desarrollo con C++

Bueno este estas son las operaciones basicas que se deben saber de Colas, las cuales son ingresar datos, borrar dato e imprmir los datos.

Código: #include<stdio.h> #include #include<stdlib.h>

void insertar_colas(); void imprimir_colas(); void eliminar_colas(); typedef struct nodoc { int dato_colas;//donde se guarda el telefono int dura_colas;//donde se guarda el tiempo struct nodoc *sgte;//puntero siguiente }nodoc; long int fono; int tiempo; nodoc *act_1,*fin,*inicio_1=NULL; main() { int opcion; do { system("color "); system("CLS"); printf("\n\t\t\t\t***MENU***\n"); printf("\n\n Trabajo Colas\n"); printf(" ---Trabajar con COLAS---\n"); printf("\n 1.- Realizar llamada"); printf("\n 2.- Mostrar llamadas y su duracion:"); printf("\n 3.- SALIR"); printf("\n\n * Para Salir Presione 4: "); printf("\n\n Ingrese una opcion: "); scanf("%d",&opcion); printf("\n"); if(opcion>3) { printf("\n Opcion NO VALIDA concentrese porfavor"); printf("\n\n ** PRESIONE CUALQUIER TECLA PARA VOLVER AL MENU **"); getch(); } switch(opcion) { case 1: insertar_colas(); break; case 2: imprimir_colas(); break; case 3: exit(0); } } while(opcion!=0); getch(); } void insertar_colas() { printf("\n\n Ingrese numero: ");

scanf("%d",&fono); printf("\n Ingrese duracion:"); scanf("%d",&tiempo); act_1=(nodoc*)malloc(sizeof(nodoc)); act_1->dato_colas=fono; act_1->dura_colas=tiempo; act_1->sgte=NULL; if(fin==NULL) fin=inicio_1=act_1; else { fin->sgte=act_1; fin=act_1; } } } void imprimir_colas() { act_1=inicio_1; while(act_1!=NULL) { printf(" La llamada %d duro : %d min\n",act_1->dato_colas,act_1>dura_colas); act_1=act_1->sgte; } printf("\n\n ** PRESIONE CUALQUIER TECLA PARA VOLVER AL MENU **"); getch(); }

Saludos _________________

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 “s 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 =)

2 Comments on “Estructuras de datos y algoritmos en C/C++: Listas y Colas” 1.

1

Julito said at 12:59 am on julio 3rd, 2009:

Hola, muy xvr tu pag, pero

2.

2

marcela hernandez said at 9:56 am on octubre 26th, 2009:

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; stry(nuevo->nombre,pnombre); nuevo->cantidad=pcantidad; stry(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; stry(nuevo->nombre,pnombre); nuevo->cantidad=pcantidad; stry(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 “ <<“\t “<nombre<<“\t “ <<“\t “ <<“\t\t “ <<endl; cout<siguiente; } cout identificacion !=aux){ cout<<“\tNO HAY COINCIDENCIAS”<<endl; cout<<“\tO ES POSIBLE QUE NO HAYA DATOS”<<endl; } else{ cout<<“\tNOMBRE DE EL PRODUCTO:”<nombre costo = pcosto; stry(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: “ <<endl; cout<<“\tTELEFONO DEL ESTUDIANTE: “ <<endl; cout<<“\tCARRERA DEL ESTUDIANTE: “ <<endl; cout<siguiente; system(“pause”); } cout<<“\n”; system(“pause”); } }

https://cimec.org.ar/~mstorti/repositorio-p/

Una lista es una estructura de datos que nos permite agrupar elementos de una manera organizada. Las listas al igual que los algoritmos son importantísimas en la computación y críticas en muchos programas informáticos. Las listas están compuestas por nodos, estos nodos tienen un dato o valor y un puntero a otro(s) nodo(s). Existen varios tipos de listas: Simplemente enlazada, doblemente enlazada, circular simplemente enlazada, circular doblemente enlazada. Vamos a revisar las listas enlazadas simples, por ser el punto de partida y fundamentales para poder entender las otras. Una lista enlazada tiene un conjunto de nodos, los cuales almacenan 2 tipos de información: El dato que contienen y un puntero al siguiente nodo en la lista. El último nodo de la lista tiene como siguiente nodo el valor NULL. Entonces las listas enlazadas simples solo pueden ser recorridas en una dirección, apuntando al nodo siguiente, mas no a un nodo anterior. Aquí una ejemplo de un lista enlazada simple.

1 2 3 4

En cristiano: 55-> 60-> 31-> 5-> 4-> 51-> 9-> 27-> 68-> 62-> NULL Internamente:

5 6 7 8 9 10 11 12 13 14

Nodo-> Nodo-> Nodo-> Nodo-> Nodo-> Nodo-> Nodo-> Nodo-> Nodo-> Nodo->

Dato: Dato: Dato: Dato: Dato: Dato: Dato: Dato: Dato: Dato:

55 60 31 5 4 51 9 27 68 62

Direcion: Direcion: Direcion: Direcion: Direcion: Direcion: Direcion: Direcion: Direcion: Direcion:

0x3d2c00 0x3d2c80 0x3d2c90 0x3d2ca0 0x3d2cb0 0x3d2cc0 0x3d3ab8 0x3d3ac8 0x3d3ad8 0x3d3ae8

Siguiente: Siguiente: Siguiente: Siguiente: Siguiente: Siguiente: Siguiente: Siguiente: Siguiente: Siguiente:

0x3d2c80 0x3d2c90 0x3d2ca0 0x3d2cb0 0x3d2cc0 0x3d3ab8 0x3d3ac8 0x3d3ad8 0x3d3ae8 0

Obviamente, internamente no existen las palabras nodo, dato,dirección y siguiente, es solo una representación. Como una lista es una estructura de datos dinámica, el tamaño de la misma puede cambiar durante la ejecución del programa. Como vimos en post anteriores, se puede generar memoria dinámicamente para un array, pero un array es una estructura estática pues su tamaño tiene un limite y así creáramos array dinámicos hay que redimensionar el tamaño si es necesario, lo cual ya implica un costo de volver a generar memoria dinámica. Entonces podemos ver una ventaja de la listas sobre los arrays: No tener que redimensionar la estructura y poder agregar elemento tras elemento indefinidamente. Cuando uno ya ha trabajado con arrays (vectores y matrices) y empieza a estudiar las listas, se da cuenta que una restricción de las listas es el a los elementos. En un vector podíamos hacer algo como v[50] y nos estábamos refiriendo al índice 50 del vector v. A esto se le conoce como aleatorio. En el caso de las listas el es secuencial, es decir, para acceder a un elemento del conjunto debemos de recorrer uno por uno los elementos hasta llegar al solicitado. Rápidamente se puede concluir que el tiempo de a los elementos de un array es muchísimo más rápido que en una lista. Esta es una gran desventaja de las listas, por lo que buscar elementos por índice sería muy costoso. Esto no quiere decir que trabajar con arrays sea mejor que con listas. Las listas son muy flexibles y para muchos casos son imprescindibles. Bueno, aquí va la primera práctica que hice sobre listas enlazadas. Implementación de una clase Lista, clase Nodo y los siguientes métodos: 

Añadir un elemento al inicio.



Añadir un elemento al final



Añadir un elemento de manera ordenada



Llenar la lista por teclado



Llenar la lista aleatoriamente



Imprimir la lista



Buscar un elemento



Eliminar un elemento por dato



Eliminar un elemento por posicion o índice



Eliminar toda la lista



Invertir una lista



Ordernar una lista



Cargar una lista desde archivo



Guardar la lista en un archivo



Concatenar una lista a otra



Intersección entre 2 listas

Podrán ver la variable *temp en casi todos los métodos , este es el puntero de tipo Nodo que me va a permitir moverme a través de la lista y que inicialmente es igual a la cabeza (head). Mientras exista algo en la lista, voy avanzado el puntero para que apunte al siguiente. Esto se consigue en casi todos los casos con un while.

1 2 3

while (temp) { temp = temp->next; }

Otra operación común en los métodos es preguntar si inicialmente la lista está vacía, es decir, si la cabeza no contiene algo o es igual a Null.

1 2 3

if (!m_head) { ... }

Apliqué mis limitados conocimientos de templates para tener una lista genérica y así pueda funcionar con varios tipos de datos y de verdad funciona. Ahí la definición e implementación de la clase, lista, clase nodo y el main para ver el funcionamiento. Cualquier crítica, sugerencia o comentarios son bienvenidos siempre. node.h #ifndef NODE_H 1 #define NODE_H 2

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include using namespace std; template class Node { public: Node(); Node(T); ~Node(); Node *next; T data; void delete_all(); void print(); }; #endif // NODE_H

22 23 24 node.p

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include "node.h" // Constructor por defecto template Node ::Node() { data = NULL; next = NULL; } // Constructor por parámetro template Node ::Node(T data_) { data = data_; next = NULL; } // Eliminar todos los Nodos template void Node ::delete_all() { if (next) next->delete_all(); delete this; }

// Imprimir un Nodo template void Node ::print() { //cout << "Node-> " << "Dato: " << dato << " Direcion: " << this << " Siguiente: << endl; cout << data << "-> "; } template Node ::~Node() {}

list.h

1 2 3 4

#ifndef LIST_H #define LIST_H #include #include

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <string> #include <stdlib.h> #include "node.h" #include "node.p" using namespace std; template class List { public: List(); ~List(); void void void void void void void void void void void void void void void void

add_head(T); add_end(T); add_sort(T); concat(List); del_all(); del_by_data(T); del_by_position(int); fill_by_(int); fill_random(int); intersection(List); invert(); load_file(string); print(); save_file(string); search(T); sort();

private: Node *m_head; int m_num_nodes; }; #endif // LIST_H

list.p #include "list.h" 1

2 3 4 5 6

using namespace std; // Constructor por defecto template List ::List()

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

{ m_num_nodes = 0; m_head = NULL; } // Insertar al inicio template void List ::add_head(T data_) { Node *new_node = new Node (data_); Node *temp = m_head; if (!m_head) { m_head = new_node; } else { new_node->next = m_head; m_head = new_node; while (temp) { temp = temp->next; } } m_num_nodes++; } // Insertar al final template void List ::add_end(T data_) { Node *new_node = new Node (data_); Node *temp = m_head; if (!m_head) { m_head = new_node; } else { while (temp->next != NULL) { temp = temp->next; } temp->next = new_node; } m_num_nodes++; } // Insertar de manera ordenada template void List ::add_sort(T data_) { Node *new_node = new Node (data_); Node *temp = m_head; if (!m_head) { m_head = new_node; } else { if (m_head->data > data_) { new_node->next = m_head;

54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

m_head = new_node; } else { while ((temp->next != NULL) && (temp->next->data < data_)) { temp = temp->next; } new_node->next = temp->next; temp->next = new_node; } } m_num_nodes++; } // Concatenar a otra List template void List ::concat(List list) { Node *temp2 = list.m_head; while (temp2) { add_end(temp2->data); temp2 = temp2->next; } } // Eliminar todos los nodos template void List ::del_all() { m_head->delete_all(); m_head = 0; } // Eliminar por data del nodo template void List ::del_by_data(T data_) { Node *temp = m_head; Node *temp1 = m_head->next; int cont = 0; if (m_head->data == data_) { m_head = temp->next; } else { while (temp1) { if (temp1->data == data_) { Node *aux_node = temp1; temp->next = temp1->next; delete aux_node; cont++; m_num_nodes--; } temp = temp->next; temp1 = temp1->next; } }

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147

if (cont == 0) { cout << "No existe el dato " << endl; } } // Eliminar por posición del nodo template void List ::del_by_position(int pos) { Node *temp = m_head; Node *temp1 = temp->next; if (pos < 1 || pos > m_num_nodes) { cout << "Fuera de rango " << endl; } else if (pos == 1) { m_head = temp->next; } else { for (int i = 2; i <= pos; i++) { if (i == pos) { Node *aux_node = temp1; temp->next = temp1->next; delete aux_node; m_num_nodes--; } temp = temp->next; temp1 = temp1->next; } } } // Llenar la Lista por teclado template void List ::fill_by_(int dim) { T ele; for (int i = 0; i < dim; i++) { cout << "Ingresa el elemento " << i + 1 << endl; cin >> ele; add_end(ele); } } // Llenar la Lista aleatoriamente para enteros template void List ::fill_random(int dim) { srand(time(NULL)); for (int i = 0; i < dim; i++) { add_end(rand() % 100); } } // Usado por el método intersección template void insert_sort(T a[], int size)

148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194

{ T temp; for (int i = 0; i < size; i++) { for (int j = i-1; j>= 0 && a[j+1] < a[j]; j--) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; } } } // Números que coinciden en 2 Lists template void List ::intersection(List list_2) { Node *temp = m_head; Node *temp2 = list_2.m_head; // Creo otra Lista List intersection_list; int num_nodes_2 = list_2.m_num_nodes; int num_inter = 0; // Creo 2 vectores dinámicos T *v1 = new T[m_num_nodes]; T *v2 = new T[num_nodes_2];

// Lleno los vectores v1 y v2 con los datas de la lista original y segunda list respectivamente int i = 0; while (temp) { v1[i] = temp->data; temp = temp->next; i++; } int j = 0; while (temp2) { v2[j] = temp2->data; temp2 = temp2->next; j++; } // Ordeno los vectores insert_sort(v1, m_num_nodes); insert_sort(v2, num_nodes_2); // Índice del 1er vector (v1) int v1_i = 0; // Índice del 2do vector (v2) int v2_i = 0;

195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241

// Mientras no haya terminado de recorrer ambas Lists while (v1_i < m_num_nodes && v2_i < num_nodes_2) { if (v1[v1_i] == v2[v2_i]) { intersection_list.add_end(v1[v1_i]); v1_i++; v2_i++; num_inter++; } else if (v1[v1_i] < v2[v2_i]) { v1_i++; } else { v2_i++; } } // Solo si hay alguna intersección imprimo la nueva lista creada if (num_inter > 0) { cout << "Existen " << num_inter << " intersecciones " << endl; intersection_list.print(); } else { cout << "No hay intersección en ambas listas" << endl; } } // Invertir la lista template void List ::invert() { Node *prev = NULL; Node *next = NULL; Node *temp = m_head; while (temp) { next = temp->next; temp->next = prev; prev = temp; temp = next; } m_head = prev; } // Cargar una lista desde un archivo template void List ::load_file(string file) { T line; ifstream in; in.open(file.c_str()); if (!in.is_open()) { cout << "No se puede abrir el archivo: " << file << endl << endl; } else { while (in >> line) { add_end(line); } }

242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288

in.close(); } // Imprimir la Lista template void List ::print() { Node *temp = m_head; if (!m_head) { cout << "La Lista está vacía " << endl; } else { while (temp) { temp->print(); if (!temp->next) cout << "NULL"; temp = temp->next; } } cout << endl << endl; } // Buscar el dato de un nodo template void List ::search(T data_) { Node *temp = m_head; int cont = 1; int cont2 = 0; while (temp) { if (temp->data == data_) { cout << "El dato se encuentra en la posición: " << cont << endl; cont2++; } temp = temp->next; cont++; } if (cont2 == 0) { cout << "No existe el dato " << endl; } cout << endl << endl; } // Ordenar de manera ascendente template void List ::sort() { T temp_data; Node *aux_node = m_head; Node *temp = aux_node; while (aux_node) { temp = aux_node; while (temp->next) {

289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335

temp = temp->next; if (aux_node->data > temp->data) { temp_data = aux_node->data; aux_node->data = temp->data; temp->data = temp_data; } } aux_node = aux_node->next; } } // Guardar una lista en un archivo template void List ::save_file(string file) { Node *temp = m_head; ofstream out; out.open(file.c_str()); if (!out.is_open()) { cout << "No se puede guardar el archivo " << endl; } else { while (temp) { out << temp->data; out << " "; temp = temp->next; } } out.close(); } template List ::~List() {}

336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 main.p #include 1

2 3 4 5 6 7

#include "list.h" #include "list.p" using namespace std; int main()

8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

{ List list_1; List list_2; int ele; int dim; int pos; string file_with_list; cout << "Ingresa la dimensión de la lista: " << endl; cin >> dim; list_1.fill_random(dim); cout << "Lista A al inicio " << endl; list_1.print(); cout << "Agrega un elemento por la cabeza: " << endl; cin >> ele; list_1.add_head(ele); list_1.print(); cout << "Lista invertida: " << endl; list_1.invert(); list_1.print(); cout << "Lista ordenada: " << endl; list_1.sort(); list_1.print(); cout << "Agrega un elemento. Será insertado ordenadamente: " << endl; cin >> ele; list_1.add_sort(ele); list_1.print(); cout << "Busca un elemento: " << endl; cin >> ele; list_1.search(ele); cout << "Elimina un elemento por dato: " << endl; cin >> ele; list_1.del_by_data(ele); list_1.print(); cout << "Elimina un elemento por posición: " << endl; cin >> pos; list_1.del_by_position(pos); list_1.print(); cout << "Cargar una lista desde archivo - Ingresa el nombre(Ex: list.txt): " << endl; // El archivo debe estar en el mismo directorio que este programa cin >> file_with_list; list_2.load_file(file_with_list);

55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

cout << "Lista B: " << endl; list_2.print();

cout << "Guardar la lista en un archivo - Ingresa el nombre(Ex: list2.txt): " << endl; cin >> file_with_list; list_2.save_file(file_with_list); cout << "Interseccion entre las listas A y B: " << endl; list_1.intersection(list_2); cout << "Listas A y B concatenadas: " << endl; list_1.concat(list_2); list_1.print(); list_1.del_all(); list_1.print(); return 0; }

cola.h #ifndef COLA_H #define COLA_H /* * Autor: William David Parras Mendez

* Dependencias: nodo.h */

/* Plantilla de clase cola */ template class Cola { private: Nodo * start,* end; /* Apuntadores al inicio y al final de la cola */ int length; /* Longitud actual de la cola */ public: Cola(); /* Constructora */ ~Cola(); /* Destructora */ void push(int); /* Encola un elemento */ int pop(void); /* Desencola un elemento */ int Length(void); /* Devuelve longitud de la cola */ void display(void); /* Muestra la cola */ bool isEmpty(void); };

template Cola ::Cola(){ start = end = NULL; length = 0; }

template void Cola ::push(int value){ Nodo * newNode = new Nodo (); newNode->set_data(value); if(start==NULL){ start = newNode; end = newNode; newNode->set_nxt(NULL); length++; }else{ end->set_nxt(newNode); newNode->set_nxt(NULL); end = newNode;

length++; } }

template int Cola ::pop(){ int value = -1; if(start==NULL) return -1; else{ value = start->get_data(); start = start->get_nxt(); length--; } return value; }

template int Cola ::Length(){ return length; }

template bool Cola ::isEmpty(){ if(start == NULL) return true; else return false; }

template void Cola ::display(){ if(start==NULL) std::cout << "NO DATA"; else{ for(Nodo * seeker = start;seeker != NULL;seeker = seeker>get_nxt()){ std::cout << seeker->get_data() << ", "; }

} } Raw

#endif

funciones.p #include #include "nodo.h" #include "cola.h" #include #include <stdio.h> #include <exception> using namespace std;

/* Prototipos */ /* vacio insert( ,<prioridad del dato>, )

*/

void insert(int,int,Cola *); /* vacio displayC( , ) */ void displayC(Cola *,int); /* entero deleteItem( , ) */ int deleteItem(Cola *,int);

int main(void){ /* Crea un arreglo de colas, cada posicion es una prioridad */ /* Maxima prioridad igual a longitud de arreglo menos uno */ Cola * cola = new Cola [5]; // Prueba de la funcion de insercion insert(3,4,cola); insert(2,4,cola); insert(3,0,cola); insert(5,2,cola); insert(7,1,cola); insert(1,3,cola); insert(8,2,cola); insert(9,1,cola); // Muestra la cola de prioridad actual displayC(cola,5);

// extrae algunos elementos de la cola cout << "Extrayendo elemento: "<<deleteItem(cola,5)<<endl; cout << "Extrayendo elemento: "<<deleteItem(cola,5)<<endl; cout << "Extrayendo elemento: "<<deleteItem(cola,5)<<endl; cout << "Extrayendo elemento: "<<deleteItem(cola,5)<<endl; getchar(); return 0; }

void insert(int data,int priori, Cola * a ){ // Si sale fuera de los limites genera una excepcion try{ // Inserta el dato en la cola almacenada en la prioridad indicada a[priori].push(data); }catch(exception& e){ cout << "OUT OF MEMORY: "; } }

void displayC(Cola * a, int Maxpriori ){ // recorre toda el arreglo de colas for(int i = 0; i < Maxpriori; i++ ){ // para cada cola almacenada llama a su respectivo metodo display a[i].display(); // da un salto, esto permite separar por prioridad // y mostrar una prioridad por lina, si se elimina el salto // se mostrara una sola cadena, esto es opcional cout << endl; } }

int deleteItem(Cola * a, int Maxpriori ){ int i = 0; // Mientras no se llegue al final del arreglo while(i < Maxpriori){ // verifica si la prioridad mas alta esta vacia // si esta vacia entonces avanza a la siguiente // prioridad mas alta

if(a[i].isEmpty()){ i++; }else{ // cuando la prioridad tenga elementos encolados // saca el elemento mas proximo de la cola y lo retorna // por lo tanto se detiene la ejecucion de la funcion return a[i].pop(); } } // en caso que no encuentra elementos retorna -1 esto puede // servir para controlar excepciones return -1; Raw

}

nodo.h #ifndef NODO_H #define NODO_H /* * Autor: William David Parras Mendez * Dependencias: Ninguna */

/* Clase Nodo De un camino*/ /* Pantilla */ template class Nodo { /* Datos privados */ private: Nodo * nxt; /* Apuntador a otro nodo */ T data; /* Dato que Almacena el nodo */ public: /* Prototipos */ Nodo(); /* Constructora */ ~Nodo(); /* Destructora */ void set_data(T); /* Inicializa dato del nodo */

T get_data(void); /* Obtiene Dato almacenado en el nodo */ Nodo * get_nxt(void); /* Enlaza el nodo */ void set_nxt(Nodo *); /* Obtiene el enlace del nodo */ };

/* Inicializa componentes */ template Nodo ::Nodo(){ nxt = NULL; data = 0; }

/* Definicion de la insercion del dato */ template void Nodo ::set_data(T value){ data = value; }

/* Retorna el dato actual almacenado */ template T Nodo ::get_data(){ return data; }

/* Enlaza a otro nodo */ template void Nodo ::set_nxt(Nodo * item){ nxt = item; }

/* Obtiene el enlace del nodo */ template Nodo * Nodo ::get_nxt(){ return nxt; } #endif

3 lines (38 sloc)

1.25 KB

/* * Copyright (C) 2009 Ronny Yabar Aizcorbe * * This program is free software; you can redistribute it and/or modify it * under the and conditions of the GNU Lesser General Public License, * version 2.1, as published by the Free Software Foundation. * * This program is distributed in the hope it will be useful, but WITHOUT ANY * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS * FOR A PARTICULAR PURPOSE.

See the GNU Lesser General Public License for

* more details. * * You should have received a copy of the GNU Lesser General Public License * along with this program; if not, write to the Free Software Foundation, * Inc., 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. */

#include

using namespace std;

// Función factorial con tail recursion int fact_tail_sum(int n, int sum) { if (n == 1) { return sum; } else { return fact_tail_sum(n - 1, sum * n);

} }

// Para mantener la sintaxis original de como se llama a la función factorial int fact_tail(int n) { return fact_tail_sum(n, 1); }

int main() { int num = 0; cout << "Ingresa un nro " << endl; cin >> num; cout << "Su factorial es " << fact_tail(num) << endl; return 0; }

La recursividad es una técnica de programación que consiste en que una serie de instrucciones se repiten como una subtarea de la tarea principal, es decir, las funciones, procesos o rutinas se llaman a sí mismos cada vez que lo requieran y se ejecutan repetidas veces hasta que se satisface una condición específica. Sin embargo, la recursividad en algunos casos, tiene un costo computacional alto, debido a las constantes llamadas a la misma función, rutina y muchas veces estas llamadas consumen demasiada memoria. En algunos algoritmos recursivos, se puede implementar un caso de recursividad especial llamado Tail Recursion (recursividad por cola), la cual es una técnica para optimizar la recursividad eliminando las constantes llamadas recursivas. Tail recursion es cuando la llamada recursiva es la última instrucción de la función. Sin embargo, las funciones tail recursive deben cumplir la condición que en la parte que realiza la llamada a la función, no debe existir ninguna otra sentencia.

Una ventaja de la recursividad por cola es que podemos evitar la sobrecarga de cada llamada a la función y nos evitamos el gasto de memoria de pila. Con una función tail recursive se puede evitar lo que se conoce como stack overflow, que ocurre cuando la pila de llamadas (call stack) consume mucha memoria. Veamos esta técnica con un ejemplo muy conocido que es encontrar el factorial de un número. Esta simple función obtiene el factorial de un número de la manera recursiva convencional: La explicación es sencilla, llamamos a la misma función fact hasta que n sea igual a 1, en ese momento la recursividad se detiene.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int fact_recursivo(int n) { if(n == 1) return n; else return n * fact_recursivo(n-1); } int main() { int num = 0; cout << "Ingresa un nro " << endl;

cin >> num;

cout << "Su factorial es " << fact_recursivo(num); return 0; }

Digamos que ingresé 15, si compilamos el programa la función me daría 2004310016, lo cual es correcto, pero hay que tener en cuenta todas las llamadas recursivas que hizo la función fact_recursivo, es decir, la función tiene que calcular el factorial de 14 y este el fact de 13, y este el fact de 12… sucesivamente hasta 1. Tenemos un crecimiento del número de llamadas recursivas. Ahora vamos a realizar la misma función usando tail recursion. En este caso no se necesita guardar un marco de pila para cada llamada recursiva, y el algoritmo se comporta como si fuera iterativo. Para conseguir esto usamos un parámetro adicional que actúa como acumulador. Esta sería la función factorial con tail recursion:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

// Función factorial con tail recursion int fact_tail_sum(int n, int sum) { if (n == 1) { return sum; } else { return fact_tail_sum(n - 1, sum * n); } } // Para mantener la sintaxis original de como se llama a la función factorial int fact_tail(int n) { return fact_tail_sum(n, 1); } int main() { int num = 0;

15 16 17 18 19 20 21

cout << "Ingresa un nro " << endl; cin >> num; cout << "Su factorial es " << fact_tail(num) << endl; return 0; }

El resultado igualmente sería 2004310016, pero el costo computacional baja drásticamente debido a que cuando se hace la llamada return fact_tail_sum(n – 1, sum*n) ambos parámetros son inmediatamente resueltos. Con esta llamada podemos calcular sin esperar una llamada a una función recursiva para que nos devuelva un valor. En este caso el compilador reduce drásticamente el uso de la pila y la cantidad de información que debe ser almacenada, el valor de n y sum es independiente del número de llamadas recursivas. Una función recursiva normal se puede convertir a tail recursive usando en la función original un parámetro adicional, usado para ir guardando un resultado de tal manera que la llamada recursiva ya no tiene una operación pendiente. También se usa una función adicional para mantener la sintaxis de como llamamos normalmente a la función. En el caso del factorial, para seguir llamando a la función de la forma fact(n). En conclusión: • Una llamada es tail recursive (recursiva por cola) si no tiene que hacer nada más después de la llamada de retorno. • Tail recursion es cuando la llamada recursiva es la última instrucción en la función. • Usar tail recursion es muy ventajoso, porque la cantidad de información que debe ser almacenada durante el cálculo es independiente del número de llamadas recursivas. • El compilador trata una función tail recursive como si fuera una función iterativa. El código fuente de este y otros ejercicios de C++ está disponible en Github: https://github.com/ronnyml/C---Tutorial Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace: Report this ad Report this ad

Related

Quicksort en C++In "C++" Listas en HaskellIn "Haskell" Vectores, Matrices y Punteros en c++In "C++" Written by Ronny Yabar May 19, 2009 at 10:30 pm Posted in C++ Tagged with C++, Recursividad, Tail Recursion, Tail Recursion en C++ « La senda del Líder del Dalai Lama Vectores, Matrices y Punteros en c++ »

7 Responses Subscribe to comments with RSS. 1.

En que casos específicos es bueno utilizar la recursividad, ya que dijeron que consume mucha memoria.

#include <stdio.h> #include <stdlib.h>

/* DECLARACIÓN DE TIPOS */ typedef char elemento; struct NODE{ elemento info; struct NODE *sgte; }; typedef struct NODE nodo; typedef struct NODE *posicion; /* La cola es un puntero a nodo */ typedef struct { int longitud; posicion prim, ult; }COLA;

/* DECLARACIÓN DE FUNCIONES */ int vacia(COLA); int queue(COLA *, elemento); int dequeue(COLA *, elemento *); int mostrar_cola(COLA); int borrar_cola (COLA*); void crear_cola(COLA *); int llena(posicion *); int tamagno(COLA);

main(){

int opcion; COLA C; elemento x;

C.longitud=-1;

printf("\n Este programa realiza las siguientes operaciones con pilas:\n");

do{

printf ("\n 1: Crear cola.\n 2: Encolar.\n 3: Desencolar.\n 4: Ver elementos.\n 5: Borrar cola. \n 6: Salir. \n Seleccione la operacion que desea realizar: "); scanf(" %d", &opcion);

switch(opcion){ case 1: crear_cola(&C); break; case 2: printf("\n Dame el elemento a meter: ");do scanf("%c",&x);while(x=='\n');queue(&C,x);break; case 3: dequeue(&C,&x); break; case 4: mostrar_cola(C);break; case 5: borrar_cola(&C);break; case 6: break; default: printf("\n Error, ha de introducir un numero del 1 al 6.\n"); } printf("\n Pulsa [ENTER] para continuar..."); getchar();getchar(); }while (opcion!=6); }

/* FUNCIONES */

/* Función que inicializa la cola */ void crear_cola(COLA *C){ (*C).prim=NULL; (*C).ult=NULL; (*C).longitud=0; printf("\nSe ha creado una cola vacia\n"); }

/* Función que averigua si hay algún elemento en la cola */ int vacia (COLA C){ if (C.longitud<0) return -1; else{ if (C.longitud==0) return 1; else return 0; } }

/* Esta función devuelve 1 si no se puede reservar más memoria */ int llena(posicion *tmp){ *tmp=(nodo*)calloc(1,sizeof(nodo)); if ((*tmp)==NULL)

return 1;

else return 0; }

/* Función que devuelve el tamaño de la cola */ int tamagno(COLA C){ return C.longitud; }

/* Función que inserta elementos en la cola */ int queue (COLA *C, elemento x){ posicion tmp;

if (vacia(*C)<0){ printf("\nError, debe crear una cola\n"); return 0; } else { if (llena(&tmp)){ printf("\n Error: no se puede reservar mas espacio"); return 0; } else{ /* Se ha reservado espacio y se procede con la inserción */ (*tmp).info=x; (*tmp).sgte=NULL; /* Al ser el último elemento de la cola,no hay más después */ if(vacia(*C)==1) (*C).prim=tmp; /* Si además la cola está vacía, también será el primero */ else if(vacia(*C)==0) (*C).ult->sgte=tmp; /* Se inserta a continuación del último */ (*C).ult=tmp;/* Pues erá el último elemento de la cola */ (*C).longitud=(*C).longitud+1; /* Ahora hay un elemento más en la cola */ return 1; }

} }

/* Función que saca elementos de la cola */ int dequeue(COLA *C, elemento *x){ posicion tmp; if (vacia(*C)<0){ printf("\nError, debe crear una cola\n"); return 0; } else{ /* Ya existe una cola */ if (vacia(*C)==0) { /* Hay algún elemento que sacar */ tmp=(*C).prim; *x=tmp->info; if(tamagno(*C)==1) /* Sólo hay un elemento */ (*C).ult=NULL; /* La cola queda vacía */ (*C).prim=tmp->sgte; /* El siguiente del primero pasa a ser el nuevo primer elemento */ free(tmp); /* Se libera la memoria que ocupaba el nodo */ (*C).longitud=(*C).longitud-1; /* Ahora hay un elemento menos en la cola */ //printf("\n El elemento desencolado es: '%c'\n",x); //printf("\nLa longitud de la cola es: %d\n", (*C).longitud); return 1; } else{ /* No hay elementos que sacar */ printf("\nLa cola esta vacia\n"); return 0;

} } }

/* Función que muestra los elementos que hay en la cola */ int mostrar_cola (COLA C){ posicion aux; int longitud;

longitud=tamagno(C); /* Es el número de elementos que hay que mostrar */ aux=C.prim; /* aux apunta al primer elemento de la cola */

if (longitud<0){ printf("\nError, debe crear una cola\n"); return 0; } else{ /* Ya existe una cola */ if (longitud==0){ /* No hay elementos que mostrar */ printf("\n La cola esta vacia.\n"); return 0; } else{ printf("\n"); while(longitud>0){ /* Mientras haya elementos en la cola,los muestra */ printf(" '%c' ", aux->info); //printf(" longitud--;

'%s'

", aux->info);

aux=(*aux).sgte; /* aux avanza al siguiente elemento */ } return 1; } } }

/* Función que borra los elementos de la cola */ int borrar_cola (COLA *C){ elemento x; if (vacia(*C)<0){ /* No existe ninguna pila que borrar */ printf("\nError, debe crear una cola\n"); return 0; } else{ /* Existe una pila */ if(vacia(*C)==1) return 0; /* No hay nada que mostrar */ else { while(vacia(*C)==0){ /* Mientras haya elementos, los sacamos */ dequeue(C,&x); } return 1; } } } #include using namespace std; class NodoEntero{//CLASE NODOENTERO// private:

int valor; NodoEntero *siguiente; public: NodoEntero(int valor){ this->valor=valor; this->siguiente=NULL; } //METODOS SET Y GET// void setValor(int valor){ this->valor=valor; } void setSiguiente(NodoEntero*siguiente){ this->siguiente=siguiente; } int getValor(){ return valor; } NodoEntero* getSiguiente(){ return siguiente; } };//FIN CLASE// class Cola{ private: NodoEntero *frente; NodoEntero *final; public: Cola(){//CONSTRUCTOR// this->frente=NULL; this->final=NULL; } bool estaVacio(){ return frente=NULL; } int obtenerValor(){ return frente->getValor(); } void meter(int valor){ NodoEntero *nuevoNodo = new NodoEntero(valor); if(estaVacio()){ frente=nuevoNodo; final=nuevoNodo; }else{ final->setSiguiente(frente); final=nuevoNodo; } } int sacar(){ NodoEntero *apuntadorNodo= frente; int valor=frente->getValor();

frente=apuntadorNodo->getSiguiente(); delete (apuntadorNodo); return valor; } void mostrar(){ NodoEntero *apuntadorNodo=frente; while(apuntadorNodo!=NULL){ cout<<" "< getValor(); apuntadorNodo=apuntadorNodo->getSiguiente(); } } };

El error que estoy teniendo al llamar a mostrar( ) es que entro en un bucle infinito, y no para al llegar al último elemento de la lista. c++

compartirmejorar esta pregunta editada el 25 sep. 17 a las 17:26

Trauma 10.1k21243 formulada el 25 sep. 17 a las 15:26

José A. Solís 227

añade un comentario

1 respuesta activasmás antiguas

votos

voto a favor3votar en contra

Tienes 2 fallos: bool estaVacio( ) { return frente = NULL; }

aceptada

Eso que haces es una asignación. Para comparar, sería return frente == NULL;

El otro fallo es: void meter( int valor ) { NodoEntero *nuevoNodo = new NodoEntero( valor ); if( estaVacio( ) ) { frente = nuevoNodo; final = nuevoNodo; } else { final->setSiguiente( frente ); final = nuevoNodo; } }

Lo que haces en el else es crear una lista circular. Los nodos se apuntan en bucle unos a otros, haciendo imposible que se pueda recorrer. Lo correcto sería } else { final->setSiguiente( nuevoNodo ); final = nuevoNodo; } compartirmejorar esta respuesta editada el 25 sep. 17 a las 20:18 respondida el 25 sep. 17 a las 17:24

Trauma 10.1k21243

añade un comentario

Programación en C++/Librería Estándar de Plantillas/Colas < Programación en C++ | Librería Estándar de Plantillas

Editores: Oscar E. Palacios

← Librería Estándar de Plantillas Sumario [ocultar]    

1C++ queue estándar 2Colas con prioridad 3Copia de contenedor 4Métodos

C++ queue estándar[editar] Una cola (queue) es una estructura en donde los elementos son insertados en el inicio (front) de la misma, y retirados al final de la misma, debido a ello el comportamiento de una cola se conoce como FIFO ( primero en entrar, primero en salir ). Ver Estructuras II

La Libreria estándar de plantillas soporta el uso de estructuras de cola a travez de la plantilla de clase queue, la cual posee el mecanismo de operación necesario para manejar operaciones de insertar (push), borrar(pop), entre otras. La clase queue posee únicamente seis métodos y dos constructores. En seguida se presenta un ejemplo sumamente básico, el cual consiste en crear una cola para contener elementos de tipo char. Los caracteres se introducen en orden desde la 'A' hasta la 'Z' y, tal como tiene que ser, al recuperarlos se obtienen en el orden ingresados, o sea, desde la 'A' hasta la 'Z'. En el programa se debe observar que, se usa el método push para agregar componentes a la lista; el método front regresa una referencia al elemento que se encuentra en el inicio de la cola y este es usado para leer y desplegar el carácter; y se emplea el método pop para eliminar el elemento que está en el frente de la cola. // programa: cola01.p // un simple ejemplo del uso de la plantilla queue #include #include #include using namespace std; int main(int argc, char *argv[]) { queue s;

for (int i='A'; i <= 'Z'; i++) s.push(i); while (! s.empty() ) { cout << s.front() << " " ; s.pop(); } cout << endl; system("PAUSE"); return EXIT_SUCCESS; }

Colas con prioridad[editar] Las colas prioritarias ( priority_queue ) de la STL de C++ son parecidas a las colas, con la diferencia de que en estas los elementos se ordenan mediante algun predicado. Aunque se ha dicho que las colas prioritarias son parecidas a las colas, su comportamiento es diferente, ya que en una priority_queue no se cumple el algoritmo FIFO. Por ejemplo, en el siguiente programa se puede observar como se insertan de manera no ordenada elementos a la lista por medio de push, los cuales al ser recuperados se presentan en orden. #include #include #include using namespace std; void cola01() { priority_queue p; // insertar elementos p.push(100); p.push(35); p.push(12); p.push(200); // mostrar elementos while (! p.empty() )

{ cout << p.top() << endl; p.pop(); } cout << endl; } int main(int argc, char *argv[]) { cola01(); system("PAUSE"); return EXIT_SUCCESS; }

La salida del programa anterior es: 200 100 35 12

y se debe al hecho de que por defecto la función o predicado que compara los elementos de la priority_queue es menor (less). Ahora bien, el predicado puede ser cambiado para que la comparación se mayor (greater) y para lograrlo se debe de usar una plantilla basada en la clase vector o en la clase deque. El programa que se mostrará en seguida es un ejemplo de como usar la clase deque para declarar una priority_queue. #include #include #include using namespace std; void cola02() { cout << "test 02" << endl; priority_queue , greater > p; p.push(100); p.push(35); p.push(12);

p.push(200); while (! p.empty() ) { cout << p.top() << endl; p.pop(); } cout << endl; } int main(int argc, char *argv[]) { cola02(); system("PAUSE"); return EXIT_SUCCESS; }

La salida del programa anterior es: 12 35 100 200

Copia de contenedor[editar] La magia de una priority_queue nos permite usar un constructor para obtener una copia ordenada de un contenedor ( vector, deque ). Así, en el siguiente ejemplo se muestra como crear una copia de un vector. El resultado es una priority_queue conteniendo en orden a todos los elementos del vector original. Veamos. #include #include #include #include using namespace std;

// declaración de tipo typedef priority_queue<string, vector<string>, greater<string> > STRPQUE; int main(int argc, char *argv[]) { vector<string> v; v.push_back("pera"); v.push_back("uva"); v.push_back("manzana"); v.push_back("banana"); v.push_back("coco"); vector<string>::iterator it = v.begin(); cout << "Contenido del vector" << endl; while (it != v.end() ) cout << "\t" << *it++ << endl; STRPQUE p( v.begin(), v.end() ); cout << "\nContenido de la priority_queue" << endl; while (! p.empty() ) { cout << "\t" << p.top() << endl; p.pop(); } cout << endl; system("PAUSE"); return EXIT_SUCCESS; }

Si se compila y ejecuta el programa anterior, la salida en pantalla resultante será: Contenido de la priority_queue banana coco manzana

pera uva

esto, a pesar de que el predicado ( greater<string> ), usado en la declaración de tipo, indica que los elementos se deben ordenar atendiendo al resultado de una comparación ( mayor que ). El hecho de tales resultados se debe a la naturaleza misma de la priority_queue, es decir, los elementos en esta están realmente ordenados de mayor a menor pero del inicio al fin, luego, como la orden top() regresa una referencia al último elemento de la cola, se obtiene asi un listado de los elementos ordenados de menor a mayor.

Introducción Cada objeto del TDA Cola, modela una cola de elementos de la clase T, una cola es un tipo particular de lista en la que los elementos se insertan por un extremo (el final) y se consultan y suprimen por el otro (cabecera). Son listas del tipo FIFO (First In, First Out).

Son objetos mutables, residen en memoria dinámica.

Primitivas de la cola

Dentro del TDA Cola hemos propuesto las siguientes primitivas, aunque esto no quiere decir que sean las mejores ni las más adecuadas para todos los casos:



Cola () -> constructor primitivo, nos crea una cola vacía.

 p.

Cola (const Cola &c) -> constructor de copia, crea una cola que es copia

PARÁMETROS : c -> cola que se copia.

 Bool vacia () const -> informa si la cola está vacía, devuelve true si la cola está vacía, false en otro caso.

 T& cabecera () -> al elemento al principio de la cola, devuelve una referencia al elemento en la cabecera de la cola.

 Void poner (const T & elem) -> añade un elemento en la cola, inserta un nuevo elemento al final de la cola. PARÁMETROS : elem -> elemento que se inserta.

 Void quitar () -> quita un elemento de la cola, elimina el elemento en la cabecera de la cola. PRECONDICIÓN : el receptor no puede estar vacío.

 Int num_elementos () -> obtiene el número de elementos incluidos en la cola.

 ~Cola () -> destructor, el receptor es destruido liberando todos los recursos que usaba. POSTCONDICIÓN : el receptor es modificado.

Ejemplos de uso

En este apartado vamos a mostrar un ejemplo para que comprendamos el funcionamiento de las primitivas del TDA Cola:

Rotar una cola

La función rota una cola un número n de veces,si está vacía la función no hace nada. Cola c; void rotar (int n) { int nrotaciones, e; if (!c.vacia ()) { nrotaciones = n % c.num_elementos(); for (int i = 0; i < nrotaciones; i++) { e = c.cabecera (); c.quitar (); c.poner (e); } } }

Implementación de las colas

Implementación enlazada Igual que en el caso de las pilas, cualquier implementación de listas es válida para las colas. No obstante, para aumentar la eficiencia de poner es posible aprovechar el hecho de que las inserciones se efectúan sólo en el extremo posterior de forma que en lugar de recorrer la lista de principio a fin cada vez que desea hacer una inserción se puede mantener un apuntador al último elemento, como en las listas de cualquier clase, tambien se mantiene un puntero al frente de la lista, aquí ese puntero es útil para ejecutar mandatos del tipo cabecera o quitar. Utilizaremos al igual que para las listas, un nodo de cabecera con el puntero frontal apuntándola con lo que nos permitirá un manejo más cómodo.

Puesto que esta implementación se basa en una lista la cola es una lista de tipo T con todos sus componentes.

Veamos la especificación de la función de abstracción y el invariante de la representación de este tipo de cola:

Función de Abstracción Dado el objeto del tipo rep r, el objeto abstracto al que representa es: c = l, con la cabecera de la cola en la posición l.primero () y el final en la posición l.final ().

Invariante de Representación true.

De manera que la clase Cola (con implementación enlazada) en C++ tendría el siguiente aspecto: Class Cola {

Public: Cola (); Cola (const Cola &c); bool vacia () const; T& cabecera (); void poner (const T& elem); void quitar ();

int num_elementos () const; ~Cola ();

Private: Lista cola;

}

Pasemos ahora a ver la implementación de cada una de las primitivas enunciadas con anterioridad en C++:

template

inline Cola ::Cola() { }

template

inline Cola ::Cola(const Cola & c) : cola(c.cola) { }

template

inline bool Cola ::vacia() const { return cola.vacia(); }

template inline T& Cola ::cabecera() { return cola.elemento(cola.primero()); }

template

inline void Cola ::poner(const T & elem) { cola.insertar(cola.final(), elem); }

template

inline void Cola ::quitar() { cola.borrar(cola.primero()); }

template inline int Cola ::num_elementos() const { return cola.num_elementos(); }

template inline Cola ::~Cola() { }

Implementación mediante matrices circulares La implementación matrical de las listas no es muy eficiente para las colas, puesto que si bien con el uso de un apuntador al último elemento es posible ejecutar poner en un tiempo constante, quitar que suprime le primer elemento, requiere que la cola completa ascienda una posición en la matriz con lo que tiene un orden de eficiencia lineal proporcional al tamaño de la cola. Para evitarlo se puede adoptar un criterio diferente, imaginemos a la matriz como un circulo en el que la primera posición sigue a la última, la cola se encuentra en alguna parte de ese círculo ocupando posiciones consecutivas.

Tenemos pues un vector elementos con los elementos de la cola, Lmax que denota el número de posiciones que tiene la cola y los punteros post y ant.

Para insertar un elemento en la cola se mueve el puntero post una posición en el sentido de las agujas del reloj y se escribe el elemento en esa posición, veámoslo en la siguiente figura.

Para suprimir un elemento simplemente se mueve ant una posición en el sentido de las agujas del reloj, de esta forma, la cola se mueve en ese sentido conforme se insertan y suprimen elementos, veámoslo.

Obsérvese que utilizando este modelo los procedimientos poner y quitar se pueden implementar de manera que su ejecución se realice en tiempo constante.

Existe un problema que aparece en la representación y en cualquier variación menor de esta estrategia (por ejemplo que post apunte a la última posición en el sentido de las agujas del reloj), el problema es que no hay forma de distinguir una cola vacia de una que llene el círculo completo salvo que mantengamos un bit que sea verdad si y solo si la cola está vacia., si no deseamos mantener este bit debemos prevenir que la cola llene alguna vez la matriz.

Para ver por qué puede pasar esto, supongamos que la cola de la figura anterior tuviera MAX_LONG elementos, entonces, post apuntaría a la posición anterior en el sentido de las agujas del reloj de ant, ¿qué pasaria si la cola estuviese vacia?, para ver como se representa una cola vacia, consideramos primero una cola de un elemento, entonces post y ant apuntarian a la misma posición, si extraemos un elemento, ant se mueve una posición en el sentido de las agujas del reloj, formando una cola vacia., por tanto una cola vacia tiene post a una posición de ant en el sentido de las agujas del reloj, que es exactamente la misma posición relativa que cuando la cola tenia MAX_LONG elementos, por tanto vemos que aún cuando la matriz tenga MAX_LONG

casillas, no podemos hacer crecer la cola más allá de MAX_LONG-1 casillas, a menos que introduzcamos un mecanismo para distinguir si la cola está vacía o llena.

Veamos la especificación de la función de abstracción y el invariante de la representación de este tipo de cola:

Función de Abstracción Dado el objeto del tipo rep r, r = {elementos, Lmax, ant, post}, el objeto abstracto al que representa es: Si r.ant == (r.post + 1) % r.Lmax, entonces c = <>

En otro caso : c = < r.elementos[r.ant], r.elementos[(r.ant+1) % r.Lmax],..., r.elementos[r.post] >

Invariante de Representación 0 < r.Lmax.

0 <= r.ant < r.Lmax.

0 <= r.post < r.Lmax.

r.post != r.post.

r.elementos apunta a una dirección con espacio para al menos r.Lmax componentes.

De manera que la clase Cola (con implementación basada en matrices circulares) en C++ tendría el siguiente aspecto: Class Cola {

Public: Cola (int LongMax = 100); Cola (const Cola &c); bool vacia () const; T& cabecera (); void poner (const T& elem); void quitar (); int num_elementos () const; ~Cola ();

Private: T *elementos; const int Lmax; int ant; int post;

bool llena () const; }

Pasemos ahora a ver la implementación de cada una de las primitivas enunciadas con anterioridad en C++:

template

inline Cola ::Cola(int LongMax) : Lmax(LongMax + 1) { elementos = new T [LongMax + 1]; assert(elementos != 0); ant = 0; post = Lmax -1; }

template

inline Cola ::Cola(const Cola & c) : Lmax(c.Lmax) {

ant = c.ant; post = c.post; elementos = new T [Lmax]; assert(elementos != 0); for (int i = ant; i != post; i = (i + 1) % Lmax) elementos[i] = c.elementos[i]; elementos[post] = c.elementos[post]; }

template inline bool Cola ::llena() const { return ((post + 2) % Lmax) == ant; }

template inline bool Cola ::vacia() const { return ((post + 1) % Lmax) == ant; }

template inline T& Cola ::cabecera() { return elementos[ant]; }

template

inline void Cola ::poner(const T & elem) { assert(!llena()); post = (post + 1) % Lmax; elementos[post] = elem; }

template

inline void Cola ::quitar() { assert(!vacia()); ant = (ant + 1 ) % Lmax; }

template inline int Cola ::num_elementos() const { if (vacia()) return 0; if (post > ant) return post - ant + 1; else

return (Lmax - ant + 1) + (post + 1); }

template inline Cola ::~Cola() { delete [] elementos; }

Colas En C 2d5n2h

Overview 26281t

More details 6y5l6z

Related Documents 3h463d

Colas Dobles En C 572i6o

Colas En C Ejemplo 4n3d69

Colas En C 2d5n2h

Pilas Y Colas En Lenguaje C++ 3g3m

Ejercicios Colas 172g48

Ejercicios Pilas Y Colas En Java 6k1c5q

More Documents from "Winny lesly" 6o5g1g

Colas En C 2d5n2h

19 Sumber Makanan Yang Mengandung Kalsium Tinggi Selain Susu 4h37d

Etika Enjiniring 4y3d6t

4p345f

Don Sanguchon Finallllllll 4c121x

Monografia De Power Point z553a