Algoritmos e Estruturas de Dados [LEEC] (2024/2025)

Aulas teóricas

Artur Miguel Dias

Teórica 03 (21/mar/2025)

Implementação do TAD turma usando um vetor que cresce automaticamente.
Introdução às coleções padrão genéricas.
TAD Info, blocos informativos e funções universais.

Slides

Problema da turma - versão com vetor extensível

Pretende-se uma nova versão do programa que permita gerir as notas dos alunos duma turma.

Na versão original do programa, cada turma tem capacidade para 100 alunos e não pode crescer.

Nesta nova versão do programa, cada turma continua a ser criada com a capacidade inicial de 100 alunos, mas deve poder crescer automaticamente, consoante as necessidades.

Sempre que se tenta acrescentar um aluno numa turma cheia, duplica-se a capacidade da turma e assim o novo aluno já cabe.

Uma turma que esteja constantemente a receber novos alunos e a crescer, vai assumindo as seguintes capacidades: 100 → 200 → 400 → 800 → 1600 → ...

Discussão

O que precisa de ser alterado no programa?

Está em causa uma simples alteração interna no TAD Turma. Portanto basta alterar o que for necessário no ficheiro "Turma.c" e o resto do programa permanece sem alteração.

Veja abaixo a nova versão do ficheiro "Turma.c". Bastou alterar o seguinte:

No tipo struct Turma, o vetor de tamanho fixo:
é trocado por um apontador:
O vetor dos alunos será allocado dinamicamente para poder crescer.
As funções que precisam de ter a sua implementação alterada são apenas as seguintes:
Estas funções estão marcadas com o comentário "// MUDOU".

Duas implementações alternativas?

Decidimos programar a nova implementação do TAD Turma num novo ficheiro chamado "TurmaX.c".

Mas não deitamos fora o "Turma.c" original. Consoante a nossa decisão, podemos incorporar qualquer uma das duas implementações no projeto do Code::Blocks.

Não faz mal nenhum guardar as duas versões. Mas cuidado: não podemos incorporar as duas implementações ao mesmo tempo pois isso causaria erros de "Multiple definition ...".

Turma.h

O ficheiro "Turma.h" não sofre alteração.

TurmaX.c

O ficheiro "TurmaX.c" apresenta a visão privada do TAD Turma e implementa este TAD.

Esta implementação faz crescer automaticamente o vetor de alunos interno. Na versão original, o vetor tem tamanho fixo.

Para fazer crescer o vetor, o código mostra duas maneiras de programar a função privada asseguraCapacidade. A versão que usa a função do C realloc é mais simples do que versão baseada em malloc; mas importa observar as duas formas de resolver o problema.

MainTurma.c

O ficheiro "MainTurma.c" não sofre alteração.

AlunoG.c

O ficheiro "AlunoG.c" reimplementa o TAD Aluno usando objetos que podem ser usados em coleções genéricas.

Este é o primeiro exemplo em que usamos o TAD Info, da nossa biblioteca.

Para os alunos poderem ser usados em contextos genéricos, o que é preciso fazer é simples:

Escrever "Info info;" no primeiro campo da struct Aluno.

Na função criaAluno, inicializar o campo info desta maneira:

a->info = criaInfo("Aluno", destroiAluno, NULL, comparaAluno, NULL, textoAluno);

Info.h

As nossas coleções genéricas vão guardar objetos que têm o tipo indeterminado obj, assim definido:

typedef void *obj;

Os objetos guardados nas nossas coleções genéricas precisam de conter um bloco informativo com informação requerida pelas coleções. O TAD Info define e implementa esses blocos informativos.

Aos objetos que contenham blocos informativos, podem aplicar-se as seguintes seis funções universais:

string tipo(obj ob);
void destroi(obj ob);
void destroiTudo(obj ob);
int compara(obj ob1, obj ob2);
int dispersao(obj ob, int dim);
string texto(obj ob);

Veja no exemplo "AlunoG.c" como os blocos informativos são construidos, na prática.

Info.c

A implementação do TAD Info. Faz a gestão do que é guardado nos blocos informativos.

Não vamos estudas esta implementação nas aulas. Para nós o importante será entender o ficheiro "Info.h" para saber com implementar objetos preparados para serem usados em coleções genéricas.

#60