Estrutura de Dados 1

Prévia do material em texto

CONTEÚDOS: (Conhecimentos, Habilidades, Atitudes)
Tipos abstratos de dados: Abstração. Modularização. Encapsulamento. Ocultamento de
informações. Listas lineares: Conceituação. Tipos de listas. Operações básicas.
Implementações. Aplicações. Pilhas: Conceituação. Operações básicas. Implementações.
Aplicações. Filas: Conceituação. Tipos de filas. Operações básicas. Implementações.
Aplicações. Árvores: Conceituação. Tipos de árvores. Aplicações. Árvores binárias:
Conceituação. Formas de passeio. Árvores binárias de pesquisa: Conceituação. Operações
básicas. Implementação. Aplicações.
AVALIAÇÃO DA APRENDIZAGEM : Avaliação única resultante da média ponderada
das listas de exercício (peso 4), participação (peso 1), atividades avaliativas (peso
3), e projeto (peso 2).
FONTES DE PESQUISA: (Bibliografia)
Básica:
CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN,
Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.
EDELWEISS, Nina. Estruturas de dados. Porto Alegre: Bookman, 2011. (online)
(muito básico sem exercicios resolvidos por enquanto)
GOODRICH, Michael T. Estruturas de dados & algoritmos em Java. 5. ed. Porto
Alegre: Bookman, 2013. (online)
(muito raso )
Complementar:
http://denan.com.br/documentos/JavaDeitel.pdf (melhor até agora)
https://www.youtube.com/watch?v=tujIyo7cMds&list=PLjcmNukBom6_nyEVge9stJLdq
-bAeDoWx
DEITEL, Harvey M.; DEITEL, Paul J. Java: como programar. 8. ed. São Paulo: Pearson,
2011. DROZDEK, Adam. Estrutura de dados e algoritmos em C++. 2. ed. São Paulo:
Cengage Learning, 2018. ( só no papel )
MORAES, Celso Roberto. Estruturas de dados e algoritmos: uma abordagem didática.
2. ed. São Paulo: Futura, 2003.
PEREIRA, Silvio do Lago. Estruturas de dados fundamentais: conceitos e aplicações.
12. ed. São Paulo: Érica, 2012.
SZWARCFITER, Jayme Luiz. Estruturas de dados e seus algoritmos. 3. ed. Rio de
Janeiro: LTC, 2010.
http://denan.com.br/documentos/JavaDeitel.pdf
https://www.youtube.com/watch?v=tujIyo7cMds&list=PLjcmNukBom6_nyEVge9stJLdq-bAeDoWx
https://www.youtube.com/watch?v=tujIyo7cMds&list=PLjcmNukBom6_nyEVge9stJLdq-bAeDoWx
1 Aula
Open files from System
Selecione a pasta e finalize
● Se não funcionar faça isso(imagem);
● Todas as modificações serão no main,
nunca nos testes.
● Toda modificação vai ser no main;
● com botão direito fazemos no teste para
ver os erros;
● clique duas vezes com
botão esquerdo e vai abrir essa
tela
● ela vai mostrar os erros
e falhas que temos no projeto;
erro - compilação errada
falha - menos grave apenas
lógica errada;
Na parte de baixo você clica
nos erros e vai aparecer a
opção de consertar, assim
sai do vermelho para azul (
falhas).
Lembre de colocar rerun para ir
verificando o que falta
Dicas: crie um novo projeto,
coloque o nome do prof e
depois abra a pasta do windows
e arraste o source para cima da
pasta do Eclipse
Os tipos abstratos de dados (TADs) são estruturas de dados capazes de
representar os tipos de dados que não foram previstos no núcleo das linguagens de
programação e que, normalmente, são necessários para aplicações específicas.
Essas estruturas são divididas em duas partes: os dados e as operações. A
especificação de um TAD corresponde à escolha de uma boa maneira de
armazenar os dados e à definição de um conjunto adequado de operações para
atuar sobre eles.
Aula 2 e 3 - 19 /08/21 a 23/08/21
Alocação Dinâmica na Memória
Criar e manter estrutura de dados exige uma alocação dinâmica de memória.
O Java não libera memória, ele simplesmente faz uma coleta de lixo automática
sobre os objetos as quais não se faz mais referência. O new é primordial para
uma alocação dinâmica.
Assert.assertEquals(expected,actual)
Quando vc consertou mas ficou alguma falha (azul), vc clica nela e vai
mostrar onde está essa falha assim depois vc clica na 1 linha deste código da falha
e vai debugar
De 40:00 até 1: 10 ele ensina a debugar. s
Lista 00
Questão 1
Crie uma classe SumDivision que contém os dois métodos static a seguir: 1. método sum
que recebe dois parâmetros x1 e x2 do tipo double e retorna um double que é a soma
entre x1 e x2.
2. Método divide que recebe dois parâmetros: x1 e x2 do tipo double e retorna um
double que é o resultado da divisão de x1 por x2.
A variável result no código a seguir
double n = 15;
double result = SumDivision.sum(n, 0);
Armazena o seguinte conteúdo.
15
Questão 2
Crie uma classe Volume contendo um método static chamado getName que recebe
volume do tipo int e retorna uma String com a descrição de volume a seguir
1. “Min Volume”, caso volume seja menor ou igual a 0;
2. “Low Volume”, caso volume seja maior que 0 e menor ou igual à 25; 3.
“Medium Volume”, caso volume seja maior que 25 e menor ou igual que 75;
4. “High Volume”, caso volume seja maior que 75 e menor que 100;
5. “Max Volume”, caso volume seja maior ou igual à 100.
Exemplos:
A variável result no código a seguir
int volume = 25;
String result = Volume.getName(volume);
Armazena o seguinte conteúdo.
"Low Volume"
Questão 3
Crie uma classe Pair para encapsular um par de strings contendo:
1. 2 atributos left e right ambos do tipo String ;
2. Construtor que recebe as variáveis left e right e inicializa os respectivos atributos
left e right;
3. Sobrescreva o método toString para retornar o valor dos atributos left e right
entre parênteses e separados por vírgula: “(left, right)”
4. Sobrescreva o método equals para que a igualdade entre 2 objetos do tipo Pair
retorne true apenas quando tanto left quanto right de ambos sejam iguais.
Crie uma classe Pairing para encapsular o pareamento entre 2 strings contendo
1. Atributo pairs do tipo vetor de Pair e respectivo método acessador
getPairs;
2. Método getList
a. Modificador de acesso private;
b. Recebe uma string s como argumento;
c. Retorna um vetor de elementos do tipo String com um elemento para
cada substring em s separada por vírgula
3. Método obtainPairs
a. modificador de acesso public
b. Recebe como argumento duas variáveis s1 e s2 do tipo String
c. Retorna um vetor de elementos do tipo Pair em que o i-ésimo elemento
tem como left e right, respectivamente, o i-ésimo elemento getList(s1) e
getList(s2).
d. Lança exceção caso o tamanho do vetor getList(s1) seja diferente do
vetor getList(s2)
4. Construtor
a. Recebe String s1, String s2
b. Lança exceção
c. Inicializa o atributo pairs a partir do resultado obtainPairs(s1,s2)
Exemplos:
A variável result no código a seguir
String s1 = "Person 1, Person 3, Person 5";
String s2 = "Person 2, Person 4, Person 6";
Pairing pairing = new Pairing(s1, s2);
String result = pairing.toString();
Armazena o seguinte conteúdo.
"(Person 1, Person 2), (Person 3, Person 4), (Person 5, Person 6)"
package com.diegopinheiro.ed1_00_workshop;
public class Pair {
// 1. 2 atributos left e right ambos do tipo String ;
private String left, right;
// 2. Construtor que recebe as variáveis left e right
//e inicializa os respectivos atributos left e right;
public Pair(String left, String right) {
this.left = left;
this.right = right;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if(obj instanceof Pair ) {
Pair other = (Pair)obj;
return this.left.equals(other.left) &&
this.right.equals(other.right);
}
return false;
}
@Override
public String toString() {
return "("+ this.left + ", " + this.right + ")";
}
}
package com.diegopinheiro.ed1_00_workshop;
public class Pairing {
private Pair [] pairs; // 1. Atributo pairs do tipo vetor de Pair
public Pairing (String s1, String s2)throws Exception {
this.pairs = obtainPairs(s1, s2);
}
// 1. método acessador getPairs;
public Pair[] getPairs() {
return pairs;
}
private String [] getList (String s) {
if (s.isEmpty()) {
return new String[0];
}
return s.split(", ");
}
public Pair [] obtainPairs(String s1, String s2) throws Exception{
int tam1, tam2, i;
String arr1 [] = getList(s1);
String arr2 [] = getList(s2);
Pair [] pairArr;
tam1 = arr1.length;
tam2 = arr2.length;
if(s1.equals("")&& s2.equals("")) {
pairArr = new Pair[0];
//se as strings estiverem vazias o Pair tem tamanho 0.
}
else if(tam1 == tam2) {
pairArr = new Pair[tam1];
for ( i = 0; i < tam1; i++) {
pairArr[i] = new Pair(arr1[i], arr2[i]);
}
} else {
throw new Exception("Cannot obtain pairs with different sizes!");
}
return pairArr;
}
@Override
public String toString() {
int tam = this.pairs.length;
String frase = "";
if (tam != 0) {
for (int i=0; i<tam; i++) {
if (i != this.pairs.length-1) { //verifica se
esta na ultima palavra do array
frase += pairs[i] + ", ";
} else {
frase += pairs[i];
}
} }
return frase; } }
Aula 4 - 26/08/21
Aula 5 - 30/08/21
Ele continuou a revisão de POO
Garbage collector - ajuda no gerenciamento de memória, ele pega endereços de
memória que não estão sendo usados e desaloca, deixando livre.
(apagando)
PS:
procurar ver
sobre Tipo
de dado de
Referência: Pair (Diego indicou o Core Java 11 edição )
Data Abstract - os dados primitivos são colocados dentro das referências. É um tipo
onde sua representação é escondida(hidden) do client ( ) .
1:20 em diante -
This - variável que
guarda a auto
referência das
instâncias do objeto.
Aula 6 - Pilhas 02/09/2021
- aula 2 e 3 ele falou de @test e @before ( executa antes dos outros )
String - encapsula char
Determinadas listas lineares apresentam uma disciplina restrita organização e de
acesso aos seus nodos, que deve ser obedecida por todas as operações realizadas nestas
listas. São listas especiais nas quais não são permitidas operações sobre quaisquer nodos,
somente sobre aqueles definidos pela organização da lista.
Políticas de Abstração
LIFO ( last in first out) - o último elemento (nodo) a ser inserido, será o primeiro a ser
retirado. Assim, uma pilha permite acesso a apenas um item de dados, o último
inserido. Para processar o penúltimo item inserido, deve-se remover o último. São
exemplos de uso de pilha em um sistema:
● Funções recursivas em compiladores;
● Mecanismo de desfazer/refazer dos
editores de texto;
● Navegação entre páginas Web;
Todas as operações em uma pilha podem ser imaginadas como as que
ocorre numa pilha de pratos ( um novo prato é sempre colocado no topo da pilha, e
o primeiro prato a ser retirado e o do topo da pilha):
● criação: informar a capacidade ( se for implementação sequencial - vetor);
● push - empilhar (com argumento, sem retorno);
● pop - desempilhar (sem argumento, com retorno);
● consultar e/ou modificar e/ou mostrar o topo;
TAD pilha inclui os seguintes métodos auxiliares:
● isEmpty - verificar se a pilha está vazia (retorna boolean);
● is Full - verificar se a pilha está cheia (implementação sequencial - vetor).
Todas as consultas,
alterações, inclusões e
remoções de nodos
somente podem ser
realizadas sobre um
nodo, o da extremidade
(topo da pilha).
No Livro: GOODRICH, Michael T. Estruturas de dados & algoritmos em Java
-5/2013 na página 208 capítulo 5 , ele mostra uma estrutura básica de pilha:
@Before - colocar para executar antes dos outros
Basicamente, se sua estrutura for uma pilha você faz a aplicação baseada
nos recurso que ela possui citados acima (push, pop, top…). Estrutura básica de
pilha segundo Isidro (aula youtube):
package pilhas;
public class Pilha {
private int valores[];
private int topo;
public Pilha(){ // construtores
valores = new int[5];
topo = -1;
// com esse valor a pilha está vazia
}
public void push(int elementos){ // empilhar - inserir elementos
topo ++;
valores[topo] = elementos;
}
public boolean isEmpty(){ //verificar se esta vazia ou nao
return topo == -1;
}
public boolean isFull() {
return topo == 4;
}
public int pop() {
int elementos;
elementos = valores[topo];
topo --;
return elementos; } }
Lista 01 Questão 1
Crie uma classe StackArray para implementar o Tipo Abstrato de Dados Pilha. Você
deve utilizar arrays na implementação e a interface IStack fornecida. Ou seja, deve
possuir os métodos
1. void push(Integer value),
2. Integer pop() throws IllegalStateException;
3. boolean isEmpty()
package com.diegopinheiro.ed1_01_lista;
public class StackArray implements IStack {
private Integer[] pilhaArray;
// isso aqui é o próprio corpo da pilha (array)
// a pilha tem o topo e o corpo
private int top;
public StackArray(int capacity) {
// método construtor
this.pilhaArray = new Integer[capacity];
this.top = 0;
// Pq nao posso gerar em source??
}
@Override
public void push(Integer value) {
if (this.isFull()) {
throw new IllegalStateException("Nao da");
}
pilhaArray[this.top] = value;
this.top ++;
}
@Override
public Integer pop() throws IllegalStateException {
Integer num;
if (this.isEmpty()) {
throw new IllegalStateException();
}
num = this.pilhaArray[top-1];
this.pilhaArray[top-1] = null;
/*Com as duas posições preenchidas do array teremos o top = 2.
* Logo top-1 = pos do último elemento do array*/
this.top--;
return num;
}
@Override
public boolean isEmpty() {
return this.top == 0;
// como a pilha e um vetor de array, e ela está cheia então o top(topo) é
igual ao comprimento do vetor
}
private boolean isFull() {
return this.top == this.pilhaArray.length; } }
====================================================
Revisão:
====================================================
public class StackArray implements IStack {
private Integer [] pilhaArray ;
// a pilha tem o topo e o corpo inicialmente
private int top;
public StackArray(int capacity) {
this.pilhaArray = new Integer [capacity];
// nao entendi bem isso
this.top = -1; // pilha vazia segundo o livro e isidro
};
@Override
public void push(Integer value) {
// antes de adc temos que saber se a pilha está cheia ou vazia
if(this.isFull() ) {
throw new IllegalStateException("Ta cheio bro");
}
else { // Coloquei um else mesmo
pilhaArray[top] = value; // como não está vazia, o
topo vai ser acima do valor que colocaremos, por isso top++
top++;
}
}
private boolean isFull() {
return this.top == pilhaArray.length;
// como a pilha e um vetor de array ela está cheia então o top(topo) é igual
ao comprimento do vetor
}
@Override
public Integer pop() throws IllegalStateException {
Integer valu = null;
// pq ele fez embaixo this.pilhaArray[top-1] = null;???? Foi para inicializar,
mas como ele sabia disso??
if(this.isEmpty()) {
throw new IllegalStateException("Ta vazio bro");
}
else {
pilhaArray[top -1] = valu ;
this.top--;
}
return valu;
}
@Override
public boolean isEmpty() {
return this.top == 0; } }
Aula 7 - Filas 06/09/21 (Faltei) Total: 2
Outra estrutura de dados fundamental. E uma “prima” da pilha, pois uma fila é
uma coleção de objetos que são inseridos e removidos de acordo com o princípio
FIFO (First in, first out - o primeiro que entra é o primeiro que sai).
● Head - início S;
● enqueue - enfileirar (Insere o elemento no fim da fila.);
● Tail - final;
● dequeue - Retira e retorna o objeto da frente da fila. Ocorre erro se a fila
estiver vazia.
Funcionamento de uma fila de banco,
onde as pessoas são atendidas na
ordem que entram na fila: o primeiro a
chegar será o primeiro a ser atendido
TAD fila inclui os seguintes métodos auxiliares:
● size - Retorna o número de objetos na fila
● isEmpty - Retorna um booleano indicando se a fila está vazia.
● front - Retorna, mas não remove o objeto na frente da fila. Ocorre erro se a
fila estiver vazia.
Aula 8 - Filas 09/09/21
Herança de Interface para pilhas em Java
Para usar um tipo abstrato de dados em Java envolve dois passos:
● Definição de uma Application Programming Interface (API, ou interface), que
descreve os nomes dos métodos que o TAD suporta e como eles são
declarados e usados;
● Definição de exceções para qualquer erro que possa ocorrer.
exemplo de Herança de Interface
Herança de Implementação
Outro mecanismo que tem essa estrutura abaixo:
Lista 01 Questão 2
Crie uma classe QueueArray para implementar o Tipo Abstrato de Dados Fila. Você
deve utilizar arrays na implementação e a interface IQueue fornecida.
1. void enqueue(Integer value);2. Integer dequeue() throws Exception;
3. boolean isEmpty();
package com.diegopinheiro.ed1_01_lista;
public class QueueArray implements IQueue {
private Integer [] listaArray ;
private int head;
public QueueArray(int capacity) {
this.listaArray = new Integer [capacity];
this.head = 0;
}
@Override
public void enqueue(Integer value) {
if(this.isFull()) {
throw new IllegalStateException(" Nao pode colocar mais que 3");
}
listaArray[this.head] = value;
this.head ++;
}
@Override
public Integer dequeue() throws Exception {
if(this.isEmpty()) {
throw new IllegalStateException(" Ta cheio");
}
return head;
}
@Override
public boolean isEmpty() {
return this.head == 0;
}
private boolean isFull() {
return this.head == this.listaArray.length; } }
Revisão
public class QueueArray implements IQueue {
private Integer[] listaArray;
private int head;
public QueueArray(int capacity) {
this.listaArray = new Integer [capacity];
this.head = 0;
}
@Override
public void enqueue(Integer value) {
if(this.isFull()) {
throw new IllegalStateException("ta cheio
colega");
}
listaArray[this.head] = value;
this.head++;
}
private boolean isFull() {
return this.head == this.listaArray.length;
}
@Override
public Integer dequeue() throws Exception {
Integer num ;
if (this.isEmpty()) {
throw new IllegalStateException("Vazio");
}
num = this.listaArray [head-1] ;
this.listaArray[head-1] = null;
this.head--;
return num;
}
@Override
public boolean isEmpty() {
return this.head == 0; } }
Lista 01 Questão 3
Implemente o método void reverse(IQueue queueToBeReversed, IStack stackAuxiliary)
na classe Utils que reverte a fila queueToBeReversed. Apenas utilize os métodos da
IQueue e IStack para reverter a fila queueToBeReversed.
Ps: Uma Stack para reverter uma fila, assim vamos empilhar a fila
package com.diegopinheiro.ed1_01_lista;
import java.util.Iterator; // da onde veio isso??
public class Utils {
public static void reverse (IQueue queueToBeReversed, IStack
stackAuxiliary) {
try {
while (!queueToBeReversed.isEmpty()) {
stackAuxiliary.push(queueToBeReversed.dequeue());
}
while (!stackAuxiliary.isEmpty()) {
queueToBeReversed.enqueue(stackAuxiliary.pop());
}
}catch(Exception e) { e.printStackTrace(); } } }
Ps: try/catch: uso quando não quero que a exceção se perpetue pelo código, pois
não vou usar aquele "problema" em nenhum outro lugar.
● try{ … } - linhas de código que podem vir a lançar uma exceção.
● catch(tipo_excessao e) { … } - ação que ocorrerá quando a exceção for
capturada.
throws: quando quero passar a possível exceção do método que estou para outras
classes, quando o tratamento não é necessário naquela classe pois vou precisar da
exceção em outra classe.
throw: quando eu quero lançar uma exceção/quando quero que aquele método
específico de um erro(exceção)
Aula 9 - Listas Unicamente Encadeadas 13/09/21 (Faltei Total 3)
(Singly Linked Lista)
E mais uma estrutura de
dados abstrata, dinâmica
(seu comprimento pode
aumentar ou diminuir), e
recursiva.
Cada quadrado desse é
um node, que vai ter um
valor e o next. A lista
termina quando o next
aponta para null.
Como o nome diz, são nodos conectados por links que fazem a referência.
Esses links dizem como vai ser o acesso no nodo posterior. Os nodos podem
conter dados de qualquer tipo até mesmo objetos de outras classes.
Um array é limitado pois temos que declarar seu tamanho, assim se
esperamos mais itens vamos declarar mais espaços, e os espaços excedentes
podem não ser usados assim vai ter uma perda de desempenho (desperdiçando
memória). Já nas listas encadeadas adicionamos e retiramos os elementos de
acordo com a demanda (alocação dinâmica de memória).
Podemos imaginar como se fosse uma pessoa apontando para outra que tem
uma camisa preta, e essa de camisa preta aponta para (mesmo tipo - pessoa)
outra de camisa branca e por aí vai, ou a pessoa pode apontar para si mesmo.
Inserindo
Aula 10 - Listas Unicamente Encadeadas Parte 2 16/09/21
Explicou sobre o equals (retorna boolean) de 20:00 até 40:00.
? ==
true
CompareTo - retorna um inteiro
Size Listas Unicamente Encadeadas
1. Percorre o array para saber o tamanho. Começamos pelo head
(currentNode = this.head ).
2. O próximo nó e o próprio nó mais value e next assim:
currentNode = currentNode.getNext();
3. Fazer isso enquanto o nó for diferente de null :
while(currentNode != null)
4. Como e tamanho vamos incrementar e depois retornar esse tamanho,
assim você fecha o que a função pede retornando o incremento;
Aula 11 e 12 - Listas Unicamente Encadeadas 20/09/21 a 23/09/21
Delete (questão 6)
Deletar um node significa que ele perdeu a referência e o garbage collector do
programa percebe isso e desaloca a memória (apaga).
Não vamos escrever
nada para apagar
deixamos para o
garbage collector.
Vamos pegar o
getPrevious
Outro exemplo de aula,
caso base: aplicado até
numa lista com apenas 1 elemento.
1. Encontrar o node anterior ( previous começa no head), assim o previous
get.next nao for igual ao no que quer deletar passa para o próximo;
2. Atribuir ao próximo como o próximo do próximo;
Para o reverse
Dicas and Cheats Listas Unicamente Encadeadas
1. get (obter valor) ele vai ser uma função assim vai ter um retorno e se for set
(atribui valor) vai ser um método apenas tendo que colocar parâmetro entre
parênteses;
2. O size do SinglyLinkedList vai ser o mesmo de CircularLinkedList:
public int size() {
int size = 0;
SinglyListNode node = this.head;
while (node != null) {
size++;
node = node.getNext();
}
return size;
}
3. Para o método (função) isOrdered se estiver vazia vai estar ordenada!!
4. Qual a diferença entre ???
SinglyListNode node = this.head;
SinglyListNode newHead = new SinglyListNode(this.head,value);
5. No addFirst invés de colocar assim:
SinglyListNode newHead = new SinglyListNode(this.head, value);
ou
SinglyListNode newHead = this.head;
6. Às vezes Diego gosta de simplificar, logo fiquem atentos:
public boolean isOrdered(boolean ascending) {
if(isEmpty()) {
return true;
}
Integer lastValue; -- Integer lastValue = node.getValue()
SinglyListNode node; -- SinglyListNode node = this.head;
node = this.head;
lastValue = node.getValue();
7. O método addLast(value) e um espelho do addFirst ;
8. Lembre-se que a ordem dos parâmetros definida pelo construtor na
classe SinglyListNode vai ser aplicada em SinglyLinkedList;
9. No addFirst, addLast, isOrdered, reverse e delete, iremos usar o
isEmpty();
10.No delete podemos “deletar”, no início, meio ou fim. Assim sendo
Lista 02
1. Crie uma classe SinglyListNode que contém os atributos next do tipo
SinglyListNode, um atributo value do tipo Integer, um construtor para inicializar
value e next, e os métodos get and set desses atributos. Não utilize uma
variável de instância previous.
Ps: lista vazia o head == null
package com.diegopinheiro.ed01_02_lista;
public class SinglyListNode {
private SinglyListNode next ;
private Integer value;
public SinglyListNode(SinglyListNode next, Integer value) {
this.next = next;
this.value = value;
}
public SinglyListNode getNext() {
return next;
}
public void setNext(SinglyListNode next) {
this.next = next;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value; } }
// Aqui precisamos adicionar dois procedimentos: Funcao equals e
toString
// em alguma aula ele resumiu isso (aula 10) ??
@Override
public boolean equals(Object obj) {
if(this == obj)
return true;
if(obj == null)
return false;
if(getClass() != obj.getClass()) // da onde veio
getClass??
return false;
SinglyListNode other = (SinglyListNode) obj ;
return this.value.equals(other.value);
}
@Override
public String toString() {
return String.valueOf(this.value); } }
2. Crie uma classe de uma lista unicamente ligada SinglyLinkedList que
contenha a referência head para a cabeça da lista do tipo ListNode (não utilize
uma variável de instância tail), e contenha os seguintes métodos:
a. isEmpty(), que retorna true quando alista está vazia e false caso
contrário;
package com.diegopinheiro.ed01_02_lista;
public class SinglyLinkedList {
private SinglyListNode head;
public boolean isEmpty() {
// ele pede true quando a lista está vazia e false caso contrário;
// Inicialmente a lista está vazia, logo o head aponta para null, ai nao
precisa fazer if e else
return this.head == null;
}
b. addFirst(value), adiciona o elemento value no início da lista;
public void addFirst(Integer value) {
// aqui vai criar um novo no
SinglyListNode newHead = new
SinglyListNode(this.head,value);
this.head = newHead; }
// aqui adicionamos o value e depois declaramos que a cabeça e o no
que acabamos de instanciar
c. search(value), que retorna o nó ListNode cujo elemento procurado
value se encontra ou null caso o elemento não esteja na lista;
public SinglyListNode search(Integer value) {
SinglyListNode node = this.head; // ???
while(node != null) {
if(value == node.getValue()) {
// o que esse getValue faz??
return node;
}
node = node.getNext();
}
return null; }
d. size(), retorna o tamanho da lista;
public int size() {
// esse size vai ser o mesmo para listas circulares
int size = 0;
SinglyListNode node = this.head;
while (node != null) {
size++;
node = node.getNext();
}
return size; }
3. Implemente o método isOrdered(ascending) que retorna true caso os
elementos estejam ordenados e false caso contrário. Os elementos podem
estar ordenados ascendentemente quando ascending é true (i.e., 1,2,3,4) ou
descendentemente quando ascending é false (ie., 4,3,2,1).
???? Está dando loop
public boolean isOrdered(boolean ascending) {
// pq se está vazia, vai estar ordenada!!
if(isEmpty()) {
return true;
}
SinglyListNode node = this.head;
// aqui criamos um novo nó e dizemos que e" a cabeça (head)
Integer lastValue = node.getValue();
// o último valor e o no
while(node.getNext() != null) {
/* enquanto o próximo nó não for nulo, não vai estar vazia e assim
veremos se é ascendente ou descendente */
node = node.getNext();
if(ascending) {
if(lastValue > node.getValue()){
return false;
}
}else {
if(lastValue < node.getValue()){
return false;
}
}
lastValue = node.getValue(); //????
}
return true;
}
4. Implemente o método addLast(value) na classe SinglyLinkedList que
adiciona o value no fim da lista.
public void addLast(Integer value) { // espelho do addFirst
if(isEmpty()){
// se estiver vazia o último adc é igual ao primeiro por isso chama o
addFirst
addFirst(value);
return;
}
// lembre-se que a ordem definida pelo construtor em SinglyListNode
aplica-se aqui
SinglyListNode novoNode = new SinglyListNode(value,
null); // Aqui cria um novo no??
SinglyListNode node = this.head;
while(node.getNext() != null) {
node = node.getNext();
}
node.setNext(novoNode); }
5. Implemente o método reverse() na classe SinglyLinkedList que reverte a
ordem dos itens. Não crie uma nova instância da SinglyLinkedList ou
SinglyListNode. Atualize apenas as referências next de cada SinglyListNode e
head da SinglyLinkedList. DÚVIDA
public void reverse() {
if(isEmpty() || size() == 1) {
// nao tira o return pois vai ser o break do if
return;
}
SinglyListNode ultimoNode = this.head;
// está invertendo, assim o que era a cabeca passa a ser o ultimo
SinglyListNode node = ultimoNode.getNext();
// o próximo node
SinglyListNode nextNode = node.getNext(); //pq cria
esse??
do {
node.setNext(ultimoNode);
ultimoNode = node;
node = nextNode;
if (node != null) {
nextNode = node.getNext();
}
} while (node != null);
node = this.head;
this.head = ultimoNode;
node = search(node.getValue());
node.setNext(null); }
6. Implemente o método delete(node) na classe SinglyLinkedList.
public void delete(SinglyListNode nodeDelete) {
if(isEmpty()) {
return ;
}
SinglyListNode ultimoNode = this.head;
if(nodeDelete.equals(this.head)) {
/* se o nó a ser deletado for o inicio, como vai deletar o início se
está dizendo na linha acima que o ultimoNode = this.head*/
this.head = nodeDelete.getNext();
}else { // deletar no meio ou fim
while(ultimoNode != null) {
if(ultimoNode.getNext().equals(nodeDelete)) {
// ultimo vai ser deletado ????
ultimoNode.setNext(nodeDelete.getNext()); // ???
break;
}
ultimoNode = ultimoNode.getNext(); } } }
======================================================
Lista 02 COMPLETA
======================================================
package com.diegopinheiro.ed01_02_lista;
public class SinglyListNode {
private SinglyListNode next;
private Integer value;
public SinglyListNode(Integer value, SinglyListNode next ) {
this.next = next;
this.value = value;
}
public SinglyListNode getNext() {
return next;
}
public void setNext(SinglyListNode next) {
this.next = next;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
// precisamos adicionar dois procedimentos: Funcao equals e toString
@Override
public boolean equals(Object obj) {
if(this == obj)
return true;
if(obj == null)
return false;
if(getClass() != obj.getClass())
// checando se a classe deles é diferente
return false;
SinglyListNode other = (SinglyListNode) obj ;
return this.value.equals(other.value);
}
@Override
public String toString() {
return String.valueOf(this.value); // retorna o valor do no
} }
-----------------------------------------------------
package com.diegopinheiro.ed01_02_lista;
public class SinglyLinkedList {
private SinglyListNode head;
public boolean isEmpty() {
//Inicialmente a lista está vazia, logo o head aponta para null, ai nao precisa
fazer if e else
return this.head == null;
}
public void addFirst(Integer value) { // aqui vai criar um novo no
SinglyListNode newHead = new SinglyListNode(value, this.head);
// tive que trocar a ordem pq?? Obedece a ordem do construtor da classe
SinglyListNode
this.head = newHead;
}
public SinglyListNode search(Integer value) {
SinglyListNode node = this.head;
while(node != null) {
if(value == node.getValue()) {
return node;
}
node = node.getNext();
}
return null;
}
public int size() {
// esse size vai ser o mesmo para listas circulares
int size = 0;
SinglyListNode node = this.head; // pq usa
SinglyListNode??
while (node != null) {
size++;
node = node.getNext();
}
return size;
}
public boolean isOrdered(boolean ascending) {
// pq se esta vazia, vai estar ordenada?? Meio vago
if(isEmpty()) {
return true;
}
SinglyListNode node = this.head;
// aqui criamos um novo nó e dizemos que e" a cabeça (head)
Integer lastValue = node.getValue();
// o último valor e o no
while(node.getNext() != null) {
/* enquanto o próximo nó não for nulo não vai estar vazia e assim veremos se
e ascendente ou descendente */
node = node.getNext();
if(ascending) {
if(lastValue > node.getValue()){
return false;
}
}else {
if(lastValue < node.getValue()){
return false;
}
}
lastValue = node.getValue();
}
return true;
}
public void addLast(Integer value) {
// espelho do addFirst
if(isEmpty()){ // se estiver vazia o ultimo adc
e igual ao primeiro
addFirst(value);
return;
}
// lembre-se que a ordem definida pelo construtor em
SinglyListNode aplica-se aqui
SinglyListNode novoNode = new SinglyListNode(value,
null); // Aqui cria um novo no??
SinglyListNode node = this.head;
while(node.getNext() != null) { // Pq pega o
getNext()???
node = node.getNext();
}
node.setNext(novoNode);
}
public void reverse() {
if(isEmpty() || size() == 1) { // Pq nao tira o
retunr???
return;
}
SinglyListNode ultimoNode = this.head; // esta
invertendo
SinglyListNode node = ultimoNode.getNext(); // ???
SinglyListNode nextNode = node.getNext(); // ???
do {
node.setNext(ultimoNode);
ultimoNode = node;
node = nextNode;
if (node != null) {
nextNode = node.getNext();
}
} while (node != null);
node = this.head;
this.head = ultimoNode;
node = search(node.getValue());
node.setNext(null);
}
public SinglyListNode getHead() {
return this.head;
}
public void delete(SinglyListNode nodeDelete) {
if(isEmpty()) {
return ;
}
SinglyListNodeultimoNode = this.head;
if(nodeDelete.equals(this.head)) { /* se o no a ser
deletado for o inicio, como vai deletar o inicio se
esta dizendo na linha acima que o ultimoNode =
this.head*/
this.head = nodeDelete.getNext();
}else { // deletar no meio ou fim
while(ultimoNode != null) {
if(ultimoNode.getNext().equals(nodeDelete)) {
// ultimo vai ser deletado ????
ultimoNode.setNext(nodeDelete.getNext()); // ???
break;
}
ultimoNode = ultimoNode.getNext(); } } } }
Aula 13 - Listas Duplamente Encadeadas 27/09/21
Doubly Linked List
Agora os nodes vão ter 3 atributos sendo adicionado o previous que vai fazer
referência.
Ps: ele comentou sobre label attachment.
E aquela que possui duas referências ao invés de uma, permitindo que a lista
seja percorrida nos dois sentidos – do início para o final, e do final para o início.
Para que isto seja possível, cada nodo apresenta dois elos: um que armazena o
endereço do nodo imediatamente anterior na lista (Previous/Anterior) e o outro que
armazena o endereço do nodo seguinte (Next/Próximo).
Ps: A operação de criação (muda somente o tipo de
nodo utilizado) e de destruição da lista duplamente
encadeada, vai ser igual da lista simplesmente
encadeada. Já as operações de: inserção, remoção e
acesso devem ser adaptadas.
Adição/ inserção
O valor vai ser o valor, o old
head não tem (nulo).
DoublyListNode newHead = new DoublyListNode(value, this.head, null)
if (this.isEmpty ()){
tail = newHead;
}else{
head.setPrevious(newHead);
}
head = newHead;
Ele colocou
os passos no
desenho e
no código.
Aula 15 -
Listas
Duplamente Encadeadas parte 3 04/10/21
null
Aula 16 - Listas Circulares 07/10/21
Size para Listas Duplamente encadeadas
Fez na lista 3 parte 1 questão 2:
public int size() {
int size = 0;
DoublyListNode currentNode = this.head;
while(currentNode != null) {
size ++;
}
Dicas and Cheats Listas Duplamente Encadeadas
1. get (obter valor) ele vai ser uma função assim vai ter um retorno e se
for set (atribui valor) vai ser um método apenas tendo que colocar
parâmetro entre parênteses;
2. Diferença entre atributo e variável ???
3. O DoublyListNode vai ser a mesma coisa do SinglyListNode,
com a diferença que vai ter um atributo a mais: next.
4. O isEmpty()vai ter a mesma implementação da lista single
o ideal seria colocar assim:
return this.head == null && return this.tail == null;
5. Size vai ser exatamente igual ao da lista SinglyLinkedList:
public int size() {
int size = 0;
// o nó atual e o head, aí enquanto for diferente de nulo, vamos
ao próximo e incrementamos o size
DoublyListNode currentNode = this.head;
while(currentNode != null) {
size ++;
currentNode = currentNode.getNext();
}
return size;
}
6. Para o addFirst vamos criar um novo nó, sendo o mesmo um nó
que tem o início (head) e não tem fim (null), para dele fazer as
condicionais.
public void addFirst(Integer value) {
DoublyListNode newNo = new DoublyListNode ( value, this.head,
null);
if(this.isEmpty()) { // se estiver vazio a tail e o novo no(newHead)
this.tail = newNo;
}
else {
head.setPrevious(newNo); // senão, a cabeça vai ser o próximo no
que é o newNo (newHead)
}
head = newNo; // ??? no caso a cabeça e igual ao novo no
(newHead)
}
7. O search vai ser parecido com o size. Vamos criar dois nos para
percorrer a lista: temporário ( atribuímos ao this.head) e resultado
(atribuímos a null). Se o temporário for igual ao valor retorne o
temporário, caso não seja igual, pegamos o próximo. Se não for
nenhuma das condições acima retornaremos o resultado.
public DoublyListNode search(Integer value) {
if(isEmpty()) {
return null;
}
// vamos criar dois nos: temporário e resultado para percorrer a
lista
DoublyListNode temp = this.head;
DoublyListNode result = null;
do {
if(temp.getValue().equals(value)) {
// se o temporário for igual ao valor retorne o temporário
return temp;
}
temp = temp.getNext();
// caso não seja igual pegamos o próximo.
}while(temp != null);
return result;
// Se não for nenhuma das condições acima retornaremos o
resultado
}
8. O addLast vai ser um espelho do add first, sendo que usa tail pois
adiciona por último ( no caso ao invés de criarmos uma nova Cabeça (
newHead), vamos criar um newTail
9. O reverse() dúvida
10. O delete() antes de "deletar" temos que verificar se a lista vai estar
vazia ou apenas com um node, por isso checaremos os isEmpty() e o
size().
11. O isOrdered(boolean ascending) antes de confirmar a ordem,
temos que verificar se a lista vai estar vazia ou apenas com um node,
por isso checaremos os isEmpty() e o size(), assim se estiver vazia vai
estar ordenada e se o tamanho for único vai estar ordenada também
12.
Lista 3 - Parte 1
Questão 1 - Crie uma nova classe DoublyListNode e, além dos value e next,
adicione o atributo previous do tipo DoublyListNode. Crie um construtor para
inicializar os 3 atributos, e os métodos get and set dos atributos.
package com.diegopinheiro.ed01_03_lista;
public class DoublyListNode {
private Integer value;
private DoublyListNode next; // ja tinha esse
private DoublyListNode previous;
public DoublyListNode(Integer value, DoublyListNode next,
DoublyListNode previous) {
// construtor
this.value = value; // inicializar os atributos
this.next = next;
this.previous = previous;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public DoublyListNode getNext() {
return next;
}
public void setNext(DoublyListNode next) {
this.next = next;
}
public DoublyListNode getPrevious() {
return previous;
}
public void setPrevious(DoublyListNode previous) {
this.previous = previous;
}
PS: Ele falou anteriormente sobre esse equals
@Override
public boolean equals(Object obj) {
if(this == obj) {
return true;
}
if(obj instanceof DoublyListNode) {
DoublyListNode other = (DoublyListNode) obj;
return this.value.equals(other.value);
}
return false;
????????? Ou
@Override
public boolean equals(Object obj) {
if(this == obj)
return true;
if(obj == null)
return false;
if(getClass() != obj.getClass())
// checando se a classe deles é diferente
return false;
DoublyListNode other = (DoublyListNode) obj ;
return this.value.equals(other.value);
}
@Override
public String toString() {
return String.valueOf(this.value);
// retorna o valor do no } }
Questão 2 -Crie uma outra classe DoublyLinkedList que, além do atributo head
para a cabeça da lista da DoublyLinkedList, também contenha a referência tail
para a calda a lista.
package main.java.com.diegopinheiro.ed01_03_lista;
public class DoublyLinkedList {
private DoublyLinkedList head, tail;
public DoublyLinkedList(DoublyListNode head, DoublyListNode tail)
{
this.head = head;
this.tail = tail;
}
public DoublyListNode getHead() {
return head;
}
public void setHead(DoublyListNode head) {
this.head = head;
}
public DoublyListNode getTail() {
return tail;
}
public void setTail(DoublyListNode tail) {
this.tail = tail; }
Questão 3 - Considerando que a DoublyLinkedList também tem um atributo tail e
que o DoublyNodeList agora possui o novo atributo previous, implemente os
seguintes métodos:
1. isEmpty(), que retorna true quando a lista está vazia e false caso contrário;
2. size(), retorna o tamanho da lista;
3. addFirst(value), adiciona o elemento elem no início da lista;
4. search(value), que retorna o nó ListNode cujo elemento procurado elem se
encontra ou null caso o elemento não esteja na lista;
5. addLast(value) que adiciona no fim da lista;
6. reverse() que reverte a ordem dos itens da lista;
7. o método delete(node) que deleta no node da lista.
8. isOrdered(ascending) que retorna true caso os elementos estejam ordenados
e false caso contrário. Os elementos podem estar ordenados ascendentemente
quando ascending é true (i.e., 1,2,3,4) ou descendentemente quando ascending
é false (ie., 4,3,2,1).
package com.diegopinheiro.ed01_03_lista;
public class DoublyLinkedList {
private DoublyListNode head, tail;
public DoublyLinkedList(DoublyListNode head, DoublyListNodetail)
{
this.head = head;
this.tail = tail;
}
public DoublyListNode getHead() {
return head;
}
public void setHead(DoublyListNode head) {
this.head = head;
}
public DoublyListNode getTail() {
return tail;
}
public void setTail(DoublyListNode tail) {
this.tail = tail;
}
1) public boolean isEmpty() {
return this.head == this.tail;
// o ideal seria colocar assim:
//return this.head == null && return this.tail == null
}
2) public int size() {
int size = 0;
DoublyListNode currentNode = this.head;
while(currentNode != null) {
size ++;
currentNode = currentNode.getNext();
o no corrido e o head, aí enquanto for diferente de nulo, vamos ao próximo e
incrementamos o size
}
return size;
}
3)public void addFirst(Integer value) {
DoublyListNode newHead = new DoublyListNode(value, this.head,
null);
// vamos criar um novo nó, sendo o mesmo um nó que tem o início (head) e
nao tem fim (null),para dele fazer as condicionais
// essa ordem obedece a ordem do CONSTRUTOR
// previous e null
if(this.isEmpty()) {
// se estiver vazio a tail e o novo no(newHead)
tail = newHead;
}else {
head.setPrevious(newHead); //senão, a cabeça vai ser o próximo
no que é o newHead. Pq usa o Previous???
}
head = newHead;
// Pq não usa o this.head??? no caso a cabeça e igual ao novo no
(newHead)}
5) public void addLast(Integer value) {
// vai ser um espelho do add first, sendo que usa tail pois adc por último
DoublyListNode newTail= new DoublyListNode(value,null,
this.tail);
if(this.isEmpty()) {
this.head = newTail; //se está vazio a cabeça e o
rabo
}else {
tail.setPrevious(newTail); // Previous ?
}
tail = newTail;
}
}
4) public DoublyListNode search(Integer value) {
// vai ser a mesma coisa do size
if(this.isEmpty()) {
return null;
}
// percorrer a lista
DoublyListNode resultado = null;
DoublyListNode temporaria = this.head;
while(temporaria != null) {
if(temporaria.getValue().equals(value)) {
return temporaria;
}
temporaria = temporaria.getNext();
}
return resultado;
}
6) public void reverse() {
// como vai reverter vamos ter que atribuir 4 nos para as diversas situacoes
DoublyListNode nodeAnterior = this.head; // no caso e o 1
no
DoublyListNode nodeMeio = this.head.getNext(); // pegamos o
proximo
DoublyListNode nodeProximo = nodeMeio.getNext(); // proximo do
proximo
DoublyListNode oldHead = this.head;
do {
nodeMeio.setNext(nodeAnterior);
// proximo troca para o meio e o meio vai para o anterior
nodeMeio.setPrevious(nodeProximo);
// a anterior do nodeMeio era o anteriorNode, sendo que agora é o próximo
nodeAnterior = nodeMeio;
nodeMeio = nodeProximo;
if(nodeMeio != null) {
nodeProximo = nodeMeio.getNext();
// o primeiro no nao esta sendo alterado
}
}while(nodeMeio != null);
// se for nulo vai ter apenas o nodeAnterior e assim não vai reverter
// ???? toda essa passagem não entendi
oldHead.setPrevious(oldHead.getNext());
oldHead.setNext(null); // virou o tail, ai o próximo do tail sempre e null
this.tail = this.head;
this.head = nodeAnterior;
}
7) public void delete(DoublyListNode nodeDelete) {
// antes de "deletar" temos que verificar se a lista vai estar vazia ou apenas
com um node
if(isEmpty() || size() == 1) {
// pq nao tira o head e tail é só colocar o return??
this.head = null;
this.tail = null;
return;
// se não colocar o return ele vai para parte de baixo
}
DoublyListNode anteriorNode =
nodeDelete.getPrevious(); // atribuindo a um node previousNode que
deleta o node anterior
DoublyListNode proximoNode = nodeDelete.getNext();
// atribuindo a um node nextNode que deleta o próximo node
if(nodeDelete.equals(this.head)) { // se o nor a ser
deletado for a (igual) cabeça, ao próximo node deve ser nulo
proximoNode.setPrevious(null);
this.head = proximoNode; // atualizando a cabeça
para o próximo node
}
else if(nodeDelete.equals(this.tail)) {
// se o nor a ser deletado for a (igual) calda, ao node anterior deve ser nulo
anteriorNode.setNext(null);
this.tail = anteriorNode;
// atualizando a calda para o node anterior
}
else {
// se nenhuma das condições acima for encaixada faremos:
proximoNode.setPrevious(anteriorNode); // ?????
anteriorNode.setNext(proximoNode); // ?????
}
}
8) public boolean isOrdered(boolean ascending) {
if (isEmpty() || size() == 1) {
return true;
}
DoublyListNode node = this.head;
Integer previousValue;
while(node.getNext() != null) {
node = node.getNext();
previousValue = node.getPrevious().getValue();
if (ascending) {
if (previousValue > node.getValue()) {
//verifica se a ordem crescente esta incorreta
return false;
}
} else {
if (previousValue < node.getValue()) {
//verifica se a ordem decrescente esta incorreta
return false;
}
}
}
return true;
}
======================================OU=============
Tirar essa dúvida com Aquiles:
public boolean isOrdered(boolean ascending) {
// antes de confirmar a ordem, temos que verificar se a lista vai
estar vazia ou apenas com um node, por isso checaremos os isEmpty() e o
size().
if (isEmpty() || size() == 1) { // se estiver vazia
vai estar ordenada e se o tamanho for único vai estar ordenada
também
return true;
}
DoublyListNode node = this.head;
Integer value;
while(node.getNext() != null) { // enquanto o
proximo no for diferente de nulo, significa que nao chegou ao fim
this.head.getNext();
value = this.head.getNext().getValue();
if(ascending) {
if(value > this.head.getValue()) {
//verifica se a ordem crescente esta incorreta
return false;
}
else {
if(value < this.head.getValue()) {
//verifica se a ordem decrescente esta incorreta
return false;
}
}
}
}
return true;
}
========================================================
Revisão
package com.diegopinheiro.ed01_03_lista;
public class DoublyLinkedList {
private DoublyListNode head;
private DoublyListNode tail;
public DoublyListNode getHead() {
return head;
}
public void setHead(DoublyListNode head) {
this.head = head;
}
public DoublyListNode getTail() {
return tail;
}
public void setTail(DoublyListNode tail) {
this.tail = tail;
}
public boolean isEmpty() {
return this.head == null; // mesma implementação da lista
single
// o ideal seria colocar assim: return this.head == null && return this.tail ==
null;
}
public void addFirst(Integer value) {
DoublyListNode newHead = new DoublyListNode(value, this.head,
null);
// essa ordem obedece a ordem do CONSTRUTOR
//criação de novo no previous e null
if(this.isEmpty()) {
this.tail = newHead;
}else {
DoublyListNode oldHead = this.head;
oldHead.setPrevious(newHead);
// pq coloca o set?? Previous???
}
this.head = newHead;
}
public int size() {
int size = 0;
DoublyListNode currentNode = this.head;
while(currentNode != null) {
size ++;
currentNode = currentNode.getNext();
}
return size;
}
public void addLast(Integer value) {
// vai ser um espelho do add first, sendo que usa tail pois adc por último
DoublyListNode newTail = new DoublyListNode(value, null,
this.tail);
if(this.isEmpty()) {
this.head = newTail;
// se está vazio a cabeça e o rabo
}else {
this.tail.setNext(newTail); // tem que ser set
pois ele muda, o get retorna
}
this.tail = newTail;
}
public DoublyListNode search(Integer value) {
// vai ser a mesma coisa do size
if(this.isEmpty()) {
return null;
}
// percorrer a lista
DoublyListNode temporaria = this.head;
while(temporaria != null) {
if(temporaria.getValue().equals(value)) {
return temporaria;
}
temporaria = temporaria.getNext();
}
return null;
}
public void delete(DoublyListNode nodeDelete) {
// antes de "deletar" temos que verificar se a lista vai estar vazia ou apenas
com um node
if(isEmpty() || size() == 1 ) {
this.head = null;
this.tail = null;
return ;
// se não colocar o return ele vai para parte de baixo
}
DoublyListNode anteriorNode =
nodeDelete.getPrevious(); // criando um no previousNode
DoublyListNode proximoNode = nodeDelete.getNext();
if(nodeDelete.equals(this.head)) {
proximoNode.setPrevious(null);
this.head = proximoNode;
}
else if(nodeDelete.equals(this.tail)) {
anteriorNode.setNext(null);
this.tail= anteriorNode;
}
else {
proximoNode.setPrevious(anteriorNode);
anteriorNode.setNext(proximoNode);
}
}
public boolean isOrdered(boolean ascending) {
return false;
}
public void reverse() {
DoublyListNode anteriorNode = this.head;
DoublyListNode meioNode = this.head.getNext();
DoublyListNode proximoNode = this.head.getNext().getNext();
DoublyListNode oldHead = this.head;
do {
meioNode.setNext(anteriorNode); // desenhar
meioNode.setPrevious(proximoNode);
anteriorNode = meioNode;
meioNode = proximoNode;
if(meioNode != null) {
proximoNode = meioNode.getNext(); // o
primeiro no nao esta sendo alterado
}
}while(meioNode != null);
oldHead.setPrevious(oldHead.getNext());
oldHead.setNext(null);
this.tail = this.head;
this.head = anteriorNode;
}
}
Questão 4
Crie uma classe Utils e implemente o método static isPalindrome(list) que recebe
uma list do tipo DoublyLinkedList e retorna true caso a sequência de values na
list seja um palíndromo e false caso contrário. Um palíndromo é uma sequência
que tem a propriedade de poder ser lida tanto da esquerda para a direita quanto da
direita para a esquerda. Por exemplo, 2 -> 5 -> 5 -> 2 é um palíndromo e 2 -> 5 -> 1
-> 2 não é um palíndromo.
Listas Circulares 07/11/21
Dicas and Cheats Listas Circulares
1. O CircularListNode vai ser igual ao DoublyListNode no caso de declarar as
variáveis:
public class CircularListNode {
private Integer value;
private CircularListNode next, previous;
2. Depois gera os get e set lembrando:
get - (obter valor) ele vai ser uma função assim vai ter um retorno
set - (atribui valor) vai ser um método apenas tendo que colocar parâmetro
entre parênteses;
Lista 3 - Parte 2
Questão 5 - Crie uma class CircularLinkedList que, em vez de possuir head and
tail, possui uma sentinel do tipo CircularListNode inicializado com ambos next e
previous apontando para sentinel e implemente os seguintes métodos:
1. isEmpty(), que retorna true quando a lista está vazia e false caso
contrário;
2. addFirst(elem), adiciona o elemento elem no início da lista;
3. search(elem), que retorna o nó ListNode cujo elemento procurado elem
se encontra ou null caso o elemento não esteja na lista;
4. size(), retorna o tamanho da lista;
5. addLast(elem) que adiciona no fim da lista;
public void addLast(Integer value) {
CircularListNode node = new CircularListNode(value,
null, getTail());
if(isEmpty()) {
setHead(node);
}else {
getTail().setNext(node);
}
setTail(node);
}
=========================================
public void addLast(Integer value) {
CircularListNode oldNode = getTail();
CircularListNode newNode = new CircularListNode(value,
null, oldNode);
oldNode.setNext(newNode);
setTail(newNode);
}
6. reverse() que reverte a ordem dos itens da lista;
7. o método delete(node) que deleta no node da lista.
if(isEmpty() || size() == 1 ) {
this.sentinel.setNext(this.sentinel);
this.sentinel.setPrevious(this.sentinel);
return ; // se nao colocar o return ele vai para
parte de baixo
}
CircularListNode anteriorNode =
nodeDelete.getPrevious(); // criando um no previousNode
CircularListNode proximoNode = nodeDelete.getNext();
if(nodeDelete.equals(getHead())) {
setHead(proximoNode);
}
else if(nodeDelete.equals(getTail())) {
setTail(anteriorNode);
}
else {
proximoNode.setPrevious(anteriorNode);
anteriorNode.setNext(proximoNode);
}
}
====================================
public void delete(CircularListNode nodeDelete) {
CircularListNode anteriorNode =
nodeDelete.getPrevious();
CircularListNode proximoNode = nodeDelete.getNext();
anteriorNode.setNext(proximoNode); // basta tirar a
referencia dele e o garbagge colector destroi
proximoNode.setPrevious(anteriorNode);
}
=======================================================
public boolean isOrdered(boolean ascending) {
if(isEmpty()) {
return true;
}
CircularListNode node = getHead();
do {
if(ascending) {
if(node.getValue() >
node.getNext().getValue()) {
return false;
}
}else {
if(node.getValue() <
node.getNext().getValue()) {
return false;
}
}
node = node.getNext();
}while (node.getNext() != this.sentinel);
return true;
}
Questão 6 - Implemente o método copy() na CircularLinkedList que retorna uma
cópia também do tipo CircularLinkedList baseado no objeto em que o método foi
chamado. Utilize o método addLast(value) implementado anteriormente.
Questão 7 - Implemente o método isEquals(list) na CircularLinkedList que
recebe um list do tipo CircularLinkedList e retorna true caso a list seja igual a
lista na qual o método foi chamado ou false caso contrário.
public boolean isEquals(CircularLinkedList l2) {
if(size() != l2.size()) {
return false;
}
CircularListNode nodeList1 = getHead();
CircularListNode nodeList2 = l2.getHead();
do {
if(nodeList1.getValue() != nodeList2.getValue()) {
return false;
}
nodeList1 = nodeList1.getNext();
nodeList2 = nodeList2.getNext();
}while(nodeList1.getNext() != this.sentinel); // se
nao colocar getNext() o do While vai querer pegar o rpxoximo =
null point exception
return true;
}
Questão 8 - Implemente o método get(index) na CircularLinkedList que percorre
a lista circular e obtém o elemento da posição index da lista e retorna uma exceção
caso a lista esteja vazia. Caso index > 0 continue circulando a lista até encontrar o
valor. Dado, por exemplo, a list = {1,2,3}, list.get(0) == list.get(3) == list.get(6) == 1.
Da mesma forma, list.get(1) == list.get(4) == list.get(7) == 2. Dica: você tem que
“pular” a sentinela.
public int get(Integer index ) throws Exception {
if(isEmpty()) {
throw new Exception("List is empty");
}
CircularListNode node = getHead();
for(int i = 0; i < index ; i ++) {
node = getSuccessor(node);
}
return node.getValue();
}
Lista 03 COMPLETA
package com.diegopinheiro.ed01_03_lista;
public class CircularLinkedList {
private CircularListNode sentinel; // criou uma etiqueta
public CircularLinkedList() {
this.sentinel = new CircularListNode(null, null, null);
// sentinela sem valor
this.sentinel.setNext(this.sentinel);
this.sentinel.setPrevious(this.sentinel);
}
public boolean isEmpty() {
return getHead() == this.sentinel;
}
public CircularListNode getHead() {
return this.sentinel.getNext();
}
public void addFirst(Integer value) {
CircularListNode node = new CircularListNode(value,
getHead(), this.sentinel);
if(isEmpty()) {
setTail(node);
}else {
getHead().setPrevious(node);
}
setHead(node);
}
public void setHead(CircularListNode node) {
node.setPrevious(this.sentinel);
this.sentinel.setNext(node);
}
public void setTail(CircularListNode node) {
node.setNext(this.sentinel);
this.sentinel.setPrevious(node);
}
public int size() {
int size = 0;
CircularListNode currentNode =
this.getHead();
while(currentNode != this.sentinel) {
size ++;
currentNode = currentNode.getNext();
}
return size;
}
public void addLast(Integer value) {
CircularListNode node = new CircularListNode(value,
null, getTail());
if(isEmpty()) {
setHead(node);
}else {
getTail().setNext(node);
}
setTail(node);
}
public boolean isOrdered(boolean ascending) {
return false;
}
public CircularListNode search(Integer value) {
if(isEmpty()) {
return null;
}
CircularListNode auxilio = getHead();
while(auxilio != this.sentinel) {
if(auxilio.getValue() == value) {
return auxilio;
}
auxilio = auxilio.getNext();
}
return null;
}
public void delete(CircularListNode nodeDelete) {
if(isEmpty() || size() == 1 ) {
this.sentinel.setNext(this.sentinel);
this.sentinel.setPrevious(this.sentinel);
return ; // se nao colocar o return ele vai para
parte de baixo
}
CircularListNode anteriorNode =
nodeDelete.getPrevious(); // criando um no previousNode
CircularListNode proximoNode = nodeDelete.getNext();
if(nodeDelete.equals(getHead())) {
setHead(proximoNode);
}
else if(nodeDelete.equals(getTail())) {
setTail(anteriorNode);
}
else {
proximoNode.setPrevious(anteriorNode);
anteriorNode.setNext(proximoNode);
}
}
public CircularListNode getTail() {
return this.sentinel.getPrevious();
}
public boolean isEquals(CircularLinkedListl2) {
return false;
}
public CircularLinkedList copy() {
CircularLinkedList lista = new CircularLinkedList();
CircularListNode auxilio = getHead();
while(auxilio != this.sentinel) {
lista.addLast(auxilio.getValue());
auxilio = auxilio.getNext();
}
return lista;
}
public int get(int i) throws Exception {
if(isEmpty()) {
throw new Exception("List is empty");
}
return 0;
}
public CircularListNode getSuccessor (CircularListNode
currentNode) throws Exception {
if(isEmpty()) {
throw new Exception("List is empty");
}
if(currentNode.getNext() == this.sentinel) {
return currentNode.getNext().getNext();
}
return currentNode.getNext();
}
public void reverse() {
}
}
Aula 16 07/10/21
Quando uma lista linear encadeada apresenta um elo ligando o último nodo
ao primeiro, ela se torna uma lista circular. As operações apresentadas para listas
simplesmente encadeadas podem ser adaptadas para listas circulares. A criação da
lista não é alterada, uma vez que somente o ponteiro da lista é inicializado. A lista é
vazia quando o ponteiro para o seu início é nulo. A operação de destruição da lista é
praticamente a mesma, mudando somente a identificação do último nodo a ser
liberado, que é aquele que contém o endereço do primeiro em seu campo de elo. Já
as operações de inserção, remoção e busca apresentam algumas alterações
SENTINEL - o próximo dele é ele mesmo e o anterior é ele mesmo.
Não temos mais head e tail, são
trocados por getHead e getTail .
Inicializamos o Sentinel.
Add First
Ps: list node tem 3 variáveis de instância??
passo e criar o nó, depois
CircularListNode newHead = new CircularListNode (value, getHead, sentinel)
if(isEmpty()){
}
getHead().setPrevious(newHead);
setHead(newHead);
Ps: o previous vai ser sempre o sentinel
Ps: esse getHead faz o papel do oldHead (Diego prefere colocar oldHead pois hoje
está fácil de perceber que está implícito, mas em 10 anos na frente não saberemos).
Aula 18 14/10/21
Considere pessoas dispostas em um círculo para serem executadas uma a uma
até que apenas uma sobreviva. As n pessoas são colocadas em círculo nas
posições de 0 até n-1. Partindo da posição 0, cada cada m-ésima vai sendo
executada percorrendo o círculo até que apenas 1 pessoa sobreviva.
O josephus problem consiste em encontrar qual a posição inicial uma pessoa
deve escolher para não ser executada.
Crie a classe JosephusProblem e implemente o método estático Integer[]
solve(int m, int n) para retornar a ordem na qual as pessoas são executadas.
- Por exemplo, solve(2,7) deve retornar {1, 3, 5, 0, 4, 2, 6}. Ou seja, a pessoa na
posição 6 sobrevive.
- Por exemplo, solve(4,7) deve retornar {3, 0, 5, 4, 6, 2, 1}. Ou seja, a pessoa na
posição 1 sobrevive.
1. Utilize uma CircularLinkedList
2. Os métodos get, search, e delete podem ajudar;
3. A criação de um método getSuccessor(node) na lista circular pode ajudar a
evitar retornar a sentinel;
4. A criação de um get(currentNode, index) pode ajudar também.
Aula 19 18/10/21
Ele foi convencido a não fazer a prova hoje!!
Delete(node)
Ele falou novamente do
garbage collector, assim
vamos tirar as referências
do no que queremos
deletar.
Para fazer um by-pass” vamos setar o anterior assim:
next = nodeDelete.getNext();
previous = nodeDelete.getPrevious();
next.setPrevious(previous);
previous.setNext(next);
Nesse ultimo print serve para
deletar o ultimo no.
ps: 8:36 -
mostrou como
era o delete
antigo com 2
linhas
Prova 1
1. Sua tela inteira deve estar compartilhada durante todo o tempo da avaliação,
caso contrário sua avaliação será anulada.
2. Você deve estar presente na sala durante todo o tempo da avaliação caso contrário
sua avaliação será anulada.
3. Você deve utilizar o projeto java disponibilizado em formato .ZIP no classroom
da disciplina.
4. Você pode reutilizar qualquer código implementados por você em sua listas
da disciplina de qualquer forma.
5. Sua implementação deve estar dentro da pasta src/main/java (não coloque dentro
da pasta src/test/java).
6. A submissão deve conter todo o projeto compactado em formato .ZIP
7. O nome do arquivo .ZIP submetido deve respeitar a nomenclatura recebida
exceto NOME_SOBRENOME que devem ser substituídos por seu nome e
sobrenome, respectivamente.
8. A submissão não deve ser feita após o prazo (nem 1 minuto a mais)
Crie uma class CircularLinkedList que, em vez de possuir head and tail, possui uma
sentinel do tipo ListNode inicializado com ambos next e previous apontando para
sentinel.
Considerando a CircularLinkedList criada, faça as questões a seguir.
Questão 1
Implemente os métodos
1. isEmpty(), que retorna true quando a lista está vazia e false caso
contrário;
2. addFirst(value), adiciona o elemento value no início da lista;
3. addLast(value) que adiciona no fim da lista;
4. reverse() que reverte a ordem dos nós da lista;
5. size() que retorna a quantidade de nós na lista;
Questão 2
Implemente o método toString() que retorna a representação da lista em string como
uma sequência de cada value contido na lista. Exemplo: [1, 2, 3, 4]
Questão 3
Implemente um método copy() que retorna uma cópia também do tipo
CircularLinkedList baseado no objeto em que o método foi chamado. Utilize o
método addLast(value) implementado anteriormente. Não modifique a lista original na
qual o método copy() foi chamado.
Questão 4
Implemente o método isReverse(otherList) em uma CircularLinkedList que recebe
como parâmetro otherList, um objeto também também do tipo CircularLinkedList, e
retorna true caso otherList esteja na ordem revertida em relação à lista no qual o
método isReverse foi
chamado. Por exempl, caso list seja {1,2,3} e otherList seja {3,2,1},
então list.isReverse(otherList) retorna true.
Prova 2
Crie uma class CircularLinkedList que, em vez de possuir head and tail, possui uma
sentinel
do tipo ListNode inicializado com ambos next e previous apontando para sentinel.
Considerando a CircularLinkedList criada, faça as questões a seguir.
Questão 1
Implemente os métodos
1. isEmpty(), que retorna true quando a lista está vazia e false caso contrário;
2. addFirst(value), adiciona o elemento value no início da lista;
3. addLast(value) que adiciona no fim da lista;
4. reverse() que reverte a ordem dos nós da lista;
5. size() que retorna a quantidade de nós na lista;
Questão 2
Implemente o método toString() que retorna a representação da lista em string como
uma sequência de cada value contido na lista. Exemplo: [1, 2, 3, 4]
Questão 3
Implemente o método deleteAll(value) que deleta todos os nós da lista cujo value é
value.
Questão 4
Implemente o método get(index) na CircularLinkedList que percorre a lista circular e
obtém o
elemento da posição index da lista ou retorna uma exceção caso a lista esteja vazia.
Index
pode ser positivo ou negativo. Por exemplo, se list = {1,2,3,4}, então
- list.get(0) == list.get(4) == list.get(-4) == list.get(8) == list.get(-8) == 1.
- list.get(1) == list.get(-3) == list.get(5) == list.get(-7) == 2.
Projeto
Considere pessoas dispostas em um círculo para serem executadas uma a uma
até que apenas uma sobreviva. As n pessoas são colocadas em círculo nas
posições de 0 até n-1. Partindo da posição 0, cada cada m-ésima vai sendo
executada percorrendo o círculo até que apenas 1 pessoa sobreviva. O josephus
problem consiste em encontrar qual a posição inicial uma pessoa deve escolher
para não ser executada.
Crie a classe JosephusProblem e implemente o método estático Integer[]
solve(int m, int n) para retornar a ordem na qual as pessoas são executadas.
- Por exemplo, solve(2,7) deve retornar {1, 3, 5, 0, 4, 2, 6}. Ou seja, a pessoa na
posição 6 sobrevive.
- Por exemplo, solve(4,7) deve retornar {3, 0, 5, 4, 6, 2, 1}. Ou seja, a pessoa na
posição 1 sobrevive.
1. Utilize uma CircularLinkedList
2. Os métodos get, search, e delete podem ajudar;
3. A criação de um método getSuccessor(node) na lista circular pode ajudar a
evitar retornar a sentinel;
4. A criação de um get(currentNode, index) pode ajudar também.
Lista: 04 – Pilhase Filas com Listas Circulares
Interface como se fosse um conjunto.A intersecção entre esses e em comum entre
eles.
Questão 1 Considerando a interface genérica IStack<Value> de Value, implemente
a classe genérica StackCircularLinkedList<Value> de Value que implements
IStack<Value>, ou seja, faz herança de interface (i.e., subtyping apenas).
Utilizando uma Lista Circular com sentinela como base, a classe
StackCircularLinkedList<Value> deve possuir os seguintes métodos:
1. Value pop() throws Exception
2. void push(Value value)
3. boolean isEmpty()
Questão 2 Considerando a interface genérica IQueue<Value> de Value,
implemente a classe genérica StackCircularLinkedList<Value> de Value que
implements IQueue <Value>, ou seja, faz herança de interface (i.e., subtyping
apenas). Utilizando uma Lista Circular com sentinela como base, a classe
QueueCircularLinkedList<Value> deve possuir os seguintes métodos:
1. void enqueue(Value item)
2. Value dequeue() throws Exception
3. boolean isEmpty()
package com.diegopinheiro.ed01_04_lista;
public class CircularListNode <Value>{
private Value value;
private CircularListNode <Value> next;
private CircularListNode <Value> previous;
public CircularListNode(Value value, CircularListNode <Value>
next, CircularListNode <Value> previous) {
this.value = value;
this.next = next;
this.previous = previous;
}
public <Value>Object getValue() {
return this.value;
}
public void setValue(Value value) { //
this.value = value;
}
public CircularListNode <Value> getNext() {
return next;
}
public void setNext(CircularListNode <Value> next) {
this.next = next;
}
public CircularListNode <Value> getPrevious() {
return previous;
}
public void setPrevious(CircularListNode <Value> previous) {
this.previous = previous;
}
@Override
public boolean equals (Object obj) {
CircularListNode other = (CircularListNode) obj;
return this.value.equals(this.value);
}
@Override
public String toString() {
return String.valueOf(this.value);
}
}
package com.diegopinheiro.ed01_04_lista;
public class CircularLinkedList <Value>{
public CircularListNode <Value> sentinel;
public CircularLinkedList() {
this.sentinel = new CircularListNode(0, null, null);
this.sentinel.setNext(this.sentinel);
this.sentinel.setPrevious(this.sentinel);
}
public boolean isEmpty() {
return getHead() == this.sentinel; // return
this.sentinel.getNext() == this.sentinel;
}
public CircularListNode getHead() {
return this.sentinel.getNext();
}
public CircularListNode getTail() {
return this.sentinel.getPrevious();
}
public void setHead(CircularListNode node) {
node.setPrevious(this.sentinel);
this.sentinel.setNext(node);
}
public void setTail(CircularListNode node) {
node.setNext(this.sentinel);
this.sentinel.setPrevious(node);
}
public void addFirst(Value value) {
CircularListNode oldHead = this.sentinel.getNext();
CircularListNode newHead = new CircularListNode(value,
oldHead, this.sentinel);
oldHead.setPrevious(newHead);
this.sentinel.setNext(newHead);
}
public void addLast(Value value) {
CircularListNode oldTail = this.sentinel.getNext();
CircularListNode newTail = new CircularListNode(value,
this.sentinel, oldHead);
oldTail.setNext(newTail);
this.sentinel.setNext(newHead);
}
public CircularListNode getSuccessor (CircularListNode <Value>
currentNode) throws Exception {
if(isEmpty()) {
throw new Exception("List is empty");
}
if(currentNode.getNext() == this.sentinel) {
return currentNode.getNext().getNext();
}
return currentNode.getNext();
}
}
package com.diegopinheiro.ed01_04_lista;
public class StackCircularLinkedList <Value> implements IStack
<Value> {
private CircularLinkedList <Value> list ;
//this.stack = new Integer[value];
public StackCircularLinkedList () { //
construtor para inicializar
this.list = new CircularLinkedList<Value>();
}
@Override
public boolean isEmpty() {
return this.list.isEmpty();
}
@Override
public void push(Value key) {
this.list.addFirst(key);
// antes de adc temos que saber se a pilha está cheia ou
vazia
//if (this.isFull()) {
// throw new IllegalStateException("Nao da");
}
// nao tem o isFull pois so precisamos de apenas as funcoes
da pilha
@Override
public Value pop() throws Exception {
Integer num;
if (this.isEmpty()) {
throw new IllegalStateException("Stack is Empty");
}
else {
CircularListNode node = list.getHead();
list.delete(node);
return (Value) node.getValue();
}
return null;
}
}
package com.diegopinheiro.ed01_04_lista;
public class QueueCircularLinkedList<value> {
public boolean isEmpty() {
return false;
}
public void enqueue(Integer valueFirst) {
}
public Integer dequeue() {
return null;
}
}
Aula 23 01/1/21
Aula 24 04/01/21
Stack com singly Linked List
O push se traduz num addFirst ou num addLast:
Para um pop:
- verificar se está vazia
node = getHead()
Num processo inverso seria no addLast:
----------------------------------------
8:49
Aula 27 18/11/21
Quando formos criar nossos nós
public class Node < key implements Comparable < key> , Value > {
private Key key;
private Value value;
private Node < key, value >; left;
private Node < key, value > right;
Árvores
Tipo específico de grafos. Precisa da raiz para existir, eles podem estar
ligados de forma direta ou indireta. No caso o grau vai ser determinado pela
quantidade de nós que forem criados a partir de outro
Árvores Binárias
Consideramos que uma árvore vai ter subárvores, podendo elas estarem vazias ou
não .
Árvore binária de Busca - os nós possuem :
1. Comparable Key
2. Value
3. Restrição de Busca
Em uma BST cada nó possui uma comparable key ( respectivo Value, e satisfaz a
restrição que a key de qualquer nó é maior que as keys de qualquer nó em sua
subárvore esquerda e menor que as keys de qualquer nó da substring direita.
Aula 22/11/21
O A e menor que E por isso fica abaixo, podemos ver o no como um nó ou uma
árvore,
8:00 até 8:34
public Value get (key x) {
return get(this.root, key) ;
private Value get ( node <key,value> x, key x ) {
// métodos com o mesmo nome o que os diferencia são os argumentos
if(x == null ){
return null;
}
// se não estiver vazia:
int compare = key.compareTo(x.getkey());
if (compare < 0 ){
return get(x.getLeft() , key );
} else if(compare > 0 ){
return get(x.getRight(), key);
} else {
return x.getValue();
}
Aula 25/11/21
Lista 5 - Árvore Binária de busca
Subclasse -
Subtipos - herda interface usando implements
extends -
Aula 29/11/21
public void put
Aula 31 - 02/12/21
In order (x)
inOrder(x.getL3eft)
visit(x)
atualizar imagem
visitação em
profundidade
Visitação (breadthFirst) 08: 09
Inicializa a pilha com root. Ordem diferente vamos precisar de uma outra estrutura
de dados se o right do E não for null coloca na pilha e se o left também coloca na
pilha.
8:25 - pilha e busca de profundidade
- fila busca de
http://www2.ic.uff.br/~vanessa/material/ed/04-ArvoresBinariasBusca.pdf
Diversas aplicações precisam buscar um determinado valor em um conjunto
de dados. Árvores binárias possibilitam buscas com eficiência Exemplo: buscar
dados de uma pessoa que possui um determinado CP, são armazenados numa
árvore binária de busca e o CPF funciona como “chave”, pois é único para cada
pessoa.
Aula 32 - Delete
delete(x node, key key )
Lista 5
Parte 1
Implemente uma classe genérica Node<Key, Value> em que a classe Value possa ser
de qualquer tipo e a classe Key tem que extends Comparable<Key>. A classe Node
deve possuir os atributos (e respectivos métodos get e set) a seguir:
1. key do tipo Key;
2. value do tipo Value;
3. left do tipo Node<Key, Value>;
4. right do tipo Node<Key, Value>; e
5. size do tipo int.
Parte 2
package com.diegopinheiro.ed1_05;
public class TreeNode <Key extends Comparable <Key> ,Value> {
private Key key;
private Value value;
private int size;
http://www2.ic.uff.br/~vanessa/material/ed/04-ArvoresBinariasBusca.pdf
private TreeNode <Key, Value> left;
private TreeNode <Key, Value> right;
public int getSize() {
return size;
}public void setSize(int size) {
this.size = size;
}
public Key getKey() {
return key;
}
public void setKey(Key key) {
this.key = key;
}
public Value getValue() {
return value;
}
public void setValue(Value value) {
this.value = value;
}
public TreeNode<Key, Value> getLeft() {
return left;
}
public void setLeft(TreeNode<Key, Value> left) {
this.left = left;
}
public TreeNode<Key, Value> getRight() {
return right;
}
public void setRight(TreeNode<Key, Value> right) {
this.right = right; } }
Implemente uma classe genérica BinarySearchTree<Key, Value> em que a classe
Value possa ser de qualquer tipo e a classe Key tem que extends Comparable<Key>.
Implemente os seguintes métodos:
1. Value get(Key key), que recebe um Key e retorna um Value
encontrado;
2. void put(Key key, Value value) que adiciona um Value na Key;
3. int size() que retorna um int com a quantidade de nós;
4. Key min() que retorna a Key de menor valor;
5. Key max() que retorna a Key de maior valor;
6. void delete(Key key) que remove o nó associado com a Key;
package com.diegopinheiro.ed1_05;
public class BinarySearchTree <Key extends Comparable <Key>
,Value> {
private TreeNode <Key,Value> root;
public void delete(String string) {
}
public void put(String value, Key key ) {
}
public void put(Key key, Value value) { // Aula 29/11
// root - rotula null de comeco
this.root = this.put(this.root, key, value); // vai ser
associado a esse put
}
private TreeNode<Key,Value> put(TreeNode<Key, Value> x , Key
key, Value value){
if(x == null) {
return new TreeNode<Key,Value>(key,value,1);
}
int emp = key.compareTo(x.getKey());
if(emp < 0) {
TreeNode <Key,Value> leftNode =
this.put(x.getLeft(),key, value);
x.setLeft(leftNode);
}else if (emp > 0) {
TreeNode<Key, Value> rightsubTreenewwithPuttedNode
= this.put(x.getRight(), key, value);
x.setRight(rightsubTreenewwithPuttedNode);
}else {
x.setValue(value);
}
int newsize = this.size(x.getLeft()) +
this.size(x.getRight()) +1; // pq esse mais 1???
x.setSize(newsize);
return x;
}
private put(TreeNode, key, value) {
}
public int size() {
return this.size(this.root);
}
private int size (TreeNode <Key, Value> x) {
if(x == null) {
return 0;
}
else {
return x.getSize();
}
}
public Value get (Key key) { //
return get(this.root, key);
}
private Value get(TreeNode <Key,Value> x , Key key) {
int compare = key.compareTo(x.getKey());
return x.getValue();
}
}
Parte 3
Implemente uma classe genérica BinarySearchTree<Key, Value> em que a classe
Value possa ser de qualquer tipo e a classe Key tem que extends Comparable<Key>.
A BinarySearchTree<Key, Value> recebe uma BinarySearchTree<Key, Value> em seu
construtor. Implemente métodos que visitam a árvore e retornam uma List<Key>
contendo as chaves nas ordens visitadas a seguir:
1. List<Key> inOrder()
2. List<Key> breadthFirst()
3. List<Key> preorder()
4. List<Key> postorder()