#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define INFINITO 1000000
typedef int vertice;
typedef struct CelAdj CelAdj;
struct CelAdj
{
vertice vert;
int minutos;
CelAdj *prox;
};
typedef struct CelVert CelVert;
struct CelVert
{
char aeroporto[30];
CelAdj *listaAdj;
};
typedef struct digrafo digrafo;
struct digrafo
{
int nvert;
CelVert *vertices;
};
typedef struct node node;
struct node
{
int vertice;
node *prox;
};
typedef node *pilha;
typedef node *posicao;
void BubbleSort (digrafo *G)
{
//EXECUTA 'BUBBLE-SORT' NAS LISTAS ADJACENTES DO DIGRAFO G
int i, vert_aux, minutos_aux;
CelAdj *P;
bool mudou = true;
for(i = 0; i <= G->nvert-1; i++)
{
P = G->vertices[i].listaAdj;
while(mudou == true)
{
mudou = false;
P = G->vertices[i].listaAdj;
while(P->prox != NULL)
{
if(P->vert > P->prox->vert)
{
vert_aux = P->vert;
minutos_aux = P->minutos;
P->vert = P->prox->vert;
P->minutos = P->prox->minutos;
P->prox->vert = vert_aux;
P->prox->minutos = minutos_aux;
mudou = true;
}
P = P->prox;
}
}
}
}
int Dijkstra(digrafo G, int ref, int desc, vertice parent[], vertice dist[])
{
vertice v, w, v_aux, w_aux;
CelAdj *P;
for (w = 0; w <= G.nvert-1; w++)
{
parent[w] = -1;
dist[w] = INFINITO;
}
parent[ref] = ref;
dist[ref] = 0;
while (1)
{
//EXECUTA O LOOP ENQUANTO ALGUMA DISTANCIA SOFRE ALTERACAO, TODA VEZ QUE SE PERCORRE O DIGRAFO
int min_dist = INFINITO;
for (v = 0; v <= G.nvert-1; v++)
if (parent[v] != -1)
for (P = G.vertices[v].listaAdj; P != NULL; P = P->prox)
if (parent[P->vert] == -1 && min_dist > dist[v] + P->minutos)
{
min_dist = dist[v] + P->minutos;
v_aux = v;
w_aux = P->vert;
}
if (min_dist == INFINITO)
break;
parent[w_aux] = v_aux;
dist[w_aux] = min_dist;
}
return dist[desc];
}
void push (pilha *P, vertice v)
{
node *temp;
temp = *P;
*P = (node *) malloc (sizeof (node));
(*P)->vertice = v;
(*P)->prox = temp;
}
void pop (pilha *P)
{
node *temp;
temp = *P;
*P = (*P)->prox;
free (temp);
}
void DFS(vertice v, bool *aciclico, vertice *expl, vertice *comp, pilha *P, int *ce, int *cc, digrafo G, FILE *f_saida)
{
expl[v] = ++(*ce);
push(P,v);
CelAdj *Q;
for(Q = G.vertices[v].listaAdj; Q != NULL; Q = Q->prox)
if(expl[Q->vert] == 0) //CASO AINDA NAO TENHA SIDO EXPLORADO, ENTRA NESSE VERTICE
DFS(Q->vert, aciclico, expl, comp, P, ce, cc, G, f_saida);
else if (expl[Q->vert] < expl[v] && comp[Q->vert]==0)
{
//CASO SEJA UMA ARESTA DE RETORNO (B), MOSTRA CILICIDADE, E IMPRIME O CICLO
*aciclico = false;
int j, tamanho_pilha = 0;
posicao T, F;
T = *P;
while(T->prox != NULL)
{
T = T->prox;
tamanho_pilha++;
}
F = T;
while(tamanho_pilha >= 0)
{
for(j = tamanho_pilha, T = *P; j >= 1; j--)
T = T->prox;
fprintf(f_saida, "%d-", T->vertice);
tamanho_pilha--;
}
fprintf(f_saida, "%d\n", F->vertice);
}
pop(P);
comp[v] = ++(*cc);
}
void Ciclos (digrafo G, vertice *expl, vertice *comp, FILE *f_saida)
{
pilha P;
P = NULL;
bool aciclico = true;
int ce = 0, cc = 0;
vertice v;
for (v = 0; v <= G.nvert-1; v++)
{
expl[v] = 0;
comp[v] = 0;
}
for (v = 0; v <= G.nvert-1; v++)
if (expl[v] == 0)
DFS(v, &aciclico, expl, comp, &P, &ce, &cc, G, f_saida);
}
int main()
{
digrafo G;
FILE *f_entrada, *f_saida;
f_entrada = fopen("entrada.txt", "r");
f_saida = fopen("saida.txt", "w");
int i;
/** RECEBE OS VERTICES **/
char aeroporto[31], lixo;
fscanf(f_entrada, "%d%c", &G.nvert, &lixo);
G.vertices = (CelVert *)malloc(G.nvert * sizeof(CelVert));
for(i = 0; i <= G.nvert-1; i++)
G.vertices[i].listaAdj = NULL; //ZERA TODAS AS LISTAS ADJACENTES
for(i = 0; i <= G.nvert-1; i++)
{
fgets(aeroporto, 31, f_entrada);
aeroporto[strlen(aeroporto)-1] = '\0'; //TIRA O '\N' DO FINAL DA STRING
strcpy(G.vertices[i].aeroporto, aeroporto); //PASSA O NOME PARA O DIGRAFO
}
/** RECEBE OS ARCOS **/
int quant_arcos;
fscanf(f_entrada, "%d", &quant_arcos);
int pred, suc, custo;
CelAdj *P;
for(i = 1; i <= quant_arcos; i++)
{
fscanf(f_entrada, "%d %d %d", &pred, &suc, &custo);
if(G.vertices[pred].listaAdj == NULL) //INICIA A LISTA ADJACENTE DE 'PRED'
{
P = G.vertices[pred].listaAdj = (CelAdj *)malloc(sizeof(CelAdj));
P->vert = suc;
P->minutos = custo;
P->prox = NULL;
}
else //CONTINUA A LISTA ADJACENTE JA INICIADA
{
P->prox = (CelAdj *)malloc(sizeof(CelAdj));
P = P->prox;
P->vert = suc;
P->minutos = custo;
P->prox = NULL;
}
}
BubbleSort(&G); //ORDENA AS LISTAS DE ADJACENCIAS
fprintf(f_saida ,"Digrafo:\n");
for(i = 0; i <= G.nvert-1; i++)
{
fprintf(f_saida, "%d (%s):", i, G.vertices[i].aeroporto);
P = G.vertices[i].listaAdj;
while(P != NULL)
{
fprintf(f_saida, " %d(%d)", P->vert, P->minutos);
P = P->prox;
}
fprintf(f_saida, "\n");
}
fprintf(f_saida, "\n");
/** CONSULTAS DE ROTAS MINIMAS **/
fprintf(f_saida, "Rotas minimas:\n");
int c, partida, chegada, dist_esp; //CONSULTA DE ROTAS MINIMAS
vertice *dist; //VETOR DE PONTEIROS PARA INT
vertice *parent; //VETOR DE PAIS DE UM VERTICE
vertice vert, filho;
dist = (vertice *)malloc(G.nvert * sizeof(vertice));
parent = (vertice *)malloc(G.nvert * sizeof(vertice));
fscanf(f_entrada, "%d", &c);
for(i = 1; i <= c; i++) //PARA CADA 'C', EXECUTA O ALG. DIJKSTRA
{
fscanf(f_entrada, "%d %d", &partida, &chegada);
fprintf(f_saida, "%d a %d: ", partida, chegada);
if(partida == chegada)
fprintf(f_saida, "(0 minutos)\n");
else
{
dist_esp = Dijkstra(G, partida, chegada, parent, dist); //EXECUTA DIJKSTRA PARA DEFINIR 'PARENT'
if(dist[chegada] == INFINITO)
fprintf(f_saida, "sem voos\n");
else
{
while (partida != chegada) //IMPRIME O CAMINHO A SER SEGUIDO
{
for(vert = chegada; vert != partida; vert = parent[vert])
filho = vert;
fprintf(f_saida, "%d-", vert);
partida = filho;
}
fprintf(f_saida, "%d ", chegada);
fprintf(f_saida, "(%d minutos)\n", dist_esp);
}
}
}
fprintf(f_saida, "\n");
fclose(f_entrada);
/** ANALISE DE TRAJETOS FECHADOS **/
fprintf(f_saida, "Trajetos fechados:\n");
vertice *expl, *comp;
expl = (vertice *)malloc(G.nvert * sizeof(vertice));
comp = (vertice *)malloc(G.nvert * sizeof(vertice));
Ciclos(G, expl, comp, f_saida); //IMPRIME OS CICLOS, SE EXISTIREM
fclose(f_saida);
return 0;
}
domingo, 29 de novembro de 2015
LAB 5 / CES 11
Olá! Nesta publicação, o projeto tinha a função de avaliar a manipulação de grafos, através de algoritmos como o de Dijkstra, DFS (Depth-First Search) e de Tarjan modificado para verificar a ciclicidade de um dígrafo. A ideia seria a de fornecer a uma agência aérea: os menores caminhos (custo-mínimo) e os ciclos existentes entre aeroportos. Acompanhe a seguir:
quarta-feira, 18 de novembro de 2015
LAB4 - Trabalhando com HeapSort e MergeSort
Olá! Neste laboratório, o que foi proposto é a leitura de elementos obtidos a partir de um documento de texto "entrada.txt" e, a partir dos algoritmos de ordenação HeapSort e MergeSort, ordená-los e escrever um novo arquivo "saida.txt", contendo esses elementos já ordenados e as unidades de tempo necessárias para executar essa operação por completo.
Veja, abaixo, a execução do programa e o código, por completo:
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;
}
Assinar:
Comentários (Atom)