Linguagem C
86 pág.

Linguagem C


DisciplinaAlgoritmos e Estrutura de Dados I682 materiais7.925 seguidores
Pré-visualização18 páginas
é inicializado com um valor em particular; 
c) Percorre a lista comparando o campo info do novo nó com cada nó da lista. 
d) Ao determinar a posição de inserção, o elo proximo do anterior do nó corrente aponta para o 
novo nó e, o elo proximo do novo nó aponta para o elo proximo do nó corrente. 
A operação de remoção consiste em remover um nó do início ou ao longo da lista e 
retornar o valor armazenado nela. Deve-se observar que: 
a) Não se pode remover um nó de uma lista vazia; 
b) A remoção de um único nó de uma lista ligada de apenas um nó, o ponteiro Primeiro deve ser 
atualizado; 
c) A remoção do primeiro nó da lista com pelo menos dois nós exige a atualização do ponteiro 
Primeiro; 
d) A remoção de um nó no meio de uma lista deve ser realizada somente após efetuar as ligações 
necessárias afim de manter a consistência da lista. 
 
 
 
 
 
 
Figura 14.5 Ilustração de uma lista singularmente ligada. 
 
 
 
 
 
 
 
 
 
2 5 8 41 
Primeiro 
A 
 
Primeiro 
 
Tmp 
A 
 
Primeiro 
 
Tmp 
A 
 
Primeiro 
(1) (2) (3) 
 76
Figura 14.6 Ilustração de inserção em uma lista singularmente ligada. 
 
 
 
 
 
 
 
 
 
Figura 14.7 Ilustração de inserção em uma lista singularmente ligada. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Primeiro 
A 
 
Tmp 
C 
(1) 
 
Primeiro
A 
 
Tmp
C 
(2) 
 
Primeiro 
A C 
(3) 
 
Primeiro 
A C S R 
A 
(3) 
 
Primeiro 
A C S R 
A 
 
Tmp 
(2) 
A 
 
Tmp 
 
Primeiro 
A C S R 
(1) 
 77
 
Figura 14.8 Ilustração de inserção em uma lista singularmente ligada. 
 
14.3.2 Listas Duplamente Ligadas 
Uma lista duplamente ligada (ou lista linear duplamente ligada) consiste em dados e 
elos para o próximo item e para o item precedente. A vantagem de possuir dois elos são: 
\u2022 A lista pode ser lida em ambas as direções; 
\u2022 Se um dos elos tornar-se inválido, a lista pode ser reconstruída utilizando-se o outro elo. 
A inserção de um nó de forma ordenada em uma lista duplamente ligada pode ser 
realizada basicamente de três formas: 
\u2022 no início da lista; 
\u2022 no meio da lista; 
\u2022 no fim da lista. 
O processo para a inserção no início da lista é realizado em quatro etapas: 
a) Um novo nó é criado inicializando-se os dados (inclusive os ponteiro como nulo); 
b) O elo proximo do novo nó recebe Primeiro; 
c) O elo anterior apontado por Primeiro recebe novo nó; 
d) O ponteiro Primeiro recebe novo nó. 
O processo para a inserção no fim da lista é realizado em quatro etapas: 
a) Um novo nó é criado inicializando-se os dados (inclusive os ponteiro como nulo); 
b) O elo anterior do novo nó recebe Ultimo; 
c) O elo proximo apontado por Ultimo recebe novo nó; 
d) ponteiro Ultimo recebe novo nó. 
 
 
 
 
 
 
 
Figura 14.8 Ilustração de uma lista linear duplamente ligada. 
 
O processo de adicionar um novo nó ao longo da lista duplamente ligada de forma 
ordenada é realizada em quatro etapas: 
a) Um novo nó é criado inicializando-se os dados (inclusive os ponteiro como nulo); 
Primeiro 
1 9 3 5 
Último 
 78
b) O campo info do nó é inicializado com um valor em particular; 
c) Percorre a lista comparando o campo info do novo nó com cada nó da lista. 
d) Ao determinar a posição de inserção, o elo proximo do anterior do nó corrente aponta 
para o novo nó. O elo anterior do novo nó aponta para o anterior do nó corrente. O elo 
proximo do novo nó aponta para o nó corrente e, o elo anterior do nó corrente aponta 
para o novo nó. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 14.9 Ilustração de inserção em uma lista duplamente ligada. 
 
A operação de remoção consiste em remover um nó do início, do fim ou ao longo da 
lista e retornar o valor armazenado nela. Deve-se observar que: 
a) Não se pode remover um nó de uma lista vazia; 
 
Primeiro Ultimo 
S 
(1) 
 
Primeiro Ultimo 
S 
(2) 
 
Primeiro Ultimo tmp 
S 
(3) 
E 
 
Primeiro Ultimo 
S 
(4) 
S 
 
tmp Primeiro Ultimo 
S 
(5) 
S 
 
 79
b) A remoção de um único nó de uma lista ligada de apenas um nó, o ponteiro Primeiro e Ultimo 
deve ser atualizado; 
c) A remoção do primeiro nó da lista com pelo menos dois nós exige a atualização do ponteiro 
Primeiro; 
d) A remoção do ultimo nó da lista com pelo menos dois nós exige a atualização do ponteiro 
Ultimo; 
e) A remoção de um nó no meio de uma lista deve ser realizada somente após efetuar as ligações 
necessárias afim de manter a consistência da lista. 
Uma outra construção possível é a lista circular ligada que pode conter ou não a 
indicação para o início da lista 
 
 
 
 
 
 
 
 
Figura 14.9 Ilustração de uma lista circular duplamente ligada com cabeçalho. 
 
14.4 Árvores Binárias 
Árvore binária é um conjunto finito de elementos que está vazio ou é particionado 
basicamente em três subconjuntos disjuntos: raiz, subárvore esquerda e subárvore direita. Cada 
elemento de uma árvore binária é chamado nó da árvore. Em cada nó contém um registro, e, para 
cada nó, a seguinte propriedade é verdadeira: 
\u2022 Todos os registros com chaves menores estão na subárvore esquerda e todos os registros 
com chaves maiores estão na subárvore direita; 
\u2022 O número de subárvores de um nó é chamado grau daquele nó; 
\u2022 Um nó de grau zero é chamado de nó externo ou folha. Os outros nós são chamados de nó 
interno; 
\u2022 Grau de uma árvore é o mais alto dentre os graus de seus nós; 
\u2022 Árvore binária são árvores de grau 2; 
\u2022 O nível do nó raiz é 0. Se um nó está no nível i então a raiz de suas subárvores estão no 
nível i+1; 
Início 
1 9 3 5 
 80
\u2022 A altura de um nó é o comprimento do caminho mais longo deste nó até um nó folha; 
\u2022 A altura de uma árvore é a altura do nó raiz; 
\u2022 A profundidade é o número de arestas da raiz até um determinado nó. A raiz possui 
profundidade 0. As subárvores (sucessores diretos) da raiz possuem profundidade 1. Um nó 
no nível n possui a profundidade n. 
As árvores podem ser utilizadas para administrar grandes quantidades de dados em uma 
ordem qualquer, permitem o uso de listas ligadas e a divisão de um conjunto de dados em 
subconjuntos, administrando-as de forma hierárquica. Além disso, podem representar processos 
decisórios. 
 
 
 
 
 
 
 
 
 
Figura 14.10 Ilustração de uma árvore binária. 
 
Embora árvores sejam fáceis de visualizar, elas apresentam alguns problemas difíceis de 
programação. A maioria das funções que usam árvore é recursiva porque a própria árvore é uma 
estrutura de dados recursiva. Isto é, cada subárvore é ela própria uma árvore. 
O procedimento de acesso a cada nó na árvore é chamado de transversalização da 
árvore. Existem três maneiras de percorrer uma árvore: de forma ordenada, pré-ordenada e pós-
ordenada. Usando a forma ordenada, cada nó é visitado da subárvore da esquerda, a raiz e, em 
seguida, a subárvore da direita. Na maneira pré-ordenada, cada nó é visitado da raiz, a subárvore da 
esquerda e, em seguida, a subárvore da direita. Com a pós-ordenada, cada nó é visitado da 
subárvore da esquerda, a subárvore da direita e, depois, a raiz. Considerando-se o exemplo da figura 
14.11, a ordem de acesso à árvore usando cada método é: 
 
 
Ordenada a b c d e f g 
Pré-ordenada d b a c f e g 
Pós-ordenada a c b e g f d 
 
 
Raiz: 15 
Grau da árvore: 2 
Nível 0: 15 
Nível 1: 5 e 16 
Nível 2: 2, 12 e 20 
Nível 3: 10, 13, 18 e 23 
Nível 4: 6 
Nível 5: 7 
Altura da árvore: 7 
 
f 
d
ge 
b
ca
 81
 
Figura 14.11 Exemplo de árvore binária. 
Uma árvore binária ordenada é aquela em que a subárvore da esquerda contém nós que 
são menores ou iguais à raiz e os da direita são maiores que a raiz. 
 
14.5 EXERCÍCIOS 
1. Elaborar as funções pop() e push() de uma pilha. 
2. Elaborar um programa que simule o armazenamento e recuperação de uma pilha. 
3. Elaborar as funções para armazenar e recuperar dados em uma fila. 
4.