JAVA PARA TODOS: estrutura de dados

1. Introdução: Olá e bem-vindos a uma nova turma. Já abordamos os conceitos básicos de Java e programação em geral. E nesta classe falamos sobre estrutura de dados. Então, em primeiro lugar, definimos uma estrutura de dados. Que tipos de estrutura de dados temos na programação, como criá-los e usá-los. E ele se concentrará em estruturas de dados lineares, como pilhas, filas e LinkedList. E já falamos sobre arrays e usá-los nas classes anteriores. Então estaríamos focando principalmente na pilha cuz LinkedList. Então, na pilha, vamos aprender como criar uma estatística nós mesmos e como usar a pilha Java embutida, como usar a pilha baseada na lista vinculada. Então continuaremos com uma fila. Fazemos a mesma coisa com a fila. E, finalmente, crie nossa lista única e duplamente vinculada para vê-lo no próximo vídeo. 2. Estrutura de dados: Neste vídeo, vamos falar sobre estruturas de dados. E a estrutura de dados é um formato especializado para organizar, processar , recuperar e armazenar dados, onde existem vários tipos estruturais básicos e avançados. Qualquer estrutura de dados é projetado para organizar dados para atender a finalidade específica para que eles possam ser acessados e trabalhados com uma maneira apropriada. Como você pode ver aqui, temos dois tipos de estrutura de dados. Temos o linear e o não-linear. Por exemplo, matriz é um, é um exemplo de uma estrutura de dados linear, e nós o usamos tantas vezes nas classes anteriores. Nós também temos pilha e listas vinculadas. No LinkedList temos listas individuais e duplamente vinculadas. E o tipo não-linear, temos gráficos e árvores. Então, nesta aula, vamos aprender como e quando devemos usar cada um deles. E como eles podem nos ajudar? E quais são as vantagens? Vê-lo no próximo vídeo. 3. Stack com a matriz: Uma pilha é uma estrutura de dados linear que segue uma ordem particular em que as operações são realizadas. Há muitos exemplos da vida real de uma pilha. Por exemplo, as jogadas que são empilhadas umas sobre as outras para que ela seja atualizada, que está no topo, é a primeira a ser removida. E a placa que foi colocada na posição mais baixa, permanece na pilha para o período mais longo de tempo. Aqui, por exemplo, nós temos nossa pilha vazia e nós empurramos, por exemplo, o número um, e então nós empurrá-lo no número dois e depois três. Então temos 123. Agora, se queremos tirar um elemento, vai levar três, que é o último elemento, o inserido. Então pode ser simplesmente visto para seguir a ordem lifo que é o último a entrar, primeiro a sair. Então aqui temos duas operações principais, o push and pop. Agora temos uma classe de pilha em Java, mas não usá-lo neste vídeo. Vamos implementar os métodos sozinhos. E para implementar a pilha, usamos um array. Então vamos em frente e usar array para implementar nossa pilha. Vamos em frente e criar um novo projeto. Vamos nomeá-lo. E este nome do pacote como uma fase. E, e este pacote irá criar. Então esta é a nossa pilha de matriz de classe. E vamos criar uma interface e nomeá-la pilha. Então aqui temos interface, e aqui teremos todos os métodos. Então esta é a nossa interface. E, em primeiro lugar, temos, como você disse, o método push and pop. Então haverá um impulso de vazio público, e estaremos empurrando um objeto. Pode ser inteiros, string, caractere e assim por diante. E outro método que é e estourar um objeto. E vamos criar alguns outros métodos. Então, em vez de estourar, estourar um elemento, e quando abrimos um elemento, movemo-lo da pilha. No entanto, se nós, nós só queremos dar uma olhada neste elemento, precisamos criar outro método e vamos nomeá-lo. Então nós apenas temos um olhar para este objeto usando esse método superior. E vamos em frente e criar algum outro método. Por exemplo, o tamanho para verificar o tamanho da pilha e o SMD. Está vazio. E para verificar se a pilha está vazia ou não, ele irá retornar um verdadeiro booleano se ele está vazio e falso caso contrário. Então aqui temos nossos métodos. Agora. Temos um problema aqui. Porque sempre que queremos empurrar e reutilizar matriz, por isso, se quisermos empurrar, a matriz está cheia, temos um limite na matriz. E por exemplo, digamos que a área é de tamanho quatro. E já estamos pressionados por elementos. E tentamos empurrar o quinto. Então teremos uma média aqui. Uma vez que a matriz é limitada e não podemos empurrar cinco elementos em um elemento de quatro em um. E, claro, se você quiser pop um elemento ea pilha está vazia, então não terá, não vai ter qualquer elemento para pop para ver a partir do topo método. Então, para corrigir isso, precisamos criar nossa própria classe de exceção. Então vamos em frente e criar nossa exceção. Vamos nomeá-lo exceção pilha. E como de costume, vamos apenas criar nossa exceção pública construtor. E vamos pegar uma mensagem e puxar o jantar. E, claro, vamos lançar estender, desculpe, a classe de exceção para usá-lo nesta classe. Então, agora terminamos com essa exceção Stark. Vamos voltar e precisamos lançar esta estática essa exceção. Então lança exceção. E a mesma coisa. Outros métodos que exceção. E agora estes são o nosso método. Então aqui temos um erro lança. Agora vamos voltar para a classe de pilha baseada em matriz e implementar este método criado anteriormente aqui. Então, primeiro de tudo, precisamos estender ou implementar a interface de pilha. Porque sempre que queremos usar uma interface, precisamos adicionar aqui implementos e vamos implementar a interface de pilha. E, claro, temos um erro dizendo que herdamos métodos abstratos e que precisamos implementar. Então vamos e cada método, e estes são os nossos métodos. Então vamos começar com o primeiro de tudo, precisamos criar o construtor, é claro. então, primeiro de tudo, nós temos hoje, e pode ser uma string inteira, caractere, o dobro de qualquer coisa. Então vamos dar-lhe o valor do objeto e vamos nomeá-lo. E é claro que temos nosso inteiro menor que m. E então este seria o lugar onde vamos nos mover. Agora, vamos criar nosso construtor. E o construtor da base. Então este é o construtor e ele vai levar a capacidade da matriz ou a pilha se você quiser. E, claro, vamos instanciar o objeto em um com o valor da capacidade. E ainda temos top. Então, no início, digamos que tau é igual a menos1, e veremos por que em um minuto. Então top é igual a menos1, e aqui temos público. Então este é o nosso construtor. Agora vamos para o nosso método é vazio. Então, se por exemplo, se superior é igual a minus1, retorna true, que está vazio, caso contrário, retorna false. Então, se topo é igual a menos um, ele está na condição inicial ou não temos nada e a pilha apenas retornar true, caso contrário retornar false. Agora, temos um atalho para isso. Então, em vez de dizer retorno, caso contrário, retorno, podemos simplesmente dizer retorno é igual a menos um. Então esta afirmação, topo é igual a menos um. Ele irá verificar se top é igual a minus1 irá retornar automaticamente um booleano. E retornar um booleano aqui resultaria no retorno de um método booleano. Então, se o topo for igual a menos um, ele retornará verdadeiro. Caso contrário, ele retornará falso. Agora, ainda temos o tamanho que é fácil. Então o ano vai simplesmente retornar o que temos aqui, um top plus um. Então, no início temos top é igual a menos um. Então, sempre que precisarmos saber o tamanho, nós apenas adicionamos um no topo. Então aqui temos menos um mais um igual a 0. Assim, a condição inicial da pilha é de tamanho 0. Agora, vamos para o nosso método de push. Então temos o nosso arbusto. E aqui, antes de tudo, precisamos verificar se a pilha está cheia, então não podemos adicionar outros elementos. Então, primeiro de tudo, precisamos definir o tamanho. É igual ao array.length. Então, sempre que temos o tamanho que é superior mais um é igual a array.length do que precisamos lançar nossa exceção aqui. Lançar uma exceção. Essa exceção com uma mensagem de método. Diz que SQL. Agora, se este não for o caso, então continuaremos normalmente. Então o que vamos fazer é primeiro incrementar, vez que adicionamos um elemento configurado, não menos 1 mais, é igual a mais um, que é igual a 0. Então, agora, se quisermos usar o tamanho, obtemos top mais 10 mais 11. E isso é quantos elementos temos na pilha no momento se usarmos o método push. Então agora depois de incrementar o topo, precisamos ouvir a matriz no valor do objeto que entramos aqui. E agora terminamos com nosso método de push. Vamos para a nossa doca. Aqui. Primeiro de tudo, precisamos verificar se nossa pilha está vazia, então não temos nenhum elemento para mostrar. Se estiver vazio. Então jogue essa exceção. Exceção e dizendo que a pilha está vazia. Agora, se este não for o caso, então nosso elemento basta adicionar o copo de índice. Agora vamos ao nosso método final. E o método que precisamos verificar se está vazio. Se a pilha está vazia, precisamos lançar exceção, dizendo isso. Caso contrário, precisamos retornar esse objeto. Tudo o que temos no topo. Aqui. Por exemplo, se usarmos pop aqui, então precisamos retornar esse objeto e movê-lo da pilha. No entanto, se você usar stop, então vamos apenas ter um olhar para este objeto que é igual a três sem removê-lo da pilha. Então vamos voltar. E aqui, primeiro de tudo, vamos criar um objeto ClassName e retornar. Então este é o objeto que vamos devolver, e é. Agora começamos o objeto aqui e esta variável para retornar. E precisamos remover esse elemento, então simplesmente damos um valor nulo. E agora não, removemos um elemento, então precisamos diminuir isso. Então, por exemplo, se tivermos três elementos e usarmos o método pop, então irá diminuir nossa variável superior de três para dois para um. Então vamos simplesmente decrementar por um top menos menos e retornamos este objeto e esta variável aqui. Então o que chegamos aqui é que criamos nossa interface, nossa exceção, e nossa classe, que temos, todos os nossos métodos. Então, no próximo vídeo, vamos criar nossa classe de driver e usar esses métodos nele. 4. Aplicação de tack: Então, agora que temos todos os nossos métodos, vamos criar nossa classe de driver. Então, este é o nosso motorista. E eu seria o método principal. Claro que você vai lançar uma exceção de pilha. Ou podemos dizer exceções, vez que a exceção de pilha é uma subclasse da classe de exceção. E antes de tudo, precisamos criar o nosso em um nome S pilha base, uma pilha com uma capacidade de porta, por exemplo. Agora, a primeira coisa que vamos fazer é adicionar um elemento a isso, então usamos a pilha, o Bush. Vamos adicionar outro e empilhar o push para empilhar os três. Então vamos fazer como este exemplo. Então, primeiro de tudo, temos uma pilha vazia. Então empurramos três elementos. Agora, o que? Isso vai acontecer aqui, quando executarmos esse código, vamos para nossa pilha baseada em array. Vamos usar este método três vezes. Então, primeiro de tudo, temos o topo inicialmente é igual a menos um. Quando empurrámos o número um. O que está acontecendo aqui é, em primeiro lugar, ele deve estar verificando o tamanho deste tamanho é igual a array.length. Agora o array.length é a capacidade aqui. Então esta capacidade e a classe de driver aqui é o array.length. Agora, o array.length aqui é igual a quatro. Então é um PE, uma vez que o tamanho é igual a mais um e superior é igual a menos1. E inicialmente tão tamanho igual a 0 uma vez que não temos nenhum elemento e 0 não é igual a quatro. Então não vamos lançar a exceção de pilha. Então agora vamos incrementar o topo. Agora DOB é igual a 0. E neste caso vamos adicionar este elemento, que é um. Vamos adicioná-lo ao a, na posição 0, uma vez que o incrementamos aqui. Agora, a mesma coisa. Vamos fazer a mesma coisa mais duas vezes para o objeto 23, para inteiros 23. Então, e nós vamos verificar se o tamanho. Agora o tamanho é igual a um. Uma vez que o tamanho é igual a mais um e superior é igual a 0. Portanto, o tamanho é igual a 0 mais um. E, claro, não é igual a quatro, não é igual ao comprimento. Então a pilha ainda não está cheia, e nós incrementá-lo mais uma vez e vamos armazená-lo em, em uma posição um, então você elemento e, em seguida, na posição da matriz para o segundo, o terceiro elemento. Então, deixe-me ver os lados aqui. Então nós imprimimos o tamanho da pilha. E depois de adicionar, esse elemento irá. Vamos verificar o tamanho, o tamanho. E, finalmente, vamos verificá-lo depois de adicionar o terceiro elemento. Então vamos em frente e executar este código. Veja o que vai acontecer. Então, primeiro de tudo, temos esse tamanho igual a 123. E deixe-me usar a pilha é método vazio. Então, aqui a pilha está vazia, ela deve retornar true. Então a pilha está vazia. Agora, se o usarmos, por exemplo, aqui, a pilha está vazia. Deve retornar falso. Uma vez que a pilha não está vazia, temos três elementos na pilha. Agora, nós também temos a pilha, o topo. Aqui. Temos três elementos. Então, se usarmos a pilha no topo, ele nos dará esse valor sem removê-lo. Então vamos usá-lo aqui. Nós dizemos elemento superior. Assim, esses dados. E vamos executar o código que nos dará o elemento superior é igual a três. Agora vamos usar o pop, pop, e ele também vai nos dar três. No entanto, se usarmos a pilha, o método superior, novamente aqui, agora que removemos o elemento três não obteria três. Vamos ter dois agora, já que movemos este elemento, agora, o novo elemento na posição superior é o elemento dois. Então, estes são todos os métodos que implementamos na classe de pilha baseada em array e a interface, é claro. Então, este é o fim para este vídeo. Vejo-te no próximo. 5. com o problema de correspondência de símbolos: Vamos demonstrar o uso de pilha. Então vamos fazer um exemplo. Vamos considerar esta etiqueta. Então aqui temos a nossa pilha, e vamos fazer um exemplo de correspondência de símbolos. Então nosso programa deve retornar que a expressão é válida ou não. Então, por exemplo, estes são os símbolos de abertura, e estes são os símbolos de fechamento. Agora, deixe-me escrever assim. Então aqui temos nossos três símbolos. E deixe-me escrever aqui alguns exemplos. Por exemplo, se dissermos etch. Então nosso programa deve retornar verdadeiro aqui, já que este símbolo de abertura tem um de fechamento. No entanto, se nós, por exemplo, vamos dizer borda, e deixe-me colocar um aqui. Portanto, este símbolo de abertura não tem um fecho antes de abrir um novo. Então aqui temos isso. E para ser uma expressão válida, devemos adicionar uma aqui e você mudou isso. Agora, cada símbolo de abertura é seguido por um de fechamento. E é claro que podemos adicionar o que você quiser. E então este é um sentido válido. Cada símbolo de abertura é seguido por um fechamento. Então o que vamos fazer é aceitar uma expressão e então armazenar cada abertura, cada símbolo de abertura na pilha. Então vamos supor que temos essa expressão. Ok? Então temos, por exemplo, a, B, C e D. Deixe-me clicar em 20. E então esta é a nossa expressão e passará por esta expressão um por o. Então um não corresponde a nenhum destes símbolos de abertura, abertura. Então vamos ignorá-lo e ir para este colchetes. E combina com este. Então nós o armazenamos na pilha. Então aqui temos, agora esses colchetes. Então nós vamos para B. Nós não temos em B não corresponde a nenhum destes, qualquer um destes símbolos, vai ignorá-lo e ir para este. Este também não corresponde a nenhuma destas aberturas, mas coincide com a de fecho. Então aqui temos este melhor jogo. E, claro, vamos estourar este elemento na pilha, compará-lo com este. Se eles são iguais, então continuaremos em nossa expressão. Caso contrário, retornaremos falso. A expressão é inválida. Então vamos fazer a mesma coisa aqui. Temos essas fantasias e eu vou compará-las. Este. Vamos colocá-lo na pilha e compará-lo com este aqui. E finalmente, temos os colchetes também. Agora podemos ter também, por exemplo, algo como isto. Então o que vai acontecer aqui é deixar-me, deixa-me apagar é. E então esta é a nossa expressão. E em primeiro lugar, vou olhar para isso. É um símbolo de abertura, então vai colocá-lo aqui. E então vamos olhar para o segundo elemento. Temos colchetes. Então é um símbolo de abertura também, e vamos armazená-lo na pilha. Então vamos empurrá-lo. Então essas fantasias vão descer aqui e os colchetes aqui. Agora, vamos verificar o terceiro elemento, este fechamento, vamos compará-lo com o elemento superior na pilha. Então aqui temos um fechamento colchetes e uma abertura colchetes, a partida. Então, vamos apenas estourar este daqui. E vamos continuar aqui. E é claro que vamos colocar os parênteses aqui. Agora, depois disso, vamos comparar este símbolo de abertura com o último elemento aqui. E, claro, a imagem, então nossa expressão é válida, caso contrário, seria inválida. Então esta é uma idéia rápida sobre este problema, e vamos começar com a escrita de código R. Então, aqui temos nossa pilha baseada em array. Vamos criar uma nova classe, nome e símbolo de correspondência. E agora classe, é claro, temos o nosso método principal e vamos criar um método que retorna um verdadeiro booleano se a expressão é válida, caso contrário ele vai retornar false. Então seria um booleano estático privado. Vamos nomeá-lo, validar, e ele vai aceitar uma expressão como uma forma de string. Agora, em primeiro lugar, vamos começar com o loop Y. E vamos ver o que vamos colocar como condição aqui. Agora vamos criar nossa pilha baseada em array e com o perímetro de expressão desse comprimento. Assim, o número máximo de elementos que podem ser armazenados na pilha é o número máximo de elementos nesta string. Então, se todos eles estão abrindo, podemos armazenar todos eles. Mas é claro que devolverá um inválido, falso já que não os fechamos. Agora, nós temos, nossa pilha criou, por exemplo, um índice, o mesmo índice. Será às 0. E uma declaração booleana é válida. Bem, em primeiro lugar, para ser igual a verdadeiro e caráter, vamos nomear a corrente. Agora. Embora seja válido e por que essa expressão é válida, então vamos continuar executando esse código. E, claro, enquanto o índice é menor que o comprimento, comprimento da expressão. Portanto, estas condições estão satisfeitas. Continue executando este código. Agora, primeiro de tudo, vai armazená-lo nesta corrente, este caractere igual à expressão no índice. Então vamos supor que temos este exemplo e antes de tudo, vamos armazenar borda e corrente. Agora vamos verificar se este diretor corresponde a algum dos símbolos de abertura ou fechamento. Então, para fazer isso, deixe-me criar alguma abertura, algumas cordas para criá-las lá fora. Eles serão privados. Terapia. Esta abertura será igual a estes símbolos de abertura. E, claro, estática privada. String de fechamento b igual a é símbolos de fechamento. Agora, o que vamos fazer é verificar se esta corrente corresponde a algum dos símbolos de abertura. Então, se nos lembrarmos corretamente, temos a classe string, o índice método off. Então vamos usá-lo aqui. Então F up o nome que o índice off. Então o que estamos tentando fazer aqui é verificar se a corrente é uma abertura. Então, se abrir esse índice de corrente, então se atual é um dos caracteres na string de abertura, então ele irá retornar o índice dele. Assim, por exemplo, se temos corrente é igual a este símbolo de abertura, ele retorna 0, disciplinando símbolo um, eo último símbolo de abertura que ele iria retornar para. Caso contrário, ele retornará menos um se não for igual a nenhum desses símbolos. Então, f adivinhar. Símbolo não é igual a menos um. Em seguida, vamos simplesmente empurrá-lo para o status da pilha que empurrar. E vamos empurrar essa quantia, mas agora não é o caso. Pode ser um símbolo de fecho. Então o que vamos fazer é verificar como fechar esse índice. Esta corrente também não é igual a menos um. Se esta corrente é um dos símbolos de fechamento, em seguida, ele iria retornar qualquer valor diferente de menos um. Então este é o caso e a corrente é um símbolo de fechamento. Então nós, então nós vamos compará-lo com uma abertura da pilha. Então vamos estourar um símbolo de abertura da pilha. E podemos facilmente comparar os símbolos ou recontar comparar o índice. Então, por exemplo, temos os colchetes. Então, se compararmos o índice de abertura e fechamento, se eles são iguais, então os símbolos são iguais. Então é isso que vamos fazer. Então, se abrir esse índice de pilha, esse disco não é igual ao índice de fechamento desta corrente. E este não é o caso, então nós apenas retornar é válido para falso. Agora temos um erro aqui dizendo que o índice método do tipo String classe não aceita objeto desde a pilha que pop é um objeto. E também sabemos que só estamos armazenando neste caractere de pilha. Então posso dizer com segurança que sabemos que precisamos que isto seja um personagem. E agora vamos ver exceção não tratada, uma vez que podemos ter exceção aqui e este tipo de empurrar e empilhar o pop. Então, para estar no lado seguro, vamos usar uma tentativa e pegar. Então vamos tentar isto. Caso contrário, se a exceção de pilha ocorreu, apenas gadget e retornar false. Vamos incrementar o índice para passar por toda a expressão dos elementos nesta expressão. E nós vamos voltar é válido. Assim, ele retornará true se a expressão for válida, caso contrário ele retornará false. Agora ainda temos uma modificação e vamos fazê-lo no próximo vídeo. Por que executar o código para vê-lo no próximo. 6. Como combinar o problema de símbolo 2: Então vamos ver o que nosso código faria até agora. Por exemplo, se tivermos essa expressão, em primeiro lugar, ele irá obter o primeiro elemento e compará-lo com um dos símbolos de abertura. Se este não for o caso, ele irá compará-lo com os finais. E, claro, se não coincidir com nenhum destes abrindo e fechando, continuaremos sem fazer nada. Então, em segundo lugar, vamos obter este símbolo de abertura comparado com um dos símbolos de abertura na abertura da string. E, claro, ele vai coincidir com os colchetes e nós vamos empurrá-lo para a pilha. Agora, vamos fazer a mesma coisa com este D e o de um personagem. Não vamos fazer nada desde os símbolos de abertura ou fim. Então teríamos esse símbolo de fechamento e combinaria com um dos símbolos de fechamento e a tensão de fechamento. E se for esse o caso, então não aparecemos nada. O primeiro elemento, o elemento superior na pilha, que é este, este símbolo. E vamos compará-lo com o final. Vamos comparar a análise deles e eles são iguais, então não vamos fazer nada. Se eles não estão, então nós vamos, eu vou dizer que como válido agora é falso. Por exemplo, se tivermos esse símbolo do que a pilha, vamos ter os colchetes para baixo e os parênteses para cima. E vamos comparar os parênteses com os colchetes e o não igual. Então ele retornará falso. Agora ainda temos uma modificação a fazer. Por exemplo, suponha que temos, digamos que temos isso, esse código seria executado corretamente. No entanto, vamos supor que temos colchetes aqui. Agora, vou citar, vai começar todos esses personagens, todos esses símbolos e o veado. E primeiro de tudo, ele vai estourar este parênteses e compará-lo com este parênteses de fechamento lá igual, então ele vai continuar. E o outro, que é este colchetes e compará-lo com os colchetes. Agora, vamos terminar com B e não vamos fazer nada. E nosso código retornamos verdadeiro já que não temos nenhum problema com a abertura e fechamento. No entanto, ainda temos este colchetes e nossa pilha. Então deveria, devemos retornar falso desde então. Nem todos os símbolos são combinados entre si. Então o que vamos fazer é comparar o veado, usar o f m está vazio. Então, se pilha está vazia, se ele não está vazio, então é válido vai ser falso. Uma vez que ainda temos um ou mais elementos na pilha. E isso deve retornar falso, não é verdade. E é claro que vamos voltar é válido. Agora, vamos ver os últimos exemplos. Por exemplo, o 3.5. Este código. Temos um símbolo de fecho. E é claro que vamos saltar da pilha e abrir um. Agora a pilha está vazia e não temos nenhum símbolo nela. Então isso irá gerar uma exceção e nós vamos pegá-lo aqui e devolvido cai diretamente. Então este é o nosso código e vamos usá-lo aqui. Então, em primeiro lugar, deixe-me começar aceitando uma expressão. Usamos scanner. Quando novo Scanner, como de costume. A expressão igual à varredura. A próxima linha. Vamos usar este método de validação. Então, se validar, se for verdade, então vamos imprimir expressão é expressão de marca válida. E vamos executar este código. Vamos ver se vai acontecer. Por exemplo, vamos inserir a expressão de retorno é válida. Agora, vamos supor que temos esses símbolos. E, claro, eles são válidos, uma vez que cada abertura é seguida por um símbolo de fechamento. E se tivermos apenas uma abertura que será convidada, apenas um símbolo de fechamento, é claro que seria inválido. E finalmente, se, por exemplo, temos os valores, os símbolos. Desta forma, ele não será válido mesmo que cada abertura tenha um símbolo de fechamento, mas eles não são ordenados da maneira correta. Então ele retornou um inválido. Então este é o símbolo do grupo correspondente. E vejo você no próximo vídeo. 7. Problema de mensagem secreta: Agora já temos uma pilha embutida em Java. Então vamos usá-lo e trabalhar com o problema. Essa é uma mensagem secreta. Então a idéia é que vamos receber uma mensagem secreta que reserva mensagem invertida. Então, por exemplo, em vez de dizer olá, Eddie será o. Então vamos converter isso para Olá inebriante usando preso. Então, primeiro de tudo, vamos criar nosso método principal. Mas isso tem um método principal e outro método que é decodificar essa mensagem. Mas você será estática particular. String, nomeie, decodifique e mensagem de string. Vamos criar nossa pilha aqui. Então, primeiro de tudo, temos uma pilha, e a pilha será uma pilha de caracteres. E este nome é igual a nu. E, claro, vamos precisar de uma corda. E vamos usar o StringBuilder. Então esta é uma classe de string. Corda. É uma classe definida em Java como nome em SBI e B igual a U StringBuilder. Então, neste StringBuilder, vamos mudar nossos personagens e, eventualmente, nossas palavras. Então vamos usar um tokenizer de cordas. Então classe tokenizer distinta permitiu quebrar uma string em token. Então, para instanciar o tokenizer de cordas, nós simplesmente escrevemos string, o colonizador. E você pode encontrá-lo no Java que você acha que classe é chamado SD, instanciado com a string, a própria mensagem. Agora que estamos prontos, vamos em frente e fomos absolvidos. Então diz que a estrela não pode resultar também. Então simplesmente pode colocar pilha de Java Tutor. E aqui devemos voltar, devolvemos mais tarde. Então, primeiro de tudo, iria ler cada palavra no tokenizer string. Então, enquanto o organizador rigoroso tiver mais tokens, continuará executando. A primeira coisa que vamos fazer é criar uma linha reta fora da lista Emit word. E se esta palavra O valor que está no tokenizer string para dar-lhe como G, o próximo token. Agora, suponha que temos esta expressão primeiro, onde seria esta. E nós vamos lê-lo e empurrar cada personagem para a pilha. Então aqui criamos um loop for. Para i é igual a 0 até que i é menor que ou é que o comprimento irá simplesmente empurrar este personagem para a pilha para que a criança. E nós simplesmente empurramos todos os caracteres na pilha nesta palavra para esta etapa. Depois de empurrá-los, precisamos extraí-los usando o método pop e uma plantá-los no StringBuilder. Então, enquanto isso não está vazio, nós simplesmente acrescentamos caracteres que usando a lâmpada padrão. E depois disso, depois de terminar do loop selvagem, simplesmente anexamos esse espaço em branco. Então vamos ver o que fizemos aqui e um exemplo. Então, por exemplo, como dissemos, se temos, vamos escrevê-lo. Por exemplo. Olá, em vez de ter uma baixa estará acontecendo. Isto. Agora, a primeira coisa, nós vamos armazenar esta vírgula e, em seguida, O , L, E, e F. Então nossa pilha vai parecer e L, o. E, e, e vamos separar isso. Então aqui temos, esta é a nossa pilha. Temos 123456 caracteres. Agora, depois de classificá-los em pilha, precisamos extraí-los usando o livro estatutário. Então, enquanto desce, o primeiro passo seria então E, depois L, L O. Então vamos pegar e l, l. Então, se dermos essa entrada, isso nos devolverá esta. E é disso que precisamos. Isto é o que vamos fazer. Precisamos reverter a palavra de “O Alelo Edge” para “Olá”. Então vamos voltar aqui. E simplesmente depois de buscar do loop selvagem, simplesmente retornamos SB para dois. Agora, vamos voltar ao nosso método principal. E neste método, precisamos ter a mensagem e a mensagem decodificada. Em primeiro lugar, usaremos um scanner para pedir ao usuário que insira uma mensagem. E simplesmente pedimos ao usuário para inserir uma mensagem. E vamos guardá-lo na mensagem. Então vamos para o decodificado usando o método decodificar e vendemos na mensagem decodificar. Para decodificar nossa mensagem. Então vamos imprimi-lo. Mensagem decodificada. E imprima a mensagem descodificada. Vamos em frente e executar este código. Então teríamos inserido uma mensagem. Por exemplo, como dissemos, olá. Para conseguir essa mensagem descodificada, é olá, feliz. Então é assim que usamos o estado definido em Java e como usá-lo para reverter qualquer coisa de mensagem para números ou qualquer coisa. Queremos vê-lo no próximo vídeo. 8. Quede filas com a matriz: Agora vamos falar sobre filas. Uma fila é uma estrutura de dados linear que segue uma ordem específica em que as operações são executadas. O odor é o primeiro a entrar, o primeiro a sair. Um bom exemplo de uma fila é um restaurante. A pessoa que vier primeiro será servida primeiro. A diferença entre pilhas e filas está na remoção. Em vez disso, removemos o item adicionado mais recentemente, e a fila, removemos o item menos recentemente adicionado. Por exemplo, aqui temos duas posições frente e basicamente temos duas operações principais, enqueue e dequeue. Eles são equivalentes a empurrar e estourar em pilhas. Então, quando queremos enfileirar e q, o elemento na posição. E quando queremos desenfileirar, basta usar a posição frontal e remover o elemento da primeira posição ou segundos, assim por diante. Então agora vamos demonstrar o uso de uma fila e um exemplo. Vamos voltar ao Eclipse. Feche essas classes de ações e crie um novo pacote. E baseado em sname. P: Então neste pacote, como fizemos neste exemplo, vamos criar uma interface q a q básica. Claro que vamos criar uma exceção. Exceção. Vamos renomeá-lo. Então estas são as nossas três classes principais. E vamos começar com a nossa interface. Vamos ter os métodos, como fizemos neste exemplo. Temos um azul, mas o tamanho booleano está vazio. vazio público levará objetos públicos para retornar um objeto e você o move. E vamos nomear um objeto preto, nomeá-lo de frente. Só para ver a frente. Aqui temos um capital energético. E como fizemos nos exemplos anteriores, neste exemplo, precisamos criar nossa exceção. Vamos criar uma mensagem construtor, mensagem de codificação e estende exceção. Agora, nós só precisamos lançar essas exceções e esses métodos exceção fila. E fazemos o mesmo aqui e aqui. Então este é para Q e Q exceção. E o próximo vídeo que usaremos funcionará com o goo baseado em array e criará nossos métodos. 9. Quote com a fila de espera com a matriz 2: Agora vamos começar com o cubo baseado em matriz. Como você pode ver aqui neste exemplo, temos a entrada frontal do índice. Então, primeiro de tudo, precisamos criar uma matriz de nomeação de objeto. E é claro que vamos criar uma frente e tamanho. Agora vamos em frente e criar nosso construtor. Então, como de costume, a capacidade, porque estamos trabalhando com uma matriz e precisamos dar o, o tamanho do comprimento e criar nosso objeto com a capacidade igual ao tamanho, igual a 0, igual a 0 inicialmente. Agora, vamos começar com o nosso tamanho. Claro que vamos implementar e precisamos autorizá-lo em dois métodos. Então, aqui temos todos os métodos e a interface de lado com o tamanho simplesmente retornará o tamanho, seja qual for o tamanho como nós apenas retorná-lo. Agora, vazio está vazio. Nós apenas retornamos se o tamanho for igual a 0. Então, se a ciência é igual a 0, então ela está vazia. Caso contrário, ele não está vazio e deve retornar true. Esta expressão é uma expressão booleana e retorna true se o tamanho for igual a 0, caso contrário ele retornará false. Agora, vamos começar com o enfileiramento. Em primeiro lugar, precisamos verificar se o tamanho é igual a array.length. Então não temos mais espaço na inclinação e precisamos lançar a exceção. Por isso, temos de lançar a excepção. E dizendo que Q S pé. Esta é a primeira condição. Agora, se este não for o caso, então podemos adicionar o elemento à inclinação. Então, para adicioná-lo, vamos apenas usar o ano. Então vamos adicioná-lo na parte de trás. E agora precisamos incrementar a leitura. Então, quando simplesmente podemos dizer que, que v mais mais. No entanto, quando chegarmos a um ponto onde a traseira está na posição seis, e adicionamos um elemento aqui, então precisamos incrementar o U2 real estará na posição sete. Agora, no entanto, se tentarmos adicionar mais uma vez, isso nos dará uma exceção. Mas se um dos elementos da frente aqui são excluídos. Por exemplo, se usarmos o Q e removermos um, então temos um espaço vazio aqui. E nós não o usamos porque isso é apenas incrementando em um. Então precisamos resolvê-lo. Precisamos resolver este problema dizendo que sempre que esta esfera é igual a array.length, neste caso é igual a sete. Então precisamos modificá-lo e dar-lhe um valor de 0 para retornar p2 aqui. Então, para fazer isso, podemos simplesmente dizer pode usar f declaração. E se eu precisava de comprimento é igual à traseira, então vamos apenas dar que um valor de 0. No entanto, podemos simplesmente dizer que v é igual a cerveja mais um. Nós o incrementamos e o restante do tempo. Então o que estamos dizendo aqui é que V é igual a d mais um. Toda vez que o real mais um é menor do que esse comprimento IDed, não temos nenhum problema. Tudo funcionará corretamente desde j mais um restante de array.length é o mesmo. Uma vez que, por exemplo, se dissermos para Comandante de cinco, é 43 restantes de cinco. - É. No entanto, se cinco, o restante de cinco é 0, então sempre que temos três mais um é igual a array.length traseira se tornará 05 restante de cinco sextos, restante de seis é igual a 0. Então é isso. E vamos apenas incrementar o tamanho desde que adicionamos um elemento. Agora vamos para a fila. E este exemplo aqui. Primeiro de tudo, precisamos verificar se o tamanho é igual a 0 ou podemos usar como método vazio. Por exemplo, se ele está vazio, seria apenas você fila exceção dizendo que nessa fila está vazia. E depois podemos trabalhar. Agora, primeiro de tudo, precisamos criar um objeto para retornar. Então o que vamos devolver é o elemento na frente. Então, simplesmente retornamos. E agora precisamos removê-lo da fila. Então, para fazer isso, nós simplesmente usamos a mesma técnica que usamos para o ano r1 mais um restante de em um nono em, vamos entrar em um tamanho de decréscimo desde que removemos um elemento e apenas voltamos para retornar para isso é para o desenfileiramento? Ainda temos um último método. E este método vamos apenas dar uma olhada no que, o que temos na frente. Então, primeiro de tudo, vamos verificar se está vazio. Rema. Deixe-me copiar isto. E basicamente rasgar. E, claro, o array retornado na frente. Não precisamos remover nada. Só nos voltamos para voltar. Estes são os nossos métodos. E retornou ainda tem um novo método. Esse é um método toString. Nós não o usamos na pilha, mas você pode criar um aqui e imprimir a fila sempre que quisermos. Então vamos em frente e implementado. Agora, se queremos criar este método público, tentando string, e podemos trabalhar com o loop for e passar por todos os elementos na matriz. No entanto, prefiro modificá-lo toda vez que enfileiramos ou desenfileiramos. Então, primeiro de tudo, vamos criar um StringBuilder. É como uma string, mas podemos modificá-la. Você pode adicionar a ele sempre que quisermos ou excluir dele. Então nós novamente criar uma string sob este definido na classe java.lang. Então StringBuilder sb, sb, e ele vai dar-lhe, vai instanciar que novo StringBuilder. E muito bom, podemos usá-lo. Então, toda vez que enfileiramos, podemos acrescentar para distinguir o SP que acrescenta o que quer que incrementamos que adicionamos mais espaço. E toda vez que desenfileirar, podemos desenfileirar o elemento q a partir daqui para apenas sba dot delete da posição 0 para o comprimento do objeto mais um para contabilizar o espaço em branco. Então, até que o objeto para retornar esse comprimento. Para retornar o toString, em primeiro lugar, precisamos convertê-lo em uma string que é nove mais um. E é assim que excluímos do StringBuilder. E, claro, aqui nós simplesmente retornamos sba dot dois. E estamos bem. Então, isso é para a classe de fila baseada em array. E no próximo vídeo, vamos criar a classe de driver na qual vamos testar esses métodos. 10. Aplicação em fila de filas: Agora que temos todos os nossos métodos, vamos criar nossa classe de transferência. Então este é um motorista e discutir comida. Temos o nosso método principal. Precisamos saber a exceção da fila. E vamos criar a base inimiga, ou seja, U igual a U com base em matriz Q com a capacidade de. Para. Agora, vamos enfileirar alguns elementos. Então, por exemplo, q ponto q um. E vamos copiá-lo quatro vezes 234. Agora, se usarmos, se imprimirmos Q ou Q, as duas cordas são as mesmas. Temos 1234. Agora, por exemplo, vamos desenfileirar. Então, por exemplo, se dissermos, vamos imprimi-lo para ver o que vamos remover. Q ponto dq. Ele irá desenfileirar o elemento frontal no material de posição. Então, neste caso, vamos conseguir um. Então desenfileiramos a lagoa e se formos imprimi-los mais uma vez, teremos 234. Agora, se adicionarmos um elemento, por exemplo, digamos que vamos adicionar cinco. Então o que vamos conseguir se imprimi-lo agora é 2345. Então é isso. Agora. Não se parece com isso no, já que estamos usando o StringBuilder. No entanto, este cinco está na posição 0 Agora na matriz. Mas vemos, estamos vendo como 2345, já que estamos apenas adicionando o elemento na posição derivada e você está movendo-o da posição esquerda e do StringBuilder. Agora, por exemplo, vamos usar alguns dos outros métodos. Por exemplo, o tamanho de livre, para usar lados q-dot. Aqui, teremos três, já que temos apenas três elementos. Então aqui temos três elementos. No entanto, se usarmos aqui, imprima o tamanho u ponto tamanho, obtemos quatro desde que adicionamos mais um elemento. Então aqui podemos ver claramente é antes de tudo, nós temos três. No entanto, se imprimi-lo depois de adicionar o elemento cinco, obtemos quatro. Agora vamos tentar Q que está vazio. Vamos imprimir. Está vazio e vamos ficar falso desde que adicionamos alguns elementos aqui. No entanto, ele poderia dividi-lo com isso antes de enfileirar. Então vamos obter isso verdadeiro e depois falso desde que adicionamos alguns elementos. Este é um exemplo rápido de Q. E no próximo vídeo vamos falar sobre problema do Josephus e aprendemos como resolvê-lo. Vejo vocês no próximo vídeo. 11. Problema de Josephus: Agora vamos resolver o problema do Joseph. Primeiro de tudo, vamos entender isso. Então, para este problema, vamos ter jogadores e um número. Por exemplo, digamos que temos três jogadores, John, Alfred e tendências. Neste caso, digamos que temos o número e o número é igual a dois. Para, por exemplo. Primeiro de tudo, precisamos armazenar esses nomes, UTI Neonatal. O jogo termina quando uma pessoa é deixada. Por exemplo, quando dizemos k igual a quatro, Primeiro de tudo, precisamos desenfileirar. Vamos desenfileirar daqui. Precisamos desenfileirar John e adicionar aqui. Então. Então, esta é uma vez que executamos quatro vezes. Então ainda temos três vezes. Então precisamos desenfileirar, enfileirar , desenfileirar e AQ. Então esta é a última vez. Então agora executamos esta operação para todos os tempos. E acabamos com Alfred na primeira posição. Então, desenfileiramos. Agora ainda temos dois nomes. Então vamos executar a mesma operação também quatro vezes. Então DQ, Cress, e a mesma coisa aqui. E finalmente, da última vez com um pedaço enorme e coloque-o aqui. Então acabamos com crista na primeira posição. Então nós removê-lo usando o método q e acabamos com John switch. John é o vencedor. Então é isso. Então esta é a ideia da Geórgia, este problema que vamos resolver. Vamos agora implementado e de saída. Primeiro de tudo, vamos criar o nosso método mais nomeá-lo para que ele vai levar uma estadia em uma matriz de strings. E vamos nomeá-los jogadores e um inteiro k. Agora, primeiro de tudo, vamos criar uma string e adicionar um baseado dois q igual nu em uma visão base com a capacidade de jogadores desse comprimento. Então, quantos jogadores nós temos apenas daria a exibição da sugestão. Agora, primeiro de tudo, vamos tentar. E se algo acontecer, vamos pegar essa exceção é uma exceção de fila, é claro, e simplesmente retornar esse selvagem, identificando o vencedor. Agora, vamos trabalhar com nosso bloco Try. Primeiro de tudo, precisamos colocar todos os jogadores no cubo. Então, para todos, podemos dizer que para o loop for, há esse comprimento e na fila cada vez no entanto, podemos usar outra forma pagar MOOC, que é vamos nomear jogador. Quatro jogadores em camadas distintas, apenas enfileirariam esta camada. Então esta é outra forma do loop for. Podemos usá-lo quando temos uma mancha ou algo que podemos trabalhar com como, como uma variável e podemos incluir nesta fila usando este para loop. Agora, vamos para o nosso loop while. Enquanto a nossa fila tem mais de um elemento, vai apenas continuar trabalhando nele. Portanto, o tamanho da fila y é maior do que um. Este código seria executado. Então, primeiro de tudo, vamos imprimir a fila sem modificá-la. Então, seria apenas imprimir fila. E assim q. Agora usamos o loop de telefone de 0, del k. vamos apenas usar o enqueue q-dot, Q, Q. Então o que estamos fazendo aqui é, antes de tudo, vamos desenfileirar, indo para remover um elemento do , em seguida, armazenou-a mais uma vez usando o enfileiramento. Então podemos dizer que precisamos de objeto. Por exemplo, igual a Q dot dQ. Nós apenas desenfileiramos o elemento e depois armazenamos. Então isso é a mesma coisa, mas você pode simplesmente adicionar isso ao parâmetro do q-dot enfileirado. Uma vez que Enqueue aceita um objeto e este du, o dq retorna um objeto. Então, isto é o mesmo. Agora nós simplesmente depois de trabalhar com neste para loop em fila e desenfileiramento para k vezes. Agora, nós simplesmente desenfileiramos o último elemento, o primeiro nome do jogador. Então, podemos simplesmente visualizar desenfileiramento e você movê-lo da lista e digamos que está fora. Agora, terminamos com isso. Depois de executar este loop while, ainda temos um jogador e ele é o vencedor. Então, quando r igual a Q ponto dq e nós removê-lo da lista, claro que temos um erro porque este é um objeto e este vencedor é alterado. Então, e você sabe com certeza que este elemento é uma string. Então, podemos dar-lhe valor de string. Agora que terminamos com nosso código seria retornado por último. Então nós simplesmente aqui. Então este é o problema do Josephus. Vamos criar nosso método principal e executado. Mas vamos antes de tudo criar uma cadeia de matrizes, assim, e uma cadeia de nomes. Vamos dar um nome de camadas. E isso, vamos criar os nomes, por exemplo, Chris, Fred e John. Então esta é a nossa string e uma string e temos um inteiro k que sarja vem pedir ao usuário para entrar. Então vamos usar o scanner para digitalizá-lo. E vamos perguntar ao usuário e gays e armazenados o que quer que o usuário digitou e a variável k. Agora, o vencedor é resolver camadas e K. Então, como isso retorna uma string, podemos armazená-la em uma string e simplesmente imprimi-la. Agora, vamos em frente e executar este código. Então o que vamos conseguir é entrar k Por exemplo, vamos deixar. Primeiro, temos Chris, Alfred Chuang. Agora executamos k4 vezes. Então mudamos o Chris, o Alfred, John e o Chris, e acabamos com o Alfred na primeira posição. Então desenfileiramos Alfred e Alfred está fora. Agora. Ainda temos John e Chris. Então, realizamos esta operação quatro vezes. John, Chris, John e Chris, e acabamos com John na primeira posição. E John está fora. Então ainda temos um elemento ou um jogador, e ele é o vencedor. Então imprima que o vencedor é Chris. Então este é o problema do Josephus. Vejo você no próximo vídeo. 12. Lista de ligação de a lista de um único parte 1: Como matrizes, lista ligada é uma estrutura de dados linear. No entanto, os elementos nesta lista são vinculados usando ponteiros. Quando usamos arrays, temos algumas limitações. Por exemplo, o tamanho das matrizes é fixo. E quando precisamos inserir um novo elemento na matriz, é caro porque precisamos criar espaço para este elemento específico. Então este é um exemplo de uma LinkedList. Agora, estes são nós, então temos quatro nós neste exemplo. E cada nó é dados e endereço. Então, temos uma caixa para dados onde armazenamos nosso objeto elemento, inteiro, string, caractere, e assim por diante. E temos outra caixa para armazenar o endereço do próximo nó. Então podemos pensar neste endereço de um ponteiro. Não precisamos saber o número numérico exato aqui, mas deve apontar para o endereço do próximo nó. Então o LinkedList é esta lista. E quando dizemos isoladamente, Isso significa que os nós estão ligados entre si usando uma direção. Então não podemos voltar de 20 a 10, só podemos ir de 10 a 2030 e assim por diante. Então esta é a idéia de uma lista unificada. E vamos para o nosso espaço de trabalho Eclipse e criar um novo pacote. Nomeie a lista vinculada individualmente. E este pacote, como sempre. Vamos primeiro criar nossa classe de exceção. Agora, uma vez que esta lista é infinita, então podemos adicionar o que quisermos nesta lista e não temos um limite. Então vamos nomear essa exceção como exceção de lista vazia. Uma vez que não temos que nos preocupar se excedemos os elementos é que não temos nenhum limite. E nesta exceção, é claro, vamos estender a classe de exceção. Estende exceção como fizemos antes, e criar nossa lista vazia construtor, a mensagem chamada sopa com mensagem de parâmetro. Então esta é a nossa exceção de lista vazia. Vamos em frente e criar outra classe. Agora. Vamos ver, por exemplo, vamos criar Primeiro de tudo, a posição e esta interface vai ter apenas um método para obter o elemento. Agora, precisamos especificar que este é um tipo genérico. Então, quando dizemos d, Agora, este é um tipo de dados genérico. E ficamos com essa aula. Nós vimos como usá-lo em, deixe-me apenas criar outra classe que é nó. Então vamos nomeá-lo isoladamente ligado nó lista escutando com S naught. E como fizemos na posição, que simplesmente em D. E, claro, vamos implementar a posição da interface. E, e o método debug get elemento. E simplesmente, vamos criar algumas variáveis de elementos fora. Nós temos o elemento d. Nós também temos o S nada em si. A menos que o nome e o próximo Então temos de valores privados, variáveis fora. Então, para obter o elemento, simplesmente retornamos o elemento. Então este é o nosso método de elemento de dados. Agora também podemos querer retornar o próximo nó. Então, simplesmente dizemos que o público nevou ainda a seguir. E voltamos a seguir. Então temos o próximo nó dois. Agora também podemos querer definir o próximo nó. Por exemplo, vamos criar outro método para enviar para defini-lo. Então, anulo público, é o nome dele e ele vai tirá-lo, e ele vai tomar um nó e pagamento em seguida. Agora, vamos definir isto para ser igual a este. Então o que fizemos aqui foi definir o próximo nó. Temos aqui. É nomeado em seguida e defina tudo o que temos aqui. Então esta é a sub-rede. E se quisermos definir o elemento, temos o elemento d pode simplesmente criar outro elemento de conjunto vazio público. E neste caso, obtemos um elemento, o elemento e dizer este elemento ponto para elemento. Quando usamos isso, estamos dizendo que precisamos da variável local d a partir daqui e configurá-lo para o que temos, o parâmetro aqui. Agora, vamos criar nossa próxima interface. Esta interface seria, digamos que eu sou um Teslas. Então esta lista S é meio interface, absolutamente. E aqui temos todos os nossos métodos. Então, o primeiro método, e é claro que é um tipo genérico. O primeiro método, como geralmente, será o tamanho. Então booleano público está vazio. Agora nós ainda, nós também temos que responder. Agora, se formos a este exemplo. Então esta é a nossa cabeça e esta é a nossa vala. Então podemos querer armazenar um valor na mão. Então vamos criar um método que armazenado na cabeça. Então vazio público, inserir na cabeça e o que quer que seja o animal. Além disso, talvez queiramos vendê-lo na cauda. Então responda. Agora, uma vez que é ilimitado, então não temos que nos preocupar com a exceção da lista vazia. Qualquer exceção. Dessa vez, podemos querer remover um elemento usando a remoção de Pat. E neste caso, precisamos lançar a exceção lista vazia, uma vez que a lista pode estar vazia. E a mesma coisa ocorrerá se usarmos removido da cauda, lança uma exceção. Então, agora terminamos com nossa posição S list e vamos continuar com isso no próximo vídeo. 13. Lista de ligação de a parte 2: Então, agora que temos todos os nossos métodos, vamos criar uma nova classe e escrevê-los. Então, esta classe será uma classe de lista vinculada individualmente. E nesta classe vamos em primeiro lugar, ampliar ou implementar a lista S que criamos anteriormente. Mas, claro, em primeiro lugar, poderia ser genérico e implementado. Podemos ter os 0s e precisamos herdar os métodos. Agora temos todos os métodos e vamos trabalhar com eles. Então, em primeiro lugar, temos o tamanho. E antes disso, vamos criar algumas variáveis lá fora. A primeira variável é os nós. Como dissemos, temos dois nós, a cabeça, que será o primeiro elemento ou o primeiro nó. Então este é o nó principal e a cauda está no último nó. Então temos dois nós como não com E. E também temos sinais como de costume. E vamos criar o StringBuilder para usá-lo para o método toString. Agora temos também a lista república construtor uniformemente vinculada. E aqui, vamos instanciar a cabeça e a cauda para ser igual a. Então, a primeira vez que criamos a lista uniformemente vinculada, temos a cabeça e t igual a nenhum. E o tamanho será igual a 0. E vamos criar o StringBuilder. Agora também temos aqui. Então este é o líquido, o construtor. Vamos começar com a ciência. Em primeiro lugar, para o tamanho, simplesmente devolvemos o tamanho. Para o vazio está vazio, nós simplesmente retornamos como de costume. Se o tamanho for igual a 0. Agora vamos passar para os outros métodos. Eles são muito mais complicados e precisamos trabalhá-los lentamente. Então, o primeiro método é inserir na cabeça. Então vamos voltar ao filme. E aqui podemos ver quatro nós. Suponha que precisamos adicionar um nó aqui. Suponha que precisamos adicionar uma auditoria com um elemento 0. Então, a primeira coisa que precisamos fazer é criar o nó e, em seguida, vinculá-lo a este nó. Depois disso, precisamos mover a cabeça já que eles tinham estava aqui. Agora precisamos movê-lo para aqui. Então vamos dar a cabeça. A nova posição, que é o novo nó. Então vamos voltar aqui e implementado. Então a primeira coisa que precisamos fazer é criar esse nó. E vamos nomeá-lo conhecido como nó. Será igual a novo nó, este nó usando e. E o próximo nó é, como de costume, temos isso, esta lista vinculada. Se criarmos um novo nó aqui, o próximo nó será o cabeçalho. Agora, ainda temos e vamos ver o que é. Então sim, precisamos criar o construtor. E o nevado que esquecemos de criar. Então vamos voltar ao S nada e criar nosso construtor, que é conhecimento público. E estou servindo como elemento. E levará dois parâmetros, a0 e a1. E elemento será igual a E, max seria igual a. E agora podemos voltar à nossa lista unida. E nós, ok, agora depois disso, depois de criar isso como nó, precisamos verificar se a lista está vazia. A lista está vazia ou podemos simplesmente dizer que F está vazia. Se este for o caso, então não temos nenhum elemento neste nó. Então o primeiro elemento que vamos adicionar será a cabeça e a cauda. Então, novamente, diga que DE é igual a mu nada. Em ambos os casos, se estiver vazio ou não, a cabeça será igual a isso. Então este f apenas executar esta linha. E eles tinham em ambos os casos seria igual a esta nova assintota. Depois disso, precisamos incrementar o tamanho desde que adicionamos um novo elemento e precisamos inseri-lo no SPS StringBuilder para que possamos acrescentar. Mas quando usamos append, acrescentamos ao fim. No entanto, precisamos adicioná-lo no primeiro como o primeiro elemento. Então vamos precisar usar inserção, bem, precisamos inseri-lo na posição 0? E o que precisamos responder? Precisamos inserir este novo nó e este novo elemento que é E. E esse é o espaço em branco aqui. E vamos conversar. Então isso é para inserir na cabeça. Agora vamos trabalhar com inserção na cauda. Então, a primeira coisa que precisamos verificar, inserir uma cauda é também se ele está vazio. Agora vamos criar o novo nó AST. Como nó. O novo nó como nó, o valor de E. E assim o próximo nó, como você pode ver nesta imagem, é nulo. Por exemplo, se você quiser adicionar um elemento aqui, um ODE. Então precisamos apontar daqui para o novo nó. E agora a tabela seria o último nó. E este último nó não apontará nada. Não será. Então vamos voltar para aqui e trabalhar. Então aqui temos inserido no ele. Primeiro de tudo, precisamos verificar se está vazio. Se está vazio, então é também o poderia esta nova nevou. E em ambos os casos, será igual ao astronauta. Caso contrário, se não for o caso, se não estiver vazio e já temos um elemento. Então este elemento, o último elemento, que é o detalhe aqui, vamos apontar para este nó. Então, como fazemos isso? Se não estiver vazio, então cauda que sentou próximo membro, criamos um método para definir max e o delta setText será o novo nó. Agora, a cauda seria este novo nó. Como dissemos. Nós incrementar o tamanho e anexado no final do construtor de cordas ou usando qualquer especificação ToString LAS, ainda temos removido do chapéu, removido da cauda. E você pode adicionar, chegar em frente e obter cauda para dar uma olhada no que temos na cabeça e cauda. E, claro, nosso último método, esse método toString. Então, trabalhamos neles no próximo vídeo. 14. Lista de ligação de a parte 3: Ainda temos alguns métodos aqui. Então, vamos começar com o método removido da cabeça. Em primeiro lugar, vamos excluir isso. E a primeira coisa que vamos fazer é verificar se a lista está vazia. Então, se estiver vazio, então precisamos lançar a exceção lista vazia. Digite a exceção e dizendo que a lista está vazia. Se este não for o caso, então continuaremos sem lançar esta exceção. Agora, o elemento que vamos retornar que armazená-lo em uma variável chamada para retornar. E é o elemento que está na cabeça que obter elemento. Então agora temos este elemento e armazená-lo e retornar. Agora, se precisamos verificar se a cabeça é igual a cauda outro n, Em outras palavras, que só temos um elemento nesta lista, então tanto cabeça e cauda será igual a null neste caso. Então f é igual a k, então vai simplesmente dizer que AD é igual a, é igual a nove. Então, movemos esse elemento para ele. Só tínhamos um elemento e removemos isso. Então agora a cabeça e a cauda serão iguais a nulos. Caso contrário. Se este não for o caso, então, desde que removemos da cabeça, foi remover este elemento. Agora, em vez de apontar para este elemento, agora a cabeça será este nó. Então precisamos remover os ponteiros da cabeça daqui até aqui. Então, para fazer isso, vamos simplesmente dizer que a cabeça é igual a cabeça que a seguir. Próximo. Então é isso. E, claro, uma vez que estamos removendo um elemento, precisamos diminuir o tamanho em um e excluir do StringBuilder, como o lead do StringBuilder. Precisamos começar com 0 e, e com o que temos aqui. E este objeto, é para retornar à força e o comprimento dele mais um ponto de contagem de pé espaço em branco. Vamos apagar e, finalmente, voltar para voltar. Agora isso é inferido, removido do sem cabeça. Continue com ela se mudar de Taylor. Agora aqui. Mesma coisa. Primeiro de tudo, precisamos verificar se está vazio, está vazio, então lançamos uma exceção dizendo essa lista. E, caso contrário, continuamos. Precisamos armazenar o retorno igual ao que temos em detalhes desde a remoção da cauda que obter elemento. Agora, nós também precisamos verificar se a cabeça é igual a k. em outras palavras, é cabeça e caudas. O mesmo nó. Então, temos apenas um elemento. Então. A cabeça e a cauda serão iguais a null e a lista estará vazia. Então, se a cabeça é igual a, nós simplesmente dizemos que tinha que ser igual para levar a isso. Caso contrário, só vou trabalhar com isso já que estamos nos mudando de hoje. Então vamos voltar para a nossa foto aqui. E vamos ver, por exemplo, se queremos remover este nó. Então removemos isso. Agora, precisamos dizer que a cauda é esse nó. E para fazer isso, lembre-se, esta é uma lista unificada. Não podemos voltar daqui para aqui. Então o que precisamos fazer é criar um loop e passar por todos os nós até chegarmos a este nó. Então não queremos o último nó, precisamos do antes dele. Então, para fazer isso, vamos voltar ao Eclipse e implementar esse código. Então, antes de tudo, precisamos criar um novo nó que não seja a cabeça e a cauda. Então aqui temos a cabeça e aqui temos meio detalhado para criar um limite de atlas. E ele passará por todos os nós até chegar a este nó. Então aqui temos um novo nó, D. Vamos nomear uma cidade no primeiro, na primeira posição. Está na cabeça. Enquanto úmido não é igual ao detalhe, este código será executado, modo que será igual a eles, mas obter o próximo. Então, toda vez que verificamos se a próxima nota é a cauda, se não é a cauda, então vamos para o próximo nó. E chegar a este. Nós, quando chegarmos a este, verificamos se o próximo nó é a cauda. Sim, então vamos sair deste loop enquanto. Agora temos nossa posição, nossa nova posição que está aqui, e a umidade está apontando para este nó. Portanto, podemos simplesmente dizer que eles seriam iguais ao tempo. E claro, já que estamos aqui e não queremos mais esse árabe, simplesmente damos esse valor, um valor nulo. Então podemos simplesmente dizer que se sentou ao lado de um valor de nulo. Não precisamos mais apontar para nenhum nó depois da cauda. Agora que terminamos com este ouro, podemos simplesmente diminuir o tamanho e varrer, remover um elemento, e precisamos excluí-lo daqui, do StringBuilder. Agora, vamos ver como podemos excluir. Por exemplo, se agora StringBuilder, temos 1234 e precisamos remover da cauda. Então o que vamos fazer é saber qual é o comprimento disso e menos o comprimento do valor final. Por exemplo, é 12 com o espaço em branco 34567. Então é sete menos um, que é seis. Então vamos começar nesta posição e terminaremos o comprimento. Então, como fazemos isso? Nós simplesmente direita comprimento do ponto sba menos o que temos neste elemento para retornar a string, que nono menos1. E terminaremos com SBY, esse comprimento. Agora nós excluímos do StringBuilder e simplesmente retorná-lo. Então este é o fim para o removido de Dale. E vamos continuar com a outra mensagem. Enviamos, pegamos a cabeça e pegamos a cauda. E, claro, o último método que é uma string. Então vamos começar com o “get”. E nós simplesmente forçamos, nós vamos lançar a exceção lista vazia. Se estiver vazio. Vamos lançar esta exceção. E esta exceção de que a lista está vazia. Agora, caso contrário, não é o caso. Então nós simplesmente retornar cabeça que get elemento. Vamos copiar este código e criar “get tail”. Então, em vez de obter cabeça ou cauda e verificar se ele está vazio, caso contrário, temos uma cauda que obter elemento. Agora, o último método é cadeia pública para cadeia de caracteres. E uma vez que usamos o StringBuilder, pode simplesmente retornar, ele, retorna Sb à força. Então estes são os nossos métodos e agora estamos prontos. Podemos usá-los em uma aula de retórica no próximo vídeo. 15. Aplicativo de lista de lista de referência de único para o único: Agora que temos todos os nossos métodos, vamos em frente e usá-los em nossa classe de motorista. Então esta é a nossa aula de motorista. E esta classe, como de costume, é o método principal. Vamos criar a lista uniformemente vinculada de inteiros. E o mesmo que individualmente ligado lista SLL. Você acha que LinkedList. E primeiro de tudo, vamos imprimir o tamanho dele. Então, como tamanho do ponto, vamos em frente e executar este código. Contagem de CO2 para acontecer. O tamanho é 0. Agora vamos adicionar alguns elementos. Então eu disse que inserir na cabeça um, SLL, que inserir em para ajudar SLL inserção ponto em tinha três. Vamos imprimir a lista aqui. E agora vamos ter 12. E depois disso inserimos na cabeça o elemento três. Então esta é a cabeça, então temos 312. Agora, se inserirmos no Tate, por exemplo, inserir a data número um, e depois imprimi-la mais uma vez. Vamos pegar o 3121. Agora, vamos verificar aqui. Se está vazio, está vazio, e vamos verificar mais uma vez. Está vazio. Execute este código, ficamos verdadeiros no início e depois de adicionar alguns elementos, obtemos falso. Agora, ainda temos alguns métodos. Por exemplo, vamos remover da cabeça. Então, podemos simplesmente salvar esse ponto SLL remover da cabeça. Imprima SLL. Temos aqui. Portanto, este erro é exceção não tratada, precisamos lançar esta exceção, sabe exceção vazia. Agora vamos em frente e executar este código. Não tenho mais uma terra. E temos um senso de um para um, removemos esse elemento da cabeça. Vamos fazer a mesma coisa à data. Então, como LL remover da cauda e imprimir uma última vez. Vamos pegar um depois de remover o último elemento. E em todos os nossos exemplos usamos inteiro. No entanto, podemos escolher qualquer tipo que você quiser. Por exemplo, a corda dupla, qualquer coisa. E funcionará da mesma maneira. Então este é o fim para este vídeo. Vejo você no próximo. 16. Stack de bases.: Agora, uma coisa que podemos fazer esta lista unificada é criar um passo. Então aqui temos as aulas, que é uma sala de 100 para esta etiqueta. Então vamos criar nossa interface de pilha. Diga o nome. E a pilha seria genérica. Tipo. Vai como de costume. O booleano está vazio. E o empurrão. O que vamos empurrar o elemento b. B também que colisão. E, claro, precisamos criar a classe de exceção, mas esta tag, então pilha exceção. E como de costume estender exceção com o construtor. Mas esta mensagem, mas esta mensagem e terminamos com esta exceção, usaria com Bob e Top, então sabe que exceção. E aqui também sabe exceção. Mas a diferença entre usar listas vinculadas isoladamente e em um é que quando precisamos empurrar, não temos um limite já que a lista vinculada individualmente não é limitada. No entanto, quando usamos matriz, lembre-se que usamos para jogar aqui também uma exceção desde que podemos estar excedendo o limite do dia. Então este é o fim para o StatPlus. Agora vamos em frente e criar nossa pilha baseada em lista vinculada individualmente. Então esta é uma lista unificada baseada. E esta lista unificada que temos. Então os métodos que criamos na interface. Então, vamos simplesmente implementar a interface de pilha. E no canto superior direito, todos os métodos. Vamos simplesmente substituí-los de E por adicionar métodos implementados e os métodos. Agora, a primeira coisa que vamos fazer é criar a lista uniformemente ligada fora antes do construtor, privado lista uniformemente ligada de D. Agora vamos criar um construtor, lista pública uniformemente ligada com base nisso. E neste, neste construtor vai simplesmente. Dê um sela definido você nova coisa, a lista ligada. E, claro, aqui temos assim. Então é isso e isso é separá-los. Então este é o nosso construtor. Agora vamos para a ciência. Ao usar o tamanho. Podemos simplesmente retornar a lista vinculada individualmente usando está vazia. Também podemos usar o método isEmpty disponível e o SLR. Então, vamos simplesmente devolver TUDO o que está vazio. Agora, o que estamos fazendo aqui é que criamos como uma lista vinculada. E lista vinculada. Temos todos os métodos. Nós inserimos cabeça, inserir, remover, obter, e, claro, tamanho e vazio, para que possamos usá-los simplesmente. E nossa pilha baseada em lista vinculada individualmente, porque tamanho e é Vazio são os mesmos. Agora, quando formos para Bush, vou avançar. Então, usamos o empurrar da cabeça ou inserir na cabeça e a classe LinkedList isoladamente. Então, para fazer isso, nós simplesmente dizemos SLL, mas inserir no que temos aqui. E isso é basicamente agora. Primeiro de tudo, vamos usar um bloco tentar e pegar. Então tente se algo aconteceu, apenas pegue. E esta deve ser a lista vazia. Se estiver vazio. Se a lista estiver vazia, então o que vamos fazer é lançar a nova exceção que criamos, que é a exceção de pilha. Então, neste, criamos uma nova exceção dizendo que a pilha está vazia. Agora, esta é a pegadinha. Vamos voltar para tentar escrever algum código aqui. A primeira coisa que vamos fazer é criar o objeto. E também precisamos remover do chapéu. Então, nesta pilha, como dissemos antes, adicionamos a primeira e a última saída. E podemos dizer que N é o primeiro a sair. Por isso, temos de avançar. E é ao mesmo tempo, se quisermos bombear, precisamos estourar da cabeça. Então ponto SLL, retire do chapéu. Agora, depois de remover isso, simplesmente retornamos. E acabamos com o pub. Vamos apenas ir para conectar método que é topo. Então, como fizemos e tentar pegar, pegar a exceção lista vazia. Se temos uma exceção ativista, então lançamos uma nova exceção pilha. E diremos que a pilha está vazia. Agora, se este não for o caso, então nós apenas Seja um objeto para retornar e usar o método get de SLL, mas obter ajuda e retornar este objeto. Então este é o método de topo. E agora terminamos com todos os métodos à frente e criamos uma classe para usá-los. Vamos nomeá-lo pilha baseada em SLL. Então, nesta classe, como de costume, temos o nosso método principal e que é criado SLL baseado inteiro escuro e esmagar-lo SLL b igual a novo inteiro pilha. A primeira coisa que vamos fazer é criar um empurrão, empurrar um elemento que é um, ser o Bush e o regime Bush. Vamos em frente e imprimir o tamanho, tamanho e este código. Veja o que conseguimos. Então temos três. Agora esquecemos de criar o método toString. Podemos simplesmente criá-lo após esse método. E esse método será simplesmente o SLM. Bom. Agora vamos voltar aqui e executar este código mais uma vez. Vamos pegar três. Agora, se formos em frente e imprimir SLM b terá três para um, já que estamos empurrando na pilha. Então, primeiro, empurramos um, depois dois, depois empurramos três. Então colocando-os em D. Agora, se nós bombear a partir deste, nós vamos obter SLL B que nós temos o número três aqui dizendo que exceção não tratada, nós precisamos lançar esta exceção aqui, lança a exceção e executar este código terá três. Agora, se formos em frente e imprimi-lo mais uma vez, vamos chegar a um. Vamos verificar se está vazio. Isso está vazio, ele deve retornar falso, já que temos dois elementos. E por último, vamos usar o método das nádegas. Então SLL v dot. E devemos pegar o número 222 é a primeira posição. Então isso é para a pilha baseada em lista vinculada individualmente. Agora, implementamos pilha usando três métodos. O primeiro é usando matriz, e o segundo foi usando a pilha Java embutida. E, por último, usamos lista vinculada individualmente para implementar pilha. Então este é o fim para este vídeo. Vejo você no próximo. 17. Lista de ligação com um link particular parte 1: Vamos passar para a lista duplamente ligada. E lista duplamente ligada é uma estrutura de dados vinculados que consiste em um conjunto chacais ligação chamados nós. Cada nó contém três campos para vincular campos ao nó anterior e ao próximo. E, claro, um campo de dados. Então, por exemplo, esse nó contém um campo de dados para armazenar dados. E, por exemplo, suponha que temos variável chamada b e dois nós, dois campos para apontar para o nó anterior e para o próximo nó. E, claro, temos no primeiro campo, no primeiro nó, nenhum, e no último campo, o último nó e também não. E aqui temos a cabeça apontando para o primeiro nó e o comerciante apontando para o último nó. Então vamos em frente e implementar este programa aqui. Então vamos criar um novo pacote e nomeá-lo duplamente LinkedList. E neste pacote, vamos começar com a criação da nossa interface de posição. Como fizemos com uma lista unificada. Temos a nossa posição de interface. E nesta posição será genérico, tipo genérico. Temos apenas um método, obter elemento. Então esta é a nossa classe de posição. Vamos criar outra classe. Gostaria de notar classe é chamado D, vez que é uma lista duplamente ligada, o nó. E nesta classe, deixe-me apenas, sim, ok, então aqui vamos implementar a interface de posição. Então, simplesmente escrevendo implementa posição. E é claro que você não precisa substituir esse método. Obter elemento. Então vamos criar uma variável fora deste nome do elemento. Nós. Precisamos de dois nós aqui já que estamos trabalhando com o anterior e o próximo. Então vamos nomeá-los, denotar o anterior. E o próximo. Agora, neste método, o que vamos retornar o elemento, nós simplesmente retornar o elemento aqui. Neste caso. Agora, vamos criar alguns outros métodos. Por exemplo, precisamos obter o nó anterior. Portanto, será o esquecimento público e também ser do tipo d nada. E aquele anterior. Neste caso, basta retornar o raio, obter o próximo. Então, neste caso, o nó para o próximo nó, e nós simplesmente retornar próximo. Agora, podemos querer configurar o nó anterior e o próximo. Então vamos criar um método para configurá-los. Então, ele será do tipo vazio, já que estamos apenas configurando esses nós. Então definir anterior. E temos de lhe dar o seu nome, o seu anterior. E simplesmente definir esta terceira variável local total anterior IE anterior para ser igual ao pedômetro para desvalorizar inserido pelo usuário para o programa. Então, será igual ao anterior. E precisamos criar outro método, métodos, método para definir a seguir. Como fizemos nos dois anteriores, seria este ponto próximo igual ao próximo. Então, agora terminamos com a configuração e obtenção anterior e seguinte. Agora ainda temos apenas um método que é definir o elemento. Então, será um elemento vazio e elemento. E este elemento é igual a elementos. E agora terminamos com essa aula. Vamos em frente e criar alguma classe de exceção. Então, como de costume, em primeiro lugar, temos a exceção de lista vazia. Então eu iria lista pode estar vazio. Então vamos criar uma exceção. Mas essa exceção de lista vazia. E ele só vai estender exceção com a criação do construtor e a mensagem de exceção lista e essa mensagem. Então esta é a primeira exceção. Agora vamos criar algumas outras exceções e falaremos sobre elas mais tarde. Portanto, também temos exceção de posição inválida. E será o mesmo. Ele estende exceção. E então a última exceção que vamos criar é a exceção de violação de limites. Então, essa exceção tornará mais fácil para nós detectar e colocaremos essa estrutura de dados de lista duplamente vinculada. Exceção de violação de limites. E é claro que eu deveria estender a classe de exceção. O construtor. O construtor. Agora, com feito com essas classes de exceção. E podemos ir em frente e trabalhar com nossa lista duplamente vinculada. Como fizemos com uma lista vinculada individualmente, criamos uma interface para nomeá-la lista S. Então aqui vamos criar a lista D, uma vez que é uma lista duplamente ligada. Então, vamos criar esta lista D, e então vamos substituir todos os métodos desta interface em nossa classe lista WMA. Então vamos fazer isso no próximo vídeo. 18. Lista de ligação com um link de dois duque parte 2: Agora, antes de criar nossa classe delist, vamos entender essas exceções. Então, primeiro de tudo, temos a exceção de lista vazia. E esta classe nesta exceção, quem vai verificar se a lista está vazia? Então só vamos lançar esta exceção se a lista pode estar vazia. A outra exceção, a exceção de posição invertida. Então, por exemplo, se o usuário está inserindo um nó, ele não está na lista, então vamos lançar esta exceção de posição inválida dizendo que o nó não é parte da lista ou nós não e identificar o nevado. E, por último, a exceção de violação de limites. Então, ao passar pela lista, por exemplo, se vamos usar um próximo método, vamos passar pelo nó e acabamos com o último nó. E usámos mais uma vez, na outra. Então vamos lançar essa exceção de violação de limites, já que não temos nenhum nó após o último. Então estas são as nossas três exceções, óculos. E vamos em frente e criar a classe denote. Então, neste caso, este é o Denote, a lista, desculpe. E esta classe será T. E isso cria um método. Primeiro de tudo, temos, como de costume, booleano está vazio, está vazio. E nós temos o método para obter o primeiro elemento, o primeiro nó. Então, será do tipo denota T e será o primeiro. Então aqui a lista pode estar vazia. Então o que vamos fazer é lançar a exceção da lista vazia. Agora, também podemos criar um método para obter o último nó na lista. E, claro, também pode estar vazio. Então vamos jogar isso até a sucessão mais uma vez. Agora, deixe-me ver o que está acontecendo aqui. O corpo método, sinto muito, escondido. Precisamos criar a interface e a classe de matemática da interface. E cancelou isso. Vamos criar o método ao lado para obter o próximo nó. Então aqui não temos nada para conseguir o próximo. Vamos nomeá-lo em seguida. E aceitará uma denota. de aceitá-Lo E depoisde aceitá-Lo, aceitando este nó, temos dois problemas aqui. Primeiro de tudo, esse nó pode não ser um dos nós na lista. Então, o que vamos jogar. A exceção de posição inválida. Uma vez que esta posição que entramos aqui pode ser inválida neste caso, vamos lançar esta exceção. Agora. Também podemos encontrar uma exceção de violação de limites, já que vamos tentar acessar o próximo nó. Suponha que este nó seja o último, para que não possamos acessar o próximo nó. Então, para corrigir isso, nós simplesmente desenhamos a exceção de violação de limites. Agora também temos o anterior. Então temos o mesmo DNA. Os lançamentos finais, exceção de variação inválida e limitada. Depois disso, temos dois métodos para remover e substituir. Então, primeiro de tudo, vamos criar o movimento. Então vamos remover um elemento. Então é div. Vamos nomeá-lo, você se moveu, e então vamos removê-lo do nó. Vamos nomear um deem e removê-lo. Talvez este nó não seja um dos nós na lista. Então o que vamos lançar é a exceção de posição inválida. E vamos lançar a mesma coisa se quisermos substituir, por exemplo. Observe que aqui pode não ser também um dos nós na lista. Então, vamos colocar em posição violeta a seguir. Agora vamos inserir. Podemos inserir em primeiro lugar, inserir finalmente, e inserir antes de um nó, e inserir depois. Então vamos voltar para a nossa foto aqui. Por exemplo, podemos inserir aqui entre a e b. Assim, podemos usar tanto inserir antes de b ou inserir após a. E você também pode responder no primeiro e inserir último. Então vamos voltar e criar esses métodos. Primeiro de tudo, vamos criar o nó e inserir primeiro. E nós vamos aceitar e elemento d. Em seguida, a mesma coisa na classe, inserir o último E, e vamos nomeá-lo E. Então temos inserir antes de um nó e inserir depois de um nó. Então, agora insira o nó. E vamos nomeá-lo, inserir antes. Agora vamos aceitá-los. Então vamos saber qual nó inserir antes. E vamos aceitá-lo aqui. Vamos citar um d e, claro, o animal que em relação a inserir. Então este é o elemento d. Agora denotar que nos é dado, pode ser e válido. Então é claro que você vai lançar a exceção de posição inviolada. A mesma coisa com a inserção em um nó específico, insira após o sname que D, D, E e E terá o lance da exceção de posição inválida mais uma vez. Então, é isso para a turma. Estes são todos os nossos métodos, por enquanto. E no próximo vídeo, vamos implementá-los na classe lista duplamente vinculada. 19. Lista de ligação com duque de uma lista de ligação parte 3: Então temos agora no método na lista D interface. Vamos criar a classe LinkedList duplamente. Então lista duplamente ligada. E nesta classe, vamos implementar essa interface. E, claro, vamos substituir todos os métodos para me deixar usar isso e adicionar métodos não implementados. Então vamos ter todos os métodos aqui. Primeiro de tudo, vamos criar nosso construído e algumas variáveis fora. Então, como de costume, temos o tamanho e temos dois nós. Agora, o D, vamos chamá-los de cabeçalho e trailer. Agora podemos criar nosso construtor. E neste construtor vai configurar nosso cabeçalho, fracasso e suicídio. Tão tamanho. Então temos cabeçalho e Taylor. Então vamos voltar a esta imagem. Este é o nosso cabeçalho, e estes são os nossos dados. Primeiro de tudo, não temos nenhum nó nesta lista duplamente vinculada juntar-se criando o cabeçalho e comerciante, o cabeçalho deve apontar para o trailer e o alfaiate deve apontar para o cabeçalho. Então aqui podemos dizer que esta caixa aponta para o alfaiate e a falha, a primeira caixa deve apontar para a cabeça. Então vamos voltar e ver como podemos implementar isso. Primeiro de tudo, nosso cabeçalho será igual ao novo nó E, nó. Nó E. E em primeiro lugar, nós temos, como dissemos, na classe de posição, deixe-me ver onde nosso denote. Temos elemento anterior e seguinte, mas esqueceu de criar o nosso construído. Então isso foi criado. E neste caso, o construtor será de três parâmetros. Ele vai tomar d nó, nó D. Vamos nomeá-lo soapy anterior eo elemento e. E , por último, o d nada, que é o próximo nó. E, claro, vamos colocá-los aqui. Assim, o elemento será igual a um, anterior seria igual a b. E, por último, próximo. E claro que ele identificou isso. Agora podemos voltar à nossa nota, e aqui precisamos criar o próximo e elemento anterior. Então, em primeiro lugar, já que não temos nenhum anterior. Em seguida, definimos como Nulo. E depois disso vamos criar nosso trailer. Agora, vou Taylor, como dissemos, deve apontar para o cabeçalho. Então nenhum, nenhum. E também dissemos que o cabeçalho também deve apontar para alfaiate. No entanto, aqui ao criar o cabeçalho, não tínhamos nenhum adaptado para. Então, em vez disso, vamos apontar aqui. Cabeçalho que sentou próximo E vamos definir ao lado do trailer. Agora, terminamos com este método e o construtor, quero dizer, e podemos trabalhar com o nosso método. Então, primeiro de tudo, temos o tamanho simplesmente retornará o tamanho. Então temos o SMT e como de costume determinado tamanho igual a 0. Agora podemos trabalhar com nossos métodos mais complicados. Então, primeiro de tudo, temos o primeiro método e como dissemos, ao extrair um nó, ele pode listar, pode estar vazio. Então, para estar no lado seguro, lançamos essa exceção de lista vazia. Agora vamos criar esse método. Então aqui temos, não queremos extrair a primeira denota. Então, primeiro de tudo, vamos verificar se ele está vazio para que a lista esteja vazia, então vamos lançar uma nova exceção vazia. E neste caso, vamos dizer que a lista está vazia. Agora, este não é o caso. Então vamos simplesmente retornar o primeiro modo. Como acessamos o nó disperso? Vamos voltar ao pin. E podemos ver que sempre que temos alguns nós na lista, o primeiro, o cabeçalho vai apontar para o primeiro nó. E o comerciante que vai apontar neste último nó. Então o eixo, o primeiro nó, nós simplesmente, vamos voltar. E no Eclipse, nós simplesmente retornar o que temos no cabeçalho que chegar ao próximo nó para o cabeçalho é o primeiro nó na lista. E a mesma coisa aqui. Primeiro de tudo, vamos verificar, então deixe-me copiar isso e colar aqui. Se este não for o caso, então vamos simplesmente retornar carcereiro que obter o nó anterior. Então, depois de obter o anterior, vamos voltar a esta foto e verificar. Então aqui temos nosso trailer. O último nó na lista é o nó antes disso mais tarde. Então, o que quer que o Taylor esteja apontando é o último nó nesta lista. Agora vamos voltar aqui e vamos trabalhar com os outros métodos mais tarde nos próximos vídeos. 20. Lista de ligação com um link de duque de parte 4: Vamos agora passar para o próximo, anterior e remover, substituir e assim por diante. Então, aqui no próximo método que pode lançar uma exceção de posição inválida e a exceção de violação de limite. Então vamos ver o que é uma exceção de posição inválida é para nós. Assim, por exemplo, se o nó inserido é nenhum, é evento a não é uma posição válida. O, é claro, se entrarmos no cabeçalho do nó ou trailer, também não há uma posição válida. E, finalmente, se este nó está apontando para um nó seguinte ou anterior, como podemos ver aqui, todos os nós nesta lista devem apontar para o próximo e o nó anterior. Somente o cabeçalho e o trailer podem apontar apenas em um nó. Então o cabeçalho está apontando que o primeiro e o Taylor no último. E aqui não podemos ter nenhum. E a mesma coisa aqui. Agora vamos voltar aqui. Então vamos criar outro método que verifica para nós as posições inválidas com as quais podemos trabalhar. Então ele é criado antes deste próximo método. Isso seria privado, já que só estamos usando nesta aula. Então vamos chamá-lo de “vazio privado”. E só irá verificar a posição e a posição deste t nada. E, claro, deve através da exceção de posição inválida. Primeiro, vamos verificar se D não é nenhum. Então vamos lançar a nova posição inválida. Exceção de posição inválida. Deixar exceção de posição. E, claro, vamos escrever curado que nulo não é uma posição válida. E deixe-me copiar isso e colar duas vezes. E se D é igual ao cabeçalho, então vamos também entrar lançar a exceção posição inválida, mas dizendo que o cabeçalho não é uma posição válida. E também o trailer vai jogar carcereiro não é uma posição válida. Então a última coisa que vamos verificar é se este nó D ponto próximo é igual a nulo. Ou o anterior também é igual a null, então isso não faz parte da lista. Então vamos jogar sua posição inválida. Exceção, dizendo que o nó não é parte de um acordo é. Agora terminamos com este método. Podemos usá-lo em nossos métodos aqui. Então, antes de tudo, antes de fazer qualquer coisa, precisamos verificar a posição. Então ele chama esse método. Então, se algo ocorreu como se uma exceção de posição inválida de bom simplesmente jogá-lo usando esta posição de camarada. Então ele vai entrar para verificar. E se nada acontecer, então você pode trabalhar como de costume. E deixe-me ver qual é o problema que devemos devolver. Claro, vamos devolvê-lo no final. Então, antes de tudo, já que vamos obter o próximo nó, primeiro, vamos verificar se o próximo é mais tarde. Se a porta ao lado é uma cauda, então podemos pegar o próximo nó. Envia Taylor não faz parte da lista. Então vamos lançar a nova exceção de violação de limites, dizendo que não pode se mover como a última nota. Então, quando esta condição é satisfeita, então estamos no último nó e não podemos acessar depois disso. Este não é o caso. Então nós simplesmente retornamos o próximo. Agora, vamos fazer a mesma coisa com o “Get Anterior”. Mas vamos verificar se o nó anterior é o cabeçalho. E este caso, não podemos acessá-lo já que não faz parte da lista. Então, primeiro de tudo, precisamos verificar a posição. Se estiver tudo bem , podemos continuar. Se anterior for igual a, neste caso, a exceção de violação de limite que escrevemos, uma exceção de violação de limite de nova linha dizendo que não pode mover o primeiro nó. E aqui, este não é o caso. Basta retornar os estudos anteriores, os métodos próximos e anteriores. Vamos continuar com o nosso método de remoção. Vamos voltar. E vamos supor que precisamos remover esse nó. Neste caso. Primeiro de tudo, precisamos cortar esses ponteiros daqui e aqui e criar novos ponteiros. Então um vai apontar para o mar. E C vai apontar para a. Então vamos implementar isso em nosso código. Para remover, simplesmente criamos. Em primeiro lugar, precisamos verificar a posição do nó. Se tudo funcionar corretamente, então podemos continuar. Então precisamos voltar. Vamos criar um retorno de objeto. E neste caso, será o elemento ponto-ponto. Agora, antes de definir esses campos em não, precisamos definir esses dois campos em a e C para apontar um para o outro. Então, como acessamos um? Podemos simplesmente escrever esse nó d ponto obter anterior. Então, quando dizemos que não ficou anterior, estamos recebendo um e precisamos definir um para estar apontando para o mar. Então, como você faz isso? Podemos simplesmente escrever d que fica anterior. Agora, usando obter anterior, temos um. O que vamos fazer é definir este campo para apontar no mar. Então que se sentou a seguir. Vamos definir o próximo. E como acessamos c por um, o ditado que B, que começa a seguir. Então o que é, o que devemos escrever aqui é velocidade ou DDL GetMax, desculpe. Não ser o próximo. Então deixe-me repetir. Primeiro de tudo, acessamos um usando DDL obter anterior depois de acessar o anterior. Aqui. Depois de dizer acidentalmente este a, nós simplesmente definir este campo para estar apontando para o nó após B, e nós acessamos que usando B quer obter próximo. Agora ainda temos que definir este campo para estar apontando para um. Então, como fazê-lo com simplesmente acessar o próximo elemento, o próximo nó. E devemos definir o anterior para o anterior. Então o que fizemos aqui foi acessar o próximo elemento, o próximo nó. Então, usando o ponto get próximo, temos C. E o que devemos, o que devemos armazená-lo aqui no anterior. Então vamos definir anterior para estar apontando para um e o que é um? A é d, D obteria anterior. Agora, depois de fazer isso, podemos simplesmente definir próximo de D igual a nulo e o anterior igual a nulo, e simplesmente decrementando tamanho e deter nome para retornar. Então é assim que removemos o nó da lista. Isso é um pouco complicado quando se trata de definir e chegar aqui. Mas se trabalharmos nisso passo a passo, será simples. Então vamos continuar com a substituição no próximo vídeo. 21. Lista de listagem de ligação com duque de um link de parte 5: Agora vamos continuar com o método de substituição. Primeiro de tudo, precisamos verificar se este nó é válido. Então vamos usar a posição de bate-papo. A posição é válida. Então você pode continuar. Primeiro de tudo, precisamos criar um objeto, retornar um elemento para retornar, e retornar o que temos em D. Então vamos definir o elemento em dois ser igual a e. E aqui temos algo faltando na substituição método. Então vamos voltar ao nosso detesto e consertar isso. Quando precisamos substituir, Precisamos entrar em um nó e um elemento. Vamos voltar aqui e consertar isso. Agora, podemos adicionar este elemento aqui e retornar o que temos o objeto para retornar. Agora, vamos começar com o método de inserção. Primeiro de tudo, temos a inserção primeiro. Então deixe-me criar o nó. Temos o elemento aqui no parâmetro. Então, tudo o que precisamos fazer é criar ignorado o e vamos nomeá-lo em seu denote. Neste caso, o seria igual ao ânodo e à nota. E levará três parâmetros. Agora deixe-me voltar a esta foto. Suponha uma necessidade de criar um novo nó aqui. Este novo nó deve apontar para este nó a, e um deve também apontar para este nó que eu preciso criar. E, claro, cabeçalho deve apontar para o nó recém-adicionado. Em vez de apontar para isso um nada. Então deixe-me voltar aqui. Primeiro de tudo, quando precisamos criar este nó, ele deve apontar no cabeçalho. Em seguida, o elemento e, em seguida, apontar o que quer que tenhamos tido um get. Próximo. Depois de obter este nó, precisamos consertar as setas. Agora. Temos a seta apontando daqui para o cabeçalho. Então deixe-me corrigir isso simplesmente digitando head.next. Agora eu acessei o primeiro nó aqui, que é um E o que eu preciso fazer é definir anterior para ser igual ao novo nó. Então, simplesmente dizendo set anterior. E neste caso, ou isso ou podemos simplesmente dizer que o novo V nada. Agora, nós também temos que definir o cabeçalho o próximo. Então, em vez de apontar o a, ele deve apontar para o novo nó. Então, como é que se sentou ao lado do novo denote. Por último, precisamos incrementar o tamanho. E, claro, devolva esta nova denota. Este é o primeiro para a inserção. Vamos continuar com a inserção por último. Uma vez que você entenda a idéia é a mesma para o último, antes e depois. Então, primeiro de tudo, precisamos criar o nó, o novo denote para ser igual a denotar. E aqui, quando queremos responder na última posição, precisamos configurar nosso nó apontando para d de um que ação e para o Taylor da outra direção. Então, podemos simplesmente acessar o nó simplesmente acessando o ponto do trailer obter elemento anterior é e. E agora vamos modificar as setas. Primeiro de tudo, o anterior. Então, neste caso, é este nó D. E quando precisamos, quando acessá-lo, podemos simplesmente definir o próximo para ser igual ao novo denote. Então precisamos definir o anterior do Taylor em vez de ser apontado em d, ele deve apontar para o novo nó. Então, a nova denota anterior. E, finalmente, incrementar o tamanho determina essa nova denotação. Agora vamos continuar com inserir antes. Aqui estamos aceitando incógnitas. Portanto, devemos verificar a posição desse conhecimento. E depois podemos trabalhar. Permitam-me que volte a este exemplo. Suponha que precisamos, deixe-me levar isso. E suponha que precisamos inserir nó. Aqui está o nosso novo nó. E precisamos configurá-lo entre B e C. Então aqui, C deve apontar para este campo, e claro que este campo também deve apontar para o mar. E a mesma coisa com B. Então, quando criamos este novo nó, então este é o novo d nada. Deixe-me escrever aqui. Mu. E com alguma nova denotar e minimizar a frente. Então aqui temos nosso novo denote, e este nó é o nó d. Então aqui estamos recebendo o nó D E precisamos inserir o novo nó antes deste D. Então suponha que este nó é C0 e precisamos inserir antes. Então, primeiro de tudo, precisamos modificar as setas e criar o novo nó. Então deixe-me clicar em Criar e novo denotar D. D, desculpe. Nova denota será igual a novo V nada. E em primeiro lugar, ele deve apontar para o B e C. Então, a partir da primeira posição, ele deve apontar que d ponto obter anterior. Em seguida, o elemento e, em seguida, ele deve apontar para D. Agora, vamos modificar as setas aqui. Este nó deve apontar para este campo. Então, para acessar este nó, podemos simplesmente dizer que e ponto obter anterior. Depois de obter o anterior, devemos definir próximo e anterior para ser igual ao novo, denotar. O deveria. Devemos definir o anterior de D para ser igual a novo denote também. Por último, incremente o tamanho e gire esta nova denota D. Agora vamos fazer a mesma coisa com a inserção depois. Então aqui, essa posição depois que criar a nova denotar, o novo nó igual a denotar. E voltemos a este exemplo. Suponha que precisamos modificar esta lista adicionando um novo nó entre B e C. Mas usamos a inserção depois, desculpe, modificando-a usando a inserção depois B. E isso é, o que devemos fazer, é uma vez que configuramos o novo denotar, ele deve apontar para este nó e, em seguida, o próximo. Portanto, deve apontar que o elemento é e e d, mas obter o próximo. Então agora vamos definir o próximo deste nó, que é neste caso. E podemos acessá-lo dizendo D dot get próximo. Agora, acessamos o segundo nó e precisamos definir para ser igual a novo denote. Em seguida, o novo denotar, incrementar o tamanho e retornar novo nó. Então este é para inserir antes e inserir depois. Vejo você no próximo vídeo. 22. Lista de ligação com um link de outro único parte 6: Ainda temos o método toString, mas será muito complicado desde que temos inserir antes e inserir depois, Mostrar e precisamos criar um meio StringBuilder para levar em conta a inserção antes de um elemento e depois de um animal. Então, para ser um pouco complicado, então vamos criar nossa classe tribal e trabalhar neste nome de classe na demonstração DLL. E ele, como de costume, nosso método principal. Vamos criar nossa lista duplamente vinculada, digite inteiro e nomeando DLL listas duplamente vinculadas. E aqui vamos adicionar alguns valores. Então vamos inserir primeiro e valorizar um. Inserir o último. Vamos inserir após o primeiro nó. Inserir depois de qualquer coisa. É o primeiro. Então DLL Deus primeiro. E precisamos armazená-lo para a frente. Inserir ponto depois, antes. Então, queremos armazenar antes do último. E agora temos alguns erros. Vamos ver. Temos exceções não tratadas para lançar a classe de exceção. E agora vamos imprimir, por exemplo, vamos remover um elemento. Então, para removê-lo, isso é impressão digital. Nós removemos, removemos o elemento, uma DLL, a anterior ao último elemento. Assim, o anterior do último elemento. E neste caso, vamos imprimir. Nós somos removidos dois. Agora, como podemos ver aqui, em primeiro lugar, entramos em um do que entramos em cinco. Então, após a primeira posição, após o primeiro nó que entramos para. Então aqui temos quatro e depois temos que fazer. Então, quando precisamos remover o elemento antes do último, vamos remover este, e ainda temos 145. Então vamos imprimir tamanho DLL, mas tamanho, temos agora três. Como você pode ver, tamanho se três, está vazio, não é. ponto Dlls está vazio. Você ganha dobras. Agora, se quisermos imprimir os elementos nesta lista. Então, podemos criar um loop for começando com i igual a 0, igual ao tamanho do ponto DLL. Mas desde DLL, esse tamanho é pode mudar ao remover, adicionar. Então vamos começar com uma variável fora ouvindo tamanho médio igual ao tamanho. E neste caso, o limite será o tamanho. Agora vamos criar um denote lá fora. Então denote D igual a um para ser igual a DLL. Mas primeiro, e imprimimos o elemento. E antes disso está na mesma linha. E então toda vez que entramos neste loop, precisamos modificar o B igual aos próximos dois, b igual a d, o próximo. Agora, ao executar este código, algo pode acontecer. Então vamos colocá-lo em um bloco de tentar e pegar. E se uma exceção de qualquer tipo, basta jogá-lo fora deste para loop. Agora, vamos em frente e correr. Este código terá 1425. Então deixe-me remover um elemento aqui. Por exemplo. Como fizemos antes. O LL remover ponto amarelo anterior. Ainda assim. Então vamos em frente e executar este código e ver o que vai acontecer com a mudança para, e vamos acabar com esta lista 145. Agora, também podemos usar esse método na lista duplamente vinculada e criar um método toString. Mas achei mais fácil quando o usamos na classe principal, já que estamos criando a lista ao mesmo tempo que imprimi-lo. Então é isso para a lista duplamente ligada. É muito mais complicado do que a lista vinculada individualmente, mas é mais poderoso em termos de inserção e remoção de sempre que queremos. 23. Sort de inserção: Considere que você tem uma lista de inteiros como esta lista. E você quer que eles sejam classificados do mais baixo para o mais alto. Ei, você pode usar salga. E há, na verdade, vários algoritmos de classificação e vamos falar sobre alguns deles. Então, dentro por inserção de classificação. A classificação de inserção é um algoritmo de classificação simples que funciona semelhante à forma como você viu cartas de jogo em suas mãos. O array é praticamente dividido em uma parte classificada e não classificada. Os valores da parte não classificada são escolhidos e colocados na posição atual na parte classificada. E aqui podemos começar com este exemplo. Vamos supor que temos esta lista, e esta lista será dividida em duas partes, uma parte ordenada e não ordenada. Então, em primeiro lugar, nossa parte classificada será apenas o primeiro elemento. Então esta é a nossa primeira lista, e esta é a segunda parte. Agora, quatro já está ordenado uma vez que é apenas um elemento, há apenas um elemento nesta lista. E você não tem que fazer nada. Não há nenhum elemento à esquerda de que seja maior do que quatro, então precisamos adicionar três. Então temos 43. Comparamos três com quatro. Então quatro é maior que três. Então devemos trocá-los e teremos 34. Agora, a parte classificada da lista é 34 e a parte não ordenada é o que há aqui. E passaremos para o próximo elemento. Temos que comparar dois a 44 é maior que dois, então trocamos eles. E a mesma coisa que comparamos dois com 33 é maior do que dois também. Então troque-os mais uma vez, e teremos 234. E agora esta é a parte classificada e esta é a parte não ordenada, e assim por diante até chegar ao último elemento da lista. E então terminaremos. Então a idéia geral é comparar cada elemento com todos os elementos à esquerda. Trocar. Cada vez que encontramos um elemento à esquerda maior do que o elemento que estamos usando. Então vamos em frente e escrever o código. Você vai e cria uma classe. E primeiro de tudo, vamos criar nossa matriz inteira, nossa lista de inteiros. E, por exemplo, temos cinco elementos nesta matriz. Deixe-me armazená-los diretamente no 5110. Então este é o nosso array, e vamos criar o nosso método. Mas vamos dar o nome de inserção. E para tomar parâmetro um array, vamos nomeá-lo no trabalho aqui. Então, primeiro de tudo, temos o loop for para passar por todos os elementos de 0 para o comprimento listado menos1. 0 já está classificado, então não temos que começar com 0. Então começamos com um. Então o nosso resultado para loop com um e termina um comprimento de ponto menos um. Agora vamos criar um inteiro. Vamos nomear chave ID, e será o nosso elemento nesta lista. Então vamos comparar um de i. Então aqui está três a 1012 e assim por diante. E nós vendemos e um inteiro chamado jogo. E teremos outro inteiro será j, i menos um para i menos um e voltar até atingir 0. E o que estamos fazendo aqui é que estamos iniciando esse número, por exemplo, que o estado faz caso. A terceira linha, terceira chave em um inteiro. E nós pensamos que este número para um inteiro chamado chave. E então armazenamos a posição que estamos recuperando para começar, que é a posição i menos um, j i menos um. Então vamos para o lado desta posição e voltar até chegar a 0. Então vamos criar um loop while. Enquanto j é maior que 0 e a chave é menor que um de J, precisamos trocar. Então, para dizer aqui é que enquanto j é menor, é maior que 0. Então, aqui neste caso j é igual a um. Tão bom. E a segunda condição, enquanto a chave, que é dois, é menor que um de J, neste caso quatro. Então precisamos trocá-los. Nós trocamos. E mais uma vez, verificamos as condições. Temos j maior que ou igual a 0. Neste caso, j é igual a 0. Então essa condição é válida. E dois neste caso, temos aqui dois e aqui quatro, então 23, então três é maior que dois. Então isso também é válido. Precisamos trocar mais uma vez. E então terminamos com isso para loop desde j será maior do que 0. E neste caso, então toda vez que executamos isso para loop, j será decrementado por um. E aqui precisamos trocar isso, criar um inteiro chamado tamp. E como de costume, essa troca vai levar um de j e armazenamento aqui, e dez e um de j. um de j. mais um neste caso. E finalmente, vamos pegar um j mais um e dar-lhe o valor de w. então aqui nós trocá-los. E agora dissemos, vamos voltar e imprimir. Primeiro de tudo, vamos imprimir a matriz como está antes de classificar. Então imprima em um e algum espaço. Em seguida, execute este método com um a. e, em seguida, isso é impresso mais uma vez. Para vamos imprimir a luz a partir do código e tempo e vai começar em primeiro lugar, o sem sal adicionado e, em seguida, obter o ordenado, já que usamos o método de inserção que criamos aqui. Agora podemos ver como isso mudou todas as vezes. Então vamos imprimir a matriz para criar outro loop for após cada mudança em largura, depois de executar o loop. E imprimir um J2, neste caso, algum espaço. E então, e aqui precisamos imprimir uma ilha. Antes de executar este loop e executar o código irá obter isso. Então, em primeiro lugar, temos 32510. Começamos com i igual a um. Então eu igual a OnRestart, t igual a um de i, j é igual a um de 12, e j é igual a 0 neste caso, que é i menos1 0. Então temos um loop while que será executado apenas uma vez desde J é igual a 0 e, em seguida, ler recomendado. Portanto, a condição aqui , não será válida para outra execução. Portanto, precisamos trocá-los, uma vez que as duas condições estão satisfeitas. A mesma coisa com cinco. Comparamos cinco a agora. Cinco com 25 é maior que dois, então esta condição não está satisfeita. Não vai entrar no loop for com simplesmente embora e incrementar I por um. Agora temos o número um. A mesma coisa aqui. Vamos comparar este com cada elemento e trocar os dois números. Assim, por exemplo, 15 irão trocá-los. E então 13, nós os trocamos mais uma vez. E por último, 12 trocá-los. E finalmente teremos 1010 é maior do que todos os outros elementos. Então ele não entrará no loop, o loop while, e vamos ser feitos com os dois loops, o loop interno e externo. E nós podemos imprimir, imprimir dizendo que você olha para fora o novo array para fora. Então isso é para a classificação de inserção. Vamos explorar mais algoritmos de classificação nos próximos vídeos. 24. Classificação de seleção: Vamos passar agora para outro algoritmo de classificação é a seleção. O algoritmo de classificação de seleção classifica uma matriz encontrando repetidamente o elemento mínimo da parte não classificada e colocando-o no início. Agora estamos considerando ordem ascendente. Nós também temos a ordem decrescente em que podemos encontrar o elemento máximo e armazená-lo no início. E como o tipo de inserção, temos duas partes. O que já estava ordenado e a parte não ordenada. E cada iteração de classificação de seleção, o elemento mínimo da sub-matriz não ordenada é pego e movido para a sub-matriz ordenada. Então vamos usar um exemplo. Vamos usar a mesma lista aqui. E vamos apagar isto. Temos este método, exclua estes. E manteremos este método funcionar aqui. Mas antes, vamos executar este código e usar esta lista. Agora. Mas nós vamos fazer neste algoritmo de classificação é encontrar o mínimo cada vez e armazená-lo na parte não ordenada, a ordenada. Então, primeiro de tudo, vamos encontrar o mínimo e esta lista aqui nós temos um como o mínimo, vamos pegar este 11 e trocá-lo com este número. Seja qual for esse número, vamos trocá-lo por um. Então aqui temos um agora. Então deixe-me escrevê-lo aqui. Então temos 1253 e que o próximo passo é encontrar o mínimo e esta lista. Portanto, o mínimo é verdadeiro e precisamos armazená-lo nesta posição. Então estamos bem, já que o mínimo é dois. Então o próximo passo seria o mesmo que o primeiro. Sense, não precisamos mudar nada. Agora, vamos olhar para esta lista. Temos 5310 e encontramos o mínimo aqui. O mínimo é três. Precisamos armazená-lo no primeiro elemento. Então precisamos trocar três por cinco para o próximo. Ou seja, para trocá-los. Então, vamos ter 123510 e esquema de vidro comparado esses dois números como de costume, Encontre o mínimo entre eles e armazená-lo no primeiro elemento desta lista. E como dez é maior que cinco, então não precisamos fazer nada. E esta é a nossa lista final. Então agora vamos em frente e escrevê-lo como um código. Então pública estática, void, seleção, parâmetro de uma matriz, inteiro. E neste caso, por exemplo, em primeiro lugar, precisamos armazenar o comprimento, o comprimento, o comprimento para usá-lo no loop for. Então aqui temos o comprimento desta lista. Ao lado do nosso loop for, podemos dizer array.length ou ambos, o mesmo. E agora precisamos encontrar o elemento mínimo na parte não triada. Então a parte não ordenada deve começar com i mais um. Então, toda vez que terminarmos com eu vou comparar e encontrar o mínimo e parte de I mais um no comprimento. E aqui temos n menos um. Como não temos que terminar no último elemento, podemos simplesmente adicionar e aqui. E o loop interno para compararia os dois últimos elementos. Então, neste caso, vamos armazenar o mínimo como i igual a i. E agora devemos encontrar o mínimo e a parte não ordenada. Então começamos com i mais um e, em seguida, com array, array.length ou e a mesma simplicidade Maxwell. E agora vamos comparar todos os elementos para encontrar o mínimo. Então, primeiro de tudo, consideramos que o mínimo está no índice i.O índice e um inteiro chamado mínimo. Em primeiro lugar, eu é igual a 0. Então consideramos que o número mínimo nesta lista está no índice 0 para ir e olhar para o índice 00. Então vamos encontrar três e não é o mínimo. Então precisamos comparar esse número com todos os outros. E isso é o que vamos fazer para comparar um J. Neste caso, j é a lista de i mais um daqui até o fim. Então, se i de j é menor que a matriz de homens, então precisamos trocar o índice e os homens, será na verdade o outro anexo. Então o que estamos dizendo aqui é que os homens seriam iguais, e vamos trabalhar com esse exemplo para entendê-lo melhor. Então, primeiro de tudo, começamos com i igual a 0, i igual a 0. Armazenamos no mínimo 0. Agora estamos olhando para este número e j será igual a 0 mais um é aquele que se sentou com um com 1234 e com quatro. Vamos comparar a matriz de um. Se qualquer um de um é menor que a matriz de homens e homens, lembre-se, muitos xn igual a 0 e J, neste caso é igual a um, irá comparar T2, que é qualquer off um com três, apenas no mínimo de 0. F dois é menos de três, então o mínimo agora não é este. Não está mais no índice 0. Está no índice j, neste caso no índice um. Então vamos dar valor mínimo e nu de um. E a mesma coisa de antes. Agora, J é igual a dois. Compararia J, I, J e K de dois. Temos a I2 aqui, cinco com qualquer um dos novos mínimos, que é um. Então você deve comparar agora, é cinco com 25 é maior que dois, então nada vai acontecer. Então vamos para aqui, comparamos matriz de três, que é um com L2. Então um é menor do que T2. Então precisamos dar ao mínimo um novo valor, o valor de um. E, finalmente, temos aqui em que índice, o valor mínimo como depois de encontrar o mínimo usando isso para loop, precisamos trocar este mínimo com o elemento na lista classificada onde devemos resolvê-los. Então o que você deve fazer é como de costume, vamos tomar, no mínimo, pode armazená-lo em um inteiro chamado amortecido que. Mudamos o mínimo com os nossos olhos. E por último, dar a este i índice ID array no índice i, o valor da barragem. Então aqui nós trocá-los e vamos voltar e usar este método aqui. Então seleção e as matrizes, matriz. E a mesma coisa. Vamos imprimi-los e vamos conseguir 123510. Então eu acho que a classificação de seleção é mais fácil do que a inserção. Então, em termos de compreensão, é basicamente apenas encontrar o mínimo no loop interno para e, em seguida, trocá-lo com o primeiro elemento aqui. Mas aqui. E isso é para seleção, então ele vê-lo no próximo vídeo. 25. Lista de bolhas: O terceiro algoritmo de classificação que vamos falar é bubblesort. Bubblesort é o algoritmo de classificação mais simples que funciona trocando repetidamente os elementos adjacentes se eles estão em águas subterrâneas. Portanto, considere esta lista de cinco elementos. Em primeiro lugar, comparamos os dois primeiros elementos e os trocamos uma vez que cinco é maior do que um. E então fazemos a mesma coisa para o número 235 é maior que quatro, então devemos trocar. Então este é o ninho agora. E a mesma coisa para o número do elemento. 345 é maior que dois, ela deve trocar. E, por último, temos 58. E como estão na ordem correta, oito é maior que cinco, então não trocamos. Agora, podemos ver que esta lista ainda não está classificada, já que temos 1424 é maior do que dois. Então o que você deve fazer é repetir os mesmos passos e outra vez até chegarmos à lista ordenada. O pior cenário, se tivermos o aqui um elemento, por exemplo, que dizem 0. Então este 0 deve ser trocado 12345 vezes. Temos seis elementos nesta lista. E o pior cenário é trocar isso 05 vezes. Então, se temos uma lista de n elementos, devemos trocar n menos uma vez. Então, podemos executar esta operação n menos uma vez, e eventualmente você vai obter esta lista ordenada. Então vamos em frente e escrever este código para criar outro método. Ou ele bolha com uma matriz ID de nome de parâmetro como de costume e iria trabalhar aqui. Então, primeiro de tudo, temos um loop for. Como dissemos, de 0 a n menos um, podemos dizer array.length. E dentro deste para loop temos outro para loop para trocar a cada dois elementos. Se o código errado para nós comparamos a cada dois elementos adjacentes, um de j é um de j é maior do que um de j mais um. Então vamos trocá-los. Vamos criar um integer tamp. Agora aqui, RAM spring, e a mesma coisa aqui. E se considerarmos que a temperatura igual à matriz ponto j a j, o que quer que haja em j mais um. E então se j plus1, o valor sal, e este é o nosso método e eu sinto muito, teremos n menos um e n menos um. Vamos usar esta bolha e usá-la aqui, e imprimir a última mais uma vez. E vamos conseguir 325110. Isto é antes de comer e depois de salgar 123510. Agora, nosso código pode ser melhorado fazendo uma tarefa simples. Então, por exemplo, aqui, nós trocamos os elementos aqui. Primeira vez. E na segunda vez, só precisávamos trocar 42. E esta lista está ordenada agora. Mas em nosso exemplo, somos obrigados a passar por toda a lista e menos1 vezes. Então uma coisa que podemos melhorar é f. E chegamos a um ponto em que nosso loop interno para não executar qualquer tarefa, então podemos equacionar porque não temos elementos para trocar. Então, podemos fazer essa tarefa usando um booleano. Então vamos dar o nome de SWAT. Primeiro de tudo, é, deve ser e não dar-lhe o valor aqui vai dar-lhe o valor dentro do nosso exterior para loop. Swap dois será primeiro igual a false neste caso. E se, se nós só vomitarmos pelo menos uma vez, então depois de sair deste loop interno vai verificar swap. Se trocado igual a false. Então não realizamos nenhuma troca aqui. Então, podemos sair do loop for uma vez que nossa lista está classificada agora. Então podemos quebrar. Caso contrário, será a troca contínua. E executamos o código, obtemos o mesmo resultado de antes. Mas agora é muito mais simples e não levará tanto tempo quanto antes. Então isso é para bubblesort, o algoritmo de classificação mais simples entre todos eles. E vejo você no próximo vídeo. 26. : Passando para outro algoritmo de classificação, merge sort. Merge sort é um algoritmo de divisão e conquista. Então deixe-me ir em frente e criar uma nova classe. Subclasse, criado nome de inserção que mesclou. E ele vai discutir o tipo de fusão. Primeiro de tudo, vamos considerar uma pequena lista de quatro elementos e depois discutir uma lista maior. Por exemplo, vamos considerar uma lista com quatro elementos, 2431. Então o que vamos fazer é dividir esta lista em duas listas. O primeiro teremos 24, conterá dois elementos, e o segundo terá os dois últimos elementos, 31. Então vamos classificar cada lista sozinho. Então, 24 já estão classificados, então não precisamos fazer nada, apenas digitá-los. E aqui temos 31, precisamos trocá-los. Então esta é a nossa segunda lista ordenada. E depois disso precisamos fundi-los. Uma vez que eles são classificados. Então, o primeiro elemento deve ser o menor. Então vamos comparar o primeiro elemento nas duas listas. Aqui temos 21. Então alguém é explorado e escreveria um. E então vamos comparar dois com 32 é menor que dois, e então três com quatro. A mesma coisa, orgulho. E então ainda temos o último elemento na primeira lista, apenas quatro, e então terminamos. Agora, vamos usar uma lista maior. Temos nesta lista sete elementos. Dividimos esta lição a Troilo. E a primeira lista será quatro elementos e o segundo três elementos. Então fazemos a mesma coisa com esta lista dividida em duas listas, duas, e para a mesma coisa com a outra também. E ainda temos apenas um elemento, então vamos dividi-lo em um e vamos fazer a mesma coisa. E esta lista, nós temos dois elementos, iria dividi-la em um elemento e cada lista. E então teremos a lista 1234567. Cada lista contém apenas um elemento. Depois disso, precisamos fundi-los. Começamos com os dois elementos aqui. Temos vinte e sete e trinta e oito. Vinte e sete é menor do que você escreveria 2738. A mesma coisa aqui, 343982. E depois disso, precisamos mesclar as duas listas aqui, como fizemos no exemplo anterior. Então, primeiro de tudo, temos três, depois temos vinte e sete, trinta e oito, quarenta e três. A mesma coisa aqui. E finalmente temos a nossa lista finita salgada final. A idéia de tipo de fusão é bastante simples. Ele requer para chamar o método seria mais de 1s, dois até chegar. Lista de um elemento e, em seguida, recriar listas classificadas como mostrado aqui. Vamos escrever agora. Então, para completar a classificação de mesclagem, precisa escrever dois métodos. O primeiro método poderia ser pensado, a principal função que classifica o array usando outro método. Então vamos escrever. Vazio público. Vamos chamá-lo de estático público, vazio. E ele vai aceitar um inteiro e nenhum índice e índice alto. Eles representam por onde devemos começar? E então, se baixo é menor que o difícil, então podemos continuar. Caso contrário, não precisamos fazer nada. Isso significa que baixo é maior ou igual a alto. Neste caso, temos apenas um elemento na lista e não precisamos citá-lo. Então estamos trabalhando se baixo é menor que alto. Então o que devemos fazer aqui é para o índice médio igual a baixo dividido por dois. E então o que vamos fazer é classificar e dividir a lista em duas listas. E então, então, a parte esquerda sozinho e então a direita, mas assim pode fazer isso entrará no nosso Em um, temos com baixo e, em seguida, classificar a direita, mas em um meio mais um. E depois disso, precisamos mesclar as metades classificadas. Então, vamos chamar uma mesclagem de limite de método. E levará como parâmetros à esquerda, baixo e alto. E vamos em frente e criar nosso método de mesclagem. Então temos aqui pode torná-lo privado, privado, estático, vazio, mesclado e como método habitual. E agora precisamos encontrar os tamanhos dos dois subarrays e ser mesclados. Assim, o primeiro tipo é limite n um igual a menos um. E o segundo é N2 igual a oi menos. Agora temos os dois tamanhos. Novas listas. Então, nomeamos a lista um. Ou podemos emitir esquerda e direita. Então temos esquerda, o tamanho e a direita. Este segundo lado. Depois disso, você precisa copiar os dados deste array original para nossos dois arrays. Agora, para fazer isso, simplesmente usamos um loop for com o limite de un1 e copiamos todos os dados da direita para a esquerda. Então esquerda i igual a i. e outro para loop para copiar os dados da parte direita da matriz para a nossa lista chamada direita. Neste caso, vamos começar com uma matriz de meio mais um e mais j. e agora copiamos os dados aqui. Além disso, sinto muito. E é assim que copiamos nossos dados. Agora, precisamos fundi-los juntos. Então o que você deve fazer é criar um loop while para copiar todos os dados que armazenamos e esquerda e direita copiados de volta para a nossa atualização original. Então, como dissemos neste exemplo, depois de ir para esta fase, precisamos armazená-los de volta na lista original. Então aqui vamos comparar os dois elementos e, em seguida, vamos iniciá-los e a matriz original e a mesma coisa aqui. Comparamos esses elementos juntos e obteremos nossa lista classificada. Então vamos voltar ao nosso código e escrever um loop while. E a condição deste loop while que ainda temos elementos na esquerda e na direita. Então, aqui vamos criar inteiros i igual a 0, e a mesma coisa para J, 0. E vamos criar um inteiro e nome para nomeá-lo, que é igual a o. Agora, enquanto i é menor que n, um, que é o tamanho da esquerda e J é menor que. E dois trabalharão neste loop. Agora primeiro de tudo, vamos comparar esquerda com direita de j, de i é menor que j, então nós armazenamos. Este componente e a lista original. Então um seria igual à esquerda. E então nós incrementamos I. Já que terminamos com isso, por exemplo, vamos voltar aqui. O que fizemos neste caso foi compararmos a esquerda de i aqui, 27 com três. F, 27 é menos de três. Devíamos guardá-lo aqui. Agora, neste caso, 27 é maior que três, então devemos armazenar três neste caso. Então, caso contrário, devemos guardá-lo. E em qualquer componente derivado k e incremento j por um. E em ambos os casos, devemos implementar k Uma vez que será preenchido de qualquer maneira. Agora, depois de terminar este loop while, podemos ter alguns elementos restantes em qualquer lista. Então, para preencher o original, devemos completar o que resta em nossas duas listas. Então criamos um loop while. Enquanto eu é menor que N1. O N1 se i é igual a N1. E nós saímos deste loop while por causa de i igual a um, então este loop enquanto não funcionará uma vez que já seria igual linha um. Então, se este for o caso, nós só devemos comprar o que há na parte esquerda e incremento, incremento k. E a mesma coisa com n2 se j é menor que e fazer a mesma coisa exata, para escrever incremento j e k. Então agora estamos feitos com a nossa função de mesclagem. E vamos em frente e usá-lo e nosso método principal. Então vamos voltar. Mas antes vamos verificar nossos limites. Aqui temos esquerda e direita e vamos. Aqui. Devíamos começar com um nó. Uma vez que não estamos sentados com zeros, sentou-se com qualquer que seja o nosso índice aqui. E agora vamos voltar e documentado aqui. Nosso método principal. Isso cria um atraso igual a, neste caso, quatro a 718 e usá-lo agora, use o tipo com um comprimento 0 menos um. E então use um loop for para imprimir nossos elementos. E discórdia 12478. Então isto é para a Fusão. Então, vejo você próximo vídeo. 27. Classificação rápida: Como a classificação de mesclagem, quicksort é um algoritmo de divisão e conquista. Ele leva um elemento como Pivot e particiona a matriz em torno do pivô. Existem muitas versões diferentes de quicksort que pivô grande e maneiras diferentes. Podemos escolher o pivô como o primeiro elemento. Primeiro elemento, elemento aleatório, ou a mídia. Eu perguntaria explicado o que é pivô em um momento. Primeiro, vamos escrever uma lista. Então considere que temos uma lista contém 101819. E esta é a nossa lista. Agora nós escolhemos elemento como um pivô. Então vamos em frente e escolher, por exemplo, o último elemento e separá-los para entendê-lo. E vai ter que fazer a mesma coisa aqui. Então aqui temos esta lista e este é o nosso pivô. Por isso, aqui em baixo. E aqui temos o primeiro elemento. Agora precisamos de duas setas, 2,2 a duas posições nesta lista. O primeiro, começamos com o primeiro elemento da esquerda e o último elemento antes do pivô. Então aqui temos o nosso primeiro, digamos que este é o primeiro elemento e este é o último. Agora, o que vai fazer é comparar o primeiro elemento se ele for maior que o pivô, do que precisamos trocá-lo, precisamos acabar com uma parte que é menor que o pivô e a outra parte deve ser maior que o pivô. Então, para fazer isso, primeiro, dez é maior que o pivô. Agora, então vai se mover, vai passar para 80. Aqui temos 80. Então agora estamos em 8050. Então 80 está pronto para ser trocado. Agora vamos olhar para 5050. 50 é maior que o pivô? Não, então podemos trocá-lo. Então agora trocamos 50 por 80. Aqui terá 80, e aqui temos 15. Agora mudamos as posições dessas setas. Temos esta flecha na 42ª 30. Agora, a mesma coisa fará a mesma coisa aqui. Temos 13, 30 é menor que o pivô? Sim. Então não precisamos trocar. Ele vai para outro ir para 90. E agora vamos comparar 90 com 40. 90 maior que o pivô? Sim. Então precisamos trocá-lo. 40 é menor que o pivô? Sim. Então precisamos trocar esses dois elementos, terá 90 aqui. E as, agora as duas setas, vamos nomeá-las para poder ver o que vai acontecer. Temos baixo e alto. Agora, antes de trocar, estas eram as posições e baixo e alto fluxo na posição 0123 e posição alta para. Agora, depois de trocar os dois elementos, precisamos incrementar em um e diminuir alto em um. Então eu vou estar em posição, nesta posição e baixo será nesta posição. E sempre que o baixo é igual ou superior ao alto, podemos saber que terminamos aqui, uma vez que o baixo passou alto. Agora, a última coisa que devemos fazer é trocar este elemento com o pivô. Então você terá 17 E no pivô 90. Agora podemos ver que todos os elementos aqui menores que 70, e todos os elementos aqui são grandes e 70. Então esta é a idéia do QuickSort. Podemos executar este mesmo algoritmo exato para esta lista. Podemos escolher 40 como o pivô e trabalhar em conformidade. E a mesma coisa acontece aqui. E deixamos a recursão fazer o trabalho por nós. Esta é a ideia geral e usaremos a recursão para poder implementá-la mais de uma vez. Agora emergiu. Então temos dois métodos aqui. Primeiro método será privado, inteiro. Vamos mudar o nome da partição. Levará os parâmetros e emitirá e baixa. E este método levará o último elemento como o pivô. O elemento pivô em sua posição correta na matriz classificada. E casos todos os elementos menores, menores do que o pivô para a esquerda e maior para a direita. Então vamos em frente e começar com este método. Primeiro de tudo, temos o nosso pivô é criado. Agora o vetor é igual ao último elemento nesta lista. E temos o índice de elemento menor. É um sname i, que é igual a menos1. E neste caso, começamos com o nosso loop for. Começamos por baixo. Todo o caminho até. Agora, precisamos verificar se o elemento atual é menor que o pivô. Então, se j é menor neste caso, e precisamos incrementar i. Um, swap e array j. Então vamos trocá-lo. E igual a editar a. Ele então igual a, desculpe, a igual a i, igual a j. E finalmente, de volta a G. Então agora nós trocamos os dois elementos. Depois de terminar com este loop de palavras, precisamos trocar o pivô com um i mais um. Então, neste caso, crie outra hora e troque os dois elementos. Como dissemos. Aqui, temos o pivô no local a. e depois dando o bronzeado dois. Agora nós trocamos os dois metadados para elementos e, em seguida, vamos simplesmente retornar mais um. Então este é o nosso método, o método de partição. Este método tomou o último elemento como Pivot, coloque o elemento pivô em sua posição correta no ordenado em um, e coloca todos menores para a esquerda e maior para derivado. Agora, o outro método é a função principal que implementa esse quicksort. E vamos chamá-lo de estático público, vazio. Para que fosse preciso três parâmetros, como de costume, e baixo e alto. Primeiro de tudo, vamos verificar se o fluxo não é maior que alto. Podemos trabalhar de outra forma não funcionará porque não fará sentido. E nós teremos, vamos criar um inteiro, vamos nomeá-lo por, por particionamento e profundidade. Isso vai, onde vamos usar este método que criamos aqui. Então pi usaria partição no baixo. Agora, depois de obter o índice, mas agora devemos classificar os dois , diminuir a parte esquerda, certo? Mas então vamos usar o mesmo método mais uma vez sem outra maneira de Pi menos um. E a mesma coisa por mais uma maneira de escrever. E então terminamos com esse método. Você pode usá-lo. E o nosso método principal. Então criamos uma matriz, por exemplo, vapor, e com alguns valores 426173. E vamos chamar o método de classificação 0. E no comprimento menos1, em seguida, crie um loop for e imprima os elementos desta lista. Então, como de costume, com algum espaço aqui, e vamos em frente e correr. O código receberá 1234567. Então, esta é a matriz é ordenada matriz depois de executar este QuickSort. Então este é o fim para Quicksort. Vejo você no próximo vídeo. 28. Pesquisa de salto: Como pesquisa binária, saltos Pesquisa é um algoritmo de busca para ordenar matrizes. A idéia básica é verificar menos elementos do que a pesquisa linear, pulando à frente por abas fixas ou ignorando alguns elementos em vez de procurar todos os elementos na lista. Então, por exemplo, considere que temos essa lista. Temos 16 elementos aqui. Vamos supor que estamos procurando o número 55. Assim, a pesquisa de salto vai encontrar o valor de 55 usando alguns passos. Primeiro, vamos considerar que o tamanho do bloco a ser saltado como para desde 16, raiz quadrada de 164. Então, primeiro de tudo, ele vai saltar do índice 0 para o índice quatro. Então ele vai saltar para 01234. Ir para este elemento em comparação com 5535 ainda é maior do que três. Então saltamos mais uma vez para qualquer um. A mesma coisa aqui, 21 é menos de 55, então precisamos pular, vai pular para 144. E então podemos ver que 144 é maior que 55. Então vamos voltar para 21 e fazer uma busca linear de 21244 até encontrarmos nosso elemento para o número 55. Geralmente usamos a raiz quadrada do comprimento como o tamanho do bloco a ser saltado. Porque na pior das hipóteses, este é o melhor passo a dar. Então vamos começar com o nosso código. Pular. Os principais ij de inteiro e x que vamos procurar nesta lista. E aqui, em primeiro lugar, precisamos armazenar a duração do dia. Precisamos escolher nossa pilha. E como dissemos, vamos tomar a raiz quadrada de n usando a massa. E esta raiz quadrada de massa. Por exemplo, suponha que temos 17 elementos, dar US 14 e assim como um número. Então, depois de tomar a raiz quadrada de e formatado usando Math.Floor. E então, desde que atribuímos um inteiro para converge para n, e se o elemento existe, então precisamos encontrar o bloco onde o elemento está presente. Então vamos voltar ao nosso exemplo. E ele 55 está entre 2144. Então precisamos encontrar esses dois elementos. E nós já temos um inteiro, temos recriar uma outra entidade ou vamos chamá-lo, por exemplo, líquido anterior para 0. Então, no início, anterior é igual a 0, então ele está na posição 0 e o passo está na posição quatro. E se o elemento não for encontrado neste intervalo, então devemos dar anterior o valor de quatro. Então, o anterior está agora na posição quatro e precisamos adicionar quatro ao passo. Então passo seria na posição oito e continuar até encontrar um elemento de trabalho e esta interpretação e nosso intervalo. Então, para fazer isso, precisamos criar um loop while e definir o loop selvagem como em é menor que x. agora, podemos chegar a um ponto onde se continuarmos adicionando quatro, o passo, podemos ter passo maior que n, então não podemos acessar a meio passo. Então, em vez de acessar matriz de passo que diz um radar mínimo entre passo e, e. Então, toda vez que executamos esse loop, precisamos mudar anterior para o novo valor. E o mesmo para o passo três para adicionar. O que quer que tenhamos aqui. Então, acrescentou e, em seguida, vamos obter anterior é maior do que ou igual a. E então estamos acabados. Não encontramos o animal que simplesmente virou menos1. E ele devemos mudar para inteiro. Agora. Então o que estamos dizendo aqui neste loop while, vamos usá-lo neste exemplo. Primeiro de tudo, temos anterior igual a 0 e passo quatro posição por agora, vamos passar por isso loop while. Primeiro de tudo, vamos verificar matriz de mínimo entre passo e, em seguida, passo é certamente menor do que n. Neste caso, passo é igual a quatro. Matemática em um de quatro, que é três. Neste caso, vamos verificar se três é menor que x. sim, então vamos continuar executando isso enquanto loop vai mudar os valores. Agora, reverso é igual a quatro e passo é igual a oito. E então vamos verificar se passamos os limites. Se anterior é maior ou igual a n, então passamos os limites e fizemos, não encontramos nenhum número que corresponda aos atos. Agora estamos na posição quatro. E posição oito. A mesma coisa. Comparamos este 21 com 5521 é menor que 55 e precisamos executar o loop while mais uma vez anterior está agora na posição oito. Então esta é a posição para, esta é a ajuda de posição. E o passo está na posição 12. Neste caso, temos 144. Então comparado cento e quarenta e quatro, cinquenta e cinco anos menos do que um 144, em seguida, vai sair do loop. Tendo anterior o valor de oito e passo o valor de 12, então temos o nosso intervalo e 55 está neste intervalo. Agora, depois de sair do loop while, precisamos executar uma busca linear para x e um y e outro loop while. Então, enquanto matriz de resultado com o anterior. Agora, uma vez que o anterior está na posição oito e passo está na posição cento e quarenta e quatro e cinquenta e cinco, que mostrou que o receptor está em discórdia primeiro intervalo, então vamos começar com 21 e continuar. Tão largo transporte no anterior é menor que x, então vamos incrementar em um. E se chegamos a um ponto em que anterior é igual a qualquer passo, igual a 12 sobre n, Então igual ao mínimo entre os dois inteiros, qualquer carimbo. E então precisamos quebrar ou retornar menos1 pode simplesmente retornar menos um. Neste caso, já que não encontramos o nosso número. E então verificamos se encontramos o elemento. Então, se array anterior é igual a x, então retornamos esta posição e retornamos menos um. Se morrermos, não encontraremos. Então este é um t que adicionamos não pode convergir de n Booleano, temos uma falta. Então é isso, esta é a nossa função. E vamos em frente e escolhê-lo aqui. Então vamos imprimir pedaço e vamos procurar por 55. Então vamos pegar isso e colocá-los em nosso, este é o nosso array e ele vai retornar dez. Então 55 está na posição dez. Então estas duas primeiras linhas eram das funções passadas agora esta hora do que a nossa posição onde 55 está nesta lista. Então é isso para saltos. Vejo você no próximo vídeo. 29. Pesquisa de interpolação: E outro algoritmo de busca como busca por interpolação. pesquisa de interpolação funciona melhor do que a pesquisa binária. Porque a pesquisa binária sempre verificar em uma base de elemento intermediário. Mas a pesquisa de interpretação pode ir para diferentes locais de acordo com o valor de P a ser pesquisado. Então, por exemplo, se quisermos procurar o número três e esta lista, se usarmos a pesquisa binária, vamos verificar no meio. Então, ou 1321034, então este é o meio da lista. No entanto, se usarmos a pesquisa de interpolação irá para o valor que está mais próximo do nosso número usando uma fórmula específica e falaremos sobre isso mais tarde. Então ele três está mais perto de 0 do que está mais perto de 610. Então nossa fórmula nos levará a um número entre estes. Então, a mesma idéia que a pesquisa binária, mas em vez de ter um elemento intermediário, teremos uma posição que mudará de acordo com nossos elementos. Então vamos em frente e criar nosso método público. E vamos chamá-lo de interpolação. E como normalmente para tomar uma matriz de elementos e o tamanho do elemento, bem como o IV ou digamos x. agora, precisamos definir nosso baixo e alto e baixo igual a 0 e será e menos 1 y loop. Então, enquanto baixo é menor ou igual a i, caso contrário, não precisamos mais trabalhar porque não encontramos nosso elemento. Então é o mesmo que fizemos na busca binária. E precisamos adicionar algumas condições. Enquanto nosso elemento x é menor ou igual a, nosso baixo é maior ou igual, sinto muito, e é menor ou igual ao nosso elemento. Assim, desde que estas condições estejam satisfeitas, podemos trabalhar aqui. Agora, sempre que chegamos a um ponto em que nosso baixo é igual ao nosso índice alto, então isso significa que nós fizemos isso ou encontramos o elemento ou não. Então vamos verificar se eu sei o mesmo, uma vez que eles são iguais, é igual ao nosso x. E este é o caso retorno baixo, caso contrário, retorno menos1. E depois de verificar esta condição, agora podemos trabalhar, podemos criar nossa fórmula que a mesma posição que vai saltar. Como fizemos em nossa busca binária, criamos uma posição chamada elemento metal. Toda vez que vamos para o elemento do meio agora, criamos outro inteiro chamado posição. E a fórmula é a seguinte. É assim que calculamos a interpolação. E um de alto menos baixo. Então nós multiplicá-lo com I iria x menos um de carga. E agora verificamos se um raio nesta posição é igual ao nosso elemento, então apenas retornamos nossa posição. Caso contrário, vamos verificar se um nesta posição é menor do que o nosso elemento. Então precisamos mudar nossa posição baixa de baixa para alta mais uma. A mesma coisa que fizemos e em busca binária, mas em vez de posição e usamos método caso contrário será posição menos um. Então, caso contrário, se o temos em uma posição é maior que x, então du seria igual a posição menos1. E depois de terminar esta condição e tudo, o loop while, podemos retornar menos um se não encontrarmos o inteiro. E agora vamos voltar e usá-lo aqui. Então eu imprimi interpolação. Temos a a e B e x será o número. Então, por exemplo, vamos supor para uma busca por b. E vamos em frente e executar nosso código. Vai ficar para SO três está na posição 401234. Vamos mudar este número para 89 e vamos para a posição 11. Então 89 está na posição 11. E a última coisa que viemos verificar se introduzimos um número que não está nesta lição, 900, obtemos menos um. Então é isso para busca por interpolação. Vejo você no próximo vídeo. 30. Pesquisa exponencial: O último algoritmo de busca que vamos falar é de busca exponencial. pesquisa exponencial envolve duas etapas. Primeiro, precisamos encontrar o intervalo onde o elemento está presente. E então faremos uma busca binária no estranho. Então vamos considerar esta lição. Temos 16 elementos e temos de encontrar, por exemplo, 89. Então o que vamos fazer é, em primeiro lugar, considerar se o nosso número é igual ao primeiro elemento desta lista. Se este for o caso, então retornamos 0, então ele está na posição 0. Caso contrário, verificamos todos os outros elementos. Começamos com i igual a um e com doublet I igual a dois, então i igual a 24816 e assim por diante. E vamos em frente e implementado para entender melhor isso. Vá aqui e você tem estática pública, e vamos nomeá-lo exponencial. Como de costume, pegue uma matriz de inteiros e, e, e o valor que vamos procurar, vamos nomeá-lo x aqui. Primeiro de tudo, como dissemos, precisamos verificar se no índice 0, se o valor estiver no índice 0, então simplesmente retornamos 0. Caso contrário, precisamos encontrar o intervalo para a pesquisa binária por duplicação repetida. Então vamos definir um inteiro com o valor de um, e entramos no loop. Enquanto i é menor que n, a duração do dia. E em um, em i é menor que o nosso, menor ou igual ao nosso número. Este loop será executado. Então vamos simplesmente multiplicar i por dois. Então, toda vez que entramos neste loop, multiplicamos i por dois. Então vamos ver aqui neste exemplo, quando podemos sair deste loop. Por exemplo, se quisermos procurar o número 13, primeiro lugar, verificamos se 0 é igual a 13. Não, não é. Então definimos i igual a um e entramos neste loop. Eu é igual a um, vou verificar. Enquanto eu em um, em i é menor ou igual a x, um é menor ou igual a 13. Sim, então multiplicamos i por. Então agora temos eu igual a dois, e vamos para o nosso próximo elemento. Aqui temos também um, é menor que 13 e i é menor que n. Então multiplicamos i por 21 mais tempo. Agora temos duas vezes 24201234. Agora estamos aqui. Verificamos que o é inferior a 13. Então podemos multiplicar mais uma vez para quatro vezes 28. Então agora estamos com 5678, estamos com 21. Agora. Vamos verificar que 21 é menos de 13. Não, não é. Então. Saímos do loop com i igual a oito. Agora temos eu igual a oito. E para obter o nosso intervalo, temos i igual a oito e i igual a quatro, que é oito dividido por dois. Então, depois de encontrar o nosso intervalo aqui, nós simplesmente usamos a pesquisa binária. E eu trabalho em um e aqui temos eu dividido por dois. Este é o nosso intervalo e mínimo entre i e um, i e n. Uma vez que pode ser, pode ser que i é maior do que n e não podemos trabalhar fora de nossos limites. E aqui temos nosso inteiro x. e como precisamos retornar o tipo, então simplesmente giramos a pesquisa binária. E então terminamos. Vamos em frente e usá-lo aqui. Então vamos em frente e imprimir exponencial em array.length e w. Vamos procurar por exemplo, 13. E o código terá sete. Então, 13 está na posição sete. Então vamos torná-lo melhor, melhor. E exponencial. Vamos guardá-lo como exponencial. E um resultado inteiro é igual a este exponencial. Se o resultado for maior do que 0, então imprimimos o elemento está presente no índice. E imprimimos o índice. Caso contrário, imprimimos que o elemento não está presente. E Ray e agrupamento do código obterá elemento está presente e índice sete. Agora temos um atalho em Java que você pode usar. Então, em vez de escrever tudo isso, podemos simplesmente imprimir uma das duas linhas. Então precisamos definir aqui a condição se o resultado for menor que 0, este é o caso. Podemos imprimir. O elemento não está presente. E a outra afirmação seria elemento está presente, índice. E imprimimos o índice. Então vamos em frente e ver o que teria sido aqui. Vamos executar o código e obtemos elemento está presente e índice sete. Então, este atalho, Primeiro de tudo, método NDA System.out.Print. Nós definimos a condição que seu resultado é menor que 0. Em seguida, automaticamente este método irá imprimir a primeira instrução. Caso contrário, ele irá imprimir o que há depois dos dois pontos aqui. Então nós perguntamos a eles se não é pedido é menor que 0, sim, imprimir isso. Caso contrário. Imprima isto. Isso é muito útil se não queremos complicar as coisas e precisamos de uma forma muito simples de impressão. Então isto é para procurar algoritmos. Vejo você no próximo vídeo. 31. Projeto: Vamos finalmente passar para o projeto é muito fácil e simples um, e este projeto terá duas pilhas e pilha um e começar a. Aqui você precisa empurrar alguns pontos fortes para essas tags. Então, por exemplo, eu empurrei você é como teve a baixa para obter Olá teve o, como você está. Agora, o que você precisa fazer é criar esse método que é chamado de mesclagem. Para mesclar pilha um e começar a nova etapa e , em seguida, armazená-lo em uma nova pilha aqui fora no método principal. Então, claro, imprimiu eu usei e pilha Java. Mas é claro que você pode usar a pilha que nós construímos antes. Você também pode usar qualquer tipo de dados aqui em vez de força. Mas eu escolhi as coisas para ver como seria quando eu imprimir a mensagem ou as palavras. E, claro, é assim que o seu método deve ser. Ele deveria. 32. Recapitulação: Obrigado e parabéns pelo discurso de soco. Aqui está uma breve recapitulação do que fizemos. Primeiro de tudo, falamos sobre pilha. Usamos arrays e listas vinculadas individualmente para implementar essas tags. Em seguida, movemos para dicas e lista uniformemente e duplamente vinculados. E, claro, finalmente, falamos sobre classificação e busca de algoritmos. Nós fizemos tantos deles, como rápida e bubblesort e busca linear e binária. E ainda temos a estrutura de dados não-linear. E espero que vamos cobri-los mais tarde nas próximas aulas. Então, obrigado por comparecer e nos vemos na próxima aula.