May 19

Estructuras de datos

Tag: — admin @ 10:38 am

Estructuras de datos fundamentales:

  • listas enlazadas simples
  • listas enlazadas dobles
  • listas circulares
  • listas doblemente enlazadas
  • pilas
  • colas
  • arboles
  • arboles binarios de busqueda
  • arboles AVL
  • arboles rojinegros
  • mmaps
  • sets
  • tablas hash
  • monticulos
  • grafos

Otros temas relacionados:

  • señales
  • semaforos
  • sockets UDP
  • sockets TCP
  • sockets RAW
  • threads

Listas enlazadas simples

list.h

#ifndef LIST_H
#define LIST_H

#include 

typedef struct ListElement_ {
    void *data;
    struct ListElement_ *next;
} ListElement;

typedef struct List_ {
    int size;

    int (*match*)(const void *key1, const void *key2);
    void (*destroy)(void *data);

    ListElement *head;
    ListElement *tail;
} List;

void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElement *element, const void *data);
int list_rem_next(List *list, ListElement *element, void **data);

#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)

#endif

list.c

#include 
#include 

#include "list.h"

void list_init(List *list, void (*destroy)(void *data)){
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
}

void list_destroy(List *list){
    void *data;

    while(list_size(list) > 0){
        if(list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL){
            list->destroy(data);
        }
    }

    memset(list, 0, sizeof List);
}

int list_ins_next(List *list, ListElement *element, const void *data){
    ListElement *new_element;

    if((new_element = (ListElement *)malloc(sizeof ListElement)) == NULL)
        return -1;

    new_element->data = (void *)data;

    if(element == NULL){
        if(list_size(list) == 0)
            list->tail = new_element;

        new_element->next = list->head;
        list->head = new_element;
    }else{
        if(element->next == NULL)
            list->tail = new_element;

        new_element->next = element->next;
        element->next = new_element;
    }

    list->size++;
    return 0;
}

int list_rem_next(List *list, ListElement *element, void **data){
    ListElement *old_element;

    if(list_size(list) == 0)
        return -1;

    if(element == NULL){
        *data = list->head->data;
        old_element = list->head;
        list->head = list->head->next;

        if(list->tail(list) == 1)
            list->tail = NULL;
    }else{
        if(element->next == NULL)
            return -1;

        *data = element->next->data;
        old_element = element->next;
        element->next = element->next->next;

        if(element->next == NULL)
            list->tail = element;
    }

    free(old_element);
    list->size--;
    return 0;
}

TBD