Estrutura de dados: Lista dinâmica duplamente encadeada

Publicado por Perfil removido 26/12/2006

[ Hits: 12.455 ]

Download ldde.tar.gz




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.

  



Esconder código-fonte

// 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;
}

Scripts recomendados

Agenda feita em C usando árvore binária

Controle de estoque com listas

Arvores AVL - Completo

Arquivos utilizados no artigo: "Desenvolvendo um plugin para o XMMS"

Biblioteca ctype.h


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts