Matrizes

DCC200 – Algoritmos II

Universidade Federal de Juiz de Fora

Departamento de Ciência da Computação

1 / 99
Conteúdo

▶ Introdução
▶ TADs
▶ TAD Vetor
▶ TAD Vetor Flexı́vel
▶ TAD Matriz
▶ TAD Matriz - Representação Linear
▶ TAD Matriz Flexı́vel - Representação Linear
▶ Matrizes Especiais
▶ Diagonal
▶ Triangular Inferior (ou Superior)
▶ Simétrica
▶ Anti-Simétrica
▶ Matrizes Esparsas
▶ Vetor Esparso
▶ Matriz Esparsa

2 / 99
Introdução

▶ Em computação, as matrizes são representadas por meio

de estruturas conhecidas como vetores (arrays), onde cada
posição/valor pode ser referenciada por um ou mais
ı́ndices (dependendo da quantidade de dimensões da
matriz);
▶ Enquanto na matemática uma matriz possui sempre duas
dimensões, na computação chama-se qualquer vetor de
matriz, podendo possuir uma ou mais dimensões.
▶ Matrizes unidimensionais (ou vetores)
▶ Matrizes bidimensionais
▶ Matrizes n-dimensionais

3 / 99
Introdução

▶ Quanto de memória ocupa uma matriz 5000 × 5000 de

valores reais?
▶ Um valor real (float) ocupa 4 bytes;
▶ Então, essa matriz ocupa aproximadamente 100MB.

▶ E se somente alguns poucos elementos dessa matriz

fossem diferentes de zero?
▶ Seria possı́vel reduzir a sua representação de forma que ela
passasse a ocupar menos espaço de memória?
▶ Veremos como representar essas matrizes de forma
compacta:
▶ Matrizes Diagonais;
▶ Matrizes Triangulares;
▶ Matrizes Esparsas;
▶ Etc...

4 / 99
TADs

▶ TAD Vetor (matriz unidimensional);

▶ TAD Vetor Flexı́vel;
▶ TAD Matriz bidimensional;
▶ TAD Matriz - Representação Linear;
▶ TAD Matriz Flexı́vel - Representação Linear.

5 / 99
TAD Vetor
▶ Seja o TAD Vetor de n elementos reais, representado na
classe em C++ a seguir:
class Vetor
{
public:
Vetor(int tam);
∼Vetor();
float get(int indice);
void set(int indice, float valor);

private:
int n; // tamanho do vetor
float *vet; // array que armazena n floats

bool verifica(int indice);

};

6 / 99
TAD Vetor

▶ Implementar o TAD Vetor anterior para um vetor de reais,

de acordo com as seguintes especificações:
▶ O tamanho do vetor deve ser definido em tempo de
execução. Assim, o construtor deve alocar memória de
acordo com o tamanho especificado pelo seu parâmetro
tam;
▶ Ao acessar ou modificar um elemento do vetor, verificar a
validade do ı́ndice;

▶ Em seguida, desenvolver um programa (implementar

main()) para testar o TAD Vetor, usando um vetor de 60
elementos reais.

7 / 99
TAD Vetor
▶ Construtor e destrutor
Vetor::Vetor(int tam) {
// inicializa a variavel interna n e
// aloca memoria para o vetor vet
n = 0;
if (n > 0)
n = tam;
vet = new float[n];

// opcional: inicializar vet com zeros

for(int i=0; i<n; i++)
vet[i] = 0.0;
}

Vetor::∼Vetor() {
// desaloca a memoria alocada no construtor
delete [] vet;
}
8 / 99
TAD Vetor

▶ A função privada verifica() analisa a validade do

ı́ndice do vetor.
▶ O ı́ndice pode assumir um valor entre 0 e n–1 (padrão
C/C++):
bool Vetor::verifica(int indice)
{
// verifica validade de indice
if(indice >= 0 && indice < n)
return true;
else
return false;
};

9 / 99
TAD Vetor
float Vetor::get(int indice)
{
if ( verifica(indice) )
return vet[indice];
else {
cout << "Indice invalido: get" << endl;
exit(1) ; // finaliza o programa
}
}

void Vetor::set(int indice, float valor)

{
if ( verifica(indice) )
//armazena valor na posicao indice de vet
vet[indice] = valor;
else
cout << "Indice invalido: set" << endl;
}
10 / 99
TAD Vetor
▶ Programa que usa o TAD Vetor criando um vetor de 60
elementos reais:
#include "Vetor.h"

int main() {
int tam = 60;
Vetor v(tam); // aloca vet[60]

for(int i=0; i<tam; i++) // armazena seq

[Link](i,i+1); // de 1 a 60

for(int i=0; i<tam; i++)

{
float val = [Link](i) ;
cout << val << endl;
}
return 0;
}
11 / 99
Vetor com Índices Flexı́veis

▶ Sabendo que na linguagem C/C++, o ı́ndice de um vetor

de tamanho n é um valor inteiro entre 0 e n − 1, pede-se:
▶ Desenvolver um TAD para possibilite criar vetores cujos
ı́ndices podem assumir seus valores em intervalos inteiros
e quaisquer, como por exemplo entre −10 e 45.
▶ Desenvolver uma aplicação para testar o TAD anterior,
criando um vetor de 60 elementos reais numerados de –29
(limite inferior) a 30 (limite superior).
▶ Os valores limites (inferior e superior) do intervalo do
ı́ndice devem ser definidos na aplicação, em tempo de
execução. Assim, o construtor deve alocar memória
dinamicamente para o vetor, de acordo com a definição
desses limites.
▶ Verificar a validade do ı́ndice, quando necessário.
12 / 99
Vetor com Índices Flexı́veis

Programa
VetorFlex v(-5, 6);
C F
-5 -4 -3 -2 -1 0 1 2 3 4 5 6

TAD VetorFlex
C/C++ índices 0 1 2 3 4 5 6 7 8 9 10 11

valores 2 1 3 9 6 -5 ... ... ... ... -3 25

13 / 99
TAD VetorFlex

class VetorFlex
{
private:
int n; // tamanho do vetor
float *vet; // array que armazena n floats
int c, f // c: limite inferior do indice
// f: limite superior do indice

int detInd(int indice); // operador privado

public:
VetorFlex(int a, int b);
∼VetorFlex();
float get(int indice);
void set(int indice, float valor);
};

14 / 99
TAD VetorFlex

// construtor
VetorFlex::VetorFlex(int cc, int ff)
{
c = cc;
f = ff;
n = f - c + 1;
vet = new double[n];
}

// destrutor
VetorFlex::∼VetorFlex()
{
delete [] vet;
}

15 / 99
TAD VetorFlex

▶ A função detInd(int i) é privada, isto é, só pode ser

utilizada dentro da classe VetorFlex.
▶ A função detInd(int i) verifica a validade do ı́ndice
de vet, isto é, se c ≤ i ≤ f .
▶ Se for válido, retorna o valor do ı́ndice de acordo com o
padrão C/C++, isto é, o valor correspondente a ı́ndice
dentro do intervalo de 0 a n–1.
▶ Senão (se for inválido), retorna −1.

16 / 99
TAD VetorFlex

int VetorFlex::detInd(int indice)

{
if(c <= indice && indice <= f)
return (indice - c);
else
return -1;
};

▶ Até então só foram utilizados atributos (variáveis

membro) como membros privados.
▶ Por que criar uma função privada em uma classe?
▶ Para realizar alguma tarefa que só é de interesse da classe.
▶ Nesse exemplo, o usuário do TAD VetorFlex não precisa
saber se essa verificação é feita ou como ela é feita antes de
acessar ou modificar um elemento do vetor.

17 / 99
TAD VetorFlex
float VetorFlex::get(int indice) {
int i = detInd(indice);
if(i != -1)
return vet[i];
else {
cout << "Indice invalido: get\n";
exit(1);
}
}

void VetorFlex::set(int indice, double val) {

int i = detInd(indice);
if(detInd(indice) != -1)
vet[i] = val;
else {
cout << "Indice invalido: set\n";
exit(1);
}
}
18 / 99
Vetor com Índices Flexı́veis
Aplicação

#include "VetorFlex.h"

int main()
{
int cc = -29; int ff = 30;
VetorFlex v(cc,ff);
for(int i = cc; i <= ff; i++)
{ // valores no intervalo 1...60
double val = i - cc + 1;
[Link](i,val);
}
for(int i = cc; i <= ff; i++)
{
double val = [Link](i);
cout << val << endl;
}
return 0;
}
19 / 99
Matrizes

▶ Matrizes com mais de uma dimensão.

▶ As principais operações são de atribuição e consulta;
▶ O projeto do TAD Matriz é idêntico ao do TAD Vetor,
devendo-se utilizar tantos ı́ndices quantas forem as
dimensões da matriz considerada;
▶ Exemplos de aplicações:

20 / 99
Matrizes

▶ Serão estudadas 2 formas diferentes de representar

matrizes:
1. Ponteiro de ponteiro (ou vetor de vetores): TAD Matriz2D
2. Representação linear: TAD Matriz

21 / 99
Matrizes
▶ TAD Matriz2D
▶ Representação por ponteiro de ponteiro (ou vetor de
vetores).
▶ Esquema:

22 / 99
TAD Matriz2D
▶ Classe para o TAD Matriz de 2 dimensões:
class Matriz2D
{
public:
Matriz2D(int nnl, int nnc);
∼Matriz2D();

float get(int i, int j);

void set(int i, int j, float valor);

private:
int nl; // numero de linhas
int nc; // numero de colunas
float **mat; // array com nl*nc floats

bool verifica(int i, int j);

};
23 / 99
TAD Matriz2D
▶ Construtor e destrutor.
Matriz2D::Matriz2D(int nnl, int nnc)
{
nl = nnl;
nc = nnc;
// aloca o vetor de vetores
mat = new float*[nl];
// aloca cada um dos vetores (cada linha)
for(int i = 0; i < nl; i++)
mat[i] = new float[nc];
}

Matriz2D::∼Matriz2D()
{
// desaloca a memoria alocada no construtor
for(int i = 0; i < nl; i++)
delete [] mat[i];
delete [] mat;
}
24 / 99
TAD Matriz2D

▶ A função privada verifica() analisa a validade dos

ı́ndices i e j seguindo o padrão C/C++;
▶ O ı́ndice i pode assumir valor entre 0 e nl − 1;
▶ e ı́ndice j entre 0 e nc − 1.

bool Matriz2D::verifica(int i, int j)

{
if(i >= 0 && i < nl && j >= 0 && j < nc)
return true;
else
return false; // indice invalido
};

25 / 99
TAD Matriz2D
float Matriz2D::get(int i, int j)
{
if ( verifica(i, j) )
return mat[i][j];
else {
cout << "Erro: indice invalido" << endl;
exit(1);
}
}

void Matriz2D::set(int i, int j, float valor)

{
if ( verifica(i, j) )
mat[i][j] = valor;
else {
cout << "Erro: indice invalido" << endl;
exit(1);
}
}
26 / 99
TAD Matriz2D

▶ Desenvolver um programa que usa o TAD Matriz2D para:

a) Ler 25 valores reais e gerar uma matriz 5x5, linha por linha.
b) Imprimir a 4ª coluna da matriz.
c) Ler ı́ndice de linha, ı́ndice de coluna e um valor real e
alterar a posição correspondente da matriz.
d) Determinar e imprimir a transposta da matriz.
e) Determinar o maior valor da diagonal secundária da
matriz.

27 / 99
Aplicação com o TAD Matriz2D
#include "Matriz2D.h"

int main() {
Matriz2D mat(5,5);

for(int i=0; i<5; i++)

for(int j=0; j<5; j++) {
float val;
cin >> val;
[Link](i,j,val);
}

for(int i=0; i<5; i++) {

cout << [Link](i,3) << endl;
}

// etc ...

return 0;
} 28 / 99
Matriz
▶ No TAD Matriz2D, apresentado anteriormente, usamos
um array bidimensional float **mat para representar a
matriz e o acesso era realizado com a seguinte operação:
mat[i][j].
▶ Seja a matriz A (3 × 4) de inteiros
 
5 9 6 7
A = −3 2 0 4 
1 8 3 −5
▶ Também pode-se armazenar a matriz A na memória
usando um único array unidimensional float *mat,
assim todos os elementos de A serão armazenados em
posições consecutivas de memória a partir de um endereço
base.
▶ Essa forma é conhecida como representação linear.
29 / 99
Matriz
Representação linear

▶ Para o exemplo anterior, considere que

▶ o ı́ndice da linha L varia de 0 a 2;
▶ o ı́ndice da coluna C varia de 0 a 3;
▶ a matriz seja percorrida linha por linha para ser
armazenada em memória.

▶ Visão da representação linear na memória

linha 0 linha 1 linha 2

Endereços b+0 b+1 b+2 b+3 b+4 b+5 b+6 b+7 b+8 b+9 b+10 b+11

Valor ... 5 9 6 7 -3 2 0 4 1 8 3 -5 ...

L ... 0 0 0 0 1 1 1 1 2 2 2 2 ...
C ... 0 1 2 3 0 1 2 3 0 1 2 3 ...

30 / 99
Matriz
Representação linear

31 / 99
Matriz
Representação linear

▶ Desta forma, a matriz bidimensional A(3 × 4) é

representada linearmente por um vetor V do tipo:
float V[12];

▶ Isto é, V é a representação linear de A.

▶ Para acessar um elemento de A em V, é necessário

relacionar o ı́ndice k de V com os ı́ndices i e j da matriz A.

▶ Isso é feito através da seguinte relação:

k = 4i + j

32 / 99
Matriz
Representação linear

▶ Assim, dados:
▶ o vetor V (representação linear da matriz A)
▶ um par de ı́ndices válidos i e j de A

▶ Para obter o valor do elemento A[i,j], deve-se acessar o

elemento V[k], sendo

k = 4i + j

▶ Notar que a matriz A está armazenada na memória através

de sua representação linear V.

▶ O que se deseja é consultar o valor de A[i, j] a partir de V.

33 / 99
Matriz
Representação linear

▶ Representação Linear de Matrizes

▶ Desenvolver o TAD Matriz para uma matriz m × n de
elementos reais.
▶ Observações:
▶ A representação interna da matriz deve ser linear.
▶ O número de linhas m e o de colunas n devem ser definidos
em tempo de execução.
▶ Assim, o construtor deve alocar memória de acordo com o
tamanho da matriz especificado pelos parâmetros m e n;
▶ Verificar a validade dos ı́ndices;
▶ Desenvolver um programa para testar o TAD Matriz, que
usa uma matriz 7 × 11 de elementos reais.

34 / 99
TAD Matriz

class MatrizLin
{
public:
MatrizLin(int m, int n);
∼MatrizLin();

float get(int i, int j);

void set(int i, int j, float val);

private:
int nl, nc; // numero de linhas e colunas
float *vet; // vetor de tamanho nl*nc

int detInd(int linha, int coluna);

};

35 / 99
TAD Matriz - Representação linear

▶ Construtor e destrutor

MatrizLin::MatrizLin(int m, int n)
{
// inicializa as variaveis internas
// e aloca memoria de vet (representacao linear)
nl = m;
nc = n;
vet = new float[nl*nc];
}

MatrizLin::∼MatrizLin()
{
// desaloca a memoria alocada no construtor
delete [] vet;
}

36 / 99
TAD Matriz - Representação linear

▶ A função privada detInd converte os ı́ndices linha e

coluna da matriz no ı́ndice k do vetor vet.
▶ Além disso, verifica validade de linha e coluna. Todos os
ı́ndices (linha, coluna e k) variam a partir de 0 (padrão
C/C++):
int MatrizLin::detInd(int i, int j)
{
if(i >= 0 && i < nl && j >= 0 && j < nc)
return i*nc + j;
else
return -1; // indice invalido
};

37 / 99
TAD Matriz - Representação linear
float MatrizLin::get(int i, int j)
{
int k = detInd(i, j);
if(k != -1)
return vet[k];
else {
cout << "Erro: get" << endl;
exit(1);
}
}

void MatrizLin::set(int i, int j, float valor)

{
int k = detInd(i, j);
if(k != -1)
vet[k] = valor;
else {
cout << "Erro: set" << endl; exit(1);
}
} 38 / 99
Aplicação com o TAD Matriz
#include "MatrizLin.h"

int main() {
int m = 7, n = 11;
MatrizLin mat(m,n);

for(int i=0; i<m; i++)

for(int j=0; j<n; j++)
{
float val = j + n*i;
[Link](i,j,val);
}

for(int i=0; i<m; i++) {

for(int j=0; j<n; j++)
{
float val = [Link](i,j) ;
cout << val << "\t";
}
cout << endl;
}

return 0;
}
39 / 99
Matriz - Representação linear

▶ Vamos considerar agora uma situação mais geral na qual

os elementos de uma matriz possuem ı́ndices quaisquer
(similar ao TAD VetorFlex).
▶ Seja A uma matriz com m × n de elementos de um tipo
qualquer. Os ı́ndices das linhas L e colunas C são:
▶ L = c1 . . . f1
▶ C = c2 . . . f2
▶ A matriz A possui um total de:
▶ linhas: m = f1 − c1 + 1
▶ colunas: n = f2 − c2 + 1
▶ O ı́ndice k da representação linear V que corresponde ao
elemento A[L, C] é dado por

I = (C − c2 ) + n(L − c1 ).

40 / 99
TAD Matriz Flexı́vel - Representação linear

▶ Representação Linear de Matrizes

▶ Desenvolver o TAD MatrizFlex para uma matriz m × n de
elementos reais com ı́ndices quaisquer.
▶ Observações:
▶ A representação interna da matriz deve ser linear;
▶ Os limites dos intervalos dos ı́ndices de linha e de coluna
devem ser arbitrários e definidos em tempo de execução.
Assim, o construtor deve alocar memória de acordo com
esses limites;
▶ Verificar a validade dos ı́ndices, quando necessário;
▶ Desenvolver um programa que use o TAD MatrizFlex e crie
uma matriz de elementos reais com os intervalos de linha =
-2..7 e de coluna = 0..5.

41 / 99
TAD MatrizFlex
class MatrizFlex
{
public:
MatrizFlex(int cc1, int ff1, int cc2, int ff2);
∼MatrizFlex();

float get(int i, int j);

void set(int i, int j, float val);

private:
float *vet; // representacao linear da matriz
int m, n; // numero de linhas e colunas
int c1; // limite inicial da linha
int c2; // limite inicial da coluna
int f1; // limite final da linha
int f2; // limite final da coluna
int detInd(int linha, int coluna);
};
42 / 99
TAD MatrizFlex
▶ Construtor e destrutor
MatrizFlex::MatrizFlex(int cc1, int ff1,
int cc2, int ff2)
{
// inicializa os limites
c1 = cc1;
c2 = cc2;
f1 = ff1;
f2 = ff2;
m = f1 - c1 + 1; // calcula o numero de linhas
n = f2 - c2 + 1; // calcula o numero de colunas
vet = new float[m*n] ;
}

MatrizFlex::∼MatrizFlex()
{
delete [] vet;
}
43 / 99
TAD MatrizFlex

▶ A função privada detInd converte os ı́ndices linha e

coluna da matriz no ı́ndice k do vetor vet. Além disso,
verifica validade de linha e coluna.
int MatrizFlex::detInd(int i, int j)
{
if(i >= c1 && i <= f1 && j >= c2 && j <= f2)
return (j - c2) + n*(i - c1);
else
return -1;
};

44 / 99
TAD MatrizFlex
float MatrizFlex::get(int i, int j)
{
int k = detInd(i, j) ;
if(k != -1)
return vet[k];
else
cout << "Indice invalido: get" << endl;
exit(1);
}

void MatrizFlex::set(int i, int j, float val)

{
int k = detInd(i, j) ;
if(k != -1)
vet[k] = valor;
else
cout << "Indice invalido: set" << endl;
exit(1);
}
45 / 99
TAD MatrizFlex
#include "MatrizFlex.h"

int main(){
int c1 = -2, f1 = 7;
int c2 = 0, f2 = 5;

MatrizFlex mat(c1,f1,c2,f2);

// atribui valores a matriz mat

for(int i=c1; i<=f1; i++)
for(int j=c2; j<=f2; j++){
float val = (f2-c2+1)*(i-c1) + j - c2; // 0...(n*m-1)
[Link](i,j,val);
}

// imprime a matriz mat

for(int i=c1; i<=f1; i++) {
for(int j=c2; j<=f2; j++) {
float val = [Link](i,j);
cout << val << "\t";
}
cout << endl;
}
return 0;
} 46 / 99
Matrizes Especiais

47 / 99
Matrizes Especiais

▶ Matriz Diagonal
▶ Matriz Triangular Inferior
▶ Matriz Triangular Superior
▶ Matriz Simétrica
▶ Matriz Anti-Simétrica
▶ Matriz Tridiagonal

48 / 99
Matrizes Especiais

▶ Serão apresentados diferentes tipos de matrizes especiais.

▶ A representação linear será usada para representar cada
tipo de matriz.
▶ Um TAD fundamental será desenvolvido com as seguintes
operações:
▶ Construtor
▶ Destrutor
▶ Função para consultar (get) um elemento Aij
▶ Função para alterar (set) o valor de um elemento Aij

49 / 99
Introdução
Representação Linear

▶ A representação linear (ou vetorial) é sempre usada pelo

computador para o armazenamento de uma matriz com
duas ou mais dimensões.
▶ Para usar uma representação linear V da matriz A, deve-se
realizar três tarefas:
1. Definir quais e de que forma os elementos de A serão
alocados em V;
2. Dimensionar V;
3. Relacionar os ı́ndices i, j de A com o ı́ndice k de V.
▶ Para atender a restrição da linguagem C/C++, será
considerada a variação dos ı́ndices a partir de 0 (zero) nos
casos que se seguem.

50 / 99
Matriz Diagonal

a00
a11
i==j
a22
... diagonal
principal
dia
gon
al
pr
inc
ipa
l i != j
...
fora da diagonal
principal
an-1n-1

a00 a11 a
vet 22 an-1n-1

0 1 2 n-1

▶ Implemente o TAD MatrizDiagonal como exercı́cio.

51 / 99
Matriz Triangular

▶ Matriz triangular inferior

 
l11 0 0
lij = 0, ∀ i < j, Exemplo: L =  l21 l22 0 
l31 l32 l33

▶ Matriz triangular superior

 
u11 u12 u13
uij = 0, ∀ i > j, Exemplo: U =  0 u22 u23 
0 0 u33

52 / 99
Matriz Triangular Inferior

▶ Vamos estudar como representar uma matriz triangular

inferior de n × n elementos reais.
▶ O procedimento é similar para uma matriz triangular
superior.
 
l11 0 0 ... 0
l21 l22 0 . . . 0 
L= .
 
 .. .. 
. 
ln1 ln2 ln3 . . . lnn

▶ Questões importantes:
1. Quantos elementos armazenar?
2. Representação linear: como armazenar os elementos?
3. Como acessar/modificar um elemento?

53 / 99
Matriz Triangular Inferior

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

Representação linear

índices 0 1 2 3 4 5 6 13 14

vet 1 2 3 4 5 6 7 ... ... ... 14 15

54 / 99
Matriz Triangular Inferior
▶ Quantos elementos a matriz triangular inferior L de
dimensão n possui?
 
l11 0 0 ... 0
l21 l22 0 . . . 0 
 
L = l31 l32 l33 . . . 0 
 
 .. .. 
 . . 
ln1 ln2 ln3 . . . lnn

▶ Linha por linha:

▶ Na linha 1 temos 1 elemento
▶ Na linha 2 temos 2 elementos
▶ Na linha 3 temos 3 elementos
▶ ...
▶ Na linha n temos n elementos
▶ Total = 1 + 2 + 3 + . . . + n elementos
55 / 99
Matriz Triangular Inferior

▶ Quantos elementos armazenar?

▶ Total = 1 + 2 + 3 + . . . + n elementos.
▶ Progressão aritmética (PA) de razão r = 1.
▶ Soma dos n termos de uma PA:
(a1 + an )n
Sn =
2
(n+1)n
▶ Portanto, a matriz possui um total de 2 elementos.

56 / 99
Matriz Triangular Inferior

▶ Como armazenar os elementos?

▶ Utilizando uma representação linear.
▶ Armazenar os elementos da matriz no vetor vet da
seguinte forma:
▶ Linha por linha;
▶ Da esquerda para a direita.

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

índices 0 1 2 3 4 5 6 ..... ... 13 14

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

57 / 99
Matriz Triangular Inferior
▶ Como acessar/modificar um elemento?
▶ Para acessar o elemento na posição (i, j):
▶ Contar quantos elementos tem antes da linha i:
1 0 0 0 0
2 3 0 0 0
4 5 6 0 0
7 8 9 10 0
11 12 13 14 15

índices 0 1 2 3 4 5 6 ...

vet 1 2 3 4 5 6 7 8 9 ...

▶ Número de elementos até a linha i:

(i + 1)i
2
▶ Para acessar o elemento (i, j) basta somar j, isto é
(i + 1)i
k= +j
2
58 / 99
Matriz Triangular Inferior

class MatrizTriInf
{
public:
MatrizTriInf(int ordem);
∼MatrizTriInf();

float get(int i, int j);

void set(int i, int j, float valor);

private
int n; // ordem da matriz triangular
float *vet; // representacao linear

bool verifica(int i, int j);

};

59 / 99
Matriz Triangular Inferior
MatrizTriInf::MatrizTriInf(int ordem)
{
n = ordem;
int tam = n*(n + 1)/2;
vet = new float[tam];
}

MatrizTriInf::∼MatrizTriInf()
{
delete [] vet;
}

bool MatrizTriInf::verifica(int i, int j)

{
if(i >= 0 && i < n && j >= 0 && j < n)
return true;
else
return false;
};
60 / 99
Matriz Triangular Inferior

float MatrizTriInf::get(int i, int j)

{
if(verifica(i, j))
{
if(i >= j)
{
int k = i*(i + 1)/2 + j;
return vet[k];
}
else
return 0.0;
}
else
cout << "Erro: indice invalido\n";
exit(1);
}

61 / 99
Matriz Triangular Inferior
void MatrizTriInf::set(int i, int j, float val)
{
if(verifica(i, j))
{
if(i >= j)
{
int k = i*(i + 1)/2 + j;
vet[k] = valor;
}
else
if(valor != 0.0)
cout << "Elemento fora da parte "
<< "triangular inferior\n";
}
else
cout << "Erro: indices invalidos\n";
}

62 / 99
Matriz Triangular Superior

▶ Para uma matriz triangular superior...

 
u11 u12 u13 . . . u1n
 0 u22 u23 . . . u2n 
 
U= 0
 0 u33 . . . u3n 
 .. . . 
 . . 
0 0 0 . . . unn

▶ Questões importantes:
1. Quantos elementos armazenar?
2. Representação linear: como armazenar os elementos?
3. Como acessar/modificar um elemento?

63 / 99
Matriz Simétrica

▶ Definição:
aij = aji , ∀ i, j
▶ Exemplo:
 
a11 a12 a13 . . . a1n
a12 a22 a23 . . . a2n 
 
A = a13 a23 a33 . . . a3n 


 .. .. 
 . . 
a1n a2n a3n . . . ann

▶ Representação: matriz triangular superior (ou inferior).

▶ Se a representação for por uma matriz triangular superior:
▶ Se i < j, retorna o elemento k = (j+1)j
2 + i.
▶ Senão, retorna o elemento k = (i+1)i
2 + j.

64 / 99
Matriz Anti-Simétrica

▶ Definição:
aij = −aji , ∀ i, j
▶ Exemplo:
 
0 a12 a13 . . . a1n
a12 0 a23 . . . a2n 
 
A = a13 a23 0 . . . a3n 
 
 .. .. 
 . . 
a1n a2n a3n . . . 0

65 / 99
Matriz Tridiagonal

dia
go
nal
pr
inc
ipa dia
l go
na
ls
up
er
ior

dia
go
na
l in
fer
ior

n n-1 n-1

i==j i-j == -1 i-j==1

diagonal diagonal diagonal
principal superior inferior

66 / 99
Exercı́cios

1. Desenvolver um TAD para matrizes diagonais.

2. Desenvolver um TAD para matrizes triangulares
superiores.
2. Desenvolver um TAD para matrizes simétricas.
3. Desenvolver um TAD para matrizes anti-simétricas.
4. Desenvolver um TAD para matrizes tridiagonais.
* Em cada caso desenvolver uma aplicação para testar e usar
o TAD da matriz desenvolvido.

67 / 99
Matrizes Esparsas

68 / 99
Vetor e Matriz Esparsa

▶ Uma matriz é chamada de esparsa quando a maioria dos

seus elementos são zero.
▶ Caso a maioria dos elementos sejam não-zero, então, a
matriz é chamada de densa.
▶ “...matrices that allow special techniques to take advantage of the
large number of zero elements.” (J. Wilkinson)
▶ Neste caso, é possı́vel economizar memória encontrando
uma representação especial para a matriz.
▶ Objetivo: desenvolver TADs para representar matrizes
esparsas.

69 / 99
Vetor Esparso

▶ As duas formas mais usuais para representar um vetor

esparso (ou matriz esparsa unidimensional) são:
i. Através de dois outros vetores:
▶ indices
▶ valores
ii. Através de um vetor de registros (structs)

▶ Seja um vetor esparso V de componentes do tipo tipo t.

▶ Os ı́ndices dos elementos variam de c até f .
▶ O vetor V possui n = f − c + 1 elementos.

70 / 99
Vetor Esparso
Representação com dois vetores

▶ Exemplo da representação de um vetor esparso utilizando

dois vetores, uma para armazenar os valores não-zero e
outro para armazenar os seus ı́ndices que variam de C a F.

C F
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8

2 1 3 0 0 6 9 0 12 -5 0 0 0 -3

índices -5 -4 -3 1 0 3 4 8

valores 2 1 3 9 6 12 -5 -3
folga

71 / 99
Vetor Esparso
Representação com vetor de duplas

▶ Exemplo da representação de um vetor esparso utilizando

vetor de duplas com ı́ndices que variam de C a F.

C F
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8

2 1 3 0 0 6 9 0 12 -5 0 0 0 -3

Dupla
etor de -5 -4 -3 1 0 3 4 8
ind = 3
duplas 2 1 3 9 6 12 -5 -3 val = 12
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
folga

72 / 99
TAD Vetor Esparso
▶ Desenvolver o TAD VetorEsparso e o seu MI para um
vetor esparso de elementos reais, cujos ı́ndices podem
variar de C até F.
▶ Os limites C e F devem ser definidos em tempo de execução
para que o construtor aloque memória de forma
apropriada;
▶ O número inicial de elementos não-zeros também deve ser
fornecido para o construtor;
▶ Representar o vetor esparso original sem os seus
elementos nulos usando um vetor de duplas.
▶ Definição da dupla:

typedef struct
{
int ind;
float val;
} Dupla;

73 / 99
TAD Vetor Esparso

class VetorEsparso
{
private:
int c, f;
int max; // capacidade maxima do vetor tab
int nnz; // numero de nao-zeros incluidas
Dupla *tab; // vetor de registros
int detInd(int i);

public:
VetorEsparso(int cc, int ff, int naozeros);
∼VetorEsparso();
float get(int i);
void set(int i, float valor);
};

74 / 99
TAD Vetor Esparso
Construtor e Destrutor

VetorEsparso::VetorEsparso(int cc, int ff, int

naozeros)
{
c = cc;
f = ff;
max = naozeros; // capacidade do vetor tab
nnz = 0; // nenhuma dupla adicionada ainda
tab = new Dupla[max];
}

VetorEsparso::∼VetorEsparso()
{
delete [] tab;
}

75 / 99
TAD Vetor Esparso
int VetorEsparso::detInd(int i)
{
if(i >= c && i <= f) // verifica validade
{
for(int t = 0; t < nnz; t++)
{
// determina indice k no vetor tab
if(tab[t].ind == i) return t;
}
// elemento nao esta representado
return -1;
}
else
{
cout << "Indice invalido!" << endl;
exit(1);
}
}
76 / 99
TAD Vetor Esparso
float VetorEsparso::get(int i)
{
int k = detInd(i);
if(k != -1) return tab[k].val;
else return 0;
}

void VetorEsparso::set(int i, float valor)

{
int k = detInd(i);
if(k != -1) tab[k].val = valor;
else {
if(nnz < max) {
tab[nnz].ind = i;
tab[nnz].val = valor;
nnz++;
}
else cout << "Nao ha espaco no vetor!" << endl;
}
} 77 / 99
TAD Vetor Esparso

▶ Na implementação do TAD VetorEsparso anterior, não

foi considerado a folga.
▶ Caso haja a necessidade de modificar o vetor V, pode-se
usar uma das representações estudadas anteriormente
considerando uma folga.
▶ Pode-se utilizar um valor flag nos campos ind das
posições de folga.
▶ No exemplo a seguir, o valor F + 1 foi utilizado.

78 / 99
TAD Vetor Esparso
Observações

▶ Note que a implementação anterior da função set(i,

valor) do TAD VetorEsparso não considera algumas
situações.
▶ Se detInd(i) ̸= -1
▶ O elemento já está representado (é não-zero)
▶ Atribuir um novo valor que é zero. Nesse caso, é preciso
remover um valor não-zero do vetor de registros
▶ Se detInd(i) = -1
▶ O elemento não está representado (é zero)
▶ Tratar o erro ao tentar atribuir um novo valor não-zero
quando o vetor de registros está cheio e não tem espaço
para inserir mais valores não-zero.

79 / 99
TAD Vetor Esparso 2

▶ O TAD VetorEsparso2 resolve as questões relacionadas à

função set() do TAD VetorEsparso discutidas
anteriormente.
▶ Para isso, duas funções (private) auxiliares serão criadas
no novo TAD:
▶ remove(i): remove o elemento não-zero da posição i do
vetor de registros (isto é, o transforma em zero);
▶ insere(i, valor): insere um novo elemento não-zero
na posição i caso haja espaço suficiente no vetor de
registros.

80 / 99
TAD Vetor Esparso 2
class VetorEsparso2
{
private:
int c, f; // indices: comeco e fim
int max; // capacidade maxima do vetor
int nnz; // numero de elementos nao-zero
Dupla *tab; // vetor de registros

int detInd(int i);

void remove(int k);
void insere(int i, float valor);

public:
VetorEsparso2(int cc, int ff, int naozeros);
∼VetorEsparso2();
float get(int i);
void set(int i, float valor);
};
81 / 99
TAD Vetor Esparso 2
Construtor e Destrutor
VetorEsparso2::VetorEsparso2(int cc, int ff, int
naozeros)
{
c = cc;
f = ff;
max = naozeros + 10; // num nao-zeros + folga
nnz = 0;
tab = new Dupla[max];
// inicializa o vetor com max duplas de folga
for(int i = 0; i < max; i++) {
tab[i].ind = f + 1;
tab[i].val = 0.0;
}
}

VetorEsparso2::∼VetorEsparso2()
{
delete [] tab;
} 82 / 99
TAD Vetor Esparso 2
int VetorEsparso2::detInd(int i)
{
if(i >= c && i <= f) {
for(int t = 0; t < nnz; t++)
if(tab[t].ind == i)
return t;
return -1;
} else {
cout << "Indice invalido!" << endl; exit(1); }
}

float VetorEsparso2::get(int i)
{
int k = detInd(i);
if(k != -1)
return tab[k].val;
else
return 0;
}
83 / 99
TAD Vetor Esparso 2

▶ Possibilidades da operação set(i,valor) do TAD

VetEsparso2.

84 / 99
TAD Vetor Esparso 2

void VetorEsparso2::set(int i, float valor)

{
int k = detInd(i);
if(k != -1)
{
if(valor == 0.0) // remove o elemento
remove(k);
else
tab[k].val = valor; // atualiza o valor
}
else if(valor != 0.0)
insere(i, valor); // insere uma nova dupla
}

85 / 99
TAD Vetor Esparso 2

void VetorEsparso2::remove(int k)
{
int t;

// zera o elemento (dupla) de indice k

for(t = k; t < nnz-1; t++)
{
// desloca duplas de (k+1) a nnz para esquerda
tab[t].ind = tab[t+1].ind;
tab[t].val = tab[t+1].val;
}

//inclui uma folga no final

tab[nnz].ind = f1+1;
tab[nnz].val = 0.0;
nnz--;
}

86 / 99
TAD Vetor Esparso 2
void VetorEsparso2::insere(int i, float valor)
{
if(nnz < max) {
int t = 0;
// inserir o indice na ordem correta
while(t < nnz tab[t].ind < i)
t++;
for(int m = nnz; m > t; m--) {
// desloca p/ direita ate t, p/ abrir espaco
tab[m].ind = tab[m-1].ind;
tab[m].val = tab[m-1].val;
}
// insere dupla na posicao t
tab[t].ind = i;
tab[t].val = valor;
nnz++;
}
else
cout << "Nao ha espaco!" << endl;
} 87 / 99
Matrizes Esparsas

▶ Existem diversas representações possı́veis para matrizes

esparsas.
▶ Pode-se usar representações análogas às do caso
unidimensional.
▶ Seja, por exemplo, uma matriz esparsa bidimensional M.
▶ Pode-se fazer a representação dos seus elementos
não-zeros através de:
i. três vetores: um para armazenar os ı́ndices de linhas, um
para os ı́ndices de colunas e outro para os valores
correspondentes dos elementos de M;
ii. um vetor de triplas: ı́ndice de linhas, ı́ndice de colunas e
valor do elemento.
▶ Em ambos os casos, pode-se considerar uma folga,
dependendo da necessidade.

88 / 99
 Matriz Esparsa
Vetor de Triplas

▶ Representação de matriz esparsa por um vetor de triplas.

▶ Índices variando de 0 a 6.

2 1 3 0 0 0 0
0 4 6 0 0 0 0
-5 0 9 0 0 0 0
-8 0 0 3 0 0 0
Tripla
0 0 0 0 2 0 0
lin = 3
0 0 0 0 0 8 0 col = 0
0 0 0 0 0 0 7 val =-8

Vetor de lin = 0 lin = 0 lin = 0 lin = 1 lin = 1 lin = 2 lin = 2 lin = 3 lin = 3 lin = 4 lin = 5 lin = 6
col = 0 col = 1 col = 2 col = 1 col = 2 col = 0 col = 2 col = 0 col = 3 col = 4 col = 5 col = 6
triplas val = 2 val = 1 val = 3 val = 4 val = 6 val = -5 val = 9 val = -8 val = 3 val = 2 val = 8 val = 7

89 / 99
TAD Matriz Esparsa
▶ Desenvolver o TAD MatrizEsparsa e o seu MI para uma
matriz esparsa M de elementos reais.
▶ M deve ser representada sem os seus elementos nulos;
▶ Utilizar uma folga de 10%;
▶ O ı́ndice de linha i varia de c1 até f1;
▶ O ı́ndice de coluna j varia de c2 até f2;
▶ Os limites c1,f1,c2 e f2 devem ser definidos em tempo
de execução, para que o construtor aloque memória de
forma adequada.
▶ A tripla é definida como:

typedef struct
{
int lin;
int col;
float val;
} Tripla;

90 / 99
TAD Matriz Esparsa
class MatrizEsparsa
{
private:
int c1, f1; // limites do indice de linha
int c2, f2; // limites do indice de coluna
int max; // capacidade maxima do vetor
int nnz; // numero de nao-zeros (triplas)
Tripla *tab; // vetor de registros
int detInd(int i, int j);
void remove(int k);
void insere(int i, int j, float valor);

public:
MatrizEsparsa(int i1,int i2,int j1,int j2,int n);
∼MatrizEsparsa();
float get(int i, int j);
void set(int i, int j, float valor);
};
91 / 99
TAD Matriz Esparsa
Construtor
MatrizEsparsa::MatrizEsparsa(int a1, int b1, int a2
, int b2, int n)
{
c1 = a1;
f1 = b1;
c2 = a2;
f2 = b2;
int folga = ((f1-c1+1)*(f2-c2+1)) * 0.1;
max = n + folga;
nnz = 0;
tab = new Tripla[max];
// inicializa tab com triplas de folga
for(int i = 0; i < max; i++) {
tab[i].lin = f1 + 1;
tab[i].col = f2 + 1;
tab[i].val = 0.0;
}
}
92 / 99
TAD Matriz Esparsa
Determina ı́ndice
int MatrizEsparsa::detInd(int i, int j)
{
if(i >= c1 && i <= f1 && j >= c2 && j <= f2) {
int k = -1;
for(int t = 0; t < nnz; t++) {
if(tab[t].lin == i && tab[t].col == j) {
k = t;
break;
}
}
return k;
}
else
{
cout << "Indice invalido!" << endl;
exit(1);
}
}
93 / 99
TAD Matriz Esparsa

▶ Possibilidades da operação set(i, j, valor) do TAD

MatrizEsparsa.

94 / 99
TAD Matriz Esparsa
float MatrizEsparsa::get(int i, int j)
{
int k = detInd(i, j);
if(k != -1) return tab[k].val;
else return 0;
}

void MatrizEsparsa::set(int i, int j, float valor)

{
int k = detInd(i, j);
if(k != -1)
{
if(valor == 0.0)
remove(k);
else
tab[k].val = valor;
}
else if (valor != 0.0)
insere(i, j, valor);
95 / 99
TAD Matriz Esparsa
Remove elemento não-zero do vetor de triplas
void MatrizEsparsa::remove(int k)
{
int t;
// remove a tripla da posicao k de tab
for(t = k; t < nnz-1; t++)
{
// desloca triplas de (k+1) a nnz p/ esq
tab[t].lin = tab[t+1].lin;
tab[t].col = tab[t+1].col;
tab[t].val = tab[t+1].val;
}
// inclui uma tripla de folga
tab[nnz].lin = f1+1;
tab[nnz].col = f2+1;
tab[nnz].val = 0.0;
nnz--;
}

96 / 99
TAD Matriz Esparsa
void MatrizEsparsa::insere(int i, int j, float valor)
{
if(nnz < max) {
int t = 0;
// inserir o indice na ordem correta
while(t < nnz) {
if(tab[t].lin > i) break;
if(tab[t].lin == i && tab[t].col > j) break;
t++;
}
for(int m = nnz; m > t; m--) {
//desloca para direita ate t para abrir espaco
tab[m].lin = tab[m-1].lin;
tab[m].col = tab[m-1].col;
tab[m].val = tab[m-1].val;
}
// insere tripla na posicao t
tab[t].lin = i;
tab[t].col = j;
tab[t].val = valor;
nnz++;
}
else
cout << "Nao ha espaco!" << endl;
} 97 / 99
Matriz Esparsa
Exercı́cios

1. Desenvolver o TAD para representar uma matriz esparsa

usando a representação com três vetores, a qual é
usualmente conhecida como formato coordenadas.
2 1 3 0 0 0 0
0 4 6 0 0 0 0
-5 0 9 0 0 0 0
-8 0 0 3 0 0 0
0 0 0 0 2 0 0
0 0 0 0 0 8 0
0 0 0 0 0 0 7

linha 0 0 0 1 1 2 2 3 3 4 5 6

coluna 0 1 2 1 2 0 2 0 3 4 5 6

valores 2 1 3 4 6 -5 9 -8 3 2 8 7

folga

98 / 99
Matriz Esparsa
Exercı́cios

1. Desenvolver o TAD para representar uma matriz esparsa

usando a representação com três vetores, a qual é
usualmente conhecida como formato coordenadas.
▶ Faça o construtor e destrutor e operações para consultar e
atribuir/alterar um valor da matriz esparsa;
▶ Considere uma folga de 10% sobre o total de elementos;
▶ Na operação set utilize operações auxiliares remove e
insere como feito no TAD anterior;
▶ remove(i, j): operação para atribuir a um elemento
não-zero o valor zero;
▶ insere(i, j, valor): operação para incluir um novo
elemento não-zero na matriz.

99 / 99