Examen Parcial - 75.41. Algoritmos y Programación II

Cátedra: Mandrafina
Fecha: Primera Oportunidad - Segundo Cuatrimestre 2004
Día: 08/10/2004

Dado el siguiente programa se requiere indicar lo que se mostraría por pantalla:

#include <iostream> 
using namespace std; 
 
int main(){ 
    int *A, *C; 
    int **B; 
    char *D, *E, *F; 
    char G; 
    int H; 
 
    H = 15; 
    G = 'B'; 
    A = new int();
 
    *A = 64; 
    cout << H << G << *A << endl; 
    B = &A; 
    cout << **B << endl; 
    D = (char*) A; 
    C = (int*) D; 
    cout << *D << *C << endl; 
    delete A; 
    if ( *D == '?' ) { 
        cout << G << H << endl; 
    } 
} 
 

¿Qué es programación por contrato? Explique los conceptos de precondición, postcondición y axioma, dentro de la teoría de Tipos de Datos Abstractos.

Construtir un TDA ConsultaCompetidor que permita acceder a la información del siguiente archivo:

Las primitivas que debe ofrecer son (agregue las que considere necesarias):

• obtenerTiempoPromedio( ConsultaCompetidor cc )
• obtenerCompetidorMejorTiempo(ConsultaCompetidor cc )
• obtenerCompetidorPeorTiempo(ConsultaCompetidor cc )
• obtenerCompetidor(ConsultaCompetidor cc, int nroCompetidor )

La implementación del TDA puede hacer con la estructura de datos que se considere conveniente, pero deben especificarse e implementarse todas las primitivas.

Resolución de problema de aplicación (1hr 20 min)

Dado los archivos descriptos más abajo, totalmente desordenados, construir un programa para emitir un listado de ciudades, ordenado por código de país y cantidad de habitantes, para el continente con CodigoContinente = 1:

Los archivos tienen la siguiente estructura:

Nota:

1. Explicar la estrategia de solución adoptada con claridad (usar esquemas)
2. Los archivos se procesarán secuencialmente, una sola vez, luego en forma directa
3. Los archivos no deben almacenarse en memoria bajo ninguna circunstancia
4. Completar todo lo necesario para la resolución del problema, tipos, variables, procedimientos, etc.

/************************************************************************************
El ordenamiento de la lista se hace de la siguiente manera:
 
ResultadoComparacion compararDato(Dato dato1, Dato dato2) {
    if (getTiempoVuelta(dato1.competidor) == getTiempoVuelta(dato2.competidor)) {
        if (getNombre(dato1.competidor) == getNombre(dato2.competidor))
            return igual;
        else {
            if (getNombre(dato1.competidor) > getNombre(dato2.competidor))
                return mayor;
            else
                return menor;
        }
    }
 
    else
        if (getTiempoVuelta(dato1.competidor) > getTiempoVuelta(dato2.competidor))
            return mayor;
        else
            return menor;
}
*******************************************************************************************/
/*
Pre: Ninguna
Post: La consulta queda creada y lista para ser usada
*/
void crear(cCompetidor &miConsulta) {
    crearLista(miConsulta.competidores);
}
 
/*
Pre: La consulta debe haber sido creada
Post: La consulta queda destruída e inutilizable
*/
void destruir(cCompetidor &miConsulta) {
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
 
    ptrCompetidor = primero(miConsulta.competidores);
    while (ptrCompetidor != fin()) {
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        destruir(datoCompetidor.competidor);
        colocarDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
    }
    eliminarLista(miConsulta.competidores);
}
 
/*
Pre: La consulta debe haber sido creada, así como el competidor a agregar
Post: El competidor queda agregado a la consulta
*/
void agregarCompetidor(cCompetidor &miConsulta, Competidor* miCompetidor) {
    Dato datoCompetidor;
 
    datoCompetidor.competidor = miCompetidor;
    insertarDato(miConsulta.competidores,datoCompetidor);
}
 
/*
Pre: La consulta debe haber sido creada, y miCompetidor debe referenciar a un competidor
Post: Se elimina al competidor de la consulta (no se destruye el competidor)
*/
void quitarCompetidor(cCompetidor &miConsulta, Competidor* miCompetidor){
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
    bool encontrado = false;
 
    ptrCompetidor = primero(miConsulta.competidores);
    while ((ptrCompetidor != fin()) && (!encontrado)){
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        if (datoCompetidor.competidor == miCompetidor){
            encontrado = true;
        }
        else {
            ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
        }
    }
 
    if (encontrado){
        eliminarNodo(miConsulta.competidores,ptrCompetidor);    
    }
}
 
/*
Pre: La consulta debe haber sido creada y "pathCompetidores" debe ser la ruta a un archivo con formato correcto
Post: Se agregan todos los competidores del archivo a la consulta
*/
void cargarCompetidores(cCompetidor &miConsulta, string pathCompetidores) {
    ArchivoRegistros fCompetidores;
    regCompetidor registro;
    Competidor* nvoCompetidor;
    unsigned int tiempo;
 
    crear(fCompetidores,pathCompetidores,sizeof(regCompetidor));
    while (!fin(fCompetidores)) {
        leer(fCompetidores,static_cast<void*>(&registro));
        crear(nvoCompetidor,registro.numero,registro.nombre);
        setEdad(nvoCompetidor,registro.edad);
        tiempo = convertirTiempo(registro.tiempo);
        setTiempoVuelta(nvoCompetidor,tiempo);
        setPais(nvoCompetidor,registro.pais);
        agregarCompetidor(miConsulta,nvoCompetidor);
    }
    destruir(fCompetidores);
}
 
/*
Pre: La consulta debe haber sido creada
Post: Se devuelve el tiempo promedio de los competidores de la consulta. En caso de haber un error se retorna "0"
*/
float obtenerTiempoPromedio(cCompetidor &miConsulta) {
    float promedio = 0;
    int cantidadCompetidores = 0;
    int sumatoria = 0;
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
 
    ptrCompetidor = primero(miConsulta.competidores);
    while (ptrCompetidor != fin()) {
        cantidadCompetidores++;
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        sumatoria += getTiempoVuelta(datoCompetidor.competidor);
        ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
    }
 
    if (cantidadCompetidores != 0) {
        promedio = (float)sumatoria/cantidadCompetidores;
    }
 
    return promedio;
}
 
/*
Pre: La consulta debe haber sido creada
Post: Se retorna una referencia el competidor de mejor tiempo. En caso que no hay competidores, se retorna "0"
*/
Competidor* obtenerCompetidorMejorTiempo(cCompetidor &miConsulta) {
    Competidor* competidor = 0;
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
 
    ptrCompetidor = primero(miConsulta.competidores);
    if (ptrCompetidor != fin()) {
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        competidor = datoCompetidor.competidor;
    }
    return competidor;
}
 
/*
Pre: La consulta debe haber sido creada
Post: Se retorna una referencia el competidor de peor tiempo. En caso que no hay competidores, se retorna "0"
*/
Competidor* obtenerCompetidorPeorTiempo(cCompetidor &miConsulta) {
    Competidor* competidor = 0;
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
 
    ptrCompetidor = ultimo(miConsulta.competidores);
    if (ptrCompetidor != fin()) {
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        competidor = datoCompetidor.competidor;
    }
    return competidor;
}
 
/*
Pre: La consulta debe haber sido creada
Post: Se retorna una referencia al competidor cuyo número es nroCompetidor. En caso de no existir en la consulta, se retorna 0
*/
Competidor* obtenerCompetidor(cCompetidor &miConsulta, int nroCompetidor) {
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
    bool encontrado = false;
    Competidor* competidor = 0;
 
    ptrCompetidor = primero(miConsulta.competidores);
    while ((ptrCompetidor != fin()) && (!encontrado)) {
    obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        if (getNumero(datoCompetidor.competidor) == nroCompetidor) {
            encontrado = true;
            competidor = datoCompetidor.competidor;
        }
        else
            ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
    }
    return competidor;
}

Para que todo esto ande, obviamente hace falta el TDA Competidor:

using namespace std;
 
const string NOPAIS = "Orígen Indefinido";
 
typedef struct Competidor{
    int numero;
    string nombre;
    unsigned int edad;
    string pais;
    unsigned int tiempoVuelta;
};
 
/*
Pre: Ninguna
Post: Crea el dato y lo deja listo para su uso
*/
void crear(Competidor* &miCompetidor, int numero, string nombre){
    miCompetidor = new Competidor;
    miCompetidor->numero = numero;
    miCompetidor->nombre = nombre;
    miCompetidor->edad = 0;
    miCompetidor->pais = NOPAIS;
    miCompetidor->tiempoVuelta = 0;
}
 
/*
Pre: El dato debe haber sido creado
Post: Destruye el dato, y lo deja inutilizable
*/
void destruir(Competidor* &miCompetidor){
    miCompetidor->numero = 0;
    delete miCompetidor;
    miCompetidor = NULL;
}
 
/*
Pre: El dato debe haber sido creado
Post: Establece el nombre del competidor
*/
void setNombre(Competidor* miCompetidor, string nombre){
    miCompetidor->nombre = nombre;
}
 
/*
Pre: El dato debe haber sido creado
Post: Establece la edad del competidor
*/
void setEdad(Competidor* miCompetidor, unsigned int edad){
    miCompetidor->edad = edad;
}
 
/*
Pre: El dato debe haber sido creado
Post: Establece el país del competidor
*/
void setPais(Competidor* miCompetidor, string pais){
    miCompetidor->pais = pais;
}
 
/*
Pre: El dato debe haber sido creado y tiempoVuelta debe ser un entero, representado en segundos
Post: Establece el tiempo de vuelta del competidor
*/
void setTiempoVuelta(Competidor* miCompetidor, unsigned int tiempoVuelta){
    miCompetidor->tiempoVuelta = tiempoVuelta;
}
 
/*
Pre: El dato debe haber sido creado
Post: Establece el tiempo de vuelta del competidor (en segundos)
*/
int getNumero(Competidor* miCompetidor){
    return miCompetidor->numero;
}
 
/*
Pre: El dato debe haber sido creado
Post: Retorna el nombre del competidor
*/
string getNombre(Competidor* miCompetidor){
    return miCompetidor->nombre;
}
 
/*
Pre: El dato debe haber sido creado
Post: Retorna la edad del competidor
*/
unsigned int getEdad(Competidor* miCompetidor){
    return miCompetidor->edad;
}
 
/*
Pre: El dato debe haber sido creado
Post: Retorna el país del competidor
*/
string getPais(Competidor* miCompetidor){
    return miCompetidor->pais;
}
 
/*
Pre: El dato debe haber sido creado
Post: Retorna el tiempo de vuelta del competidor (en segundos)
*/
unsigned int getTiempoVuelta(Competidor* miCompetidor){
    return miCompetidor->tiempoVuelta;
}

Se cargan todos los paises en el continente 1, ordenándolos por código ascendente. Luego se lee el archivo de ciudades insertándolas en la lista de ciudades del pais correspondiente, si existiera ( se inserta en forma ascendente por habitantes )

struct tPais{
    PtrNodoLista corriente;
    char codigo[3];
    Lista ciudades;
};
struct tCiudad{
    int habitantes;
    long prr;
};
struct RegPais{
    char codigo[2];
    int continente;
    char nombre[30];
};
struct RegCiudad{
    int codigo;
    char cod_pais[2];
    char nombre[40];
    int habitantes;
};
 
const int IGUAL = 0;
const int MAYOR = 1;
const int MENOR = -1;
 
int compararPais( tPais& p1, tPais& p2 )
{
    string cod1 = getCodigo( p1 );
    string cod2 = getCodigo( p2 );
 
    if( cod1 == cod2 ) return IGUAL;
    if( cod1 < cod2 ) return MENOR;
    if( cod1 > cod2 ) return MAYOR;
}
 
int main()
{
    Lista paises;
 
    crearLista( paises );
    cargarPaises( paises );
    cargarCiudades( paises );
    mostrarListado( paises );
 
    liberarListaPais( paises );
    eliminarLista( paises );
    return 0;
}
 
void cargarPaises( Lista paises )
{
    ArchivoRegistro arch;
    RegPais aux;
    tPais pais;
 
    crearArchivoReg( arch, “paises.dat”, sizeof( RegPais ) );
    while( !fin(arch) ){
        leer(arch, &aux);
        if( aux.continente == 1 ){
            crearPais(pais, aux.codigo );
            insertarDato( paises, pais );
            destruirPais( pais );
        }
    }
    destruirArchivo( arch );
}
 
void cargarCiudades( Lista paises )
{
    PtrNodoLista pOrigen; // puntero al nodo del pais encontrado
    tPais pais; // patron de busqueda
    ArchivoRegistro arch;
    RegCiudad aux;
    tCiudad ciudad;
 
    crearArchivoReg(arch, “ciudades.dat”, sizeof(RegCiudad));
    while(!fin(arch)){
        leer(arch,aux);
        crearPais( pais, aux.cod_pais);
        pOrigen = localizarDato( paises, pais );
        destruirPais( pais );
        if( pOrigen != fin( paises ) ){
            obtenerDato( paises, pais, pOrigen );
            crearCiudad( ciudad, aux.habitantes, posicion(arch) );
            agregarCiudad( pais, ciudad );
            colocarDato( paises, pais, pOrigen );
            destruirCiudad( ciudad );
        }
    }
    destruirArchivo(arch);
}
 
void liberarListaPais( Lista paises )
{
    tPais pais;
    PtrNodoLista pNodo;
 
    pNodo = primero( paises );
    while( pNodo != fin( paises) ){
        obtenerDato(paises, pais, pNodo );
        destruirPais(pais);
        colocarDato( paises, pais, pNodo);
        pNodo = siguiente( paises, pNodo );
    }
}
 
void mostrarListado( Lista paises )
{
    long prr:
    tPais pais;
    tCiudad ciudad;
    RegCiudad aux;
    PtrNodoLista pNodo;
    ArchivoRegistro arch;
 
    crearArchivoReg( arch, “ciudades.dat”, sizeof(RegCiudad)),
    cout << “PAIS\tCIUDAD\t\tHABITANTES\n”;
    pNodo = primero( paises );
    while( pNodo != fin(paises)){
        obtenerDato(paises, pais, pNodo);
        primerCiudad( pais );
        while( obtenerCiudad( pais, ciudad) ){
            prr = getPrr( ciudad );
            posicionarse( arch, prr);
            leer( arch, aux);
            cout << getCodigo(pais) << “\t” << aux.nombre << “\t\t”;
            cout << getHabitantes(ciudad) << endl;
        }
        pNodo = siguiente(paises, pNodo );
    }
    destruirArchivo( arch );
}
 
// TDAs utilizados ( structs declarados arriba )
// tPais
 
void crearPais( tPais& pais, char cod[] )
{
    pais.codigo[2] = '\0'; // fin de cadena
    pais.codigo[0] = cod[0];
    pais.codigo[1] = cod[1];
    crearLista( pais.ciudades );
}
 
void destruirPais( tPais& pais )
{
    tCiudad ciudad;
    PtrNodoLista pNodo;
 
    pNodo = primero( pais.ciudades);
    while( pNodo != fin(pais.ciudades) ){
        obtenerDato( pais.ciudades, ciudad, pNodo);
        destruirCiudad( ciudad );
        colocarDato( pais.ciudades, ciudad, pNodo);
        pNodo = siguiente( pais.ciudades, pNodo );
    }
    eliminarLista( pais.ciudades );
}
 
//mueve el puntero corriente a la primer ciudad, sin obtenerla
void primerCiudad( tPais& pais )
{
    pais.corriente = primero( pais.ciudades );
}
 
//obtiene la ciudad actual, mueve el puntero al siguiente, devuelve true si la ciudad
// obtenida es válida
bool obtenerCiudad( tPais& pais, tCiudad& ciudad )
{
    if( pais.corriente == fin( pais.ciudades ) )
        return false;
 
    obtenerDato( pais.ciudades, ciudad, pais.corriente );
    pais.corriente = siguiente( pais.ciudades, pais.corriente );
    return true;
}
 
//obtiene el codigo
string getCodigo( tPais& pais )
{
    return string( pais.codigo );
}
 
//TDA Ciudad
// tCiudad
void crearCiudad( tCiudad& ciudad, int habitantes, long prr )
{
    ciudad.habitantes = habitantes;
    ciudad.prr = prr;
}
 
void destruirCiudad( tCiudad& ciudad )
{
}
 
long getPrr( tCiudad& ciudad )
{
    return ciudad.prr;
}
 
int getHabitantes( tCiudad& ciudad )
{
    return ciudad.habitantes;
}

Hasta acá llevo 1 hora 16 minutos. Más tarde, cuando pasaba la resolución, me di cuenta que faltaba la primitiva agregarCiudad. La listo a continuación:

void agregarCiudad( tPais& pais, const tCiudad& ciudad )
{
    insertarDato( pais.ciudades, ciudad );
}