Curso de C

Gabarito de Lista de Exercícios

Aula 9: Tipos de Dados Avançados

Clique aqui para acessar a Lista 9

 
Exercício 1: Página cA60.html
Enunciado:
Refaça o exemplo desta página, mas ao invés de trabalhar com um vetor de inteiros, use um vetor de strings (ou uma matriz de char, como você preferir). Faça leituras e apresente os resultados na tela.

Solução:
#include <stdio.h>
#define TAM 5
void main ()
{
/* Declarando um vetor de apontadores */
char *mat[TAM];
int i,j;
for (i=0; i<TAM; i++)
  {
  mat[i]=(char *) calloc(80, sizeof(char));
          /* 80 = Numeros de caracteres por linha */
  if (!mat)
        {
        printf ("** Erro: Memoria Insuficiente **");
        for(j=0; j < (i+1); j++)
          free(mat[j]);
        exit();
        }
  }
printf("\nEntre com %d Frases:\n\n", TAM);
for(i=0; i<TAM; i++)
  gets(mat[i]);
for(i=0; i<TAM; i++)
  printf("%s\n", mat[i]);
for(j=0; j<TAM; j++)
  free(mat[j]);
}
 

Exercício 2: Página cA70.html
Enunciado:
Refaça o programa de multiplicação de matrizes usando alocação dinâmica de memória para as matrizes. Avalie as principais vantagens desta forma de gerenciamento de memória neste caso.

Solução:
/* --------------------------------------------------------
   Multiplicacao de Matrizes: Versao 3 --------------------
   Usando alocacao dinamica de memoria
   Multiplica as matrizes 1 e 2, colocando o resultado na
   matriz 3
   -------------------------------------------------------- */
#include <stdio.h>
#define p_acesso(A,B,C,D) (A+(B*C)+D)
#define acesso(A,B,C,D) (*p_acesso(A,B,C,D))
void main()
{
int *mat1,  /* Matrizes 1 e 2 serao lidas */
    *mat2,
    *mat3;  /* Matriz 3: Resultado da multiplicacao */

int linha1, coluna1;   /* Dimensoes das matrizes */
int linha2, coluna2;
int linha3, coluna3;
int i, j, t, erro=0;

printf("\n\n-------- Multiplicacao de Matrizes: Versao 3:\n");
printf("                Alocacao Dinamica de Memoria\n");
printf("------------------------------------------------\n");

/* Le e compara as dimensoes das matrizes.
   So abandona o loop se as dimensoes forem validas
   Atencao aa condicao...                           */
do
{
  printf("\nDimensoes da matriz 1: ");
  scanf("%d%d", &linha1, &coluna1);
  printf("\nDimensoes da matriz 2: ");
  scanf("%d%d", &linha2, &coluna2);
  if ( coluna1 != linha2 )
    printf("\nDimensoes Invalidas! Tente de novo..\n");
} while ( coluna1 != linha2 );

/* Dimensoes da matriz de resposta: */
linha3 = linha1;
coluna3 = coluna2;

/* Aloca a memoria para as matrizes: */
if ((mat1 = (int *) calloc(linha1*coluna1, sizeof(int))) == NULL) erro = 1;
if ((mat2 = (int *) calloc(linha2*coluna2, sizeof(int))) == NULL) erro = 1;
if ((mat3 = (int *) calloc(linha3*coluna3, sizeof(int))) == NULL) erro = 1;
if (erro)
  {
  printf("\n Memoria Insuficiente! Abortando..\n");
  exit(1);
  }

/* Le a Matriz 1: */
printf("\n\nDigite a Matriz 1:\n");
for (i = 0; i < linha1; i++)               /* Linha 49 */
  {
  printf("\nlinha %d: %d elemento(s)\n", i+1, coluna1);
  for (j=0; j<coluna1; j++)
    scanf("%d", p_acesso(mat1,i,linha1,j));
  }

/* Le a Matriz 2: */
printf("\n\nDigite a Matriz 2:\n");
for (i = 0; i < linha2; i++)
  {
  printf("\nlinha %d: %d elemento(s)\n", i+1, coluna2);
  for (j=0; j<coluna2; j++)
    scanf("%d", p_acesso(mat2,i,linha2,j));
  }

/* Imprime as Matrizes Lidas... */
printf("\n\n==> Matriz 1 :\n");
for (i = 0; i < linha1; i++)               /* Linha 70 */
  {
  for (j=0; j<coluna1; j++)
    printf("%d\t", acesso(mat1,i,linha1,j));
  printf("\n");
  }

printf("\n\n==> Matriz 2 :\n");
for (i = 0; i < linha2; i++)
  {
  for (j=0; j<coluna2; j++)
    printf("%d\t", acesso(mat2,i,linha2,j));
  printf("\n");
  }

/* Calculo da Matriz resposta, segundo o algoritmo apresentado
na lista de exercicios:
----------------------------------------------------------*/
/* ------- Primeiro e preciso iniciar a matriz com zeros..*/
for (i=0; i<linha3; i++)
  for (j=0; j<coluna3; j++)
    acesso(mat3,i,linha3,j) = 0;

/* --------------------- Multiplicacao..*/
for(i=0; i< linha3; i++)
  for(j=0; j< coluna3; j++)
    for(t=0; t< linha2; t++)   /* linha2, que e igual a coluna1.. */
      acesso(mat3,i,linha3,j) += acesso(mat1,i,linha1,t)*acesso(mat2,t,linha2,j);

/* ------------- Imprime a Matriz Calculada... */
printf("\n\n==> Matriz 3 :\n");
for (i = 0; i < linha3; i++)
  {
  for (j=0; j<coluna3; j++)
    printf("%d\t", acesso(mat3,i,linha3,j));
  printf("\n");
  }
free(mat1);
free(mat2);
free(mat3);
}
 
Comentários:
Há vários comentários a se fazer neste programa. Vamos tentar enumerar alguns:
- O tamanho do programa:
É um programa grande; possivelmente algum erro tenha passado desapercebido ou não tenha sido identificado. Acontece em programas quando o número de linhas começa a aumentar muito.
- O uso de macros:
Foram definidas duas macros: acesso e p-acesso. A macro p_acesso usa como parâmetro a matriz desejada, a posição [i][j] e o tamanho da linha. Em tempo de compilação, ela é substituída por uma expressão que retornará o ponteiro para a posição desejada. Isto é feito usando aritmética de ponteiros. A macro acesso chama p_acesso, e é substituida por uma expressão atraves da qual podemos acessar o valor da matriz na posição desejada. O uso de macros aqui encapsula toda a aritmética que seria necessária para os ponteiros.
- A otimizacão: O uso de alocação dinâmica de memória.
A versão anterior (sem alocação dinâmica) tinha dois problemas: O primeiro era alocar 3 matrizes 10X10 ainda que todas as matrizes manipuladas fossem bem pequenas (tipo 3X3). O uso da memória é bastante irracional desta forma. Este problema foi resolvido com a alocação dinâmica de memória.
O outro problema era o tamanho limitado das matrizes. Não creio que seria o caso neste programa simples, mas se você quisesse fazer um programa que trabalhasse com matrizes de até 100X100, seria necessário declarar matrizes 100X100 sempre, ainda que fosse uma vez ou outra que você as usasse.
- O único incoveniente do uso de ponteiros e alocação dinâmica de memória é a complexidade do programa, que aumenta em muito. E isto é muito ruim. Para que o seu código se torne claro, e necessário que você gaste maior tempo em identação, comentários e use nomes mais instintivos.

 

Exercícios de Fixação:

Exercício 1:
Considerando o conceito e finalidade dos modificadores de tipo, relacione as afirmativas com as palavras reservadas correspondentes (todas as afirmativas devem ser preenchidas com o número relacionado ao modificador correspondente, e existe pelo menos uma afirmativa para cada modificador):
   (1)const        (3)extern       (5)register     (7)void
   (2)volatile     (4)static       (6)auto         (8)enum

( 1 ) informa ao compilador que o valor da variável não pode ser alterado por nenhum comando do programa, mas que pode ser inicializado
( 8 ) associa valores inteiros a uma lista de constantes especificadas
( 7 ) informa ao compilador que nenhum valor será devolvido pela função
( 2 ) informa ao compilador que a variável pode ser modificada por algum evento que não está sob o controle do programa
( 3 ) avisa ao compilador que as variáveis que o seguem já foram declaradas em outro lugar
( 4 ) torna a variável permanente, mantendo seu valor entre chamadas
( 1 ) muito utilizada em ROM (Read-Only-Memory, memória só de leitura)
( 8 ) cria tipos compostos de uma lista de nomes constantes
( 4 ) útil ao escrever funções generalizadas e funções de biblioteca que podem ser usadas por outros programadores, pois permite esconder porções do programa de outras partes do código, evitando assim o uso de variável global
( 7 ) permite criar apontadores genéricos (que apontam para qualquer tipo)
( 1 ) quando apontadores forem passados para a função, garante que nenhum código na função poderá modificar os objetos apontados
( 5 ) armazena o valor da variável em um registrador da CPU, acelerando operações
( 6 ) usada para declarar variáveis locais em contraposição as globais, mas muito pouco usada por já ser o padrão (default)
( 2 ) avisa ao compilador que a variável em questão sera largamente usada e deve permanecer acessível da forma mais eficiente possível
( 3 ) permite ao compilador conhecer a variável sem criar armazenamento para ela novamente em outro modulo
 

Exercício 2:
Faça um programa que leia uma matriz de pontos flutuantes e a copie em outra área de memória. O programa deverá primeiramente perguntar ao usuário sobre a dimensão da matriz, e alocar a memória. Em seguida deverá ler a matriz (via teclado ou via arquivo) e *copiá-la em outra área de memória. No final apresentar o resultado na tela.
*Existem dois caminhos para se copiar a matriz:
- Fazer um loop que copie cada posição;
- Usar a função memcpy (de string.h), que copia o conteúdo de uma área de memória para uma determinada posição. Veja parte do conteúdo do Manual de Linux para programadores, retirado de um mail desta semana do Cesar Augusto:

MEMCPY(3)           Linux Programmer's Manual           MEMCPY(3)
NAME
       memcpy - copy memory área
SYNOPSIS
       #include <string.h>
       void *memcpy(void *dest, const void *src, size_t n);
DESCRIPTION
       The  memcpy() function copies n bytes from memory área src
       to memory área dest.  The memory areas  may  not  overlap.
       Use memmove(3) if the memory areas do overlap.
RETURN VALUE
       The memcpy() function returns a pointer to dest.

Solução:
#include <stdio.h>
#define TAM 3
void main()
{
float mat[TAM][TAM], copia[TAM][TAM];
int i,j;
printf("\nEntre com os valores da matriz:");
for (i=0; i<TAM; i++)
  {
  printf("\nLinha %d (%d elementos): ", i+1, TAM);
  for (j=0; j<TAM; j++)
    scanf("%f", &mat[i][j]);
  }
memcpy(copia, mat, TAM*TAM*sizeof(float));
printf("\nMatriz copiada:\n");
for (i=0; i<TAM; i++)
  {
  for (j=0; j<TAM; j++)
    printf("%10.2f", copia[i][j]);
  printf("\n");
  }
}
 

DESAFIO:

Jogo da Velha:
Simule um "jogo da velha" simples, que utiliza uma matriz 3x3 alocada dinamicamente (semelhante ao exemplo apresentado no curso), contendo os símbolos 'X' e 'O' para marcações. Deverão ser definidas as seguintes funções:
- cria_matriz: aloca e inicializa a matriz com brancos;
- verifica_vencedor: verifica se ha' um vencedor (linhas, colunas ou diagonais preenchidas com o mesmo símbolo);
- mostra_matriz: imprime a matriz na tela;
- obtem_jogada_usuario: obtém a jogada do usuário;
- obtem_jogada_computador: obtém a jogada do computador;
Observações:
- o programa principal deverá inicializar a matriz e entrar em um laço que mostra a matriz, obtém a jogada do usuário, verifica se há vencedor, obtém a jogada do computador e verifica novamente se há vencedor. Ao final, devera' fornecer a matriz resultante e a identificação do ganhador.
- a jogada do computador devera' buscar a primeira posição vazia da matriz e lá colocar o símbolo correspondente ('X' ou 'O').
- este programa não justificaria uma alocação dinâmica, visto que o tamanho da matriz e' previamente conhecido. Sua utilização foi solicitada apenas como exercício.

Solução:
#include <stdio.h>
#include <stdlib.h>

char **matriz; /* matriz do jogo, a ser alocada dinamicamente */
char verifica_vencedor(void);
void cria_matriz(void);
void libera_matriz(void);
void obtem_jogada_usuario (void);
void obtem_jogada_computador(void);
void mostra_matriz(void);

void main(void)
{
    char resp;
    printf ("\n          *** JOGO DA VELHA ***\n\n");
    printf ("Voce estara' jogando contra o computador\n");
    resp = ' ';
    cria_matriz();
    do {
     mostra_matriz();
     obtem_jogada_usuario();
     resp = verifica_vencedor(); /* verifica se ha' vencedor */
     if (resp != ' ') break;     /* houve vencedor */
     obtem_jogada_computador();
     resp = verifica_vencedor(); /* verifica se ha' vencedor */
    } while (resp == ' ');
    if (resp == 'X')
     printf ("\n** Parabens! Voce ganhou! **\n");
    else
     printf ("\n** Eu ganhei! **\n");
    mostra_matriz();                /* mostra as posicoes finais */
    libera_matriz();
}

/* inicializa a matriz */
void cria_matriz(void)
{
  int i, j;
  matriz = (char **) calloc (3, sizeof(char *));
  if (matriz == NULL) {
     printf ("*** Erro de alocacao da matriz ***\n");;
     }
  /* alocando as colunas da matriz */
  for ( i=0; i<3; i++ ) {
      matriz[i] = (char *) calloc (3, sizeof(char));
      if (matriz[i] == NULL) {
     printf ("*** Erro de alocacao da matriz ***\n");
     }
      }
  for (i=0; i<3; i++)
      for (j=0; j<3; j++)
        matriz[i][j] = ' ';
}
/* libera a matriz */
void libera_matriz(void)
{
  int i;
  /* liberando as linhas da matriz */
  for (i=0; i<3; i++) free (matriz[i]);
  /* liberando a matriz */
  free (matriz);
}
/* obtem a sua jogada */
void obtem_jogada_usuario(void)
{
    int x, y;
    printf ("Entre com as coordenadas para o X (lin,col): ");
    scanf ("%d,%d", &x, &y);
    x--; y--;
    if (matriz[x][y] != ' ') {
       printf ("Posicao invalida, tente novamente\n");
       obtem_jogada_usuario();
    }
    else matriz[x][y] = 'X';
}
/* obtem a jogada do computador */
void obtem_jogada_computador(void)
{
    int i, j, achou;
    achou = 0;
    /* obtem a primeira posicao livre na matriz */
    for (i=0; i<3; i++) {
    for (j=0; j<3; j++)
        if (matriz[i][j] == ' ') {
           achou = 1;
           break;
        }
    if (achou) break;
    }
    if (!achou) {
       printf ("\n** Empatamos... **\n");
       mostra_matriz();
       exit(0);
    }
    else matriz[i][j] = 'O';
}
/* mostra a matriz na tela */
void mostra_matriz(void)
{
    int t;
    for (t=0; t<3; t++) {
    printf (" %c | %c | %c", matriz[t][0], matriz[t][1],
matriz[t][2]);
    if (t != 2) printf ("\n---|---|---\n");
    }
    printf ("\n");
}
/* verifica se ha' um vencedor */
char verifica_vencedor(void)
{
    int i;
    for (i=0; i<3; i++)    /* verifica as linhas */
    if (matriz[i][0] == matriz[i][1] && matriz[i][0] == matriz[i][2])
       return matriz[i][0];
    for (i=0; i<3; i++)    /* verifica as colunas */
    if (matriz[0][i] == matriz[1][i] && matriz[0][i] == matriz[2][i])
       return matriz[0][i];
    /* testa as diagonais */
    if (matriz[0][0] == matriz[1][1] && matriz[0][0] == matriz[2][2])
       return matriz[0][0];
    if (matriz[0][2] == matriz[1][1] && matriz[0][2] == matriz[2][0])
       return matriz[0][2];
    return ' ';
}

Comentários:
- o computador joga de forma simples: quando é a sua vez, a função obtem_jogada_computador() varre a matriz, procurando por uma célula desocupada; ao encontrar uma, ele poe um 'O' na posição. Caso ele não encontre uma célula vazia, ele indica jogo empatado e termina.
- a função obtem_jogada_usuario() pergunta onde você quer colocar um 'X'. O canto superior esquerdo é a posição (1,1) e o canto inferior direito é a posição (3,3).
- a matriz do tabuleiro é inicializada para conter espaços, o que torna mais fácil sua apresentação na tela.
- toda vez que é feito um movimento, o programa chama a função verifica_vencedor(), que devolve um espaço se ainda nao há vencedor, um 'X' se o usuário ganhou e um 'O' se o computador ganhou. Ela varre as linhas, as colunas e as diagonais, procurando uma que tenha tudo 'X' ou 'O'.
- a função mostra_matriz() apresenta o estado atual do jogo. Observe como a inicialização com espaços simplifica essa função.
- todas estas rotinas acessam a matriz de forma diferente. Estude-as para ter certeza que você compreendeu cada operação com matriz.
- para uma matriz do tamanho desta, e previamente dimensionada, não se justifica utilizar alocação dinâmica. Ela foi incluída aqui apenas como forma de exercitar sua utilização.
- NUNCA esquecam de desalocar aquilo que foi alocado!

  Sumário

Dúvidas? Dê uma olhadinha em nosso FAQ

Perguntas para a lista do Curso de C
Curso de C do CPDEE/UFMG - 1996-1998