Estruturas de Dados – 2014/2
Aula de Laboratório – 24/11/2014
Profa Patrícia Dockhorn Costa ([email protected])
Busca Binária
Considere um tipo que representa os dados de um aluno definido pela estrutura:
struct aluno {
int mat; /* n´umero de matr´ıcula */
char turma; /* turma do aluno: a, b, c, d, ou e */
char nome[81]; /* nome do aluno */
float p1, p2, p3; /* notas */
};
typedef struct aluno Aluno;
1) Considere um vetor que armazena, em ordem crescente do número de matrícula,
ponteiros para estruturas Aluno. Usando a técnica de busca binaria vista no curso, escreva
uma função para buscar um aluno no vetor dado um número de matrícula. A função deve
receber como parâmetros o número de alunos, o vetor e o número de matrícula a ser
buscado. A função deve retornar o índice no vetor onde o elemento está armazenado. Se
o número de matrícula não for encontrado no vetor, a função deve retornar -1. A função
deve obedecer ao prototipo definido a seguir:
int busca (int n, Aluno** v, int mat);
2) Considere um vetor que armazena, em ordem alfabética de nomes, ponteiros para
estruturas Aluno. Considere que os nomes armazenados contêm apenas letras minúsculas.
Usando a técnica de busca binária vista no curso, escreva uma função para buscar um
aluno no vetor dado um nome. A função deve receber como parâmetros o número de
alunos, o vetor e o nome a ser buscado. A função deve retornar o índice no vetor onde o
elemento está armazenado. Se o número de matrícula não for encontrado no vetor, a
função deve retornar -1. A função deve obedecer ao protótipo definido a seguir:
int busca (int n, Aluno** v, char* nome);
3) Considere um vetor que armazena, em ordem alfabética de nomes, estruturas Aluno.
Considere que os nomes armazenados contêm apenas letras minúsculas. Usando a técnica
de busca binária vista no curso, escreva uma função para buscar um aluno no vetor dado
um nome. A função deve receber como parâmetros o número de alunos, o vetor e o nome
a ser buscado. A função deve retornar o índice no vetor onde o elemento está
armazenado. Se o número de matrícula não for encontrado no vetor, a função deve
retornar -1. A função deve obedece A função deve obedecer ao protótipo definido a
seguir:
int busca (int n, Aluno* v, char* nome);
Considere uma árvore binária de busca que armazena valores inteiros. Nesta estrutura, pode
ocorrer repetições de um mesmo valor. Assim, os valores associados aos nós da subárvore da
esquerda são menores que o valor associado à raiz, e os valores associados à subárvore da
direita são maiores ou iguais. O tipo que representa o nó da árvore é dados por:
struct arv {
int info;
struct arv* esq;
struct arv* dir;
};
typedef struct arv Arv;
4) Escreva uma função que retorne o número de ocorrências de um dado valor x
na árvore. A função deve tirar proveito da ordenação da árvore e obedecer
ao seguinte protótipo:
int ocorrencias (Arv* a, int)
5) Escreva uma função que imprima os valores associados às folhas em ordem
não crescente (isto é, do maior para o menor, podendo haver repetições). A
função deve obedecer ao seguinte protótipo:
int imprime_folhas (Arv* a)