Atividade de Laboratório 5 - LAB EXAME

Faaaala Professor!! Deboa?? É, como o tempo passa rápido né? Final de ano chegou voando e tamo ai com o ultimo Lab de CES 11 de 2015, é nóis!! Esse lab me ensinou a manipular grafos orientados utilizando listas de adjacência, além de me ensinar a aplicação dos Algoritmos de Tarjan e Dijkstra para o mesmo digrafo. Também utilizei a ordenação de listas.

Link para o vídeo: https://youtu.be/DlBCPXbcevM

Código Fonte:
#include <bits/stdc++.h>
#define infinito 9999999

using namespace std;

///implementação da estrutura de dados descrita no arquivo do lab

typedef int vertice;
typedef struct CelAdj CelAdj;
typedef struct Dijkstra_struct Dijkstra_struct;
typedef int* vetor;
typedef vetor* matriz;

struct Dijkstra_struct
{
    int** distancia;
    int** predecessor;
};

struct CelAdj
{
    vertice vert;
    int minutos;
    CelAdj *prox;
};
struct CelVert
{
    char aeroporto[30];
    CelAdj *listaAdj;
};
struct digrafo
{
    int nvert;
    CelVert *vertices;
};
digrafo G;

void Ordenar_listas();

void Memoria()
{
    G.vertices = (CelVert*)malloc(G.nvert*sizeof(CelVert));
    for(int i = 0; i< G.nvert; i++)
    {
        G.vertices[i].listaAdj = NULL;
    }
}
void Leitura(FILE* arqEntrada)
{
    int origem, destino, lig, tempo, rotas_minimas, destino1, destino2;
    CelAdj* aux;
    fscanf(arqEntrada,"%d ", &G.nvert);
    Memoria();
    for(int i = 0; i < G.nvert ; i++)
    {
        fgets(G.vertices[i].aeroporto, 30, arqEntrada);
    }
    fscanf(arqEntrada,"%d", &lig);
    for(int j = 0; j < lig; j++)
    {
        fscanf(arqEntrada,"%d %d %d", &origem, &destino, &tempo);
        aux = G.vertices[origem].listaAdj;
        if(aux != NULL)///se já houver alguem ligado ao vertice
        {
            for(; aux->prox != NULL; aux = aux->prox);
            aux->prox = (CelAdj*)malloc(sizeof(CelAdj));
            aux = aux->prox;
            aux -> vert = destino;
            aux -> minutos = tempo;
            aux ->prox = NULL;
        }
        else///se nao houver ninguem ligado ao vertice ainda
        {
            G.vertices[origem].listaAdj = (CelAdj*)malloc(sizeof(CelAdj));
            (G.vertices[origem].listaAdj)->vert = destino;
            (G.vertices[origem].listaAdj)->minutos = tempo;
            (G.vertices[origem].listaAdj)->prox = NULL;
        }
    }
    ///ordenação das listas de adjacência; ta ok!!!
}
void Printar_Grafo(FILE* saida)
{
    fprintf(saida,"Digrafo:\n");
    for(int i = 0; i < G.nvert; i++)
    {
        fprintf(saida,"%d (%s):",i, G.vertices[i].aeroporto);
        for(CelAdj* aux = G.vertices[i].listaAdj; aux != NULL; aux = aux->prox)
        {
            if(aux->prox != NULL)
                fprintf(saida," %d(%d)", aux->vert, aux -> minutos);
            if(aux->prox == NULL)
                fprintf(saida," %d(%d)\n", aux->vert, aux -> minutos);
        }
    }
}
void Ordenar_listas()///ordena as listas de adjacência de cada elemento do vetor de structs
{
    for(int i = 0; i < G.nvert; i++)
    {
        CelAdj* aux;
        aux = G.vertices[i].listaAdj;
        if(aux->prox == NULL)
        {
            return;
        }
        else
        {
            for(; aux->prox!=NULL; aux = aux->prox)
            {
                CelAdj* q = NULL;
                q = aux->prox;
                if(q->prox == NULL)
                {
                    return;
                }
                else
                {
                    q = aux->prox;
                    q = q->prox;
                    aux = aux->prox;
                    for(; q!=NULL; q = q->prox)
                        if(q->vert < aux->vert)
                        {
                            CelAdj x = *aux;
                            *aux = *q;
                            *q = x;
                        }
                }

            }
        }
    }
}
Dijkstra_struct Dijkstra() ///Preenche as matrizes de distancia e de predecessão, aplicando o algoritmo de Dijkstra n vezes
{
    Dijkstra_struct grafo;
    CelAdj *p;
    bool **analisado;
    int n = G.nvert, menor;

    analisado = (bool**)malloc(n*sizeof(bool*));
    grafo.distancia = (matriz)malloc(n*sizeof(vetor));
    grafo.predecessor = (matriz)malloc(n*sizeof(vetor));


    for(int i = 0; i < n; i++)
    {
        grafo.distancia[i] = (vetor)malloc(n*sizeof(int));
        grafo.predecessor[i] = (vetor)malloc(n*sizeof(int));
        analisado[i] = (bool*)malloc(n*sizeof(bool));
    }

    for(int i = 0; i < n; i++)
    {
        grafo.distancia[i][i] = 0;
        grafo.predecessor[i][i] = i;
        analisado[i][i] = false;
        for(int j = 0; j < n; j++)
        {
            if(i != j)
            {
                grafo.distancia[i][j] = infinito;
                grafo.predecessor[i][j] = -1;
                analisado[i][j] = false;
            }
        }
    }

    for(int i = 0; i < n; i++)
    {
        for(int t = 0; t < n; t++)
        {
            int k;
            for(k = 0; k < n; k++)
            {
                if(!analisado[i][k])
                {
                    menor = k;
                    break;
                }
            }
            for(int j = 0; j < n; j++)
            {
                if(grafo.distancia[i][j] < grafo.distancia[i][menor] && !analisado[i][j])
                    menor = j;
            }
            analisado[i][menor] = true;
            for(p = G.vertices[menor].listaAdj; p != NULL; p = p->prox)
            {
                if(grafo.distancia[i][p->vert] > grafo.distancia[i][menor] + p->minutos)
                {
                    grafo.distancia[i][p->vert] = grafo.distancia[i][menor] + p->minutos;
                    grafo.predecessor[i][p->vert] = menor;
                }
            }
        }
    }

    return grafo;
}
void Rota_Minima(FILE* entrada, FILE* saida, Dijkstra_struct grafo, int n)
{
    stack<int> pilha;
    int rotas, de, para, atual = 0;
    fscanf(entrada, "%d", &rotas);
    fprintf(saida, "Rotas minimas:\n");
    while (rotas > 0)
    {
        fscanf(entrada, "%d %d", &de, &para);
        fprintf(saida, "%d a %d: ", de, para);
        if(grafo.distancia[de][para] < infinito)
        {

            if(para != de)
            {

                fprintf(saida, "%d", de);
                atual = para;

                while(grafo.predecessor[de][atual] != de)
                {

                    pilha.push(atual);
                    atual = grafo.predecessor[de][atual];

                }

                pilha.push(atual);

                while(!pilha.empty())
                {

                    fprintf(saida, "-%d", pilha.top());
                    pilha.pop();

                }
                fprintf(saida, " (%d minutos)\n", grafo.distancia[de][para]);

            }
            else
                fprintf(saida, "(0 minutos)\n");

        }
        else
            fprintf(saida, "sem voos\n");
            rotas--;
    }
    fprintf(saida, "\n");
}
void DFS(int* pai, int *expl, int *comp, int *ce, int *cc, int v, FILE* saida)///auxilia no algoritmo de tarjan para encontrarmos trajetos fechados
{
    CelAdj *p;
    expl[v] = ++(*ce);
    for(p = G.vertices[v].listaAdj; p != NULL; p = p->prox)
    {
        if(expl[p->vert] == 0)
        {
            pai[p->vert] = v; /// Armazenamos os pais na árvore de exploração
            DFS(pai, expl, comp, ce, cc, p->vert, saida);
        }
        else if(expl[p->vert] < expl[v] && comp[p->vert] == 0)
        {
            stack<int> pilha;
            int atual = v;
            fprintf(saida, "%d", p->vert);
            ///invertemos a ordem da impressão
            while(atual != p->vert)
            {
                pilha.push(atual);
                atual = pai[atual];
            }
            while(!pilha.empty())
            {
                fprintf(saida, "-%d", pilha.top());
                pilha.pop();
            }
            fprintf(saida, "-%d\n", p->vert);
        }
    }
    comp[v] = ++(*cc);
}
void ciclos(FILE* saida)
{
    int *pai = (vetor)malloc(G.nvert*sizeof(int));
    int *expl = (vetor)malloc(G.nvert*sizeof(int));
    int *comp = (vetor)malloc(G.nvert*sizeof(int));
    int ce = 0, cc = 0;
    for(int i = 0; i < G.nvert; i++)
    {
        expl[i] = 0;
        comp[i] = 0;
        pai[i] = -1;
    }
    fprintf(saida, "Trajetos fechados:\n");
    for(int i = 0; i < G.nvert; i++)
    {
        if(expl[i] == 0)
            DFS(pai, expl, comp, &ce, &cc, i, saida);
    }
}
int main()
{
    FILE *entrada, *saida;
    entrada = fopen("entrada.txt", "r");
    saida = fopen("saida.txt", "w");
    Leitura(entrada);
    Ordenar_listas();
    Dijkstra_struct grafo = Dijkstra();
    Printar_Grafo(saida);
    Rota_Minima(entrada, saida, grafo, G.nvert);
    ciclos(saida);
    fclose(entrada);
    fclose(saida);
}

ATIVIDADE DE LABORATÓRIO 4 - ALGORITMOS DE ORDENAÇÃO

Fala prof!! Como o senhor está? Então, estamos aqui para mais um laboratório de Ces 11. Dessa vez o estudo buscou abordar a manipulação de algoritmos de ordenação O(N*logN) em listas ligadas, utilizando uma estrutura de vetor de structs, que são listas.

Segue o código fonte comentado abaixo:

Link para o Vídeo: https://youtu.be/NQANgfgGMCI


///Murilo Orofino Tarosso - T-19.3 - CES - 11

#include<stdio.h>
#include<stdlib.h>
#include <bits/stdc++.h>

using namespace std;

struct node
{
    int num;
    node * prox;
};
struct vet_structs
{
    int tamanho;
    node* pont;
};
typedef struct node node;
typedef node* posicao;
typedef node* lista;
typedef vet_structs* vetor;
typedef vetor* vetor_listas;

int Numero_Filiais(FILE* arqEntrada)
{
    int n=0, num;
    while(fscanf(arqEntrada,"%d", &num)!=EOF)
    {
        n++;
    }
    return n;
}
int Numero_Listas(FILE* arqEntrada, int n)
{
    int* v;
    v = (int*)malloc(n*sizeof(int));
    int i = 0, num, resp;
    while(fscanf(arqEntrada, "%d", &num)!= EOF)
    {
        v[i] = num;
        i++;
    }
    resp = 0;
    for(int j = 1; j <= i; j++)
    {
        if(v[j-1] > v[j])
        {
            resp++;
        }
    }
    return resp + 1;
}

node* Prox(int n)
{
    node * p = (node*)malloc(sizeof(node));
    p->num = n;
    p->prox = NULL;
    return p;
}

vet_structs* Read(int n, FILE* entrada)
{
    vetor v = (vet_structs*)malloc((n+1)*sizeof(vet_structs));
    posicao p = NULL;
    int a = 0, b = 0;
    int i = 0;
    b = INT_MAX; ///Evita análises particulares
    while(fscanf(entrada,"%d",&a) != EOF)
    {
        if(a >= b) ///mesma lista
        {
            v[i].tamanho++;
            p->prox = Prox(a);
            p = p->prox;
        }
        else ///próxima lista
        {
            i++;
            v[i].tamanho = 1;
            v[i].pont = (node*)malloc(sizeof(node));
            p = v[i].pont;
            p->num = a;
            p->prox = NULL;
        }
        b = a;
    }
    return v;
}

void Troca(vetor a, vetor b)///troca todo o conteúdo das structs a e b; troca como se fosse por igualdade de inteiros;
{
    vet_structs auxiliar = *a;
    *a = *b;
    *b = auxiliar;
}
void Sift(int i, int n, vetor v)///algoritmo Sift para a reconstrução do heap de mínimo
{
    int aux;
    int esq = 2*i;
    int dir = 2*i + 1;
    int maior = i;
    if (esq <= n && v[esq].tamanho < v[i].tamanho)
        maior = esq;
    if (dir <= n && v[dir].tamanho < v[maior].tamanho)
        maior = dir;
    if (maior != i)
    {
        aux = v[i].tamanho;
        v[i].tamanho = v[maior].tamanho;
        v[maior].tamanho = aux;
        Sift(maior, n, v);
    }
}
void Build(vetor v, int n)///Construção do Heap
{
    int i;
    for (i = n/2; i > 0; i--)
        Sift(i, n, v);
}
void Criar_Heap(vetor v, int num_listas)
{
    Build(v, num_listas);
}

vet_structs Minimo(vetor m, int n) ///Retirada da raíz, ou seja, do mínimo valor do heap
{
    vet_structs aux = m[1];
    m[1] = m[n];
    Sift(1, n-1, m);
    return aux;
}
vet_structs Merge(node* a1, node* b1, int *tempo) /// Ordenação intercalda de duas listas node dadas (a1 e b1)
{
    vet_structs A;
    A.tamanho = 1;
    A.pont = (node*)malloc(sizeof(node));
    node* p = A.pont;
    p->prox = NULL;
    if(a1->num <= b1->num) /// Evitar o armazenamento de memórias "junks"
    {
        p->num = a1->num;
        a1 = a1->prox;
    }
    else
    {
        p->num = b1->num;
        b1 = b1->prox;
    }
    (*tempo)++;
    while(a1 && b1) /// Selecionar o menor dados dois elementos para inserir na nova lista
    {
        if(a1->num <= b1->num)
        {
            p->prox = Prox(a1->num);
            a1 = a1->prox;
        }
        else
        {
            p->prox = Prox(b1->num);
            b1 = b1->prox;
        }
        p = p->prox;
        A.tamanho++;
        (*tempo)++; /// A cada número inserido, incrementamos o tempo
    }
    while(a1)
    {
        p->prox = Prox(a1->num);
        a1 = a1->prox;
        p = p->prox;
        A.tamanho++;
        (*tempo)++;
    }
    while(b1)
    {
        p->prox = Prox(b1->num);
        b1 = b1->prox;
        p = p->prox;
        A.tamanho++;
        (*tempo)++;
    }
    return A; /// Retorna a struct que entra no vetor inicial
}
int Ordenacao(vet_structs* v, int *n)
{
    int t = 0;
    if((*n) == 1) /// O processo termina quando houver apenas uma sequência
        return 0;
    vet_structs aux = Minimo(v, (*n)--); /// A passagem por referência faz-se necessária aqui
    v[1] = Merge(aux.pont, v[1].pont, &t); /// Concatenamos as duas menores listas em uma só
    return t + Ordenacao(v, n);
}
void Imprimir(vet_structs M, int t) ///Impressão da saída ordenada em um arquivo de nome "saida.txt"
{
    FILE* arqSaida = fopen("saida.txt", "w");
    for(node* p = M.pont; p != NULL; p = p->prox)
    {
        fprintf(arqSaida, "%d\n", p->num);
    }
    fprintf(arqSaida, "%d\n", t);
    fclose(arqSaida);
}

int main()
{
    FILE* arqEntrada;
    arqEntrada = fopen("entrada.txt","r");
    int m = Numero_Filiais(arqEntrada), tempo = 0;
    fclose(arqEntrada);
    arqEntrada = fopen("entrada.txt", "r");
    int n = Numero_Listas(arqEntrada, m);
    fclose(arqEntrada);
    arqEntrada = fopen("entrada.txt","r");
    vetor v = Read(n,arqEntrada);
    Criar_Heap(v, n);
    tempo = Ordenacao(v, &n);
    Imprimir(v[1], tempo);
}