Estrutura de Dados - UFJF · relevante importância é a forma de armazenar as informações, ... Prof. Gerson Borges Estrutura de Dados I 27 Estrutura da Lista usando Ponteiros

Prof. Gerson Borges Estrutura de Dados I 1

Estrutura de Dados

Introdução a Ponteiros


Sumárioè Explicação da importância do planejamento de ensino;è Métodos e técnicas que iremos trabalhar durante o semestre;è Grupos de Trabalhos – Seminário;è Atividade Ensino Aprendizagem – AEA; è Monitoria;è Tópicos abordados na disciplina ao longo do semestre;


Introduçãoè A automatização de tarefas é um aspecto marcante da sociedade moderna e na ciência da computação houve um processo de desenvolvimento simultâneo e interativo de máquinas (hardware) e dos elementos que gerenciam a execução automática (software) de uma tarefa. è Nesta grande evolução do mundo computacional, um fator de relevante importância é a forma de armazenar as informações, já que, informática é a ciência da informação. Então de nada adiantaria o grande desenvolvimento do hardware e do software, se a forma de armazenamento e tratamento da informação não acompanhasse esse desenvolvimento. Por isso a importância das estruturas de dados,que nada mais são, que formas otimizadas de armazenamento e tratamento das informações eletronicamente.


Introduçãoè As estruturas de dados, na sua maioria dos casos, foram espelhadas em formas naturais de armazenamento do nosso dia a dia, ou seja, nada mais são que a transformação de uma forma de armazenamento já conhecida e utilizada no nosso mundo para o mundo computacional;è Cada tipo de estrutura de dados possuem vantagens e desvantagens e cada uma delas tem sua área de atuação (massa de dados);


Tipo Apontador (Ponteiro)è Um das características mais marcantes do pascal é permitir a criação e destruição de variáveis durante a execução do programa;è Essas variáveis criadas e destruídas durante a execução do programa são chamadas variáveis dinâmicas;è Essas variáveis criadas e destruídas durante a execução do programa são chamadas variáveis dinâmicas;è Uma variável dinâmica não é declarada na parte de declaração de variáveis porque esta ainda não existe antes do seu tempo de execução, ela não possui sequer um nome, ficando a cargo dos ponteiros desempenhar esta função de “nome”;è Uma variável dinâmica é sempre referenciada indiretamente por um apontador, ou seja, para cada variável dinâmica criada deve existir um apontador, que literalmente aponta para ela, permitindo a sua manipulação.


è Os apontadores são declarados como as demais variáveis, seguindo a sintaxe da linguagem de programação utilizada;è Eles são variáveis que armazenam o endereço de memórias de outras variáveis, funcionando assim, como meio de referenciar uma variável dinâmica, permitindo o acesso a essa variável;è Outra característica dos apontadores é que na sua declaração deve ser indicada qual o tipo de variável este irá armazenar o endereço;è A principal função dos ponteiros é permitir a criação e a manipulação das variáveis dinâmicas, as quais irão compor as estruturas de dados dinâmicas.

Ponteiro - Características Gerais


è Declaração : a sintaxe de declaração de um tipo ponteiro é o seguinte.è type identificador = ^tipo; {onde o símbolo ^ indica que o identificador é um ponteiro};è isso indica que teremos um ponteiro com o nome de identificador com a capacidade de armazenar o endereço de memória de uma variável desse tipo;è Como os ponteiros são utilizados para implementar as estruturas de dados dinâmicas, o mais comum é que seja criado um tipo do ponteiro desejado (type) e depois declaramos (var) as variáveis ponteiros deste tipo.

Ponteiro no Pascal


ExemplotypeNome: string[35];PontNome : ^Nome;

varnome1,nome2,nome3 : PontNome;


Contextualizaçãoè Inicialização : como os ponteiros armazenam endereços de memória, assim que eles são declarados o seu conteúdo é um valor desconhecido (como as demais variáveis), ou seja, näopodemos prever para qual área de memória este esta apontando, por isso, a linguagem pascal permite que um ponteiro seja inicializado, da seguinte forma :è identificador := nil; {nil é um valor constante e pode ser armazenado em uma variável do tipo apontador para indicar que a variável não contém endereço de memória de nenhuma variável dinâmica}


è Criação de uma variável dinâmica: para criação de uma variável dinâmica é necessário que exista uma variável do tipo apontador para o tipo da variável que se deseja criar, e então utilizar-se o procedimento new, cuja sintaxe é a seguinte :è new(identificador); {onde, identificador deve ser uma variável do tipo ponteiro para o tipo de variável a ser criada};è Obs: quando uma variável dinâmica é criada através do procedimento NEW, um espaço de memória do tamanho da variável criada é alocado na memória heap e este espaço ficaráalocado até ser liberado.

Contextualização


è Destruição de uma variável dinâmica : para que o espaço de memória heap seja liberado é necessário que a variável dinâmica seja destruída, isso pode ser feito através do procedimento dispose, utilizando a seguinte sintaxe;è dispose(identificador); è Referencia a uma variável dinâmica : quando uma variável dinâmica é criada através de uma ponteiro, este pode ser utilizado para referenciá-la, permitindo a manipulação (leitura, atribuição, escrita, etc) desta variável como outra variável qualquer, para isso devemos utilizar o símbolo ^ após o nome da variável do tipo ponteiro:è identificador^

Contextualização


program ManipulacaoVariaveisDinamicas;type

nome = string[30];ponteiro = ^nome;

varp1, p2 : ponteiro;

beginnew(p1); new(p2);readln(p1^);p2^ := 'José Maria';p1^:= p1^ + ' ' + p2^;writeln(p1^);

end.

Exemplo


Exemplo

program ponteiro;type

pont = ^real;var

p1, p2 : p1, p2 : pontpont;;beginp1 := new(pont); p2 := new(pont);p1^ := 3.5;p2^ := -5.9;p1^ := p2^;p1 := p2;

end.


program ponteiro;

Exemplo



pont = ^real;

Exemplo



pont = ^real;var

p1, p2 : p1, p2 : pontpont;;

Exemplo

p1

p1



pont = ^real;var

p1, p2 : p1, p2 : pontpont;;beginp1 := new(pont);

Exemplo

p1

p1

10H

Endereço de Memória

10H



pont = ^real;var

p1, p2 : p1, p2 : pontpont;;beginp1 := new(pont); p2 := new(pont);

Exemplo

p1

p1

10H

20H


10H

20H



pont = ^real;var

p1, p2 : p1, p2 : pontpont;;beginp1 := new(pont); p2 := new(pont);p1^ := 3.5;

Exemplo

p1

p1

10H

20H

3.5


10H

20H



pont = ^real;var

p1, p2 : p1, p2 : pontpont;;beginp1 := new(pont); p2 := new(pont);p1^ := 3.5;p2^ := -5.9;

Exemplo

p1

p1

10H

20H

3.5


10H

-5.9 20H



pont = ^real;var

p1, p2 : p1, p2 : pontpont;;beginp1 := new(pont); p2 := new(pont);p1^ := 3.5;p2^ := -5.9;p1^ := p2^;

Exemplo

p1

p1

10H

20H

-5.9


10H

-5.9 20H



pont = ^real;var

p1, p2 : p1, p2 : pontpont;;beginp1 := new(pont); p2 := new(pont);p1^ := 3.5;p2^ := -5.9;p1^ := p2^;p1 := p2;

end.

Exemplo

p1

p1

10H

20H

-5.9


10H

-5.9 20H


LISTAS SIMPLESMENTE ENCADEADAS


LISTAS

Ø Definição: seqüência de zero ou mais elementos a1,a2, ...,an sendoai elementos de um mesmo tipon o tamanho da lista linear

Ø Propriedade fundamental: os elementos têm relações de ordem na listaai precede ai+1 (e ai sucede ai-1);a1 é o primeiro elemento da listaan é o último elemento da lista


ListasØ São estruturas flexíveis, que podem

crescer ou diminuir durante a execução do programa, de acordo com a demanda

Ø São mais adequadas para aplicações nos quais não é possível prever a demanda por espaços

Ex.: Gerência de memória, manipulação de símbolos, etc...


LISTAS COM IMPLEMENTAÇÃO ATRAVÉS DE PONTEIROS


Estrutura da Lista usando PonteirosØ Cada elemento da lista é trabalhado como

um nó;Ø Utilização de dois nós cabeças, um

apontando para o início da lista, e outro apontando para o final da lista, para facilitar as operações de Inserção e Busca

Ø Os nós (itens) da lista são registros com um ponteiro para guardar o endereço do seu sucessor

...x2 xnx1

Primeiro Último


Implementação da Lista Simplesmente Encadeadatype

Ponteiro = ^TipoNo;TipoItem = record

chave: TipoChave; {outros componentes desejadas...}

end;TipoNo = record

Item: TipoItem; Prox: Ponteiro;

end; TipoLista = record

Primeiro: Ponteiro;Ultimo : Ponteiro;

end;var L: TipoLista;


Implementação: Inicia_Lista e Lista_Vaziaprocedure Inicia_Lista (var L: TipoLista);

begin

New (L.Primeiro);

L.Último := L.Primeiro;

L.Primeiro^.Prox := nil;{L.Último^.Prox := nil}

end;

function Lista_Vazia (var L: TipoLista): boolean;

begin

Lista_Vazia := L.Último = L.Primeiro;end;


Procedimento de Inserçãoprocedure Insere (var L:TipoLista;

x:TipoItem);{ A inserção é feita à direita do ponteiro

Último }var pNovo: Ponteiro;begin

new(pNovo);L.Último^.Prox := pNovo;L.Último := pNovo;L.Último^.item := x; {pNovo^.item := x}L.Último^.Prox := nil; {pNovo^.item := nil}

end;


Inserção em lista simplesmente encadeada

pNovonew(pNovo);L.Último^.Prox := pNovo;L.Último := pNovo;L.Último^.item := x; L.Último^.Prox := nil;

ÚltimoPrimeiro

x1 x2

Último

Último

x


Implementação: Retira_Listaprocedure Retira_Lista(p: Ponteiro; var L: TipoLista;

var Item: TipoItem; var flag: boolean);{ o item a ser removido é o sucessor do apontado por p }var paux: Ponteiro;beginif Lista_Vazia(L) OR (p = nil) OR (p^.Prox=nil) then begin

writeln (`Erro: Lista Vazia ou Posição não existe`);flag := FALSE;

end else begin

flag := TRUE;paux:= p^.Prox; Item :=paux^.Item; p^.Prox:= paux^.Prox;if p^.Prox = nil then

L.Último := p;dispose(paux);end;

end;


Remoção em lista simplesmente encadeada

paux

paux:= p^.Prox; Item:= paux^.Item; p^.Prox:= paux^.Prox;if p^.Prox = nil then

L.Último := p;dispose(paux);

ÚltimoPrimeiro p

x2

x1 x3x2

Último

p : ponteiro para o nó anterior ao que será removido


Implementação: Imprime_Listaprocedure Imprime_Lista(var L: TipoLista);

var Aux: Ponteiro;

beginAux:= L.Primeiro^.Prox;

while (Aux <> nil) do

begin

writeln (‘Chave: ‘, Aux^.Item.Chave);Aux := Aux^.Prox;

end;

end;


ExemploØ Seja uma lista de alunos da disciplina XØ Registro para cada aluno:

Chave :1..999; {número de inscrição/matrícula}Nota :0..10; {média final}Curso :1..20; {código do curso}

Ø Problema: a partir da lista de alunos, gerar a lista dos alunos aprovados e reprovados na disciplinaØ Aprovado: Nota >= 7.0Ø Reprovado: caso contrário

Ø Imprimir a lista dos aprovados e dos reprovados


SoluçãoProgram TestaListaAlunos;Uses crt, ALUNOS;

var Aprovado, Reprovado : TipoLista;x: TipoItem;ok, fim: boolean;tecla: char;p, paux : TipoLista;

beginclrscr;writeln('####Programa com Listas de Alunos####');writeln;Inicia_Lista(Aprovado);Inicia_Lista(Reprovado);fim:=false;


Solução (cont)while NOT (fim) do begin { Entrada de dados }

writeln ('Entre com o numero de matricula ou -1 para sair');readln(x.chave);if (x.chave > 0) then begin

writeln ('Entre com a media');readln(x.nota);writeln ('Entre com o codigo do curso');readln(x.curso);if (x.nota>=7) then begin

Insere_Lista(x,Aprovado,ok);if ok then writeln('Inserçao em Aprovado ok');

endelse begin

Insere_Lista(x,Reprovado,ok);if ok then writeln('Inserçao em Reprovado ok');

endend else fim:=true;

end;


Solução (cont)writeln;writeln;writeln('####Lista dos Aprovados####')Imprime_Lista(Aprovado);writeln;writeln;writeln('####Lista dos Reprovados####')Imprime_Lista(Reprovado);

tecla:= readkey;clrscr;

end.

Documents

Estrutura de Dados - UFJF · relevante importância é a forma de armazenar as informações, ... Prof. Gerson Borges Estrutura de Dados I 27 Estrutura da Lista usando Ponteiros