Estruturas de Dados Elementares

"A vida imita o vídeo,
Garotos inventam um novo inglês,
Vivendo num país sedento
Um momento de embriaguez."
—Somos Quem Podemos Ser, Engenheiros do Hawaii

Este é um resumo da primeira parte do

• capítulo 3 (Elementary Data Structures) do livro "Algorithms in C, Third Edition" de Robert Sedgewick e do
• capítulo 2 (Data Types in C) do livro "Programming Abstractions in C" de Eric Roberts.

Todos os programas foram extraídos desses livros (alguns foram ligeiramente simplificados).

Exercícios preliminares

1. O seguinte trecho de código promete determinar se é verdade que todos os componentes do vetor a[0..n-1] são positivos.

         i = 0;
         while (a[i] > 0 && i < n) i++;
         if (a[i] > 0) printf("Tudo positivo.");
         else printf("Nem tudo positivo.");
   

   Critique o código.

Funções e documentação

Esta seção dá exemplos dos conceitos de função, documentação e invariantes.  Também menciona o mecanismo include da inguagem C.  O material está no início da seção 3.1 (Building Blocks) do livro do Sedgewick, em particular no Program 3.1, p.73.

No programa abaixo, a função  lg  recebe um número inteiro positivo N e devolve o logaritmo de N na base 2 arredondado para baixo.  Esse número é conhecido como  piso ( log₂N ) .

#include <stdio.h> int lg (int); // A função main imprime uma tabela dos valores de lg(N) e N lg(N) // para N = 10^2, 10^3, ..., 10^6. // int main (void) { int i, N = 10; for (i = 1; i <= 6; i++) { N = 10 * N; printf("%7d %2d %9d\n", N, lg(N), N * lg(N)); } return 0; } // A função lg recebe um inteiro N > 0 // e devolve piso(log_2 N) // int lg (int N) { int i, n; i = 0; n = N; while (n > 1) { n = n / 2; ++i; } return i; }

n i 10 5 2 1 0 1 2 3

Aplique a função lg ao argumento N = 10, por exemplo.  A tabela registra os valores das variáveis no início de sucessivas iterações (o início de uma iteração fica imediatamente antes da comparação de n com 0):

Invariante: no começo de cada iteração temos

n = piso(N/2ⁱ) .

(A propósito, o comentário   /* n = N/2^i */   logo depois do while seria muito útil para ajudar o leitor a entender o que está acontecendo.)  No começo da última iteração, é fácil verificar que temos n = 1, donde  1 < N/2ⁱ < 2,  donde  2ⁱ < N < 2ⁱ⁺¹,  donde  i < log₂ N < i+1.  Portanto, a função lg de fato faz o que promete fazer.

O programa acima também serve para ilustrar o tipo-de-dados int.

Exercícios

2. O que fazem as seguintes funções? Escreva a(s) invariante(s).

   int lg1 (int N) {  
       int i = 0, n;
       for (n = N; n > 1; n = n/2) 
          ++i;
       return i; }
   
   
   int lg2 (int N) {  
       int i = 0, n = 1;
       while (n <= N) {
          n = 2 * n;
          ++i;
       }
       return i - 1; }
   
   
   int lg3 (int N) {  
       int i = 0, n;
       for (n = 2; n <= N; n *= 2) 
          i++;
       return i; }
   
   

3. O que faz a função abaixo? Escreva a(s) invariante(s).

   int lg4 (int N) {  
       int i = 0, n = 1;
       while (n < N) {
          n = 2 * n;
          ++i;
       }
       return i;    
   }
   
   

4. A biblioteca math contém a função  floor,  que recebe um número real x e devolve piso(x), ou seja, o maior inteiro que seja menor que ou igual a x.  Analogamente,  ceil(x)  é o menor inteiro que seja maior que ou igual a x.  O arquivo-interface para a biblioteca math é math.h.   Suponha agora que x é uma variável do tipo float e diga quais das seguinte afirmações são verdadeiras.

   float(x) == (int)x / 2
   ceil(x) == (int)x / 2 + 1
   

   Escreva uma função que faça a mesma coisa que float e outra que faça a mesma coisa que ceil.

Moldes e números aleatórios

Esta seção ilustra os conceitos de tipo-de-dados e molde (= cast). Também usa a função rand da biblioteca padrão stdlib.  A seção foi baseada no Program 3.2, p.75, do livro do Sedgewick.

#include <stdio.h> #include <math.h> #include <stdlib.h> // Este programa abaixo calcula a média e o desvio padrão // de N números inteiros aleatórios. int main (void) { int i, N, x; float m1, m2; m1 = m2 = 0.0; printf("\nValor de N: "); scanf("%d", &N); for (i = 0; i < N; i++) { x = rand(); m1 += ((float)x) / N; m2 += ((float)x * x) / N; } printf(" Average: %f\n", m1); printf("Std. deviation: %f\n", sqrt(m2 - m1 * m1)); return 0; }

Qual o invariante do processo iterativo no programa acima? Fácil: no começo de cada iteração, m1 é a soma dos i primeiros números aleatórios dividida por N. Analogamente, m2 é a soma dos quadrados dos i primeiros números aleatórios dividida por N.

Exercícios

5. No programa acima, o que acontece se a linha "#include <stdlib.h>" for trocada pela linha abaixo?

   int rand(void);
   

6. Por que não fazer o cálculo da média como abaixo?

   int soma;
   for (i = 0; i < N; i++) {
       x = rand();
       soma += x;
   }
   m1 = (float)x / N; 
   

Veja minhas notas de aula sobre caracteres, strings e inteiros.

Endereços e ponteiros

Esta seção é baseada nas seções 2.2-2.3, p.56-65, do livro do Roberts.  Ela introduz os conceitos de endereço (= address) e ponteiro (= pointer).  Em particular, a seção introduz os operadores

&   ("endereço de"  ou  "address-of")   e
*   ("conteúdo de"  ou  "dereference").

// Function SolveQuadratic. // Usage: SolveQuadratic(a, b, c, &x1, &x2); // ---------------------------------------- // This function solves the quadratic equation ax^2 + bx + c = 0. // If the equation has no real solution, the function returns 0. // Otherwise, the function returns 1 and places the solutions // in x1 and x2. int SolveQuadratic (float a, float b, float c, float *px1, float *px2) { float discr, sqrtDiscr; discr = b * b - 4 * a * c; if (discr < 0) return 0; sqrtDiscr = sqrt(discr); if (a == 0) return 0; *px1 = (-b + sqrtDiscr) / (2 * a); *px2 = (-b - sqrtDiscr) / (2 * a); return 1; }

Exercícios

7. Escreva um programa que leia números A, B e C e imprima as soluções da equação Ax²+Bx+C = 0. O seu programa deve usar a função SolveQuadratic definida acima.  Escreva também uma pequena função que verifique se as soluções produzidas por SolveQuadratic estão corretas. O programa principal (main) deve usar essa função de teste.

8. [Roberts #17, p.96]  Qual o efeito do segmento de código abaixo?

   int v1, v2, *p1, *p2;
   v1 = 10; v2 = 25;
   p1 = &v1; p2 = &v2;
   *p1 += *p2;
   p2 = p1;
   *p2 = *p1 + *p2;
   

9. O que faz a função Soma abaixo?

   int SomaVetor(int *p, int n) {
       int i, s = 0;
       for (i = 0; i < n; i++) {
          s += *p;
          p++; 
       }
       return s; }
   

   Reescreva a função de modo que ela fique mais de acordo com o protótipo

   int SomaVetor(int vetor[], int n) ;
   

10. Qual o efeito do seguinte trecho de programa?

    int x;
    scanf("%d %d", &x, x);
    

Vetores (= arrays)

Esta seção introduz o conceito de vetor.  Ela corresponde à primeira parte da seção 3.2 (Arrays) do livro do Sedgewick. O programa abaixo é essencialmente o mesmo que Program 3.5, p.84, no Sedgewick.

#include <stdio.h> #define N 10000 // Este programa imprime uma lista de todos os // números primos menores que N. // O método usado é o do crivo de Eratóstenes // (veja Program 3.5, p.84, no Sedgewick). int main (void) { int i, j, a[N]; for (i = 2; i < N; i++) a[i] = 1; for (i = 2; i < N; i++) if (a[i] == 1) { printf("%5d\n", i); for (j = i; i*j < N; j++) a[i*j] = 0; } return 0; }

É claro que cada elemento do vetor a[2..N-1] vale 0 ou 1.  Podemos então formular o invariante principal do programa assim: no começo de cada iteração do segundo for, para cada h em 2..N-1,

a[h] == 1 se e somente se h não é divisível por nenhum dos números do intervalo 2..i-1.

Portanto, para h=2..i-1, o número h é primo se e só se a[h]==1.

Exercícios

11. Por que j começa em i e não em 2? 

12. Quanto tempo o programa consome em função de N?

13. [Sedg 3.15]  Que acontece se o programa for trocado pelo seguinte?

        for (i = 2; i < N; i++) a[i] = 1;
        for (i = 2; i < N; i++)
           for (j = i; i*j < N; j++) a[i*j] = 0;
        for (i = 2; i < N; i++)
           if (a[i] == 1) 
              printf("%4d ", i);
    

    Faça testes para comparar o consumo de tempo da versão original com o desta nova versão.

14. [Sedg 3.14]  Use o crivo de Eratóstenes para traçar um gráfico (ou histograma) da quantidade de número de primos menores N para N variando de 1 até 1000,

15. [Sedg 3.11] Diga (sem usar o computador) qual o conteúdo do vetor a depois dos seguintes comandos?

        int a[99];
        for (i = 0; i < 99; ++i) a[i] = 98 - i;
        for (i = 0; i < 99; ++i) a[i] = a[a[i]];
    

16. Qual o conteúdo do vetor a depois dos seguintes comandos?

        int a[99];
        for (i = 0; i < 99; ++i) *(a+i) = 98 - i;
    

17. Qual a diferença entre as duas expressões C abaixo?

        for (i = 0; i < 10; ++i) . . . 
        for (i = 0; i < 10; i++) . . . 
    

18. Qual a diferença entre as três expressões C abaixo?

        while (i <= n && a[++i] < 0) {}
        while (i <= n && a[i++] < 0) {}
        while (i <= n && a[i] < 0) ++i ;
    

19. Problema: Dado um inteiro x e um vetor a[0..n-1], encontrar j tal que a[j] == x. As funções abaixo prometem resolver o problema. Discuta. Depois, escreva a sua própria solução para o problema.

    int func1 (int x, int a[]) { 
       int achou = 0, j = 0;
       while (j < n && !achou) {
           if (a[j] == x) achou = 1;
           else j++; }
       if (!achou) j = 0;
       return j; }
    

    int func2(int x, int a[]) {
       int j, k;
       for (k = 0; k < n; k++) 
          if (a[k] == x) j = k;
       return j; }
    

20. Um segmento horizontal de um vetor a[0..n-1] é um subvetor a[i..k] tal que  a[i] == a[i+1] ==  . . .  == a[k].  O comprimento de um tal subvetor é k-i+1. Um segmento horizontal é máximo se não existe segmento horizontal de comprimento maior.  Escreva uma função que receba um vetor inteiro não vazio a[0..n-1] e devolva o comprimento de um segmento horizontal máximo no vetor. Procure escrever uma função simples e limpa.

Alocação dinâmica de memória

Esta seção introduz o conceito de alocação dinâmica de memória e a função malloc da biblioteca padrão stdlib.  Também introduz o operador sizeof. O programa abaixo é uma cópia do Program 3.6, p.85, do livro do Sedgewick.

#include <stdlib.h> #include <stdio.h> // Este programa imprime uma lista de todos os números primos // menores que N. // O método usado é o do crivo de Eratóstenes. int main (void) { int i, j, N; int *a; printf("\nValor de N: "); scanf("%d", &N); a = malloc(N * sizeof (int)); for (i = 2; i < N; i++) a[i] = 1; for (i = 2; i < N; i++) if (a[i] == 1) { printf("%5d\n", i); for (j = i; i*j < N; j++) a[i*j] = 0; } return 0; }

Há uma relação estreita entre ponteiros, endereços e vetores porque os elementos de um vetor têm endereços consecutivos.  Assim, no exemplo acima, as expressões

a[i]      e      *(a+i)

são equivalentes.

Exercícios

21. [Sedg 3.13, p.89]  Escreva uma função que diga quantos números primos são estritamente menores que N.

Caras e coroas

O programa abaixo é uma cópia do Program 3.7, p.87, de Sedgewick.

#include <stdlib.h> int heads (void); // Este programa faz M experimentos. Cada experimento consiste em // contar o número de caras (= heads) em N jogadas de uma moeda. // O programa imprime um histograma dos resultados. // int main (void) { int i, j, cnt, N, M; int *f; printf("\nValor de N: "); scanf("%d", &N); printf("\nValor de M: "); scanf("%d", &M); f = malloc((N+1) * sizeof (int)); if (a == NULL) { printf("A memória está esgotada!\n"); return 1; } for (j = 0; j <= N; j++) f[j] = 0; for (i = 0; i < M; i++) { cnt = 0; for (j = 0; j < N; j++) if (heads()) cnt++; f[cnt]++; } for (j = 0; j <= N; j++) { printf("%2d ", j); for (i = 0; i < f[j]; i += 10) printf("*"); printf("\n"); } free(f); return 0; } // A função heads devolve um elemento aleatório do conjunto {0,1}. // int heads (void) { return rand() <= RAND_MAX / 2; }

[Sedgewick diz "< RAND_MAX/2",  mas eu acho que isso está errado.  Mesmo "<= RAND_MAX/2" só está certo porque RAND_MAX é ímpar.  A propósito, veja a aula sobre números aleatórios.]

Pontos no plano

Esta seção introduz o conceito de registro (= struct)  e a idéia de tipo-de-dados criado pelo usuário (typedef).  Esse material está na parte final da seção 3.2 do livro do Sedgewick.

typedef struct { float x; float y; } point; // Esta função devolve a distância entre os points A e B. // O tipo point é um ponto no plano: A.x e A.y são as // coordenadas cartesianas do point A. float distance (point A, point B) { float dx, dy; dx = A.x - B.x; dy = A.y - B.y; return sqrt(dx * dx + dy * dy); }

O programa abaixo gera N pontos no quadrado unitário fechado  [0,1]×[0,1]  e em seguida conta quantos pares de pontos estão à distância menor que d um do outro.  Esse material está em Programs 3.3, 3.4, 3.8, p.79-88, do livro do Sedgewick.

#include <math.h> #include <stdio.h> #include <stdlib.h> typedef struct { float x; float y; } point; float distance (point A, point B) { float dx = A.x - B.x, dy = A.y - B.y; return sqrt(dx * dx + dy * dy); } float randFloat (void) { return 1.0 * rand() / RAND_MAX; } int main (void) { float d, int i, j, cnt, N; point *a; printf("\nValor de N: "); scanf("%d", &N); printf("\nValor de d: "); scanf("%f", &d); a = malloc(N * sizeof (point)); // Deveria ter verificado se a é NULL cnt = 0; for (i = 0; i < N; i++) { a[i].x = randFloat(); a[i].y = randFloat(); } for (i = 0; i < N; i++) for (j = i+1; j < N; j++) if (distance(a[i], a[j]) < d) cnt++; printf("%d pares de pontos mais próximos que %f\n", cnt, d); free(a); return 0; }

Consumo de tempo: proporcional a N².  Assim, quando N dobra, o consumo de tempo é multiplicado por 4.  Quando N é multiplicado por 10, o consumo de tempo é multiplicado por 100.

Exercícios

22. Escreva uma função que decida se dois objetos do tipo point são iguais.

23. [Sedg 3.22]  Modifique o programa para que ele imprima as coordenadas de um par de pontos mais próximos.

24. [Sedg 3.23]  Gere N pontos aleatórios em um cubo unitário. Calcule o número de pontos que estejam à distância menor que d um do outro.

25. Qual o valor de k no fim do seguinte trecho de programa?

    k = 0;
    for (i = 2; i < n-2; i++)
        for (j = n; j > i; j--)
            k++;
    

26. [Sedg 3.6]  Defina uma struct que seja apropriada para representar cartas de baralho.