P4_2014.2_INF1007 - Prog 2

Prévia do material em texto

��
Disciplina: INF1005 - Programação I
Avaliação:	 P1	Data: 12/09/2014
Algumas Funções de Bibliotecas (NESTA PROVA VOCE PODE USÁ-LAS EM QUALQUER QUESTÃO)
	stdio.h:
int scanf (char* formato, ...);
int printf (char* formato, ...);
FILE* fopen (char* nome, char* modo);
int fclose (FILE* fp);
int fscanf (FILE* fp, char* formato, ...);
int fprintf (FILE* fp, char* formato, ...);
char*fgets(char* str, int size, FILE* fp);
int sscanf(char* str, char* formato, ...);
stdlib.h:
void* malloc (int nbytes);
void free (void* p);
	
	math.h:
double sqrt (double x);
double pow (double x, double exp);
double cos (double radianos);
double sin (double radianos);
string.h:
int strlen (char* s);
int strcmp (char* s, char *t);
char* strcpy (char* destino, char* fonte);
char* strncpy (char* destino, char* fonte, int n);
char* strcat (char* destino, char* fonte);
char* strdup (char* s);
void qsort (void *v, int n, int tam, int (*cmp)(const void*, const void*));
void * bsearch(void * info, void * v, int n, int tam, int (*cmp)(const void *, const void *));
1ª Questão (2,0 pontos) Considere o tipo estruturado abaixo (não é TAD) que representa um imóvel em uma imobiliária:
struct endereco
{	char rua[31];
	int numero;
	char complemento[21];
	char bairro[21];
};
typedef struct endereco Endereco;
struct imovel
{	Endereco endereco;
	int	 numQuartos;
	float	 valor;
};
typedef struct imovel Imovel;
Escreva a função obtemImoveisPerfil, que:
- recebe um vetor de Imoveis, o número de imóveis, um bairro e um número de quartos. Recebe também o endereço de uma variável inteira, onde deve ser retornado o número de imóveis que atendam simultaneamente aos critérios bairro e número de quartos;
- cria e retorna (o endereço do primeiro elemento de) um novo vetor de PONTEIROS para Imoveis, alocado dinamicamente do tamanho exato necessário, com os ponteiros para os imóveis do vetor original recebido que atendam simultaneamente aos critérios bairro e número de quartos. Não esqueça que também deve ser devolvido, em uma variável inteira cujo endereço deve ser fornecido na chamada da função, o número de imóveis que atendam ao critério. 
Obs: Caso não exista nenhum imóvel que atenda aos critérios, nenhum vetor é criado e deve ser retornado NULL. Caso não seja possível criar o novo vetor, também deve ser retornado NULL.
Por exemplo, se fosse recebido o vetor abaixo com 6 imóveis, o bairro BOTAFOGO e o número de quartos igual a 3:
Seria retornado o vetor de ponteiros com 2 elementos: �
2ª Questão (3,0 pontos) Considere o Tipo Abstrato de Dados (TAD) Perfume que representa um perfume vendido por uma perfumaria. A interface do TAD encontra-se no arquivo Perfume.h, descrito abaixo:
 /* Interface do TAD Perfume: arquivo Perfume.h */
typedef struct perfume Perfume;
/* funcao perfCriaPerfume: recebe um nome, um fabricante, um preco e um percentual de desconto, e cria um novo Perfume com esses dados, retornando um ponteiro (ou seja, o endereço) para o Perfume criado */
Perfume *perfCriaPerfume (char *nome, char *fab, float preco, float percentualDesconto);
/* funcao perfExibe: recebe um ponteiro para um Perfume existente e exibe os dados desse Perfume */
void perfExibe (Perfume *pe);
/* funcao perfObtemPrecoFinal: recebe um ponteiro para um Perfume existente e retorna o preco final desse Perfume, ou seja, o preco calculado já com o DESCONTO*/
float perfObtemPrecoFinal(Perfume *pe);
/* funcao perfLibera: recebe um ponteiro para um Perfume existente e libera o espaco ocupado por esse Perfume */
void perfLibera (Perfume *pe);
Considerando o TAD Perfume acima, escreva a função ordena.
A função ordena:
- recebe um vetor de ponteiros para o TAD Perfume e o número de perfumes;
- ordena o vetor recebido crescentemente por preço final. 
Sua função deve utilizar o método quicksort. Você deve escrever e utilizar uma função de comparação em separado. (Pode ser usada a qsort da biblioteca).
Exemplo: 
�
Se os perfumes (apontados) do vetor são:
•	love-DIOR-70.50-10.00
•	luar-DIOR-90.50-5.00
•	rose-DGAB-70.50-20.00
•	mine-CHER-80.50-10.00
•	jazz-DIOR-90.50-10.00
•	kate-DIOR-70.50-10.00
•	bela-CHER-80.50-20.00
•	flor-DGAB-60.50-10.00
Após a ordenação, temos:
•	flor-DGAB-60.50-10.00 (PRECO FINAL: 54.45)
•	rose-DGAB-70.50-20.00 (PRECO FINAL: 56.40)
•	kate-DIOR-70.50-10.00 (PRECO FINAL: 63.45)
•	love-DIOR-70.50-10.00 (PRECO FINAL: 63.45)
•	bela-CHER-80.50-20.00 (PRECO FINAL: 64.40)
•	mine-CHER-80.50-10.00 (PRECO FINAL: 72.45)
•	jazz-DIOR-90.50-10.00 (PRECO FINAL: 81.45)
•	luar-DIOR-90.50-5.00 (PRECO FINAL: 85.97)
�
3ª Questão (2,0 pontos) Considere uma lista simplesmente encadeada de (ponteiros para) Paciente, cujo nó é representado pelo tipo estruturado NoLista abaixo:
typedef struct paciente Paciente;
struct paciente
{	char nome[51];
	int idade;
};
typedef struct noLista NoLista;
struct noLista
{	Paciente *pac;
	struct noLista *prox;
};
Escreva a função verificaOrdAlfabeticamente, que:
- recebe (um ponteiro para) a lista encadeada,
- retorna 1 se a lista encontra-se ordenada alfabeticamente por nome ou 0 em caso contrário.
Obs: Caso a lista esteja vazia ou possua um único elemento, a função retorna 1.
4ª Questão (2,0 pontos) Considere uma árvore binária de busca que guarda as informações (nome e nota) dos candidatos de um concurso, ordenada crescentemente por nota, cujo tipo que representa o nó da árvore é o ABB apresentado abaixo:
struct candidato
{	char nome[51];
	float nota;
};
typedef struct candidato Candidato;
struct no_abb_busca
{	Candidato *info;
	struct no_abb_busca *esq;
	struct no_abb_busca *dir;
};
typedef struct no_abb_busca ABB;
Escreva a função mostraOrdDecAcima, que:
- recebe (um ponteiro para) a raiz da árvore binária de busca e uma nota limite inferior X;
- exibe na tela, em ordem decrescente de nota, os dados dos candidatos com nota > x.
Por exemplo, se a árvore binária de busca fosse a da figura acima e a nota limite fosse 5.0, teríamos a seguinte saída na tela:
{kyra, 9.0}, {rosa, 7.5}, {davi, 7.5}, {vera, 6.5}, {luiz, 6.0}, {sofia, 5.5}, {liana, 5.3}
�
Soluções:
Q1)
Imovel *obtemImoveisPerfil(Imovel *vim, int n, char *bairro, int nQ, int *pQtd)
{	Imovel **vpi;
	int i, j;
	*pQtd=0;
	for (i=0; i<n; i++)
		if(strcmp(vim[i].endereco.bairro, bairro)==0 && vim[i].numQuartos == nQ)
			(*pQtd)++;
	if (*pQtd == 0)
		return NULL;
	vpi = (Imovel **) malloc ((*pQtd)*sizeof(Imovel *));
	if (vpi == NULL)
		return NULL;
	j = 0;
	for (i=0; i<n; i++)
		if(strcmp(vim[i].endereco.bairro, bairro)==0 && vim[i].numQuartos == nQ)
		{	vpi[j]=&vim[i];
			j++;
		}
	return vpi;
}
Q2)
float compPerf(Perfume *pe1, Perfume *pe2)
{	float pr1= perfObtemPrecoFinal(pe1);
	float pr2= perfObtemPrecoFinal(pe2);
	return pr1-pr2;
}
void ordena(Perfume **vp, int n)
{	int a, b;
	Perfume *aux, *pivo;
	if (n<=1)
		return;
	pivo= vp[0]; a=1; b=n-1;
	do
	{	while (a<n && compPerf(vp[a],pivo)<=0) a++;
		while (compPerf(vp[b],pivo)> 0) b--;
		if (a<b)
		{	aux = vp[a]; vp[a]= vp[b]; vp[b]=aux;
			a++; b--;
		}
	} while (a<=b);
	vp[0]= vp[b]; vp[b]=pivo;
	ordena(vp,b);
	ordena(&vp[a], n-a);
}
�
Q3)
int verificaOrdAlfabeticamente (NoLista *lst)
{	if (lst==NULL || lst->prox==NULL)
		return 1;
	while(lst->prox!=NULL)
	{	if (strcmp(lst->pac->nome, lst->prox->pac->nome)>0)
			return 0;
		lst = lst->prox;
	}
	return 1;
}
Q4)
void mostraOrdDecAcima (ABB *r, float notaLimI)
{	if (r==NULL)
		return;
	if(r->info->nota <= notaLimI)mostraOrdDecAcima (r->dir, notaLimI);
	else
	{	mostraOrdDecAcima (r->dir, notaLimI);
		printf("\n%s-%.2f ", r->info->nome, r->info->nota);
		mostraOrdDecAcima (r->esq, notaLimI);
	}
}
VPat,12,112
BOTAFOGO
3 quartos 700000,00
BMit,77,734
LEBLON
2 quartos 800000,00
BRib,85,914
COPACABANA
3 quartos 700000,00
SClem,55,401
BOTAFOGO
2 quartos 700000,00
RGrand,7,503
BOTAFOGO
3 quartos 650000,00
ACop,79,202
COPACABANA
1 quarto 600000,00
ana
24
teo
32
bia
45
leo
61
rui
28
Fig1: lista ordenada, a funcao retorna 1
lea
32
bia
40
edu
55
cris28
28
mac
43
Fig2: lista NAO ordenada, a funcao retorna 0
luiz
6.0
davi
7.5
kyra
9.0
vera
6.5
dina
4.0
lais
3.0
andre
4.0
sofia
5.5
liana
5.3
rosa
7.5
furia
allan
2010
nada
costa
2011
azul
mark
2014
briga
allan
2011
love
mark
1995
pain
costa
1994
raso
liam
2000
veloz
mark
2006
luva
mark
2004
bela
liam
2013
feroz
allan
1997
corra
mark
1997
morte
mark
2009
� PAGE \* MERGEFORMAT �3�
_1477842235.bin