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