Índice > Lista > Matriz Esparsa e Lista Cruzada > Implementação

Instituto de Ciências Matemáticas de São Carlos 
Departamento de Computação e Estatística 
SCE182 - Algoritmos e Estruturas de Dados 1 
Profs. Resp.: Graça Pimentel, Maria Cristina e Rosane

Implementação

Definição da ED 
Type
   Preg = ^Reg;
   Lista = Preg;
   Reg  = record
             linha: 1..nl;
             coluna: 1..nc;
             valor: TipoElemento;
             PL,PC: Preg;  { pont p/ prox registro }
          end;
    vetorCol = array[1..nl] of Lista;
    vetorLin = array[1..nc] of Lista;

var
   L: vetorLin;
   C: vetorCol;

1) Acesso ao primeiro elemento não nulo da linha i:

  • L[i] ^

    • 2) Acesso ao elemento i,j:

  • percorrer a lista L[i] até encontrar registro com campo de coluna = j ou
  • percorrer a lista C[j] até encontrar registro com campo de linha = i

    • Operacões com matrizes esparsas

    Além de armazenar matrizes esparsas, as aplicações normalmente exigem a realização de operações sobre essas matrizes, como por exemplo:
  • multiplicar uma dada linha ou coluna por uma constante
  • somar uma constante a todos os elementos de uma linha ou coluna
  • somar duas matrizes esparsas de igual dimensão

    • Como consequência desses operacões, alguns elementos podem deixar de ser nulos, enquanto que outros podem se tornar nulos.

    Por exemplo, ao se somar -4 a coluna 5 do exemplo temos:

    Esse exemplo ilustra que, quando um elemento a(i,j) deve ser eliminado, ele deve ser eliminado, de fato, de duas listas: L[i] e L[j]. O mesmo ocorre quando um elemento deve ser inserido. No algoritmo abaixo, essas operações são feitas por operações inserir e eliminar de matrizes esparsas.

    Algoritmo: Somar k aos elementos da coluna j

      Procedure Soma_col (Var L:vetorLin; Var C:vetorCol; col,lin,j: INTEGER, k: TipoElemento);
  Var p: Lista;
  begin
    p := C[j];
    for i := 1 to lin do
      if p = nil then inserir(i,j,k,L,C,col,lin)
      else
        begin
          if p^.linha  <>  i then       { valor era nulo}
              inserir(i,j,k,L,C,col,lin)    {insere antes de p}
          else
            begin
              p^.valor := p^.valor + k;
              if  p^.valor  = 0 then
                begin
                  p := p^.pl;
                  eliminar(i,j,L,C,col,lin);
                end
              else p := p^.pl;
              end;
           end;
  end;
    -> Fazer os algoritmos de inserir e eliminar
    -> Re-fazer a definição do tipo para Matrizes esparsas de forma que ele fique adequado
    para uma implementação de um TAD Matrizes esparsas. Sugestão: adicionar a definção. um registro que
    armazene o vetor de linhas, o vetor de colunas (L e C), o número atual de linhas da
    matriz, e o número atual de colunas da matriz. Re-fazer inserir, eliminar, e Soma_col
    diante das novas modificações no tipo.
    -> Extrair um TAD Matrizes esparsas. Não esquecer de definir operações para inicializar
    o TAD, definindo número de linhas e colunas para a matriz.

    Avaliação de desempenho

    Matriz Esparsa