Introdução a Estruturas de Dados

Estruturas de dados são a espinha dorsal de qualquer software, mas para muitos iniciantes ou até mesmo programadores experientes, esse conceito pode parecer abstrato ou até assustador. O objetivo deste artigo é servir como ponto de partida e dar uma introdução a estruturas de dados de forma simples e prática.

Vamos abordar desde o conceito básico de dados até uma introdução às estruturas mais conhecidas, com exemplos claros e objetivos.

Se você está começando ou quer reforçar suas bases, este guia é para você.

O Que São Dados e Como o Computador os Representa?

Antes de falar sobre estruturas de dados, é essencial entender o que são dados e como eles são tratados por um computador.

O Que São Dados?

A grosso modo, o computador trabalha com dois tipos de informações, dados e instruções. Dados são informações que podem ser interpretadas ou processadas, enquanto as instruções são o direcionamento de como o computador vai processar esses dados.

Podemos classificar os dados em 3 tipos principais:

• Numéricos (Inteiros e reais): Como 5, 42, 47.3 ou -10.
• Caracteres: Como “Olá, mundo!”.
• Lógicos: Como verdadeiro (true) ou falso (false).

Em resumo, qualquer pedaço de informação que você quiser armazenar ou manipular em um programa é considerado dado.

Como o Computador Representa os Dados?

Os computadores trabalham em seu nível mais interno, apenas com sinais elétricos digitais que podem assumir dois valores básicos ligado = 1 e desligado = 0. Tudo que um computador faz, acaba se resumindo a uma sequência de zeros ou uns.

Cada 0 ou 1 é chamado de bit, e agrupamentos de 8 bits formam um byte. Tudo no computador — texto, números, imagens, sons — é traduzido para essa linguagem binária, ou seja, é representado como bits e bytes.

Por exemplo:

• O número 5 em binário é representado como 00000101.
• A letra A é traduzida para binário com base em tabelas como a ASCII (por exemplo, 01000001).

Essa representação simplificada permite ao computador processar e armazenar grandes volumes de informações.

Tipos Primitivos de Dados

Os tipos de dados mais básicos presentes em um programa de computador, são chamados de tipos primitivos. Esses tipos são usados como base para a construção de todas as estruturas de dados mais complexa, e estão presentes em todas as linguagens de programação.

Os tipos primitivos mais básicos são:

Números Inteiros (integers)

Números inteiros representam valores numéricos sem casas decimais, como -10, 0 ou 42.

Os números inteiros são armazenados como sequências de bits (0s e 1s), então para entender como um computador representa um número inteiro, basta convertê-lo de decimal para binário.

Para representar números negativos, as linguagens de programação adotam um padrão de reservar o bit mais a esquerda do número para representar o sinal (0 para positivo, e 1 para negativo).

Além disso, é possível representar um número inteiro sem sinal, dessa forma, usando todos os bits para representação do próprio valor do número, permitindo números maiores, mas sem valores negativos.

Exemplo: Para um inteiro de 8 bits (1 byte):

1. Para uma variável do tipo inteiro com sinal, o número 37 é representado como 00100101, enquanto o número -37 é representado como 10100101;
2. Se definirmos a variável como tipo inteiro sem sinal, o número 37 continua sendo igual a 00100101, porém o número -37 não existe, nesse caso, o dígito mais a esquerda faz parte do número, então usando o número 10100101 do exemplo anterior, ao invés de -37, nesse caso, o valor da variável seria o número 165.

Para fazer testes por conta própria, você pode utilizar esse conversar de número decimal em binário.

O intervalo de valores que podem ser representados, vai depender da quantidade de bytes utilizados para representar o número. A tabela abaixo demonstra quantos números podem ser representados em uma variável do tipo inteiro, de acordo com o tamanho da variável em bytes.

Números de Ponto Flutuante (floats)

Números de ponto flutuante, são a forma como o computador representa números racionais, como 3.14, 0.1 ou 0.999....

A representação de um número de ponto flutuante pelo computador, de maneira simplificada, é feita da seguinte maneira:

Os bits do número são divididos em 3 partes, sinal, expoente, e mantissa. A mantissa define o valor do número, e o expoente a magnitude, ou seja, a posição da vírgula.

Para um número de ponto flutuante de 4 bytes, uma representação comum é 1 bit para sinal S, 8 bits para expoente E, e 23 bits para mantissa M. E a conversão do número é feita através da fórmula n = (-1)^S x 2^{(E – 127)} x 1,M.

Exemplo. Número 35.5 representado em ponto flutuante:

• Sinal: 0
• Expoente: 10000100₂ = 132₁₀
• Mantissa: 00011100000000000000000₂

Aplicando na fórmula temos:

(-1)⁰ x 2^{(132 – 27)} x 1.00011100000000000000000₂ = 1 x 2⁵ x 1.109375₁₀ = 35.5

Não vamos aprofundar tanto na aritmética de ponto flutuante nesse artigo, caso você tenha interessa em aprofundar, você pode checar esse artigo do IME com uma Introdução aos números em ponto flutuante. Caso queira verificar na prática a conversão, pode utilizar essa calculadora de ponto flutuante.

Caracteres (Texto)

Para a representação de caracteres, é usada uma tabela que mapeia números em caracteres de texto, como a tabela ASCII. Cada caractere é associado a um número decimal, e que internamente é convertido para binário para o computador processar.

Booleanos

Dados booleanos, são aqueles utilizados para representar o resultado de expressões lógicas, ou seja, possuem apenas dois valores possíveis, Verdadeiro e Falso.

Algumas linguagens possuem tipos específicos para representar valores booleanos, e palavras reservadas para representar os valores possíveis, como no exemplo abaixo em Java:

boolean trueValue = true;
boolean falseValue = false;

Outras linguagens, como C, não possuem tipos dedicados pra isso, e utilizam apenas os números 1 ou 0 para representar os valores lógicos, 1 é igual a verdadeiro e 0 é igual a falso.

int trueVale = 1;
int falseValue = 0;

Tipos Estruturados de Dados

Tipos estruturados de dados, são estruturas que permitem organizar dados de maneira mais complexa. Diferente dos tipos primitivos de dados, que podem assumir um único valor, os tipos estruturados são compostos por múltiplos valores, sendo esses valores de tipos primitivos, outros tipos estruturados, e de mesmo tipo ou tipos diferentes.

Os tipos estruturados mais conhecidos são os vetores, matrizes e registros.

O que são vetores e matrizes?

Vetores e matrizes, ou arrays, são tipos estruturados de dados que servem para organizar um conjunto de dados do mesmo tipo, em uma estrutura indexada, que permite acessar cada um dos valores individuais de forma direta.

Os arrays são utilizados em situações onde precisamos trabalhar com listas longas de dados de mesmo tipo, e precisamos acessar esses dados de maneira direta, nesse caso, ao invés de declarar múltiplas variáveis, podemos declarar apenas um array com o tamanho igual à quantidade máxima de dados que vamos precisar.

A diferença entre vetores e matrizes, é que vetores são uma estrutura unidimensional, enquanto matrizes podem ter diversas dimensões.

Podemos entender uma matriz como um vetor de vetores, formando uma estrutura bidimensional … da mesma forma, podemos criar um vetor de matrizes, passando a ter uma estrutura tridimensional, e assim por diante.

O que são registros

Registros ou structs, são tipos de dados que permitem agrupar valores de diferentes tipos, permitindo definir um tipo de dado customizado, e que possa assumir um papel semântico mais complexo.

Por exemplo, podemos definir um registro chamado Usuario que possua o nome, a idade, e o cpf do usuário, e então declarar variáveis com o tipo Usuario e guardar todos esses dados em uma única variável do nosso programa.

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

struct Usuario {
    char nome[50];
    int idade;
    char cpf[11];
};

int main()
{
    struct Usuario u;
    strcpy(u.nome, "Amauri");
    u.idade = 30;
    strcpy(u.cpf, "12345678901");

    printf("Nome: %s\n, Idade: %d\n, CPF: %s\n", u.nome, u.idade, u.cpf);

    return 0;
}

Tipos Abstratos de Dados (TADs)

Tipos Abstratos de Dados ou TADs, é um conceito teórico dentro da Ciência da Computação que visa definir de maneira abstrata conjuntos de dados, suas relações, operações, e regras para organização, e manipulação, sem se preocupar com os detalhes específicos da implementação dessas regras.

Um exemplo, é o TAD Pilha, que define uma estrutura onde é possível inserir múltiplos elementos, e que esses elementos devem obrigatoriamente serem removidos na ordem contrária em que foram inseridos, ou seja, o último elemento a entrar, é o primeiro sair.

Uma pilha pode ser implementada utilizando um vetor, ou pode ser implementada usando uma estrutura dinâmica baseada em registros, como uma lista encadeada, pouco importa, desde que siga a regra mencionada acima, e garanta a ordem correta de entrada, e saída dos elementos.

Alguns TADs comuns são, Filas, Pilhas, Grafos, Árvores, Tabelas Hash.

O Que São Estruturas de Dados?

O termo “estruturas de dados” pode ser utilizado em qualquer contexto que envolva algum dos tipos mais complexos de dados mencionados anteriormente, qualquer grupo de dados estruturado de maneira organizada, buscando realizar operações específicas pode ser considerado uma estrutura de dados.

Mas no geral, sempre que você encontrar o termo “estruturas de dados” por aí, o contexto vai ser a implementação de algum dos TADs conhecidos.

Como dito na sessão anterior, o Tipo Abstrato de Dados, vai definir as regras para organização dos dados e operações que devem ser realizadas nesses dados, enquanto a estrutura de dados em si, vai tratar de todos os detalhes da implementação.

Por Que Você Precisa Saber Sobre Estruturas de Dados?

Entender estruturas de dados é essencial por várias razões:

1. Eficiência no Código: Escolher a estrutura certa pode melhorar drasticamente a performance do seu programa.
2. Habilidade de Resolver Problemas: Muitos desafios em programação envolvem organizar e processar dados de forma eficiente.
3. Relevância em Entrevistas Técnicas: Entrevistas de emprego frequentemente testam seu entendimento de estruturas como listas, pilhas ou árvores.
4. Aplicações Reais: Estruturas de dados estão presentes em quase tudo, desde mecanismos de busca até aplicativos de redes sociais.

Quando e Como Escolher a Estrutura de Dados Certa?

A escolha da estrutura de dados depende de:

1. Operações frequentes: Como busca, inserção ou remoção.
2. Volume de dados: Grandes conjuntos podem exigir estruturas otimizadas.
3. Memória disponível: Algumas estruturas consomem mais memória do que outras.

Exemplos:

• Pilha: Ideal para tarefas como desfazer/redo.
• Hash: Ideal para cenários onde temos um conjunto grande dados em memória, te teremos muitas buscas por uma chave específica;
• Árvore B: Ideal quando temos que trabalhar com dados salvos em disco.

Livros sobre estruturas de dados

Mesmo sendo plenamente possível entender estruturas de dados de maneira efetiva com conteúdos disponíveis na Internet e em cursos, é importante saber que boa parte desses conteúdos, vai ter como base alguns livros que são referência na área. Então caso queira se aprofundar, e entender mais detalhadamente do assunto, é recomendado procurar alguma dessas referências.

Abaixo cito alguns livros que são referência em boa parte dos cursos de computação:

1. “Algoritmos – Teoria e Prática” – Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
   • A bíblia dos algoritmos e estruturas de dados, popularmente conhecido apenas como “Cormen”.
   • Cobre estruturas de dados e algoritmos de forma detalhada e abrangente. É ideal para estudantes universitários.
   • É base pra todo curso de computação. Se quiser buscar um único livro para entender sobre a base teórica, vá com o “Cormen”.

1. “Projeto De Algoritmos Com Implementações Em Pascal E C” – Nivio Ziviani
   • Escrito pelo Prof. Nivio Ziviani da UFMG, é um dos melhores livros para se aprender algoritmos básicos e estruturas de dados.

1. “Cracking the Coding Interview” – Gayle Laakmann McDowell
   • Inclui uma revisão de conceitos fundamentais de estruturas de dados.
   • Focado em exercícios práticos e entrevistas de programação.
   • Passa pelo conteúdo de maneira superficial, mas pra quem deseja apenas entender por alto e ter exemplos de aplicações das estruturas de dados em entrevistas de programação, é uma boa escolha.

Conclusão

Estruturas de dados são essenciais para qualquer desenvolvedor. Elas permitem que você organize informações de maneira eficiente e resolva problemas com confiança. Dominar esses conceitos é um grande passo em direção ao desenvolvimento profissional.

Em futuros artigos, exploraremos em detalhes estruturas como listas encadeadas, árvores e grafos. Inscreva-se para não perder os próximos conteúdos!

Valeu demais, e até a próxima!

Andrew Cavalcante Pacífico

Bacharel em Ciência da Computação pela Universidade Federal do Amazonas, MBA em Gerenciamento de Projetos pela Fundação Getúlio Vargas.

Atualmente trabalha como Gerente de Engenharia na Meliuz.

Com 20 anos de experiência na área, já trabalhou com um pouco de tudo, C, C++, Java, C#, Delphi, Node.js, AWS, PHP, Python, React, Angular, jQuery, e mais um monte de coisa que nem existe mais 😀

andrewpacifico.com

Artigos relacionados:

Lista Encadeada – Conceito, e implementação em C Quicksort vs Mergesort vs Heapsort: Análise de desempenho Busca Binária e Sequencial: Entenda os principais Algoritmos de busca Como criar um aplicativo para Android Iniciando na Programação Android – Android Studio Tutorial