03.ED.Matrizes-3-Esparsas-2014-1

Prévia do material em texto

DCC013 
 
Estruturas de Dados 
Matrizes Esparsas 
Matrizes Esparsas 
 Uma matriz é chamada esparsa se possui 
elementos nulos. 
 Neste caso, é possível economizar memória 
encontrando uma representação especial para a 
matriz. 
Matrizes 
2 
Matrizes Esparsas Unidimensional 
 As duas formas mais usuais para representar um 
vetor esparso são: 
Através de dois outros vetores: 
 indice 
valor 
Através de um vetor de registros (structs): 
Matrizes 
3 
Matrizes Esparsas Unidimensional 
Representação por dois vetores 
 Seja um vetor esparso V de componentes do 
tipo_t, com índice variando de c até f. Neste caso, 
V possui n = (f – c + 1) elementos. 
 V pode ser representado por dois outros vetores: 
 indice: vetor de elementos do tipo int, indexados de 
0 a (n-1), que contêm os índices de V. 
 valor: vetor de elementos do tipo_t, também 
indexados de 0 a (n-1), que contêm os valores de V. 
 Assim, um valor inteiro 0 ≤ k ≤ (n – 1) usado 
como índice tanto de indice como de valor, 
identifica o par (índice, valor) de V, 
respectivamente. 
Matrizes 
4 
Matrizes Esparsas Unidimensional 
Representação por dois vetores 
Exemplo: 
 Seja um vetor V de elementos reais, com índices 
variando no intervalo [-2, 7]: 
 
 
 
 V poderia ser representado pelos dois seguintes 
vetores: 
Matrizes 
5 
0 1 2 3 4 5 6 7 8 9 
indice = -2 -1 0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7 8 9 
valor = 0.0 5.3 0.0 0.0 3.2 -5.4 0.0 7.9 0.0 0.0 
-2 -1 0 1 2 3 4 5 6 7 
V = 0.0 5.3 0.0 0.0 3.2 -5.4 0.0 7.9 0.0 0.0 
Representação por dois vetores 
Exemplo: 
 A forma mais simples de declarar esses dois 
vetores em C++ é: 
 
int indice[10]; 
float valor[10]; 
Matrizes 
6 
Representação por dois vetores 
Exemplo: 
 Então, para k = 5 por exemplo: 
indice[5] = 3 e valor [5] = -5.4 
 
 
 
 
 
 
Dessa forma, identifica-se o par (índice, valor) de V, 
isto é: 
V [indice [5]] = valor [5] ou 
V[3] = -5.4 
Matrizes 
7 
0 1 2 3 4 5 6 7 8 9 
Indice = -2 -1 0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7 8 9 
Valor = 0.0 5.3 0.0 0.0 3.2 -5.4 0.0 7.9 0.0 0.0 
Representação por dois vetores. Aplicação 1: 
 Desenvolver o TAD (TVetIndValor) e o MI 
respectivo, para um vetor esparso de elementos 
reais, cujo índice pode variar de c até f. Obs: 
 Os limites c e f devem ser definidos em tempo de 
execução de forma que o construtor possa alocar 
memória apropriadamente; 
 O vetor esparso original deve ser representado no 
TVetIndValor através de dois outros vetores indice e 
valor. 
 Verificar a validade do índice original; 
 Desenvolver um PA suportado pelo TAD 
TVetIndValor que utiliza o vetor V de elementos 
reais com índice variando no intervalo -30..72. 
Matrizes 
8 
Representação por dois vetores 
 Aplicação 1: TAD TVetIndValor 
Matrizes 
9 
class TVetIndValor 
{ 
 int c, f; 
 int tam; // total de elementos dos vetores 
 int *indice; // vetor de índices 
 float *valor; // vetor de valores 
 int DetInd(int i); 
 public: 
 TVetIndValor(int comeco, int fim); 
 float Consulta(int i); 
 void Atribui(int i, float val); 
 ~TVetIndValor(); 
}; 
Representação por dois vetores 
 Aplicação 1: MI do TAD TVetIndValor 
 Construtor: 
Matrizes 
10 
TVetIndValor::TVetIndValor(int comeco, int fim) 
{ 
 c = comeco; 
 f = fim; 
 tam = f - c + 1; 
 indice = new int[tam]; 
 valor = new float[tam]; 
 // inicializa o vetor com os índices 
 for(int i = c, k = 0; i <= f, k < tam; i++, k++) 
 { 
 indice[k] = i; 
 valor[k] = 0.0; 
 } 
} 
Representação por dois vetores 
 Aplicação 1: MI do TAD TVetIndValor 
 Destrutor: 
Matrizes 
11 
TVetIndValor::~TVetIndValor() 
{ 
 delete [] indice; 
 delete [] valor; 
} 
Representação por dois vetores 
 Aplicação 1: MI do TAD TVetIndValor 
 Operação DetInd: 
Matrizes 
12 
int TVetIndValor::DetInd(int i) 
{ 
 if(i >= c && i <= f){ 
 int k = 0; 
 while(indice[k] != i) 
 k++; 
 return k; 
 } 
 else 
 return -1; 
} 
Obs.: como a validade 
de i já foi testada no 
if(i >= c && i <= f), 
não é necessário 
verificar no while se k 
atingiu o limite do 
vetor (k < tam) 
Representação por dois vetores 
 Aplicação 1: MI do TAD TVetIndValor 
 Operação Consulta: 
Matrizes 
13 
float TVetIndValor::Consulta(int i) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 return valor[k]; 
 else 
 { 
 cout<<"Indice invalido!"<<endl; 
 exit(1); 
 } 
} 
Representação por dois vetores 
 Aplicação 1: MI do TAD TVetIndValor 
 Operação Atribui: 
Matrizes 
14 
void TVetIndValor::Atribui(int i, float val) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 valor[k] = val; 
 else 
 cout << "Indice invalido!" << endl; 
} 
Representação por vetor de registros (structs) 
 Agora, o vetor esparso é representado através da 
seguinte estrutura de dados: 
typedef struct {int ind; tipo_t val;} dupla; 
dupla tab[n]; 
 O vetor V do exemplo anterior seria, agora, 
definido como: 
typedef struct {int ind; float val;} dupla; 
dupla tab[10]; 
 
Matrizes 
15 
Representação por vetor de registros (structs) 
 A variável tab, que contem todas as duplas (ind 
e val) de V, pode ser representada graficamente 
da seguinte forma: 
Matrizes 
16 
0 1 2 3 4 5 6 7 8 9 
tab = 
-2 -1 0 1 2 3 4 5 6 7 
0.0 5.3 0.0 0.0 3.2 -5.4 0.0 7.9 0.0 0.0 
Matrizes Esparsas Unidimensional 
 A princípio não há vantagem nenhuma em usar 
essas representações, mas como V é esparso, pode-
se considerar somente os seus elementos não nulos. 
 Desta forma, as representações do vetor V ficam 
reduzidas a: 
Dois vetores: Vetor de structs : 
Matrizes 
17 
0 1 2 3 
tab = 
-1 2 3 5 
5.3 3.2 -5.4 7.9 
0 1 2 3 
indice = -1 2 3 5 
0 1 2 3 
valor = 5.3 3.2 -5.4 7.9 
Matrizes Esparsas Unidimensional 
 As definições das estruturas de dados em C++ 
correspondentes a essas representações 
reduzidas de V passam a ser: 
 Os dois vetores: 
int indice[4]; 
float valor[4]; 
 
 O vetor de structs: 
typedef struct {int ind; float val;} dupla; 
dupla tab[4]; 
Matrizes 
18 
Representação por vetor de registros (structs) 
Aplicação 2: 
 Desenvolver o TAD (TVetEsparso) e o seu MI 
para um vetor esparso de elementos reais, cujo 
índice pode variar de c até f. Obs: 
 Os limites c e f, bem como o número inicial de 
elementos não nulos devem ser definidos em tempo 
de execução de forma que o construtor possa alocar 
memória apropriadamente; 
 O vetor esparso original deve ser representado no 
TVetEsparso sem os seus elementos nulos e 
através de um vetor de duplas (structs). 
 Verificar a validade do índice original; (Continua...) 
Matrizes 
19 
Representação por vetor de registros (structs) 
Aplicação 2 (Continuação): 
 Desenvolver um PA suportado pelo TAD 
TVetEsparso que utiliza o vetor V1 de 
elementos reais com índice variando no 
intervalo [-30, 72], sendo V1[-28] = 47.0, 
V1[-15] = 4.5, V1[-7] = -39.8, V1 [-6] = 1.0, 
V1 [0] = 5.4, V1 [18] = 43.0, V1 [33] = 3.3, 
V1 [35] = 47.9, V1 [59] = -3.7, V1 [72] = 5.2 e 
todos os demais elementos são nulos. 
Matrizes 
20 
Representação por vetor de registros (structs) 
 Aplicação 1: TAD TVetEsparso 
Matrizes 
21 
// struct contendo um par (indice, valor) 
typedef struct 
{ 
 int ind; 
 float val; 
}dupla; 
Representação por vetor de registros (structs) 
 Aplicação1: TAD TVetEsparso 
Matrizes 
22 
class TVetEsparso 
{ 
 int c, f; 
 int max; // capacidade máxima do vetor tab 
 int total; // total de duplas já incluidas 
 dupla *tab; // vetor de registros 
 int DetInd(int i); 
 public: 
 TVetEsparso(int cc, int ff, int naonulos); 
 float Consulta(int i); 
 void Atribui(int i, float valor); 
 ~TVetEsparso(); 
}; 
Representação por vetor de registros (structs) 
 Aplicação 1: MI do TAD TVetEsparso 
 Construtor e destrutor: 
Matrizes 
23 
TVetEsparso::TVetEsparso(int cc,int ff,int naonulos) 
{ 
 c = cc; 
 f = ff; 
 max = naonulos; // capacidade do vetor tab 
 total = 0; // nenhuma dupla adicionada ainda 
 tab = new dupla[max]; 
} 
 
TVetEsparso::~TVetEsparso() 
{ 
 delete [] tab; 
} 
Representação por vetor de registros (structs) 
 Aplicação 1: MI do TAD TVetEsparso 
 Operador DetInd: 
Matrizes 
24 
int TVetEsparso::DetInd(int i){ 
 if(i >= c && i <= f){// verifica validade 
 int k = -1; 
 for(int t = 0; t < total; t++){ 
 if(tab[t].ind == i){ 
 k = t; // determina índice k no vetor tab 
 break; 
 } 
 } 
 return k;} 
 else 
 cout<<"Indice invalido!"<<endl; 
 exit(1); 
} 
Representação por vetor de registros (structs) 
 Aplicação 1: MI do TAD TVetEsparso 
 Operação Consulta: 
Matrizes 
25 
float TVetEsparso::Consulta(int i) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 return tab[k].val; 
 else 
 return 0; 
} 
Representação por vetor de registros (structs) 
 Aplicação 1: MI do TAD TVetEsparso 
 Operação Atribui: 
Matrizes 
26 
void TVetEsparso::Atribui(int i, float valor) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 tab[k].val = valor; 
 else { 
 if(total < max){ 
 tab[total].ind = i; 
 tab[total].val = valor; 
 total++; 
 } 
 else 
 cout<<"Nao ha espaco no vetor!"<<endl; 
 } 
} 
Matrizes Esparsas Unidimensional 
 Caso haja a necessidade de modificar o vetor V, 
pode-se usar uma das representações estudadas 
anteriormente considerando uma folga. 
 O vetor exemplo V com uma folga de tamanho 3 
pode ser definido em C++ como: 
 Vetor de registros: 
typedef struct {int ind; float val;} dupla; 
dupla tab[7]; 
 Dois vetores: 
int indice[7]; 
float valor[7]; 
Matrizes 
27 
Representação por vetor de registros (structs) 
 Representação esquemática do vetor de dupla’s 
correspondente ao vetor exemplo V, com uma 
folga de tamanho 3: 
 
 
 
 
 Deve-se observar que o ind = 8 das Dupla’s de folga é 
um valor que está fora do intervalo original dos 
possíveis índices de V (-2 a 7). 
 val = 0.0 nas folgas é opcional. 
Matrizes 
28 
0 1 2 3 4 5 6 
TAB = 
-1 2 3 5 8 8 8 
5.3 3.2 -5.4 7.9 0.0 0.0 0.0 
Representação por vetor de registros (structs) 
 Neste formato, é possível fazer algumas alterações 
no vetor V manipulando tab, como, por exemplo: 
 Atribuir o valor 0.0 ao elemento de índice 3 de V: 
Antes 
 
 
 
Depois 
Matrizes 
29 
0 1 2 3 4 5 6 
-1 2 5 8 8 8 8 
5.3 3.2 7.9 0.0 0.0 0.0 0.0 
0 1 2 3 4 5 6 
-1 2 3 5 8 8 8 
5.3 3.2 -5.4 7.9 0.0 0.0 0.0 
 Obs.: 
 Os índices de V em tab devem ser mantidos sempre 
em ordem crescente. Assim, as dupla’s de folga 
ficam sempre no início ou no fim de tab. No 
exemplo, como ind = 8, as dupla’s ficaram no final. 
 Após executar a atribuição V[3] = 0.0, o tamanho da 
folga aumentou para 4. 
Matrizes 
30 
0 1 2 3 4 5 6 
tab = 
-1 2 5 8 8 8 8 
5.3 3.2 7.9 0.0 0.0 0.0 0.0 
Representação por vetor de registros (structs) 
Representação por vetor de registros (structs) 
 Outro exemplo: 
 Executar V[0] = -1.8, isto é, atribuir o valor –1.8 ao 
elemento de índice 0 de V: 
Antes 
 
 
 
Depois 
Matrizes 
31 
0 1 2 3 4 5 6 
tab = 
-1 0 2 5 8 8 8 
5.3 -1.8 3.2 7.9 0.0 0.0 0.0 
0 1 2 3 4 5 6 
tab = 
-1 2 5 8 8 8 8 
5.3 3.2 7.9 0.0 0.0 0.0 0.0 
Representação por vetor de registros (structs) 
Aplicação 3: 
 Desenvolver o TAD (TVetEsparso2) e o seu MI 
para um vetor esparso V1 de elementos reais, cujo 
índice genérico i pode variar de c até f. Obs.: 
 V1 deve ser representado no TVetEsparso2 sem os 
seus elementos nulos, através de um vetor de dupla’s 
(structs) tab1 contendo inicialmente 10 dupla’s de 
folga. 
 Os limites c e f e o número inicial de elementos não 
nulos devem ser definidos em tempo de execução de 
forma que o construtor possa alocar memória 
apropriadamente; 
 Verificar a validade do índice original; (Continua...) 
Matrizes 
32 
Representação por vetor de registros (structs) 
Aplicação 3 (Continuação): 
 O TAD TVetEsparso2 deve conter, além de suas 
operações padrão (Verifica_Validade, Construtor, 
Destrutor, Consulta e Atribuição), as seguintes 
operações auxiliares: 
 Dado um índice válido i de V1, determinar o índice k de 
tab1 que contem a dupla (i, V1[i]). Se a dupla não 
existir, retornar com -1 para k; 
 Dado um índice válido k de tab1, zerar tab1[k].val; 
 Dado um índice válido i de V1 correspondente a um 
elemento representado em tab1 e um valor real r ≠ 0.0, 
alterar o valor val da dupla para r; 
 Dado um índice válido i de V1 correspondente a um 
elemento não representado em tab1 e um valor real 
r ≠ 0.0, incluir a dupla (i, r) em tab1; (Continua...) 
Matrizes 
33 
Representação por vetor de registros (structs) 
Aplicação 3 (Continuação): 
 Desenvolver um PA suportado pelo TAD 
TVetEsparso2 que utiliza o vetor V1 de 
elementos reais com índice variando no intervalo 
[-30, 72], sendo V1[-28] = 47.0, V1[-15] = 4.5, 
V1[-7] = -39.8, V1 [-6] = 1.0, V1 [0] = 5.4, 
V1 [18] = 43.0, V1 [33] = 3.3, V1 [35] = 47.9, 
V1 [59] = -3.7, V1 [72] = 5.2 e todos os demais 
elementos são nulos. Em seguida, ler 10 conjuntos 
de dois valores, i inteiro e r real e atribuir r a 
V1[i]. Finalmente, imprimir todos os pares i e 
V1[i] dos elementos não nulos de V1. 
Matrizes 
34 
Representação por vetor de registros (structs) 
 Aplicação 3: TAD TVetEsparso2 
Matrizes 
35 
class TVetEsparso2 
{ 
 int c, f; 
 int max; // capacidade máxima do vetor 
 int total; // total de elementos 
 dupla *tab; // vetor de registros 
 int DetInd(int i); 
 void Remove(int k); 
 void Insere(int i, float valor); 
 public: 
 TVetEsparso2(int cc, int ff, int naonulos); 
 float Consulta(int i); 
 void Atribui(int i, float valor); 
 ~TVetEsparso2(); 
}; 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Construtor: 
Matrizes 
36 
TVetEsparso2::TVetEsparso2(int cc,int ff,int naonulos) 
{ 
 c = cc; 
 f = ff; 
 max = naonulos + 10; // número de não nulos + folga 
 total = 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; 
 } 
} 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Destrutor: 
Matrizes 
37 
TVetEsparso2::~TVetEsparso2() 
{ 
 delete [] tab; 
} 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Operação DetInd: 
Matrizes 
38 
int TVetEsparso2::DetInd(int i) 
{ 
 if(i >= c && i <= f) { 
 int k = -1; 
 for(int t = 0; t < total; t++) { 
 if(tab[t].ind == i){ 
 k = t; 
 break; 
 } 
 } 
 return k; 
 } 
 else{cout<<"Indice invalido!"<<endl; 
 exit(1);} 
} 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Operação Consulta: 
Matrizes 
39 
float TVetEsparso2::Consulta(int i) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 return tab[k].val; 
 else 
 return 0; 
} 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Operação Atribui: 
Matrizes 
40 
void TVetEsparso2::Atribui(int i, float valor) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 { 
 if(valor == 0.0) // remove o elemento (dupla) 
 Remove(k); 
 else 
 tab[k].val = valor; // atualiza o valor 
 } 
 else 
 Insere(i, valor); // insere uma nova dupla 
} 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Operação Remove: 
Matrizes 
41 
void TVetEsparso2::Remove(int k) 
{// zera o elemento (dupla) de índice k 
 int t; 
 for(t = k; t < total-1; t++) 
 {// desloca duplas de (k+1) a total para esquerda 
 tab[t].ind = tab[t+1].ind; 
 tab[t].val = tab[t+1].val; 
 } 
 tab[total].ind = f1+1;//inclui uma folga no final 
 tab[total].val = 0.0; 
 total--; 
} 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Operação Insere: 
Matrizes 
42 
void TVetEsparso2::Insere(int i, float valor) 
{ 
 if(total < max){ 
 int t = 0; 
 // inserir o índice na ordem correta 
 while(t < total && tab[t].ind < i) 
 t++; 
 // ... continua 
Representação por vetor de registros (structs) 
 Aplicação 3: MI do TAD TVetEsparso2 
 Operação Insere: 
Matrizes 
43 
 // ... continua 
 for(int m = total; m > t; m--){ 
 //desloca pra direita até t, para abrir espaço 
 tab[m].ind = tab[m-1].ind; 
 tab[m].val = tab[m-1].val; 
 } 
 // insere dupla na posição t 
 tab[t].ind = i; 
 tab[t].val = valor; 
 total++; 
 } 
 else 
 cout<<"Nao ha espaco!"<<endl; 
} 
Matrizes Esparsas Multidimensional 
 Pode-se usar representações análogas às das 
unidimensionais. 
 Seja, por exemplo, uma matriz esparsa 
bidimensional M. Pode-se fazer a representação 
dos seus elementos não nulos através de: 
 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; 
 um vetor de TRIPLA’s: índice de linhas, índice de 
colunas e valor do elemento. 
 Em ambos os casos, pode-se considerar uma 
folga, dependendo da necessidade. 
Matrizes 
44 
Representação por vetor de registros (structs) 
Aplicação 4: 
 Desenvolver o TAD (TMat2DEsparsa) e o seu MI 
para uma matriz bidimensional esparsa M de 
elementos reais, cujo índice de linha i varia de c1 
até f1 e o de coluna j de c2 até f2. Obs.: 
 M deve ser representada no TMat2DEsparsa sem os 
seus elementos nulos, através de uma das 
representações estudadas e contendo inicialmente 
uma folga de 10% do total de seus elementos. 
 Os limites c1, f1, c2 e f2 e o número inicial de 
elementos não nulos devem ser definidos em tempo 
de execução de forma que o construtor possa alocar 
memória apropriadamente; 
Matrizes 
45 
Matrizes bidimensionais 
 Aplicação 4: TAD TMat2DEsparsa 
Matrizes 
46 
// Struct contendo uma tripla (linha, coluna, valor) 
typedef struct 
{ 
 int lin; 
 int col; 
 float val; 
}tripla; 
Matrizes bidimensionais 
 Aplicação 4: TAD TMat2DEsparsa 
Matrizes 
47 
class TMat2DEsparsa 
{ 
 int c1, f1; // limites do indice de linha 
 int c2, f2; // limites do indice de coluna 
 int max; // capacidade máxima do vetor 
 int total; // total de triplas de tab 
 tripla *tab; // vetor de registros 
 int DetInd(int i, int j); 
 void Remove(int k); 
 void Insere(int i, int j, float valor); 
 public: 
 TMat2DEsparsa(int cc1,int ff1,int cc2,int ff2, 
 int naonulos); 
 float Consulta(int i, int j); 
 void Atribui(int i, int j, float valor); 
 ~TMat2DEsparsa(); 
}; 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Construtor: 
Matrizes 
48 
TMat2DEsparsa::TMat2DEsparsa(int cc1, int ff1, int cc2, 
 int ff2, int naonulos) 
{ 
 c1 = cc1; 
 f1 = ff1; 
 c2 = cc2; 
 f2 = ff2; 
 max = naonulos + ((f1-c1+1)*(f2-c2+1) / 10);//não 
 //nulos + folga 
 total = 0; 
 tab = new Tripla[max]; 
 // ... continua 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Construtor: 
Matrizes 
49 
 // ... continua 
 // 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; 
 } 
} 
Representação por vetor de registros (structs) 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Destrutor: 
Matrizes 
50 
TMat2DEsparsa::~TMat2DEsparsa() 
{ 
 delete [] tab; 
} 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Operação DetInd: 
Matrizes 
51 
int TMat2DEsparsa::DetInd(int i, int j) 
{ 
 if(i >= c1 && i <= f1 && j >= c2 && j <= f2){ 
 int k = -1; 
 for(int t = 0; t < total; t++) { 
 if(tab[t].lin == i && tab[t].col == j){ 
 k = t; 
 break; 
 } 
 } 
 return k; 
 } 
 // ... continua 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Operação DetInd: 
Matrizes 
52 
 // ... continua 
 else 
 { 
 cout<<"Indice invalido!"<<endl; 
 exit(1); 
 } 
} 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Operação Consulta: 
Matrizes 
53 
float TMat2DEsparsa::Consulta(int i, int j) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 return tab[k].val; 
 else 
 return 0; 
} 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Operação Atribui: 
Matrizes 
54 
void TMat2DEsparsa::Atribui(int i, int j, float valor) 
{ 
 int k = DetInd(i, j); 
 if(k != -1) 
 { 
 if(valor == 0.0) // remove a tripla 
 Remove(k); 
 else 
 tab[k].val = valor; 
 } 
 else 
 Insere(i, j, valor); 
} 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Operação Remove: 
Matrizes 
55 
void TMat2DEsparsa::Remove(int k) 
{// remove a tripla da posição k de tab 
 int t; 
 for(t = k; t < total-1; t++){ 
 // desloca tripla’s de (k+1) a total para esquerda 
 tab[t].lin = tab[t+1].lin; 
 tab[t].col = tab[t+1].col; 
 tab[t].val = tab[t+1].val; 
 } 
 tab[total].lin = f1+1;//inclui uma tripla de folga 
 tab[total].col = f2+1; 
 tab[total].val = 0.0; 
 total--; 
} 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Operação Insere: 
Matrizes 
56 
void TMat2DEsparsa::Insere(int i, int j, float valor) 
{ 
 if(total < max){ 
 int t = 0; 
 // inserir o índice na ordem correta 
 while(t < total){ 
 if(tab[t].lin > i) 
 break; 
 if(tab[t].lin == i && tab[t].col > j) 
 break; 
 t++; 
 } 
 // ... continua 
Matrizes bidimensionais 
 Aplicação 4: MI do TAD TMat2DEsparsa 
 Operação Insere: 
Matrizes 
57 
 // ... continua 
 for(int m = total; m > t;m--){ 
 //desloca para direita até t para abrir espaço 
 tab[m].lin = tab[m-1].lin; 
 tab[m].col = tab[m-1].col; 
 tab[m].val = tab[m-1].val; 
 } 
 // insere tripla na posição t 
 tab[t].lin = i; 
 tab[t].col = j; 
 tab[t].val = valor; 
 total++; 
 } 
 else 
 cout<<"Nao ha espaco!"<<endl; 
}