11.3.4 – Encadeamento circular11.3.4 – Encadeamento circular

No encadeamento apresentado, seja No encadeamento apresentado, seja pp um um ponteiroponteiro apontando para um determinado nóapontando para um determinado nó

Com sucessivas execuções do comando Com sucessivas execuções do comando p = p-p = p->prox;>prox; pode-se pode-se percorrer a listapercorrer a lista

Mas, com esse comando não se chega a Mas, com esse comando não se chega a nós nós anterioresanteriores

p

Lista encadeada circular:Lista encadeada circular:

O ponteiro do O ponteiro do último nóúltimo nó aponta para o aponta para o nó-nó-líderlíder, ao invés de apontar para , ao invés de apontar para NULLNULL

Para determinadas aplicações, os conceitos de Para determinadas aplicações, os conceitos de primeiroprimeiro, , segundosegundo, ... e , ... e últimoúltimo elementos da elementos da lista lista não têm relevâncianão têm relevância

Então pode-se Então pode-se eliminar o nó-lídereliminar o nó-líder, sendo um , sendo um ponteiro para qualquer nó do encadeamento ponteiro para qualquer nó do encadeamento suficiente para suficiente para identificaridentificar a lista a lista

11.3.5 – Listas duplamente encadeadas11.3.5 – Listas duplamente encadeadas

Há Há aplicaçõesaplicações de listas lineares que exigem de listas lineares que exigem frequentes frequentes percursos nos dois sentidospercursos nos dois sentidos

Pode-se Pode-se acrescentar a cada nóacrescentar a cada nó mais um mais um campo do tipo ponteiro (campo do tipo ponteiro (prevprev), com a ), com a finalidade de apontar para o finalidade de apontar para o nó anteriornó anterior no no encadeamentoencadeamento

Declarações:Declarações:

typedef char nome[16];typedef char nome[16];typedef struct noh noh;typedef struct noh noh;typedef noh *lista;typedef noh *lista;typedef noh *posicao;typedef noh *posicao;struct noh {struct noh {

nome elem; noh nome elem; noh *prev*prev, *prox;, *prox;};};

Inserção de um nó na posição p:Inserção de um nó na posição p:

p Nó a ser inserido

Remoção do um nó da posição p:Remoção do um nó da posição p:

p

Nó a ser removido

Exercícios 11.3:Exercícios 11.3:

1.1.Escrever um subprograma que receba como argumentos Escrever um subprograma que receba como argumentos uma lista linear uma lista linear LL encadeada por ponteiros e que elimine encadeada por ponteiros e que elimine dessa lista os elementos em duplicata. Escrever também dessa lista os elementos em duplicata. Escrever também um programa principal para testar devidamente essa um programa principal para testar devidamente essa funçãofunção

2.2.Escrever um subprograma que receba como argumentos Escrever um subprograma que receba como argumentos dois ponteiros dois ponteiros L1L1 e e L2L2, apontando cada um para um , apontando cada um para um encadeamento distinto de estruturas, ambos iniciados por encadeamento distinto de estruturas, ambos iniciados por um nó-líder, e que efetue uma troca de estruturas nesses um nó-líder, e que efetue uma troca de estruturas nesses encadeamentos. No encadeamento de encadeamentos. No encadeamento de L1L1 devem ficar devem ficar todas as estruturas cujos elementos guardados sejam todas as estruturas cujos elementos guardados sejam números ímpares e no encadeamento de números ímpares e no encadeamento de L2L2 aquelas aquelas contendo números pares.contendo números pares.

Esse subprograma não deve alocar nenhuma nova Esse subprograma não deve alocar nenhuma nova estrutura, nem deixar nenhuma estrutura já existente fora estrutura, nem deixar nenhuma estrutura já existente fora dos encadeamentos, nem trocar o valor guardado em dos encadeamentos, nem trocar o valor guardado em nenhuma estrutura.nenhuma estrutura.

Escrever um programa principal para testar devidamente Escrever um programa principal para testar devidamente o referido subprogramao referido subprograma

3.3. Escrever um subprograma que receba como Escrever um subprograma que receba como argumento uma lista argumento uma lista L L encadeada circular sem nó-encadeada circular sem nó-líder e que inverta seu encadeamento, conforme líder e que inverta seu encadeamento, conforme apresentado na figura abaixoapresentado na figura abaixo

Importante: Importante: o subprograma não deve deletar, nem o subprograma não deve deletar, nem criar qualquer nó, nem mudar o conteúdo de nenhum criar qualquer nó, nem mudar o conteúdo de nenhum nó.nó.

Escrever um programa principal para testar Escrever um programa principal para testar devidamente o referido subprograma.devidamente o referido subprograma.

Capítulo XI – Noções de Capítulo XI – Noções de Estruturas de DadosEstruturas de Dados

11.1 – Importância de boa 11.1 – Importância de boa estruturação de informaçõesestruturação de informações

11.2 – Modelos de armazenamento de 11.2 – Modelos de armazenamento de informaçõesinformações

11.3 – Listas lineares encadeadas11.3 – Listas lineares encadeadas11.4 – Pilhas e filas11.4 – Pilhas e filas11.5 – Árvores11.5 – Árvores

11.4 – Pilhas e Filas11.4 – Pilhas e Filas11.4.1 – Listas lineares com disciplina de 11.4.1 – Listas lineares com disciplina de

acessoacesso As As listas lineares geraislistas lineares gerais admitem admitem inserçãoinserção e e

remoçãoremoção de elementos em de elementos em qualquer posiçãoqualquer posição Existem Existem listas lineares especiaislistas lineares especiais que admitem que admitem

inserçãoinserção e e remoçãoremoção somente em suas duas somente em suas duas extremidades extremidades

São elas as São elas as pilhaspilhas, as , as filasfilas e os e os deques deques Pilhas: Pilhas: inserção e remoção em apenas uma das inserção e remoção em apenas uma das

extremidadesextremidades Filas:Filas: inserção numa extremidade e remoção na outra inserção numa extremidade e remoção na outra Deques:Deques: as duas operações nas duas extremidades as duas operações nas duas extremidades

11.4.2 – Pilhas11.4.2 – Pilhas O O últimoúltimo a entrar é o a entrar é o primeiroprimeiro a sair ( a sair (LIFOLIFO – –

last in first out)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:Estrutura encadeada para pilhas:

Declarações:Declarações:typedef struct noh noh;typedef noh *pilha;struct noh {

int elem; noh *prox;};pilha P;

Operações típicas:Empilhar um

elementoDesempilhar o elemento do

topoCopiar o elemento do topoEsvaziarVerificar se está vazia

Utilidade de pilhas:Utilidade de pilhas:

Cálculo de expressõesCálculo de expressões

Gerenciamento da área de dados das funções Gerenciamento da área de dados das funções na execução de um programana execução de um programa

Algoritmos para árvores e grafosAlgoritmos para árvores e grafos

Eliminação de recursividadeEliminação de recursividade

11.4.3 – Filas11.4.3 – Filas

O O primeiroprimeiro a entrar é o a entrar é o primeiroprimeiro a sair ( a sair (FIFOFIFO – first in first out)– first in first out)

Podem usar estrutura Podem usar estrutura contíguacontígua e e encadeadaencadeada

A seguir, uma representação gráfica da A seguir, uma representação gráfica da estrutura encadeadaestrutura encadeada

Estrutura encadeada para filas:Estrutura encadeada para filas:

Declarações: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

elementoRemover o elemento da

frenteCopiar o elemento da frenteEsvaziarVerificar se está vazia

Utilidade de filas:Utilidade de filas:

Gerenciamento da utilização de recursos Gerenciamento da utilização de recursos computacionais pelo sistema operacionalcomputacionais pelo sistema operacional

Software de controle de saída e chegada de Software de controle de saída e chegada de aeronaves em aeroportosaeronaves em aeroportos

Algoritmos para árvores e grafosAlgoritmos para árvores e grafos

Circuitos eletrônicosCircuitos eletrônicos

Capítulo XI – Noções de Capítulo XI – Noções de Estruturas de DadosEstruturas de Dados

11.1 – Importância de boa 11.1 – Importância de boa estruturação de informaçõesestruturação de informações

11.2 – Modelos de armazenamento de 11.2 – Modelos de armazenamento de informaçõesinformações

11.3 – Listas lineares encadeadas11.3 – Listas lineares encadeadas11.4 – Pilhas e filas11.4 – Pilhas e filas11.5 – Árvores11.5 – Árvores

11.5 – Árvores11.5 – Árvores11.5.1 – Definições11.5.1 – Definições

Forma natural de apresentação

Cada Cada elementoelemento é armazenado em um é armazenado em um nónó

Sobre os nós existe uma Sobre os nós existe uma hierarquia paternahierarquia paterna

Entre alguns pares, existe a relação Entre alguns pares, existe a relação “pai de”“pai de”

A é pai de B, C e D

D é pai de H

C é pai de F e G

etc.

Raiz: Raiz: nó de nó de máxima hierarquiamáxima hierarquia de uma de uma árvoreárvore

Abaixo, Abaixo, A A é a é a raizraiz

Cada nó tem um e Cada nó tem um e apenas um paiapenas um pai (exceto a (exceto a raiz)raiz)

Cada nó tem Cada nó tem zero ou mais filhoszero ou mais filhos

Um nó não pode ter um Um nó não pode ter um ancestral como filhoancestral como filhoExemplo: I não pode ser pai de H, D ou A

Definição recursiva de Árvore:Definição recursiva de Árvore:

Um Um único nóúnico nó é por si mesmo uma é por si mesmo uma árvoreárvore; ele ; ele é a é a raizraiz dessa árvore dessa árvore

Sejam Sejam AA11, , AA22, ... , , ... , AAkk, árvores de raízes , árvores de raízes nn11, , nn22, ..., , ..., nnkk, respectivamente e , respectivamente e nn um nó não um nó não pertencente a nenhuma delas pertencente a nenhuma delas Fazendo Fazendo nn pai de pai de nn11, , nn22, ..., , ..., nnkk, obtém-se uma , obtém-se uma

nova árvorenova árvore

n1

A1

n2

A2

n3

A3

nk

Ak

n

Mostrar que a seguinte figura é uma árvore:Mostrar que a seguinte figura é uma árvore:

A

HGF

DC

E

B

K J I

II,, J J e e K K são por si só árvores; fazendo são por si só árvores; fazendo H H pai das pai das raízes raízes II,, J J e e K K, obtém-se nova árvore, obtém-se nova árvore

FF,, G G e e E E são por si só árvores; fazendo são por si só árvores; fazendo B B pai de pai de EE, , C C pai de pai de F F e e GG,, ee D D pai de pai de HH, obtém-se novas , obtém-se novas árvoresárvores

Fazendo Fazendo A A pai de pai de BB, , C C e e DD, , obtém-se nova árvoreobtém-se nova árvore

A

HGF

DC

E

B

K J I

FolhaFolha: nó sem filhos; abaixo, : nó sem filhos; abaixo, EE,, F F,, G G,, I I,, J J e e K K são folhassão folhas

IrmãosIrmãos: filhos de um mesmo nó; abaixo:: filhos de um mesmo nó; abaixo:

BB, , C C e e D D são irmãos; são irmãos; F F e e G G são irmãos; são irmãos; II, , JJ e e K K são irmãossão irmãos

FlorestaFloresta: conjunto de zero ou mais árvores : conjunto de zero ou mais árvores disjuntasdisjuntas

Forma parentética: Forma parentética: forma de forma de representarrepresentar uma uma árvore em que cada elemento é um árvore em que cada elemento é um caracterecaractere

Coloca-se entre Coloca-se entre parêntesisparêntesis: primeiramente a : primeiramente a raizraiz, depois as , depois as formas parentéticasformas parentéticas das sub- das sub-árvores da raiz ordenadas da esquerda para a árvores da raiz ordenadas da esquerda para a direita (direita (recursividaderecursividade):):

(A (B (E)) (C (F) (G)) (D (H (I) (J) (A (B (E)) (C (F) (G)) (D (H (I) (J) (K))) )(K))) )

Forma parentética: Forma parentética: definição recursivadefinição recursiva

1.1.Sendo Sendo c c um caractere genérico, um caractere genérico, (c)(c) é uma é uma forma parentética corretaforma parentética correta

2.2.Se Se αα11, , αα22, , αα33, ... , ... ααnn, são formas parentéticas , são formas parentéticas corretas corretas (n > 0)(n > 0), então , então (c α(c α11αα22αα33 ... α ... αnn)) também étambém é

Ordenação ou caminhamento em pré-ordem: Ordenação ou caminhamento em pré-ordem: é uma forma de ordenar todos os nós de uma é uma forma de ordenar todos os nós de uma árvoreárvore

Primeiramente aparece a raiz Primeiramente aparece a raiz nn Seguida dos nós de Seguida dos nós de AA11 em pré-ordem em pré-ordem Seguidos dos nós de Seguidos dos nós de AA22 em pré-ordem, etc. em pré-ordem, etc. Até os nós de Até os nós de AAkk em pré-ordemem pré-ordem

n1

A1

n2

A2

n3

A3

nk

Ak

n

É também uma definição recursiva

Exemplo: pré-ordem da árvore abaixo:Exemplo: pré-ordem da árvore abaixo:

A B E C F G D H I J KA B E C F G D H I J K

11.5.2 – Estruturas de dados para 11.5.2 – Estruturas de dados para árvoresárvores

Uma árvore também pode ser armazenada num Uma árvore também pode ser armazenada num vetorvetor ou num ou num encadeamentoencadeamento de estruturas de estruturas

Seja a árvore já vista:Seja a árvore já vista:

A) Estrutura contígua (vetor)A) Estrutura contígua (vetor)

Nós são índices do vetorNós são índices do vetor

Os nós estão em pré-ordemOs nós estão em pré-ordem

Declarações:Declarações:typedef int noh;typedef int noh;typedef struct celula celula;typedef struct celula celula;typedef struct arvore arvore;typedef struct arvore arvore;struct celula {char info; int nfilhos, pai;}struct celula {char info; int nfilhos, pai;}struct arvore {celula Espaco[100]; int nnos;}struct arvore {celula Espaco[100]; int nnos;}noh n1, n2, n3;noh n1, n2, n3;arvore A1, A2, A3;arvore A1, A2, A3;

Nesta estrutura, os algoritmos são geralmente ineficientes

B) Estrutura com encadeamento de pais e B) Estrutura com encadeamento de pais e irmãosirmãos

Declarações:Declarações:typedef struct celula celula;typedef struct celula celula;typedef celula *noh;typedef celula *noh;typedef celula *arvore;typedef celula *arvore;struct celula {char informacao; noh pai, fesq, idir;};struct celula {char informacao; noh pai, fesq, idir;};noh n1, n2, n3;noh n1, n2, n3;arvore A1, A2, A3;arvore A1, A2, A3;

Nós Nós são ponteiros parasão ponteiros paracélulascélulas

Para ilustrar, a seguir,Para ilustrar, a seguir,comandos para construir comandos para construir a árvore ao ladoa árvore ao lado

info

pai

fesq idir

celula

arvore A; noh x, y;arvore A; noh x, y; A = (noh) malloc (sizeof (celula));A = (noh) malloc (sizeof (celula)); A->info = 'A'; A->pai = A->idir = NULL;A->info = 'A'; A->pai = A->idir = NULL; A->fesq = (noh) malloc (sizeof (celula));A->fesq = (noh) malloc (sizeof (celula)); x = A->fesq;x = A->fesq; x->info = 'B'; x->pai = A;x->info = 'B'; x->pai = A; x->fesq = (noh) malloc (sizeof (celula));x->fesq = (noh) malloc (sizeof (celula)); x->idir = (noh) malloc (sizeof (celula));x->idir = (noh) malloc (sizeof (celula)); x->fesq->info = 'E';x->fesq->info = 'E'; x->fesq->pai = x;x->fesq->pai = x; x->fesq->fesq = x->fesq->idir = NULL;x->fesq->fesq = x->fesq->idir = NULL; x = x->idir;x = x->idir; x->info = 'C';x->info = 'C'; x->pai = A;x->pai = A; x->idir = NULL;x->idir = NULL; x->fesq = (noh) malloc (sizeof (celula));x->fesq = (noh) malloc (sizeof (celula)); y = x->fesq;y = x->fesq; y->info = 'F';y->info = 'F'; y->pai = x;y->pai = x; y->fesq = NULL;y->fesq = NULL; y->idir = (noh) malloc (sizeof (celula));y->idir = (noh) malloc (sizeof (celula)); y->idir->info = 'G';y->idir->info = 'G'; y->idir->pai = x;y->idir->pai = x; y->idir->fesq = y->idir->idir = NULL;y->idir->fesq = y->idir->idir = NULL;

A

x y

G

A

x

B

E

xC

y

F

A

G

A

B

E

C

F

Os comandos anteriores formam apenas esta árvore em particular

Em CES-11 serão vistos algoritmos gerais de formação de árvores