Simulación de algoritmos/Ordenamiento/Externo/Mezcla Equilibrada.Escrito en C ESTANDAR

Descripción

Este código es un simulador de ordenación externa con arreglos en lugar de archivos.
Se ha echo un intento por mostrar gráficamente en la consola el proceso de actualización de los archivos de intercambio temporal. El autor espera que sea útil. :)

Ejecución

Faltan algunos gráficos de su ejecución.

Compilación y ejecución de la versión actual

El código está probado para ser compilado bajo linux con el gcc y no requiere ninguna biblioteca especial.
Requiere abrir un archivo preexistente (para proveer una simulación realista, ya que el archivo se puede modificar antes de cada corrida para mostrar que realmente funciona).

Mejoras deseables

  1. Quizá una versión con fopen, fwrite y fread sea también útil.


Código del Simulador 1

/*
    Este código es un simulador de ordenación externa con arreglos.
    El contenido inicial se toma de un archivo de texto con el siguiente formato:
 
    {comienzo_de_archivo}{registro1}{retorno_de_carro}{registro2}{retorno_de_carro}
    {registro3}...{registroN}{fin_de_archivo}
 
En realidad es muy sencillo, todos los registros están separados por un
retorno de carro, pero después del último registro, no debe haber retorno de carro. ;-P
 
He aquí un ejemplo:
 09
 29
 ...
 36
 11
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define ARCHIVO_ORIGEN  "prueba.txt"
#define NUM_ELEM 35
 
#define ARCHIVO_NINGUNO -1
#define ARCHIVO_F  0    //auxiliares
#define ARCHIVO_F1 1
#define ARCHIVO_F2 2
#define ARCHIVO_F3 3
 
#define FIN -1
 
typedef enum boolean{false, true} boolean;
typedef int registro;
typedef enum abertura{cerrado, lectura, escritura} abertura;
 
 
//archivos
int f[4][NUM_ELEM];
//posición del cursor para cada archivo
int ix[4];
//estado de cada archivo
abertura abierto[4];
 
 
void abrirL(int archivo);
void abrirE(int archivo);
void cerrar(int archivo);
void escribir(int archivo, int valor);
boolean leer(int archivo, registro *r);
boolean fin(int archivo);
void imprimir(const char *msg);
 
void mezclaEquilibrada(int archf, int archf1, int archf2, int archf3);
void particionInicial(int archf, int archf2, int archf3);
void particionFusion(int archfa, int archfb, int archfc, int archfd);
void ayuda1(registro *aux, registro r, int fc, int fd, boolean band);
void ayuda2(registro *aux, registro r, int fc, int fd, boolean *band);
void ayuda3(registro *aux, registro r, int f, int fc, int fd, boolean *band);
 
 
 
/*
    Ordenación externa por Mezcla Equilibrada
*/
int main(int argc, char *argv[]){
 
    FILE *fuente=NULL;
    int c;
    int i;
 
    fuente=fopen(ARCHIVO_ORIGEN, "r");
    if (fuente==NULL) {
        printf("\n--No se pudo habrir el archivo de entrada: %s--\n", ARCHIVO_ORIGEN);
        exit(1);
    }
 
    i=0;
    abrirE(ARCHIVO_F);
    while(fscanf(fuente, "%d", &c)>0 && i++<NUM_ELEM)
        escribir(ARCHIVO_F, c);
    fclose(fuente);
    cerrar(ARCHIVO_F);
 
    // para ponerle FIN a todas las posiciones
    abrirE(ARCHIVO_F1); cerrar(ARCHIVO_F1);
    abrirE(ARCHIVO_F2); cerrar(ARCHIVO_F2);
    abrirE(ARCHIVO_F3); cerrar(ARCHIVO_F3);
 
 
    //correr el algoritmo
    mezclaEquilibrada(ARCHIVO_F, ARCHIVO_F1, ARCHIVO_F2, ARCHIVO_F3);
 
    system("PAUSE");
    return 0;
}
 
void mezclaEquilibrada(int archf, int archf1, int archf2, int archf3){
    int archivo_vacio=ARCHIVO_NINGUNO;
 
    boolean band;
    particionInicial(archf, archf2, archf3);
    //imprimir("después de partición inicial");
    band = true;
    do{
        if(band){
            particionFusion(archf2, archf3, archf, archf1);
            //imprimir("después de partición fusión con band=true");
            band=false;
        }else{
            particionFusion(archf, archf1, archf2, archf3);
            //imprimir("después de partición fusión con band=false");
            band=true;
        }
 
        abrirL(archf1);
        if(fin(archf1)) archivo_vacio=ARCHIVO_F1;
        cerrar(archf1);
 
        if(archivo_vacio==ARCHIVO_NINGUNO){
            abrirL(archf3);
            if(fin(archf3)) archivo_vacio=ARCHIVO_F3;
            cerrar(archf3);
        }
    }while(archivo_vacio==ARCHIVO_NINGUNO);
    imprimir("al final");
    printf("el archivo que está vacío es: %d\nEl listado final está en el: %d\n",
        archivo_vacio, archivo_vacio-1);
}
 
void particionInicial(int archf, int archf2, int archf3){
 
    registro aux, r;
    /* Si band==true, el último registro se escribió en f2,
    * sino, fue en f3
    */
    boolean band;
 
    abrirL(archf);
    abrirE(archf2);
    abrirE(archf3);
 
    if(!leer(archf, &r)){
        printf("Archivo vacío\n");
        cerrar(archf);
        cerrar(archf2);
        cerrar(archf3);
        exit(0);
    }
    escribir(archf2,r);
    band=true;
    aux=r;
    while(!fin(archf)){
        leer(archf, &r);
        if(r>=aux){
            aux=r;
            if(band){
                escribir(archf2,r);
            }else{
                escribir(archf3,r);
            }
        }else{
            aux=r;
            if(band){
                escribir(archf3,r);
                band=false;
            }else{
                escribir(archf2,r);
                band=true;
            }
        }
    }
 
    cerrar(archf);
    cerrar(archf2);
    cerrar(archf3);
}
 
void particionFusion(int archfa, int archfb, int archfc, int archfd){
    registro aux, r1, r2;
    /*
    */
    boolean band, dele1, dele2;
 
    abrirL(archfa);
    abrirL(archfb);
    abrirE(archfc);
    abrirE(archfd);
 
    band = true;
    leer(archfa, &r1);
    leer(archfb, &r2);
    if(r1<=r2)
        aux = r1;
    else
        aux = r2;
    dele1 = dele2 = false;
    while((!fin(archfa) || dele1!=true) && (!fin(archfb) || dele2!=true)){
        if(dele1){
            leer(archfa, &r1);
            dele1=false;
        }
        if(dele2){
            leer(archfb, &r2);
            dele2=false;
        }
        if(r1<r2){
            if(r1>=aux){
                //printf("probando... aux %d, r1 %d, r2 %d\n", aux, r1, r2);
                ayuda1(&aux, r1, archfc, archfd, band);
                dele1=true;
            }
            else if(r2>=aux){
                //printf("probando... r1 %d, aux %d, r2 %d\n", r1, aux, r2);
                ayuda1(&aux, r2, archfc, archfd, band);
                dele2=true;
            }
            else{
                //printf("probando... r1 %d, r2 %d, aux %d\n", r1, r2, aux);
                ayuda2(&aux, r1, archfc, archfd, &band);
                dele1 = true;
            }
        }
        else{
            if(r2>=aux){
                //printf("probando... aux %d, r2 %d, r1 %d\n", aux, r2, r1);
                ayuda1(&aux, r2, archfc, archfd, band);
                dele2=true;
            }
            else if(r1>=aux){
                //printf("probando... r2 %d, aux %d, r1 %d\n", r2, aux, r1);
                ayuda1(&aux, r1, archfc, archfd, band);
                dele1=true;
            }
            else{
                //printf("probando... r2 %d, r1 %d, aux %d\n", r2, r1, aux);
                ayuda2(&aux, r2, archfc, archfd, &band);
                dele2 = true;
            }
        }
    } //fin del while
    if(dele1 && fin(archfa))
        ayuda3(&aux, r2, archfb, archfc, archfd, &band);
    if(dele2 && fin(archfb))
        ayuda3(&aux, r1, archfa, archfc, archfd, &band);
 
    cerrar(archfa);
    cerrar(archfb);
    cerrar(archfc);
    cerrar(archfd);
}
 


void ayuda1(registro *aux, registro r, int fc, int fd, boolean band){
    *aux = r;
    if(band){
        escribir(fc, r); //fputs("\n", fc);
    }else{
        escribir(fd, r); //fputs("\n", fd);
    }
    //imprimir("ayuda1");
}
void ayuda2(registro *aux, registro r, int fc, int fd, boolean *band){
    *aux = r;
    if(*band){
        escribir(fd, r); //fputs("\n", fd);
        *band=false;
    }
    else{
        escribir(fc, r); //fputs("\n", fc);
        *band=true;
    }
    //imprimir("ayuda2");
}
void ayuda3(registro *aux, registro r, int f, int fc, int fd, boolean *band){
    if(r>=*aux)
        ayuda1(aux, r, fc, fd, *band);
    else
        ayuda2(aux, r, fc, fd, band);
    while(leer(f, &r)){
        if(r>=*aux)
            ayuda1(aux, r, fc, fd, *band);
        else
            ayuda2(aux, r, fc, fd, band);
    }
    //imprimir("ayuda3");
}
 
//Abre el archivo para lectura
void abrirL(int archivo){
    ix[archivo]=0;
    abierto[archivo]=lectura;
}
 
//Abre el archivo para escritura
void abrirE(int archivo){
    int i;
    if(abierto[archivo]!=cerrado){
        printf("archivo %d, abierto, no se puede volver a abrir\n", archivo);
        //system("pause");
        exit(1);
    }
    ix[archivo]=0;
    abierto[archivo]=escritura;
    for(i=0; i<NUM_ELEM; i++)
        f[archivo][i]=FIN;
}
 
void cerrar(int archivo){
    ix[archivo]=0;
    abierto[archivo]=cerrado;
}
 
void escribir(int archivo, int valor){
    if(abierto[archivo]!=escritura){
        printf("archivo %d, cerrado, no se puede escribir\n", archivo);
        exit(1);
    }
    f[archivo][ix[archivo]++]=valor;
}
 
//retorna verdadero si hay un registro que leer,
//retorna falso, si se ha alcanzado el fin del archivo
boolean leer(int archivo, registro *r){
    if(abierto[archivo]!=lectura){
        printf("archivo %d, cerrado, no se puede leer", archivo);
        exit(1);
    }
    *r = f[archivo][ix[archivo]++];
    if (f[archivo][ix[archivo]-1]!=FIN)
        return true;
    else{
        ix[archivo]--;
        return false;
    }
}
 
//responde si se ha alcanzado el fin del archivo
boolean fin(int archivo){
    return f[archivo][ix[archivo]]==FIN;
}
 
void imprimir(const char *msg){
    int i, j;
    printf("\n%s:\n", msg);
    for(i=0; i<4; i++){
        printf("Archivo %d (estado: %d):\n", i, abierto[i]);
        for(j=0; j<NUM_ELEM; j++){
            printf("%02d ", f[i][j]);
        }
        printf("\n");
        for(j=0; j<ix[i]; j++)
            printf("   ");
        printf("|-> %d\n\n", ix[i]);
    }
    printf("---\n\n\n");
    system("PAUSE");
}
 
// fin del código

No hay comentarios :

Publicar un comentario

DEJA TU COMENTARIOS CON TUS DUDAS Y SUGERENCIAS,ASI COMO TAMBIEN UN PEDIDO EN PARTICULAR.
TAMBIEN PUEDES TU CORREO ELECTRONICO PARA UNA RESPUESTA MAS RAPIDA.