Laboratório de Bioinformática - LBI: veja nossos projetos

Exercícios

Defina o tipo abstrato de dados "complexo", incluindo pelo menos cinco operações.

Solução: Veja abaixo os arquivos complexo.h e complexo.c.

complexo.h:

/*----------------------------------------

  Tipo "complexo"

----------------------------------------*/

struct compl {
  double a;
  double b;
};

typedef struct compl * complexo;

complexo soma (complexo x, complexo y);

complexo diferenca (complexo x, complexo y);

complexo produto (complexo x, complexo y);

complexo quociente (complexo x, complexo y);

double modulo (complexo x);

complexo.c:

#include "complexo.h"
#include 		/* para malloc, NULL */
#include 		/* para sqrt */

complexo soma (complexo x, complexo y) {

  complexo r;

  r = (complexo)malloc(sizeof(struct compl));
  if (r == NULL) {
    return NULL;
  } else {
    r->a = x->a + y->a;
    r->b = x->b + y->b;
  }

  return r;

}

complexo diferenca (complexo x, complexo y) {

  complexo r;

  r = (complexo)malloc(sizeof(struct compl));
  if (r == NULL) {
    return NULL;
  } else {
    r->a = x->a - y->a;
    r->b = x->b - y->b;
  }

  return r;

}

complexo produto (complexo x, complexo y) {

  complexo r;

  r = (complexo)malloc(sizeof(struct compl));
  if (r == NULL) {
    return NULL;
  } else {
    r->a = x->a * y->a - x->b * y->b;
    r->b = x->b * y->a + x->a * y->b;
  }

  return r;

}

/*----------------------------------------
  Na funcao abaixo, deveria haver um modo
  melhor de indicar que o divisor e' zero
  (no momento retorna-se NULL).
  ----------------------------------------*/

complexo quociente (complexo x, complexo y) {

  complexo r;
  double m;

  r = (complexo)malloc(sizeof(struct compl));
  if (r == NULL) {
    return NULL;
  } else {
    m = modulo(x);
    if (m == 0) {
      return NULL;
    } else {
      r->a = (x->a * y->a + x->b * y->b)/m;
      r->b = (x->b * y->a - x->a * y->b)/m;
    }
  }

  return r;

}

double modulo (complexo x) {

  return sqrt(x->a * x->a + x->b * x->b);

}

Determine a complexidade (número de operações) executadas pelo algoritmo abaixo (selection sort) em função do tamanho n do vetor de entrada:
```
0.   void SelectionSort(int *v, int n) {
1.      int i, j, k, t;
2.      for(i=0; i<n-1; i++) {
3.         j=i;
4.         for(k=j+1; k<n; k++)
5.            if (v[k] < v[j] )
6.               j=k;
7.         t=v[i]; v[i]=v[j]; v[j]=t;
8.      }
9.   }
```
Solução: Faremos uma análise apenas da ordem de grandeza do número de operações. As linhas 0, 1 e 9 são executadas uma vez só. As linhas 2, 3 e 7 são executadas O(n) vezes. As linhas 4 e 5 são executadas O(n²) vezes, pois trata-se de somar (n-1)+(n-2)+...+1, o que pode ser obtido usando-se a fórmula da soma de uma P.A. Finalmente, não dá para avaliar exatamente o número de vezes que a linha 6 será executada, pois depende dos dados, mas certamente não passará de O(n²).

Logo, a complexidade total é O(n²).
Suponha as seguintes declarações em C:
```
int i;
int v[10];
int *p;
```
Quais dos seguintes comandos estão corretos, quais dão erros de compilação, e quais dão erros de execução? Suponha que os comandos são executados na ordem dada, e que os que dão erro não afetam os outros.
```
1.      p = v;
2.      i = *v;
3.      p += 3;
4.      v = p - 2;
5.      *i = v[0];
6.      v[2] = p[1];
7.      p[7] = i;
8.      *(v + 1) = i;
9.      i = p + 2;
```
Solução:
1. Ok, tanto p como v são do tipo int *.
2. Ok, tanto i como *v são do tipo int. A expressão *v equivale a v[0].
3. Ok, o ponteiro p é avançado três posições. O compilador sabe que ele é um ponteiro para inteiros e portanto vai avançá-lo exatamente da quantidade de memória ocupada por três inteiros. Por exemplo, se um inteiro ocupa 4 bytes numa dada implementação, o ponteiro avançará 12 bytes.
4. Erro de compilação, pois v é constante e portanto não pode ter seu valor alterado. O lado esquerdo da atribuição está ok, e os tipos são compatíveis, mas dá erro pois v é constante.
5. Erro de compilação, pois *i não pode ser executado, já que i não é ponteiro.
6. Ok, ambos os lados são do tipo int. A expressão p[1] equivale a *(p+1).
7. Erro de execução, pois p[7] vai parar depois do final do vetor v. De resto, estaria ok.
8. Ok, a expressão *(v + 1) equivale a v[1].
9. Erro de compilação, pois i é int e p + 2 é int *.
Se p é int *, qual é o tipo de *p ? E de &p ?
Solução:
*p é int **.
&p é int.
Considere um tipo abstrato de dados Pilha que deve poder ser usado conforme o seguinte programa de teste:
```
Pilha p;

InicializaPilha(&p);
for(i=1; i<=10; i++) {
  if (Empilhou(&p, i)) {
    printf("Empilhou %d ok\n", i);
  }
}

while (!Vazia(&)) {
  if (Desempilhou(&p, &i)) {
    printf("%d\n", i);
  } else {
    printf("Erro ao desempilhar\n");
  }
}
LiberaPilha(&p);
```
Implemente esta estrutura de dados "pilha de inteiros" em C usando vetor. Depois, implemente esta mesma estrutura em C usando lista ligada.
Solução:
Veja aqui o programa teste testaPilha.c. Devem sair 10 mensagens empilhando os números de 1 a 10, depois os mesmos números na ordem inversa.

A implementação com vetor está aqui: pilha.h, pilha.c. Para compilá-la e testá-la, use:
```
gcc testePilha.c pilha.c -o testePilhaV
./testePilhaV
```
A implementação com lista ligada está aqui: pilha.h, pilha.c. Para compilá-la e testá-la, use:
```
gcc testePilha.c pilha.c -o testePilhaL
./testePilhaL
```
Implemente a estrutura de dados "fila de inteiros" em C usando vetor.
Implemente a estrutura de dados "fila de inteiros" em C usando lista ligada.
Implemente uma estrutura de dados "lista ligada" em C onde se possa tirar ou colocar inteiros na frente ou atrás.