---

Bem-vindos à disciplina de Estruturas de Dados. Ao longo deste semestre estudaremos como representar informações de forma organizada e eficiente, permitindo que programas manipulem grandes quantidades de dados utilizando algoritmos rápidos e escaláveis.

Ao chegar nesta disciplina, espera-se que vocês já estejam familiarizados com programação em linguagem C, incluindo o uso de variáveis, funções, vetores, matrizes, registros (structs), ponteiros e alocação dinâmica de memória. Esses conceitos constituem a base necessária para estudarmos estruturas de dados, mas, sozinhos, eles não são suficientes para resolver problemas mais complexos.

Nesta primeira aula faremos uma visão geral da disciplina, procurando responder uma pergunta bastante importante:

Se eu já sei programar em C, por que preciso estudar Estruturas de Dados?

---

Programar não é apenas escrever código

Considere alguns sistemas utilizados diariamente:

• um aplicativo de mensagens instantâneas;
• uma rede social;
• um sistema bancário;
• um mecanismo de busca na Internet;
• um sistema de gerenciamento de biblioteca.

Todos esses sistemas possuem algo em comum: eles armazenam e manipulam uma enorme quantidade de informações.

Não basta que os dados estejam armazenados. É necessário responder perguntas rapidamente:

• Como localizar um usuário específico?
• Como encontrar um livro pelo ISBN?
• Como listar todos os alunos matriculados em uma disciplina?
• Como manter milhares de registros organizados?
• Como remover ou inserir novos dados sem comprometer o desempenho?

Esses problemas não são resolvidos apenas utilizando variáveis, vetores ou registros. É necessário organizar os dados de maneira adequada e escolher algoritmos eficientes para manipulá-los. Esse é exatamente o objetivo das Estruturas de Dados.

---

Tipos de dados

Toda linguagem de programação oferece mecanismos para representar informações. Em linguagem C esses mecanismos são chamados de tipos de dados.

Os tipos de dados definem quais valores podem ser armazenados e quais operações podem ser realizadas sobre eles.

Tipos primitivos

Os tipos primitivos representam valores simples e indivisíveis.

int idade = 20;
float nota = 8.5;
char sexo = 'F';
double pi = 3.1415926535;

Cada variável armazena apenas um único valor.

Tipos estruturados

Além dos tipos primitivos, a linguagem C permite construir tipos mais complexos combinando diversos valores em uma única estrutura.

O exemplo mais conhecido é o struct.

typedef struct {
    int matricula;
    char nome[100];
    float media;
} Aluno;

Nesse exemplo foi criado um novo tipo chamado Aluno, composto por três campos diferentes.

Também fazem parte dos tipos estruturados recursos como vetores, matrizes, strings e ponteiros.

Aluno turma[50];
char disciplina[40];
Aluno *p;

Esses recursos serão utilizados durante toda a disciplina.

---

Tipos de dados não são estruturas de dados

É importante não confundir esses dois conceitos.

Os tipos de dados fornecem uma maneira de representar informações na memória. Entretanto, eles não dizem como essas informações devem ser organizadas nem quais operações podem ser realizadas de forma eficiente.

Por exemplo, suponha que desejamos armazenar todos os alunos de um curso.

Aluno alunos[1000];

Esse vetor permite armazenar mil registros, mas ainda permanecem diversas perguntas importantes:

• Como localizar rapidamente um aluno pela matrícula?
• Como inserir um novo aluno mantendo a organização?
• Como remover um aluno?
• Como listar os alunos em ordem alfabética?
• Como lidar com uma quantidade de alunos maior que o tamanho do vetor?

Observe que nenhuma dessas perguntas é respondida pelo tipo de dado utilizado.

O vetor apenas fornece espaço para armazenar os registros. Ainda precisamos decidir como esses registros serão organizados e quais algoritmos utilizar para manipulá-los.

É exatamente nesse ponto que entram as estruturas de dados.

---

O que é uma estrutura de dados?

Uma estrutura de dados é uma forma organizada de representar informações juntamente com mecanismos eficientes para manipulá-las.

Uma estrutura de dados define:

• como os dados serão armazenados;
• como os elementos estarão relacionados;
• quais operações poderão ser realizadas;
• como essas operações serão implementadas.

Diferentes estruturas são adequadas para diferentes problemas. Não existe uma estrutura de dados que seja a melhor em todas as situações.

Durante a disciplina aprenderemos a escolher a estrutura mais adequada para cada contexto.

---

Do mundo real ao computador

Antes de implementar qualquer sistema é necessário compreender o problema que desejamos resolver.

Considere, por exemplo, um sistema para gerenciamento de uma biblioteca.

No mundo real existem livros, autores, usuários, empréstimos, devoluções e diversas relações entre esses elementos.

Nosso primeiro objetivo é compreender essas entidades e como elas se relacionam. Somente depois pensamos em como representá-las no computador.

Mundo Real
↓
Abstração
↓
Modelo Lógico
↓
Modelo Físico
↓
Implementação em C

Essa sequência aparece em praticamente qualquer projeto de software, independentemente da linguagem utilizada.

---

Abstração

Abstração consiste em identificar apenas as características relevantes de um problema, ignorando detalhes que não são importantes naquele momento.

Voltando ao exemplo da biblioteca, não interessa ao sistema saber a cor da capa de um livro ou o tipo de tinta utilizado em sua impressão.

Por outro lado, informações como título, autor, ISBN e disponibilidade para empréstimo são relevantes e precisam ser representadas.

Abstrair significa justamente selecionar quais informações são importantes para resolver o problema.

---

Modelo lógico

Após identificar as entidades do problema, construímos um modelo lógico.

O modelo lógico descreve quais dados existem e como eles se relacionam, sem se preocupar ainda com detalhes de implementação.

No exemplo da biblioteca podemos identificar entidades como:

• Livro;
• Autor;
• Usuário;
• Empréstimo.

Também identificamos os relacionamentos entre elas, por exemplo:

• um livro possui um ou mais autores;
• um usuário pode realizar diversos empréstimos;
• cada empréstimo está associado a um livro e a um usuário.

Nesse momento ainda não discutimos vetores, listas, árvores ou tabelas hash. Estamos apenas modelando o problema.

---

Modelo físico

Depois que o modelo lógico está definido, precisamos decidir como essas informações serão representadas na memória do computador.

Essa etapa é chamada de modelo físico.

Agora surgem perguntas como:

• Devemos utilizar um vetor ou uma lista encadeada?
• Uma árvore permitiria buscas mais rápidas?
• Uma tabela hash seria mais adequada?
• Como implementar inserções e remoções?

Observe que diferentes escolhas produzem diferentes desempenhos. Em muitos casos, dois programas resolvem exatamente o mesmo problema, mas apresentam tempos de execução completamente diferentes apenas porque utilizam estruturas de dados distintas.

Ao longo desta disciplina aprenderemos justamente como realizar essas escolhas de maneira fundamentada.

---

Estruturas de dados existem para suportar operações

Um erro bastante comum é pensar que uma estrutura de dados serve apenas para armazenar informações.

Na realidade, sua principal função é permitir que determinadas operações sejam realizadas de maneira eficiente.

Considere novamente um cadastro de alunos.

Se os registros estiverem armazenados em um vetor, algumas perguntas surgem naturalmente:

• Como inserir um novo aluno?
• Como remover um aluno?
• Como localizar uma matrícula?
• Como manter os registros ordenados?
• Como percorrer todos os alunos?

Essas operações serão utilizadas repetidamente durante toda a disciplina.

Cada estrutura de dados oferece vantagens e limitações diferentes para cada uma delas.

---

Um exemplo em linguagem C

Em C não existe suporte nativo ao conceito de classes, mas é perfeitamente possível implementar um TAD utilizando um struct juntamente com um conjunto de funções.

Considere, por exemplo, uma conta bancária.

typedef struct {
    int numero;
    char titular[100];
    float saldo;
} Conta;

Os dados da conta ficam armazenados na estrutura.

As operações podem ser implementadas através de funções:

void depositar(Conta *c, float valor);
void sacar(Conta *c, float valor);
float consultarSaldo(Conta *c);

Observe que a estrutura representa apenas os dados. As funções representam o comportamento esperado desse tipo abstrato.

Ao longo da disciplina utilizaremos esse mesmo padrão para implementar listas, pilhas, filas, árvores e diversas outras estruturas.

---

Exemplo: quando um vetor deixa de ser suficiente

Imagine um sistema que armazena milhares de músicas.

Inicialmente, um vetor pode parecer suficiente.

Musica playlist[10000];

Agora suponha que desejamos inserir uma nova música exatamente na quinta posição da lista.

Para abrir espaço, será necessário deslocar todos os elementos seguintes uma posição à frente.

Da mesma forma, remover uma música do início do vetor exige deslocar todos os demais elementos.

Embora o vetor seja extremamente eficiente para acessar elementos por posição, ele não é necessariamente a melhor escolha para inserções e remoções frequentes.

Essa observação motiva o estudo das listas encadeadas, que veremos mais adiante na disciplina.

---

Motivação para listas

Diversos problemas envolvem coleções de elementos cujo tamanho varia durante a execução do programa.

Alguns exemplos são:

• lista de reprodução de músicas;
• lista de tarefas;
• histórico de mensagens;
• cadastro de usuários;
• agenda telefônica.

Nesses casos é comum realizar inserções e remoções constantemente.

Durante a disciplina estudaremos listas simplesmente encadeadas, listas duplamente encadeadas e listas circulares, comparando suas vantagens e limitações em relação aos vetores.

---

Motivação para árvores

Nem todo problema pode ser representado por uma sequência linear de elementos.

Em muitas situações os dados possuem uma organização hierárquica.

Alguns exemplos são:

• a estrutura de diretórios de um sistema operacional;
• a árvore genealógica de uma família;
• a organização de departamentos em uma empresa;
• o índice de um livro;
• a estrutura sintática de um programa.

Esses problemas são naturalmente representados utilizando árvores.

Além de modelar relações hierárquicas, árvores permitem realizar buscas muito mais eficientes do que listas em diversas situações.

Mais adiante estudaremos árvores binárias, árvores de busca, árvores balanceadas e estruturas especializadas para processamento de strings.

---

Motivação para algoritmos de ordenação

A ordenação é um dos problemas mais estudados em Ciência da Computação.

Diversas operações tornam-se mais simples quando os dados estão organizados.

Por exemplo, uma lista de alunos ordenada pelo número de matrícula facilita buscas, consultas e geração de relatórios.

Da mesma forma, uma lista de produtos ordenada por código permite localizar informações mais rapidamente do que uma coleção completamente desorganizada.

Ao longo da disciplina estudaremos diferentes algoritmos de ordenação e veremos que, embora todos produzam exatamente o mesmo resultado final, seu desempenho pode variar significativamente dependendo da estratégia utilizada.

---

Memória principal e memória secundária

Grande parte da disciplina será dedicada ao estudo de estruturas de dados armazenadas na memória principal (RAM). Entretanto, muitos sistemas trabalham com volumes de dados muito maiores do que a memória disponível.

Nesses casos torna-se necessário armazenar informações em dispositivos de memória secundária, como discos rígidos e unidades SSD.

Embora o princípio geral seja o mesmo, existem diferenças importantes entre esses dois ambientes.

Memória principal

• Acesso muito rápido.
• Capacidade relativamente limitada.
• Os dados são perdidos quando o computador é desligado.
• Utilizada por vetores, listas, árvores, heaps e tabelas hash.

Memória secundária

• Acesso significativamente mais lento.
• Grande capacidade de armazenamento.
• Os dados permanecem armazenados mesmo após desligar o computador.
• Exige estruturas especialmente projetadas para reduzir acessos ao disco.

Essa diferença explica por que algumas estruturas estudadas no final da disciplina, como Árvores B e Árvores B+, são bastante diferentes das árvores binárias vistas anteriormente.

---

Visão geral da disciplina

Agora que discutimos os conceitos fundamentais, podemos apresentar uma visão geral do que será estudado ao longo do semestre.

Embora as estruturas de dados pareçam assuntos independentes, elas foram desenvolvidas para resolver diferentes classes de problemas. Cada estrutura procura tornar determinadas operações mais eficientes, normalmente sacrificando outras. Por esse motivo, uma das principais habilidades desenvolvidas nesta disciplina será aprender a escolher a estrutura mais adequada para cada situação.

De maneira simplificada, o conteúdo da disciplina pode ser organizado conforme a Figura abaixo.

             Problema
                 ↓
     Como representar os dados?
                 ↓
    ----------------------------
    |            |             |
  Vetores      Listas       Árvores
    |            |             |
    ----------------------------
                 ↓
       Como realizar operações?
                 ↓
 Busca  Inserção  Remoção  Ordenação

Inicialmente estudaremos algoritmos de ordenação, pois eles permitem compreender que diferentes estratégias podem produzir resultados idênticos com desempenhos bastante distintos.

Em seguida estudaremos listas lineares, tanto utilizando memória contígua (vetores) quanto memória dinâmica (listas encadeadas). Esses conteúdos servirão de base para estruturas como pilhas, filas e deques.

Na sequência veremos estruturas hierárquicas, como árvores binárias, árvores de busca e árvores balanceadas, utilizadas quando operações de busca e organização precisam ser realizadas de maneira eficiente.

Posteriormente estudaremos estruturas especializadas, como árvores Trie para processamento de strings, tabelas hash para buscas rápidas e Árvores B/B+, amplamente utilizadas em bancos de dados e sistemas de arquivos.

Por fim, veremos técnicas clássicas de compressão de dados, mostrando como estruturas de dados também podem ser utilizadas para reduzir o espaço necessário para armazenamento de informações.

---

Conteúdo programático

Conteúdo	Objetivo
Algoritmos de Ordenação	Comparar diferentes estratégias para organizar dados.
Tipos Abstratos de Dados	Separar interface e implementação.
Vetores	Representação utilizando memória contígua.
Listas Encadeadas	Inserções e remoções eficientes utilizando memória dinâmica.
Pilhas, Filas e Deques	Resolução de problemas baseados em restrições de acesso.
Heaps	Implementação de filas de prioridade.
Árvores Binárias	Representação hierárquica e buscas eficientes.
Árvores Balanceadas	Garantir desempenho consistente para operações de busca.
Estruturas para Strings	Busca eficiente utilizando Tries, Patricia e TST.
Tabelas Hash	Busca rápida baseada em funções de espalhamento.
Árvores B e B+	Indexação de dados armazenados em disco.
Compressão de Dados	Representação eficiente da informação.

---

Como estudar esta disciplina

Estruturas de Dados é uma disciplina essencialmente prática. Apenas ler os algoritmos normalmente não é suficiente para compreender seu funcionamento.

Para obter um bom aproveitamento recomenda-se:

• implementar todas as estruturas estudadas utilizando linguagem C;
• executar os algoritmos com diferentes conjuntos de dados;
• testar casos extremos, como estruturas vazias ou contendo apenas um elemento;
• desenhar as estruturas no papel antes de implementá-las;
• comparar diferentes soluções para um mesmo problema.

Ao longo do semestre será dada grande ênfase não apenas à implementação correta, mas também à capacidade de analisar vantagens, limitações e aplicações de cada estrutura.

---

Resumo da aula

Nesta primeira aula apresentamos os conceitos fundamentais que servirão de base para todo o restante da disciplina.

Em particular, vimos que:

• tipos de dados e estruturas de dados são conceitos diferentes;
• estruturas de dados organizam informações e oferecem suporte eficiente para operações sobre esses dados;
• todo problema deve ser abstraído antes de ser implementado;
• o desenvolvimento de software passa por um modelo lógico e posteriormente por um modelo físico;
• Tipos Abstratos de Dados permitem separar interface e implementação;
• existem estruturas específicas para memória principal e para armazenamento em disco;
• cada estrutura possui aplicações, vantagens e limitações próprias.

Durante o restante da disciplina aprofundaremos cada um desses tópicos, estudando suas implementações em linguagem C e analisando seu desempenho em diferentes situações.

---

Exercícios

1. Explique, com suas próprias palavras, a diferença entre um tipo de dado e uma estrutura de dados.
2. Considere um sistema para gerenciamento de uma biblioteca. Quais entidades fazem parte do modelo lógico? Como elas se relacionam?
3. Dê três exemplos de aplicações que poderiam utilizar listas encadeadas.
4. Dê três exemplos de aplicações que naturalmente utilizam árvores.
5. Por que um vetor nem sempre é a melhor solução para armazenar grandes conjuntos de dados?
6. Pesquise o conceito de Tipo Abstrato de Dados e explique por que a separação entre interface e implementação é importante.
7. Qual é a diferença entre memória principal e memória secundária? Por que algumas estruturas são projetadas especificamente para acesso em disco?
8. Escolha um software utilizado no seu dia a dia (por exemplo, um navegador, um editor de texto ou um aplicativo de mensagens) e identifique quais estruturas de dados você acredita que sejam utilizadas internamente. Justifique suas respostas.

---

Sugestões de Respostas dos Exercícios

Exercício 1

Um tipo de dado define como um valor é representado na memória e quais operações básicas podem ser realizadas sobre ele. Exemplos incluem int, float, char e também tipos criados pelo programador, como struct.

Uma estrutura de dados, por outro lado, organiza diversos dados de maneira a permitir operações eficientes como busca, inserção, remoção e percurso. Enquanto um vetor ou uma estrutura (struct) apenas armazenam informações, estruturas como listas, árvores e tabelas hash também definem como esses dados serão organizados e manipulados.

Exercício 2

No sistema de biblioteca podemos identificar entidades como:

• Livro;
• Autor;
• Usuário;
• Empréstimo.

Alguns relacionamentos possíveis são:

• Um livro pode possuir um ou mais autores.
• Um usuário pode realizar diversos empréstimos.
• Cada empréstimo relaciona exatamente um usuário a um livro.

Esse conjunto de entidades e relacionamentos constitui um modelo lógico do problema, independentemente da linguagem de programação utilizada.

Exercício 3

Exemplos de aplicações que podem utilizar listas encadeadas incluem:

• Histórico de navegação de um navegador.
• Lista de reprodução de músicas.
• Lista de tarefas de um aplicativo.
• Escalonamento de processos.
• Implementação de pilhas e filas.

Esses problemas realizam inserções e remoções frequentes, situação em que listas costumam ser mais adequadas que vetores.

Exercício 4

Estruturas em árvore aparecem naturalmente em diversos problemas, por exemplo:

• Estrutura de diretórios de um sistema operacional.
• Árvore genealógica.
• Organização de departamentos em uma empresa.
• DOM de uma página HTML.
• Índices de bancos de dados.

Todos esses exemplos possuem uma organização hierárquica, característica típica das árvores.

Exercício 5

Vetores possuem tamanho fixo e armazenam elementos em posições contíguas da memória. Embora permitam acesso muito rápido por índice, inserções e remoções em posições intermediárias normalmente exigem deslocar diversos elementos.

Quando essas operações são frequentes, outras estruturas, como listas encadeadas, podem ser mais adequadas.

Exercício 6

Um Tipo Abstrato de Dados descreve o comportamento esperado de uma estrutura, definindo apenas as operações disponíveis e sua semântica, sem especificar como elas serão implementadas.

Separar interface e implementação torna o software mais modular, facilita manutenção e permite substituir uma implementação por outra sem alterar o código que utiliza aquela estrutura.

Exercício 7

A memória principal (RAM) é rápida, porém limitada e volátil. Os dados armazenados nela são perdidos quando o computador é desligado.

A memória secundária (HD ou SSD) possui capacidade muito maior e mantém os dados permanentemente, porém apresenta tempos de acesso significativamente maiores.

Por essa razão, estruturas como Árvores B e B+ foram desenvolvidas especificamente para minimizar acessos ao disco.

Exercício 8

A resposta depende do software escolhido. Um possível exemplo é um aplicativo de mensagens:

• Lista para armazenar conversas.
• Fila para envio de mensagens.
• Tabela hash para localizar usuários rapidamente.
• Árvores para indexação e pesquisa.
• Heap para gerenciamento de prioridades.

Existem diversas respostas corretas, desde que sejam devidamente justificadas.