Trabalho AVL e Heapsort

                                      UNIVERSIDADE FEDERAL DE OURO PRETO

INSTITUTO DE CIÊNCIAS EXATAS E APLICADAS

DEPARTAMENTO DE ENGENHARIA ELÉTRICA

ALGORITMOS E ESTRUTURAS DE DADOS I

Trabalho Prático  2

                                                    AVL e Heap Máximo

                                                    Chave Fabricante

Docente:

Professor: Erik de Britto e Silva

Discentes:

            Adonis Silva Oliveira                            15.1.5936

             Gustavo Dos Santos Viana                    15.2.8103

            Jeannie Lacerda Sales                            16.1.828

             Karine Araujo Goncalves                      12.2.4236

            Marina Fumian Breijão                         11.2.8060

            Matheus Augusto F. Martins                  15.2.8142

JOÃO MONLEVADE-MG

JANEIRO/2018

Introdução:

O Trabalho Prático 2 é a partir do Trabalho Prático 1 que foi montar uma Lista Simplesmente Encadeada que seria exibida pela variável  char fabricante. 

O trabalho foi desenvolvido á partir dos códigos  de fornecidos  pelo Professor : Erik de Britto e Silva. As implementações foram realizadas nas estruturas Heap, Arvore AVL,Lista Simplesmente Encadeada .As estruturas que basearam o trabalho foram:

struct lista

{

    int size;

    struct node* head;

};

struct fila

{

    int size;

    struct node* head, *tail;

};

struct tree

{

    float key;

    NodeT value;

    Tree left, right;

};

struct heap

{

    int size,capacity;

    Item v;

};

 E para desenvolver o trabalho prático 2 essas estruturas foram modificadas de acordo com a necessidade.

Desenvolvimento:

Para iniciar o trabalho foi necessário criar um TAD de acordo com o solicitado abaixo:

Será utilizado o mesmo TAD DRONE1 do TP1, com as mesmas características

1. Peso em Kg com duas casas decimais

2. Nome do fabricante com no máximo 40 caracteres

3. Nome do modelo do drone com no máximo 20 caracteres

4. Capacidade de fornecimento de corrente das baterias em mAH, exemplo: 1200 mAH, 8000 mAH e 10000 mAh

5. Tempo máximo que o drone consegue se manter no ar, no formato hh:mm:ss (sempre armazenado  assim)

De acordo com as informações acima repassadas foi criada a struct lista e a struct drone:

/* Definição da Lista Encadeada

 Contem size e apenas o apontador head que aponta para o primeiro Drone*/

 struct lista{

int size;

   Drone* head;

     };

// Definição  do Drone - Elemento da Lista

struct drone {

void* item;

float peso;

char fabricante[41];

char modelo[21];

int cap_mAH;

char pesos[14]; char tempoar[9];

struct  drone* next;

};typedef struct drone Drone;

 1-Leitura dos Drones

O primeiro item pedido é efetuar a leitura de todos os drones de um arquivo de texto de nome“drones-tp2.txt” que foi fornecido pelo professor. E inseri-los  na estrutura definida para o grupo  que foi Lista Simplesmente Encadeada

Primeiro é preciso  criar uma função para criar uma lista vazia.

// Função que cria a lista com zero de tamanho e nenhum elemento

Lista l_new() {

  Lista l = (Lista) malloc(sizeof(Lista));

  l->size = 0;

  l->head = NULL;

  return l;

}

Segundo cria-se a função l_add que adiciona os drones que é a abaixo:

// Função que adiciona o fabricante na primeira posição da lista

void l_add(Lista l,char pesos[], char fabricante[], char modelo[],int cap_mAH, char tempoar[]) {

   // Aloca o "novo" Drone

  float peso;

  Drone* novo = ( Drone*) malloc(sizeof( Drone));

  strcpy(novo->fabricante,fabricante);

  strcpy(novo->modelo,modelo);

  novo->cap_mAH=cap_mAH;

  peso=atof(pesos);//função converte uma palavra em um numero

  novo->peso=peso;

  strcpy(novo->tempoar,tempoar);

  l->size++;

    novo->next = l->head;

    l->head = novo;

    return;

  }

Terceiro cria-se a lista:

Lista l = l_new();

E por último através da função ledrones é feita a leitura e a inserção dos drones na lista.

/*Executa leitura dos drones a partir do arquivo de texto*/

 void ledrones(Lista l){

FILE *arq;

    char fabricante3[41], modelo[21];