"Menu" estrutura de dados e algorítmos para copy-paste

[Thiago Adams]

Pedi ao chatGPT que criasse uma lista simplesmente encadeada em C.

Funcionou! Ele gerou um exemplo e esta ideia de ter um assistente para

gerar código pareceu boa.

Porém, o resultado foi um código estilo educacional  sem o devido cuidado

com o tratamento de erros.

Então é bem legal para aprender, mas se eu quiser usar este código em

produção qual é a garantia?

Pensando nisso decidi criar um repositório com um "menu" de estrutura de

dados que eu possa confiar para um copy paste no futuro.

O projeto está no início, comecei com a lista ligada mas quis compartilhar

desde agora pois talvez seja um projeto bem interessante para ser colaborativo.

O primeiro objetivo é ter os exemplo, vantagens desvantagens etc e depois

ir validando e passando a segurança.

https://github.com/thradams/data-structures-and-algorithms

Mais adiante pensei em ter um site PWA com uma interface estilo

autoatendimento de hambúrguer, aonde a pessoa seleciona o que

quer e  diz os opcionais ou extras. Este interface pode assistir/ajudar

o programador a decidir o que precisa fazendo algumas perguntas

oferendo sugestões.

[Thiago Adams]

Uma diferença entre este repositório e por exemplo outro que tenha uma "STL"

para C  é que este não tenta implementar código através de macros.

Ele não é um repositório de "lib".

Ao invés disso ele é um repositório de exemplos concretos.

Serão escolhidos tipos que representam bem categorias de acordo com atributos

do tipo "cópia barata?" estilo um int, ou este tipo precisa de um destrutor etc..

Será colocado um exemplo para cada coisa.

Combinações de funcionalidades podem ocorrer e é mais um motivo

da importância do gerador para não termos que ter milhares de combinações de

exemplos.

Não sei quem mais trabalha com C, mas algo que ocorre (quando não se usa C++ STL)

é que o tipos de dados acabam sendo a abstração.

Por exemplo, em C++ você pode fazer uma classe SymbolTable com funções específicas

e dentro dela ter um std::map que só tem a parte do mapa.

Já em um exemplo de estrutura em C, acaba que struct SymbolTable já é por si as duas

coisas. Então se começa com um exemplo e vai modificando ao invés de ir acoplando

partes.

[Thiago Adams]

On Monday, March 20, 2023 at 9:12:24 AM UTC-3 Thiago Adams wrote:

Pedi ao chatGPT que criasse uma lista simplesmente encadeada em C.

Funcionou! Ele gerou um exemplo e esta ideia de ter um assistente para

gerar código pareceu boa.

Porém, o resultado foi um código estilo educacional  sem o devido cuidado

com o tratamento de erros.

Outra coisa engraçada dos exemplos educacionais é que muitas

vezes  eles tem uma variável global para fazer a estrutura de dados.

Alguns exemplos de lista encadeada  tem um "node *head" global.

Já pensaram uma coisa assim em código real? Também ao invés

de ter uma lista com um "tail" tem um loop para andar até o fim

da lista e depois inserir.  Sério, já pensou em ter isso em um código

real para economizar 1 ponteiro sendo que a lista pode N objetos?

Além disso, alguns código educacionais ainda terão um printf no meio.

Imagine um programa rodando e ir dizendo "inseriu nó tal.." etc.

Ou seja, exemplos educacionais nem sempre são bons para código real.

Este repositório tem a intenção de ter os exemplo reais.

[Felipe Magno de Almeida]

On Mon, Mar 20, 2023 at 9:12 AM Thiago Adams <thiago...@gmail.com> wrote:
>

Bom dia Thiago,

> Pedi ao chatGPT que criasse uma lista simplesmente encadeada em C.
> Funcionou! Ele gerou um exemplo e esta ideia de ter um assistente para
> gerar código pareceu boa.

O que me passou pela cabeça agora é que vai dificultar minhas
entrevistas isso aí.

> --
> http://ccppbrasil.github.io/
> https://twitter.com/ccppbrasil

Abraços,
--
Felipe Magno de Almeida
Owner @ Expertise Solutions
www: https://expertise.dev
phone: +55 48 9 9681.0157
LinkedIn: in/felipealmeida

[Thiago Adams]

Se alguém tiver curiosidade,  este é o código gerado pelo chatgpt para lista ligada.

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

// Define the node structure
struct node {
    int data;
    struct node* next;
};

// Function to create a new node
struct node* createNode(int data) {
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the beginning of the linked list
void insertAtBeginning(struct node** headRef, int data) {
    struct node* newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

// Function to insert a node at the end of the linked list
void insertAtEnd(struct node** headRef, int data) {
    struct node* newNode = createNode(data);
    if (*headRef == NULL) {
        *headRef = newNode;
    }
    else {
        struct node* temp = *headRef;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// Function to display the linked list
void displayList(struct node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Function to delete the entire linked list
void deleteList(struct node** headRef) {
    struct node* current = *headRef;
    struct node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *headRef = NULL;
}

// Main function to test the linked list implementation
int main() {
    struct node* head = NULL;
    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtBeginning(&head, 0);
    insertAtEnd(&head, 3);
    printf("Linked list: ");
    displayList(head);
    deleteList(&head);
    return 0;
}

[Thiago Adams]

E este é  o código gerado para "dynamic array"

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

// Define the dynamic array structure
struct dynamicArray {
    int* array;
    int size;
    int capacity;
};

// Function to create a new dynamic array
struct dynamicArray* createDynamicArray() {
    struct dynamicArray* da = (struct dynamicArray*)malloc(sizeof(struct dynamicArray));
    da->size = 0;
    da->capacity = 1;
    da->array = (int*)malloc(da->capacity * sizeof(int));
    return da;
}

// Function to get the value at a specific index in the dynamic array
int getValue(struct dynamicArray* da, int index) {
    if (index < 0 || index >= da->size) {
        printf("Error: Index out of bounds\n");
        return -1;
    }
    return da->array[index];
}

// Function to set the value at a specific index in the dynamic array
void setValue(struct dynamicArray* da, int index, int value) {
    if (index < 0 || index >= da->size) {
        printf("Error: Index out of bounds\n");
        return;
    }
    da->array[index] = value;
}

// Function to append a value to the end of the dynamic array
void appendValue(struct dynamicArray* da, int value) {
    if (da->size == da->capacity) {
        da->capacity *= 2;
        da->array = (int*)realloc(da->array, da->capacity * sizeof(int));
    }
    da->array[da->size++] = value;
}

// Function to remove the value at a specific index in the dynamic array
void removeValue(struct dynamicArray* da, int index) {
    if (index < 0 || index >= da->size) {
        printf("Error: Index out of bounds\n");
        return;
    }
    for (int i = index; i < da->size - 1; i++) {
        da->array[i] = da->array[i + 1];
    }
    da->size--;
}

// Function to display the contents of the dynamic array
void displayArray(struct dynamicArray* da) {
    printf("[ ");
    for (int i = 0; i < da->size; i++) {
        printf("%d ", da->array[i]);
    }
    printf("]\n");
}

// Main function to test the dynamic array implementation
int main() {
    struct dynamicArray* da = createDynamicArray();
    appendValue(da, 1);
    appendValue(da, 2);
    appendValue(da, 3);
    displayArray(da);
    setValue(da, 0, 0);
    displayArray(da);
    removeValue(da, 1);
    displayArray(da);
    free(da->array);
    free(da);
    return 0;
}

Ao meu ver o nosso emprego esta garantido por enquanto :D

Mas olhando estes exemplos vocês podem imaginar porque seria legal ter

um gerador de qualidade. (Claro que o chatGPT tem um grande mérito e provavelmente

 ele poderia aprender com exemplos melhores)

[Thiago Adams]

Hashmap gerado pelo chat GPT

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 1000

// Definição da estrutura do elemento da tabela hash
typedef struct Element {
    char* key;
    int value;
    struct Element* next;
} Element;

// Definição da estrutura da tabela hash
typedef struct HashTable {
    Element** buckets;
} HashTable;

// Função hash simples que retorna um índice a partir da chave
unsigned int hash(char* key) {
    unsigned int hashval = 0;
    for (; *key != '\0'; key++) {
        hashval = *key + 31 * hashval;
    }
    return hashval % TABLE_SIZE;
}

// Função que cria e retorna um novo elemento
Element* new_element(char* key, int value) {
    Element* elem = (Element*)malloc(sizeof(Element));
    elem->key = key;
    elem->value = value;
    elem->next = NULL;
    return elem;
}

// Função que cria e retorna uma nova tabela hash
HashTable* new_hash_table() {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    table->buckets = (Element**)calloc(TABLE_SIZE, sizeof(Element*));
    return table;
}

// Função que insere um elemento na tabela hash
void insert(HashTable* table, char* key, int value) {
    unsigned int index = hash(key);
    Element* elem = new_element(key, value);
    elem->next = table->buckets[index];
    table->buckets[index] = elem;
}

// Função que busca e retorna o valor associado à chave na tabela hash
int search(HashTable* table, char* key) {
    unsigned int index = hash(key);
    Element* elem = table->buckets[index];
    while (elem != NULL) {
        if (strcmp(elem->key, key) == 0) {
            return elem->value;
        }
        elem = elem->next;
    }
    return -1;
}

// Função que remove um elemento da tabela hash
void remove_element(HashTable* table, char* key) {
    unsigned int index = hash(key);
    Element* elem = table->buckets[index];
    Element* prev = NULL;
    while (elem != NULL) {
        if (strcmp(elem->key, key) == 0) {
            if (prev == NULL) {
                table->buckets[index] = elem->next;
            }
            else {
                prev->next = elem->next;
            }
            free(elem);
            return;
        }
        prev = elem;
        elem = elem->next;
    }
}

// Função que imprime os elementos da tabela hash
void print_table(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Element* elem = table->buckets[i];
        while (elem != NULL) {
            printf("Key: %s, Value: %d\n", elem->key, elem->value);
            elem = elem->next;
        }
    }
}

// Função principal
int main()
{
    HashTable* table = new_hash_table();

    // Exemplo de inserção de elementos
    insert(table, "key1", 1);
    insert(table, "key2", 2);

}

Neste código , inserindo duas vezes com a mesma chave gera um leak.

[Thiago Adams]

Este é meu código para dynamic array de int. (equivalente vector<int>)

https://github.com/thradams/data-structures-and-algorithms/blob/main/array1.md

Podem enviar os erros!

Talvez alguém estranhe mas gosto de usar int para size e capacity.

Fiz um teste, e o erro da falta de memoria de um realloc vai ocorrer bem antes

de acabar o int.

No meu teste (windows etc etc) ele deu out of mem no indice  204324850 então x 4

que é size of int seria 817.299.400 bytes ~8M.

Cada código tem uma história requisitos etc..(que é a função do ser humano julgar)

A estratégia de crescimento foi aumentar mais metade do que já se tem.

[Thiago Adams]

Link para gerador online (array e lista) por enquanto

http://thradams.com/generator/singly_linked_list.html