EXERCÍCIOS DE REVISÃO PARA P2 (2013.2)
Parte I: Busca e Ordenação
Considere que uma instituição mantém os dados dos resultados dos candidatos de um
concurso em um vetor de ponteiros para o tipo estruturado definido a seguir:
typedef struct candidato {
int media;
/* media final (0 a 100) */
int redacao;
/* nota da redação (0 a 100) */
int prioridade;
/* prioridade atribuida ao candidato (0 a 5) */
char nome[81]; /* nome do candidato */
} Candidato;
Para se poder realizar a alocação de vagas para os candidatos, é necessário ordenar
os candidatos de acordo com o seguinte critério:
• os candidatos devem ser ordenados em ordem decrescente de média
• candidatos com a mesma média devem ser ordenados em ordem
decrescente de nota de redação
• candidatos com mesma média e nota de redação devem ser ordenados em
ordem crescente de prioridade
[1a] Escreva uma função ordenaBolha que, usando o algoritmo bubble sort, ordena
um vetor de ponteiros para Candidato conforme o critério descrito acima. A função
deve receber, como parâmetros, o vetor de candidatos e o número de elementos do
vetor:
void ordenaBolha(Candidato **v, int n);
[1b] Escreva uma função ordenaRapida que, usando o algoritmo quick sort, ordena
um vetor de ponteiros para Candidato conforme o critério descrito na questão
anterior. Novamente, a função deve receber, como parâmetros, o vetor de candidatos
e o número de elementos do vetor:
void ordenaRapida(Candidato **v, int n);
Neste exercicio você pode usar a função qsort da biblioteca padrão de C se desejar.
Ela tem o protótipo, abaixo, descrito em stdlib.h:
void qsort(void *v, int n, int tam, int (*cmp) (const void *, const void *));
[2] Escreva uma função que, considerando que o vetor de ponteiros para Candidato
está ordenado conforme o critério descrito anteriormente, e usando a estratégia de
busca binária, descubra qual a maior nota de redação dentre os candidatos que
obtiveram a média especificada. Caso nenhum candidato tenha obtido a média
especificada, a função deve retornar 0. Se encontrar pelo menos um candidato com
essa média, a função retornará 1 e preencherá a maior nota de redação encontrada
para essa média no endereço recebido como parâmetro. Os outros parâmetros para a
função são o vetor de candidatos, o número de elementos do vetor e a média para a
qual se deseja a maior nota de redação:
int maiorNotaRedacao(Candidato **v, int n, int media, int *nota);
Parte II: TAD
Neste exercício vamos criar um tipo de dado para representar um número racional, o
tipo Racional, e definir algumas operações simples sobre esse tipo. Um número
racional é expresso por dois inteiros: um numerador e um denominador (este
último diferente de zero!)
[1a] Vamos começar definindo a interface do tipo Racional, criando o arquivo
racional.h. Esse arquivo deve conter a definição (typedef) do tipo Racional e as
operações abaixo:
/* TAD: Racional n/d */
/* Tipo exportado */
typedef struct racional Racional;
/* Cria novo número racional */
Racional *cria_racional (int numerador, int denominador);
/* Mostra um número racional na tela como uma fração */
void mostra_racional (Racional *r);
/* Libera a memória de um número racional */
void libera_racional(Racional *r);
/* Obtem o numerador */
int numerador_racional(Racional *r);
/* Obtem o denominador */
int denominador_racional(Racional *r);
[1b] Vamos criar agora uma implementação do tipo Racional, em um arquivo
racional.c (não esqueça de incluir, neste arquivo, o arquivo que define a interface
desse tipo, racional.h , além dos arquivos com os protótipos das funções da
biblioteca padrão usadas por essa implementação!)
• Para representar o tipo de dado Racional, defina uma estrutura para
armazenar dois inteiros: o numerador e o denominador.
• Crie uma função interna ao módulo racional.c chamada mdc, que receba
dois números inteiros e retorne o maior divisor comum dos dois:
static int mdc (int x, int y);
Como essa função é definida como static, ela não será "visível" fora desse
módulo! Lembre-se que criamos uma função mdc no Laboratório 8, usando a
definição abaixo:
• mdc(x,y) = x, se y = 0
• mdc(x,y) = mdc(y, x%y), se y > 0
• Implemente agora a função cria_racional . Ela deve alocar dinamicamente a
estrutura que representará o racional, inicializar seus campos e retornar seu
endereço. Caso não seja possível alocar memória, mostre uma mensagem e
termine o programa, chamando exit.
ATENÇÃO: a representação interna do racional deve sempre usar os menores
números possíveis, ou seja, mesmo que o usuário forneça os valores 4 e 6
(racional 4/6), deve-se armazenar "2/3". Use a função interna mdc para fazer a
transformação necessária.
• Implemente a função mostra_racional . Ela deve exibir na tela o numerador e
o denominador, como uma fração, por exemplo 2/3 (isto é, colocando uma '/'
entre eles)
• Implemente a função libera_racional . Ela deve apenas liberar a memória
alocada para a representação do racional.
• Implemente as funções numerador_racional e denominador_racional .
[2] Crie agora um outro arquivo C para testar a sua implementação, contendo algo
como abaixo:
#include <stdio.h>
#include "racional.h"
int main (void) {
int um, outro;
Racional *meunum;
printf("Entre o valor do racional (formato numerador/denominador): ");
scanf ("%d/%d", &um, &outro);
while (um!=0) {
meunum = cria_racional (um, outro);
mostra_racional (meunum);
libera_racional(meunum);
printf("Entre próximo valor (0/0 para terminar): ");
scanf ("%d/%d", &um, &outro);
}
return 0;
}
Construa seu programa e teste as funções de racionais.
[3] Acrescente à interface de Racional (em racional.h) uma função para
multiplicar dois números racionais:
/* Retorna o produto de dois racionais */
Racional *mult_racional (Racional *um, Racional *outro);
Implemente essa função em racional.c: essa função deve criar um novo Racional,
reduzindo o resultado da multiplicação (i.e, o racional resultante deverá os menores
números possíveis). Você pode aproveitar algum código que você já tenha
implementado...
Mude sua main para testar essa função.
[4] Acrescente agora à interface uma função de soma:
/* Retorna a soma de dois racionais */
Racional *soma_racional (Racional *um, Racional *outro);
e implemente essa função, sem esquecer de reduzir o resultado.
Mude sua main para testar essa função.