Lista simplesmente encadeada com busca auto-organizada

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

[ Hits: 3.172 ]

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

caixa de supermercado em c

Fila usando lista encadeada

Métodos de Ordenação - Radix Sort

Metaphone para Português

Aritmética de ponteiros


  

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