Texto Complementar 09 ESTRUTURA DE DADOS DINÂMICAS EM C

Prévia do material em texto

Disciplina: 
Estruturas de Dados 
Texto Complementar 
ESTRUTURA DE DADOS DINÂMICAS EM C - LISTAS, FILAS, 
PILHAS E ÁRVORES 
 
 
- Objetivo desta leitura 
Proporcionar ao aluno uma visão mais abrangente sobre a importância das Estruturas de Dados. 
 
- Com isso você será capaz de (habilidades desenvolvidas): 
Através da presente leitura complementar, o aluno irá aprofundar seus conhecimentos em relação as Estruturas 
de Dados por meio da interpretação das informações e analise dos conteúdos e refletir sobre os resultados obtidos com 
a leitura. 
 
ESTRUTURA DE DADOS DINÂMICAS EM C - LISTAS, FILAS, PILHAS E 
ÁRVORES 
 
 
 
São elementos das estruturas dinâmicas de dados e são essenciais na linguagem C e no estudo 
da computação, de um modo geral. 
Aprendendo estrutura de dados dinâmica, iremos nos aproximar do conhecimento que é 
realmente empregado nos mais diversos aplicativos e sistemas existentes. 
 
 
O que é Estrutura Dinâmica de Dados em Linguagem C 
 
 
Aqui em nossa apostila de C, já estudamos estrutura de dados quando aprendemos sobre 
vetores, que foi uma maneira de manipular várias informações (variáveis ou estruturas) de uma 
vez só, pois poderíamos declarar vários desses elementos. 
Quando isso era feito, esses dados estavam em uma sequência rigidamente definida na 
memória, bem como o número de elementos eram constantes. Esses dois detalhes, na verdade, 
possuem algumas limitações. 
 
Ou seja, estamos um trecho do título deste tutorial, a parte de "Estrutura de Dados". 
Também estudamos a outra parte, que se refere ao dinamismo. Vimos isso em nossa seção de 
Alocação dinâmica de memória, onde deixamos de estar presos ao conceito de "número de 
elementos fixos", pois lá alocávamos e realocávamos o tanto de espaços de memória que 
queríamos, da maneira que queríamos. 
 
Pois bem, agora é hora de 'unir forças' e usar esses poderosos conceitos para criar outro 
importante conceito, o de estrutura de dados dinâmicas, ou seja, as estrutura de dados que são 
alocadas, realocadas e movidas o quanto e do jeito que quisermos. 
 
Ou seja, ao contrário de vetores de tamanhos fixos, iremos basicamente colocar 
estruturas(structs) em uma sequência que será criada dinamicamente, da maneira que 
quisermos. Ou seja, podemos colocar elementos nessa sequência, tirar, mudar de lugar, 
percorrer e fazer coisas incríveis. 
 
Mas só falando dessa maneira, a coisa fica um pouco confusa e abstrata. 
Vamos entrar em detalhes nos tipos de estrutura de dados que iremos estudar: Listas, Filas, 
Pilhas e Árvores. 
 
 
O que é uma Lista em C (Lists) 
 
 
squeça a programação. Use seu bom senso e responda: o que é uma lista? 
Vamos supor que você fez uma lista de compras. 
Ou seja, tem um pedaço de papel com diversos elementos, em uma dada ordem. 
Provavelmente essa ordem é a que você vai comprar, do primeiro para o último. Geralmente elas 
tem uma sequência lógica, como elementos do mesmo setores estarem adjacentes. 
Depois você vai trabalhar com essa lista, seguir a ordem dela, marcar se comprou ou não, anotar 
o preço etc. 
 
A analogia é parecida para uma lista em C. 
Em programação, lista é uma série de elementos ligados. O primeiro é ligado no segundo, que é 
ligado no terceiro etc. 
Iremos aprender como colocar elementos, tirar, mudar de posição. Como elas estão ligadas, 
basta que tenhamos o endereço (ponteiro) para o primeiro elemento da lista. 
 
Ou seja, iremos estudar as chamadas listas encadeadas, que são itens 'alinhados' numa fila. 
 
 
 
 
 
Filas em C (Queue) 
 
Outro importante conceito de estrutura de dados dinâmica são as filas, que são exatamente 
iguais as do mundo real. 
Como funciona a fila de um caixa eletrônico? 
 
Chega a primeira pessoa, é atendida. Já a segunda, fica na fila, e será atendida depois da 
primeira. 
A terceira a chegar só vai ser atendida depois da segunda, e assim sucessivamente. 
 
Ou seja, os primeiros elementos a chegar serão os primeiros a serem atendidos. 
Um termo muito conhecido para designar tal tipo de ideia é FIFO - First In, First Out (Primeiro que 
entra, primeiro que sai). 
 
Em termos de programação, dizemos que os elementos que chegam vão para a cauda da fila, ou 
seja, para o final, serão atendidos por último. Os elementos que serão primeiro atendidos são os 
que estão na cabeça da fila (na frente). 
Também chamamos o ato de colocar algo na fila de ENQUEUE, e de tirar de DEQUEUE. 
 
 
 
 
 
Pilhas em C (Stack) 
 
 
Outra importante estrutura dinâmica de dados são as pilhas (stacks, em inglês), que tem um 
funcionamento contrário ao das filas. São ditas do tipo LIFO - Last In, First Out (Ultimo a entrar, 
primeiro a sair). 
 
 
 
 
Para entender esse tipo de estrutura, podemos imaginar uma pilha de pratos. 
Você come uma coisa, e guarda o prato. 
Come a segunda coisa, e põe o segundo prato em cima do primeiro. 
Come a terceira e põe este prato em cima do segundo, e assim sucessivamente. 
 
Quando você for lavar, que prato vai retirar primeiro? O de cima. 
E qual o último prato a ser retirado? O primeiro. 
Ou seja, você vai tirando os pratos de cima, que são os pratos que chegaram por último na pilha. 
Já os pratos que chegaram primeiro na fila serão os últimos a saírem dela. 
 
Dois termos comum nesse tipo de ordenação de estruturas são PUSH e POP. 
PUSH é colocar um elemento na pilha, e POP é tirar. 
 
 
Árvores em C (Tree) 
 
Os elementos anteriores geralmente apontam para um elemento (o próximo). 
Existem listas duplamente encadeadas, que cada elemento está ligado com o anterior e o 
próximo, mas todas elas são lineares, formam uma sequência única. 
 
Já as árvores não, pois cada elemento pode estar ligado em um ou mais elemento, formando 
assim uma sub-árvore, e cada uma destas pode formar outras. Ou seja, há uma infinidade de 
caminhos e possibilidades para estruturas desse tipo. 
 
Daremos atenção especial para as árvores binárias, que possuem no máximo duas ramificações. 
 
 
 
 
Conceitos básicos de uma estrutura dinâmica de dados 
 
 
Antes de começarmos a estudar separadamente cada estrutura que foi introduzida neste tutorial, 
vamos ver um esqueleto, uma estrutura básica que iremos usar em todos os itens aqui abordados. 
 
Primeiro de tudo, iremos realmente usar estruturas, ou seja, structs. 
Isso porque são elementos bem gerais, que nos permitem criar qualquer tipo de dado, da maneira 
que quisermos. 
 
A segunda ideia essencial para esse estudo, é a chamada auto-referência. 
Ou seja, vamos criar uma struct de um determinado tipo, e dentro dela iremos declarar um membro 
que é um ponteiro. 
Como sabemos, os ponteiros apontam para tipos diferentes de dados, e nesse caso, o ponteiro que 
fica dentro de uma struct irá apontar para um tipo dessa mesma struct. 
 
Isso se chama auto-referência. Pode ser um pouco estranho, mas é perfeitamente possível e uma 
ideia bastante usada. 
Lembre-se: quando criamos uma struct, ela terá um tamanho (sizeof()) definido. Portanto, ela será 
um tipo de dado. 
Então, é possível existir um ponteiro para este tipo de dado. 
Em suma: é uma estrutura que possui um ponteiro. 
 
Geralmente chamamos de nó (ou node, do inglês) os elementos de uma estrutura de dados 
dinâmica. 
Veja como seria nossa struct: 
 
 
struct node 
{ 
 //dados e variáveis de sua struct aqui 
 struct node *nextNode; 
} 
 
Esse ponteiro será de uso essencial, como veremos em breve em nossa apostila, pois eles irão 
apontar para o próximo elemento (próximo nó) ou para NULL, caso seja o último elemento da 
estrutura de dados. 
É importante não se esquecer isso, é a terceira característica básica de todos esses tipos de 
estrutura de dados, pois é um erro bem comum entre iniciantes: o ponteiro sempre aponta para 
uma região de memória, aqui iremos fazer ele apontar para o próximo elemento da lista, pilha, fila 
ou árvore.Quando criamos uma struct, seu ponteiro automaticamente vai apontar para o lixo, que é um 
endereço de memória como é endereço de memória caso apontemos esse ponteiro para outra 
struct, não há diferença. 
Por isso é importante apontarmos o último elemento para NULL, pois diferente dos outros, só ele 
aponta para esse local, daí podemos usar essa informação para saber quando nossa estrutura de 
dados termina :) 
 
Por hora, não se assuste. Iremos explicar, em detalhes, com muitos exemplos, cada um destes 
tipos, bem como faremos diversos algoritmos. Lembrando que é um assunto de suma 
importância, pois são ideias largamente usadas em programação. 
Seu sistema operacional, por exemplo, usa e abusa de filas e pilhas para organizar os processos, 
o que deve ser executado primeiro, depois etc. 
 
 
 
 
 
 
 
 
Link: < http://www.cprogressivo.net/2013/10/Estrutura-de-dados-dinamica-em-C-Listas-Filas-Pilhas-
Arvores.html > Acesso em: 01 jan. 2016.