1º Projeto de Algoritmo e Estrutura de Dados 

Descrição do Projeto 

Durante o treino dos pilotos de Fórmula 1, é registrado no sistema as marcas alcançadas por cada carro. O treino definirá as posições de largada de cada piloto. Os carros deverão ser organizados de acordo com o melhor tempo obtido por cada piloto. Na primeira vez que o carro obtiver uma marca, deve ser colocado na ordem classificatória de acordo com o tempo. Serão possíveis diversas tentativas para o mesmo carro e, a cada nova tentativa, deve-se verificar se a marca foi melhor, o que pode levar o carro a uma posição mais à frente na classificação. Caso a marca não seja melhor, sua posição não deve ser modificada, porém, o resultado da volta deve ser armazenado. A quantidade de carros e suas respectivas marcas são desconhecidas.

Funções Usadas 

2 lista dinâmica duplamente encadeada
Randômica

Programa 


/* 1ª Projeto de Estrutura de dados 
Autoras: Stanelle Silveira , Ayres Rodrigues
Matriculas:2551 , 2510 */

//Bibliotecas necessárias 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <ctype.h>
//#include <conio.h>
//Inicio do programa

typedef struct dadosLDDE{  //Lista Tempo
   int temp[4];/*    Vetor para armazenar o tempo, sendo que o primeiro para minutos, o segundo para segundos, 
   o terceiro para milésimo e quarto para armazenar a soma dos minutos e segundos convertido em milésimo mais
   os  milésimos do terceiro vetor, assim facilitando a comparação entre as marcas.*/
   struct dadosLDDE *prox,*ant;//ponteiros para o anterior e o próximo 
}sLDDE;//estrutura lista dinamica dupalamente encadeada para o tempo;

typedef struct dadosLDSE1{  //Lista Carro
   sLDDE *lista1;//ponteiro para lista tempo
   int carro;// variavel para guarda o nome do carro
   struct dadosLDSE1 *prox,*ant;//ponteiros para o anterior e o próximo 
}slista;// estrtura lista dinamica duplamente encadeada para o carro
   
slista *inicializa1(slista *L1){
   L1 = NULL;//inicializar a estrutura lista dinamica duplamente encadeada
   return L1;// retorna o inicilização 
}

bool estaVazia(slista *L1){ //Verifica se a lista está vazia
   return (L1 == NULL); //se L1 for igual a null retorna verdadeiro se nao retorna falso
}
slista *inserir_carro(slista *L1, int op){// Função para inserir carro no final da lista
   slista *aux, *auxI; // declaração de ponteiro tipo slista, são auxiliares para a inserção
   aux =(slista*)malloc(sizeof(slista)); //alocação da variavel aux
   aux->lista1 = NULL;//inicializa a lista do tempo
  
   if(aux == NULL)// se aux for igual a null a alocação nao foi possível 
      printf("A alocacao nao foi porssivel");//caso entre no if o usuario será informado que alocação nao foi possível
   aux->carro = op;// Aux recebe o nome do carro.
   aux->prox = NULL;//o ponteiro prox recebe NULL;
      
   if(estaVazia(L1)){// se a lista está vazia, esse será o primeiro nó.  
      aux->ant=NULL;//O ponteiro ant recebe NULL já que não possui um anterior 
      L1=aux;// a lista recebe o endereço do primeiro nó
     }//fim da inserção do primeiro nó
   else{//se não for o primeiro elemento entra nessa estrutura condicional
      auxI = L1;  // Usar uma segundo auxiliar para percorre até o ultimo nó, aqui ele recebe o primeiro da lista
      while (auxI->prox != NULL) //percorre a lista até o ultimo nó
         auxI = auxI->prox;// auxI recebe o endereço que o auxI->prox está apontando
      auxI->prox = aux;//auxI na posição prox recebe o endereço do novo nó
      aux->ant=auxI;//o novo nó na posição ant recebe o endereço de auxI (nó anterior)
      } //fecha o else 
                            
   return L1; //retorna as modificações feita na lista 
} // fecha a função 

slista *randomica(slista *L1,slista *pesq){// função para inserção ordenando a marca ou seja o tempo
   sLDDE *aux, *auxp;//declaração de ponteiro tipo sLDDE, são auxiliares para a inserção das marcas
   int i;// variável para o laço for, que orienta na hora da inserção da  randômica
  
   srand ( time(NULL) );// inicia o rand 
   aux =(sLDDE*)malloc(sizeof(sLDDE)); //aloco a variável aux
   if(aux==NULL){// verifica se alocou
      printf("Impossível alocar memória!\n\n");// caso não tenha alocado aviso ao usuário
      system("pause");//parada para visualização
   }else{//caso tenha alocado, vai entrar nessa estrutura condicional                                       

   for(i=0;i<3;i++){ //laço de repetição para rodar as posições do vetor do tempo        
      aux->temp[i]=rand()%60; // a posição i do vetor recebe um numero do  sorteado pela randômico                                     
   }//fecha o for da inserção dos tempos (marcas)

   printf("\n Novo tempo %d:%d:%d\n",aux->temp[0],aux->temp[1],aux->temp[2]);  //Imprime o vetor do tempo.             
   aux->temp[3]=aux->temp[0]*60;  //transforma os minutos(posição 0) em segundos em seguida armazenar no vetor posição 3
   aux->temp[3]=((aux->temp[3]+aux->temp[1])*60);/*soma o segundos armazenados na posição 3 com os segundo na posição 
   1 e depois multiplica por 60 assim obtendo os milésimos */
   aux->temp[3]=aux->temp[3]+aux->temp[2];// Soma o que já foi transformado em milésimo com o que tem em milésimo na posição 3
             
   if(pesq->lista1 == NULL){// se a lista estiver vazia criará o primeiro nó 
      aux->prox = NULL;  // a posição prox do novo nó recebe NULL, já que este é a primeira posição 
      aux->ant = NULL; //a posição ant do novo nó recebe NULL, já que este é a primeira posição        
      pesq->lista1 = aux;//o ponteiro receberá o endereço do primeiro nó
      }//fecha o if
      
   else if(aux->temp[3] < pesq->lista1->temp[3]){ /*senão for o primeiro elemento, entra nessa estrutura condicional desde que 
   seja menor  ao anterior existente*/
         aux->prox = pesq->lista1;// o novo nó passará a apontar para o nó já existente
         aux->ant = NULL;// o posição ant do novo nó receberá NULL
         pesq->lista1->ant = aux;// a posição ant do nó já existente receberá o endereço do novo nó apontando para ele
         pesq->lista1 = aux;//o endereço do primeiro nó é atualizado
         }// fecha o else if 
         
         else{//Entra aqui caso não satisfaz a condição anterior, será inserido no meio ou no fim 
            auxp = pesq->lista1; // o auxiliar recebe o endereço do primeiro nó
            //pesquisa
while (auxp->prox != NULL && aux->temp[3] > auxp->temp[3]) //enquanto não for o ultimo nó e o tempo do novo nó for maior que o tempo do nó auxp
               auxp = auxp->prox;  //atualizo auxp,    
                                
             if (aux->temp[3] > auxp->temp[3]){ // inserir no final o novo nó que será o ultimo da lista 
                aux->prox = NULL; //a posição prox do novo nó recebe NULL
                aux->ant = auxp; //a posição ant recebe o endereço do ultimo nó
                auxp->prox = aux; //o ultimo nó passa apontar para o novo nó               
             }//fecha o if 
            
else{ //se não satisfaz a condição anterior, entra nesse caso que vai inserir no meio
                aux->prox = auxp; //o novo nó na posição prox recebe e endereço de auxp 
                aux->ant = auxp->ant; //o novo nó na posição ant recebe e endereço de ant do nó auxp 
                aux->prox->ant = aux; //o novo nó na posição prox que aponta para o endereço do próximo na posição ant recebe endereço de aux
                aux->ant->prox = aux;//o novo nó na posição ant que aponta para o endereço do anterior na posição prox recebe endereço de aux
             }//fecha o else
         }//fecha o else
   }//fecha o else
   return pesq;     //retorno da variável já que foi feito alterações nela       
}//fecha a função


slista *pesquisa(slista *L1,int op){  //Função para pesquisar o nó do carro é usando quando for inserir a marca do carro

   while(L1 != NULL && L1->carro != op){  /*Entra nesse laço se for diferente de null e diferente do valor procurado, 
   quando for igual ao valor procurado o L1 ficara com o endereço dele. */
      L1 = L1->prox;// atualiza L1 recebendo o endereço do proximo elemento
   }//fecha o while 
        
   return L1; //returna o endereço procurado
}//fecha a função



void impri_randomica(slista *pesq,int op){ //Imprime as marcas  ou seja o tempo
   sLDDE *aux;// Declaração de um ponteiro tipo estrutura de marca 
    
   if(pesq == NULL){//se pesq for igual a NULL o tempo do carro digitado não existe
      printf("\n Marcas do carro %d(mm:ss:ms):Nenhuma marca registrada ate o momento\n\n",op); //avisa ao usuário
   }//fecha o if
   
   else {//caso nao entre la no if e por que existe tempo, então aqui vai imprimir todos os tempos existente 
      printf(" Marcas do carro %d (mm:ss:ms): ",op); //Imprimir as marcas do carro   
      aux = pesq->lista1;//aux recebe o endereço da lista tempo do item pesquisado 
      
 while(aux != NULL){ //Enquanto não chegar ao fim da lista tempo 
         printf("%d:%d:%d -  ",aux->temp[0],aux->temp[1],aux->temp[2]);//imprime o vetor que contém o tempo das marcas do carro   
         aux = aux->prox;//aux recebe o endereço do proximo
      } //fecha o while     
   }//fecha o else 
}//fecha a função



slista *ordena_carros(slista *L1){ //Função para ordenar em ordem crescente a lista dos carros conforme sua classificação através da menor marca 
   slista *aux,*aux2,*aux3;//auxiliares do tipo da lista dos carros 
   aux = L1;//aux recebe o endereço do primeiro nó
   aux2 = L1->prox;//aux2 recebe o endereço do segundo nó 

   while(aux != NULL){ //Será pesquisado até o aux for null 
         
      while(aux2 != NULL){ //Aqui o aux2 pecorre toda a lista até encontrar o null, sempre comparando com o aux. 
      
         if(aux->lista1->temp[3] <= aux2->lista1->temp[3])/*será comparado se a marca anterior do endereço do aux  é menor que
           o próximo elemento, se for aux2 recebe o endereço do próximo  elemento*/
            aux2 = aux2->prox; //aux2 recebe o endereço do próximo nó 
               
         else{ // Caso nao satisfaz a condição anterior entra nesse else, assim move a marca menor para frente     
            if(aux->prox != aux2)//verifica se o  proximo elemento de aux e diferente de aux2 
               aux->prox->ant = aux2;//Se for diferente o proximo de aux vai apontar para aux2
            if(aux2->ant != aux)//verifica se o anterio do aux2 e diferente de aux 
               aux2->ant->prox = aux;//Se for,  o anterior aux2 vai apontar pra aux
            if(aux->ant != NULL)// Verifica se o anterior de aux e igual a null, caso seja que dizer que aux é o primeiro elemento
               aux->ant->prox = aux2;//o anterior ao aux vai receber o endereço do aux2 
            aux3 = aux->ant;// o aux3 vai guarda o endereço do anterior de aux
            if(aux2->ant != aux)//verifica se o anterior do aux2 e diferente de aux 
               aux->ant = aux2->ant;// se for o ant aux vai receber o endereço do anterior do ant aux2 
            else//caso anterior de aux2 for igual ao aux 
               aux->ant = aux2;//se for, o ant aux vai receber o endereço de aux2, assim fazendo com que aux2 passe para trás 
            aux2->ant = aux3;//o ant do aux2 vai receber o  endereço do anterior de aux já que anteriomente aux3 recebeu tal endereço
            if(aux2->prox != NULL)//Verifica se o proximo de aux2 e diferente de null, ou seja se for igual a null, aux2 vai ser o ultimo elemento
               aux2->prox->ant = aux;//se for, o ant do proximo de aux  vai receber o endereço do aux
            aux3 = aux->prox;//aux3 vai guarda o endereço do proximo de aux
            aux->prox = aux2->prox;//o prox do aux vai recebero o endereço do proximo de aux2
            aux2->prox = aux3;//O prox de aux2 vai receber o endereço do aux3
            if (aux2->prox == aux2)//Se o proximo de aux2 for igual ao aux2 entra nessa condição 
               aux2->prox = aux;// se entrar o prox de aux2 vai receber o aux
            if(aux2->ant == NULL)//se o ant de aux2 for igual a null
               L1 = aux2;// A lista recebe o endereço de aux2, já que este será o primeiro elemento da lista 
            // trocando as posição do auxs 
            aux3 = aux;//aux3 guarda o endereço de aux
            aux = aux2;// aux recebe o endereço do aux2
            aux2 = aux3;//aux dois vai receber o endereço do aux 3 que guarda o antigo endereço do aux
            aux2 = aux2->prox; //e aux2 vai receber o endereço do proximo elemento a ser comparado
         }//fecha o else 

      }//fecha o segundo while
      aux = aux->prox; //aux recebe o endereço do próximo nó da lista, para ser comparado com o restante da lista, afim de verificar se possui um numero menor que ele 
      
 if(aux2 == NULL && aux != NULL) //se o endereço que está em aux2 for igual a NULL e o endereço que está em aux for diferente de NULL
         aux2 = aux->prox; // aux2 recebe o endereço do próximo nó 
   }//fecha o primeiro while
   return L1; //retorna a lista modificada
}//fecha a função 



void classificacao_geral(slista *L1){//imprimi a colocação do carro no ranking

   if(estaVazia(L1)){//abre o if  se estiver vazia entra nessa condição 
      printf("\n\n Classificacao Geral:"); //Informação ao usuário
      printf("\n O treino ainda nao comecou, entre com um carro para comecar!!!\n"); //Informação ao usuário 
    }//fecha if
    
   else{ //caso a lista nao esteja vazia entra nessa condição onde será imprimido a colocação do carro 
      printf("\n\n Classificacao Geral:\n");//Informação ao usuário
      
 while(L1 != NULL){// imprimi a colocação do carro no 
         printf("Carro: %d;\n",L1->carro); //Imprime o número do carro
         L1 = L1->prox; //atualiza o ponteiro L1 com o endereço do próximo nó
        }//fecha o while
    }//fecha o else 

}//fecha a função, essa função nao teve necessidade de retorno, já que é só para imprimir a classificação 



int  posicao(slista *L1, int op){//abre função 
   int num=1; //variável num inicializada com 1 
    
   while(L1 != NULL && L1->carro != op) {//enquento L1 for diferente de NULL e a variável carro for diferente do carro procurado
      L1 = L1->prox;     //L1 recebe o endereço do próximo nó da lista 
      num++;            //incremento o contador num
    }//fecha o while
  
   return num;         //retorno da variável num, assim podendo localiza a posição do carro
}//fecha a função



void Menu(slista *L1){//Função Menu, aqui vai ser controlado todas entradas que o usuário desejar.
   slista *pesq;// declaração do ponteiro tipo slista para pesquisar quando for necessario       
   int op,posi; //declaração das variaveis que vão receber o nome do carro e o posição que ele se encontra  
   char op1;  //declaração do caracter
     
   
   do{// Laço para controla a saida do programa
       
      printf("\n\n Digite 0 para Sair ou o numero do Carro\n\n");// Informando o usuário se ele deseja sair do programa digite 0 ou inserir um novo carro  
      printf("\n\n Nome do carro_");// Informar que já pode ser digitado o novo carro ou 0 para sair
      scanf("%d",&op);//Ler a opção do usuário 
      if(op == 0){//caso ele tenha digitado 0 o programa sairá do laço 
         printf("\nFim do treino\n\n");//informa que acabou o treino
         op1='$';// a variavel  recebe o $ para poder sair do laço
      }else{ //caso a pessoa tenh adigitado o nome do carro entra nessa condição               
         pesq = pesquisa(L1,op);//Aqui é chamado a função pesquisa para verificar existe o carro escolhido      
         impri_randomica(pesq,op);/*Nesta linha é chamado a função para imprimir as marcas existente para o carro escolhido, mesmo que essa marca nao
 existe será imprimido um aviso para o usuario*/ 
 //Menu
         printf("\n\n\n  Digite:\n\n * $ para Sair\n * & para digitar outro numero de carro\n * @ para geracao randomica da nova marca do carro %d:\n",op);
          
         while(getchar()!='\n');//fazer a função da uma pausa 
         fflush(stdin);// esvaziar o buffer   
         scanf("%c",&op1);// receber a opção do usuário 
     
    if(op1 =='@'){  //Entra nessa condição se o usuário desejar inserir a marca para o carro digitado anteriomente                 
           
  
   if (pesq==NULL){// É comparado se a pesquisa feita anteriomente e igual a null porque se for que dizer que o carro ainda nao foi inserido 
               L1 = inserir_carro(L1,op);//Chama a função inserir o carro no final 
               pesq = pesquisa(L1,op); //faz uma nova pesquisa para poder ter o endereço do carro inserido anteriomente 
               pesq = randomica(L1,pesq);//A marca é enviada já em ordem crescente para o carro digitado anteriomente 
               L1= ordena_carros(L1);//ordena a posição dos carros a cada arca gerada 
               
             }//fim do if
            else{// caso o carro já exista entra nessa condição            
               pesq = pesquisa(L1,op);//faz uma nova pesquisa para poder ter o endereço do carro inserido anteriomente    
               pesq=randomica(L1,pesq);//A marca é enviada já em ordem crescente para o carro digitado anteriomente
               L1= ordena_carros(L1);//ordena a posição dos carros a cada arca gerada 
             
              }//fecha else
              
         classificacao_geral(L1); //Aqui é imprimido a classificação geral dos carros 
         posi = posicao(L1,op);// nessa função posi reberar a posição que o carro ocupa
         printf("\n\n A  classificao do carro %d  e: %d\n\n",op,posi); //Informação ao usuário   
        } // fim da opção gerar randomica           
         else if(op1!='&')//O usuário deseja inserir novo carro 
                 continue; //continua executando o laço
      }// fim do primeiro else 
   system("pause");//pausar programa 
   system("cls");//limpar tela             
   }while(op1!='$');//Ao digitar $, será imprimido a classificação geral e termina o treino 
    classificacao_geral(L1); // imprimir a classificação geral       
}//fecha a função 

int main() {//abre função principal  
   slista *lista;//declaro um ponteiro do tipo da lista do carro
   lista = inicializa1(lista);//chamada da função inicializa 
   Menu(lista);//chamada da função Menu para controle to programa 
  
   printf("\n\n\n Obrigado pela preferencia\nExecute sempre %c\n\n\n",3);// Informação ao usuário 
   
   system("pause");//
   return 0;  //retorno 0 para execução com sucesso
}//fecha a função principal