Veja, abaixo, a execução do programa e o código, por completo:
/** GUSTAVO NAHUM ALVAREZ FERREIRA **/
/** TURMA: 19.3 **/
/** LAB 4 - CES 11 **/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define teto 1000000
///FORAM USADAS DUAS STRUCTS: O NODE (UNIDADE DAS LISTAS LIGADAS)...
typedef struct node node;
struct node
{
int num;
node *prox;
};
typedef node *posicao;
///...E O NODE_HEAP (UNIDADE DO VETOR, QUE CONTERÁ O TAMANHO E O PONTEIRO PARA O INÍCIO DAS LISTAS)
typedef struct node_heap node_heap;
struct node_heap
{
int tamanho;
node *inicio;
};
typedef node_heap *heap;
//RETORNA A QUANTIDADE DE SUBSEQUENCIAS MAXIMAIS DO ARQUIVO LIDO
int quantidadeSubsequencias ()
{
//O INT NUM_ANT FOI INICIALIZADO COM "TETO", OU SEJA, 1000000...
//...POIS SE DESEJA QUE PASSE NA CONDICAO "IF" NA PRIMEIRA VEZ
int quantidade = 0, num_atual = 0, num_ant = teto;
FILE *f_entrada;
f_entrada = fopen("entrada.txt", "r");
while(fscanf(f_entrada, "%d", &num_atual) != EOF)
{
if(num_atual < num_ant)
quantidade++;
num_ant = num_atual;
}
fclose(f_entrada);
return quantidade;
}
//LE, PELA SEGUNDA VEZ, O ARQUIVO, E MONTA AS LISTAS QUE CONTEM AS SUBSEQUENCIAS
void criaHeap (heap H, int quantidade)
{
int i = 0;
node *P;
int num_ant = teto, num_atual;
FILE *f_entrada;
f_entrada = fopen("entrada.txt", "r");
i = 0;
while(fscanf(f_entrada, "%d", &num_atual) != EOF)
{
if(num_atual < num_ant)
{
//CASO "NUM_ATUAL" < "NUM_ANT", AVANCA-SE NO VETOR DE "HEAP_NODE"
//E O ESPACO "H[i].TAMANHO" EH INICIALIZADO COM 1 (POIS, AGORA, JA
//EXISTE UM PRIMEIRO "NODE" ALI)
H[++i].inicio = (node*)malloc(sizeof(node));
P = H[i].inicio;
P->num = num_atual;
P->prox = NULL;
num_ant = num_atual;
H[i].tamanho = 1;
}
else
{
//CASO CONTRARIO, AVANCA-SE NA LISTA DE UM MESMO "H[i]"
//E, LOGO, HA UM ACRESCIMO EM "H[i].TAMANHO"
P->prox = (node*)malloc(sizeof(node));
P = P->prox;
P->num = num_atual;
P->prox = NULL;
num_ant = num_atual;
H[i].tamanho++;
}
}
fclose(f_entrada);
}
///ALGORITMO "SIFT", AUXILIAR DE "HEAP-SORT"
void Sift(int i, int n, heap H)
{
int esq = 2*i;
int dir = 2*i+1;
int maior = i;
if (esq <= n && H[esq].tamanho > H[i].tamanho)
maior = esq;
if (dir <= n && H[dir].tamanho > H[maior].tamanho)
maior = dir;
if (maior != i)
{
node *aux;
int aux_int;
aux = H[i].inicio;
aux_int = H[i].tamanho;
H[i].inicio = H[maior].inicio;
H[i].tamanho = H[maior].tamanho;
H[maior].inicio = aux;
H[maior].tamanho = aux_int;
Sift(maior, n, H);
}
}
///ALGORITMO "BUILD", AUXILIAR DE "HEAP-SORT"
void Build(heap H, int quantidade)
{
int i;
for (i = quantidade/2; i > 0; i--)
Sift(i, quantidade, H);
}
///ALGORITMO "HEAP-SORT"
void HeapSort(heap H, int quantidade)
{
Build(H, quantidade);
int i;
for (i=quantidade; i>1; i--)
{
node *aux;
int aux_int;
aux = H[i].inicio;
aux_int = H[i].tamanho;
H[i].inicio = H[1].inicio;
H[i].tamanho = H[1].tamanho;
H[1].inicio = aux;
H[1].tamanho = aux_int;
Sift(1, i-1, H);
}
}
///ALGORITMO "MERGE-SORT" (ADAPTADO PARA O PROBLEMA)
int MergeSort(heap H)
{
//VAI TOMAR AS DUAS LISTAS LIGADAS INICIADAS COM "H[1].INICIO" E "H[2].INICIO"
//E, COM O AUXILIO DOS PONTEIROS "P1", "P2" E "AUX", VAI INTERCALAR OS "NODES"
//E OS SEUS "PROX" EM ORDEM CRESCENTE
posicao P1, P2, aux;
P1 = H[1].inicio;
P2 = H[2].inicio;
int tempo = H[1].tamanho + H[2].tamanho;
if(P1->num < P2->num)
{
H[1].inicio = P1;
P1 = P1->prox;
}
else
{
H[1].inicio = P2;
P2 = P2->prox;
}
while(P1->prox != NULL && P2->prox != NULL)
{
if(P1->num < P2->num)
{
if(P1->prox->num < P2->num)
P1 = P1->prox;
else
{
aux = P1->prox;
P1->prox = P2;
P1 = aux;
}
}
else
{
if(P2->prox->num < P1->num)
P2 = P2->prox;
else
{
aux = P2->prox;
P2->prox = P1;
P2 = aux;
}
}
}
if(P1->prox == NULL)
{
while(P2->prox != NULL && P2->prox->num < P1->num)
P2 = P2->prox;
if(P2->prox == NULL)
{
if(P2->num < P1->num)
P2->prox = P1;
else
P1->prox = P2;
}
else if(P2->num < P1->num)
{
aux = P2->prox;
P2->prox = P1;
P1->prox = aux;
}
else
P1->prox = P2;
}
if(P2->prox == NULL)
{
while(P1->prox != NULL && P1->prox->num < P2->num)
P1 = P1->prox;
if(P1->prox == NULL)
{
if(P1->num < P2->num)
P1->prox = P2;
else
P2->prox = P1;
}
else if(P1->num < P2->num)
{
aux = P1->prox;
P1->prox = P2;
P2->prox = aux;
}
else
P2->prox = P1;
}
return tempo;
}
int main()
{
//RESTA, NA MAIN, CHAMAR AS FUNCOES AUXILIARES E OBTER "UNIDADES_TEMPO"
int i, quantidade, unidades_tempo = 0;
node *P;
heap H;
/** PASSO I **/
quantidade = quantidadeSubsequencias();
/** PASSO II **/
H = (node_heap *) malloc ((quantidade+1) * sizeof(node_heap));
criaHeap(H, quantidade);
HeapSort(H, quantidade);
/** PASSO III **/
while(H[2].inicio != NULL)
{
//AQUI, ENFIM, OBTEM-SE AS "UNIDADES_TEMPO"
unidades_tempo += MergeSort(H);
H[1].tamanho = H[1].tamanho + H[2].tamanho;
H[2].inicio = NULL;
H[2].tamanho = teto;
HeapSort(H, quantidade);
}
/** PASSO IV **/
FILE *f_saida;
f_saida = fopen("saida.txt", "w");
for(P = H[1].inicio; P != NULL; P = P->prox)
fprintf(f_saida, "%d\n", P->num);
/** PASSO V **/
fprintf(f_saida, "%d\n", unidades_tempo);
fclose(f_saida);
return 0;
}
Nenhum comentário:
Postar um comentário