03.ED.Matrizes-2-Especiais-2014-3

Prévia do material em texto

DCC013 
 
Estruturas de Dados 
Matrizes – Casos Especiais 
REPRESENTAÇÃO LINEAR DE MATRIZES 
 A representação linear (ou vetorial) é sempre 
usada pelo computador para o armazenamento 
de uma matriz com duas ou mais dimensões e 
pode ser um recurso importante para o 
programador em casos onde seja necessário 
adotar soluções para melhoria de desempenho, 
principalmente no que diz respeito à economia 
de memória. 
Matrizes 
2 
REPRESENTAÇÃO LINEAR DE MATRIZES 
 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 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. 
 A seguir serão apresentadas alternativas de 
representações lineares de casos especiais de 
matrizes. 
Matrizes 
3 
Casos Especiais – MATRIZ DIAGONAL 
 Uma matriz M de índices i = 0..(m-1) e j = 0..(n-1), 
é chamada matriz diagonal se todos os seus 
elementos situados fora da diagonal principal são 
nulos, isto é, se M [i, j] = 0 para todo i  j. 
 Exemplo: 
Matrizes 
4 
 7.5 0.0 0.0 
M = 0.0 -5.0 0.0 
 0.0 0.0 3.0 
 0.0 0.0 0.0 
 
Casos Especiais – MATRIZ DIAGONAL 
 Pode-se economizar memória representando 
M(4x3) por um vetor V(3) contendo somente os 
elementos da diagonal principal . 
 
 
 Genericamente: 
Matrizes 
5 
V = 7.5 -5.0 3.0 
 
 
 






ji
jiiV
jiM
 se 0
 se 
,
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 1: Desenvolver o TAD TMatDiag e o 
seu MI para uma matriz diagonal mn de 
elementos reais. Usar uma representação linear 
e considerar as seguintes operações: 
 Construtor (inicializa variáveis e aloca memória); 
 Destrutor (desaloca memória); 
 Verificar a validade dos índices i e j da matriz. 
 Consultar o valor real da posição de índices i e j 
(válidos) da matriz diagonal. 
 Atribuir um novo valor real para a posição de 
índices i e j (válidos) da matriz diagonal. 
Matrizes 
6 
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 1: TAD TMatDiag 
Matrizes 
7 
class TMatDiag 
{ 
 //numeros de linhas e de colunas da matriz diagonal 
 int nl, nc; 
 //vet: representação linear da matriz diagonal 
 float *vet; 
 bool Verifica(int i, int j); 
 public: 
 TMatDiag(int m, int n); 
 float Consulta(int i, int j); 
 void Atribui(int i, int j, float valor); 
 ~TMatDiag(); 
}; 
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 1: MI para TMatDiag 
 Construtor: 
Matrizes 
8 
TMatDiag::TMatDiag(int m, int n) 
{ 
 nl = m; 
 nc = n; 
 //tam: numero de elementos da diagonal principal = 
 //= menor valor entre numero de linhas e colunas 
 int tam = nl < nc ? nl : nc; 
 vet = new float[tam]; //aloca tam floats para vet 
} 
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 1: MI para TMatDiag 
 Destrutor: 
Matrizes 
9 
TMatDiag::~TMatDiag() 
//desaloca a memória alocada pelo construtor 
{ 
 delete [] vet; 
} 
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 1: MI para TMatDiag 
 Operação Verifica: 
Matrizes 
10 
bool TMatDiag::Verifica(int i, int j) 
{//verifica validade dos indices de linha e coluna 
 if(i >= 0 && i < nl && j >= 0 && j < nc) 
 return true; 
 else 
 return false; //índices invalidos 
}; 
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 1: MI para TMatDiag 
 Operação Consulta: 
Matrizes 
11 
float TMatDiag::Consulta(int i, int j) 
{ 
 if(Verifica(i, j)) 
 return i == j ? vet[i] : 0.0; 
 else 
 cout<<“Indice invalido - Consulta”<<endl; 
 exit(1); // finaliza o programa 
} 
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 1: MI para TMatDiag 
 Operação Atribui: 
Matrizes 
12 
void TMatDiag::Atribui(int i, int j, float valor) 
{ 
 if(Verifica(i, j)){ 
 if(i == j) 
 vet[i] = valor; 
 else if(valor != 0.0) 
 cout<<“Não atribui: elemento [”<<i<<“,”<<j 
 <<“] fora da diagonal principal”<<endl; 
 } 
 else 
 cout<<“Indice invalido - Atribuição”<<endl; 
} 
Casos Especiais – MATRIZ DIAGONAL 
 Observação: A representação diagonal não 
permite que uma operação de atribuição faça 
com que o resultado deixe de representar uma 
matriz diagonal. 
Isso é uma vantagem ou uma desvantagem? 
Matrizes 
13 
Casos Especiais – MATRIZ DIAGONAL 
 Exercício 1: Desenvolver o TAD e o MI para uma 
matriz nn de elementos reais onde todos os 
elementos fora das diagonais principal e 
secundária são nulos. Considerar as mesmas 
operações do TAD anterior. 
Matrizes 
14 
Casos Especiais – MATRIZ TRIANGULAR 
 Uma matriz é chamada triangular se todos os 
elementos abaixo ou acima da diagonal principal 
são nulos. Exemplos: 
Matrizes 
15 
M (3x4) é uma matriz triangular superior de 
elementos inteiros, que pode ser representada 
pelo vetor [7, 5, 9, -7, 4, 3, 2, 8, 6]. 
 7.5 0.0 0.0 
N = 9.4 10.0 0.0 
 3.2 5.9 7.9 
 3.3 0.0 5.8 
N (4x3) é uma matriz triangular inferior de 
elementos reais, que pode ser representada pelo 
vetor [7.5, 9.4, 10.0, 3.2, 5.9, 7.9, 3.3, 0.0, 5.8]. 
 7 
 
 6 
 7 5 9 - 
M = 0 4 3 2 
 0 0 8 
Casos Especiais – MATRIZ TRIANGULAR 
Matrizes 
16 
 Generalizando: seja uma matriz quadrada M (nn), 
com índices [i, j], tal que i = 0..(n-1) e j = 0.. (n-1). 
 
 Se M[i, j] = 0 para i < j, então ela é triangular 
inferior e possui a seguinte representação natural: 
Casos Especiais – MATRIZ TRIANGULAR 
 
Matrizes 
17 
0 1 2 ... i ... n-1 
0 M[0,0] 0 0 ... 0 ... 0 
1 M[1,0] M[1,1] 0 ... 0 ... 0 
... ... ... ... ... ... ... ... 
M = i M[i,0] M[i,1] M[i,2] ... M[i, i] ... 0 
... ... ... ... ... ... ... ... 
n-1 M[n-1,0] M[n-1,1] M[n-1,2] ... M[n-1,i] ... M[n-1,n-1] 
 
Matrizes 
18 
1. Definir quais e de que forma os elementos de 
M serão alocados em V. 
Casos Especiais – MATRIZ TRIANGULAR 
 Na busca de uma representação vetorial V para 
M, deve-se realizar as três tarefas: 
0 1 2 ... i ... n-1 
0 M[0,0] 0 0 ... 0 ... 0 
1 M[1,0] M[1,1] 0 ... 0 ... 0 
... ... ... ... ... ... ... ... 
M = i M[i,0] M[i,1] M[i,2] ... M[i, i] ... 0 
... ... ... ... ... ... ... ... 
n-1 M[n-1,0] M[n-1,1] M[n-1,2] ... M[n-1,i] ... M[n-1,n-1] 
 
Solução adotada: 
Serão alocados em V todos os elementos de M 
situados na diagonal principal e abaixo dela (i ≥ j), 
percorrendo M linha por linha, de cima para baixo e 
da esquerda para a direita. 
Matrizes 
19 
V = [ M[0,0], M[1,0], M[1,1], ..., M[i,0], ..., M[i,j], ..., M[i,i], ..., M[n-1,0], ..., M[n-1,n-1]] 
1. Definir quais e de que forma os elementos de 
M serão alocados em V. 
Casos Especiais – MATRIZ TRIANGULAR 
Assim, V pode ser representado da seguinte forma: 
Matrizes 
20 
Elementos 0 
por linha 
1 
2 
... 
i + 1 
... 
n 
Total = m Total: m = n (n + 1) / 2 
2. Dimensionar V. 
Casos Especiais – MATRIZ TRIANGULAR 
0 1 2 ... i ... n-1 
0 M[0,0] 0 0 ... 0 ... 0 
1 M[1,0] M[1,1] 0 ... 0 ... 0 
... ... ... ... ... ... ... ... 
M = i M[i,0] M[i,1] M[i,2] ... M[i, i] ... 0 
... ... ... ... ... ... ... ... 
n-1 M[n-1,0] M[n-1,1] M[n-1,2] ... M[n-1,i] ... M[n-1,n-1] 
 
Desta forma, M passa a ser representada por um 
vetor V de m elementos: 
Matrizes 
21 
2. Dimensionar V. 
Casos Especiais – MATRIZ TRIANGULAR 
V = [ M[0,0], M[1,0],M[1,1], ..., M[i,0], ..., M[i,j], ..., M[i,i], ..., M[n-1,0], ..., M[n-1,n-1]] 
Considerando a variação do índice k de V a partir 
de 0 (zero), tem-se: 
Matrizes 
22 
k = 0 1 2 ................................. k ...................................................... ..... (m-1) 
 
V = [ M[0,0], M[1,0], M[1,1], ..., M[i,0], ..., M[i,j], ..., M[i,i], ..., M[n-1,0], ..., M[n-1,n-1]] 
Casos Especiais – MATRIZ TRIANGULAR 
Isto é, k varia de 0 até (m – 1). 
2. Dimensionar V. 
Matrizes 
23 
3. Relacionar os índices i e j de M com o índice k 
de V. 
Casos Especiais – MATRIZ TRIANGULAR 
Em outras palavras, busca-se determinar uma 
função k = f (i, j), que permita realizar operações 
com o elemento M[i, j] (consulta, atribuição etc.), 
manipulando efetivamente V[k]. 
Deve-se lembrar que somente o vetor V está 
armazenado na memória. A matriz M não está. 
k = 0 1 2 ................................. k ...................................................... ..... (m-1) 
 
V = [ M[0,0], M[1,0], M[1,1], ..., M[i,0], ..., M[i,j], ..., M[i,i], ..., M[n-1,0], ..., M[n-1,n-1]] 
Casos Especiais – MATRIZ TRIANGULAR 
Matrizes 
24 
Elementos 0 
por linha 
1 
2 
... 
i + 1 
... 
n 
0 1 2 ... i ... n-1 
0 M[0,0] 0 0 ... 0 ... 0 
1 M[1,0] M[1,1] 0 ... 0 ... 0 
... ... ... ... ... ... ... ... 
M = i M[i,0] M[i,1] M[i,2] ... M[i, i] ... 0 
... ... ... ... ... ... ... ... 
n-1 M[n-1,0] M[n-1,1] M[n-1,2] ... M[n-1,i] ... M[n-1,n-1] 
 
k = 0 1 2 ................................. k ........................................................... (m-1) 
 
V = [ M[0,0], M[1,0], M[1,1], ..., M[i,0], ..., M[i,j], ..., M[i,i], ..., M[n-1,0], ..., M[n-1,n-1]] 
Casos Especiais – MATRIZ TRIANGULAR 
Matrizes 
25 
Neste caso, para relacionar os índices i e j de M 
com k de V, deve-se somar as quantidades de 
elementos representados em V, pertencentes às 
(i – 1) linhas anteriores, mais os (j + 1) elementos 
da linha i e subtrair 1 (um) desse total, já que k 
varia a partir de 0 (zero). Assim: 
k = 0 1 2 ................................. k ........................................................... (m-1) 
 
V = [ M[0,0], M[1,0], M[1,1], ..., M[i,0], ..., M[i,j], ..., M[i,i], ..., M[n-1,0], ..., M[n-1,n-1]] 
1)1(
2
)1(
1)1(321 

 j
ii
jik 
Casos Especiais – MATRIZ TRIANGULAR 
Matrizes 
26 
jiik  2/)1(*
Em C/C++: 
1)1(
2
)1(
1)1(321 

 j
ii
jik 
Casos Especiais – MATRIZ TRIANGULAR 
 Aplicação 2: Desenvolver o TAD TMatTriang e o 
seu MI para uma matriz triangular inferior nn 
de elementos reais. Usar uma representação 
linear e considerar as seguintes operações: 
 Construtor (inicializa variáveis e aloca memória); 
 Destrutor (desaloca memória); 
 Verificar a validade dos índices i e j da matriz. 
 Consultar o valor real da posição de índices i e j 
(válidos) da matriz triangular. 
 Atribuir um valor real para a posição de índices i e j 
(válidos) da matriz triangular. 
Matrizes 
27 
Casos Especiais – MATRIZ TRIANGULAR 
 Aplicação 2: TAD TMatTriang 
Matrizes 
28 
class TMatTriang 
{ 
 int n; // ordem da matriz triangular 
 float *vet;// representação linear da triangular 
 bool Verifica(int i, int j); 
 public: 
 TMatTriang(int ordemMatriz); 
 float Consulta(int i, int j); 
 void Atribui(int i, int j, float valor); 
 ~TMatTriang(); 
}; 
Casos Especiais – MATRIZ TRIANGULAR 
Aplicação 2: MI para TMatTriang 
 Construtor: 
Matrizes 
29 
TMatTriang::TMatTriang(int ordemMatriz) 
{ 
 n = ordemMatriz; 
 //m: tamanho do vetor vet 
 int m = n*(n + 1)/2; 
 vet = new float[m]; //aloca m floats para vet 
} 
Casos Especiais – MATRIZ TRIANGULAR 
 Aplicação 2: MI para TMatTriang 
 Destrutor: 
Matrizes 
30 
TMatTriang::~TMatTriang() 
//desaloca a memória alocada pelo construtor 
{ 
 delete [] vet; 
} 
Casos Especiais – MATRIZ DIAGONAL 
 Aplicação 2: MI para TMatTriang 
 Operação Verifica: 
Matrizes 
31 
bool TMatTriang::Verifica(int i, int j) 
{//verifica validade dos indices de linha e coluna
 if(i >= 0 && i < n && j >= 0 && j < n) 
 return true; 
 else 
 return false; //indice invalido 
}; 
Casos Especiais – MATRIZ TRIANGULAR 
 Aplicação 2: MI para TMatTriang 
 Operação Consulta: 
Matrizes 
32 
float TMatTriang::Consulta(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<<“Não consulta: Indice invalido”<<endl; 
 exit(1); // finaliza o programa 
} 
Casos Especiais – MATRIZ TRIANGULAR 
 Aplicação 2: MI para TMatTriang 
 Operação Atribui 
Matrizes 
33 
void TMatTriang::Atribui(int i, int j, float valor) 
{ 
 if(Verifica(i, j)){ 
 if(i >= j){ 
 int k = i*(i + 1)/2 + j; 
 vet[k] = valor;} 
 else 
 if(valor != 0.0) 
 cout<<“Não atribui: elemento [“<<i<<“,”<<j 
 <<“] fora do triangulo inferior”<<endl;} 
 else 
 cout<<“Não atribui: Indices invalidos”<<endl; 
} 
Casos Especiais – MATRIZ TRIANGULAR 
 Exercício 2: Desenvolver o TAD TMatTriangSup e 
o seu MI para uma matriz triangular superior 
nn de elementos reais. Usar uma representação 
linear e considerar as seguintes operações: 
 Construtor (inicializa variáveis e aloca memória); 
 Destrutor (desaloca memória); 
 Verificar a validade dos índices i e j da matriz. 
 Consultar o valor real da posição de índices i e j 
(válidos) da matriz triangular. 
 Atribuir um valor real para a posição de índices i e j 
(válidos) da matriz triangular. 
Matrizes 
34 
Casos Especiais – MATRIZ SIMÉTRICA 
 Uma matriz quadrada M(n x n) de índices i e j é 
chamada simétrica se M[i, j] = M[j, i] para todo 
i, j = 0 .. (n-1) 
 Exemplo: 
Matrizes 
35 
- 
7 5 9 
M = 5 4 3 
9 3 8 
Neste caso, basta tratá-la como 
triangular inferior, por exemplo, 
e trabalhar com M [j, i], quando 
i < j. 
Casos Especiais – MATRIZ SIMÉTRICA 
 Aplicação 3: Desenvolver o TAD TMatSim e o seu 
MI para uma matriz simétrica nn de elementos 
reais. Usar uma representação linear e considerar 
as seguintes operações: 
 Construtor (inicializa variáveis e aloca memória); 
 Destrutor (desaloca memória); 
 Verificar a validade dos índices i e j da matriz e 
determinar o índice k da representação linear. 
 Consultar o valor real da posição de índices i e j 
(válidos) da matriz simétrica. 
 Atribuir um valor real para a posição de índices i e j 
(válidos) da matriz simétrica. 
Matrizes 
36 
Casos Especiais – MATRIZ SIMÉTRICA 
 Aplicação 3: TAD TMatSim 
Matrizes 
37 
class TMatSim 
{ 
 int n; //ordem da matriz simetrica 
 float *vet; //representação linear da simetrica 
 int DetInd(int i, int j); 
 public: 
 TMatSim(int ordemMatriz); 
 float Consulta(int i, int j); 
 void Atribui(int i, int j, float valor); 
 ~TMatSim(); 
}; 
Casos Especiais – MATRIZ SIMÉTRICA 
Aplicação 3: MI para TMatSim 
 Construtor: 
Matrizes 
38 
TMatSim::TMatSim(int ordemMatriz) 
{ 
 n = ordemMatriz; 
 //tam: tamanho do vetor vet 
 int tam = n*(n + 1)/2; 
 vet = new float[tam]; //aloca tam floats para vet 
} 
Casos Especiais – MATRIZ SIMÉTRICA 
Aplicação 3: MI para TMatSim 
 Destrutor: 
Matrizes 
39 
TMatSim::~TMatSim() 
//desaloca a memória alocadapelo construtor 
{ 
 delete [] vet; 
} 
Casos Especiais – MATRIZ SIMÉTRICA 
 Aplicação 3: MI para TMatSim 
 Operação DetInd: 
Matrizes 
40 
int TMatSim::DetInd(int i, int j) 
{//verifica validade dos indices de linha e coluna e 
 //determina o indice correspondete de vet 
 if(i >= 0 && i < n && j >= 0 && j < n){ 
 if(i >= j) //elemento do triangulo inferior 
 return (i*(i + 1)/2 + j); 
 else //elemento do triangulo superior 
 return (j*(j + 1)/2 + i);} 
 else 
 return -1; //índices invalidos 
}; 
Casos Especiais – MATRIZ SIMÉTRICA 
 Aplicação 3: MI para TMatSim 
 Operação Consulta: 
Matrizes 
41 
float TMatSim::Consulta(int i, int j) 
{ 
 int k = DetInd(i, j); 
 if(k != -1) 
 return vet[k]; 
 else 
 cout<<“Não consulta: Indices invalidos”<<endl; 
 exit(1); // finaliza o programa 
} 
Casos Especiais – MATRIZ SIMÉTRICA 
 Aplicação 3: MI para TMatSim 
 Operação Atribui: 
Matrizes 
42 
void TMatSim::Atribui(int i, int j, float valor) 
{ 
 int k = DetInd(i, j); 
 if(k != -1) 
 vet[k] = valor; 
 else 
 cout<<“Não atribui: Indices invalidos”<<endl; 
} 
Casos Especiais - MATRIZ ANTI-SIMÉTRICA 
 Uma matriz quadrada M(n x n) de índices i e j é 
chamada anti-simétrica se: 
 M[i, j] = -M[j, i] para todo i, j = 0 .. (n-1). 
 
 Exemplo: 
Matrizes 
43 
0 7 -5 
M = -7 0 9 
5 -9 0 
Neste caso, basta tratá-la como 
triangular inferior, por exemplo, 
excluindo a diagonal principal da 
sua representação vetorial e 
trabalhar com -M[j, i], quando i < j, 
e com 0 (zero), quando i = j. 
Casos Especiais – MATRIZ ANTI-SIMÉTRICA 
 Aplicação 4: Desenvolver o TAD TMatAntiSim e o 
seu MI para uma matriz anti-simétrica nn de 
elementos reais. Usar uma representação linear e 
considerar as seguintes operações: 
 Construtor (inicializa variáveis e aloca memória); 
 Destrutor (desaloca memória); 
 Verificar a validade dos índices i e j da matriz. 
 Consultar o valor real da posição de índices i e j 
(válidos) da matriz anti-simétrica. 
 Atribuir um valor real para a posição de índices i e j 
(válidos) da matriz anti-simétrica. 
Matrizes 
44 
Casos Especiais – MATRIZ ANTI-SIMÉTRICA 
 Aplicação 4: TAD TMatAntiSim 
Matrizes 
45 
class TMatAntiSim 
{ 
 int n; // ordem da matriz anti-simetrica 
 float *vet; // representação linear 
 bool Verifica(int i, int j); 
 public: 
 TMatAntiSim(int ordemMatriz); 
 float Consulta(int i, int j); 
 void Atribui(int i, int j, float valor); 
 ~TMatAntiSim(); 
}; 
Casos Especiais – MATRIZ ANTI-SIMÉTRICA 
Aplicação 4: MI para TMatAntiSim 
 Construtor: 
Matrizes 
46 
TMatAntiSim::TMatAntiSim(int ordemMatriz) 
{ 
 n = ordemMatriz; 
 //tam: tamanho do vetor vet 
 int tam = n*(n + 1)/2 - n; 
 vet = new float[tam]; //aloca tam floats para vet 
} 
 
Casos Especiais – MATRIZ ANTI-SIMÉTRICA 
 Aplicação 4: MI para TMatAntiSim 
 Destrutor: 
Matrizes 
47 
TMatAntiSim::~TMatAntiSim() 
//desaloca a memória alocada pelo construtor 
{ 
 delete [] vet; 
} 
Casos Especiais – MATRIZ ANTI-SIMÉTRICA 
 Aplicação 4: MI para TMatAntiSim 
 Operação Verifica: 
Matrizes 
48 
bool TMatAntiSim::Verifica(int i, int j) 
{//verifica validade dos indices de linha e coluna 
 if(i >= 0 && i < n && j >= 0 && j < n) 
 return true; 
 else 
 return false; //índices invalidos 
}; 
Casos Especiais – MATRIZ ANTI-SIMÉTRICA 
 Aplicação 4: MI para TMatAntiSim 
 Operação Consulta: 
Matrizes 
49 
float TMatAntiSim::Consulta(int i, int j) 
{ 
 if(Verifica(i, j)){ 
 if(i > j) 
 return vet[i*(i - 1)/2 + j]; 
 else if(i < j) 
 return -vet[j*(j - 1)/2 + i]; 
 else 
 return 0.0; 
 } 
 else 
 cout<<“Não consulta: Indices invalidos”<<endl; 
 exit(1); // finaliza o programa 
} 
Casos Especiais – MATRIZ ANTI-SIMÉTRICA 
 Aplicação 4: MI para TMatAntiSim 
 Operação Atribui: 
Matrizes 
50 
void TMatAntiSim::Atribui(int i, int j, float valor) 
{ 
 if(Verifica(i, j)){ 
 if(i > j) 
 vet[i*(i-1)/2 + j] = valor; 
 else if(i < j) 
 vet[j*(j- 1)/2 + i] = -valor; 
 else if(valor != 0.0) 
 cout<<“Não atribui: Valor invalido” 
 <<endl; 
 } 
 else 
 cout<<“Não atribui: Indices invalidos”<<endl; 
} 
Casos Especiais - MATRIZ TRIDIAGONAL 
 Uma matriz quadrada M(n x n) de índices i e j é 
chamada tridiagonal se forem nulos todos os 
elementos situados fora da diagonal principal 
(M[i, i], i = 0..(n-1)) e das duas paralelas vizinhas a 
ela (M[i+1, i]) e M[i, i+1], i = 0..(n-2). 
 Exemplo: 
Matrizes 
51 
Ex.: 
 
 4 7 0 0 
M = 13 -5 3 0 
 0 -9 -8 2 
 0 0 6 23 
 
Casos Especiais – MATRIZ TRIDIAGONAL 
 Aplicação 5: Desenvolver o TAD TMatTriDiag e o 
seu MI para uma matriz tridiagonal nn de 
elementos reais. Usar uma representação linear e 
considerar as seguintes operações: 
 Construtor (inicializa variáveis e aloca memória); 
 Destrutor (desaloca memória); 
 Verificar a validade dos índices i e j da matriz. 
 Consultar o valor real da posição de índices i e j 
(válidos) da matriz tridiagonal. 
 Atribuir um valor real para a posição de índices i e j 
(válidos) da matriz tridiagonal. 
Matrizes 
52 
Casos Especiais – MATRIZ TRIDIAGONAL 
 Aplicação 5: TAD TMatTriDiag 
Matrizes 
53 
class TMatTriDiag 
{ 
 int n; //n: ordem da matriz tridiagonal 
 float *vet; //vet: vetor de tamanho tam 
 bool Verifica(int i, int j); 
 public: 
 TMatTriDiag(int ordemMatriz); 
 float Consulta(int i, int j); 
 void Atribui(int i, int j, float valor); 
 ~TMatTriDiag(); 
}; 
Casos Especiais – MATRIZ TRIDIAGONAL 
Aplicação 5: MI para TMatTriDiag 
 Construtor: 
Matrizes 
54 
TMatTriDiag::TMatTriDiag(int ordemMatriz) 
{ 
 n = ordemMatriz; 
 //tam: tamanho do vetor vet 
 tam = n + 2*(n-1); 
 vet = new float[tam]; //aloca tam floats para vet 
} 
 
Casos Especiais – MATRIZ TRIDIAGONAL 
 Aplicação 5: MI para TMatTriDiag 
 Destrutor: 
Matrizes 
55 
TMatTriDiag::~TMatTriDiag() 
//desaloca a memória alocada pelo construtor 
{ 
 delete [] vet; 
} 
Casos Especiais – MATRIZ TRIDIAGONAL 
 Aplicação 5: MI para TMatTriDiag 
 Operação Verifica: 
Matrizes 
56 
bool TMatTriDiag::Verifica(int i, int j) 
{//verifica validade dos indices de linha e coluna 
 if(i >= 0 && i < n && j >= 0 && j < n) 
 return true; 
 else 
 return false; //índices invalidos 
}; 
Casos Especiais – MATRIZ TRIDIAGONAL 
 Aplicação 5: MI para TMatTriDiag 
 Operação Consulta: 
Matrizes 
57 
float TMatTriDiag::Consulta(int i, int j) 
{ 
 if(Verifica(i, j)){ 
 if(i == j) 
 return vet[i]; 
 else{if(i – j == -1) 
 return vet[n + i]; 
 else{if(i – j == 1) 
 return vet[n + (n-1) + j]; 
 else return 0.0;}}} 
 else cout<<“Não consulta: Indices invalidos”<<endl; 
 exit(1); // finaliza o programa 
} 
Casos Especiais – MATRIZ TRIDIAGONAL 
 Aplicação 5: MI para TMatTriDiag 
 Operação Atribui: 
Matrizes 
58 
void TMatTriDiag::Atribui(int i, int j, float valor) 
{ 
 if(Verifica(i, j)){ 
 if(i == j) 
 vet[i] = valor; 
 else{if(i – j == -1) 
 vet[n + i] = valor; 
 else{if(i – j == 1) 
 vet[n + (n-1) + j] = valor;else cout<<“Não atribui: elemento [i,j] 
 fora da tridiagonal”<<endl;}}} 
 else cout<<“Não atribui: Indices invalidos”<<endl; 
}