Estruturas de Dados - Revisão de Conceitos e Exercícios com Arrays em Java

1 Estruturas de Dados Professor Gerson Risso httpsbitlyTADS3N20222 Material de apoio httpsbitlyalgoritmossenac Downloads Email gersonrissospsenacbr Duas avaliações e uma substitutiva Média das avaliações 70 Média ADO 30 Datas das avaliações P1 071022 P2 181122 DevolutivaSubstitutiva 251122 Aula 1 Apresentação e revisão de conteúdoconceitos Slides Aula 1 1 2 Exercício Elabore um algoritmo que insira valores aleatórios reais de simples precisão em um array bidimensional quadrado de ordem igual a 5 Exiba apenas os valores da diagonal principal import javautilArrays import javautilRandom public class ExercicioMat1 public static void mainString args float m new float55 Random rd new Random for int i 0 i mlength i for int j 0 j m0length j mij rdnextFloat10 Exibir a matriz SystemoutprintlnMatriz SystemoutprintlnArraysdeepToStringmreplace SystemoutprintlnDiagonal principal for int i 0 i mlength i Systemoutprintlnm i i mii Exemplo 1 import javautilArrays 2 3 import javautilRandom public class Exercicio1 private static final int MAX10 public static void mainString args int vReferência v new intMAXAcolando o array na memória int vnew int50 inserirv mostrarv public static void inserirint v Random rd new Random int vi 5 int vf 105 for int i 0 i vlength i vi vi rdnextIntvf vi public static void mostrarint v SystemoutprintlnArraystoStringvreplace replace replace Exemplo 2 import javautilArrays import javautilRandom public class RevisaoExemplo2 public static void mainString args float m new float34 3 4 inserirm exibirm public static void inserirfloat m Random rd new Random int vi 10 int vf 110 for int i 0 i mlength i for int j 0 j m0length j mij vi rdnextFloat vf vi public static void exibirfloat m for int i 0 i mlength i for int j 0 j m0length j Systemoutprintmij Systemoutprintln for aprimorado for float i m for float j i Systemoutprintj Systemoutprintln SystemoutprintlnArraysdeepToStringmreplace Exemplo 3 Array de objetos redimensionável public class UsaArrayAluno public static void mainString args 4 5 Aluno aluno1 new AlunoGersonCurso123 Aluno aluno2 new AlunoXaropadaBSI938 Aluno aluno3 new AlunoFulanoTADS321 Aluno aluno4 new AlunoFulanaBSI451 Aluno aluno5 new AlunoXaropada2TADS959 Aluno aluno6 new AlunoRaulTADS874 Aluno aluno7 new AlunoBiaTADS321 Aluno aluno8 new AlunoGuilhermeTADS222 Aluno aluno9 new AlunoVitorTADS983 Metodosinseriraluno1 Metodosinseriraluno2 Metodosinseriraluno3 Metodosinseriraluno4 Metodosinseriraluno5 Metodosinseriraluno6 Metodosinseriraluno7 Metodosinseriraluno8 Metodosinseriraluno9 Metodosexibir public class Aluno private String nome private int id private String curso public Aluno public AlunoString nomeString cursoint id thisnomenome thiscursocurso thisidid public void setNomeString nome thisnome nome 5 6 public String getNome return thisnome public int getId return id public void setIdint id thisid id public String getCurso return curso public void setCursoString curso thiscurso curso Override public String toString return Nomethisnome Curso thiscurso IDthisid public class Metodos private static Aluno listanew Aluno4 private static int n0 public static void inserirAluno aluno iflistalengthn listaalocarNovoArray listanaluno n public static void exibir forint i0ini 6 7 Systemoutprintlnlistai private static Aluno alocarNovoArray Aluno novonew Alunolistalength4 Systemarraycopylista 0 novo 0 listalength return novo Exercícios 1 Um array unidimensional do tipo inteiro e tamanho igual a 100 deve armazenar valores aleatórios A saída deve imprimir o maior e o menor valor armazenado 2 Um array unidimensional armazena vinte valores inteiros A saída deve mostrar todos os valores pares armazenados 3 Considere uma matriz bidimensional de ordem igual a cinco com valores reais de simples precisão Leia a matriz via teclado e na saída imprima todos os valores da diagonal principal Métodos de ordenação Apresentação Métodos de ordenação Uma das tarefas mais importantes em manipulação de dados é a ordenação de um conjunto de dados Pois organizao e torna a pesquisa mais eficiente isto é mais rápida Há dezenas de métodos de ordenação cada um com suas 7 8 peculiaridades e aplicações por vezes específicas Exemplos de métodos de ordenação Bubble sort método bolha Selection sort Insertion sort Merge sort Quick sort Radix sort Heapsort O mais simples e também o menos eficiente é o método bolha Profissionalmente ele não é utilizado no entanto é muito útil para apresentar uma forma trivial de ordenação de dados já que é fácil de ser implementado Bubble sort Exemplo 0 1 2 3 4 2 6 8 7 1 Varreduras no vetor Para o vetor do exemplo haverá quatro varreduras no vetor a fim de garantir que todos os dados estejam ordenados 2 6 7 1 8 2 6 1 7 8 2 1 6 7 8 1 2 6 7 8 8 9 Em cada varredura podemos garantir que apenas um elemento é ordenado Para ilustrar httpswwwyoutubecomwatchvlyZQPjUT5B4 public class MetodoBolha public static void mainString args Metodosinserir Metodosexibir Systemoutprintln Metodosbolha Metodosexibir import javautilRandom public class Metodos private static int v new int500000 private static Random random new Random public static void inserir for int i 0 i vlength i vi 1 randomnextInt101 9 10 public static void bolha int temp for int j 0 j vlength 1 j Varreduras for int i 0 i vlength 1 j i Comparações if vi vi 1 temp vi vi vi 1 vi 1 temp public static void exibir for int i 0 i vlength i Systemoutprintvi Selection Sort O método de seleção tem desempenho melhor do que o método bolha porque reduz o número de trocas embora em cada passagem o número de comparações é igual ao método bolha No caso do método por seleção os dados ordenados ficam à esquerda porque a troca ocorre entre o elemento mais à esquerda com o elemento de menor valor na passagem Exemplo 0 1 2 3 4 4 16 8 2 1 Varreduras no vetor 1 16 8 2 4 10 11 1 2 8 16 4 1 2 4 16 8 1 2 4 8 16 Os valores na cor azul indicam os elementos já ordenados e os valores em vermelho são aqueles envolvidos nas trocas em cada passagem Para ilustrar httpswwwyoutubecomwatchvNs4TPTC8whw Código completo do Selection Sort public class SelectionSort public static void selectionSortint v int temp for int j 0 j vlength 1 j Varreduras int menorjíndice forint ij1ivlengthiComparações ifvmenorvi menori Troca tempvmenor vmenorvj vjtemp public static void exibirint v forint i0ivlengthi Systemoutprintvi Systemoutprintln 11 12 public class UsaSelectionSort public static void mainString args int v10099877512 SelectionSortselectionSortv SelectionSortexibirv Exercício Adicione uma classe Trabalhador com os atributos nome salario e id Armazene em um array de objetos e ordeneo pelo valor de id Insertion Sort Método de Inserção Comparando o método de ordenação por inserção com os demais métodos vistos anteriormente podemos afirmar que na média ele tem desempenho superior Embora não seja elementar como os anteriores esse método utiliza recursos fundamentais de programação O método consiste em tomar o segundo valor de um conjunto de dados comparálo com o valor à esquerda e caso o primeiro valor do conjunto seja maior ele deverá ser deslocado à direita E portanto o segundo valor é inserido na posição correta Assim temse uma parte do conjunto com dois elementos já ordenada E assim sucessivamente até a ordenação de todo o conjunto Array não ordenado 12 13 0 1 2 3 4 23 3 5 67 2 Ordenação passo a passo 0 1 2 3 4 3 23 5 67 2 3 5 23 67 2 3 5 23 67 2 3 2 5 23 67 httpswwwyoutubecomwatchvmTNC0ERoZI httpswwwyoutubecomwatchvROalU379l3U Simulação Insertion sort import javautilArrays import javautilRandom public class InsertionSort public static void mainString args int v new int110000 popularArrayv long t1SystemcurrentTimeMillis insertionSortv long t2SystemcurrentTimeMillis long tft2t1 SystemoutprintlnArraystoStringv SystemoutprintlnTempo tf ms Ordena um array pelo método da inserção 13 14 param v int public static void insertionSortint v for int i 1 i vlength i int temp vi int j i while j 0 vj 1 temp vj vj 1 j jj1 vj temp public static void popularArrayint v Random rdnew Random forint i0ivlengthi virdnextInt5000 Exercícios Exercícios Exercícios 1 Gerar números aleatórios armazenar no array e ordenar pelo merge sort 2 Dada a lista mamão banana Maçã AbacateperaLimão faça a ordenação pelo Merger sort Observe que alguns nomes estão com letra maiúscula mantenha assim Responda a questão A saída foi o que você esperava 3 No projeto ArrayObjetos ordene Merge sort os objetos pelo atributo nome 14 15 4 Escreva um método de ordenação insertion sort para o projeto desenvolvido em aula Array de objetos está no BB Esse método deverá ordenar os objetos do array pelo nome da pessoa a Se você não tiver o projeto baixeo do BB b Não utilize Collections escreva todos os recursos que necessitar 1 Elabore um projeto Java que gere números reais float aleatórios armazeneos em um array e ordeneo pelo insertion sort 2 Ordene um array de String pelo método insertion sort 3 Escreva uma classe Pet com os atributos nome idade e raça Utilize o método insertion sort para ordenar pela idade os objetos da classe definida 4 Meça o tempo para ordenar um array pelo insertion sort Faça isso para os outros dois métodos de ordenação Qual é a sua conclusão Quick sort Complexidade On log n Método criado por Tony Hoare cientista da computação para resolver o problema de tradução de palavras para a criação de dicionário inglêsrusso Características Naturalmente recursivo Utiliza o conceito Dividir para Conquistar Adequado para grandes quantidades de dados Desempenho caso médio Onlogn Não utiliza estrutura de dados auxiliar e portanto menos consumo de memória No pior caso com um conjunto quase ordenado o desempenho é On² Semelhante aos métodos de ordenação Selection sort insertion sort O método de ordenação quick sort aplica a estratégia dividir para conquistar assim como o merge sort Essa estratégia consiste em dividir uma instância em instância menores e assim sucessivamente até atingir um caso trivial e daí recompor as partes para a solução final Animações de métodos de ordenação 15 16 Demonstração do método quick sort Pivô de um vetor O pivô é um elemento importante no processo de ordenação por partição quick sort Podemos considerar a escolha do pivô de várias formas O valor do primeiro índice o valor do índice central um valor médio etc Porém no exemplo a seguir e no projeto prático escolhemos o último elemento do array como pivô Pivotar um vetor Significado Fazer girar em torno de um pivô Na simulação a seguir o vetor será subdividido em dois conjuntos À esquerda com valores menores que o pivô e à direita com valores maiores que o pivô Entre eles estará o pivô na posição correta em relação aos demais dados do conjunto 0 1 2 3 4 5 6 7 8 9 43 90 64 11 96 29 77 1 55 39 Imagine duas setas uma à esquerda procurando os valores maiores do que o pivô outra à direita procurando os valores menores do que o pivô 0 1 2 3 4 5 6 7 8 9 43 90 64 11 96 29 77 1 55 39 Os valores 43 e 1 serão trocados 0 1 2 3 4 5 6 7 8 9 1 90 64 11 96 29 77 43 55 39 0 1 2 3 4 5 6 7 8 9 1 90 64 11 96 29 77 43 55 39 Os valores 90 e 29 serão trocados 16 17 0 1 2 3 4 5 6 7 8 9 1 29 64 11 96 90 77 43 55 39 0 1 2 3 4 5 6 7 8 9 1 29 64 11 96 90 77 43 55 39 Os valores 64 e 11 serão trocados 0 1 2 3 4 5 6 7 8 9 1 29 11 64 96 90 77 43 55 39 Ao final desse processo temos o array subdividido Porém o pivô ainda não está na posição correta A fim de posicionálo trocamos as posições do pivô e do valor 64 índice 3 0 1 2 3 4 5 6 7 8 9 1 29 11 39 96 90 77 43 55 64 Veja que os valores à esquerda e à direita não estão ordenados Portanto devemos repetir o processo para cada uma das partes Projeto MetodoQuick O projeto na sua versão completa está disponível no Blackboard A seguir vamos apresentar os métodos quickSort e particao A classe principal Aplicação do método Quick Sort Ordenação de array com valores aleatórios author Gerson public class UsaQuick private static final int MAX5 public static void mainString args float v113324553 Systemoutprintln Array não ordenado MetodosQuickpopularv 17 18 MetodosQuickexibirv Systemoutprintln Array ordenado MetodosQuickquickSort0 vlength1 v MetodosQuickexibirv A classe MetodosQuick Definição do método de inserção Definição do método Quick Sort Definição das funções básicas author Gerson import javatextDecimalFormat public class MetodosQuick Insere valores aleatórios no array Os valores são sorteados na faixa de 0 a 10000 param v float public static void popularfloat v for int i 0 i vlength i vi float Mathrandom 10000 Método de ordenação Quick sort Ordena o array param e int índice inicial param d int índice final param a float identificador do array 18 19 public static void quickSortint e int d float a int i if d e i particaoeda Particionando o vetor quickSorte i 1a quickSorti 1 da Realiza a partição do array com base no pivô param e int índice inicial param d int índice final param a float identificador do array return int private static int particaoint e int dfloat a float pivo aux int i j pivo ad i e 1 j d do do i i 1 Procura o maior while ai pivo i d do j j 1 Procura o menor while aj pivo j 0 Aqui realiza a troca de valores aux ai ai aj aj aux while j i colocando o pivo ad em seu lugar aj ai ai ad ad aux return i 19 20 Exibe o conteúdo do array param v int public static void exibirfloat v DecimalFormat nfnew DecimalFormat00 for int i 0 i vlength i Systemoutprintnfformatvi Exercícios 1 Responda as questões a Qual método de ordenação gasta mais tempo para classificar um conjunto de dados b Qual método de ordenação gasta menos tempo para classificar o conjunto de dados c Qual é a chamada para executar o método quick sort Escreva a instrução d Como é escolhido o elemento pivô e Porque o método particao está como private 2 Elabore um projeto em Java que leia um vetor de caracteres ordeneo através do método Quick Sort e exiba o vetor ordenado Faça testes com as seguintes entradas a AbsagGBkL b 1 w W 3 2 R r T 8 3 Simule passo a passo a ordenação do array quick sort até o momento da primeira partição 0 1 2 3 4 5 6 7 8 9 10 12 23 3 34 56 15 44 78 37 89 17 4 No método quickSort 20 21 public static void quickSortint e int d float a int i if d e i particaoeda Particionando o vetor quickSorte i 1a quickSorti 1 da Como funciona o método Em que momento a chamada quickSorti1da será executada Algoritmo de intercalação import javautilArrays public class ExemploIntercalacao public static void mainString args int a1215213355123 int b151735656872 int cintercalarArraysa b SystemoutprintlnArraystoStringc public static int intercalarArraysint aint b int cnew intalengthblength int i0j0k0 whileialength jblength ifaibj ckai k i else ckbj k j whileialength ckai 21 22 i k whilejblength ckbj j k return c Método de Ordenação Merge Sort A ordenação por intercalação utiliza o conceito de dividir para conquistar recursivamente separa um conjunto de dados original em subconjuntos até o caso base de um subconjunto com um elemento A partir desse ponto os subconjuntos são intercalados para compor o vetor ordenado Características Naturalmente recursivo Utiliza o conceito Dividir para Conquistar Adequado para grandes quantidades de dados Desempenho Onlogn Utiliza estrutura de dados auxiliar portanto em implementações que consomem muita memória pode afetar o desempenho do sistema Conforme citado por Paulo Feofiloff Algoritmos em Linguagem C o método não tem pior caso Já que o desempenho é Onlogn A grande desvantagem do método merge é portanto o alto consumo de memória Igualmente ao método quick o merge consome memória com recursividade e também com um array auxiliar utilizado para intercalar os valores Exemplo de execução do método httpswwwyoutubecomwatchvXaqR3GNVoot13s 22 23 Implementação completa do método merge sort A classe UsaMetodoMerge import javautilArrays public class UsaMetodoMerge public static void mainString args int a 123563268331 Ordenacaoinserira OrdenacaomergeSort0 alength a SystemoutprintlnArraystoStringa A classe Ordenacao import javautilRandom public class Ordenacao public static void mergeSortint inicio int tamanho int v if inicio tamanho 1 int meio inicio tamanho 2 mergeSortinicio meio v mergeSortmeio tamanho v intercalarinicio meio tamanho v private static void intercalarint inicio int meio int tamanho int v int i j k int auxiliar new inttamanho inicio i inicio j meio k 0 while i meio j tamanho if vi vj auxiliark vi 23 24 k i else auxiliark vj k j while i meio auxiliark vi k i while j tamanho auxiliark vj k j for i inicio i tamanho i vi auxiliari inicio public static void inserirint a Random rd new Random for int i 0 i alength i ai rdnextInt500 1 Exercícios 1 Ordene pelo método quick sort um array de caracteres public class ExercicioOrdenacao1 public static void mainString args char agbwyopWKA QuickquickSort0alength1a Quickexibira 24 25 import javautilArrays public class Quick É um método recursivo que separa logicamente o array com relação ao valor retornado do método particao param e int é o primeiro índice param d int é o último índice param a char o array a ser ordenado public static void quickSortint e int d char a int i if d e i particaoeda Particionando o vetor quickSorte i 1a quickSorti 1 da Realiza a separação do array em duas partes segundo a referência do elemento pivô param e int é o primeiro índice param d int é o último índice param a char o array a ser ordenado return int é a posição do pivô private static int particaoint e int d char a char pivo aux int i j pivo ad i e 1 j d do do i i 1 25 26 Procura o maior while ai pivo i d do j j 1 Procura o menor while aj pivo j 0 Aqui realiza a troca de valores aux ai ai aj aj aux while j i colocando o pivo ad em seu lugar aj ai ai ad ad aux return i Exibir o conteúdo do array param a char é o array a ser exibido public static void exibirchar a SystemoutprintlnArraystoStringa Aprimorando a solução para gerar caracteres aleatórios public class ExercicioOrdenacao1 public static void mainString args char anew char20 Quickinserira QuickquickSort0alength1a Quickexibira Na classe Quick foi escrito o método inserir 26 27 Insere caracteres aleatórios no array param a char public static void inserirchar a Random rd new Random int vi 65 int vf 122 for int i 0 i alength i do ai char vi rdnextIntvf vi while ai 90 ai 97 2 Ordene pelo método merge sort um array de Strings nomes de pessoas public class ExercicioOrdenacao2 public static void mainString args String listaGerson Sandra Anna José Gaia Mel Ronda Tonica Mustafá MergemergeSort0 listalength lista Mergeexibirlista import javautilArrays public class Merge 27 28 public static void mergeSortint inicio int tamanho String v if inicio tamanho 1 int meio inicio tamanho 2 mergeSortinicio meio v mergeSortmeio tamanho v intercalarinicio meio tamanho v private static void intercalarint inicio int meio int tamanho String v int i j k String auxiliar new Stringtamanho inicio i inicio j meio k 0 while i meio j tamanho if vicompareTovj0 auxiliark vi k i else auxiliark vj k j while i meio auxiliark vi k i while j tamanho auxiliark vj k j for i inicio i tamanho i vi auxiliari inicio 28 29 public static void exibirString lista SystemoutprintlnArraystoStringlista 3 Declare uma classe Pet com os atributos nome String e idade int defina dois construtores métodos getterssetters e o toString Na classe principal crie um array de objetos insira alguns objetos e ordene pelo nome o array usando quickmerge public class Pet private String nome private int idade public Pet public PetString nomeint idade thisnomenome thisidadeidade return the nome public String getNome return nome param nome the nome to set public void setNomeString nome thisnome nome 29 30 return the idade public int getIdade return idade param idade the idade to set public void setIdadeint idade thisidade idade Override public String toString return Pet nome nome idade idade public class Merge private static Pet lista new Pet10 private static int n 0 public static void inserirPet pet listan pet n mergeSort0nlista public static void exibir forint i0ini Systemoutprintlnlistai public static void mergeSortint inicio int tamanho Pet v if inicio tamanho 1 int meio inicio tamanho 2 30 31 mergeSortinicio meio v mergeSortmeio tamanho v intercalarinicio meio tamanho v private static void intercalarint inicio int meio int tamanho Pet v int i j k Pet auxiliar new Pettamanho inicio i inicio j meio k 0 while i meio j tamanho if vigetNomecompareTovjgetNome 0 auxiliark vi k i else auxiliark vj k j while i meio auxiliark vi k i while j tamanho auxiliark vj k j for i inicio i tamanho i vi auxiliari inicio public class ExercicioOrdenacao3 31 32 public static void mainString args Pet pet1new PetGaia 4 Pet pet2new PetRonda 4 Pet pet3new PetMel 7 Pet pet4new PetTonica 8 Pet pet5new PetMustafá 6 Mergeinserirpet1 Mergeinserirpet2 Mergeinserirpet3 Mergeinserirpet4 Mergeinserirpet5 Mergeexibir Exemplos de pesquisa binária Exemplo 1 public class ExemploBuscaBinaria public static void mainString args int v 1 4 6 7 12 23 35 77Classificado SystemoutprintlnÍndicebinariav11 public static int binariaint v int b int vi 0 vf vlength 1 meio while vi vf meio vf vi 2 if b vmeio return meio else if b vmeio vf meio 1 else vi meio 1 return 1 32 33 Exemplo 2 public class Pessoa private String nome private int id public Pessoa public PessoaString nome int id thisnome nome thisid id public String getNome return nome public void setNomeString nome thisnome nome public int getId return id public void setIdint id thisid id Override public String toString return Pessoa nome nome id id public class Metodos 33 34 private static int n 0 private static Pessoa lista new Pessoa10 public static void inserirPessoa p listan p n private static void insertionSort for int i 1 i n i Pessoa temp listai int j i while j 0 listaj 1getId tempgetId listaj listaj 1 j jj1 listaj temp public static Pessoa pesquisaint b insertionSort return binariab private static Pessoa binariaint b int inicio 0 fim n 1 meio while inicio fim meio inicio fim 2 if b listameiogetId return listameio else if b listameiogetId inicio meio 1 else fim meio 1 return null public class ExemploBuscaBinaria 34 35 public static void mainString args Pessoa p1 new PessoaGerson 12 Pessoa p2 new PessoaAnna 1 Pessoa p3 new PessoaJosé 31 Pessoa p4 new PessoaSandra 67 Pessoa p5 new PessoaMaria 78 Metodosinserirp1 Metodosinserirp2 Metodosinserirp3 Metodosinserirp4 Metodosinserirp5 int id 780 Pessoa p Metodospesquisaid if p null Systemoutprintlnp else SystemoutprintlnPessoa não encontrada Aula 6 Desempenho de algoritmos Apresentação Aulas 78 Lista Simplesmente Encadeada 35 36 Figura 1 Figura 2 As Figuras 1 e 2 são representações para lista simplesmente encadeada Inserindo o primeiro elemento Inserindo o segundo elemento 36 37 public class UsaLista public static void mainString args Lista listanew Lista listainserirAnna listainserirGerson listainserirSandra listainserirMel listainserirRonda listaexibir public class Elemento private Object objeto private Elemento prox public ElementoObject objeto Elemento prox thisobjeto objeto thisprox prox public Object getObjeto return objeto public void setObjetoObject objeto thisobjeto objeto 37 38 public Elemento getProx return prox public void setProxElemento prox thisprox prox Override public String toString return Elemento objeto objeto prox prox public class Lista private Elemento inicionull atualaux public void inserirObject objeto ifinicionull inicionew Elementoobjetonull auxinicio else atualnew Elementoobjeto null auxsetProxatual auxatual public void exibir Elemento xinicio whilexnull SystemoutprintlnxgetObjeto xxgetProx Refatorando o projeto para definir uma classe interna public class Lista private Elemento inicio null atual aux public void inserirObject objeto if inicio null 38 39 inicio new Elementoobjeto null aux inicio else atual new Elementoobjeto null auxsetProxatual aux atual public void exibir Elemento x inicio while x null SystemoutprintlnxgetObjeto x xgetProx private class Elemento private Object objeto private Elemento prox public ElementoObject objeto Elemento prox thisobjeto objeto thisprox prox public Object getObjeto return objeto public void setObjetoObject objeto thisobjeto objeto public Elemento getProx return prox public void setProxElemento prox thisprox prox Override public String toString return Elemento objeto objeto prox prox 39 40 Exemplo passado em aula public class Carro private String modelo private int ano id private double preco public Carro public CarroString modelo int ano int id double preco thismodelo modelo thisano ano thisid id thispreco preco public String getModelo return modelo public void setModeloString modelo thismodelo modelo public int getAno return ano public void setAnoint ano thisano ano public double getPreco return preco public void setPrecodouble preco thispreco preco public int getId return id public void setIdint id 40 41 thisid id Override public String toString return Carro modelo modelo ano ano id id preco preco public class Lista private Elemento inicionullatualaux método de instância public void inserirObject objeto ifinicionull inicionew Elementoobjetonull auxinicio else atualnew Elementoobjetonull auxsetProxatualproxatual auxatual public void exibir Elemento xinicio whilexnull SystemoutprintlnxgetObjeto xxgetProx inner class Classe interna private class Elemento private Object objetoDados private Elemento prox public ElementoObject objeto Elemento prox thisobjeto objeto thisprox prox public Object getObjeto return objeto 41 42 public void setObjetoObject objeto thisobjeto objeto public Elemento getProx return prox public void setProxElemento prox thisprox prox Override public String toString return Elemento objeto objeto prox prox public class UsaLista public static void mainString args Lista listanew Lista Carro carro1new CarroJetta 2022 200000 Carro carro2new CarroFox 2014 20000000 Carro carro3new CarroFusca 1975 20000 Carro carro4new CarroMercedes GLA 2020 200 listainserircarro1 listainserircarro2 listainserircarro3 listainserircarro4 listaexibir Remoção de elementos na lista simplesmente encadeada São três casos distintos que devem ser considerados 1 Remoção do primeiro elemento 42 43 2 Remoção do último elemento 3 Remoção de elemento qualquer O projeto completo com as operações exibir inserir pesquisar e remover 43 44 public class Carro private String modelo private int ano id private double preco public Carro public CarroString modelo int ano int id double preco thismodelo modelo thisano ano thisid id thispreco preco public String getModelo return modelo public void setModeloString modelo thismodelo modelo public int getAno return ano public void setAnoint ano thisano ano public double getPreco return preco public void setPrecodouble preco thispreco preco public int getId return id public void setIdint id thisid id Override public String toString 44 45 return Carro modelo modelo ano ano id id preco preco public class Lista private Elemento inicio null atual aux método de instância public void inserirObject objeto if inicio null inicio new Elementoobjeto null aux inicio else atual new Elementoobjeto null auxsetProxatualproxatual aux atual public void exibir Elemento x inicio while x null SystemoutprintlnxgetObjeto x xgetProx Pesquisa os objetos da lista ligada simples param id int return Carro public Carro pesquisarIdint id Elemento x inicio Carro c while x null c Carro xgetObjeto if id cgetId return c x xgetProx return null 45 46 private Elemento pesquisarRemoveint id Elemento x inicio auxRem null Elemento v x auxRem Carro c while x null c Carro xgetObjeto if id cgetId v0x v1auxRem return v auxRem x x xgetProx return null public boolean removerint id Elemento v pesquisarRemoveid if v null Verifica se achou Elemento x v0 Elemento auxRem v1 if x inicio Verifica se é o primeiro elemento inicioxgetProx xsetProxnull else if x atual Verifica se é o último atualauxRem auxauxRem auxRemsetProxnull else Verifica se um elemento qualquer auxRemsetProxxgetProx xsetProxnull return true return falseInforma que não removeu inner class Classe interna private class Elemento private Object objetoDados private Elemento prox public ElementoObject objeto Elemento prox thisobjeto objeto thisprox prox 46 47 public Object getObjeto return objeto public void setObjetoObject objeto thisobjeto objeto public Elemento getProx return prox public void setProxElemento prox thisprox prox Override public String toString return Elemento objeto objeto prox prox public class UsaLista public static void mainString args Lista lista new Lista Carro carro1 new CarroJetta 2022 21 200000 Carro carro2 new CarroFox 2014 56 20000000 Carro carro3 new CarroFusca 1975 45 20000 Carro carro4 new CarroMercedes GLA 2020 78 200 listainserircarro1 listainserircarro2 listainserircarro3 listainserircarro4 Systemoutprintln Sem remover listaexibir Systemoutprintln Ao remover iflistaremover45 SystemoutprintlnRemovido com sucesso else SystemoutprintlnNão removido 47 48 listaexibir Lista Duplamente Encadeada A inserção de elementos na Lista Duplamente Encadeada Inserindo o primeiro elemento Inserindo outros elementos na lista 48 49 Simulação de uma lista duplamente encadeada Lista Duplamente Encadeada Remoção de elementos na Lista Duplamente Encadeada Removendo o primeiro elemento Removendo o último elemento Remoção de um elemento qualquer da lista 49 50 Exercícios Não pode usar ArrayListLinkedList Elabore uma lista duplamente encadeada para armazenar o TAD produto nomeProduto categoria String id int e preco double Realize as operações de inserção remoção e exibição Elabore um método para receber o desconto e a categoria como parâmetros e realize o desconto em todos os produtos de determinada categoria 50 51 Pilhas e Filas Estruturas de dados lineares fundamentais em computação de uso temporário e auxiliar com regra de acesso aos dados armazenados Podese encontrar uma grande gama de aplicações para essas estruturas lineares Estruturas Lineares com regra de Acesso Fila Pilha Política de acesso O Primeiro elemento que entra é o primeiro elemento que sai FIFO First In First Out O Último elemento que entra é o primeiro elemento que sai LIFO Last In First Out Aplicações Buffer de impressão Memória pilha execução de funçõesmétodos Operações básicas enqueuevalor inserirvalor dequeue remover empty vazia front frente size tamanho pushvalor inserirvalor pop remover empty vazia top topo size tamanho ADO Implemente uma pilha e uma fila usando a lista duplamente encadeada passada em aula Elas devem realizar as operações conforme a tabela acima Realize os testes conforme a tabela a seguir Operação Saída Pilha p push4 4 push3 4 3 pop 3 4 size 1 4 pop 4 pop vazia push6 6 push9 6 9 top 9 6 9 push1 6 9 1 empty falso 6 9 1 51 52 Operação Saída Fila f enqueue7 7 enqueue0 0 7 dequeue 7 0 enqueue8 8 0 front 0 8 0 dequeue 0 8 empty falso 8 size 1 8 dequeue 8 dequeue vazia front vazia enqueue3 3 52 53 Árvores Estruturas de dados não lineares com relação de hierarquia entre os elementos que a compõem É uma estrutura fundamental com inúmeras aplicações como sistemas operacionais e linguagens orientadas a objetos como Java e C A figura a seguir é a representação de uma árvore com os seus vários nós células E a tabela apresenta termos e conceitos utilizados no estudo deste tipo de estrutura de dados Nó Grau Nível Observação A 3 0 raiz B 1 1 C 2 1 D 0 1 folhaterminal E 1 2 F 0 2 folhaterminal G 1 2 H 0 3 folhaterminal J 3 3 L 0 4 folhaterminal 53 54 M 0 4 folhaterminal N 0 4 folhaterminal Grau da árvore 3 O grau representa a quantidade de filhos de um nó e o nível é a distância deste nó ao nó raiz O grau da árvore é o mesmo grau do nó de maior grau na árvore que neste caso é três Como estruturas de dados as árvores possuem características importantes de outras estruturas de dados Característica de vetor ordenado Pois a busca é rápida como no vetor ordenado Característica de lista encadeada Pois a inserção e a remoção são rápidas Árvores binárias Um tipo particularmente interessante eou importante de árvores são as árvores binárias Elas se caracterizam por ter em todos os seus nós no máximo grau dois Exemplos a 54 55 b E se a entrada de dados estiver condicionada a uma regra como é o caso da árvore do exemplo b Então temos uma árvore binária de pesquisa Árvores binárias de pesquisa A árvore do item b é uma árvore binária de pesquisa porém a árvore binária do item a não é uma árvore binária de pesquisa com relação à regra que iremos adotar a seguir As árvores binárias de pesquisa possuem uma organização na entrada de dados que pode ser representada pela regra de inserção de dados apresentada a seguir Inserção de dados Se árvore vazia então Insira o nó na raiz Senão Se nó é menor que o nó já instalado então Insira o nó à esquerda Senão Insira o nó à direita Exemplo Considere a entrada de dados a seguir 12 3 45 6 17 11 22 9 0 36 48 11 Monte uma árvore binária de pesquisa 55 56 Pesquisa A busca de valores é uma tarefa fundamental em qualquer estrutura de dados Nas árvores a busca concentrase em subárvores onde pode haver a ocorrência do valor procurado e gera um caminho de busca Por exemplo desejamos pesquisar o valor 37 na árvore binária de pesquisa apresentada anteriormente Então o caminho de busca fica 12 45 17 22 e 36 E obviamente não achou o valor de pesquisa neste caso Percurso na árvore binária O percurso é uma operação que tem por objetivo visitar todos os nós de uma árvore binária uma única vez Existem várias técnicas de percurso no entanto veremos três técnicas clássicas Préordem préfixado 1 Visitar nó raiz 2 Percorrer subárvore esquerda 3 Percorrer subárvore direita Pósordem pósfixado 1 Percorrer subárvore esquerda 2 Percorrer subárvore direita 3 Visitar nó raiz Ordem central 1 Percorrer subárvore esquerda 2 Visitar nó raiz 3 Percorrer subárvore direita Os três percursos para a árvore anterior fica Préordem préfixado 12 3 0 6 11 9 11 45 17 22 36 48 Pósordem pósfixado 0 9 11 11 6 3 36 22 17 48 45 12 Ordem central 0 3 6 9 11 11 12 17 22 36 45 48 56 57 Exercícios Para auxiliar acesse o link Árvore Binária de Pesquisa httpbtvmelezinekczbinarysearchtreehtml 1 28 35 12 45 4 6 8 81 3 5 13 25 a Montar a árvore binária de pesquisa b Realizar os três percursos préordem ordem e pósordem 2 H R T I A C J K P G M D Z L S R O F c Montar a árvore binária de pesquisa d Realizar os três percursos préordem ordem e pósordem 3 Dada a árvore a seguir Pedese a Faça os percursos préfixado préordem pósfixado pósordem e central ordem b Faça a pesquisa para os valores 41 e 16 E escreva o caminho gerado nas pesquisas 4 Considerando a árvore original do exercício anterior como ficaria esta árvore se entrássemos com os valores 84 e 61 Desenhe a árvore resultante 57 58 Implementação de uma árvore binária de pesquisa Sejam os valores de entrada 819 6 3 7 0 2 58 59 Remoção de nó em uma árvore binária de pesquisa Três casos que devemos abordar 1 Remoção de um nó com grau zero Caso simples removese o nó desejado sem realizar qualquer outra manipulação na árvore 2 Remoção de um nó com grau um Removese o nó desejado substituindoo pelo nó filho 3 Remoção de um nó com grau dois Removese o nó desejado substituindoo pelo nó de maior valor na subárvore da esquerda Poderia ser de forma alternativa substituir pelo menor da subárvore da direita Exemplo Considere a árvore da figura abaixo Devese remover os nós 19 88 e raiz E finalmente desenhar a árvore resultante Removendo o nó 19 Removendo o nó 88 59 60 Removendo o nó raiz Expressões aritméticas em árvores binárias Exemplos a AB 60 61 b ABCDEF Percursos nas árvores que armazenam expressões aritméticas pósordem EDR A B C D E F Notação polonesa reversa préordem RED A B C D E F Notação polonesa ordem ERD A B C D E F Notação clássica Exercícios 1 Considere a sequência de valores de entrada 34 4 12 57 8 10 55 61 41 15 27 19 2 46 a Monte a árvore binária de pesquisa b Remova os nós raiz 61 e 41 Desenhe a árvore resultante c Faça os três percursos clássicos na árvore resultante 2 A seguir são dadas as expressões aritméticas armazeneas em uma árvore binária e realize os três percursos clássicos apresentados nas aulas a n1n2n3n2n1n48 b abcdefghi 61 62 Exercícios Faça o download do projeto árvore binária disponível no Black Board 1 Escreva um método recursivo para cada um dos percursos pósordem e préordem 2 Escreva um método recursivo que determine e exiba o menor valor da árvore binária de pesquisa 3 Escreva um método recursivo que determine e exiba o maior valor da árvore binária de pesquisa 4 Escreva um método que dado o valor do nó ele retorne o grau desse nó Utilize o método buscar implementado em aula para localizar o nó que deseja analisar 5 Elabore uma solução que retorne a soma total dos valores armazenados na árvore Não devese modificar o método inserir escrevam um ou mais métodos se necessário 62