Estruturas de Dados Lineares - Listas com Armazenamento Sequencial

ESTRUTURAS DE DADOS LISTAS COM ARMAZ SEQUENCIAL Prof Ms Peter Jandl Junior ADS FATEC Jundiaí ESTRUTURAS DE DADOS LINEARES Estruturas de dados de relativa simplicidade capazes de auxiliar na resolução de inúmeros tipos de problemas 362022 C 20132022 JANDL 2 ESTRUTURAS DE DADOS LINEARES 362022 C 20132022 JANDL 3 São aquelas onde a organização lógica de seus elementos é feita de maneira que Todo elemento tem um vizinho anterior e outro vizinho posterior Exceto o primeiro que não tem anterior e o último que não tem posterior Permite que um único trajeto de navegação entre o primeiro e o último elemento percorra todos os demais elementos existentes ESTRUTURAS DE DADOS LINEARES O armazenamento sequencial provido por arrays é bastante conveniente para armazenar elementos de estruturas de dados lineares devido sua forma de organização comum Estruturas de dados lineares comuns Pilhas Filas Listas 362022 C 20132022 JANDL 4 O armazenamento sequencial é UMA das maneiras possíveis da organização INTERNA de uma estrutura de dados linear LISTAS A estrutura de dados de tipo linear mais flexível que existe 362022 C 20132022 JANDL 5 LISTAS É uma estrutura de dados onde seus elementos são colocados em sequência mas não existe uma ordenação implícita A entrada pode ser realizada em qualquer ponto ie nos extremos início e fim e entre elementos existentes A saída remoção também pode ser realizada em qualquer ponto ie nos extremos início e fim ou elementos intermediário Esta estrutura de dados é semelhante a uma lista de itens ou objetos sem qualquer ordenação própria 362022 C 20132022 JANDL 6 A ideia de Lista também é um TAD Tipo Abstrato de Dados LISTASOPERAÇÕES Operações comuns sobre uma lista Adição de elemento em qualquer posição Remoção de elemento em qualquer posição Contagem dos elementos contidos na lista Indicação de lista vazia Listagem dos elementos contidos na lista Consulta sem remoção de elemento presente em qualquer posição Tais operações são independentes do tipo de elemento armazenado na lista 362022 C 20132022 JANDL 7 Tais operações constituem a interface da estrutura de dados LISTACOM ARMAZENAMENTO SEQUENCIAL Lista também pode ser construída com array Vantagens solução simples e versátil Desvantagens elementos do mesmo tipo tamanho limitado e movimentação de elementos na adição e remoção 362022 C 20132022 JANDL 8 Lista Vazia 5 Lista com um elemento 73 5 Lista com dois elems 73 8 5 Lista com três elems 0 8 5 Lista com três elems 0 73 8 5 Lista com quatro elems LISTAREVISÃO DO PROJETO Até o momento as implementações de Pilha e de Fila foram orientadas para um tipo específico de conteúdo valores inteiros Embora úteis tais implementações são limitadas devido a restrição do seu conteúdo A construção de outras implementações para conteúdos de tipos específicos é uma solução possível mas trabalhosa Será necessária uma implementação distinta para cada tipo de conteúdo 362022 C 20132022 JANDL 9 A CLASSE JAVALANGOBJECT A raiz da hierarquia de classe do Java 362022 C 20132022 JANDL 10 JAVALANGOBJECT Classe que dá origem a hierarquia de classes do Java Toda e qualquer classe é direta ou indiretamente um descendente de Object Assim toda classe é uma subclasse de Object Isto possibilita tratar qualquer objeto do Java como um Object polimorfismo Permite criar estruturas de dados capazes de conter elementos de qualquer tipo 362022 C 20132022 JANDL 11 Bom porque é adequado a todas as situações Ruim quando se deseja garantia de conteúdo de tipo único LISTASOPERAÇÕES As operações de uma lista com uso da classe Object do Java 362022 C 20132022 JANDL 12 LISTASOPERAÇÕES Padronização das operações comuns adicionarObject adição de elemento na última posição inserirint Object adição de elemento na posição dada removerint remoção de elemento da posição dada comprimento contagem dos elementos contidos na lista vazia indicação de lista vazia elementoint consulta sem remoção do elemento na posição p cheia indicação de lista cheia capacidade quantidade máxima de elementos toString listagem dos elementos contidos na lista 362022 C 20132022 JANDL 13 Tais operações constituem a interface da estrutura de dados LISTAREPRESENTAÇÃO UML 362022 C 20132022 JANDL 14 Lista Listaint adicionarObject void inserirint Object void removerint Object elementoint Object capacidadeint comprimentoint cheia boolean vazia boolean toString String v Object fim int Lista Nome da classe CamposAtributos da classe OperaçõesMétodos da classe Legenda público privado protegido LISTA COM ARMAZENAMENTO SEQUENCIAL Implementação de lista com elementos genéricos ie javalangObject que é a raiz da hierarquia de classes do Java 362022 C 20132022 JANDL 15 LISTAIMPLEMENTAÇÃO COM ARMAZ SEQUENCIAL public class Lista protected Object v protected int fim 0 public Lista int tam v new Object tam public Lista this4 public int capacidade return vlength public int comprimento return fim public String toString StringBuilder sb new StringBuilder for int i 0 i fim i sbappendvi sbappend sbappend return sbtoString 362022 C 20132022 JANDL 16 LISTAIMPLEMENTAÇÃO COM ARMAZ SEQUENCIAL public void inserirint pos Object elem if pos 0 pos fim throw new RuntimeExceptionpospos inválida else if fim capacidade throw new RuntimeExceptionlista cheia fim forint ifim1 ipos i vi vi1 vpos elem 362022 C 20132022 JANDL 17 LISTAIMPLEMENTAÇÃO COM ARMAZ SEQUENCIAL public void adicionarObject elem utiliza método inserir existente inserirfim elem adiçãoinserção no fim public boolean vazia return fim 0 public boolean cheia return fim vlength public Object elemento int pos if pos 0 pos fim throw new RuntimeException pos pos inválida return vpos 362022 C 20132022 JANDL 18 LISTAIMPLEMENTAÇÃO COM ARMAZENAMENTO SEQUENCIAL public Object remover int pos if vazia throw new RuntimeExceptionlista vazia Object aux elementopos for int i pos 1 i fim i vi 1 vi fim return aux 362022 C 20132022 JANDL 19 USO DA CLASSE LISTA Para declarar uma lista de objetos Lista lista Para instanciar uma lista de objetos com tamanho padrão lista new Lista Para declarar e instanciar com outro tamanho Lista lista new Lista 22 362022 C 20132022 JANDL 20 Estas operações são idênticas as estruturas de dados pilha e fila vistas anteriormente USO DA CLASSE LISTA Para saber quantos elementos existem na lista int quant listacomprimento Para conhecer a capacidade da lista int max listacapacidade Para testar se lista vazia if listavazia lista está vazia else lista não está vazia Para testar se lista cheia if listacheia lista está cheia else lista não está cheia 362022 C 20132022 JANDL 21 Estas operações são idênticas as estruturas de dados pilha e fila vistas anteriormente USO DA CLASSE LISTA Para adicionar um elemento na lista int elem 10 listaadicionarelem na inserção de tipos primitivos ocorre o autoboxing implícito Para retirar um elemento da lista Object obj listaremover0 coerção é necessária para reestabelecer o tipo original do objeto inserido int elem Integerobj Para obter sem remover um elemento da lista int elem Integer filaelemento0 o primeiro inserido início note o uso da coerção Para conhecer elemento que está no fim da lista sem removêlo Object final listaelemento listacomprimento1 362022 C 20132022 JANDL 22 As operações de manipulação são idênticas mas podem requerer coerção LISTAEXEMPLOS SIMPLES Exemplos simples do uso da Lista de objetos e de suas operações 362022 C 20132022 JANDL 23 LISTATESTALISTA01 public class TestaLista01 public static void mainString a Lista lista new Lista5 SystemoutprintlnlistatoString listacapacidade int elem 0 whilelistacheia listaadicionarelem Systemoutprintlnlista whilelistavazia elem Integer listaremover0 Systemoutprintlnlista elem 362022 C 20132022 JANDL 24 LISTATESTALISTA02 public class TestaLista02 private static int MAX 100 private static int TAM 10 public static void mainString a Lista lista new ListaTAM Systemoutprintlnlista listacapacidade forint i0 ilistacapacidade i int pos intMathrandomlistacomprimento int aux intMathrandomMAX listainserirpos aux Systemoutprintlnaux pos lista 362022 C 20132022 JANDL 25 LISTATESTALISTA02 Systemoutprintlnlista while listavazia int pos intMathrandomlistacomprimento Object aux listaremoverpos Systemoutprintlnlista aux pos 362022 C 20132022 JANDL 26 LISTAAPLICAÇÃO DE UM TAD Observe que nos programas TestaLista01 e TestaLista02 foram utilizadas listas por meio de classes que implementam um TAD Com isso As regras de utilização da lista foram observadas sem que o programador tenha ciência ou se esforce para tal Não é possível burlar as regras de utilização da lista garantindo consistência e robustez dos programas As técnicas de implementação da lista não são expostas e portanto não são conhecidas no programa Apenas os conceitos abstratos de lista são conhecidos 362022 C 20132022 JANDL 27 EXERCÍCIOS 1 Escreva um programa que utilize uma lista para armazenar 10 nomes dados pelo usuário apresentandoos após sua entrada 2 Escreva um programa que armazene até 10 valores reais dados pelo usuário positivos e negativos em listas separadas Um valor 0 zero finaliza a sequência Exiba os valores após sua entrada Nestes exercícios utilize a classe Lista dada 362022 C 20132022 JANDL 28 EXERCÍCIOS 3 Escreva um programa que armazene em uma lista para 12 valores inteiros dados pelo usuário Depois da entrada exibir os valores remover todos os elementos pares existentes e exibir novamente a lista 4 Modifique o programa 1 de maneira que armazene Aluno como elemento da lista ou seja um conjunto contendo nome sobrenome RA e curso Nestes exercícios utilize a classe Lista dada Uma classe auxiliar pode ser construída para conter um conjunto de dados qualquer 362022 C 20132022 JANDL 29