tarefa de estrutura

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
Professor: Arlino Henrique Magalhães de Araújo 
Tutor: Carlos Xavier Polo: Esperantina 
 Aluno: Jailson Carvalho santos 
 
LISTA DE EXERCÍCIO 
1ª) testes de lista simples (Test.java) postada na turma virtual de modo que o usuário possa 
inserir quantos nomes de alunos ele quiser e o programa finalize apenas quando ele digitar a 
palavra FIM. Após finalizar, o programa deve exibir todos os nomes cadastrados. 
 
import java.util.Scanner; 
public class Q1 { 
 
public static void main (String args[]){ 
SimpleList simpleList = new 
SimpleList(); 
 
Scanner entrada = new Scanner 
(System.in); System.out.print("Nome: "); 
String pessoa = entrada.next(); 
 
while(!pessoa.equals("FIM") && 
!pessoa.equals("fim")){ 
simpleList.insertAtBack(pessoa); 
System.out.print("Nome: "); 
pessoa = entrada.next(); 
} 
simpleList.print(); 
 
simpleList.insertAtBack(1); 
simpleList.insertAtBack(2); 
simpleList.insertAtFront(3)
; 
simpleList.insertAtFront(4)
; 
 
simpleList.print(); 
simpleList.removeFromBack(); 
simpleList.print(); 
simpleList.removeFromFront()
; simpleList.print();*/ 
} 
} 
 
 
 
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
2- Modifique o programa de testes de lista simples (Test.java) de modo que seja apresentado 
um menu onde o usuário pode escolher entre: Inserir na Lista, Remover da lista, Exibir itens 
da lista ou Sair do programa. 
 
import java.util.Scanner; 
public class Q2 { 
 
public static void main (String args[]){ 
SimpleList simpleList = new SimpleList(); 
Scanner entrada = new Scanner (System.in); 
System.out.println(" MENU "); 
System.out.println("1 - INSERIR NA LISTA:"); 
System.out.println("2 - REMOVER DA LISTA:"); 
System.out.println("3 - EXIBIR ITENS DA LISTA:"); 
System.out.println("4 - SAIR DO PROGRAMA"); 
System.out.print("OPÇÃO: "); 
int menu = entrada.nextInt(); 
switch (menu){ 
case 1: System.out.print("Nome: 
"); String pessoa = 
entrada.next(); 
simpleList.insertAtBack(pessoa); 
break; 
case 2: 
simpleList.removeFromBack(); 
break; 
case 3: 
simpleList.print(); 
break; 
case 4: 
break; 
default: 
System.out.println("OPÇÃO INVALIDA"); 
} 
} 
 
3- Crie um método em SimpleList.java que faça a inserção ordenada de notas dos alunos 
na lista. 
import java.util.Scanner; 
public class Q3 { 
 
public static void main (String args[]){ 
SimpleList simpleList = new SimpleList(); 
 
Scanner entrada = new Scanner (System.in)System.out.println("Tamanho da lista: " + 
SimpleList.getSize()); 
} 
} 
 
 
 
 
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
4- Crie um método em SimpleList.java que retorne a quantidade de elementos da lista. 
 
public class questao4 { 
 
private ListNode firstNode; 
 
private ListNode lastNode; 
public questao4() { 
firstNode = lastNode = null; 
} 
 
public void insertAtFront(Object newItem) { 
if (isEmpty()) { 
firstNode = lastNode = new ListNode(newItem); 
} else { 
firstNode = new ListNode(newItem, firstNode); 
} 
} 
public void insertAtBack(Object newItem) { 
if (isEmpty()) { 
firstNode = lastNode = new ListNode(newItem);
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
} 
else { 
 
} 
} 
 
 
lastNode = lastNode.next = new ListNode(newItem) 
 
public void removeFromFront() throws EmptyListException { 
if (isEmpty()) { 
throw new EmptyListException(); 
} 
if (firstNode.equals(lastNode)) { 
firstNode = lastNode = null; 
} 
else { 
firstNode = firstNode.next; 
} 
} 
public void removeFromBack() throws EmptyListException { 
if (isEmpty()) { 
throw new EmptyListException(); 
} 
if (firstNode.equals(lastNode)) { 
firstNode = lastNode = null; 
} 
else { 
ListNode current = firstNode; 
while (current.next != lastNode) { 
current = current.next; 
} 
lastNode = current; 
current.next = null; 
} 
} 
public boolean isEmpty() { 
return firstNode == null; 
} 
public void print() { 
if (isEmpty()) { 
System.out.println("A está vazia"); 
} 
ListNode current = firstNode; 
while (current != null) { 
System.out.print(current.data.toString() + " "); 
current = current.next; 
} 
System.out.print("\n");
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
} 
public int quantidade() { 
int quant = 0; 
if (isEmpty()) { 
System.out.println("A está vazia"); 
} 
else{ 
ListNode current = firstNode; 
while (current != null) { 
quant++; 
current = current.next; 
} 
System.out.print("Quantidade: " + quant); 
} 
return quant; 
} 
} 
 
5 - Crie um método que busque um aluno em uma pilha pesquisando por sua matrícula. Se 
aluno for encontrado, deve ser retornado se objeto; caso contrário, deve ser retornado nulo. 
 
public class questão5 { 
private ListNode top; 
public Q5() { 
this.top = null; 
} 
public void push (Object newItem) { 
if (isEmpty()) { 
top = new ListNode(newItem); 
} 
else { 
top = new ListNode(newItem, top); 
} 
} 
 
public void pop() throws EmptyListException { 
if (isEmpty()) { 
throw new EmptyListException(); 
} 
else{ 
top = top.next; 
} 
} 
public boolean isEmpty() { 
return top == null; 
}
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
 
public void print() { 
if (isEmpty()) { 
System.out.println("A pilha está vazia"); 
return; 
} 
ListNode current = top; 
while (current != null) { 
System.out.print(current.data.toString() + " "); 
current = current.next; 
} 
System.out.print("\n"); 
} 
public Aluno pesquisarMatricula (int matricula){ 
if (isEmpty()) { 
System.out.println("A pilha está vazia"); 
return null; 
} 
ListNode current = top; 
while (current != null) { 
Aluno aluno = (Aluno) current.data; 
if(aluno.getMatricula() == matricula){ 
return aluno; 
} 
current = current.next; 
} 
return null; 
} 
} 
 
6 - Crie um método que busque um aluno em uma fila pesquisando por sua matrícula. Se 
aluno for encontrado, deve ser retornado se objeto; caso contrário, deve ser retornado nulo. 
public class questão6 { 
private ListNode first; 
private ListNode last; 
 
public Questão6() { 
first = last = null; 
} 
public void insert (Object newItem) { 
if (isEmpty()) { 
first = last = new ListNode(newItem); 
}
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
else { 
last = last.next = new ListNode(newItem); 
} 
} 
 
public void remove() throws EmptyListException { 
if (isEmpty()) { 
throw new EmptyListException(); 
} 
if (first.equals(last)) { 
first = last = null; 
} else { 
first = first.next; 
} 
} 
 
public boolean isEmpty() { 
return first == null; 
} 
 
public void print() { 
if (isEmpty()) { 
System.out.println("A fila está vazia"); 
return; 
} 
ListNode current = first; 
while (current != null) { 
System.out.print(current.data.toString() + " "); 
current = current.next; 
} 
System.out.print("\n"); 
} 
public Aluno pesquisarMatricula(int matricula){if (isEmpty()) { 
System.out.println("A pilha está vazia"); 
return null; 
} 
ListNode current = first; 
while (current != null) { 
Aluno aluno = (Aluno) current.data; 
if(aluno.getMatricula() == matricula){ 
return aluno; 
} 
current = current.next; 
} 
return null; 
} 
} 
 
7- Modifique os programas de teste de Pilha e Fila para seja exibido um menu onde o 
usuário poderá fazer as seguintes operações: Inserir, Remover, Listar e Sair.
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
import java.util.Scanner; 
public class questão7 { 
public static void main (String args[]){ 
Fila fila = new Fila(); 
Scanner scanner = new Scanner(System.in); 
/* 
fila.insert(1); 
fila.insert(2); 
fila.insert(3); 
fila.insert(4); 
fila.insert(5); 
fila.print(); 
fila.remove(); 
fila.print(); 
*/ 
/* 
Aluno a = new Aluno(1, "João"); 
Aluno b = new Aluno(2, "José"); 
Aluno c = new Aluno(3, "Maria"); 
fila.insert(a); 
fila.insert(b); 
fila.insert(c); 
Aluno pesquisa = fila.pesquisarMatricula(2); 
Aluno pesquisa2 = fila.pesquisarMatricula(3); 
Aluno pesquisa3 = fila.pesquisarMatricula(4); 
*/ 
System.out.println(" --------- MENU ------------"); 
System.out.println("1 - Inserir"); 
System.out.println("2 - Remover"); 
System.out.println("3 - Listar"); 
System.out.println("4 - Sair\n"); 
System.out.print("Opcao:: "); 
int op = scanner.nextInt(); 
switch (op){ 
case 1: 
System.out.print("Valor a ser inserido: "); 
fila.insert(scanner.next()); 
break; 
case 2: 
fila.remove(); 
break; 
case 3: 
fila.print(); 
break; 
case 4: 
return; 
}
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
} 
} 
 
8- Faça um método que permita busca um aluno e uma árvore pesquisando por sua 
matrícula. Se aluno for encontrado, deve ser retornado se objeto; caso contrário, deve ser 
retornado nulo. 
public class 8 { 
public static void main(String args[]){ 
/* 
BinaryTree binaryTree = new BinaryTree('F'); 
TreeNode nodeF = binaryTree.root; 
TreeNode nodeB = binaryTree.intertLeft(nodeF, 'B'); 
TreeNode nodeA = binaryTree.intertLeft(nodeB, 'A'); 
TreeNode nodeD = binaryTree.intertRight(nodeB, 'D'); 
TreeNode nodeC = binaryTree.intertLeft(nodeD, 'C'); 
TreeNode nodeE = binaryTree.intertRight(nodeD, 'E'); 
TreeNode nodeH = binaryTree.intertRight(nodeF, 'H'); 
TreeNode nodeG = binaryTree.intertLeft(nodeH, 'G'); 
TreeNode nodeI = binaryTree.intertRight(nodeH, 'I'); 
binaryTree.preOrder(); 
System.out.println(); 
binaryTree.inOrder(); 
System.out.println(); 
binaryTree.postOrder(); 
*/ 
Aluno aluno = new Aluno(1, "Amanda"); 
Aluno aluno2 = new Aluno(2, "Lara"); 
Aluno aluno3 = new Aluno(3, "Francisco"); 
BinaryTree binaryTree = new BinaryTree(aluno); 
TreeNode nodeF = binaryTree.root; 
TreeNode noA = binaryTree.intertLeft(nodeF, aluno2); 
TreeNode noB = binaryTree.intertRight(nodeF, aluno3); 
Aluno pesquisa = binaryTree.pesquisaMatricula(2, binaryTree.root); 
if(pesquisa == null){ 
System.out.println("Aluno não encontrado"); 
} 
else{ 
System.out.println("Aluno Encontrado:: " + pesquisa.getNome()); 
} 
} 
} 
 
9 - Fazer um método que retorne a quantidade de nós de uma árvore. 
public class Questão9 { 
TreeNode root; 
 
Questao9(Object newItem) { 
root = new TreeNode(newItem); 
} 
 
public TreeNode intertLeft(TreeNode node, Object newItem)throws NotNullNodeException{ 
if(node.left != null)
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
throw new NotNullNodeException(); 
else{ 
TreeNode newNode = new TreeNode(newItem); 
node.left = newNode; 
return newNode; 
} 
} 
 
public TreeNode intertRight(TreeNode node, Object newItem)throws 
NotNullNodeException{ 
if(node.right != null) 
throw new NotNullNodeException(); 
else{ 
TreeNode newNode = new TreeNode(newItem); 
node.right = newNode; 
return newNode; 
} 
} 
public void preOrder(){ 
preOrder(root); 
} 
private void preOrder(TreeNode node){ 
if(node == null) 
return; 
System.out.print(node.data.toString() + " "); 
preOrder(node.left); 
preOrder(node.right); 
} 
public Aluno pesquisaMatricula(int matricula, TreeNode arvore){ 
if(arvore == null){ 
return null; 
} 
else { 
Aluno aluno = (Aluno) arvore.data; 
if(aluno.getMatricula() == matricula){ 
return aluno; 
} 
else{ 
Aluno a = pesquisaMatricula(matricula, arvore.left); 
if(a!=null){ 
return a; 
} 
} 
return pesquisaMatricula(matricula, arvore.right); 
} 
public void inOrder(){ 
inOrder(root); 
} 
private void inOrder(TreeNode node){ 
if(node == null) 
return; 
inOrder(node.left);
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
System.out.print(node.data.toString() + " "); 
inOrder(node.right); 
} 
public void postOrder(){ 
postOrder(root); 
} 
private void postOrder(TreeNode node){ 
if(node == null) 
return; 
postOrder(node.left); 
postOrder(node.right); 
System.out.print(node.data.toString() + " "); 
} 
int quantidade(TreeNode treeNode) { 
int quant = 0; 
if(treeNode == null){ 
return quant; 
}else { 
return 1 + quantidade(treeNode.left) + quantidade(treeNode.right); 
} 
} 
} 
 
10 - Fazer um método quer retorne o nível em que um aluno se encontra da na árvore 
pesquisando por sua matrícula. Se o aluno não for encontrado, deve ser retornado -1. 
public class Questão10 { 
TreeNode root; 
Questao10(Object newItem) { 
root = new TreeNode(newItem); 
} 
public TreeNode intertLeft(TreeNode node, Object newItem)throws NotNullNodeException{ 
if(node.left != null) 
throw new NotNullNodeException(); 
else{ 
TreeNode newNode = new TreeNode(newItem); 
node.left = newNode; 
return newNode; 
} 
} 
 
public TreeNode intertRight(TreeNode node, Object newItem)throws 
NotNullNodeException{ 
if(node.right != null) 
throw new NotNullNodeException(); 
else{ 
TreeNode newNode = new TreeNode(newItem); 
node.right = newNode; 
return newNode; 
} 
} 
public void preOrder(){ 
preOrder(root);
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
} 
private void preOrder(TreeNode node){ 
if(node == null) 
return; 
System.out.print(node.data.toString() + " "); 
preOrder(node.left); 
preOrder(node.right); 
} 
public Aluno pesquisaMatricula(int matricula, TreeNode arvore){ 
if(arvore == null){ 
return null; 
} 
else { 
Aluno aluno = (Aluno) arvore.data; 
if(aluno.getMatricula() == matricula){ 
return aluno; 
} 
else{ 
Aluno a = pesquisaMatricula(matricula, arvore.left); 
if(a!=null){ 
return a; 
} 
} 
} 
return pesquisaMatricula(matricula, arvore.right); 
} 
public void inOrder(){ 
inOrder(root); 
} 
private void inOrder(TreeNode node){ 
if(node == null) 
return; inOrder(node.left); 
System.out.print(node.data.toString() + " "); 
inOrder(node.right); 
} 
public void postOrder(){ 
postOrder(root); 
} 
private void postOrder(TreeNode node){ 
if(node == null) 
return; 
postOrder(node.left); 
postOrder(node.right); 
System.out.print(node.data.toString() + " "); 
} 
int quantidade(TreeNode treeNode) { 
int quant = 0; 
if(treeNode == null){ 
return quant; 
} 
else {
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
ESTRUTURA DE DADOS 
 
return 1+ quantidade(treeNode.left) + quantidade(treeNode.right); 
} 
} 
public int nivelAluno(int matricula, TreeNode arvore, int nivel){ 
if(arvore == null){ 
return -1; 
} 
else { 
nivel = nivel+1; 
Aluno aluno = (Aluno) arvore.data; 
if(aluno.getMatricula() == matricula){ 
return nivel; 
} 
else{ 
int n = nivelAluno(matricula, arvore.left, nivel); 
if( n != -1){ 
return n; 
} 
else{ 
return nivelAluno(matricula, arvore.right, nivel); 
} 
 
} 
} 
} 
}