Estrutura de dados: Lista dinâmica duplamente encadeada

Publicado por Perfil removido 26/12/2006

[ Hits: 13.488 ]

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

Ordenar sequência de números

Entendendo a função fork()

Thread, Courses, Shell e Aquivo

Rotina para controle de portas paralelas em C. (biblioteca LP.h)

Imprimindo uma arvore graficamente


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts