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 exercício 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 complexo, o tipo
Complexo, e definir algumas operações simples sobre esse tipo. Um número complexo é
expresso por dois números, a parte real e a parte imaginária.
[1a] Crie a interface do tipo Complexo, criando o arquivo complexo.h. Esse arquivo deve conter
a definição (typedef) do tipo Complexo e as operações de criar, liberar, imprimir, somar, subtrair e
multiplicar.
[1b] Crie agora a implementação do tipo Complexo, em um arquivo complexo.c (não esqueça
de incluir, neste arquivo, o arquivo que define a interface desse tipo, complexo.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 Complexo, defina uma estrutura para armazenar a parte real
e a imaginária
• Implemente a função que cria complexos. Ela deve alocar dinamicamente a estrutura que
representará o complexo, inicializar seus campos e retornar seu endereço. Caso não seja
possível alocar memória, mostre uma mensagem e retorne NULL.
• Implemente a função que exibe. Ela deve exibir na tela o número complexo na forma
tradicional, por exemplo: "3+2i"
• Implemente a função que libera complexos. Ela deve liberar a memória alocada para a
representação do complexo.
• Implemente as funções de soma, subtração e multiplicação. Relembrando:
• (a+bi) + (c+di) = (a + c) + (b + d)i
• (a+bi) - (c+di) = (a - c) + (b - d)i
• (a+bi) * (c+di) = (ac + bd) + (ad + bc)i
[2] Crie agora um outro arquivo C, usacomplexos.c, para testar a sua implementação. Seu
programa deve usar todas as funções definidas em complexo.h.
[3] Acrescente à interface e à implementação do seu TAD Complexo uma função que verifica se
o número complexo é real. Ela deve retornar 0 se o número complexo não é real, e 1 se ele é real.
Um número complexo é real se a parte imaginária é zero.
[4] Altere seu programa de teste para usar a função que você criou em [3]. Crie no seu programa
dois números complexos que não são reais, mostre que sua função confirma que eles não são
reais, efetue uma operação entre eles que resulte em um número real, e mostre que sua função
confirma que o resultado é real.