EEL170 COMPUTAÇÃO I

4a Série de slides

Versão 30/08/2016

PASCAL

Alocação dinâmica de memória

A Alocação Estática de Memória:

Definimos exatamente as variáveis necessárias para resolver um problema

Usada quando conhecemos a quantidade e a dimensão das variáveis necessárias

Ex.: Var Nr1, nr2, nr3: integer;

// variáveis tipo inteiro Temperaturas: array[1..24] of integer;

// variável estruturada homogênea do tipo inteiro com uma dimensão e 24 elementos

A Alocação Dinâmica de Memória

Permite criar variáveis dinamicamente, em tempo de execução, a medida em que forem necessárias

Usada quando não sabemos a quantidade ou a dimensão das variáveis que necessitamos para resolver um problema

Em Pascal, C e C++ a alocação dinâmica de memória é implementada via pointer

Pointer

Um pointer é uma variável que aponta para uma outra variável, esta última criada em tempo de execução

Isto permite definir, durante a execução de um programa, quantas variáveis de um tipo de pointer serão criadas, e a dimensão dessas variáveis

O pointer tem um tipo: ele só pode apontar para variáveis de seu tipo

Pode-se imaginar o pointer como contendo uma referência de uma variável

Exemplo de alocação estática

Var Nr1, nr2, nr3: integer;

nr1

nr3

nr2Todas do tipo inteiro

Exemplo de alocação dinâmica

Var Var1, var2: ^integer

var1

var2

Podem apontar para variáveis do tipo inteiro

Varnr1, nr2: inteiro // variável estáticaVar1, var2: ^inteiro // pointerBegin... nr1 nr2 var1 var2nr1 15 15nr2 nr1 15new (var1)var1^ 25nr2 var1^ 25

25

Lista encadeada por pointer

início

nó

Encadeamento

Exemplo: agenda por pointerAlgoritmo agendaPointer

(* agenda em pointer com inclusão no início *)

tipo

tContato = ^rcontato (* pointer *)

rContato = estrutura nome: literal

fone: inteirolongo

proximo: tcontato (* recursão *)

fim

var

primeiro, novo, atual, ultimo: tcontato

Inicio

Primeiro nil // para inicializar com nulo

(* aqui devem seguir os comandos para o programa na estrutura de menu, vai ser apresentado apenas o procedimento para incluir contato *)

Procedimento incluirContatoInicio

(* procedimento para incluir contato no inicio *)

inicio

New (novo) // alocação dinâmica de memória

Leia (novo^.nome, novo^.fone) (* orientar e testar *)

Novo^.proximo nil

Se primeiro = nil então

primeiro novo // primeira inclusão

Senão Novo^.proximo primeiro

Primeiro novo // demais inclusões

fim

Exemplo de agenda

Primeiro contato: zé fone 45

Segundo contato: rui fone 80

Terceiro contato: lui fone 10

Ze 45primeiro

Rui 80 Ze 45

Lui 10 Rui 80 Ze 45

primeiro

primeiro

Procedimento listarContatos

(* procedimento para listar os contatos *)

Inicio

Atual primeiro

Enquanto atual <> nil faça

Escreva(atual^.nome, atual^.fone)

Atual atual^.proximo // navegação

fim

procedimento incluirContatoFim

(* procedimento para incluir contato no fim – inclusão mantendo a ordem cronológica *)

new (novo) // alocação dinâmica de memória

leia (novo^.nome, novo^.fone) // orientar e testar

novo^.proximo nil

se primeiro = nil entãoprimeiro novo // primeira inclusãoUltimo novo

senão // demais inclusõesultimo^.proximo novoultimo novo

fim

Exemplo de agenda

Primeiro contato: zé fone 45

Segundo contato: rui fone 80

Terceiro contato: lui fone 10

Ze 45primeiro

Ze 45 Rui 80

Ze 45 Rui 80 Lui 10

primeiro

primeiro

ultimo

ultimo

ultimo

primeiro

Novo exemplo linearAgenda que permita manter os nomes e telefones

de contatos em ordem alfabética em lista circularO contato atual deve ser apresentado na tela Opções:Incluir novo contato – este passa a ser o atualExcluir o contato atual – atual será o próximoAlterar o telefone do contato atualApresentar o próximo – será o atualApresentar o anterior – será o atualConsultar um contato pelo nome - será o atualListar todos os contatos – mantido o atual

Estruturas não lineares

Nas estruturas lineares pode-se definir, dado um elemento, quais são seus sucessor e antecessor

Nas estruturas não lineares pode haver mais de um sucessor ou antecessor

As árvores são estruturas não lineares que iniciam num “nó” chamado raiz, e deste pode-se passar a seus “filhos”, em uma estrutura pai-filho, até chegar aos nós que não em filhos, chamados “folhas” da árvore.

Pode-se imaginar estas estruturas como árvores invertidas

A quantidade de filhos de cada nó dá a ordem da árvore

Nas árvores binárias cada nó pode ter até dois filhos

Exemplo de árvore binária

d

b f

a c e g

raiz

folhas

Exemplo não linear

Agenda que permita manter os nomes e telefones de contatos em ordem alfabética em uma árvore binária

Opções:

Incluir novo contato

Alterar o telefone de um contato

Consultar um contato pelo nome

Listar todos os contatos em ordem alfabética

algoritmo agendaArvore

(* agenda em árvore binária; responsável:...; data:...*)

tipo

noAgenda= ^regAgenda

regAgenda= estrutura nome: string(30)

Telefone: string(16)

esq, dir: noAgenda

fim

var

raiz, atual, novo, aux: noAgenda

inicio

raiz ← nil

repita

opção ← funMenu // função para apresentar as opções

caso opção seja:

1: procIncluir

2: procAlterar

3: procConsultar

4: procListar(raiz)

fim

ate que opção = 5

fim

procedimento procIncluir // para incluir novo contato

inicio

new(novo) // criação dinâmica de variável

leia(novo^.nome, novo^.telefone) // Orientar e validar

novo^.esq, novo^.dir ← nil

se raiz = nil então // agenda vazia

raiz ← novo

senão buscarLugar(raiz, novo) // demais casos

atual ← novo

fim

procedimento buscarLugar(var atual: noAgenda; novo: noagenda)

(* buscar o lugar na árvores descendo até um nó livre;

ATENÇÃO: o primeiro parâmetro é por referência, o que é necessário para o novo nó ser ligado à árvore *)

inicio

se atual = nil então

atual ← novo

senão se novo^.nome > atual^.nome então

buscarLugar(atual^.dir,novo)

senão buscarLugar(atual^.esq,novo)

fim

Para listar em ordem alfabética:

Vamos nos basear na topologia da árvore binária:

O nó “a” tem os filhos “b” e “c”; para se listar estes nós em ordem alfabética crescente será necessário listá-los na ordem “b a c”; esta será a base para o algoritmo de listar em ordem alfabética crescente

a

b c

procedimento procListar(atual: noAgenda)

// para listar os contatos em ordem alfabética

inicio

se atual <> nil então

inicio

procListar(atual^.esq)

escrever(atual^.nome, atual^.telefone)

procListar(atual^.dir)

fim

fim

Para listar em outras ordens

Para listar em ordem alfabética decrescente basta chamar primeiro pela direita no algoritmo anterior, escrever e depois chamar pela esquerda

Para outras ordens basta alterar a ordem dos três comandos que navegam e escrevem os dados

Isto é possível porque nos baseamos na topologia da árvore, e porque tanto a definição da árvore como o algoritmo são recursivos

Demais procedimentos do problema

Baseados no que foi exposto pode-se construir os demais procedimentos.

Fica como exercício.