Aula 4 – Matrizes e Strings

Uma ma matriz é uma coleção de variáveis de mesmo tipo, referenciada por nome comum. Para acessar um elemento específico em uma matriz, utilizamos índices. C armazena os elementos da matriz de forma sequencial na memória.

Matrizes Unidimensionais

Forma geral de declaração:

tipo nome_variável[tamanho]

Assim como outras variáveis, as matrizes precisam ser explicitamente declaradas para que o compilador aloque espaço em memória para elas. Em tipo definimos que tipo de dado é cada elemento da matriz, nome_variável conterá o nome de acesso à matriz. E tamanho são a quantia de elementos que a matriz terá.

Para declararmos uma matriz de 100 elementos inteiros fazemos:


int numeros[100];

Em C, o primeiro elemento da matriz é o 0. Logo, para acessarmos os elementos da matriz acima, começamos do 0 até o 99. Se você tentar acessar o 100º elemento, o compilador não irá gerar erro algum. Portanto cabe a você tratar erros de limite de matrizes.
O seguinte código compila, porém está errado, afinal count é uma matriz de números inteiros com 10 elementos e o laço tenta acessar 100 elementos (0 à 99):


int count[10], i;

for (i = 0; i < 100; i++) count[i] = i;

O que irá acontecer neste caso é que você poderá estar sobreescrevento dados de outro programa na memória. Podemos imaginar as consequências disto.

Para saber quanto de espaço uma matriz unidimensional ocupa na memória usamos a fórmula:
total em bytes = sizeof(tipo) * tamanho da matriz
No meu caso o tipo inteiro consome 4 bytes na memória (linux 64 bits):
total em bytes = 4 * 100
total em bytes = 400bytes;

Este programa retorna à você o tamanho do inteiro de sua plataforma:

#include

int main()
{
     printf("sizeof int: %ld\n", sizeof(int));
}

Digamos que a alocação de uma matriz de 7 elementos, comece no endereço 1000 da memória. Teríamos algo como:

char a[7];

Elemento a[0] a[1] a[2] a[3] a[4] a[5] a[6]
Endereço 1000 1001 1002 1003 1004 1005 1006

Gerando um Ponteiro para uma Matriz

Para gerar um ponteiro ao primeiro elemento da matriz, apenas usamos o seu nome, por exemplo:


int *p;
int sample[10];
p = sample;

p é um ponteiro que aponta para o primeiro endereço da matriz, o sample[0]. Poderíamos também especificar o endereço do primeiro elemento usando o perador &:

p = &sample[0];

Porém códigos profissionais C dificilmente serão escritos desta forma.

Passando Matrizes Unidimensionais para Funções
Em C, não podemos passar uma matriz inteira como parâmetro de função. Para que uma função receba a matriz, passamos-lhe o ponteiro desta. O fragmento de programa abaixo, passa o endereço da matriz i para func1().

void main()
{
int i[10];
func1(1);
.
}

A função que receberá a matriz, precisa declarar isso em seu parâmetro formal. Temos três formas de fazer isso:

/** Ponteiro */
func1(int *x)
{ … }

/** Matriz dimensionada */
func1(int x[10])
{ … }

/** Matriz adimensional */
func1(int x[ ])
{ … }

Os três métodos acima são iguais, pois todos informam ao compilador que um ponteiro inteiro será recebido. No segundo exemplo não será alocada uma matriz de 10 elementos, então não faz diferença os exemplos acima, todos funcionarão visto que C não faz verificação de limite de matrizes.

Strings

O uso mais comum de matrizes unidimensionais é como string de caracteres. Lembrando que em C, uma string é uma matriz de caracteres, terminando com o caractere nulo ‘\0’. Por este motivo, se quizermos armazenar o nome Paulo em uma matriz, precisamos declarar 6 elementos, visto que o último sempre será o terminador. Apesar de C não ter o tipo de dado string, uma constante pode ser usada e você não precisa usar o caractere terminador, pois o compilador faz isso automaticamente:

“constante de teste”

C tem muitas funções de manipulação de strings, as mais comuns são:

Nome Função
strcpy(s1, s2) Copia s2 em s1
strcat(s1, s2) Concatena s2 ao final de s1
strlen(s1) Retorna o tamanho de s1
strcmp(s1, s2) Retorna 0 se s1 e s2 são iguais; menor que 0 se s1 < s2; maior que 0 se s1 > s2
strchr(s1, ch) Retorna um ponteiro para a primeira ocorrência de ch em s1
strstr(s1, s2) Retorna um ponteiro para a primeira ocorrência de s2 em s1

Essas funções usam o cabeçalho string.h. Vamos a um exemplo:

#include <stdio.h>
#include <string.h>

int main() {
    char s1[80], s2[80];

    scanf("%s", s1);
    scanf("%s", s2);

    printf("comprimentos: %d %d\n", (int) strlen(s1), (int) strlen(s2));

    if (!strcmp(s1, s2)) printf("As strings são iguais\n");

    strcat(s1, s2);
    printf("%s\n", s1);
    strcpy(s1, "Isso é um teste. \n");
    printf("%s", s1);

    if (strchr("alo", 'o')) printf("o está em alo\n");
    if (strstr("ola aqui", "ola")) printf("ola encontrado");
}

Precisei fazer algumas modificações no programa inicial mostrado no livro. O GCC Por exemplo, não aceita a função gets() para obter dados do teclado.

Matrizes Bidimensionais

C suporta matrizes multidimensionais. A forma mais simples desta matriz é a bidimensional, por exemplo:

int d[10][20];

Acima d é uma matriz bidimensional que contém 10 linhas e 20 colunas. Para acessarmos o endereço 1,2 da matriz, usaríamos:

d[1][2];

O programa abaixo cria uma matriz bidimensional com números de 1 a 12 e escreve-os de linha à linhha.

#include <stdio.h>

void main(void) {
    int t, i, num[3][4];

    for (t = 0; t < 3; ++t)
        for (i = 0; i < 4; i++)
            num[t][i] = (t * 4) + i + 1;

    // Exibindo os dados
    for (t = 0; t < 3; ++t) {
        for (i = 0; i < 4; ++i)
            printf("%3d ", num[t][i]);
        printf("\n");
    }
}

Vamos ver como poderíamos acessar esta matriz:

0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12

Aqui a posição num[0][0] tem o valor 1, enquanto que num[0][1] tem valor 2, num[2][3] tem o valor 12 e assim por diante. O primeiro índice indica a linha e o segundo sempre indica a coluna.

Para matriz bidimensional esta fórmula calcula seu tamanho na memória:
bytes = tamanho do 1º índice * tamano do 2º indice * sizeof(tipo base)

Este programa calcula o tamanho da matriz acima mostrada:


#include <stdio.h>

int main()
{
    printf("sizeof matriz[3][4]: %ld\n", 3 * 4 * sizeof(int));
}

No meu caso, ela ocupou 48 bytes na memória RAM.

Ao passarmos uma matriz bidimensional como argumento para uma função, apenas o ponteiro para o primeiro elemento é realmente passado. Já a função que recebe esta matriz precisa definir ao menos o comprimento da segunda dimensão. Do contrário o compilador não tem como saber o comprimento de cada linha para indexar a matriz corretamente. Por exemplo:

func1 (int x[ ][10]);
{ … }

A função acima recebe uma matriz bidimensional de inteiros com dimensões 10,10. Não precisamos especificar a primeira dimensão, mas se o fizer não terá problema algum.
Em sentenças como esta

x[2][4]

o compilador precisa saber o tamanho da segunda dimensão, do contrário não saberá onde começar a terceira linha.

O programa abaixo usa uma matriz bidimensional para armazenar notas de alunos. Ele suporta até 3 classes e 30 alunos cada uma:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

// Um banco de dados simples para notas de alunos
#define CLASSES 3
#define GRADES  30

int grade[CLASSES][GRADES];

void enter_grades(void);
int get_grade(int num);
void disp_grades(int g[][GRADES]);

void main(void)
{
        char ch, str[80];
        for (;;){
                do{
                        printf("(E)ntrar notas\n");
                        printf("(M)ostrar notas\n");
                        printf("(S)air\n");
                        scanf("%s", str);
                        ch = toupper(*str);
                } while(ch != 'E' && ch != 'M' && ch != 'S');

                switch (ch){
                        case 'E':
                                enter_grades();
                                break;
                        case 'M':
                                disp_grades(grade);
                                break;
                        case 'S':
                                exit(0);
                }
        }
}

/**
 * Insere notas dos alunos
 */
void enter_grades(void)
{
        int t, i;
        for (t = 0; t < CLASSES; t++){
                printf("Turma #%d:\n", t+1);
                for(i = 0; i < GRADES; ++i)
                        grade[t][i] = get_grade(i);
        }
}

/**
 * Lê uma nota
 */
int get_grade(int num)
{
        char s[80];
        printf("entre com a nota do aluno #%d\n", num + 1);
        scanf("%s",s);
        return (atoi(s));
}

/**
 * Mostra as notas
 */
void disp_grades(int g[][GRADES])
{
        int t, i;
        for (t = 0; t < CLASSES; ++t){
                printf("Turma #%d\n", t+1);
                for (i = 0; i < GRADES; ++i)
                        printf("aluno #%d e %d\n", i+1, g[t][i]);
        }
}

Matrizes de Strings

O tamanho do índice esquerdo delimitará o limite de strings e o índice direito o tamanho de cada string:

</pre>
char str_array[30][80];

O exemplo acima pode armazenar 30 strings de até 80 caracteres cada uma. Para acessar uma string individual é simples:

</pre>
scanf(“%s”,str_array[2]);

Este comando irá ler o teclado até que a tecla enter seja pressionada e armazenar este valor na terceira string da matriz. O comando abaixo é equivalente:

</pre>
scanf(“%s”, &str_array[2][0]);

O programa abaixo usa uma matriz de string para armazenar as entradas do usuário. Fiz uma modificação do livro, pois scanf não reconhece espaços em branco:

#include <stdio.h>
#define MAX 100
#define LEN 80

char text[MAX][LEN];

// Um editor de texto muito simples
void main(void)
{
        register int t, i, j;
        printf("Digite SAIR para sair.\n");
        for (t = 0; t < MAX; t++){
                printf("%d: ", t);
                scanf("%s", text[t]);
                // Se encontrar comando sair, sai
                if (!strcmp(text[t], "SAIR")) break;;
        }

        for (i = 0; i < t; i++){
                for (j = 0; text[i][j]; j++)    putchar(text[i][j]);
                putchar('\n');
        }
}

Matrizes Multidimensionais

C permite o uso de matrizes com mais de duas dimensões, porém são pouco utilizadas devido ao consumo de memória que apresentam. Uma matriz de inteiros com tamanhos 10,6,9,4 requer 8640bytes (10 * 6 * 9 * 4 * 4 – inteiro na minha plataforma). O aumento é exponencial. Grandes matrizes multidimensionais são alocadas dinamicamente na memória, isso será visto em outras aulas.

Forma geral:

tipo nome[a][b]

[/c]

…[z];

O tempo para acessar cada índice de uma matriz multidimensional é maior do que uma unidimensional.

Ao passar matrizes multidimensionais para funções, devemos declarar todas as dimensões, menos a primeira:

int m[4][3][6][5];

uma função que receba o m, seria algo como:
func1(int d[ ][3][6][5])
{…}

Indexando Ponteiros

Ponteiros e matrizes estão intimamente relacionados em C. A próxima aula será apenas sobre ponteiros e estudaremos eles a fundo. Como sabemos, um nome de matriz sem um índice é um ponteiro para o primeiro elemento da matriz.

supondo char p[10];
As sentenças a seguir são iguais:

p
&p[0]

De outra forma: p == &p[0] retornará verdadeiro, pois o endereço do primeiro elemento de uma matriz é o mesmo que a matriz. Podemos fazer algumas coisas interessantes:


int *p, i[10];
p = i;
// Atribui usando o índice
p[5] = 100;
// Atribui usando aritmética de ponteiros
(p + 5) = 100;

Ambos os comandos de atribuição acima, colocam o valor 100 no 6º elemento da matriz i. O segundo usa aritmética de ponteiros que será vista na próxima aula.
A mesma lógica pode ser usada para matrizes de duas ou mais dimensões. Supondo que a é uma matriz 2 por 10, as sentenças abaixo são equivalentes:

a
&a[0][0]

Indo além, o elemento 0,4 de a pode ser referenciado de duas formas: por indexação de matriz, a[0][4], ou por ponteiro, *(a + 4). De mesma forma, o elemento 1,2 é a[1][2] ou *(a + 12). Em geral, para qualquer matriz bidimensional

a[j][k] é equievalente a *(a + (j * comprimento das linhas) + k)

0 1 2 3 4 5 6 7 8 9
0 10 20 33 44 53 39 23 90 50 98
1 54 23 27 11 32 34 21 94 2 3

a[1][2] = 27
*(a + 12) = 27

Olhando desta meneira percebemos facilmente como uma matriz é armazenada na memória RAM:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
10 20 33 44 53 39 23 90 50 98 54 23 27 11 32 34 21 94 2 3

Logo, o índice (a + 12) equivale a (0 + 12) equivale ao valor 27.

As vezes, ponnteiros são usados para acessar matrizes porque a aritmética de ponteiros é geralmente mais rápida que a indexação de matrizes.

O programa abaixo imprime a segunda linha de uma matriz 2 por 3 usando aritmética de ponteiros:

#include <stdio.h>
void print_row(int, int, int*);

void main(void) {
    int matrix[2][3] = {
        1, 10, 11,
        2, 23, 98
    };
    print_row(1, 3, &matrix[0][0]);
}

void print_row(int j, int row_dimension, int *p) {
    int t;
    p = p + (j * row_dimension);
    for (t = 0; t < row_dimension; ++t)
        printf("%d ", * (p + t));
    printf("\n");
}

Inicialização de Matriz

Se você reparou bem o programa acima viu algo novo, a inicialização de uma matriz logo em sua declaração.

Forma geral:
especificador_de_tipo nome_da_matriz[tamanho1]…[tamanhoN] = {lista_valores};

Como a matriz é armazenada sequencialmente na memória, a lista_valores é uma lista separada por vírgulas apenas. No exemplo abaixo, incializamos uma matriz de 10 elementos com números de 1 à 10:


int i[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

O valor de i[0] é 1 e i[9] é 10.

Matrizes de caracteres que contêm strigns podem ser inicializadas de forma abreviada:


char str[14] = “Eu gosto de C”;

// é o mesmo que usar:

char str[14] = { ‘E’, ‘u’, ‘ ‘, ‘g’, ‘o’, ‘s’, ‘t’, ‘o’, ‘ ‘, ‘d’, ‘e’, ‘ ‘, ‘C’, ’\0’ };

Como as strings terminam com o caractere nulo ‘\0’, devemos sempre assegurar que a matriz declarada será longa o bastante para incluí-lo.

Matrizes multidimensionais são inicializadas da mesma maneira:

int matrix[2][3] = {
1,10,11,
2,23,98
};

Inicialização de Matrizes Adimensionais

É um tanto quanto tedioso ficar contando a quantidade de caracteres ao criar uma matriz. Para resolver este problema o compilador C faz isto automaticamente, logo podemos iniciar a string anterior desta maneira:


char str[ ] = “Eu gosto de C”;

Podemos fazer o mesmo para inicializar uma matriz multidimensional:

int matrix[ ][3] = {
1,10,11,
2,23,98
};

Devemos especificar todas as dimensões, exceto a que está mais à esquerda. A vantagem é que podemos aumentar ou diminuir o tamanho da tabela, sem alterar as dimensões da matriz.

Um Exemplo com o Jogo-daVelha

O livro traz um excelente exemplo de manipulações de matrizes em C. A matriz multidimensional geralmente é utilizada para simular jogos de tabuleiro.

Aqui o computador faz jogadas simples, da esquerda para direita, de cima para baixo. Quando é a vez dele jogar, ele usa a função get_computer_move() que varre a matriz procurando uma célula desocupada.
Encontrando a posição ele põe um ‘O’ nela. Se não encontrar nenhuma célula vazia, avisa ao jogador que o jogo está empatado.
A função get_player_move() pergunta ao jogador onde deseja colocar o ‘X’. O jogador entra com as conrdenadas xy sendo 1,1 o primeiro campo de cima para baixo da esquerda para direita.
No início do programa, a matriz do jogo é iniciada com espaços, fica mais simples desta maneira a apresentação da matriz na tela.
Sempre que há algum movimento a função check() é chamada. Se retornar um X, o jogador é o vencedor, se retornar 0 o computador é que venceu. Se por ventura retornar espaço então o jogo está empatado.
A função disp_matrix() apresenta o estado atual do jogo.

Abaixo o código fonte:

#include <stdio.h>
#include <stdlib.h>

// Inicia matriz do jogo
char matrix[3][3];

char check(void);
void init_matrix(void);
void get_player_move(void);
void get_computer_move(void);
void display_matrix(void);

void main(void) {
    char done;
    printf("Este é o jogo da velha.\n");
    printf("Você estará jogando contra o computador.\n");
    done = ' ';
    init_matrix();
    do {
        display_matrix();
        get_player_move();
        // Verifica se á vencedor
        done = check();
        if (done != ' ') break;
        get_computer_move();
        done = check();
    } while (done == ' ');

    if (done == 'X') printf("Você ganhou!\n");
    else printf("Eu ganhei!\n");
    // Exibe as posições finais
    display_matrix();
}

/**
 * Inicializa a matriz com valores em branco
 */
void init_matrix(void) {
    int i, j;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++) matrix[i][j] = ' ';
}

/**
 * Pede ao usuário, aonde quer jogar, e então marca com X esta posição
 */
void get_player_move(void) {
    int x, y;
    printf("Entre com as coordenadas para o X: ");
    scanf("%d%d", &x, &y);
    x--;
    y--;
    if (matrix[x][y] != ' ') {
        printf("Posição inválida, tente novamente.\n");
        get_player_move();
    } else matrix[x][y] = 'X';
}

void get_computer_move(void) {
    int i, j;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++)
            if (matrix[i][j] == ' ') break;
        if (matrix[i][j] == ' ') break;
    }
    if (i * j == 9) {
        printf("empate\n");
        exit(0);
    } else
        matrix[i][j] = '0';
}

void display_matrix(void) {
    int t;
    for (t = 0; t < 3; t++) {
        printf(" %c | %c | %c ", matrix[t][0], matrix[t][1],
                matrix[t][2]);
        if (t != 2) printf("\n---|---|---\n");
    }
    printf("\n");
}

/*
 * Verifica se há algum vencedor
 */
char check(void) {
    int i;
    // Verifica as linhas
    for (i = 0; i < 3; i++)
        if (matrix[i][0] == matrix[i][1] &&
                matrix[i][0] == matrix[i][2]) return matrix[i][0];

    // Verifica as colunas
    for (i = 0; i < 3; i++)
        if (matrix[0][i] == matrix[1][i] &&
                matrix[0][i] == matrix[2][i]) return matrix[0][i];

    // Verifica diagonais
    if (matrix[0][0] == matrix[1][1] && matrix[1][1] == matrix[2][2])
        return matrix[0][0];
    if (matrix[0][2] == matrix[1][1] && matrix[1][1] == matrix[2][0])
        return matrix[0][2];

    // Se não encontrou vencedor, retorna espaço
    return ' ';
}

Comments

  1. By marcelo

    Responder

    • Responder

    • By Anderson

      Responder

  2. By Douglas

    Responder

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *