Lista simplesmente encadeada com busca auto-organizada

Publicado por Felipe (última atualização em 09/10/2016)

[ Hits: 2.987 ]

Download l_o.c




O script faz uso do conceito de Lista (estruturas de dados) com funções básicas como inserir/remover fim/inicio e imprimir, método simplesmente encadeado com 2 exemplos de sistemas de busca auto-organizado para melhorar o desempenho do algoritmo de busca, o primeiro é o mover para frente onde toda vez que determinada célula é pesquisada ela é levada para o começo da lista, outro é o conceito de transposição onde toda vez que uma célula é buscada ela anda uma posição pra frente na lista.

  



Esconder código-fonte

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct sAluno
   {
   char nome[60];
   int matricula;
   }Aluno;

typedef struct sCelula
   {
   Aluno info;
   struct sCelula * proximo;
   }Celula;

Celula * cria_celula()
   {
   return (Celula *)malloc(sizeof(Celula));
   }

void inicializa_lista(Celula **cabeca)
   {
   (*cabeca) = NULL;
   }

int lista_vazia(Celula **cabeca)
   {
   if((*cabeca) == NULL)
      {
      return 1;
      }
   return 0;
   }

int insere_fim(Celula **cabeca, Aluno info)
   {
   Celula * nova = cria_celula();
   Celula * auxiliar;
   if(nova == NULL)
      {
      return 0;
      }
   nova->info = info;
   nova->proximo = NULL;
   if(lista_vazia(cabeca))
      {
      (*cabeca) = nova;
      return 1;
      }
   auxiliar = (*cabeca);
   while(auxiliar->proximo != NULL)
      {
      auxiliar = auxiliar->proximo;
      }
   auxiliar->proximo = nova;
   return 1;
   }

int insere_inicio(Celula **cabeca, Aluno info)
   {
   Celula * nova = cria_celula();
   Celula * auxiliar;
   if(nova == NULL)
      {
      return 0;
      }
   if(lista_vazia(cabeca))
      {
      return insere_fim(cabeca, info);
      }
   nova->info = info;
   nova->proximo = (*cabeca);
   (*cabeca) = nova;
   return 1;
   }

Aluno remove_inicio(Celula **cabeca)
   {
   Aluno info;
   strcpy(info.nome," ");
   info.matricula = -1;
   Celula * auxiliar;
   if(lista_vazia(cabeca))
      {
      return info;
      }
   auxiliar = (*cabeca);
   (*cabeca) = (*cabeca)->proximo;
   info = auxiliar->info;
   free(auxiliar);
   return info;
   }

Aluno remove_fim(Celula **cabeca)
   {
   Aluno info;
   strcpy(info.nome," ");
   info.matricula = -1;
   Celula * auxiliar;
   Celula * anterior;
   if(lista_vazia(cabeca))
      {
      return info;
      }
   auxiliar = (*cabeca);
   while(auxiliar->proximo != NULL)
      {
      anterior = auxiliar;
      auxiliar = auxiliar->proximo;
      }
   info = auxiliar->info;
   anterior->proximo = NULL;
   free(auxiliar);
   return info;
   }

void imprime_info(Aluno info)
   {
   printf("\nNOme: %s\nMatricula: %d\n",info.nome, info.matricula);
   }

int imprime_lista(Celula **cabeca)
   {
   Celula *auxiliar;
   if(lista_vazia(cabeca))
      {
      return 0;
      }
   auxiliar = (*cabeca);
   while(auxiliar != NULL)
      {
      imprime_info(auxiliar->info);
      auxiliar = auxiliar->proximo;
      }
   return 1;
   }

Aluno pega_info()
   {
   Aluno info;
   printf("Nome :\n");
   setbuf(stdin,NULL);
   scanf("%[^\n]",info.nome);
   printf("Matricula :\n");
   scanf("%d",&info.matricula);
   return info;
   }

Celula * pesquisa_info(Celula **cabeca)
   {
   int mat;
   Celula * auxiliar;
   if(lista_vazia(cabeca))
      {
      return NULL;
      }
   printf("digite a matricula\n");
   scanf("%d",&mat);
   auxiliar = (*cabeca);
   while(auxiliar != NULL)
      {
      if(auxiliar->info.matricula == mat)
         {
         imprime_info(auxiliar->info);
         return auxiliar;
         }
      auxiliar = auxiliar->proximo;
      }
   return NULL;
   }

int move_frente(Celula **cabeca)
   {
   Celula * pesquisada = pesquisa_info(cabeca);
   Celula * anterior;
   if(pesquisada == NULL)
      {
      return 0;
      }
   anterior = (*cabeca);
   if(anterior == pesquisada)
      {
      return 1;
      }
   while(anterior->proximo != pesquisada)
      {
      anterior = anterior->proximo;
      }
   anterior->proximo = pesquisada->proximo;
   pesquisada->proximo = (*cabeca);
   (*cabeca) = pesquisada;
   return 1;
   }

int trans_pos(Celula **cabeca)
   {
   Celula * pesquisada = pesquisa_info(cabeca);
   Celula * anterior;
   Celula * anterior2;
   if(pesquisada == NULL)
      {
      return 0;
      }
   anterior = (*cabeca);
   if(anterior == pesquisada)
      {
      return 1;
      }
   while(anterior->proximo != pesquisada)
      {
      anterior = anterior->proximo;
      }
   anterior2 = (*cabeca);
   if(anterior2 == anterior)
      {
      anterior->proximo = pesquisada->proximo;
      pesquisada->proximo = anterior;
      (*cabeca) = pesquisada;
      return 1;
      }
   while(anterior2->proximo != anterior)
      {
      anterior2 = anterior2->proximo;
      }
   anterior->proximo = pesquisada->proximo;
   pesquisada->proximo = anterior;
   anterior2->proximo = pesquisada;
   return 1;
   }

void menu(Celula **cabeca)
   {
   int op;
   Aluno info;
   do{
   printf("1-)INsere inicio\n");
   printf("2-)INsere fim\n");
   printf("3-)Remove inicio\n");
   printf("4-)Remove fim\n");
   printf("5-)imprime lista\n");
   printf("6-)Move pra frente\n");
   printf("7-)Transposição\n");
   scanf("%d",&op);
   switch(op)
      {
      case 1:
         {
         info = pega_info();
         insere_inicio(cabeca, info);
         break;
         }
      case 2:
         {
         info = pega_info();
         insere_fim(cabeca, info);
         break;
         }
      case 3:
         {
         info = remove_inicio(cabeca);
         imprime_info(info);
         break;
         }
      case 4:
         {
         info = remove_fim(cabeca);
         imprime_info(info);
         break;
         }
      case 5:
         {
         imprime_lista(cabeca);
         break;
         }
      case 6:
         {
         move_frente(cabeca);
         break;
         }
      case 7:
         {
         trans_pos(cabeca);
         break;
         }
      }
   }while(op != 0);
   }

int main()
   {
   Celula * cabeca = cria_celula();
   inicializa_lista(&cabeca);
   menu(&cabeca);
   }

Scripts recomendados

Retorna o tempo ocioso em uma sessão do X

Lista encadeada

Criptografia de Cesar

Uso de threads no C

Potências de 2


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts