Estrutura de dados em C

Stack - Pilha
Queue - Fila
List - Lista
Hashtable - Tabela de espalhamento
Tree - Arvore

Uso

No projeto que fará uso das estruturas de dados, adicione esse repositório como um sub-módulo.

git submodule add <repository-url>

Exemplo Github

git submodule add https://github.com/<username>/<repository-name>.git <path>

Exemplo Repo

Criando um diretório para o projeto e acessando o diretório

mkdir -p project/src && cd project

Inicializando repositório git

git init

Adicionando lib no projeto

git submodule add https://github.com/dannRocha/adt.git src/lib/adt

Criando main.c no diretorio src.

// project/src/main.c
touch src/main.c

Conteúdo da main.c

#include <stdio.h>
#include <stdlib.h>
#include "lib/adt/adt.h"


int main() {

  list integers = NULL;
  list_create( &integers, free );

  for( int i = 0; i < 10; i++ )
    list_push( integers, new_int( i ) );


  for( int i = 0; i < list_length( integers ); i++ ) {
    void *value = NULL;
    list_get( integers, &value, i );
    printf( "%d\n", to_int( value ) );
  }

  list_destroy( &integers );

  return 0;
}

Compilando e executando

gcc main.c && ./a.out

Stack

São estruturas de dados do tipo LIFO (last-in first-out), onde o último elemento a ser inserido, será o primeiro a ser retirado. Assim, uma pilha permite acesso a apenas um item de dados - o último inserido.

stack_create

Função de inicialização da pilha.

void stack_create( struct stack **__stack, void( *ifree )( void* memory ) );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL; // or  stack numbers
  stack_create( &numbers, free );

  return 0;
}

Sempre inicialize a struct stack *<variable> com NULL.

struct stack *numbers = NULL;
//or
stack numbers = NULL;

O segundo parametro da função de criação da pilha (void( *ifree )( void* memory )) espera uma função que terá a responsabilidade de como será libarada a memória alocada;

Exemplo:

#include <stdlib.h>
#include "adt.h"

void my_free_function( void* memory );

int main() {

  struct stack *numbers = NULL;
  stack_create( &numbers, my_free_function );

  return 0;
}

void my_free_function( void* memory ) {
  free( memory );
}

stack_destroy

Função usada para liberar as memórias armazenadas na pilha.

void stack_destroy( struct stack **__stack );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {

  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  stack_destroy( &numbers );

  return 0;
}

A função stack_destroy pecorre toda a pilha liberando cada memória alocada chamando a função de liberação de memória customizada passada na create_stack. Levando em consideração o nome da variavel da pilha (numbers), a pilha conterá valores numericos, então a função void free(void *ptr); da stdlib.h é suficiente.

stack_push

Adiciona um item para o topo da pilha.

void stack_push( struct stack *__stack, void *value );

As estruturas de dados dessa biblioteca armazena endereços de memória e não valores, podendo assim trabalhar com vários tipos de dados. Há um trade-off nessa abordagem pois trocamos o acesso simples dos valores da estrutura pela reusabilidade das estruturas, causando uma grande quantidade do uso de casting para converter a memória em um tipo que pode ser usado nos algoritmos. É usado a heap para guarda os contéudos das estruturas de dados, então será necessário alocar dinamicamente a memória para os valores e guarda o endereço alocado nas estruturas de dados.

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  for( int i = 0; i < 10; i++ ) {
    int* value = new( int );
    *value = i;
    stack_push( numbers, value );
  }

  stack_destroy( &numbers );

  return 0;
}

Observe o trecho de código abaixo:

  int* value = new( int );
  *value = i;
  stack_push( numbers, value );

Um ponteiro pra inteiro é alocado ( int* value = new( int );), então nesse endereço é atribuido o valor da variavel i do loop for, e em seguida o endereço é adicionado na pilha (stack_push( numbers, value );).

⚠️ new

O new( <any> ) é uma macro para outra macro new_group(type, size) que apenas contém a expressão para calloc da stdlib.h.

#define new_group(type, size) (type*) calloc(sizeof(type), size)
#define new(type) new_group(type, 1)

Outra versão usando funções da biblioteca.

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  for( int i = 0; i < 10; i++ ) {
    stack_push( numbers, new_int( i ) );
  }

  stack_destroy( &numbers );

  return 0;
}

Funções utilitarias de inicialização de tipos primitivos clique aqui [ 1 ]

Funções utilitárias [ 1 ]

new_short
new_u_short
new_int
new_u_int
new_long
new_llong
new_float
new_double
new_char
new_string

As funções acima apenas diminui a verbosidade de alocar memória e atribuir valor. Não use fora da estrutura de dados evitando vazamento de memória através de escopo das funções.

Assinatura:

short* new_short( short value );

unsigned short* new_u_short( unsigned short value );

int* new_int( int value );

unsigned int* new_u_int( unsigned int value );

long* new_long (long value );

long long* new_llong (long long value );

float* new_float( float value );

double* new_double( double value );

char* new_char( char value );

char* new_string( const char* value );

stack_pop

Remove o item no topo da pilha e retorna esse item a endereço de memória armazenado no segundo parametro.

void stack_pop ( struct stack *__stack, void **value );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  // push
  stack_push( numbers, new_int( 1 ) );
  stack_push( numbers, new_int( 2 ) );

  // pop
  void *memory = NULL;
  stack_pop( numbers, &memory );
  int content = *( int* ) memory;

  printf( "%d\n", content );
  // output: 2

  numbers->free( memory );

  stack_destroy( &numbers);

  return 0;
}

O trecho que consome o valor armazenado na pilha:

  // pop
  void *memory = NULL;
  stack_pop( numbers, &memory );
  
  // casting
  int content = *( int* ) memory;

  printf( "%d\n", content );
  // output: 2

Observe que foi necessário realizar o cast da memória para um tipo manipulável.

Há trecho do código que deve ser levado em consideração:

  numbers->free( memory );

É necessário liberar manualmente a memória alocada, pois a estrutura de dados não tem mais a responsabilidade de liberar depois foi removido.

Outra versão usando funções da biblioteca.

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  // push
  stack_push( numbers, new_int( 1 ) );
  stack_push( numbers, new_int( 2 ) );

  // pop
  void *memory = NULL;
  stack_pop( numbers, &memory );
  
  printf( "%d\n", to_int( memory ) );
  // output: 2

  numbers->free( memory );

  stack_destroy( &numbers);

  return 0;
}

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

Funções utilitárias [ 2 ]

to_short
to_u_short
to_int
to_u_int
to_float
to_double
to_char
to_string

Assinatura:

short to_short( void* memory );

short to_u_short( void* memory );

int to_int( void* memory );

unsigned int to_u_int( void* memory );

float to_float( void* memory );

double to_double( void* memory );

char to_char( void* memory );

char* to_string( void* memory );

stack_peek

Olha para o item no topo da pilha sem removê-lo da pilha.

void stack_peek( struct stack *__stack, void **value );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  // push
  stack_push( numbers, new_int( 1 ) );
  stack_push( numbers, new_int( 2 ) );

  // peek
  void *memory = NULL;
  stack_peek( numbers, &memory );
  
  printf( "%d\n", to_int( memory ) );
  // output: 2

  stack_destroy( &numbers );

  return 0;
}

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

stack_clear

Remove todos os elemetos da pilha

void stack_clear( struct stack *__stack );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  // push
  stack_push( numbers, new_int( 1 ) );
  stack_push( numbers, new_int( 2 ) );

  // clear
  stack_clear( numbers );

  stack_destroy( &numbers );

  return 0;
}

stack_length

Retorna o número de elementos na pilha.

size_t stack_length( struct stack *__stack );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  // push
  stack_push( numbers, new_int( 1 ) );
  stack_push( numbers, new_int( 2 ) );

  // length
  printf( "%ld\n", stack_length( numbers ) );
  // output: 2

  stack_destroy( &numbers );

  return 0;
}

stack_is_empty

Retorna 1 para 'verdadeiro' se a pilha não contiver elementos e 0 para 'falso'.

bool stack_is_empty ( struct stack *__stack );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct stack *numbers = NULL;
  stack_create( &numbers, free );

  // is empty
  printf( "%d\n", stack_is_empty( numbers ) );
  // output: 1

  stack_destroy( &numbers );

  return 0;
}

Queue

Uma fila é uma estrutura linear que segue uma ordem particular na qual as operações são executadas. A ordem é First In First Out (FIFO).

Funções:

queue_create
queue_destroy
queue_push
queue_remove
queue_clear
queue_length
queue_is_empty

queue_create

Função de inicialização da fila.

void queue_create( struct queue **__queue , void( *ifree )( void *memory ) );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct queue *numbers = NULL; // or  queue numbers
  queue_create( &numbers, free );

  return 0;
}

Sempre inicialize a struct queue *<variable> com NULL.

struct queue *numbers = NULL;
//or
queue numbers = NULL;

Exemplo

#include <stdlib.h>
#include "adt.h"

void my_free_function( void* memory );

int main() {

  struct queue *numbers = NULL;
  queue_create( &numbers, my_free_function );

  return 0;
}

void my_free_function( void* memory ) {
  free( memory );
}

queue_destroy

Função usada para liberar as memórias armazenadas na fila.

void queue_destroy( struct queue **__queue );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {

  struct queue *numbers = NULL;
  queue_create( &numbers, free );

  queue_destroy( numbers );

  return 0;
}

queue_push

Adiciona um item para na fila.

void queue_push( struct queue *__queue, void *value );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct queue *numbers = NULL;
  queue_create( &numbers, free );

  for( int i = 0; i < 10; i++ ) {
    queue_push( numbers, new_int( i ) );
  }

  queue_destroy( &numbers );

  return 0;
}

Funções utilitarias de inicialização de tipos primitivos clique aqui [ 1 ]

queue_remove

Recupera e remove o primeiro elemento da fila.

void queue_remove( struct queue *__queue, void **value );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct queue *numbers = NULL;
  queue_create( &numbers, free );

  // push
  queue_push( numbers, new_int( 1 ) );
  queue_push( numbers, new_int( 2 ) );

  // remove
  void *memory = NULL;
  queue_remove( numbers, &memory );

  printf( "%d\n", to_int( memory ) );
  // output: 2

  numbers->free( memory );

  queue_destroy( &numbers);

  return 0;
}

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

queue_clear

Remove todos os elemetos da fila

void queue_clear( struct queue *__queue );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct queue *numbers = NULL;
  queue_create( &numbers, free );

  // push
  queue_push( numbers, new_int( 1 ) );
  queue_push( numbers, new_int( 2 ) );

  // clear
  queue_clear( numbers );

  queue_destroy( &numbers);

  return 0;
}

queue_length

Retorna o número de elementos na pilha.

void queue_destroy( struct queue **__queue );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct queue *numbers = NULL;
  queue_create( &numbers, free );

  // push
  queue_push( numbers, new_int( 10 ) );
  queue_push( numbers, new_int( 20 ) );

  // length
  printf( "%ld\n", queue_length( numbers ) );
  // output: 2

  queue_destroy( &numbers );

  return 0;
}

queue_is_empty

Retorna 1 para 'verdadeiro' se a fila não contiver elementos e 0 para 'falso'.

bool queue_is_empty( struct queue *__queue);

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct queue *numbers = NULL;
  queue_create( &numbers, free );

  // is empty
  printf( "%d\n", queue_is_empty( numbers ) );
  // output: 1

  queue_destroy( &numbers );

  return 0;
}

List

lista duplamente ligada é uma estrutura de dados ligada que consiste de um conjunto de registros sequencialmente ligados chamados de nós.

Funções

list_create
list_destroy
list_push
list_pop
list_shift
list_insert
list_remove
list_get
list_foreach
list_clear
list_length
list_index_of
list_contains
list_is_empty

list_create

Função de inicialização da lista.

void list_create( struct list **__list , void( *ifree )( void *memory ) );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct list *numbers = NULL;
  list_create( &numbers, free );

  return 0;
}

list_destroy

Função usada para liberar as memórias armazenadas na lista.

void list_destroy( struct list **__list );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct list *numbers = NULL;
  list_create( &numbers, free );

  list_destroy( &numbers );

  return 0;
}

list_create

Adiciona um elemento no final da lista

void list_push( struct list *__list, void *value );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct list *numbers = NULL;
  list_create( &numbers, free );

  for( int i = 0; i < 10; i++ ) {
    list_push( numbers, new_int( i ) );
  }

  list_destroy( &numbers );

  return 0;
}

Funções utilitarias de inicialização de tipos primitivos clique aqui [ 1 ]

Exemplo

#include <stdio.h>
#include <stdlib.h>
#include "adt.h"

struct book  {
  char* title;
  char* author;
};

void free_book_list ( void* memory );

int main() {
  
  struct list *books = NULL;
  list_create( &books, free_book_list );

  for( int i = 0; i < 10; i++ ) {
    struct book *book = new( struct book );
    
    book->title = ( char* ) malloc( sizeof( char ) * 7 );
    book->author = ( char* ) malloc( sizeof( char ) * 9 );
    
    sprintf( book->title, "Book %d", i );
    sprintf( book->author, "Author %d", i );

    list_push( books, book );
  }

  for( int i = 0; i < list_length( books ); i++ ) {
    void *value = NULL;
    list_get( books, &value, i );
    struct book *book = ( struct book* ) value;

    printf("[ %s : %s ]\n", book->author, book->title );
  }

  list_destroy( &books );

  return 0;
}

void free_book_list ( void* memory ) {
  struck book *book = ( struct book* ) memory;

  free( book->title );
  free( book->author );

  free( book ); // or free( memory );

}

Explicação sobre o "new ( <any> ) "

list_pop

Retorna e remove o ultimo elemento da lista.

void list_pop( struct list *__list, void **value );

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

list_shift

Remove o primeiro elemento da lista e retorna esse elemento removido.

void list_shift( struct list *__list, void **value );

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

list_insert

Insere um elemento em uma posição especificada na lista.

void list_insert( struct list *__list, void *value, int index );

Funções utilitarias de inicialização de tipos primitivos clique aqui [ 1 ]

list_remove

Remove e retorna um elemento em uma posição especificada da lista.

void list_remove( struct list *__list, void **value, int index );

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

list_get

Retorna um elemento na posição especificada da lista. Não libere a memória alocada através dessa função, caso queira remover e consumir um elemento da lista use a função list_remove.

void list_get ( struct list *__list, void **value, int index );

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

list_foreach

Executa uma ação para cada elemento da lista.

void list_foreach( struct list *__list, void( *callback )( void *memory, int index ) );

list_clear

Remove todos os elemetos da lista.

void list_clear( struct list *__list );

list_length

Retorna o número de elementos da lista.

size_t list_length( struct list *__list);

list_index_of

Retorna o índice da primeira ocorrência do elemento especificado na lista, ou -1 se esta lista não contiver o elemento.

int list_index_of( struct list *__list, void *value, bool( *comparator )( void *target_value, void *current_value ) );

list_contains

Retorna 1 para 'verdadeiro' se esta lista contiver o elemento especificado e 0 para 'falso'.

bool list_contains( struct list *__list, void *value, bool( *comparator )( void *target_value, void *current_value ) );

list_is_empty

Retorna 1 para 'verdadeiro' se esta lista não contiver elementos e 0 para 'falso'.

bool list_is_empty( struct list *__list );

Hashtable

Uma tabela de hash , também conhecida como mapa de hash , é uma estrutura de dados que implementa um tipo de dados abstrato de matriz associativa , uma estrutura que pode mapear chaves para valores

Funções

hashtable_create
hashtable_destroy
hashtable_put
hashtable_get
hashtable_contains
hashtable_replace
hashtable_get_keys
hashtable_foreach

hashtable_create

Função de inicialização da hashtable.

void hashtable_create( struct hashtable **__hashtable, void( *ifree )( void *memory )  );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct hashtable *table = NULL; 
  // or hashtable table = NULL;
  
  hashtable_create( &table, free );

  return 0;
}

hashtable_destroy

Função usada para liberar as memórias armazenadas na hashtable.

void hashtable_destroy( struct hashtable **__hashtable );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct hashtable *table = NULL;
  hashtable_create( &table, free );

  hashtable_destroy( table );

  return 0;
}

hashtable_put

Mapeia o especificado key para o especificado value na tabela de hash.

void hashtable_put( struct hashtable *__hashtable, const char* key, void *value );

Exemplo

#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct hashtable *table = NULL;
  hashtable_create( &table, free );

  // put
  hashtable_put( table, "firstname", new_string( "Daniel" ) );

  hashtable_destroy( table );

  return 0;
}

Funções utilitarias de inicialização de tipos primitivos clique aqui [ 1 ]

hashtable_get

Atribui o endereco de memória em (void **value) para o qual a chave especificada é mapeada ou NULL se esse mapa não contém mapeamento para a chave.

void hashtable_get( struct hashtable *__hashtable, const char* key, void **value );

Exemplo

#include <stdio.h>
#include <stdlib.h>
#include "adt.h"

int main() {
  
  struct hashtable *table = NULL;
  hashtable_create( &table, free );

  // put
  hashtable_put( table, "firstname", new_string( "Daniel" ) );

  void *value = NULL;
  hashtable_get( table, "firstname", &value );
  
  printf("FIRSTNAME: %s\n",  to_string( value ) );
  // output: FIRSTNAME: Daniel


  hashtable_destroy( table );

  return 0;
}

Funções utilitárias de casting de tipos primitivos clique aqui [ 2 ]

hashtable_contains

Testa se uma chave existe na tabela de hash.

bool hashtable_contains( struct hashtable *__hashtable, const char* key );

hashtable_replace

Substitui a entrada da chave especificada somente se ela estiver mapeada atualmente para algum valor.

void hashtable_replace( struct hashtable *__hashtable, const char* key, void *value );

hashtable_get_keys

Preenche uma struct list * previamente inicializa com as chaves da contidas na hashtable.

void hashtable_get_keys( struct hashtable *__hashtable, struct list *__list );

hashtable_foreach

Executa a ação para cada entrada na hashtable até que todas as entradas tenham sido processadas.

void hashtable_foreach( struct hashtable *__hashtable, void( *consumer )( char* key, void *value ) );

danroxha / adt Goto Github PK

adt's Introduction

Estrutura de dados em C

Uso

Exemplo Github

Exemplo Repo

Stack

Funções:

stack_create

Exemplo

Exemplo:

stack_destroy

Exemplo

stack_push

Exemplo

⚠️ new

stack_pop

Exemplo

stack_peek

Exemplo

stack_clear

Exemplo

stack_length

Exemplo

stack_is_empty

Exemplo

Queue

Funções:

queue_create

Exemplo

Exemplo

queue_destroy

Exemplo

queue_push

Exemplo

queue_remove

Exemplo

queue_clear

Exemplo

queue_length

Exemplo

queue_is_empty

Exemplo

List

Funções

list_create

Exemplo

list_destroy

Exemplo

list_create

Exemplo

Exemplo

list_pop

list_shift

list_insert

list_remove

list_get

list_foreach

list_clear

list_length

list_index_of

list_contains

list_is_empty

Hashtable

Funções

hashtable_create

Exemplo

hashtable_destroy

Exemplo

hashtable_put

Exemplo

hashtable_get

Exemplo

hashtable_contains

hashtable_replace

hashtable_get_keys

hashtable_foreach

adt's People

Contributors

Watchers