Acervos

AED - 2013-2014 - 1o Semestre
Algoritmos e Estruturas de Dados
Laborat´rio 5 - Acervos o Semana de 18 a 22 de Novembro de 2013
Dura¸ao: 2 horas c˜ O objectivo desta aula ´ o estudo e manipula¸˜o de acervos (heaps). Os ficheiros heap.c e heap.h e ca contˆm a implementa¸˜o e a interface para um tipo heap. Este tipo de dados est´ implementado como um e ca a tipo abstracto o que lhe confere grande versatilidade. Nesta implementa¸˜o, o acervo cont´m elementos ca e do tipo Item, definido no ficheiro Item.h que ´ igualmente inclu´ e ıdo. Alterando o tipo de dados Item, o mesmo c´digo pode ser usado como acervo de outros tipos de dados. o O ficheiro client.c cont´m um programa que permite experimentar v´rias opera¸˜es sobre acere a co vos contendo n´meros inteiros (at´ 16 n´meros; para acervos maiores ter´ de alterar a defini¸˜o em u e u a ca client.c). Utilize a op¸˜o ”h”do menu do client.c para verificar as opera¸˜es dispon´ ca co ıveis ou a desenvolver.
Examine cuidadosamente o c´digo contido nos ficheiros heap.h e heap.c. o 1. Compile e execute o programa cliente. Estude o exemplo (op¸˜o ”e”do menu do client.c). Qual ca ´ a condi¸˜o de acervo que est´ a ser utilizada? Verifique no c´digo como ´ testada a condi¸˜o de e ca a o e ca acervo. 2. Insira v´rios n´meros inteiros no acervo. Verifique o funcionamento da rotina FixUp(). A ordem a u pr´pria do acervo ´ mantida? o e
3. Altere o valor de um elemento do acervo, aumentando e diminuindo sucessivamente o valor. A ordem ´ mantida no acervo? Quais s˜o as fun¸˜es usadas para o efeito? e a co 4. Remova v´rias vezes o maior elemento do acervo. O que ´ que acontece? Quais s˜o as fun¸˜es a e a co necess´rias para obter este resultado? a 5. Crie uma fun¸˜o CleanHeap() que apague todos os elementos de um acervo existente libertando ca a mem´ria alocada. Associe esta funcionalidade ` op¸˜o ”c”do menu do client.c. Assegure-se o a ca ainda que na sa´ do programa toda a