Matrizes e Arrays em C

Prévia do material em texto

A
r
r
a
y
s
 
e
m
C
Idéias Gerais
Variáveis 
Estruturadas:
vetores/arranjos/agregados (arrays 1D), 
struct (agregado heterogêneo)
Estruturas homogêneas (arrays multidimensionais)
Estruturas heterogêneas
matrizes (arrays 2D), ..., nD
strings (cadeias de caracteres)
Arquivos (FILES).
A
r
r
a
y
s
 
e
m
C
Matrizes – Revisão Matemática
11 12
21 22 2 2X
a a
A
a a
⎛ ⎞= ⎜ ⎟⎝ ⎠
11 12 13
21 22 23
31 32 33 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
Cada um dos elementos aij de uma matriz (tabela) podem ser determinados 
de forma única através de seus índices de linha e de coluna.
Por convenção, o primeiro índice (i) está associado a linha, enquanto o 
segundo índice (j) está associado a coluna.
( )ij mxnA a=
A
r
r
a
y
s
 
e
m
C
11 12 13
21 22 23
31 32 33 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
linha 1
linha 2
linha 3
coluna 
1
coluna 
2
coluna 
3
Matrizes – Revisão Matemática
A
r
r
a
y
s
 
e
m
C
linha i
coluna 
j
ija
11 1
1
n
m mn mxn
a a
A
a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
…
# #
"
Matrizes – Revisão Matemática
M
a
t
r
i
z
e
s
Operações Sobre Matrizes (Arrays 2D
Matrizes Æ Matrizes operação Escalar
Vetores Æ Matrizes operação Vetores
Matrizes Æ Matrizes operação Matrizes
Operações Típicas
multiplicação de matrizes por um escalar real;
multiplicação de matrizes por um vetor;
Adição, subtração, multiplicação, ..., entre matrizes;
M
a
t
r
i
z
e
s
Operações Sobre Matrizes (Arrays 2D
Matrizes Æ Matrizes
Permutação de linhas ou colunas, inversão, transposta de uma matriz;
Verificar uma dada propriedade (simetria, triangular inferior ou superior, ...);
Boleano Æ Matrizes
Real Æ Matrizes
Determinante, traço (soma dos elementos da diagonal principal ou 
secundária), maior elemento de uma linha ou coluna, maior elemento, ..., de 
uma matriz real;
Operações Típicas
M
a
t
r
i
z
e
s
Revisão de Matrizes
Multiplicação por um escalar 
Operações entre uma matriz A e um escalar .λ ∈\
** 1 ,ijA a i j nλ λ= ≤ ≤
A operação é realizada aplicando-se a multiplicação do escalar por 
todos os elementos da matriz.
M
a
t
r
i
z
e
s
Revisão de Matrizes
Operações entre matrizes
As matrizes A e B devem satisfazer os requisitos de dimensionalidade.
Subtração
Adição
, , .ij ijA B a b i j− = − ∀
, , .ij ijA B a b i j+ = + ∀
M
a
t
r
i
z
e
s
Revisão de Matrizes
Operações entre matrizes
As matrizes A e B devem satisfazer os requisitos de dimensionalidade.
Multiplicação matricial:
( )ij nxmA a=
( )jk mxpB b= 1
( ) *
m
ik nxp ij jk
j
C C a b
=
= = ∑
.C AB=
Como obter essa relação? Vamos 
desenvolver na lousa depois. Me lembrem.
A
r
r
a
y
s
 
e
m
C
Arrays 1D
Arrays multidimensionais (1D, 2D, 3D, ..., 12D)
i
A
0 n-1
Arrays unidimensionais (1D): Coleção de componentes de um 
mesmo tipo de dados.
Acesso a componentes:
indexada Notação(ponteiros)
A[i] *(A+i)
A
r
r
a
y
s
 
e
m
C
Arrays 2D
(índice de linha)
Arrays bidimensionais (2D): Representação diagramática
i
(índice de coluna)
j
linha i
coluna i
A
r
r
a
y
s
 
e
m
C
Representação de Arrays 2D
Arrays bidimensionais (2D): Representação diagramática
(5,5)(5,4)(5,3)(5,2)(5,1)(5,0)
(4,5)(4,4)(4,3)(4,2)(4,1)(4,0)
(3,5)(3,4)(3,3)(3,2)(3,1)(3,0)
(2,5)(2,4)(2,3)(2,2)(2,1)(2,0)
(1,5)(1,4)(1,3)(1,2)(1,1)(1,0)
(0,5)(0,4)(0,3)(0,2)(0,1)(0,0)
Em C, o primeiro elemento de um 
array, independente de sua 
dimensão, está sempre na posição 
0 (zero). Logo, o primeiro elemento 
de um array 2D está na posição 
(0,0).
A representação interna de um 
array 2D é feita em posições 
adjacentes de memória. Isso é
fundamental para permitir 
aritmética de ponteiros.
0
0
i m
j n
≤ <⎧⎨ ≤ <⎩
M
a
t
r
i
z
e
s
Acesso a Componentes: Forma Indexada
A[i][j]
índice de coluna
índice de linha
Nome da variável no momento da declaração
Elemento da matriz 
A que está na linha i 
e na coluna j.
A
r
r
a
y
s
 
e
m
C
Representação Diagramática de Arrays 2D
A[5][5]A[5][4]A[5][3]A[5][2A[5][1]A[5][0]
A[4][5]A[4][4]A[4][3]A[4][2A[4][1]A[4][0]
A[3][5]A[3][4]A[3][3]A[3][2A[3][1]A[3][0]
A[2][5]A[2][4]A[2][3]A[2][2A[2][1]A[2][0]
A[1][5]A[1][4]A[1][3]A[1][2A[1][1]A[1][0]
A[0][5]A[0][4]A[0][3]A[0][2]A[0][1]A[0][0]
Cada componente de um array 2D está associada a uma única posição 
na estrutura e pode ser referenciada de forma única através de seus 
índices de posição na linha e na coluna.
M
a
t
r
i
z
e
s
Declaração de Arrays 2D
Forma Geral: Æ
Tipo_de_Dado Nome_Variavel[NumeroLinhas][NumeroColunas];
Podem ser constantes ou 
expressões constantes.
int, char, float, double, ponteiro, ..., ou 
ainda do tipo struct (ainda vamos ver).
M
a
t
r
i
z
e
s
Declaração de Arrays 2D
Exemplos: Æ ...
...
#define MAX1 100
#define MAX2 500
int A[MAX1][MAX1];
int A1[MAX1][MAX2];
double bb[2*MAX1][MAX1];
// Matriz com 100 linhas e 100 colunas
// Matriz com 100 linhas e 500 colunas
// Matriz com 200 linhas e 500 colunas
M
a
t
r
i
z
e
s
Acesso a Arrays 2D – Notação Indexada
Forma Geral: Æ
nome_da_matriz[i][j]
Nome da variável 
estruturada matriz 
(array 2D) definida 
pelo usuário.
Índice que indica 
a linha onde o 
elemento se 
localiza
Índice que indica 
a coluna onde o 
elemento se 
localiza
M
a
t
r
i
z
e
s
Usando Notação Indexada
Exemplos: Æ Supondo as declarações de variáveis abaixo:
...
#define MAX1 100
#define MAX2 500
int A[MAX1][MAX1];
int A1[MAX1][MAX2];
...
// Matriz com 100 linhas e 100 colunas
// Matriz com 100 linhas e 500 colunas
Acesso a Componentes de Arrays 2D
M
a
t
r
i
z
e
s
As seguintes instruções são válidas:
...
printf(“ %d ”, A[2][3]);
A[2][8] = A[12][25];
b = A[1][6] + sqrt(A[i][j])
...
Acesso a Arrays 2D – Notação Indexada
% imprimindo o valor do elemento da 
matriz A que está na posição (2,3);
% Alterando o valor do elemento da 
matriz A que está na posição (2,8), que 
passa a ter o mesmo valor do elemento 
que está na posição (12,25);
% a variável b recebe o conteúdo da 
expressão que soma o valor do 
elemento da matriz A na posição (1,6), 
com o valor da raiz quadrada do 
elemento da mesma matriz que está na 
posição (i,j) ( );0 , 1i j MAX≤ <
M
a
t
r
i
z
e
s
Acesso a Arrays 2D – Notação Indexada
Em síntese, os elementos de uma matriz podem ser usados em 
todos os contextos em que usamos um escalar qualquer (variável 
simples), como por exemplo, em expressões aritméticas, argumentos 
de funções primitivas, ou ainda, como passagem de parâmetros:
M
a
t
r
i
z
e
s
Acesso a Componentes de Arrays 2D
Usando Aritmética de Ponteiros
A memória de um computador é linear e não bidimensional. Assim, 
quando declaramos uma variável A do tipo array 2D ( matriz ), o 
compilador se encarrega de reservar o espaço de memória 
necessário, baseado em informações do tipo base do array. Todas 
as referências a posição (i,j) ( [ i ][ j ]) são mapeadas para o endereço 
( * )k A i NC j= + +
onde:
:
:
A
NC
⎧⎨⎩
Endereço base do array 2D (1ª posição).
Número de colunas do array 2D.
M
a
t
r
i
z
e
s
Acesso a Componentes de Arrays 2D
Equivalência entre Notações Indexada e de 
Ponteiros
A[i][j] *(A + i*NC + j)
Acesso ao elemento da matriz A que está na posição (i,j).
Notação Indexada Aritmética de Ponteiros
endereçoOperador que indica o conteúdo 
de um endereço 
M
a
t
r
i
z
e
s
Inicializando Variáveis Estruturadas 2D
Inicializando uma variável do tipo array 2d no 
momento de sua declaração
Várias Alternativas:Æ
...
#define MAX1 3
int A[MAX1][MAX1] = { {1, 2, 3}, {3,3,3}, {-4,2,0} };
int B[MAX1][MAX1] = {1,2,3,4,5,6,7,8,9};
int C[MAX1][MAX1] = {1,2,3,4,5};
...
M
a
t
r
i
z
e
s
Manipulação de Matrizes
Embora toda matriz seja uma variável estruturada, toda e qualquer 
operação sobre ela, deve ser feita sobre seus elementos 
individualmente. Isto significa, que devemossaber como “percorrer” , 
“caminhar” sobre cada um dos elementos da matriz, de forma 
sistemática e organizada (transverse sobre a estrutura ).
É claro que poderíamos acessar os elementos de uma matriz de 
variadas formas. Por convenção e por simplicidade, manipulamos os 
elementos: da esquerda para a direita, e, de cima para baixo.
O trecho de código no próximo slide é capaz de passear por todos os 
elementos de uma matriz na ordem sugerida.
Todos os códigos a seguir foram elaborados para trabalhar com 
matrizes quadradas.
M
a
t
r
i
z
e
s
Manipulação de Matrizes
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33 NlxNc
a a a a
a a a a
A
a a a a
a a a a
⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
...
for (i=0; i<Nl; i++)
for (j=0; j<Nc; j++)
operações a serem realizadas sobre o elemento A[i][j];
...
% controla o índice de linhas;
% controla o índice de colunas;
Observem que o comando de repetição associado a variável de 
controle i é mais externo, logo, para cada valor de i, a variável de 
controle j, varia de 0 até Nc -1.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
void Leitura_Valores_Matriz(int *A, int Dim) {
int i, j;
for (i=0; i<Dim; i++)
for (j=0; j<Dim; j++) {
printf(“A[%d ,%d] = ”,i,j);
scanf(“%d”, (A + i*Dim + j) );
} // for j
return;
} // Leitura_Valores_Matriz
Leitura de uma matriz quadrada com valores arbitrários:
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
void Impressao_Valores_Matriz(int *A, int Dim) {
int i,j;
for (i=0; i<Dim; i++) {
printf(“\n”);
for (j=0; j<Dim; j++)
printf(“%d ”, *(A + i*Dim + j) );
} // for i
return;
} // Impressao_Valores_Matriz
Impressão de uma matriz quadrada:
Observação: Dependendo da dimensão da matriz podemos ter problemas em 
visualizar todos os elementos. Devemos pensar numa forma alternativa.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Soma dos elementos da diagonal principal de uma matriz quadrada:
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
...
for (i=0; i<Dim; i++)
for (j=0; j<Dim; j++)
if ( i == j ) soma += soma + A[i][j];
...
Qual o problema com o trecho de código acima? É possível ser mais 
eficiente?
Primeira abordagem.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Soma dos elementos da diagonal principal de uma matriz quadrada:
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
int Soma_Diagonal_Principal(int *A, int Dim) {
int i, soma = 0;
for (i=0; i<Dim; i++)
soma += *(A + i*Dim + i );
return(soma);
} // Soma_Diagonal_Principal
Soma dos elementos da diagonal principal de uma matriz :
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Obter a transposta de uma matriz.
11 12 13
21 22 23
31 32 33 3 3
Se,
x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
11 21 31
12 22 32
13 23 33 3 3
t
x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
void Transposta_Matriz(int *A, int *AT, int Dim) {
int i,j;
for (i=0; i<Dim; i++)
for (j=0; j<Dim; j++)
*(AT + i*Dim + j) = *(A + j*Dim + i );
return;
} // Soma_Diagonal_Principal
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Verificar se uma matriz é simétrica. Uma matriz é simétrica se o elemento que 
está na posição (i,j) é igual ao elemento que está na posição (j,i), ou seja, se A = 
At.
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
...
for (i=0; i<Dim; i++)
for (j=0; j<Dim; j++)
if ( A[i][j] != A[j][i] ) return(0);
return(1); ...
...
Qual o problema com o trecho de código acima? É possível ser mais 
eficiente?
Primeira abordagem.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Verificar se uma matriz é simétrica. Uma matriz é simétrica se o elemento que 
está na posição (i,j) é igual ao elemento que está na posição (j,i), ou seja, se A = 
At.
00 01 02
10 11 12
20 21 22 3 3x
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
Observe que é suficiente trabalhar somente com os elementos acima, 
ou abaixo da diagonal.
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Verificar se uma matriz é simétrica.
int Verificar_Simetria_Matriz (int *A, int Dim) {
int i, j;
for (i=1; i<Dim; i++)
for (j=0; j<i; j++)
if ( *(A + i*Dim + j) != *(A + j*Dim + i) ) 
return(0);
return(1);
} // Verificar_Simetria_Matriz
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Permutar os elementos de duas linhas de uma matriz arbitrária. 
l1
l2
x x x x x x x x x x x
x x x x x x x x x x x
0 1 2l l Dim≤ ≠ <
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Permutar os elementos de duas linhas de uma matriz arbitrária. 
Devemos observar que além dos parâmetros normais, há a necessidade de 
mais dois parâmetros que irão indicar respectivos índices das linhas a serem 
permutadas. A responsabilidade da correção desses índices deve ser de quem 
chamou a função. Por outro lado, a função garante a correção das linhas 
permutadas. (pré-condição e pós-condição).
Considerando a matriz a esquerda e os índices 0 e 2, após a 
permutação, teríamos a matriz do lado direito:
00 01 02
10 11 12
20 21 22
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
20 21 22
10 11 12
00 01 02
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Permutar os elementos de duas linhas de uma matriz arbitrária. 
void Permutar_Linhas_Matriz (int *A, int L1, int L2, int Dim) {
int i, j, aux;
for (i=1; i<Dim; i++) {
aux = *(A + L1*Dim + i); 
*(A + L1*Dim + i) ) = *(A + L2*Dim + i);
*(A + L2*Dim + i) = aux;
}
return;
} // Permutar_Linhas_Matriz
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Somar duas matrizes arbitrárias. 
Só podemos somar matrizes com mesma dimensão.
00 01 13 00 01 02 00 01 02
10 12 13 10 11 12 10 11 12
20 21 23 20 21 22 20 21 22
a a a b b b c c c
a a a b b b c c c
a a a b b b c c c
⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟+ =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
A B C+ =
M
a
t
r
i
z
e
s
Manipulação de Matrizes - Funções
Somar duas matrizes arbitrárias. 
int Somar_Matrizes (int *A, int *B, int *C, int Dima, int Dimb) {
int i, j;
if ( Dima != Dimb) return(0);
for (i=0; i<Dima; i++)
for (j=0; j<Dima; j++)
*(C + i*Dima + j) = *(A + i*Dima + j) ) + *(B + i*Dima + j);
}
return(1);
} // Somar_Matrizes
% soma realizada com sucesso
% impossível realizar soma
M
a
t
r
i
z
e
s
Exercícios
Elabore funções para manipular matrizes quadradas arbitrárias para 
resolver os seguintes problemas:
01) Encontre a soma dos elementos da diagonal secundária;
02) Encontre a soma dos elementos acima da diagonal principal;
03) Encontre a soma dos elementos abaixo da diagonal principal;
05) Encontrar o maior elemento em valor absoluto; 
06) Realizar a permutação dos os elementos de duas colunas 
quaisquer; 
04) Encontre a soma de todos os elementos da matriz;
M
a
t
r
i
z
e
s
Exercícios
07) Encontrar a matriz mágica de dimensão n;
Uma matriz quadrada (números inteiros) é denominada mágica, se possui a 
seguinte propriedade: 
“a soma dos elementos de cada uma das linhas, das colunas e das 
diagonais, são iguais. Além disso, somente os elementos inteiros de 1 a 
n2 são permitidos. Abaixo há exemplos de matrizes mágicas de 
dimensão 3, 4 e 5.
8 1 6
3 5 7
4 9 2
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
16 2 3 13
5 11 10 8
9 7 6 12
4 14 15 1
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
S = 15 S = 34 S = 65
M
a
t
r
i
z
e
s
Exercícios
08) Obter a soma de cada uma das linhas e de cada uma das colunas 
de uma matriz quadrada de dimensão n;
sl1
sl2
sl3
00 01 02
10 11 12
20 21 22
a a a
A a a a
a a a
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
sc1 sc2 sc3
M
a
t
r
i
z
e
s
Exercícios
09) Gerar uma matriz quadrada de dimensão n, satisfazendo a relação 
abaixo:
2 * se ( )%2 0
. .ij j
i j i j
A a
i c c
⎧ + == = ⎨⎩
10) Gerar uma matriz quadrada de dimensão n, satisfazendo a relação 
abaixo:
( , * )
( )
( ) . .
j
ij
Mdc i i j se i j
A a Fatorialj i se i j
Fibonacci i j c c
⎧ >⎪= = − <⎨⎪ +⎩
M
a
t
r
i
z
e
s
Exercícios
11) Obter o produto de uma matriz quadrada de dimensão n arbitrária 
pela sua transposta. 
12) Dado uma matriz quadrada de coeficientes inteiros de ordem Dim, 
dizemos que A é uma matriz de permutação, se em cada linha e em 
cada coluna houver (n-1) elementos nulos e um único elemento igual 
a 1. Elabore uma função para verificar se uma matriz nas condições 
enunciadas é de permutação. Por exemplo, as matrizes de ordem 3 
dadas abaixo são todas de permutação.
1 0 0
0 0 1
0 1 0
A
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
1 0 0
0 1 0
0 0 1
A
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠
0 0 1
1 0 0
0 1 0
A
⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠