Especialista

12
Estruturas de Dados
Objetivos
• Ser capaz de alocar e liberar memória dinamicamente para objetos de dados.
• Ser capaz de formar estruturas encadeadas de dados usando ponteiros, estruturas referenciadas e recursão.
• Ser capaz de criar e manipular listas encadeadas, filas, pilhas e árvores binárias. • Entender várias aplicações importantes de estruturas encadeadas de dados.

Muito do que eu tinha, não consegui libertar;
Muito do que eu libertei voltou para mim.
Lee Wilson Dodd
" Você poderia andar mais depressa? " disse um peixe para um caracol. "
" Há um golfinho atrás de nós e ele está muito perto. "
Lewis Carroll
Há sempre um lugar no topo.
Daniel Webster
Vá em frente — continue andando.
Thomas Morton
Acho que nunca verei
Um poema tão encantador quanto uma árvore.
Joyce Kilmer

Sumário
12.1
12.2
12.3
12.4
12.5
12.6
12.7

Introdução
Estruturas Auto-referenciadas
Alocação Dinâmica da Memória
Listas Encadeadas
Pilhas (Stacks)
Filas (Queues)
Árvores

Resumo — Terminologia — Erros Comuns de Programação — Práticas
Recomendáveis de Programação — Dicas de Performance — Dica de Portabilidade —
Exercícios de Revisão — Respostas dos Exercícios de Revisão — Exercícios

12.1 Introdução
Estudamos estruturas de dados de tamanho fixo como arrays unidimensionais, arrays bidimensionais e structs. Este capítulo apresenta as estruturas dinâmicas de dados com tamanhos que aumentam e diminuem durante a execução de um programa.
As listas encadeadas são grupos de itens de dados "colocados em linha" — as inserções e exclusões são feitas em qualquer lugar de uma lista encadeada. As pilhas (stacks) são importantes em compiladores e sistemas operacionais — as inserções e exclusões são feitas apenas em uma extremidade de uma pilha — seu topo. As filas (queues) representam filas de espera; as inserções são feitas na extremidade posterior (também chamada fim ou cauda) de uma fila e as exclusões são feitas na extremidade anterior