Análise e Desenho de Algoritmos
Exercício de C

Departamento de Informática
Universide de Évora

2000/2001

Preâmbulo

Este é um exercício individual destinado aos alunos de Análise e Desenho de Algoritmos que queiram praticar o uso de C, e não faz parte da avaliação da cadeira.

O exercício deverá ser entregue até às 17 horas do dia 6 de Abril. Para poder ser corrigido, e os comentários à resolução serem entregues ao seu autor, terão de ser entregues uma listagem do código (em papel), e todos os ficheiros criados. Estes poderão ser entregues em disquete ou enviados por e-mail para v p@ di.uevora.pt. Para o fazer a partir do Linux, pode ser utilizado o comando

tar -czf - ficheiros-a-enviar | uuencode n-aluno.tar.gz | \
mail -s 'exercicio C' vp @ di.uevora.pt

que deve ser todo escrito numa linha (i.e., omitindo o carácter \). As listagens poderão ser deixadas no cacifo do docente, situado em frente ao gabinete 226-CLV.

Quem entregar o exercício, receberá de volta a listagem entregue, com comentários sobre a implementação feita e o código apresentado.

Enunciado

Implemente uma biblioteca para a manipulação de vectores (arrays de uma dimensão) de inteiros. A biblioteca deverá possuir as primitivas que se descrevem abaixo.

• int *vect_novo(int dimensao) - cria e devolve um vector com a dimensão dada, com todas as posições a zero; no caso de não conseguir obter memória para criar o vector ou de dimensao não ser um inteiro positivo, deve devolver NULL;
• void vect_destroi(int vect[]) - liberta a memória utilizada pelo vector;
• void vect_enche(int vect[], int dimensao, int valor) - põe valor em todas as posicões do vector;
• void vect_soma(int vect1[], int vect2[], int dimensao) - soma os elementos dos dois vectores no primeiro;
• void vect_subtrai(int vect1[], int vect2[], int dimensao) - subtrai os elementos do segundo vector aos do primeiro, onde guarda os resultados;
• void vect_mult(int vect[], int dimensao, int escalar) - multiplica todos os elementos do vector por escalar;
• int vect_prodint(int vect1[], int vect2[], int dimensao) - calcula e devolve o produto interno dos dois vectores;
• void vect_ordena(int vect[], int dimensao) - ordena o vector; a função deverá implementar um algoritmo de ordenação eficiente;
• float vect_media(int vect[], int dimensao) - calcula e devolve a média dos elementos do vector;
• int vect_max(int vect[], int dimensao) - devolve o maior elemento do vector;
• int vect_min(int vect[], int dimensao) - devolve o menor elemento do vector;
• int *vect_copia(int vect1[], int dimensao1, int vect2[], int dimensao2) - copia o conteúdo do segundo vector para o primeiro e devolve-o; se dimensao1 for menor que dimensao2, só copia dimensao1 posições; se dimensao1 for maior que dimensao2, copia dimensao2 posições e deixa as restantes inalteradas; se vect1 é NULL, então cria e devolve uma cópia de vect2, ou NULL se ocorrer algum erro;
• void vect_print(int vect[], int dimensao, int n) - mostra no écran o conteúdo do vector, escrevendo n elementos por linha alinhados verticalmente pelo dígito menos significativo; por exemplo, se o vector tiver na posição i = 0,...,8 o valor i+1 e se n for 3, o resultado será

  1·2·3
  4·5·6
  7·8·9
  

  (onde · representa um espaço), mas, se a dimensão do vector for 10, então aparecerá

  ·1··2··3
  ·4··5··6
  ·7··8··9
  10
  

Observações finais

Assuma que as únicas situações de erro que podem ocorrer são as contempladas acima, nomeadamento porque o utilizador da biblioteca terá sempre o cuidade de não passar argumentos inválidos às restantes primitivas.

Apesar disso, a biblioteca descrita é pouco simpática, porque obriga a manter dois objectos por vector, o vector e a sua dimensão, o que, além de pouco cómodo, pode dar origem a enganos resultantes da troca das dimensões de dois vectores, por exemplo. Uma alternativa, para minorar este tipo de problemas, será definir um tipo vector opaco (i.e., cujo conteúdo não é acessível pelo utilizador) que encapsule o conteúdo do vector e a sua dimensão (e, eventualmente, outra informação). Assim, as funções da biblioteca deixam de necessitar de dois parâmetros por vector, passando a ter só um do tipo definido.

Esta abordagem vai criar outro tipo de problemas, nomeadamente nas primitivas que operam sobre dois vectores que devem ser da mesma dimensão. Este aspecto foi até agora escondido por, nestes casos, se ter apenas um parâmetro a dar a dimensão dos vectores, e passando para o utilizador a responsabilidade de só aplicar estas operações a vectores de dimensões compatíveis. Ao introduzir um tipo que englobe toda a informação sobre o vector, estas primitivas passam a ter de testar se os argumentos são compatíveis e assinalar os erros através do valor devolvido (tipicamente, 0 se estiver tudo bem, e -1 no caso contrário).

Se optar por esta implementação, a declaração do tipo opaco vector será

typedef void *vector;

que estará acessível ao utilizador através do ficheiro vectlib.h, e a que corresponderá uma implementação concreta no(s) ficheiro(s) com o código das primitivas. Nestas, os pares de parâmetros vect e dimensao serão substituídos por um único, de tipo vector, e as que devolvem um valor do tipo int * passarão a devolver um vector. Será também necessário criar as novas primitivas

• int vect_dim(vector vect) - para saber a dimensão de um vector;
• int vect_poe(vector vect, int posicao, int valor) - para modificar uma posição do vector; e
• int vect_valor(vector vect, int posicao, int *valor) - para aceder ao valor na posição dada, devolvido através do parâmetro valor.

As duas primitivas anteriores devolverão -1 se a posição dada não for válida para o vector.

Questões de estilo

O código deverá estar devidamente comentado, bem formatado e os identificadores usados deverão ajudar a descrever o que representam.

BOM TRABALHO