Estrutura de dados: Lista dinâmica duplamente encadeada
Publicado por Perfil removido 26/12/2006
[ Hits: 13.507 ]
Olá, aí vai o código de uma estrutura de dados que fiz pra faculdade. Ela é bem eficiente quando se quer fazer uma pesquisa onde se quer encontrar dados que estão próximos uns dos outros.
// arquivo: interface.h #include <stdlib.h> #define SUCESSO 1 #define FRACASSO 0 #define INICIO 1 #define FIM -1 typedef struct LDDE *pLDDE, **ppLDDE; int criaLDDE(ppLDDE pp,int tamInfo); int insereLDDE(pLDDE p,void *novo,int posLog); int removeLDDE(pLDDE p,int posLog); int buscaLDDE(pLDDE p,void *destino,int posLog); int testaVaziaLDDE(pLDDE p); void reiniciaLDDE(pLDDE p); void destroiLDDE(ppLDDE pp); // Arquivo privado.h #include "interface.h" typedef struct NoLDDE { void *dados; struct NoLDDE *ant; struct NoLDDE *prox; }NoLDDE,*pNoLDDE; typedef struct LDDE { int tamInfo; int quant; pNoLDDE inicio; pNoLDDE fim; }LDDE; // arquivo ldde.c #include "privado.h" int criaLDDE(ppLDDE pp,int tamInfo) { (*pp) = (pLDDE) malloc(sizeof(LDDE)); if(*pp == NULL) return FRACASSO; (*pp)->quant = 0; (*pp)->inicio = NULL; (*pp)->fim = NULL; (*pp)->tamInfo = tamInfo; return SUCESSO; } int insereLDDE(pLDDE p,void *novo,int posLog) { pNoLDDE aux,no; int pos = 1; /* Checa por posição válida */ if((posLog < -1) || (posLog == 0) || ((posLog-1) > p->quant)) return FRACASSO; /* Aloca Nó */ no = (pNoLDDE) malloc(sizeof(NoLDDE)); if(no == NULL) return FRACASSO; no->dados = malloc(p->tamInfo); memcpy(no->dados,novo,p->tamInfo); if(no->dados == NULL) { free(no); no = NULL; return FRACASSO; } no->ant = NULL; no->prox = NULL; /* Se estiver vazio, só inclue */ if(p->quant == 0) { p->inicio = no; p->fim = no; p->quant++; return SUCESSO; } /* Inserção no final */ if(posLog == FIM) { p->fim->prox = no; no->ant = p->fim; p->fim = no; p->quant++; return SUCESSO; } /* Pega a posição */ if(posLog < (p->quant/2)) /* Mais perto do início */ { aux = p->inicio; for(pos = 1; pos < posLog; pos++) aux = aux->prox; } else /* Mais perto do fim */ { aux = p->fim; for(pos = p->quant; pos > posLog; pos--) aux = aux->ant; }/* Inserção no início */ if(aux->ant == NULL) { no->prox = aux; aux->ant = no; p->inicio = no; p->quant++; return SUCESSO; } /* Inserção no meio */ aux->ant->prox = no; no->ant = aux->ant; no->prox = aux; aux->ant = no; p->quant++; return SUCESSO; } int removeLDDE(pLDDE p,int posLog) { pNoLDDE aux; int pos = 1; /* Checa por posição válida */ if((posLog < -1) || (posLog == 0) || posLog > p->quant) return FRACASSO; /* Pega a posição */ if(posLog < (p->quant/2)) /* Mais perto do início */ { aux = p->inicio; for(pos = 1; pos < posLog; pos++) aux = aux->prox; } else /* Mais perto do fim */ { aux = p->fim; for(pos = p->quant; pos > posLog; pos--) aux = aux->ant; } if(p->quant == 1) { p->fim = NULL; p->inicio = NULL; } else if(aux->ant == NULL) { aux->prox->ant = NULL; p->inicio = aux->prox; } else if(aux->prox == NULL) { aux->ant->prox = NULL; p->fim = aux->ant; } else { aux->ant->prox = aux->prox; aux->prox->ant = aux->ant; } free(aux->dados); free(aux); p->quant--; return SUCESSO; } int buscaLDDE(pLDDE p,void *destino,int posLog) { pNoLDDE aux; int pos = 1; /* Checa por posição válida */ if((posLog < -1) || (posLog == 0) || posLog > p->quant) return FRACASSO; /* Pega a posição */ if(posLog < (p->quant/2)) /* Mais perto do início */ { aux = p->inicio; for(pos = 1; pos < posLog; pos++) aux = aux->prox; } else /* Mais perto do fim */ { aux = p->fim; for(pos = p->quant; pos > posLog; pos--) aux = aux->ant; } memcpy(destino,aux->dados,p->tamInfo); return SUCESSO; } int testaVaziaLDDE(pLDDE p) { if(p->quant == 0) return SUCESSO; return FRACASSO; } int pegaTamanho(pLDDE p) { return p->quant; } void reiniciaLDDE(pLDDE p) { while(removeLDDE(p,INICIO)); } void destroiLDDE(ppLDDE pp) { reiniciaLDDE(*pp); free(*pp); *pp = NULL; } // Aplicação para demonstrar o uso #include <stdio.h> #include <stdlib.h> #include "interface.h" #define SIM 1 #define NAO 0 int ehPrimo(int); int main(int argc, char *argv[]) { /* Inicialização */ pLDDE lista; int quant = 0, aux = 0, i = 2; criaLDDE(&lista,sizeof(int)); /* Entrada de dados */ puts("Quantos números primos? "); scanf("%i",&quant); /* Cálculo */ while(aux < quant) { while(!ehPrimo(i)) i++; insereLDDE(lista,&i,FIM); i++; aux++; } /* Saída de dados */ aux = 1; printf("\nLista: \n"); while(aux <= quant) { buscaLDDE(lista,&i,aux); printf("%i\t",i); aux++; } /* Finalização */ destroiLDDE(&lista); } int ehPrimo(int num) { int i; if(num == 2) return SIM; /* Checa até a raiz do número */ for(i = 2;i*i <= num;i++) { if(num % i == 0) return NAO; } return SIM; }
Controle de estoque com listas
Pilhas Encadeadas Detalhadamente
Joguinho de labirinto usando as setas do teclado
Google Code Jam 2010 - Africa Classification Round A
Nenhum comentário foi encontrado.
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Arch Linux - Guia para Iniciantes (2)
Problemas ao instalar o PHP (11)
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (15)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)