O objetivo desse artigo é apresentar as ideias fundamentais a respeito das estruturas de dados e sanar algumas dúvidas comuns entre aqueles que estão começando a estudar o assunto:
- O que são estruturas de dados?
- Qual a relação entre estruturas de dados e algoritmos?
- Por que eu preciso estudar esse negócio?
- Por que em C!?
- Qual a diferença entre tipos abstratos de dados e estruturas de dados?
Esse texto serve de base pra os posts do blog sobre estruturas de dados em C (links no final do artigo). Bons estudos!
O que são estruturas de dados?
Resumidamente, uma estrutura de dados é uma coleção de dados organizada de um jeito que facilite sua manipulação. Geralmente, quando falamos em estruturas de dados, nos referimos a um objeto capaz de reunir nosso conjunto de dados de uma forma que facilite as tarefas que precisamos realizar com esses dados. Pra dar conta de cada tipo de tarefa, vão existir estruturas mais ou menos adequadas.
Qual a relação entre estruturas de dados e algoritmos?
Algoritmos são procedimentos. Ou seja, sequências de instruções que devem ser executadas pra produzir algum resultado. Geralmente, nosso algoritmo recebe uma entrada, que pode ser um valor qualquer, e produz uma saída depois de realizar uma série de operações sobre essa entrada.
Estruturas de dados e algoritmos caminham juntos, porque as estruturas de dados, pra serem úteis, precisam ser manipuladas de alguma forma. Ou seja, cada estrutura de dados necessita de certos algoritmos para que suas funcionalidades sejam implementadas. Por outro lado, cada algoritmo espera receber como entrada um certo tipo de dados pra realizar sua função.
Por exemplo, podemos desenvolver um algoritmo de ordenamento por ordem alfabética pra nossa estrutura de lista encadeada, ou podemos desenvolver uma estrutura de lista encadeada para representar polinômios e possibilitar que eles sejam manipulados por um algoritmo de cálculo.
Por que estudar estrutura de dados?
Hoje em dia existem centenas de linguagens de programação, que já vêm equipadas com vários tipos de dados complexos adequados pra a maioria das tarefas de desenvolvimento. E além disso, você pode usar várias bibliotecas de terceiros que oferecem recursos e funções pra o desenvolvimento de trabalhos mais específicos. Então por que aprender estruturas de dados se você já tem tudo pronto?
A resposta rápida pra as duas perguntas é: porque isso faz de você um programador melhor. Agora vamos pra a resposta longa.
Em primeiro lugar, é justamente por conta da quantidade de opções que você tem pra resolver algum problema no seu projeto, que é importante entender o que cada uma dessas opções traz de vantagens e de desvantagens.
Como essas diversas linguagens e bibliotecas querem facilitar sua vida (exceto o C. C não quer facilitar nada), elas tendem a esconder a complexidade das estruturas de dados que elas oferecem, e fazem parecer que não importa muito qual delas você escolhe, pela falsa impressão de que são todas iguais.
Mas isso está longe de ser verdade. Escolher uma estrutura de dados pouco adequada pra a tarefa que você tem em mãos pode comprometer o desempenho do seu programa. Se o seu código é desenvolvido pra rodar poucas vezes, com poucos dados, isso pode até não fazer muita diferença.
Mas se ele deve ser executado com certa frequência, sobre um volume grande de dados, a escolha de trabalhar com vetores ou listas encadeadas ao invés de trabalhar com tabelas de dispersão ou árvores, por exemplo, pode ocasionar uma perda visível de desempenho. E se você resolver trabalhar com sistemas embarcados ou big data, então a performance se torna um fator chave!
Por que aprender estruturas de dados em C?
E por que C, que ninguém usa? Por que não, por exemplo, Python, que é bem mais fácil?
Primeiro, porque num curso de Estruturas de Dados, normalmente a gente começa aprendendo algumas estruturas fundamentais, como listas encadeadas, que são usadas pra implementar listas lineares e pilhas, e algumas estruturas um pouco mais complexas, como tabelas de dispersão, que são utilizadas pra implementar dicionários. Então parece meio fora de propósito implementar essas estruturas de dados básicas em Python, já que o Python já vem “de fábrica” com listas e dicionários, não é mesmo?
Em segundo lugar, linguagens como Python e Java tendem a esconder do desenvolvedor os detalhes de acesso e gerenciamento de memória, enquanto que em C você precisa alocar memória, armazenar o endereço da memória, e liberar a memória manualmente.
Além disso, nessas linguagens, você também não enxerga os algoritmos usados por operações aparentemente simples, como .pop() ou .remove() pra remover um elemento de uma lista ou .put() pra inserir. E tudo isso é muito importante pra que você entenda a complexidade envolvida no uso das várias estruturas de dados existentes.
Em relação a “ninguém usar C”, isso também não é verdade. Afinal, o próprio interpretador “oficial” de Python é desenvolvido em C. E se você usa Linux então, a maioria do kernel do seu sistema também é escrito em C! Mas mesmo que fosse verdade, entender o funcionamento das estruturas de dados em C é um aprendizado que se estende para qualquer linguagem que você venha a utilizar depois.
Por exemplo, se você quiser implementar um programa gerenciador de filas de atendimento online em Python, é possível que você opte por utilizar uma lista, que é a solução mais simples. Então você decide que para inserir pessoas na fila, você vai dar um append para inserir no final da lista, e pra tirar pessoas da fila, você vai dar um pop(0) pra tirar a pessoa do início da fila (se você não programa em Python, basta saber que objetos do tipo lista contam com algumas operações específicas, dentre elas, temos o append, que insere um elemento no fim da lista, e o outro é o pop(X), que remove e retorna o objeto posicionado no índice X da lista. Acontece que as listas em Python, pelo menos na implementação de referência da linguagem, são implementadas como vetores dinâmicos.
Como você vai descobrir lendo os artigos de estruturas de dados do blog, quando implementamos listas com vetores, podemos acessar qualquer índice dela em tempo constante, independente do índice ser o primeiro ou o último da lista, o que é excelente. Por outro lado, quando removemos o primeiro item de uma lista implementada com vetores dinâmicos, todos os elementos que vem depois precisam ser remanejados “pra trás”. Ou seja, o segundo elemento vira o primeiro, o terceiro vira o segundo, e por aí vai. E isso é uma operação muito custosa, principalmente pra listas com muitos elementos.
Além disso, conforme a lista cresce, seu espaço de memória precisa ser redimensionado pra dar conta das novas inserções. Ou seja, uma das maiores vantagens da lista implementada no Python, que é o acesso em tempo constante de qualquer elemento é completamente inútil pra o nosso caso, já que vamos querer acessar sempre o primeiro elemento da fila. E o maior ponto fraco do vetor dinâmico, que é a remoção do primeiro elemento, vai acontecer toda vez que alguém da fila for chamado!
Uma solução muito melhor é utilizar uma estrutura chamada justamente de fila, em que a inserção em uma das pontas e a remoção na outra ponta são implementadas de forma a tomar um tempo constante, e o número de elementos pode aumentar ou diminuir sem que seja necessário redimensionar o objeto inteiro.
Essa estrutura, que você pode aprender a implementar em C, já vem disponível na biblioteca padrão do Python e também no Java. Então, a princípio, a gente nem precisaria saber implementar uma fila do zero. Mas meter a mão na massa e ganhar uma compreensão mais profunda sobre o funcionamento dela é justamente o que ajuda a gente a fazer a melhor escolha de estrutura ou tipo de dados!
Qual a diferença entre estrutura de dados e tipo abstrato de dados?
Por falar nisso, uma outra pergunta muito comum quando começamos a estudar estruturas de dados é: qual a diferença entre estrutura de dados e tipo abstrato de dados? Bom… essa diferença é um pouco sutil. E muitas pessoas se sentiriam tentadas a responder que os dois termos significam a mesma coisa. Mas não é bem assim.
Qualquer linguagem vai oferecer a você alguns tipos de dados prontos pra usar. Esses tipos costumam ser chamados de tipos “primitivos”. Tipos de dados podem ser definidos a partir do conjunto de valores que ele pode ter e as operações que podemos fazer sobre elas.
Por exemplo, um unsigned char em C pode armazenar qualquer valor de 0 a 255. Uma string em Java pode armazenar uma sequência de caracteres de tamanho arbitrário. Listas em Python armazenam sequências mutáveis de objetos. Todos esses são tipos primitivos de dados em suas respectivas linguagens. Diferente do Java, do Python ou do C++, o C não conta com o tipo string. Strings em C são implementadas a partir de cadeias de caracteres. Então podemos dizer que em C a string não é um tipo primitivo.
Quando precisamos fazer operações mais complexas nos nossos dados, ou mais específicas que operações proporcionadas pela linguagem que estamos usando, precisamos construir uma estrutura a partir desses tipos de dados mais simples pra comportar os nossos dados. É essa composição de tipos mais simples, reunidos para criar uma estrutura mais complexa, que chamamos de estrutura de dados.
Muitas vezes, não criamos uma estrutura de dados do nada. Geralmente a gente parte de uma ideia mais ou menos estabelecida de que tipo de valores essa estrutura deve ser capaz de armazenar, e que tipo de operações a gente pode fazer com essas estruturas, independente de como isso seja feito na prática.
Por exemplo, sabemos que uma fila deve ser capaz de armazenar algum tipo de objeto, como registros de clientes, e que deve ser possível realizar operações de “inserir no fim da fila” e “remover da frente da fila”. Essa ideia abstrata do que é uma fila é o que chamamos de tipo abstrato de dados.
Um tipo abstrato de dados pode ser visto, então, como um modelo que descreve as características de determinado objeto e que tipo de operações podem ser feitas sobre ele. Enquanto que a estrutura de dados é a implementação real desse tipo abstrato numa linguagem de programação.
Também falamos em tipo abstrato de dados pra nos referir àinterface que oferecemos ao usuário do nosso código para que ele acesse a estrutura de dados que a gente criou. Por exemplo, podemos criar uma biblioteca em C com todas as funções necessárias pra a manipulação de filas, chamada de “libfila”, por exemplo, e expor para quem estiver interessado em usar nossa biblioteca um objeto do tipo fila e funções como “cria_fila”, “insere_na_fila”, “remove_da_fila”, “destroi_fila”, etc.
Então esse usuário do código pode incluir nossa biblioteca no código dele e usar esses objetos e funções sem se preocupar com as especificidades da implementação. Esse conjunto de objetos e funções que a gente expõe pra o usuário do código é chamado de interface.
E na perspectiva desse usuário, ele está lidando com um tipo abstrato de dados. É abstrato porque ele abstrai os detalhes técnicos da implementação, e é um tipo de dados porque o usuário manipula um objeto, que pode ter determinados valores, através de determinadas operações.
Então, fila é uma estrutura de dados ou um tipo abstrato de dados? Isso depende da perspectiva. Se você está se referindo a uma implementação específica de fila, é uma estrutura de dados. Se você está se referindo à ideia abstrata de fila, com suas operações específicas, é um tipo abstrato de dados. Se você está se referindo a um objeto do tipo fila que você importou de uma biblioteca em Java, então podemos falar que nesse caso, a fila é um tipo abstrato de dados, com uma estrutura de dados subjacente que faz ela funcionar!
Abaixo, segue uma lista com os tipos de dados abstratos mais comuns, junto com as estruturas de dados mais comumente utilizadas pra implementá-las:
| Tipo abstrado de dados | Costuma ser implementado com |
| Lista linear | Lista encadeada ou vetor |
| Pilha | Lista encadeada ou vetor |
| Fila | Estrutura baseada em listas encadeadas ou vetores |
| Dicionário / vetor associativo | Tabela de dispersão ou Árvore |
| Conjunto | Tabela de dispersão ou Árvore |
Aqui no blog, já preparei diversos posts ensinando a implementar estruturas de dados em C. Dá uma olhada!
