MC102: Algoritmos e Programação de Computadores - Turmas K e L

Zanoni Dias (PED)

Segunda Avaliação de Laboratório

Lista Ligada

O objetivo deste laboratório é a implementação de um programa para manipulação de conjuntos de inteiros, através de listas ligadas ordenadas. Você deve usar a seguinte declaração para o tipo básico dos conjuntos:

type Ponteiro = ^Elemento;

Elemento = record

info: Integer;

proximo: Ponteiro;

end;

Você deve usar o esboço disponível na página do curso em:

www.ic.unicamp.br/~zanoni/mc102/Documentos/Avaliacao-02.pas

e implementar as seguintes rotinas (e eventualmente outras auxiliares que você julgue necessário):

• procedure Insere(var conjunto: Ponteiro; x: Integer);

Insere o inteiro 'x' no conjunto dado, de tal forma que o conjunto permaneça ordenado.

• procedure Remove(var conjunto: Ponteiro; x: Integer);

Remove, caso exista, o elemento 'x' do conjunto.

• procedure Imprime(conjunto: Ponteiro); *

Imprime todos os elementos do conjunto, em ordem crescente, um por linha.

• procedure RemoveTudo(var conjunto: Ponteiro); *

Remove todos os elementos do conjunto.

• function Uniao (a,b: Ponteiro): Ponteiro;

Retorna um novo conjunto que representa a união dos conjuntos 'a' e 'b'.

• function Intersecao (a,b: Ponteiro): Ponteiro;

Retorna um novo conjunto que representa a interseção dos conjuntos 'a' e 'b'.

• function Cardinalidade(conjunto: Ponteiro): Integer; *

Devolve a cardinalidade do conjunto, ou seja, o número de elementos.

• function K_Esimo(conjunto: Ponterio; k: Integer): Integer; *

Devolve o k-ésimo elemento do conjunto.

Entrega

O programa é estritamente individual e deverá ser entregue até no máximo domingo, dia 14 de janeiro de 2001, através da Web Page do curso (www.ic.unicamp.br/~zanoni/mc102). Não haverá nenhum tipo de prorrogação.

Observações

Você não deve usar nenhuma estrutura de dados de alocação estática (arrays ou matrizes, por exemplo). Os conjuntos devem ser mantidos ordenados (ordem crescente). Faz parte da avaliação entender e comentar o programa principal do esboço, bem como criar entradas de teste apropriadas.

Não altere o programa principal (a menos de comentários). Não altere também as definições das rotinas, nem crie novas variáveis globais.

Implemente pelo menos metade das rotinas de forma recursiva. Será descontada nota de quem não seguir esta exigência, assim como o aluno que implementar mais do que 4 rotinas recursivas receberá um bônus proporcional o número de rotinas implementadas.

É possível implementar todas as rotinas de forma recursiva, sendo que as rotinas mais simples (marcadas com asterisco) podem ser implementadas sem o uso de nenhuma variável auxiliar, e as demais precisam de uma única variável do tipo Ponteiro.

Maiores detalhes sobre o enunciado desta avaliação serão discutidos em sala de aula e no laboratório. Não serão discutido aspectos de implementação. Qualquer tentativa de fraude será punida de acordo com o documento “Descrição do Curso” disponível na página do curso.

Boa sorte.