Estrutura de dados: Lista dinâmica duplamente encadeada

Publicado por Perfil removido 26/12/2006

[ Hits: 13.082 ]

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

Função HASH em C++

Biblioteca math.h

Leitura de String

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

Agenda feita em C usando árvore binária


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário