Algoritmos e Estruturas de Dados I

MAC0121 | Aulas | Tarefas | Alunos | Notas

Aula 18:  Sobre as tarefas E, F e G

Strings: vazia versus NULL

• O que é uma string vazia?
• Resposta certa:  strlen(s) == 0
• Resposta errada:  s == NULL, pois nesse caso s não existe e strlen(s) não faz sentido

Erro básico na tarefa E (busca palavras)

• Função de busca binária:

  int buscaBinaria (char *pal, int n, char **dic) {
      int e = 0, m, d = n-1;
      while (e <= d) { 
          m = (e + d)/2;
          if (strcmp (dic[m], pal) <= 0) e = m + 1;
          else d = m - 1;
      }
      return e;
  }
  

• Documentação errada:

  // Recebe uma palavra, o tamanho de um vetor de strings e o
  // próprio vetor para buscar a palavra recebida e devolve o
  // índice mais próximo a essa palavra.
  int buscaBinaria (char *pal, int n, char **dic) ...
  

• A documentação errada levou o cliente ao erro:

  i = buscaBinaria (pal, n, dic);
  printf ("palavra:           %s\n", pal);      // exemplo "dd"
  printf ("anterior ou igual: %s\n", dic[i]);   // exemplo "ddd"
  printf ("seguinte:          %s\n", dic[i+1]); // exemplo "eee"
  

• Documentação certa:

  // Recebe uma palavra pal e um vetor dic[0..n-1].
  // Devolve índice e tal que dic[e-1] <= pal < dic[e].
  int buscaBinaria (char *pal, int n, char **dic) ...
  

  Como sei que <= fica do lado esquerdo?
  Resposta: quando strcmp (dic[m], pal) é zero, o código reajusta e, não d.

Sobre a tarefa F (merge múltiplo)

• fscanf devolve o número de itens lidos (ou EOF):

  i = fscanf (arq, "%d %d %d", a, b, c);
  if (i < 3) ....
  if (i == EOF) ....
  

• Leia o manual:

  PF$ man fscanf
  NAME
    scanf, fscanf, sscanf, vscanf, vsscanf, vfscanf - input format conversion
  SYNOPSIS
  ...
  

Sobre a tarefa G (algoritmos de ordenação)

• Biblioteca de funções
• Funções públicas e funções privadas
• Exemplo de função privada (invisível fora do módulo):

  // Rearranja v[p..r] em ordem crescente.
  static void qcksrt (int v[], int p, int r) {
     . . .
  }
  

• Exemplo de função pública (documentação é um manual de uso):

  // Rearranja v[0..n-1] em ordem crescente.
  // Consumo de tempo: em geral, proporcional a n log n.
  // No pior caso (por exemplo, v ordenado): proporcional a n^2.
  void quicksort (int *v, int n) {
     qcksrt (v, 0, n-1);
  }
  

• Falta de documentação induziu muitos ao erro:

     qcksrt (v, 0, n);
  

Código ruim na tarefa G (algoritmos de ordenação)

• Função de verificação muito feia:

  void verificaOrdem (int *v, int n) {
      int anterior, i, ordenado = TRUE;
      if (n > 1) {
          anterior = v[0];
          for (i = 1; i < n && ordenado; i++) {
              if (anterior > v[i]) 
                  ordenado = FALSE;
              anterior = v[i];
          }
      }
      if (ordenado) printf ("Ordenado\n");
      else          printf ("Nao Ordenado\n");
  }
  

• Péssimo uso do switch:

     for (i = 1; i <= 4; i++) {
        switch (i) {
        case 1: insercao (v, n);
                break;
        case 2: mergesort (v, n);
                break;
        case 3: quicksort (v, n);
                break;
        case 4: heapsort (v, n);
                break;
        }
     }
  

Documentação errada

• Você sabe o que está errado aqui?

  // Recebe um vetor de arquivos
  // e o tamanho desse vetor, ...
  //
  int merge (FILE **arq, int n, FILE *out) {
  

• Você sabe o que está errado aqui?

  // Recebe um vetor de tamanho n de arquivos
  // e um inteiro i, no arquivo correspondente
  // a arq[i] é lido seu próximo valor ...
  //
  container ppp (FILE **arq, int num) {
  

• Você sabe onde estão os erros?

  // Recebe um vetor v[0...n-1] fora de ordem
  // e o tamanho (int n) do vetor.
  // ...
  //
  void mergesort (int v[], int n);
  

• Você sabe onde estão os erros?

  // Essa função inclui chamada para duas outras 
  // responsáveis por dividir e intercalar o vetor 
  // e os sub vetores resultantes das divisões.
  //
  void mergesort (int n, int *v);
  

Gerador de números aleatórios (tarefa G)

• veja Números aleatórios
• aleatório versus pseudoaleatório
• rand() produz um número (pseudo)aleatório em 0..RAND_MAX
• cada número é gerado a partir do anterior
• onde isso começa?
• srand() inicializa o gerador de números aleatórios:

      v = malloc (n * sizeof (int));
      srand (55);
      for (i = 0; i < n; ++i)  v[i] = rand ();
  

• na tarefa G, é melhor não usar srand()