Ejercicio usando Colas en C++

[RGT]

Hola amigos,
Resulta que tengo que hacer esto:

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 [Seleccionar] Expandir


#include <iostream>
#include <stdlib.h>     // Librería para usar la función srand()
#include <time.h>       // 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;
}


Screenshot:


Vamos bien, ahora la pregunta es:

• Cómo inserto los números en la Cola?.
  
• Cómo es eso de prioridad?.
  
• Cómo hago para que el número de dos dígitos se guarde antes que los de tres dígitos?
  

Bueno, nunca había visto Colas, espero puedan ayudarme, gracias.

[avesudra]

Hola RGT a ver, como ya habrás investigado una cola no es más que una estructura de datos de tipo FIFO, First in First Out. La aproximación que haces con la estructura nodo que has creado ahí es la ideal,
ahora bien ¿y cómo hago las funciones de insertar/sacar etc...?

Fíjate que en la cola lo que siempre tienes que saber es quién es el primero y quién es el último, ¿cómo haces eso? pues si quieres te creas otra estructura tal que así:

Código (cpp) [Seleccionar] Expandir

typedef struct _nodo {
  int dato;
  struct _nodo *siguiente;
} tipoNodo;

typedef struct _cola{
  tipoNodo *primero;
  tipoNodo *ultimo;
} tipoCola;


Para hacer la función de insertar lo que tienes que hacer es crearte un nuevo nodo que apunte al primero de la cola, pero ahora el primero de la cola pasa a ser el último que has creado. Digamos que tienes que hacer:

Código [Seleccionar] Expandir

Crea Nodo
Campo siguiente del nodo creado apunta a cola->primero
Primero ahora apunta al nodo que acabamos de crear


Tienes que tener cuidado porque el primer nodo que crees es el primero y el último y además el siguiente es NULL ya que no hay más nodos.

La función de sacar te la dejo a tí.

Lo demás ahora mismo no tengo tiempo para darte una explicación detallada pero,en las colas con prioridad cada nodo lleva asociada una prioridad y entonces tienes dos maneras de implementarlas:

• Con una lista ordenada, esto tiene el problema de que para sacar el elemento de máxima prioridad tendras un coste de O(1), sin embargo si lo que quieres es insertarlo, como la lista está ordenada vas a tener un coste de O(n) en el peor de los casos.
• Con una lista desordenada pasa al contrario para insertar tendrías un coste de O(1) ya que insertas al principio sin preocuparte por el orden, pero para sacar el máximo vas a tener que buscarlo con un coste de O(n).

Creo que esto contesta a la tercera pregunta, ya que vas a tener que decidir entre los dos y el enunciado problema es claro en esto.

En cuanto a la implementación te recomiendo que uses las clases de C++ (si te dejan) y si te dejan también podrías usar las plantillas.

Un saludo.

[RGT]

Hola, gracias por tratar de ayudarme bro.

Leyendo la documentacion, realmente no entiendo mucho.
Nunca habia visto este tema y estoy muy confundido. Ni siquiera se por que es util esto de Colas. Leyendo en internet solo veo cosas ya hechas, no hay explicaciones....

Lo que me dices que debo de hacer lo entiendo, pero como?, no se ni por donde empezar.

[avesudra]

Las colas se suelen utilizar por ejemplo para programar un planificador de tareas de un sistema operativo. Para que el primer programa que entre a ejecutarse sea el ultimo que salga y tenga una respuesta coherente, luego hay modificaciones como las colas de prioridad, ya que si al sistema operativo se le cruza algo importante lo tiene que insertar en el lugar correcto para que se ejecute lo antes posible.

¿Has programado alguna vez en C++ o te lo han soltado así porque sí?

Manejo de memoria.
Punteros...

Solo tienes que ir creando nodos con el operador new e ir metiendo datos y enlazando los nodos unos con otros por lo menos para la de insertar.

¿No has visto nunca nada de Estructuras de Datos? Pilas, Listas, Listas doblemente enlazadas, Listas circulares...

Es que la idea de estas cosas es que intentes hacer algo aunque te falle, pero entiendo que si ves C++ por primera vez o incluso C te acojone bastante.

Un saludo.

[RGT]

Las colas se suelen utilizar por ejemplo para programar un planificador de tareas de un sistema operativo. Para que el primer programa que entre a ejecutarse sea el ultimo que salga y tenga una respuesta coherente, luego hay modificaciones como las colas de prioridad, ya que si al sistema operativo se le cruza algo importante lo tiene que insertar en el lugar correcto para que se ejecute lo antes posible.

¿Has programado alguna vez en C++ o te lo han soltado así porque sí?

Manejo de memoria.
Punteros...

Solo tienes que ir creando nodos con el operador new e ir metiendo datos y enlazando los nodos unos con otros por lo menos para la de insertar.

¿No has visto nunca nada de Estructuras de Datos? Pilas, Listas, Listas doblemente enlazadas, Listas circulares...

Es que la idea de estas cosas es que intentes hacer algo aunque te falle, pero entiendo que si ves C++ por primera vez o incluso C te acojone bastante.

Un saludo.

He programado cosas en C++ en esta materia, pero nunca nada con Colas y no entiendo ni la pepa, sigo leyendo y eso pero es todo confuso.

[furciorifa]

Dedicate a otra cosa, quizá la programación no es para tí, o ve vídeos en Inglés, colas está muy fácil, en fin.

Tienes como entrada los siguientes números 1 4 6 0 19

La cola introduciría 1 -> 4 -> 6 ->0 ->19->NULL,

Necesitas entender el concepto de estructura autoreferenciada:

struct nodo{
     int dato;
    struct nodo* ptrAnododelmismotipo;

}



Dicho esto tendríamos algo así

[dato entero] [apuntador a otro nodo]->

el primero lo haces NULL quedaría así
[dato entero1]

• ->NULL
  
  después cuando introduces otro dato tendrías hacer esto
  [datoentero1]
• -> [datonuevo]
• ->NULL
  Y así es para cualquier nodo entrante.

[RGT]

Hola amigos, gracias a la documentación en la web oficial de C++, he logrado esto:

Código [Seleccionar] Expandir

#include <iostream>
#include <stdlib.h>     // Librería para usar la función srand()
#include <time.h>       // Librería para usar la función time()
#include <queue>        // Librería para el uso de priority_queue
#include <vector>       // Librería para el uso de vectores (Arreglos Dinámicos)

/*
    Escriba un programa para ejecutar el experimento siguiente:

    1. Genere 100 números aleatorios con valores en el rango entre 1 y 500.

    2. Conforme se genera cada número, insértelo en una cola inicialmente vacía.

    3. Si el número es de dos dígitos, tiene prioridad sobre números de tres dígitos.

    4. 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.
*/

using namespace std;

int main()
{
    //Declaración de variables
    int i, Numero;
    srand(time(NULL));

    priority_queue<int> numero_aleatorio;

    //Procesamiento
    for(i = 1; i <= 100; i++)
    {
        //Generamos un número aleatorio del 1 al 500
        Numero = 1 + rand() % (501 - 1);

        //Guardamos el número generado
        numero_aleatorio.push(Numero);
    }

    while (!numero_aleatorio.empty())
    {
        cout << numero_aleatorio.top() << ", ";
        numero_aleatorio.pop();
    }

    return 0;
}


El ejercicio casi esta resuelto.

Lo único que no tengo ni idea de como hacerlo es de imprimir las posiciones del numeros mayor y del numero de menor valor, segun dice el ejercicio.

Alguien puede ayudarme?.

[RGT]

Dedicate a otra cosa, quizá la programación no es para tí, o ve vídeos en Inglés, colas está muy fácil, en fin.

Gracias por esas palabras. Para una persona que lleva pocas semanas en C++, if, else, do, while, for, entender esto de colas y estructuras y punteros se hace difícil al inicio. Y mas cuando tienes profesores que no te explican nada o personas como tú que te ayudan mucho con el apoyo que te ofrecen.

Se agradece de todas formas tu ayuda, aunque no fue la mejor introducción admito. Para ti pueda que sea fácil porque ya lo entiendes, y para los nuevos que?, todos deberíamos dejar esto entonces?. Creo que tu posición no es la mejor, pero en fin como dices.. Gracias.

[avesudra]

Dedicate a otra cosa, quizá la programación no es para tí, o ve vídeos en Inglés, colas está muy fácil, en fin.

Tú humildad brilla por su ausencia, no veo que haces respondiendo mensajes aquí, ya que sabes tanto y todo es tán fácil podrías crear una empresa y ahogarte en ego.

He programado cosas en C++ en esta materia, pero nunca nada con Colas y no entiendo ni la pepa, sigo leyendo y eso pero es todo confuso.

Mmmm vale, pero ¿te decían que tenías que implementar el TAD(tipo abstracto de dato) o podías usar el de la STL de C++?

De todas maneras si haces lo que pone ese código, vas a ver que te van a salir todos los números aleatorios que has creado de mayor a menor (por defecto el constructor de la clase priority_queue toma std::less<T> como comparación para insertar los elementos). Es decir que para sacar el mayor tienes que hacer un solo pop y para sacar el menor tendrás que quedarte con el último elemento que salga antes de que la cola se quede vacía.

El problema es que la prioridad de esa cola no está bien de momento, ya que los introduce en orden, pero no los de dos cifras primero y los de 3 después.

Te estoy dando pistillas, pero así cuando tengas que hacerlo otra vez ya sabrás como hacerlo perfectamente. Inténtalo y cuando tengas algo pasas por aquí y lo vemos, si tienes tiempo antes de entregarlo claro.

En cuanto a lo que ha dicho furciorifa, aquí en España solemos decir que "A palabras necias, oídos sordos".

Un saludo.