Primeiro Semestre de 2007
Novo Laboratório 2: Catálogo de Disciplinas
Árvore de Pré-requisitos
Suponha que você queira organizar seu horário na faculdade e, para
isso, queira saber quais matérias podem ser feitas a cada
semestre. Por exemplo, considere o catálogo contendo disciplinas e
suas dependências mostrado na figura abaixo (um link de a para
b indica que a é pré-requisito de b).
A próxima figura mostra um sequenciamento válido para as disciplinas
deste catálogo.
No entanto, para fazer a projeção da integralização do seu curso, é
necessário levar em consideração o limite de créditos e a
semestralidade em que as disciplinas são oferecidas.
Formato do Arquivo de Entrada
O arquivo de entrada descreve um conjunto que contém o número n de
disciplinas e o número máximo de créditos que um aluno pode cursar em
um semestre. Em seguida, há uma lista de códigos de disciplinas, com
seus respectivos números de créditos e semestralidade (S=1 indica que
é uma disciplina oferecida em semestre ímpar, S=2 indica que é uma
disciplina oferecida em semestre par e S=5 indica que é uma disciplina
oferecida todos os semestres). Finalmente, o arquivo de entrada tem
uma lista de links do tipo disciplina1
disciplina2. Um link de uma disciplina d1 para outra
disciplina d2 informa que d2 não pode ser cursada antes da disciplina
d1; ou seja, d1 é um pré-requisito de d2.
8
30
MA111 6 5
MA141 4 5
MA211 6 5
MC102 6 5
MC202 6 5
MC404 4 5
MC514 6 5
MC336 4 5
MA111 MA211
MA141 MA211
MC102 MC202
MC202 MC404
MC404 MC514
MC202 MC336
Formato do Arquivo de Saída
O arquivo de saída deve conter a lista de pré-requisitos de uma dada
disciplina (note que esta informação é diferente da versão anterior do
laboratório).
MA211: MA141 MA111
MC202: MC102
MC404: MC202
MC514: MC404
MC336: MC202
S1: MA111 MA141 MC102
S2: MA211 MC202
S3: MC404 MC336
S4: MC514
Arquivos
Você deverá implementar o arquivo catalogo.c de acordo com as
definições feitas em catalogo.h. Você pode usar a implementação de
fila fornecida, fazendo acesso exclusivamente às funções oferecidas
(não pode fazer acesso direto às estruturas de dados definidas).