Estrutura de dados: Lista dinâmica duplamente encadeada
Publicado por Perfil removido 26/12/2006
[ Hits: 13.646 ]
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; }
Tipos de Dados Abstrato - TDA - Vetor
Nenhum coment�rio foi encontrado.
Conciliando o uso da ZRAM e SWAP em disco na sua máquina
Servidor de Backup com Ubuntu Server 24.04 LTS, RAID e Duplicati (Dell PowerEdge T420)
Visualizar câmeras IP ONVIF no Linux sem necessidade de instalar aplicativos
Realizar overclock no Miyoo Mini (plus ou normal)
Otimização de memória para máquinas modestas
Direcionar uma URL para Outra No Mikrotik (0)
linux mint reconhece microfone de lapela como fone de ouvido sem micro... (1)