Pilha, lista duplamente encadeada e Fila - linguagem C

[Bruno Pacheco]

Alguém pode me dar um exemplo de um código implementando lista duplamente encadeada, lista e pilha? Eu sei implementar as três separadamente minha maior dificuldade é unir tudo num só código. :mellow:

[Durub]

Separe os três por "unidades"! Então:

Lista duplamente encadeada:

listadup.c

listadup.h

Lista:

lista.c

lista.h

Pilha:

pilha.c

pilha.h

Quando quiser usar uma, só incluir a "{estrutura}.h".

Abraços!

[Bruno Pacheco]

Bom a minha dúvida não é essa!

-->Por exemplo, preciso inserir: partidas de futebol e gols em uma lista duplamente encadeada, nomes e pontuação em uma pilha.Apartir

daí faço então duas funções de inserção uma para lista duplamente encadeada e outra para pilha.

-->Pensei pegar por exemplo uma fila e inserir nela o que ta na lista e o que ta na pilha ( exemplo: colocar na fila partidas de futebol e gols e nomes e pontuação ). Apartir daí faço uma função de inserção para fila tambem.

exemplo de inserção em fila:

void Push (Pilha* pilha, float v){
        
        if (pilha->n == MAX) { 
        exit(1); /* aborta programa – stdlib.h *//
}
/* insere elemento na próxima posição livre */
        pilha->vet[pilha->n] = v;
        pilha->n++;//O CAMPO N DA ESTRUTURA PILHA É APONTADO PARA O PRÓXIMO ELEMENTO
}

--> Como posso fazer uma função de inserção de fila contendo elementos de uma lista duplamente encadeada e de uma pilha? :mellow:

Editado Junho 28, 2010 por Bruno Pacheco

[Durub]

Use um ponteiro para void.

Exemplo de pilha (fiz a um bom tempo atrás, tem um bug na stack_contract)

#include "stack.h"
#include "mem.h"
#include "assert.h"

/* ALLOCATION */
stack_t *stack_alloc(int quantity) {
    stack_t *stack = stack_create();
    
    assert(quantity);
    return stack_expand(stack, quantity);
}

stack_t *stack_create() {
    stack_t *stack = ALLOC(sizeof(stack_t));
    
    stack->_top = NULL;
    stack->_stacked = 0;
    stack->_alloc = 0;
    return stack;
}

stack_t *stack_expand(stack_t *stack, int quantity) {
    int by_how_many = (quantity + stack->_alloc) * sizeof(ptr_t *);
    int factor;
    
    stack->_alloc += quantity;
    if(stack->_stacked != 0) {
        factor = stack->_stacked - 1;
        stack->_top = realloc(stack->_top - factor, by_how_many);        
        stack->_top += factor;
    } else {
        stack->_top = realloc(stack->_top, by_how_many);
    }
    
    return stack;
}

stack_t *stack_contract(stack_t *stack) {
    return stack; /* not implemented correctly yet */
    
    int by_how_many = stack->_stacked * sizeof(ptr_t *);
    
    stack->_alloc = stack->_stacked;
    stack->_top = realloc(stack->_top - stack->_stacked + 1, by_how_many);
    
    return stack;
}

void stack_free(stack_t **stack) {
    assert(*stack);
    
    if((*stack)->_top != NULL) {
        if((*stack)->_stacked != 0) {
            free((*stack)->_top - ((*stack)->_stacked - 1));
        } else {
            free((*stack)->_top);
        }
    }
    
    FREE(*stack)
}

/* ELEMENTS */
void *stack_top(stack_t *stack) {
    return (void *) *(stack->_top);
}

void *stack_pop(stack_t *stack) {    
    assert(stack->_stacked > 0);
    
    stack->_stacked--;
    if(stack->_stacked == 0)
        return (void *) *(stack->_top);
    else
        return (void *) *(stack->_top--);
}

void stack_push(stack_t *stack, void *value) {
    if(stack->_alloc <= stack->_stacked) {
        stack_expand(stack, STACK_EXPANSION_FACTOR);
    }
    
    if(stack->_stacked++ > 0) {
        stack->_top++;
    }
    
    *(stack->_top) = (ptr_t) value;
} 

int stack_empty(stack_t *stack) {
    return stack->_stacked == 0 ? 1 : 0;
}

Para alguns tipos você vai ter que usar uma conversão "especializada":

void stack_push_float(stack_t *stack, float value) {
    float *persistent = ALLOC(sizeof(float));
    
    *persistent = value;
    stack_push(stack, persistent);
}

float stack_pop_float(stack_t *stack) {
    float *persistent;
    float temp;
    
    persistent = (float *) stack_pop(stack);
    temp = *persistent;
    free(persistent);
    
    return temp;
}

stack.h:

#ifndef STACK_H
#define STACK_H

#include "mem.h"

typedef struct stack_s {
    ptr_t *_top;
    ptr_t *_ptr;
    int _stacked;
    int _alloc;
} stack_t;

/* ALLOCATION */
stack_t *stack_alloc(int quantity);
stack_t *stack_create();
stack_t *stack_expand(stack_t *stack, int quantity);
stack_t *stack_contract(stack_t *stack);
void     stack_free(stack_t **stack);

/* ELEMENTS */
void *stack_top(stack_t *stack);
void *stack_pop(stack_t *stack);
void  stack_push(stack_t *stack, void *value);
int   stack_empty(stack_t *stack);

/* STACK EXPANSION FACTOR
 -> How much should go into quantity in a call to
    stack_expand when there's no allocated blocks left 
 -> Maximum space waste is (STACK_EXPANSION_FACTOR * 8) (bytes) */
#define STACK_EXPANSION_FACTOR 1

#define print_stack(s) \
    do { \
    printf("Stack ");\
    printf(#s);\
    printf(" %p \n", s);\
    printf("Number of elements: %d\nNumber of allocated blocks: %d\nTop element: %d\n\n", (s)->_stacked, (s)->_alloc, *((int *) stack_top(s))); \
    } while(0);

#endif

mem.h:

#ifndef MEM_H
#define MEM_H

#include <stdlib.h>
#include <assert.h>

static void *__graph__alloc_mem(int size) {
    void *block = malloc(size);

    assert(block);
    return block;
}

static void __graph__free_mem(void *ptr) {
    assert(ptr != NULL);

    free(ptr);
}

// coloque para 1 se estiver compilando para 64 bits (meu caso)
#define IS_64_BITS 0

#ifdef IS_64_BITS
    typedef long long ptr_t;
#else
    typedef int ptr_t;
#endif

#define DEBUG 1

#ifdef DEBUG
    #define ALLOC(x) __graph__alloc_mem(x);
    #define FREE(x) do { __graph__free_mem(x); x = 0; } while(0);
    #define free(x) __graph__free_mem(x);
#else
    #define ALLOC(x) malloc(x);
    #define FREE(x) do { free(x); x = 0; } while(0);
    #define free(x) do { assert(x != NULL); free(x); } while(0);
#endif
#endif

Ficou grande, mas acho que codeboxes prejudicam a legibilidade do "conjunto".

Abraços!