Lista simplesmente encadeada com busca auto-organizada
Publicado por Felipe (última atualização em 09/10/2016)
[ Hits: 3.014 ]
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.
#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); }
Desenhando uma curva Dragão ou o Fractal Jurassic Park
Calculadora em C separada por funções e com diretivas
Nenhum comentário foi encontrado.
Atenção a quem posta conteúdo de dicas, scripts e tal (1)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
ASRock H310CM-HG4 vs Linux (2)
pacotes 32 bit no void 64 bit (1)
erro ao clonar repo github (7)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (26)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba