Algoritmos e Estruturas de Dados I

MAC0121 | Aulas | Tarefas | Alunos | Notas

Aula 10:  Observações diversas (sobre a prova 1 e outros assuntos)

Aprenda com as tarefas

• Não prejudique sua nota com erros de layout, de indentação, de compilação!
• Muitos alunos fizeram uma função main() grande demais!
• Estude minha solução!
• Eu sei a resposta, mas não consigo escrever claramente.
  Dica: Escreva sentenças curtas, simples, afirmativas.

Vetor de strings

• Como na tarefa D:      char **dicionario;
• Não é bem assim:

  "abacate"

  "banana"

  "laranja"

  "uva"

• É mais assim
  (falta desenhar as flechas):

  •

  •

  •

  •

  "abacate"   "banana"   "laranja"   "uva"

Índices de vetores

• C não verifica se o índice de um vetor é válido. Cabe ao programador evitar bobagens.
• Exemplo: está tudo certo, mas pode produzir erro durante a execução:

     v = malloc (99 * sizeof (int));
     v[111] = 0;
  

Aritmética de ponteiros

• Exemplo: Imprime um vetor de caracteres v[0..n-1]:

  void imprime (char *v, int n) {
     char *c;
     for (c = v; c < v + n; c++)
        printf ("%c", *c);
  }
  

Redimensionamento / realocação de vetor

• Redimensionamento (e a função realloc) criam a ilusão de que um novo espaço é acrescentado no final do vetor original.

  v = malloc (n * sizeof (int));
  ...
  w = realloc (v, 2*n * sizeof (int));
  

• Na verdade, em geral, um novo bloco de memória é alocado (longe do original) e o conteúdo do vetor original é copiado para lá.
• Portanto, mo pior caso, realloc consome n unidades de tempo.

Dois tipos de alocação de variáveis

• Variáveis locais (= automáticas)  versus  variáveis alocadas por malloc.

  int funcao (void) {
     int local;
     int p;
     p = malloc (10 * sizeof (int)); 
     // p aponta um vetor não-local
     ...
  }
  

• Tempo de vida das variáveis.
• Variáveis locais:  vida curta.   Variáveis alocadas por malloc: vida longa.
• Locais desaparecem no fim da função. Alocadas por malloc não desaparecem.
• Área stack da memória: reservada para variáveis locais.
• Área heap da memória: reservada para malloc.
• Exemplo: promete acrescentar uma célula-cabeça à lista encadeada lista e devolver o endereço da nova lista. Onde está o erro?

  celula *acrescentaCabeca (celula *lista) {
     celula cabeca;
     cabeca.prox = lista;
     return &cabeca;
  }
  

• Exemplo: promete devolver um vetor com os 3 primeiros primos maiores que 1000 e devolver o endereço da nova lista. Onde está o erro?

  int *primos (void) {
     int v[3];
     v[0] = 1009; v[1] = 1013; v[2] = 1019;
     return v;
  }
  

Invariantes e funções recursivas

Busca binária

• O que é busca binária.
• Veja figura  e  invariante.
• Versão mais sofisticada da busca binária.
• Tarefa E: busca palavras em um texto (para 21/9, 2a-feira, até 23h55m).

Cliente / interface / implementação

• Ideia poderosa:  separar o cliente do implementador (veja humor)
• Interface:  contrato entre cliente e implementador
  • também conhecida como API
  • diz  o que  cada função faz
  • fica num arquivo xxx.h
• Biblioteca: coleção de funções (= ferramentas)
• Interface da biblioteca
• Exemplo: biblioteca string e sua interface string.h
• Muitos programas consistem em vários arquivos: um contém main() e outros contêm bibliotecas de funções. Cada arquivo xxx.c é um módulo do programa.