Aula 03 – 15/03
Vetores Bidimensionais – Debug - Ponteiros – Listas Encadeadas Simples
Vetores Bidimensionais - Matrizes
• Parecido com estrutura de vetores porem mais elaborada
• Estrutura que consiste de linhas e colunas que unidas damos o nome
de células
• Semelhante a tabelas
• Primeiro índice representa a linha e o segundo a coluna.
Declarações em Delphi/Pascal
Matriz estática
MatrizEstatica: array [0..1, 0..3] of string;
MatrizEstatica: array [0..1] of array[0..3] of string;
Matriz dinâmica
MatrizDinamica: array of array of string;
SetLength( MatrizDinamica, 2, 3 );
// 2 linhas 3 colunas
Acesso aos valores da matriz
Matriz[1][4] // Acesso a linha 1 coluna 4
Matriz[2] // Acesso a todos os elementos linha 2
Percorrer os elementos de uma matriz
for Linha := Low(Matriz) to High(Matriz) do
begin
for Coluna := Low(Matriz[Linha]) to High(Matriz[Linha]) do
begin
ShowMessage( Matriz[Linha, Coluna] );
end;
end;
Aplicação de Matrizes
• Manipulação de imagens – informação de cores de pixel
• Rotinas de criptografia – cálculos
• Sistemas de geolocalização – cálculo de coordenas
• Desenvolvimento de jogos – lógica
• Estrutura de tabelas em banco de dados - linhas(registros) colunas
(campos)
Listas encadeadas
Listas encadeadas simples – Listas duplamente encadeadas – Listas Circulares
Ponteiros
• Memória do computador e um grande vetor de bytes
• Cada byte é uma unidade de memória conhecida como célula
• Exemplo de uso de identificadores.
Ponteiro
1258
849
98577
Variável
Casa Azul
Casa Amarela
Casa do Vizinho
• Ponteiros ou apontadores são tipos de dados utilizados para acessar
endereços de memória.
• Os ponteiros são a base para a alocação dinâmica de memória
• O valor do ponteiro corresponde a uma posição na memória onde o
dado(valor) esta armazenado.
• Variável (qualquer que seja) e um conjunto de células de memória.
• A variável é composta por nome, tipo, conteúdo e endereço
• Cada variável ocupa uma quantidade de n de células
Integer = 4; Boolean = 1;
• Utilizamos o ^ (circunflexo) antes do tipo de dado para declarar uma
variável do tipo ponteiro
Ptr: ^Integer;
• Utilizamos o ^ (circunflexo) depois da variável para acessar o valor do
ponteiro.
Ptr^:= 28;
ShowMessage( IntToStr( Ptr^));
• Utilizamos o @ para obter o ponteiro de uma variável
Ptr: ^Integer;
Int: Inteiro;
Ptr:= @Int;
• Ponteiros tipados que são muito comuns.
PInt: ^Integer;
PStr: ^string;
PPes: ^TPessoa;
• Para alocar memória para um ponteiro utilizamos a função New(). Essa
função aloca um ponteiro com base no tamanho do tipo de dados
TPessoa = record;
Nome: string;
end;
Pessoa:= ^TPessoa;
New(Pessoa);
Pessoa^.Nome := ‘Fulano’;
ShowMessage(Pessoa^.Nome);
• Para liberar a memoria alocada com a função New() utilizamos a função
Dispose()
Dispose(Pessoa);
var
Numero: Integer;
Flag: Char;
Ptr: ^Integer;
Uso pratico de ponteiros
• Usado com a API do Windows onde vários métodos tem como
parâmetros ponteiros de memória.
• No desenvolvimento de componentes para o Delphi.
• Integrações com DLLs.
• Utilizado por componentes do Delphi(TList, TCLientDataSet. etc).
• No Delphi as referências a classes são ponteiros.
• Recursos de RTTI.
Prática
download do projeto DisplayPointers
• Declarar uma variável string e
acessar o seu valor através de
ponteiros
• Uso Debug
• Declara uma variável do tipo
record e acessar através de
ponteiros
Listas encadeadas
• É uma lista com agrupamento de itens conhecidos como nós(blocos
de memória)
• Os nós possuem um tipo de variável especial chamada ponteiro.
• O ponteiros apontam para o próximo item do agrupamento
• Os nós possuem dois campos: O Dado(valor) e o Ponteiro(posição de
memória do próximo nó)
• A listas deve ser identificada pelo primeiro nó(cabeça) e a partir desse
nó os outros itens podem ser visitados até o final da lista
• Os vetores sequencias eram acessados pelo índice pois estavam
alocados sequencialmente na memória.
• As listas encadeadas possuem seus itens em posições NÃO
sequencias na memória o que justifica o uso de ponteiros.
• Observe que os ponteiros intercalam cada nó com o seu vizinho de
modo a criar uma lista em memória
• O final da lista encadeada é identificada pelo valor nil do ponteiro.
Representação gráfica de uma lista com nós
Representação gráfica de inserção na lista
Representação gráfica de exclusão na lista
Estrutura de um nó
PApontador = ^TItem;
TItem = record
Valor: string;
Proximo: PApontador;
end;
Incluindo itens na lista
PrimeiroNo: PApontador;
...
...
var
NoAuxiliar: PApontador;
begin
New( NoAuxiliar ); // alocando espaço na memória
NoAuxiliar.Proximo:=PrimeiroNo;
NoAuxiliar.Valor:= InputBox('', 'Digite uma string', '');
PrimeiroNo:= NoAuxiliar;
end;
Excluir item na lista – Parte 1
var
NoAuxiliar, NoASerExcluido, NoAnterior: PApontador;
begin
if (PrimeiroNo.Proximo = nil) or (PrimeiroNo.Valor = ValorASerExcluido) then
begin
NoAuxiliar:= PrimeiroNo;
PrimeiroNo:= PrimeiroNo.Proximo;
Dispose( NoAuxiliar );
end else
continua
Excluir item na lista – Parte 2
begin
NoAuxiliar:= PrimeiroNo;
while ( NoAuxiliar.Proximo <> nil ) do
begin
if ( NoAuxiliar.Proximo.Valor = ValorASerExcluido ) then
begin
NoAnterior:= NoAuxiliar; // pega o item anterio
NoASerExcluido := NoAuxiliar.Proximo
NoAnterior.Proximo:= NoASerExcluido.Proximo;
Exit();
end;
NoAuxiliar:= NoAuxiliar.Proximo;
Percorrer itens na lista
var
NoAuxiliar: PApontador;
begin
NoAuxiliar:= PrimeiroNo;
while ( NoAuxiliar <> nil ) do
begin
ShowMessage( NoAuxiliar.Valor );
NoAuxiliar:= NoAuxiliar.Proximo;
end;
end;
Liberar nós alocados
var
NoAuxiliar: PApontador;
begin
NoAuxiliar:= PrimeiroNo;
while ( NoAuxiliar <> nil) do
begin
Dispose( NoAuxiliar );
NoAuxiliar:= NoAuxiliar.Proximo;
end;
Observações
• Para identificar o final de uma lista encadeada simples verificamos se
o ponteiro tem o valor nil
• Sempre quanto efetuarmos operações de inclusão ou exclusão de nós
devemos nos certificar de que o ponteiro do nó esteja sendo
preenchido corretamente
Prática
download do
• Mostrar os exemplos
implementados no programa
DisplayPointers
Exercícios
Download : aula03 – exercícios
Download

Slides - Estrutura de Dados II