MC102MN

Introdução a Algoritmos e programação de computadores

Aula XIV, structs e introdução a recursão

Quando fizemos o programa de processamento de dados, foi muito chato ter que ficar passando vários vetores diferentes para lá e para cá, um para cada atributo. Além disso, tínhamos que nos lembrar de ao trocar dois elementos de lugar trocar em todos os vetores. A linguagem C te dá uma ferramenta para resolver esse problema: structs.

Uma struct em C é um tipo de dados que você pode definir que contém várias variáveis dentro. Por exemplo, no caso daquele programa de processamento de dados, poderíamos representar um aluno como

struct aluno {
  int ra;
  double p1, p2, p3;
};
ou até como
struct aluno2 {
  int ra;
  double provas[3];
};

Isso define um tipo. Devemos declarar isso antes de main, no topo do programa. Depois podemos declarar uma variável dessa estrutura da seguinte forma:

struct aluno pedro;
podemos então atribuir os valores dos atributos:
pedro.ra = 123456;
pedro.p1 = 10;
pedro.p2 = 8.5
pedro.p3 = 5;

Podemos também guardar essas structs num vetor só

struct alunos[100];
alunos[0] = pedro;
alunos[1].ra = 654321;
etc

Quando temos um ponteiro para uma struct, o correto seria

struct aluno *pont = &pedro;
(*pont).ra = 321456;
mas como isso é esquisito de escrever C tem um operador próprio, que permite que você faça
pont->ra = 321456;

Processamento de dados com structs

Vamos ver então como fica o código do exercício de processamento de dados sem struct. Vamos usar a struct aluno acima. Como ficaria o main?

int main(int argc, char *argv[]) {
  struct aluno alunos[100];
  int nalunos = 0, op = 0;
  while (op != 5) {
    printf("(1) para inserir, (2) para remover, (3) para modificar p1, (4) para ver aluno, (5) para sair\n");
    scanf("%d", &op);
    switch(op) {
      case 1: nalunos = insere(alunos, nalunos); break;
      case 2: nalunos = retira(alunos, nalunos); break;
      case 3: modifica(alunos, nalunos); break;
      case 4: mostra(alunos, nalunos); break;
    }
  }
  return 0;
}

Antes de olhar para as funções vamos ver a busca:

int busca(struct aluno alunos[], int n, int ra) {
  int i;
  for (i = 0; i < n; ++i) {
     if (alunos[i].ra == ra) return i;
  }
  return -1;
}

Para inserir então

int insere(struct aluno alunos[], int nalunos) {
  struct aluno novo;
  scanf("%d %lf %lf %lf", &novo.ra, &novo.p1, &novo.p2, &novo.p3);
  alunos[nalunos] = novo;
  return nalunos+1;
}

Para remover

int retira(struct aluno alunos[], int nalunos) {
  int ra, i;
  scanf("%d", &r);
  i = busca(alunos, nalunos, ra);
  alunos[ra] = alunos[nalunos-1];
  return nalunos-1;
}

Para modificar a nota da p1

int modifica(struct aluno alunos[], int nalunos) {
  int ra, i;
  scanf("%d", &r);
  i = busca(alunos, nalunos, ra);
  scanf("%lf", &alunos[i].p1);
}

E para mostrar um aluno específico

int mostra(struct aluno alunos[], int nalunos) {
  int ra, i;
  scanf("%d", &r);
  i = busca(alunos, nalunos, ra);
  printf("ra: %d, p1: %lf, p2: %lf, p3: %lf\n", alunos[i].ra,
         alunos[i].p1, alunos[i].p2, alunos[i].p3);
}

E assim o programa fica bem mais simples.

Introdução a recursão

Em programação, lidamos frequentemente com algoritmos e problemas indutivos. Isso significa que boa parte do tempo nós podemos expressar a solução de um problema como sendo composta a partir da solução de partes desse problema. Por exemplo, a função fatorial

int fatorial(int x) {
  int i, f = 1;
  for (i = 1; i <= x; ++i) f *= i;
  return f;
}
obedece a seguinte propriedade:
 x! = x  *  (x-1)!
E nada nos impede de expressar isso naturalmente em C
int fatorial(int x) {
  if (x == 1) return 1;
  return x*fatorial(x-1);
}

Por que isso funciona?

Lembram que no teste de mesa cada vez que executamos uma função temos que criar uma tabela nova com todas as variáveis? É a mesma coisa quando executamos funções recursivas. Em C nada impede que uma função esteja várias vezes na "pilha de execução", que é como chamamos o conjunto de funções que estão sendo executadas a cada momento.

Por que isso é útil?

Às vezes algumas coisas são mais fáceis de pensar com recursão do que sem. Uma busca binária com recursão por exemplo deixa mais claro que metade do intervalo está sendo descartado a cada iteração:

int busca_bin(int v[], int elem, int a, int b) {
  int m = (a + b)/2;
  if (b < a) return -1;
  if (v[m] == elem) return m;
  if (v[m] < elem) return busca_bin(v, elem, m+1, b);
  return busca_bin(v, elem, a, m-1);
}

Sugestões

  • Fazer esse programa compilar e rodar
  • Modificar o programa para calcular a média dos alunos
  • Modificar o programa para mostrar todos os alunos
  • Escrever uma função recursiva para calcular o n-ésimo número de fibonacci

Author: Alexandre Tachard Passos <alexandre.tp@gmail.com>

Date: 2010-09-29 20:57:59 BRT

HTML generated by org-mode 6.21b in emacs 23