Prova 2 - Turmas A e B

Instituto de Computação da UNICAMP

Disciplina MC202: Segundo Semestre de 2001

Prova Prática

Prof.

João Meidanis (Turmas A e B)

Para evitar que futuras distribuições do laboratório apaguem os arquivos fontes de laboratórios anteriores, cada laboratório virá com sua versão enunciado e uma versão de distribuição da libdados, a qual não contém fonte em libdados/src (exceto comum.c) e nem os diretórios de laboratórios. As instruções para instalar este laboratório seguem abaixo. Este laboratorio, por utilizar alguns itens da libdados com suas estruturas alteradas, vem apenas com sua versão enunciado.

Clique em arquivos auxiliares na pagina principal da prova 02AB para pegar a versão enunciado desta prova (prova2AB.tar.gz).
Execute tar -xvzf prova2AB.tar.gz dentro de provas para descompactar a prova 2AB.

A prova2AB aborda o tema de CONJUNTOS DISJUNTOS. Um exemplo da representação que será usada é dado abaixo. Considere a coleção da figura 1, onde vemos uma coleção de conjuntos disjuntos sobre o universo {0,1,2,3,4,5}. A representação computacional desta coleção é mostrada na tabela 1. Note que, além de um campo para o pai, temos o rank (posto) e o número de elementos de cada conjunto, mas estes dois últimos campos só são relevantes para raízes (representantes) de conjuntos (em negrito na figura 1). Nos outros nós, seu valor é irrelevante e o valor mostrado é o da última vez que o nó foi raiz.

Figura 1. Exemplo de coleção.

Tabela 1. Representação da coleção da figura 1.
Em negrito, valores relevantes.
	0	1	2	3	4	5
pai	0	0	2	0	3	2
rank	2	0	1	1	0	0
nelem	4	1	2	2	1	1

O exercício do lab é implementar as funções principais Makeset, Find e Union da estrutura de conjuntos disjuntos, além de funções adicionais Libera, NSets e NElems. As especificações detalhadas destas funções estão em cdisj.c, e da estrutura em geral estão em cdisj.h.

Os arquivos de teste e solução bem como LEIAME, Makefile, prova2AB.c, etc, são fornecidos em prova2AB. O arquivo LEIAME traz a sintaxe dos comandos como especificados nos arquivos de teste.

Para compilar sua prova basta apenas executar make prova no diretório prova2AB. Este comando criará o executável prova2ABneste diretório.

Para gerar as solucões de cada teste X execute prova2AB < arqX.tes > myarqX.res. Você pode então comparar seu arquivo .res com o arquivo oficial arqX.res. Incluímos no pacote do lab um script teste.bash que pode ser usado para testar seu lab sem submeter: use o comando

. teste.bash

Para submissão você precisa enviar apenas o cdisj.c.

O programa pode ser submetido apenas na linguagem C.

26/11/2001.