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);
}