Instituto Politécnico de Setúbal
Escola Superior de Tecnologia de Setúbal
Departamento de Sistemas e Informática
Guia das aulas Práticas e de Laboratório
Algoritmos e Tipos Abstractos de Informação (ATAI)
Ano Lectivo 2005/2006
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Índice
Arrays......................................................................................................................... 4
Exercícios Práticos ................................................................................................. 4
Excepções.................................................................................................................. 9
Exercícios Práticos ................................................................................................. 9
Exercícios de Laboratórios.................................................................................... 11
Entrada e Saída de Dados, Ficheiros....................................................................... 14
Exercícios Práticos ............................................................................................... 14
Exercícios de Laboratórios.................................................................................... 16
Classes e Objectos .................................................................................................. 19
Exercícios Práticos ............................................................................................... 19
Exercícios de Laboratórios.................................................................................... 21
Herança, Classes abstractas e Interfaces................................................................ 23
Exercícios Práticos ............................................................................................... 23
Exercícios de Laboratórios.................................................................................... 26
Estruturas dinâmicas................................................................................................ 28
Exercícios Práticos ............................................................................................... 28
Exercícios de Laboratórios.................................................................................... 29
TAD Pilha ................................................................................................................. 30
Exercícios de Laboratórios.................................................................................... 30
TAD Fila ................................................................................................................... 31
Exercícios de Laboratórios.................................................................................... 31
TAD Lista ................................................................................................................. 32
Exercícios Práticos ............................................................................................... 32
Exercícios de Laboratório ..................................................................................... 33
© DSI 2005
2
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Árvores binárias ....................................................................................................... 34
Exercícios Práticos ............................................................................................... 34
Exercícios de Laboratório ..................................................................................... 35
Heap......................................................................................................................... 37
Exercícios Práticos ............................................................................................... 37
Exercícios de Laboratório ..................................................................................... 37
© DSI 2005
3
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Arrays
Exercícios Práticos
1 - Desenvolva um programa que gere números aleatórios, entre 1 e 1000, e
guarde-os num array. De seguida, escreva no ecrã qual foi o maior e o menor valor
gerado, e a média de todos os números gerados.
Nota: Crie um array com um máximo de 20 posições. Deve criar os seguintes
métodos
int maximo(int []tabela)
int minimo(int []tabela)
double media(int []tabela)
2 - Desenvolva um programa, que leia uma certa quantidade (fornecida pelo
utilizador) de números inteiros armazenando-os num array. Depois, ordene a
sequência de números inserirdos por ordem decrescente, e imprima-a no ecrã.
Nota: Deve criar o seguinte método:
int[] criarInts()
void imprimirInts(int []tabela)
void ordenarInts(int []tabela)
3 – Calculo de Histogramas
a) implemente um método que dado um array de inteiros o preencha com
números aleatórios correspondentes ao número de ocorrências de cada
elemento (índice).
b) implemente um método que dado um array de inteiros calcule o histograma
correspondente e o devolva sob a forma de um novo array como resultado
c) implemente um método que, dado o array com o histograma o imprima no
écran
Exemplo:
© DSI 2005
4
Guia das aulas praticas e de laboratório de ATAI
Elemento
Valor
Ano Lectivo 2005/2006
Histograma
0
19
*******************
1
3
***
2
15
***************
3
7
*******
4
9
*********
5
13
*************
Ou então
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Valor:
Elemento:
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
19
3
0
1
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
15
7
9
13
2
3
4
5
d) Implemente um programa que, recorrendo aos métodos anteriormente
implementados, mostre o histograma resultante.
4 - Problema do cálculo de frequência das ocorrências de cada face de um Dado.
Implemente um programa que faça 6000 lançamentos de um dado de 5 faces e
calcule as frequências de ocorrência do valor de cada face, mostrando o resultado
no écran com o formato do exemplo seguinte:
© DSI 2005
5
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Face Frequência
1
1007
2
1033
3
1016
4
979
5
999
6
966
5 - Pediu-se a 40 estudantes que avaliassem a qualidade da comida do refeitório.
Para esse efeito, eles tiveram de responder a um inquérito em que a cada pergunta
davam respostas numa escala de 1 (medíocre) a 5 (excelente). Faça um programa
que recolha as respostas às perguntas e as coloque num array de inteiros para
sumarizar os resultados do inquérito.
O array de resultado deverá ser uma matriz de NxM, sendo N é o número de
perguntas a realizar no inquérito e M=5. Uma coluna representa as classificações
por pergunta, e a outra representa a frequência de respostas para cada
classificação. Assim, ficamos com a seguinte estrutura:
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
Questões
No final, o que é mostrado ao utilizador deverá parecer-se com o exemplo seguinte:
© DSI 2005
1
Classificação
Frequência
1
4
2
30
3
2
4
2
6
Guia das aulas praticas e de laboratório de ATAI
2
3
Ano Lectivo 2005/2006
5
2
1
14
2
10
3
6
4
5
5
5
1
6
2
3
3
1
4
20
5
10
6 - Elabore um programa que cria um array de String’s, com dados fornecidos pelo
utilizador. Em seguida, deve ordenar o array por ordem crescente, e imprimi-lo no
ecrã.
Nota: Deve criar os seguintes métodos:
String[] ordenarStrings(String []tabela)
void imprimirStrings(String []tabela)
String[] preencherTabelaStrings(int dimensao)
7a) Crie a classe Programa, que está caracterizada por título, resumo, hora de
inicio e duração.
b) Crie a classe Programacao, que está caracterizada por o nome do canal e
por um conjunto de programas. Deve ser possível inserir e remover
programas.
c) Crie um método na classe Programacao, que liste todos os programas, por
ordem crescente da hora de inicio, no ecrã. Note que será necessário criar
um outro método que ordena o conjunto de programas por ordem crescente.
© DSI 2005
7
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
d) Crie uma aplicação que teste as classes anteriores. Para isso, crie um menu
que tem as seguinte funcionalidades:
1. Inserir programa
2. Listar programação
3. Ver informação sobre programa
4. Apagar programa por título
5. Sair
Nota: será necessário criar um método que preenche um programa, fornecido
pelo utilizador.
© DSI 2005
8
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Excepções
Exercícios Práticos
1 - Desenvolva um método que retorna o índice de um elemento, num array de
String’s. O método a desenvolver deve ter a seguinte assinatura:
int indiceStrings(String []tabela, String valor)
Caso o valor não esteja incluído no array, deve devolver -1.
Crie uma aplicação que testa o método anterior. Utilize o seguinte troço de
código:
String []tabela = {“Susana”, “Ricardo”, “Luís”,
“Rossana”, “Maria”, “Cátia”, “Rui”, “Ana”, “Paulo”};
int indice = 0;
“Carlos”,
indice = indiceStrings(tabela, “Cátia”);
System.out.println(tabela[indice]);
indice = indiceStrings(tabela, “José”);
System.out.println(tabela[indice]);
a) Que tipo de erros podem ocorrer?
b) Resolva o problema, utilizando excepções.
2 - Apresenta-se o código fonte do programa Propagation e da implementação da
classe ExceptionScope.
public class Propagation
{
static public void main (String[] args)
{
ExceptionScope demo = new ExceptionScope();
System.out.println("Program beginning.");
demo.level1();
System.out.println("Program ending.");
}
}
public class ExceptionScope
{
public void level1()
{
System.out.println("Level 1 beginning.");
© DSI 2005
9
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
try
{
level2();
}
catch (ArithmeticException problem)
{
System.out.println ();
System.out.println ("The exception message is: " +
problem.getMessage());
System.out.println ();
System.out.println ("The call stack trace:");
problem.printStackTrace();
System.out.println ();
}
System.out.println("Level 1 ending.");
}
public void level2()
{
System.out.println("Level 2 beginning.");
level3 ();
System.out.println("Level 2 ending.");
}
public void level3 ()
{
int numerator = 10, denominator = 0;
System.out.println("Level 3 beginning.");
int result = numerator / denominator;
System.out.println("Level 3 ending.");
}
}
a) Qual o resultado da execução do programa ? Explique a sua resposta.
b) Se no programa do exercício anterior no método level3 substituirmos a linha
2 por:
int numerator = 10, denominator = 2;
qual o resultado da execução do programa ?
3 - Implemente um método que imprima os elementos de uma matriz de inteiros,
recorrendo
ao
uso
do
tratamento
da
excepção
ArrayIndexOutOfBoundsException, em vez de uso do tamanho da matriz para
critério de paragem do ciclo.
© DSI 2005
10
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
public static imprimeMatriz(int m[][])
{//imprime os valores da matriz m
4-
a) Implemente uma classe Ponto, que tem os seguintes atributos: x, y e z.
b) Desenvolva um método que copia todos os elementos de uma tabela para
outra tabela. O método deve ter a seguinte assinatura:
void copiarTabelas(Ponto tab_1[][], Ponto tab_2[][])
c) Crie uma aplicação que testa as alíneas a) e b). Utilize o seguinte troço de
código:
Ponto tab_1[][] = new Ponto[3][3];
for (int i = 0; i <= 3; i++)
for (int j = 0; j <= 3; j++)
tab_1[i][j] = preencherPonto();
Ponto tab_2[][] = new Ponto[3][4];
copiarTabelas (tab_1, tab_2);
mostrarTabela(tab_2);
Note que irá necessitar dos métodos: preencherPonto e mostrarTabela.
Exercícios de Laboratórios
1 - Experimente o seguinte código:
int tabela[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println();
for (int i = 0; i <=10; i++)
{
System.out.print(tabela[i] + “; ”);
}
System.out.println();
a) Que tipo de erro ocorreu?
b) Resolva o problema, utilizando excepções.
© DSI 2005
11
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
2 - Vejamos o seguinte método:
int numeroRepeticoes(int []tabela, int num)
{
int rep = 0;
for (int i = 0; i <= tabela.length; i++)
{
if (tabela[i] == num)
rep++;
}
return rep;
}
a) Crie uma aplicação que testa este método.
b) Que tipo de erro ocorreu?
c) Resolva o problema, utilizando excepções, no método numeroRepeticoes.
A partir da resolução da alínea a), resolva o problema, utilizando excepções,
no método main.
3 - Implemente um método que converta string para inteiros e caso a string tenha
caracteres diferentes de dígitos de 0 a 9 dê erro, usando excepções.
4 - Implemente um programa que leia dois inteiros e imprima o resultado da divisão
a) A implementação não deverá recorrer ao uso de tratamento de excepções
b) A implementação deverá tratar a excepção da divisão por zero
5– Resolva as seguintes alíneas:
a) Crie um método que receba duas matrizes, como argumento, e devolva a
soma dessas mesmas matrizes.
int[][] somaMatrizes(double mat_1[][], double mat_2[][])
b) Crie um método que receba duas matrizes, como argumento, e devolva a
multiplicação dessas mesmas matrizes
int[][] mulMatrizes(double mat_1[][], double mat_2[][])
© DSI 2005
12
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
c) Crie um método que devolve uma matriz. A matriz pode ser preenchida com
valores fornecidos pelo utilizador ou por números aleatórios.
int[][] criarMatriz() ou int[][]preencherMatriz()
d) Crie uma aplicação que testa a funções desenvolvidas nas alíneas anteriores.
6 - Modifique o exercício 5 para incluir a criação e tratamento de excepções.
a) No método para somar matrizes deverá testar se as duas matrizes têm
dimensões iguais, caso não tenham deverá lançar uma Exception com a
mensagem (“Dimensões inválidas”)
b) No método para multiplicar matrizes deverá testar se o número de colunas
da 1ª matriz é igual ao número de linhas da 2ªa matriz caso não seja
deverá lançar uma Exception com a mensagem (“Dimensões inválidas”)
c) No método main deverá tratar essas duas excepções aquando a
invocação dos métodos.
© DSI 2005
13
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Entrada e Saída de Dados, Ficheiros
Exercícios Práticos
1 - Escreva um método que leia do teclado o nome de um ficheiro e verifique se este
ficheiro existe e se é um ficheiro válido para escrita.
2 - Implemente um método que crie um ficheiro com 100 linhas cada uma com o
numero respectivo da linha.
public static void escreve100Linhas(String nFile)
{
// cria ou abre um ficheiro com o nome nFile e escreve
// os números de 1-100
// sequencialmente (um numero por linha de ficheiro)
}
a) Compilar sem try-catch para tratamento de excepções.
b) Usar try-catch e finally (se necessário) para tratar e apanhar as excepções
ignoradas na linha anterior.
3 - Desenhe e implemente um programa que compare dois ficheiros, linha por linha
e imprima as linhas que não sejam iguais.
4 - Implemente uma classe denominada FicheiroTexto que contenha como atributos
um BufferedReader e um BufferedWriter e contenha métodos para:
- Abrir o ficheiro para leitura (se este existir no path indicado, caso contrário
lança uma excepção).
- Abrir o ficheiro para escrita (lançando uma excepção se o ficheiro já existir,
e o modo de abertura não tiver sido overwrite nem append).
- Ler uma linha do ficheiro.
- Ler um número inteiro do ficheiro.
- Ler um número real do ficheiro.
- Escrever uma linha no ficheiro.
- Escrever um número inteiro no ficheiro.
© DSI 2005
14
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
- Escrever um número real no ficheiro.
- Fechar o ficheiro se tiver sido aberto em modo de leitura.
- Fechar o ficheiro se tiver sido aberto em modo de escrita.
Nota: Nenhum dos métodos desta classe apanha excepções. Os clientes que
invocam os métodos é que deverão tratar de apanhar e lidar com as excepções que
aqui forem lançadas.
5 - Implemente um programa que lê um conjunto de inteiros de um ficheiro e os
imprima no terminal. Utiliza a classe Scanner.
6 - Desenhe e implemente um programa que conte o número de cada um dos sinais
de pontuação dum ficheiro de texto e elabore um ficheiro de texto com o relatório de
quantos sinais de cada tipo foram encontrados.
Nota: O conjunto de sinais de pontuação a considerar são ( , ; . ! ?:). Caso não
encontre o ficheiro deverá dar uma excepção. Caso não consiga criar o ficheiro
deverá dar uma excepção. Deve verificar se o ficheiro de entrada existe, caso
contrário deve ocorrer uma excepção.
7 - Implemente um método que, dado um ficheiro de texto faça um relatório do
número de vogais e consoantes contidas no mesmo.
Nota: Não esqueça o devido tratamento de excepções!
8 - Implemente um programa, que recebe como entrada um ficheiro de texto com
informação sobre livros e produz como saída a listagem das editoras destes livros
(na listagem cada editora deve aparecer uma única vez).
Considere que no ficheiro de texto cada linha descreve um livro da seguinte
maneira:
titulo, autor, editora
9 – Implemente um programa, que recebe como entrada um ficheiro de texto com
informação sobre os carros e informa a utilizador sobre quantidade de carros que se
encontra registado no ficheiro. No ficheiro cada linha corresponde a um carro.
NOTA: use BufferedReader e FileReader classes
© DSI 2005
15
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
10 – Implemente um programa, que lê um ficheiro de texto “notas.txt” com notas de
alunos a disciplinas e produz um ficheiro de texto “alunos.txt” com a media de cada
aluno.
Cada linha do ficheiro de entrada tem 3 campos separados por ponto e virgula:
nome do aluno, nome da disciplina e nota (inteiro).
O ficheiro a produzir deve ter uma linha por cada aluno com o nome do aluno e
anota média(do tipo real), separados por ponto e virgula.
Exercícios de Laboratórios
1 - Desenvolva um método que leia um inteiro do teclado. Resolva os erros de
excepções dentro do método.
a) Crie uma aplicação que testa o método anterior.
b) Experimente introduzir uma string em vez de um número inteiro. O que
aconteceu?
c) Tente resolver o problema utilizando excepções. Resolva o problema fora do
método.
2 - Implemente um método que leia um ficheiro e imprima o seu conteúdo no ecran,
caso não encontre o ficheiro deverá dar uma excepção. (Use os método exits() para
testar a existência do ficheiro)
public static void leFicheiro(String xpto)
{
// lê o conteúdo do ficheiro xpto e mostra o seu
conteúdo no ecran.
}
a) Compilar sem try-catch para tratamento de excepções
b) Usar try-catch e finally (se necessário) para tratar e apanhar as excepções
ignoradas na linha anterior
3 - Implemente um programa que leia uma String do teclado e a escreva para um
ficheiro de texto.
a) Compilar o programa sem try-catch-finally para tratamento de excepções e
verifique o ocorrido. Explique porquê.
b) Faça para a alínea anterior o devido tratamento de excepções.
© DSI 2005
16
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
c) Agora, peça ao utilizador para escrever uma frase (no mínimo com 10
palavras), e escreva a frase para um ficheiro de texto em que deve aparecer
uma palavra por linha. Se o ficheiro já existir, deve concatenar-lhe o novo
conteúdo.
Nota: Não se esqueça do devido tratamento de excepções! Use a classe
StringTokenizer para quebrar a frase nas diferentes palavras que a constituem.
4 - Implemente um método que receba dois ficheiros e crie um 3º ficheiro que é o
resultado da concatenação destes.
static public void concatenaFicheiros(String file1, String
file2, String file3){
//O ficheiro com nome file 3 é o resultado da concatenação
dos ficheiros com o nome file1 e file2
}
Nota: Deve verificar se os ficheiros de entrada existem, caso contrário deve ocorrer
uma excepção (que indique qual deles está em falta). Caso não consiga criar o
ficheiro de saída deve ocorrer uma excepção.
5 - Implemente uma classe denominada FicheiroObjectos que contenha como
atributos um ObjectInputStream e um ObjectOutputStream e contenha métodos
para:
- Abrir o ficheiro para leitura (se este existir no path indicado, caso contrário
lança uma excepção).
- Abrir o ficheiro para escrita (lançando uma excepção se o ficheiro já existir,
e o modo de abertura não tiver sido overwrite nem append).
- Ler um objecto.
- Escrever um objecto.
- Fechar o ficheiro se tiver sido aberto em modo de leitura.
- Fechar o ficheiro se tiver sido aberto em modo de escrita.
Nota: Daqui por diante deverá utilizar estas classes sempre que pretender
implementar programas que lidem com ficheiros de texto e/ou de objectos.
6 - Implemente uma classe chamada RegistoConta, que contenha atributos para
representar o número de conta, primeiro nome do titular, apelido do titular e o saldo.
© DSI 2005
17
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Desenvolva um programa que:
a) Permita gravar registos de contas bancárias num ficheiro de objectos.
b) Leia os registos de conta sequencialmente e os mostre no écran.
c) Concatene dois ficheiros de registos de contas mas sem repetições (isto é,
objectos com o mesmo conteúdo não devem aparecer mais do que uma vez
no ficheiro de resultado)
c) Nota: Não se esqueça do devido tratamento de excepções. A classe
RegistoConta deve implementar a interface Serializable para que objectos
deste tipo possam ser armazenados convenientemente no ficheiro de output.
isão por zero.
© DSI 2005
18
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Classes e Objectos
Exercícios Práticos
1 - Programa para registo e consulta de veículos automóveis para stand de usados.
a) Defina uma classe Automovel, que tem a seguinte informação: Marca, Ano,
Nº Série motor, Cor e Preço.
b) Defina um método construtor para a classe Automóvel que inicializa os
valores dos atributos através da passagem de argumentos definidos na
alínea a).
c) Defina os seguintes métodos para a classe Automovel:
•
getMarca – retorna o valor do atributo marca.
•
getAno – retorna o valor do atributo ano.
•
getSerie – retorna o valor do atributo Série.
•
getCor – retorna o valor do atributo Cor.
•
getPreco – retorna o valor do atributo Preço.
•
setPreco – modifica o valor do atributo Preço.
•
toString – retorna o automóvel em formato String.
d) Implemente a classe Stand, que guarda toda a informação referente aos
automóveis. Ou seja, esta classe não é nada mais do que uma base de
dados do stand que, através da criação de um array de objectos do tipo
Automóvel, guarda toda a informação referente aos automóveis que estão
para venda. Note que, uma base de dados também deve guardar o seu nome
e morada.
e) Defina os seguintes métodos para a classe Stand:
•
inserirAutomovel – Permite inserir um automóvel no Stand.
•
retirarAutomovel – Permite retirar um automóvel do Stand.
•
listarMarca – lista os automóveis de uma determinada marca.
•
listarAno – lista os automóveis de um determinado ano.
•
listaAutomovel – lista todas as características de um automóvel pelo seu
nº de série.
© DSI 2005
19
Guia das aulas praticas e de laboratório de ATAI
•
Ano Lectivo 2005/2006
contarMarcaAno – determina quantos automóveis existem de uma
determinada marca do ano X.
f) Defina uma classe principal que testa as classes implementadas
anteriormente. Para testar crie um menu que tem as seguintes
funcionalidades:
1) Criar base de dados
2) Introduzir automóvel
3) Remover automóvel por Número de série
4) Listar automóvel
5) Listar por Marca
6) Listar por Ano
7) Contar todos os carros por Marca e por Ano
8) Saír
2 - Implemente uma classe Ponto, que tem os seguintes atributos: x, y e z.
d) Desenvolva um método que copia todos os elementos de uma tabela para
outra tabela. O método deve ter a seguinte assinatura:
void copiarTabelas(Ponto tab_1[][], Ponto tab_2[][])
e) Crie uma aplicação que testa as alíneas a) e b). Utilize o seguinte troço de
código:
Ponto tab_1[][] = new Ponto[3][3];
for (int i = 0; i <= 3; i++)
for (int j = 0; j <= 3; j++)
tab_1[i][j] = preencherPonto();
Ponto tab_2[][] = new Ponto[3][4];
copiarTabelas (tab_1, tab_2);
mostrarTabela(tab_2);
Note que irá necessitar dos métodos: preencherPonto e mostrarTabela.
© DSI 2005
20
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Exercícios de Laboratórios
1 - Implemente um programa para registo e consulta de informação sobre os artistas
de uma companhia de circo.
a) Defina uma classe Artista que tem a seguinte informação:
•
Nome
•
n_Bi – nº do BI
•
nº cédula profissional – nº cédula profissional
•
arte – arte que desempenha (palahço, malabarista,trapezista,
ajudante, domador etc…)
•
ordenado – ordenado base
b) Defina um método constructor para a classe Artista que inicialize os valores
dos atributos através da passagem de argumentos definidos na alínea a).
c) Defina os seguintes métodos:
•
getNome – retorna o valor do atributo nome.
•
getcedula – retorna o valor do atributo Cédula
•
getArte – retorna o valor do atributo arte.
•
getOrdenado – retorna o valor do atributo ordenado.
•
setOrdenado – modifica o valor do atributo ordenado.
•
setArte – modifica o valor do atributo arte.
•
toString – retorna o empregado em formato String.
d) Implemente a classe Circo, que guarda toda a informação referente aos seus
artistas. Ou seja, esta classe não é nada mais do que uma base de dados da
empresa que, através da criação de um array de objectos do tipo Artista,
guarda toda a informação referente aos seus artistas. Note que, uma base de
dados também deve guardar o seu nome.
e) Defina os seguintes métodos para a classe Circo:
© DSI 2005
•
listarArtista – lista os atributos de um artista pelo seu nº de artista.
•
calcularOrdenado – para um determinado artista calcula o seu
ordenado líquido, supondo que desconta 11% para a Segurança
Social, 15% para o IRS e 20 EUR para a quota associativa do Circo.
21
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
•
calcularTotalOrdenado – determina qual o montante total que a
empresa despende com ordenados por mês.
•
listarArte – lista os nomes e números de todos os empregados que
trabalham uma determinada arte (todos os palhaços, ou todos os
malabaristas)
f) Defina uma classe principal que testa as classes implementadas
anteriormente. Para testar crie um menu que tem as seguintes
funcionalidades:
© DSI 2005
•
Criar base de dados
•
Introduzir Artista
•
Remover artista por Número de Artista
•
Listar Artista
•
Calcular ordenado
•
Calcular o valor total de ordenados
•
Saír
22
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Herança, Classes abstractas e Interfaces
Exercícios Práticos
1 - Implemente classes a seguir especificadas:
Publicação (classe abstracta):
•
atributos: nome
•
Métodos:
¾ void mostra() // mostra a publicação
¾ void introduzdados() // método abstracto
Livro
•
Classe que deriva de Publicação
•
atributos: nome e autor
•
Métodos:
¾ void mostra() // mostra o nome e o autor do livro
¾ void introduzDados() // lê o nome e autor do livro
Revista
•
Classe que deriva de Publicação
•
atributos: nome e numero
•
Métodos:
¾ void mostra() // mostra o nome e o numero da revista
¾ void introduzDados() // lê o nome e o numero da revista
a) No programa principal devera apresentar um menu com a opção de introduzir os
2 tipos de publicação, e consoante o tipo escolhido, pedir ao utilizador a
introdução dos dados respectivos e mostrar em seguida o conteúdo do objecto
criado.
Modificar o programa principal de modo a poder ter-se uma base de dados de
publicações, implementada sob a forma de um array de objectos de Publicações.
Implementar metodos para introduzir publicações e para listar todas as publicações
introduzidas.
© DSI 2005
23
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
2 - Cria uma interface com o nome Prova com as seguintes declarações:
int getPontuacao();
void setDataEvento(int ano, int mes, int dia);
int getDiaEvento();
int getMesEvento();
int getAnoEvento();
int getNumElementos();
void setPontuacao(int p);
a) Cria a Classe Futebol que implemente a interface Prova com os seguintes
métodos e atributos.
Futebol(String nom, int n) // Construtor
int dia,mes,ano, nElem;// data do jogo, nº elementos da equipa
char resultado; // resultado “g-ganhou, e-empatou, p-perdeu
String nome; / /Nome da equipa
Int Pontuacao
b) Implemente na classe Programa1, as seguintes funcionalidades:
•
Criação de um array de provas de futebol
•
Preenchimento da informação relativa as provas.
•
Listagem do nº da equipa e da pontuação (o numero da equipa,
corresponde ao índice do array mais uma unidade).
3 - Existe no Java a interface Comparable, que é definida do seguinte modo:
public interface Comparable
{
public int compareTo(Object o);
}
Esta interface impõe a todas as classes que a implementam, a definição de um
método que indica se uma instancia da classe é maior, menor ou igual do que outra.
© DSI 2005
24
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
a) Implemente um programa que ordene uma sequência de objectos da classe
Integer. Deverá implementar o método ordena, que recebe um array de
elementos do tipo Comparable, e a ordena, evocando o método
compareTo.
b) Defina a classe Ponto que implementa a interface Comparable.
public class Ponto implements Comparable
{
int x, y; // coordenadas
public Ponto(int x, int y)
// construtor que inicializa x e y;
public int compareTo(Object o)
/* retorna 1 se a distancia à origem do ponto receptor for maior que a
distancia do parâmetro à origem e retorna 0 se a distancia for igual.*/
}
c) Modifique o programa desenvolvido na alínea a) , de modo a este ordenar um
array de pontos. No entanto o método ordenar, não poderá ser modificado.
d) Defina a Classe Cor que implementa a interface Comparable.
public class Cor extends Object implements Comparable{
String n_cor;// nome da cor
final String[]arco_iris={ "vermelho", "laranja", "amarelo",
"verde", "azul",“roxo","violeta"};
public Cor() // construtor
public int compareTo(Object o)
/* retorna 1 se a distancia à origem do ponto receptor for maior que a
distancia do parâmetro à origem e retorna 0 se a distancia for igual.*/
}
Nota: A ordem relativa das cores corresponde à ordem do arco_íris. Ex:
Amarelo < Verde
e) Modifique o programa desenvolvido na alínea c), de modo a este ordenar
também um array de cores. No entanto o método ordenar, não poderá ser
modificado.
© DSI 2005
25
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Exercícios de Laboratórios
1 - Implemente as classes abaixo especificadas
Data - Classe abstracta
•
atributos, ano, dia, mes.
•
Métodos:
¾ boolean bissexto() //verifica se a data pertence a uma ano bissexto
¾ boolean valida() // valida se a data é correcta
¾ void mostra() // método abstracto
¾ void leData() // método abstracto
DataEuropeia - Classe que deriva de Data
•
Métodos:
¾ void mostra() // mostra a data no formato ano/mes/dia
¾ void leData() // lê os dados na seguinte forma ano/mes/dia
DataAmericana - Classe que deriva de Data
•
Métodos:
¾ void mostra() // mostra a data no formato mes/ano/dia
¾ void leData() // lê os dados na seguinte forma mes/ano/dia
DataPortuguesa - Classe que deriva de Data
•
Métodos:
¾ void mostra() // mostra a data no formato dia/mes/ano
¾ void leData() // lê os dados na seguinte forma dia/mes/ano
a) No programa principal devera apresentar um menu com a opção de utilizar os
3 formatos de data, e consoante o formato escolhido, pedir ao utilizador a
introdução de uma data, valida-la e caso esta esteja correcta mostrar a data
escolhida.
© DSI 2005
26
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
2a) Defina uma classe DATA que tem como atributos: o dia, o mês e o ano.
b) Defina uma classe EMPREGADO cujos atributos são o nome e a data de
contratação
c) Fazendo reutilização do código dado defina uma classe
EMPREGADOESPECIALIZADO que acrescenta o atributo especialidade
d) Inclua um método construtor sem argumentos e outro com argumentos que
permita fornecer valores para todos os atributos em todas as classes.
e) Inclua um método “mostrar” para todas as classes que permita visualizar os
atributos. O método mostrar definido para a classe
EMPREGADOESPECIALIZADO inclui a visualização não só do seu atributo
especialidade como também do nome e da data de contratação.
Construa uma classe TESTE para verificar todas as funcionalidades descritas
anteriormente.
3 - Cria a Classe Rali que implementa a interface Prova definida no exercício 2 das
práticas e que tem os seguintes atributos e construtor:
int dia,mes,ano, nElem,tempo; // data do rali, nº elementos da equipa,
tempo conseguido na prova
String marca,piloto,copiloto // marca do automóvel , nome do piloto e do
copiloto
Rali(String m,String pp, String cp)// inicializa marca,piloto e co-piloto
Altere a classe Programa1 para registo de corridas de rali.
4a) Defina uma classe EMPREGADO que tem como atributos o nome e o
apelido.
b) Defina uma classe DIRECTOR (tipo de empregado) que tem como atributos o
seu vencimento.
c) Defina outra classe EMPREGADOCOMISSAO (outro tipo de empregado) que
tem como atributos o seu vencimento base, as unidades extra e o numero de
unidades
d) Defina a classe EMPREGADOHORA ( pago por numero de horas) cujos
atributos são: o numero de horas e valor pago por hora.
e) Inclua um método “Salário” abstracto, na classe base. Este método será
definido nas classes derivadas de acordo com o tipo de empregado.
f) Inclua o método “Mostrar” para todas as classes e que permita visualizar os
respectivos atributos.
g) Construa uma classe TESTE para verificar todas as funcionalidades descritas
anteriormente. Nesta classe deve declarar uma referência para
EMPREGADO e utiliza-la para testar o método abstracto que implementou
nas classes derivadas .
© DSI 2005
27
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Estruturas dinâmicas
Implementação de Estruturas dinâmicas versus estruturas
estáticas.
Objectivos Operacionais:
No fim desta ficha de exercícios o aluno deve ser capaz de:
•
Destinguir uma estrutura dinâmica de uma estrutura estática.
•
Implementar estruturas dinamicas com nos simples.
•
Implementar estruturas dinamicas com nos duplos.
•
Implementar estruturas dinamicas em anel com nos simples.
•
Enumerar as vantagens
implementações realizadas.
e
desvantagens
de
cada
uma
das
Exercícios Práticos
1 - Pretende-se realizar um programa que permita construir um percurso entre
várias cidades. O programa deverá conter as seguintes funcionalidades:
•
Introduzir uma cidade no fim do percurso.
•
Introduzir uma cidade no inicio do percurso.
•
Introduzir uma cidade apos uma determinada cidade.
•
Saber quantas cidades contem o percurso.
•
Retirar uma cidade no percurso.
•
Mostrar Percurso.
a) Crie a classe Percurso que guarda informação sobre o percurso numa
estrutura estática - array de String e que implementa os métodos
necessários para executar as funcionalidades acima descritas.
b) Implemente a Classe Programa com um menu que implemente as
funcionalidades requeridas.
© DSI 2005
28
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
2 - Modifique a classe Percurso definida no exercício anterior de modo a esta
guardar os dados não sob a forma de um array, mas sobre uma estrutura dinâmica
simplesmente ligada.
Testar a classe Programa com a nova classe Percurso.
Nota: deverá para tal definir uma classe NoSimples.
3 - Modifique a classe Percurso definida no exercício 1 de modo a esta guardar os
dados não sob a forma de um array, mas sobre uma estrutura dinâmica do tipo
anel.
Testar a classe Programa com a nova classe Percurso.
Exercícios de Laboratórios
1 - Modifique a classe Percurso definida no exercício 1 dos exercícios práticos de
modo a esta guardar os dados não sob a forma de um array, mas sobre uma
estrutura dinâmica duplamente ligada.
Testar a classe Programa com a nova classe Percurso.
Nota: deverá para tal definir uma classe NoDuplo.
© DSI 2005
29
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
TAD Pilha
Programas que usam o TAD Pilha .
Implementação do TAD Pilha.
Exercícios de Laboratórios
1 - Desenvolva um programa para simular uma calculadora que funciona segunda a
notação polaca invertida:
Exemplo 1: 5 3 1 + * = 5 * ( 3 + 1 )
Exemplo 2: 1 3 + 3 1 - * = ( 1 + 3 ) * ( 3 - 1 )
Exemplo 3: 5 4 3 2 1 * - / + = 5 + (4 / (3 – ( 2 * 1 ) ) )
Exemplo 4: 6 5 / 4 3 2 * - + = ( 6 / 5 ) + ( 4 - ( 3 * 2 ) )
•
O programa deve executar as quatro operações aritméticas.
•
Os operandos são números inteiros e o resultado produzido deve ser um
número inteiro.
•
O cálculo da expressão aritmética inicia-se após a introdução de toda a
expressão.
•
Os membros da expressão (operadores e operandos) são separados por
espaços.
•
Se na expressão existirem tentativas de divisão por zero deve ser impressa
uma mensagem de erro.
Nota: o programa deve utilizar a classe java.util.Stack.
2 - Defina a interface em Java que define o TAD Pilha
a) Faça a implementação da interface TADPilha, definida na alínea anterior,
numa classe PilhaEstatica. Note que, a classe PilhaEstatica deve
implementar uma TAD Pilha através de uma estrutura estática (array)
b) Modifique o programa do exercício 3, de forma a que este use a classe
PilhaEstatica em vez da classe java.util.Stack.
© DSI 2005
30
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
TAD Fila
Exercícios de Laboratórios
1 - Desenvolva um programa que permita gerir uma pista para descolagem de
aviões dum aeroporto. Para o correcto funcionamento desta pista é necessário que
sejam implementadas as seguintes funcionabilidades:
•
Nº de aviões à espera de descolar.
•
Descolagem de um avião.
•
Entrada de um novo avião para descolar.
•
Listar todos os aviões à espera de descolar.
•
Listar as características do próximo avião a descolar.
Utilize a classe FilaVector desenvolvida no exercício 2 e a seguinte implementação
da classe Avião:
public class Aviao extends Object
{
private String nome;
private int numero;
public Aviao(String nome, int numero)
{
this.nome=nome;
this.numero=numero;
}
public String toString()
{
String str = new String(" Nome: " + nome + " Numero " +
numero);
return str;
}
}
© DSI 2005
31
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
TAD Lista
Programas que usam o TAD Lista.
Implementação do TAD Lista
Exercícios Práticos
1 - Defina as classes BoundaryViolationException, EmptyContainerException e
InvalidPositionException que são subclasses de Exception.
a) Defina o interface CurrentPosition que deve conter o método element() que
devolve o elemento existente numa determinada posição.
b) Defina um interface para o tipo abstracto List, contendo os seguintes
métodos:
size
//Retorna o tamanho da lista
isEmpty //Verifica se a lista está vazia
isFirst
//Verifica se um elemento é o primeiro da lista
isLast
//Verifica se um elemento é o último da lista
first
last
//Retorna o primeiro elemento da lista
//Retorna o último elemento da lista
before
after
//Retorna o elemento antes da posição x
//Retorna o elemento que se encontra depois da posição x
insertBefore //Insere o elemento na lista antes a posição x e
retorna a posição do elemento inserido
insertAfter //Insere o elemento na lista após a posição x e retorna
a posição do elemento inserido
insertFirst //Insere o elemento no início da lista e retorna
posição do elemento inserido
insertLast //Insere o elemento no fim da lista e retorna
do elemento inserido
remove
replace
a
a posição
//retira um elemento da lista e retorna-o
//substitui o conteúdo de um elemento e retorna este
swap //Troca dois elementos de uma lista
listAll //Lista todos os elementos da lista
© DSI 2005
32
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
c) Defina a classe LinkedList que implementa a interface List.
Exercícios de Laboratório
1 - Implemente um programa para controlo dos artigos existentes num
supermercado usando a classe LinkedList definida no exercício anterior.
a) Crie uma biblioteca com o package definido nos exercícios anteriores
chamada List.
b) Deve implementar a classe Artigo, que contem o nome, o código e o preço do
artigo.
c) Crie a classe Supermercado que contem o nome do Supermercado e uma
lista de artigos que o supermercado comercializa.
d) Implemente na classe Supermercado os seguintes métodos.
•
adicionaArtigo – adiciona um novo artigo;
•
removeArtigo – remove artigo;
•
alteraPreco- altera preço de um artigo com um determinado código;
•
listarArtigos – listas os artigos ordenados pelo nome.
e) Implemente o programa principal para interagir com o utilizador e
disponibilizar um menu com as seguintes opções:
1) Adicionar um artigo à lista do supermercado.
2) Remover um determinado artigo pelo código.
3) Alterar o preço de um artigo, pelo seu código.
4) Listar Artigos ordenados pelo nome.
© DSI 2005
33
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Árvores binárias
Exercícios Práticos
1 - Utilizando os deslocamentos Pós-ordem, Pré-ordem e In-Ordem indique a
sequência dos nós nas seguintes árvores binárias:
a)
b)
2 - Crie uma interface com o nome BinaryTree com as seguintes declarações:
public void insert(Comparable x );//Insere o Elemento x
public void remove(Comparable x );//Remove o Elemento x
public Comparable findMin( );//Retorna o menor elemento
public Comparable findMax( );//Retorna o maior elemento
public Comparable find(Comparable x);//Retorna o Elemento x
public boolean isEmpty( );//Retorna TRUE se está vazia
public void printTreeIn();//Imprime os Elementos em INORDER
public void printTreePre();//Elementos em PREORDER
© DSI 2005
34
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
public void printTreePos();//Elementos em POSORDER
a) Crie a Class BinaryNode que é responsável pela criação do nó com as
respectivas sub-árvores esquerda e direita e com os seguintes métodos e
atributos.
// Constructores
BinaryNode(Comparable theElement)
BinaryNode(Comparable theElement,
BinaryNode lt,
BinaryNode rt )
Comparable element;
BinaryNode left;
BinaryNode right;
// Elemento do Nó
// Sub-Árvore Esquerdo
// Sub-Árvore Direito
b) Crie a Class BinarySearchTree que implemente a interface BinaryTree e os
seguintes métodos:
public BinarySearchTree( ) //Constructor
void insert(Comparable x ) //Insere o Elemento x
Comparable findMin( )
boolean isEmpty( )
//Retorna o menor elemento
//Retorna TRUE se está vazia
private void printTreeIn() //Imprime os Elementos em INORDER
private void printTreePre()//Elementos em PREORDER
Exercícios de Laboratório
1 - Complete e teste as classes construídas no exercício 2.
a) Implemente na classe os seguintes métodos Class BinarySearchTree:
void remove(Comparable x ) //Remove o Elemento x
Comparable findMax( )
void makeEmpty( )
boolean isEmpty( )
© DSI 2005
//Retorna o maior elemento
//Remove todos Elementos
//Retorna TRUE se está vazia
35
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
private void printTreePos() //Elementos em POSORDER
b) Implemente na Classe Principal, as seguintes funcionalidades:
© DSI 2005
•
Inserir um elemento
•
Imprimir todos os elementos da árvore segundo INORDER
•
Imprimir todos os elementos da árvore segundo PREORDER
•
Imprimir todos os elementos da árvore segundo POSORDER
•
Imprimir o menor elemento da árvore
•
Imprimir o maior elemento da árvore
36
Guia das aulas praticas e de laboratório de ATAI
Ano Lectivo 2005/2006
Heap
Exercícios Práticos
1 - Insira os seguintes elementos numa heap {22,15,36,44,10,3,9,13,29,25}. Mostre
como estes elementos são inseridos numa árvore binária e a respectiva
representação vectorial.
2 - Crie uma classe IntegerArray que contêm um array de nós do tipo Integer que
podem ser comparados e trocados. A classe deve ser abstracta e conter os
seguintes métodos:
•
addNode - Adiciona um nó
•
getNodeAt - Retorna o nó de uma dada posição
•
compareTo - Compara dois nós guardados no array
•
swap - Troca dois nós guardados no array
•
toString - Imprime todos os nós no array
b) Crie uma interface com o nome IntHeapArray com as seguintes declarações:
public void addNode(Integer x ); //Insere o Elemento x
public void heapSort();
//Realiza a ordenação da heap
Exercícios de Laboratório
1–
a) Crie uma classe HeapArray que extende a classe IntegerArray.java e implementa
a interface IntHeapArray.
b) Crie a classe principal HeapArrayTester que adiciona os elementos {3, 2, 1, 5 , 4 ,
6, 8, 7 , 8} e efectua o heapSort()
© DSI 2005
37