11.3.4 – Encadeamento circular

No encadeamento apresentado, seja p um ponteiro apontando
para um determinado nó
p

Com sucessivas execuções do comando p = p->prox;
pode-se percorrer a lista

Mas, com esse comando não se chega a nós anteriores
Lista encadeada circular:

O ponteiro do último nó aponta para o nó-líder, ao invés de
apontar para NULL

Para determinadas aplicações, os conceitos de primeiro,
segundo, ... e último elementos da lista não têm relevância

Então pode-se eliminar o nó-líder, sendo um ponteiro para
qualquer nó do encadeamento suficiente para identificar a
lista
11.3.5 – Listas duplamente encadeadas

Há aplicações de listas lineares que exigem frequentes
percursos nos dois sentidos

Pode-se acrescentar a cada nó mais um campo do tipo
ponteiro (prev), com a finalidade de apontar para o nó
anterior no encadeamento

Declarações:
typedef char nome[16];
typedef struct noh noh;
typedef noh *lista;
typedef noh *posicao;
struct noh {
nome elem; noh *prev, *prox;
};

Inserção de um nó na posição p:
p
Nó a ser
inserido

Remoção do um nó da posição p:
Nó a ser
removido
p
Exercícios 11.3:
1. Escrever um subprograma que receba como argumentos uma
lista linear L encadeada por ponteiros e que elimine dessa lista os
elementos em duplicata. Escrever também um programa principal
para testar devidamente essa função
2. Escrever um subprograma que receba como argumentos dois
ponteiros L1 e L2, apontando cada um para um encadeamento
distinto de estruturas, ambos iniciados por um nó-líder, e que
efetue uma troca de estruturas nesses encadeamentos. No
encadeamento de L1 devem ficar todas as estruturas cujos
elementos guardados sejam números ímpares e no encadeamento
de L2 aquelas contendo números pares.
Esse subprograma não deve alocar nenhuma nova estrutura, nem
deixar nenhuma estrutura já existente fora dos encadeamentos,
nem trocar o valor guardado em nenhuma estrutura.
Escrever um programa principal para testar devidamente o referido
subprograma
3.
Escrever um subprograma que receba como argumento uma lista L
encadeada circular sem nó-líder e que inverta seu encadeamento,
conforme apresentado na figura abaixo
Importante: o subprograma não deve deletar, nem criar qualquer nó,
nem mudar o conteúdo de nenhum nó.
Escrever um programa principal para testar devidamente o referido
subprograma.
Capítulo XI – Noções de
Estruturas de Dados
11.1 – Importância de boa estruturação de
informações
11.2 – Modelos de armazenamento de informações
11.3 – Listas lineares encadeadas
11.4 – Pilhas e filas
11.5 – Árvores
11.4 – Pilhas e Filas
11.4.1 – Listas lineares com disciplina de acesso

As listas lineares gerais admitem inserção e remoção de
elementos em qualquer posição

Existem listas lineares especiais que admitem inserção e
remoção somente em suas duas extremidades

São elas as pilhas, as filas e os deques

Pilhas: inserção e remoção em apenas uma das extremidades

Filas: inserção numa extremidade e remoção na outra

Deques: as duas operações nas duas extremidades
11.4.2 – Pilhas

O último a entrar é o primeiro a sair (LIFO – last in first
out)
Podem usar
estrutura contígua
e encadeada
A seguir, uma
representação
gráfica da
estrutura
encadeada
Estrutura encadeada para pilhas:
Declarações:
typedef struct noh noh;
typedef noh *pilha;
struct noh {
int elem; noh *prox;
};
pilha P;
Operações típicas:
Empilhar um elemento
Desempilhar o elemento do
topo
Copiar o elemento do topo
Esvaziar
Verificar se está vazia
Utilidade de pilhas:

Cálculo de expressões

Gerenciamento da área de dados das funções na execução de
um programa

Algoritmos para árvores e grafos

Eliminação de recursividade
11.4.3 – Filas

O primeiro a entrar é o primeiro a sair (FIFO – first in first
out)

Podem usar estrutura contígua e encadeada

A seguir, uma representação gráfica da estrutura encadeada
Estrutura encadeada para filas:
Declarações:
typedef struct noh noh;
typedef struct fila fila;
struct noh
{int elem; noh *prox;};
struct fila {noh *fr, *tr;};
fila F;
Operações típicas:
Entrar com um elemento
Remover o elemento da
frente
Copiar o elemento da frente
Esvaziar
Verificar se está vazia
Utilidade de filas:

Gerenciamento da utilização de recursos computacionais pelo
sistema operacional

Software de controle de saída e chegada de aeronaves em
aeroportos

Algoritmos para árvores e grafos

Circuitos eletrônicos
Capítulo XI – Noções de
Estruturas de Dados
11.1 – Importância de boa estruturação de
informações
11.2 – Modelos de armazenamento de informações
11.3 – Listas lineares encadeadas
11.4 – Pilhas e filas
11.5 – Árvores
11.5 – Árvores
11.5.1 – Definições
Forma natural de
apresentação

Cada elemento é armazenado em um nó

Sobre os nós existe uma hierarquia paterna

Entre alguns pares, existe a relação “pai de”
A é pai de B, C e D
D é pai de H
C é pai de F e G
etc.

Raiz: nó de máxima hierarquia de uma árvore

Abaixo, A é a raiz

Cada nó tem um e apenas um pai (exceto a raiz)

Cada nó tem zero ou mais filhos

Um nó não pode ter um ancestral como filho
Exemplo: I não pode ser
pai de H, D ou A
Definição recursiva de Árvore:

Um único nó é por si mesmo uma árvore; ele é a raiz dessa
árvore

Sejam A1, A2, ... , Ak, árvores de raízes n1, n2, ..., nk,
respectivamente e n um nó não pertencente a nenhuma delas
 Fazendo n pai de n1, n2, ..., nk, obtém-se uma nova árvore
n
n1
A1
n2
A2
nk
n3
A3
Ak
Mostrar que a seguinte figura é uma árvore:
A
B
E
C
F
D
G
H
I
J
K

I, J e K são por si só árvores; fazendo H pai das raízes I, J e
K, obtém-se nova árvore

F, G e E são por si só árvores; fazendo B pai de E, C pai de F
e G, e D pai de H, obtém-se novas árvores
A
B
E

C
F
Fazendo A pai de B, C e D,
obtém-se nova árvore
D
G
H
I
J
K

Folha: nó sem filhos; abaixo, E, F, G, I, J e K são folhas

Irmãos: filhos de um mesmo nó; abaixo:
B, C e D são irmãos; F e G são irmãos; I, J e K são irmãos

Floresta: conjunto de zero ou mais árvores disjuntas
Forma parentética: forma de representar uma árvore em que
cada elemento é um caractere

Coloca-se entre parêntesis: primeiramente a raiz, depois as
formas parentéticas das sub-árvores da raiz ordenadas da
esquerda para a direita (recursividade):
(A (B (E)) (C (F) (G)) (D (H (I) (J) (K))) )
Forma parentética: definição recursiva
1. Sendo c um caractere genérico, (c) é uma forma parentética
correta
2. Se α1, α2, α3, ... αn, são formas parentéticas corretas
(n > 0), então (c α1α2α3 ... αn) também é
Ordenação ou caminhamento em pré-ordem: é uma forma
de ordenar todos os nós de uma árvore




Primeiramente aparece a raiz n
Seguida dos nós de A1 em pré-ordem
Seguidos dos nós de A2 em pré-ordem, etc.
Até os nós de Ak em pré-ordem
É também uma
definição recursiva
n
n1
A1
n2
A2
nk
n3
A3
Ak
Exemplo: pré-ordem da árvore abaixo:
A B E C F G D H I J K
11.5.2 – Estruturas de dados para árvores

Uma árvore também pode ser armazenada num vetor ou num
encadeamento de estruturas

Seja a árvore já vista:
A) Estrutura contígua (vetor)

Nós são índices do vetor

Os nós estão em pré-ordem
Declarações:
typedef int noh;
typedef struct celula celula;
typedef struct arvore arvore;
struct celula {char info; int nfilhos, pai;}
struct arvore {celula Espaco[100]; int nnos;}
noh n1, n2, n3;
Nesta estrutura, os algoritmos
arvore A1, A2, A3;
são geralmente ineficientes
B) Estrutura com encadeamento de pais e irmãos
Declarações:
info pai
typedef struct celula celula;
celula
typedef celula *noh;
fesq idir
typedef celula *arvore;
struct celula {char informacao; noh pai, fesq, idir;};
noh n1, n2, n3;
arvore A1, A2, A3;

Nós são ponteiros para
células

Para ilustrar, a seguir,
comandos para construir
a árvore ao lado
arvore A; noh x, y;
A = (noh) malloc (sizeof (celula));
A->info = 'A'; A->pai = A->idir = NULL;
A->fesq = (noh) malloc (sizeof (celula));
x = A->fesq;
x->info = 'B'; x->pai = A;
x->fesq = (noh) malloc (sizeof (celula));
x->idir = (noh) malloc (sizeof (celula));
x->fesq->info = 'E';
x->fesq->pai = x;
x->fesq->fesq = x->fesq->idir = NULL;
x = x->idir;
x->info = 'C';
x->pai = A;
x
x->idir = NULL;
x->fesq = (noh) malloc (sizeof (celula));
y = x->fesq;
E
y->info = 'F';
y->pai = x;

y->fesq = NULL;
y->idir = (noh) malloc (sizeof (celula));
y->idir->info = 'G';
y->idir->pai = x;
y->idir->fesq = y->idir->idir = NULL;
A

A

B
C
x


F
G


y
x
y

Os comandos anteriores
formam apenas esta árvore
em particular
A

A

Em CES-11 serão vistos
algoritmos gerais de
formação de árvores
B
C

E


F
G


