Cálculo com matrizes

Ando fazendo uma revisão em álgebra linear e comecei a criar uma classe para fazer cálculos básicos com matrizes, para auxiliar em cálculos mais complexos posteriormente.

Abaixo segue a classe Matrix.

package br.lalgebra.math.matrix;

import br.lalgebra.math.errors.MatrixError;

public class Matrix
{

 /**
  * figure out the product between a factor and a matrix 
  * @param f
  * @param A
  * @return
  * @throws MatrixError
  */
 public static double[][] productNumber( double f, double A[][] ) throws MatrixError
 {
  double r[][] = null;
  
  if (A.length == 0) 
   throw new MatrixError("There is some empty matrix");

  // matrix A (mxn)  
  int m = A.length; int n = A[0].length;
  
  r = new double[m][n];
  
  for (int i = 0; i < m; i++) {
   for (int j = 0; j < n; j++)
    r[i][j] = f * A[i][j];
  }
  
  return r;
 }
 
 /**
  * figure out the matrix product
  * @param A
  * @param B
  * @return
  */
 public static double[][] product( double A[][], double B[][] ) throws MatrixError
 {
  
  double r[][] = null;
  
  if (A.length == 0 || B.length == 0) 
   throw new MatrixError("There is some empty matrix");
  
  // matrix A (mxn)  
  int m = A.length; int n = A[0].length;
  
  // matrix B (pxq)
  int p = B.length; int q = B[0].length;
  
  if (n != p) 
   throw new MatrixError("The number of columns of matrix A, must be the same of matrix B number of rows");
  
  double aux = 0.0;
  
  // defining the new array
  r = new double[m][q];
  
  // figuring out arrays product
  for (int i = 0; i < m; i++)
   for (int k = 0; k < q; k++) 
   {
    for (int j = 0; j < n; j++) 
     aux += A[i][j] * B[j][k];
    r[i][k] = aux;
    aux = 0;
   }
  
  return r;
 }
 
 public static String getString( double[][] x ) throws MatrixError
 {
  String result = "";

  if (x.length == 0) 
   throw new MatrixError("The matrix is empty");
  
  int m = x.length; int n = x[0].length;
  
  if (n == 0)
   throw new MatrixError("The matrix is empty");
  
  for (int i = 0; i < m; i++) {
   for (int j =0; j < n; j++)
    result += x[i][j] + "\t";
   result += "\n";
  }
  return result;
 }
}

Estruturas de dados com JAVA - Lista encadeada circular

Em uma lista circular, não existem o primeiro e o último nó da mesma forma como explicado nos posts sobre listas simplesmente encadeadas e duplamente encadeadas. Geralmente usamos sentinelas de cabeçalho e rodapé nas estruturas anteriores, porém em uma lista circular, o último elemento possui como próximo, o primeiro elemento. Para percorrer uma lista circular, então é necessário definir um tipo de cursor, que nada mais é do que um nó(elemento) corrente na lista.

Então como nos outros posts, seguem os códigos para melhor entendimento:
A estrutura de dado já está definida conforme o post Lista Simplesmente Encadeada.

A implementação da lista circular segue abaixo:

public class CircleList {
    
    private Node cursor;
    private int size;
    
    /** Creates a new instance of CircleList */
    public CircleList() {
        cursor = null;
        size = 0;
    }
    
    public int size() {
        return size;
    }
    
    public Node getCursor() {
        return cursor;
    }
    
    public void advance() {
        cursor = cursor.getNext();
    }
    
    public void add(Node v) {
        if (cursor == null) {
            v.setNext(v);
            cursor = v;
        } else {
            v.setNext(cursor.getNext());
            cursor.setNext(v);
        }
        size++;
    }
    
    public Node remove() throws IllegalArgumentException {
        
        if (cursor == null)
            throw new IllegalArgumentException("lista vazia");
        
        Node aux = cursor.getNext();
        if (aux == cursor)
            cursor = null;
        else {
            cursor.setNext(aux.getNext());
            aux.setNext(null);
        }
        
        size--;
        return aux;
    }
}

e o exemplo de utilização segue também abaixo:

public class Principal {
    
    private CircleList lista;
    
    public Principal() {
        lista = new CircleList();
        
        lista.add(new Node("A", null));
        lista.add(new Node("B", null)); 
        lista.add(new Node("C", null)); 
    }
    
    public void printLista() {
        Node node = lista.getCursor();
        for(int i=0; i<lista.size(); i++) {
            System.out.println("elemento " + i + " = " + node.getElement());
            lista.advance(); node = lista.getCursor();
        }
    }

    public void clear() {
        while(true) {
            try {
                Node node = lista.remove();
                System.out.println("elemento removido  = " + node.getElement());
            } catch (IllegalArgumentException e) {
                System.out.println(e.getMessage());
                break;
            }
        }        
    }
    
    public static void main(String[] args) {
        Principal me = new Principal();
        me.printLista();
        
        // apos imprimir os elementos testa remover tudo
        me.clear();
    }
 
}

No próximo post, demonstrarei como implementar um tipo de ordenação em uma lista duplamente encadeada.

Estruturas de dados com JAVA - Lista simplesmente encadeada

Neste post, vou iniciar um dos tópcos iniciais sobre algoritmos e estruturas de dados:
Listas simplesmente encadeadas. Dada uma estrutura de dado (pode ser uma classe ou um struct em c), podemos aninhar estes elementos de forma sequencial, onde cada elemento aponta para um próximo elemento até que o último elemento não aponte para mais nada. Neste tipo de estrutura podemos identificar um elemento como sendo o inicial (header) e o elemento final é o que aponta para nada (null).

Abaixo seguem implementações para este tópico.

Definindo a estrutura de dado de um elemento Nó:

public class Node {
    
    private String element;
    private Node next;
    
    public Node(String s, Node n) {
        setElement(s);
        setNext(n);
    }

    public String getElement() {
        return element;
    }

    public void setElement(String element) {
        this.element = element;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
    
}

Abaixo segue a implementação da lista com operações básicas para navegação, inserção e remoção:

public class SList {
    
    private Node head;
    private int size;
    
    /** Creates a new instance of SList */
    public SList() {
        head = null;
        size = 0;
    }
    
    public Node getFirst() throws IllegalArgumentException {
        if (head == null)
            throw new IllegalArgumentException("Lista Vazia");
        return head;
    }
    
    public Node getNext(Node n) throws IllegalArgumentException {
        if (size == 0)
            throw new IllegalArgumentException("Lista vazia");
        if (n.getNext() == null)
            throw new IllegalArgumentException("fim da lista");
        return n.getNext();
    }
    
    public void addFirst(Node v) {
        v.setNext(head);
        head = v;
        size++;
    }
    
    public void addLast(Node v) {
        if (head != null) {
            
            Node aux = null;
            for (aux = head; aux.getNext() != null; aux = aux.getNext() );
            v.setNext(null);
            aux.setNext(v);
            size++;
            
        } else {
            addFirst(v);
        }
    }
    
    public void removeFirst() throws IllegalArgumentException {
        if (size == 0)
            throw new IllegalArgumentException();
        
        Node aux = head;
        head = head.getNext();
        aux.setNext(null);
        size --;        
    }
}

E agora um exemplo de utilização com navagação na lista:

 public class Principal {
    
    private SList lista;
    
    public Principal() {
        lista = new SList();
        
        Node node = new Node("A", null);
        
        lista.addFirst(node);
        
        node = new Node("B", null);
        lista.addFirst(node); 
        
        node = new Node("C", null);
        lista.addFirst(node); 
    }
    
    public void printLista() {
        Node node = lista.getFirst();
        do  {
            System.out.println( "Elemento:" + node.getElement() );
            node = node.getNext();
        } while (node != null);
    }
    
    public static void main(String[] args) {
        Principal me = new Principal();
        me.printLista();
    }
    
}

veja o tópico de listas duplamente encadeadas

Estruturas de dados com JAVA - Lista duplamente encadeada

Neste post, vou colocar um exemplo de implementação de uma lista duplamente encadeada:

primeiro vamos definir a estrutura de dado para cada nó da lista:

package estruturas_de_dados;
public class DNode {
    
    private String element;
    private DNode prev;
    private DNode next;
    
    public DNode(String s, DNode p, DNode n) {
        setElement(s);
        setPrev(p);
        setNext(n);
    }

    public String getElement() {
        return element;
    }

    public void setElement(String element) {
        this.element = element;
    }

    public DNode getPrev() {
        return prev;
    }

    public void setPrev(DNode prev) {
        this.prev = prev;
    }

    public DNode getNext() {
        return next;
    }

    public void setNext(DNode next) {
        this.next = next;
    }
    
    
}

Após definir a estrutura de dado, vamos então implementar a lista duplamente encadeada:

package estruturas_de_dados;

public class DList {

    private int size;
    private DNode head;
    private DNode trailer;
        
    public DList() {
        size = 0;
        head = new DNode("", null, null);
        trailer = new DNode("", head, null);
        head.setNext(trailer);
    }
    
    public int getSize() {
        return size;
    }
    
    public boolean isEmpty() {
        return (size == 0);
    }
    
    public DNode getFirst() throws IllegalArgumentException {
        if (isEmpty())
            throw new IllegalArgumentException();
        return head.getNext();
    }
    
    public DNode getLast() throws IllegalArgumentException {
        if (isEmpty())
            throw new IllegalArgumentException();
        return trailer.getPrev();
    }
    
    public DNode getPrev(DNode v) throws IllegalArgumentException {
        if (v == head)
            throw new IllegalArgumentException();
        return v.getPrev();
    }
    
    public DNode getNext(DNode v) throws IllegalArgumentException {
        if (v == trailer)
            throw new IllegalArgumentException();
        return v.getNext();
    }
    
    public void addFirst(DNode v) {
        addAfter(head, v);
    }
    
    public void addLast(DNode v) {
        addBefore(trailer, v);
    }
    
    public void addAfter(DNode v, DNode z) {
        DNode u = getNext(v);
        v.setNext(z);
        u.setPrev(z);
        z.setNext(u);
        z.setPrev(v);
        size++;
    }
    
    public void addBefore(DNode v, DNode z) {
        DNode u = getPrev(v);
        v.setPrev(z);
        u.setNext(z);
        z.setPrev(u);
        z.setNext(v);
        size++;
    }
    
    public void remove(DNode v) {
        DNode u = getPrev(v);
        DNode w = getNext(v);
        
        u.setNext(w);
        w.setPrev(u);
        
        v.setNext(null);
        v.setPrev(null);
        
        size--;
    }
    
    public boolean hasPrev(DNode v) { return (v != head); }
    
    public boolean hasNext(DNode v) { return (v != trailer); }
    
}

Agora um exemplo de utilização da lista, inserindo elementos e navegando na lista:

public class Principal {
    
    private DList lista;
    
    /** Creates a new instance of Principal */
    public Principal() {
        lista = new DList();
        
        DNode aux = null;
        DNode node = new DNode("A", null, null);
        
        lista.addFirst(node); aux = node;
        
        node = new DNode("B", null, null);
        lista.addAfter(aux, node); aux = node;
        
        node = new DNode("C", null, null);
        lista.addAfter(aux, node); aux = node;
    }
    
    public void printLista() {
        DNode node = lista.getFirst();
        do  {
            System.out.println( "Elemento:" + node.getElement() );
            node = lista.getNext(node);
        } while (lista.hasNext(node));        
    }
    
    public static void main(String[] args) {
        Principal me = new Principal();
        me.printLista();
    }
    
}