Alocacao Dinamica e Listas Lineares Encadeadas - Algoritmos de Alta Performance

1 Alocação Dinâmica Introdução à Lista Linear Encadeada Algoritmos de Alta Performance PROFa PATRÍCIA MAGNA profpatriciamagnafiapcombr 2 Definições sobre Alocação Dinâmica Algoritmos de Alta Performance Profa Patrícia Magna A alocação dinâmica significa armazenar mais um dado alocando ou obtendo uma região de memória onde este novo dado deve ser armazenado dinamicamente ou seja enquanto o programa está sendo executado Portanto deve ser utilizada quando não se conhece de antemão o número de elementos que uma estrutura deverá ter para armazenar dados de entrada de um programa O número máximo de elementos fica apenas restrito a disponibilidade de memória memória RAM O espaço de memória disponível para ser utilizado pelo programa em execução é chamado de heap 3 Regiões de Memória e seu Funcionamento Algoritmos de Alta Performance Prof Patrícia Magna Memória RAM variáveis locais media SP media 25 idade3 20 idade2 15 idade1 BP BP base pointer SP stack pointer variáveis locais main Para entender o uso e os nomes das regiões de memória RAM vamos usar um programa que tem 4 variáveis locais da função main e chama a função mediaIdades que calcula a média de 3 valores de idades passados como parâmetros retornando o valor da média 4 Regiões de Memória e seu Funcionamento Invocando um método Algoritmos de Alta Performance Prof Patrícia Magna STACK Pilha Memória RAM variáveis locais media SP m BP endereço retorno main mediaIdades 25 i3 argumentos de mediaIdades 20 i2 15 i1 media 25 idade3 20 idade2 15 idade1 BP base pointer SP stack pointer variáveis locais main Antes de chamar a função mediaIdades a função main copia as 3 valores de idades para a região de memória conhecida como pilha parâmetros deixa reservado espaço para retornar o valor da média e precisa também empilhar o ponto de retorno na função main quando a função mediaIdades for concluída 5 Regiões de Memória e seu Funcionamento Invocando um método Algoritmos de Alta Performance Prof Patrícia Magna STACK Pilha Memória RAM variáveis locais media 20 m endereço retorno main 20 mediaIdades 25 i3 argumentos de mediaIdades 20 i2 SP 15 i1 20 media 25 idade3 20 idade2 15 idade1 BP BP base pointer SP stack pointer variáveis locais main 6 Regiões de Memória e seu Funcionamento Algoritmos de Alta Performance Profa Patrícia Magna Memória RAM 3 STACK 26 SP endereço de retorno 16 media idade3 idade2 idade1 BP ocupado livre notas3 notas2 HEAP notas1 notas0 variáveis locais main Códigos de Alta Performance P rof Patrícia Magna 7 Heap A região de memória conhecida como heap é apenas uma coleção de bytes que não possui uma regra rígida de ocupação Cada byte tem marcado pelo gerenciador da memória heap se está ocupado ou seja já foi alocado para armazenar algum dado do programa ou se está livre o pode ser usado para armazenar um dado alocado dinamicamente Quando for necessário alocar reservar espaço para um dado é passado para o gerenciador da memória heap o número de bytes necessários por exemplo se for um valor inteiro este ocupará 4 bytes Cada solicitação de área para alocação dinâmica reserva bytes em endereços consecutivos 8 Lista Encadeada Introdução Executando o programa podemos ver que são apresentados na tela de saída os localizadores dos objetos na heap e não seu conteúdos public static class Elemento int idade public static void mainString args Scanner le new ScannerSystemin Elemento p1 new Elemento Elemento p2 new Elemento Elemento p3 new Elemento SystemoutprintlnInforme idades de 3 pessoas SystemoutprintPessoa 1 p1idade lenextInt SystemoutprintPessoa 2 p2idade lenextInt SystemoutprintPessoa 3 p3idade lenextInt Systemoutprintlnp1 Systemoutprintlnp2 Systemoutprintlnp3 leclose 9 Lista Encadeada Introdução Agora sim são apresentados na tela de saída os conteúdos public static class Elemento int idade public static void mainString args Scanner le new ScannerSystemin Elemento p1 new Elemento Elemento p2 new Elemento Elemento p3 new Elemento SystemoutprintlnInforme idades de 3 pessoas SystemoutprintPessoa 1 p1idade lenextInt SystemoutprintPessoa 2 p2idade lenextInt SystemoutprintPessoa 3 p3idade lenextInt Systemoutprintlnp1idade Systemoutprintlnp2idade Systemoutprintlnp3idade leclose 10 Definição de Listas Lineares Encadeadas Algoritmos de Alta Performance Prof Patrícia Magna Recordando Uma lista linear é uma coleção de elementos ordenados O conceito de lista linear especifica que é uma estrutura dinâmica caracterizada por uma seqüência ordenada de elementos Quando elementos de uma lista linear são alocados na memória principal de forma dinâmica durante a execução do programa essas listas são conhecidas como sendo listas encadeadas ou também listas ligadas E0 E1 En1 11 Lista Encadeada Introdução Algoritmos de Alta Performance Prof Patrícia Magna Podemos observar que Objetos são instanciados sem nenhuma ordem dependendo apenas de ser encontrada região de memória livre na heap Como um dos objetivos de se usar alocação dinâmica é não ter que definir antes a quantidade de elementos não faz sentido ter uma referência para cada objeto instanciado se não se quer decidir antes quantos elementos existirão na lista linear public static class Elemento int idade public static void mainString args Scanner le new ScannerSystemin Elemento p1 new Elemento Elemento p2 new Elemento Elemento p3 new Elemento SystemoutprintlnInforme idades de 3 pessoas SystemoutprintPessoa 1 p1idade lenextInt SystemoutprintPessoa 2 p2idade lenextInt SystemoutprintPessoa 3 p3idade lenextInt leclose 12 Lista Linear Encadeada Para que se transforme em uma lista linear é necessário que cada elemento tenha a indicação ponteiro de onde se encontra o elemento que é o seu sucessor Para que isto possa acontecer cada elemento deve se tornar Portanto chamaremos de nó cada elemento da lista Algoritmos de Alta Performance Prof Patrícia Magna 13 Alunos espalhados na sala que vão ser atendidos na ordem em que chegaram Primeiro a ser atendido Não tem mais ninguém depois de mim Primeiro a ser atendido 14 Representação de Lista Linear Encadeada Supondo a criação de uma lista linear encadeada formada por 3 elementos cada NÓ precisa do Campo para armazenar o valor do elemento v Campo para referenciar ou apontar para o NÓ sucessor 15 Representação de Lista Linear Encadeada A forma mais comum é Esse tipo de implementação de listas linear é chamada de LISTA LINEAR ENCADEADA 16 Declaração de um Nó Nodo nó dado tipodoelemento da lista prox referência para próximo nó O prox é uma referência para outro nó ou seja para um outro objeto nó Sendo assim a declaração é recursiva Códigos de Alta Performance P rof Patrícia Magna 17 Criando nossa primeira lista encadeada public static class NO int dado NO prox public static void mainString args Scanner le new ScannerSystemin NO p1 new NO NO p2 new NO NO p3 new NO SystemoutprintNO localizado em p1 Informe dado do 1o elemento p1dado lenextInt p1prox p2 SystemoutprintNO localizado em p2 Informe dado do 2o elemento p2dado lenextInt p2prox p3 SystemoutprintNO localizado em p3 Informe dado do 3o elemento p3dado lenextInt p3prox null SystemoutprintlnNó com dado p1dado tem como sucessor NO localizado p1prox SystemoutprintlnNó com dado p2dado tem como sucessor NO localizado p2prox SystemoutprintlnNó com dado p3dado tem como sucessor NO localizado p3prox leclose 18 Exemplo Encadeamento de Nós Elementos Algoritmos de Alta Performance Prof Patrícia Magna public class Exemplo1 public static class NO int dado NO prox public static void mainString args Scanner le new ScannerSystemin NO lista new NO Primeiro NÓ SystemoutprintInforme dado listadado lenextInt listaprox null Segundo NÓ NO novo new NO SystemoutprintInforme dado novodado lenextInt novoprox null Conectando os 2 NÓS listaprox novo leclose 19 Exercícios de Criação e Apresentação de Lista Linear Encadeada 1 Como modificar o programa anterior para gerar essa lista Vamos construir juntos no projeto ListaEncadeada 3 Como apresentar os valores armazenados na lista sem retira los 2 Como modificar o programa anterior para gerar essa lista 20 Exercícios de fixação Algoritmos de Alta Performance Prof Patrícia Magna 1 Com suas palavras explique a diferença entre a memória conhecida como stack pilha e a heap 2 Por que cada elemento de uma lista linear encadeada é chamado de nó 21 Referências Bibliográficas Algoritmos de Alta Performance Prof Patrícia Magna ASCÊNCIO AFG ARAUJO GS Estruturas de Dados Algoritmos Análise de Complexidade e Implementações em JAVA e CC São Paulo EdPearson Prentice Hall 2010 PEREIRA SL Estruturas de Dados Fundamentais Conceitos e Aplicações São Paulo Ed Érica 1996 TENEMBAUM AM et al Estruturas de Dados usando C Makron Books Ltda 1995 DEITEL P J Deitel HM Java como programar 8ª edição São Paulo EdPearson Prentice Hall 2010 22 Copyright 2024 Profa Patrícia Magna Todos direitos reservados Reprodução ou divulgação total ou parcial deste documento é expressamente proibido sem o consentimento formal por escrito dos professores Códigos de Alta Performance Prof Patrícia Magna