Ejemplo de definición de matriz escasa y uso de la estructura de datos de Java

Este artículo describe la definición y el uso de la matriz dispersa de las estructuras de datos Java. Compártelo para su referencia, como sigue:

Clase triple para elementos distintos de la matriz escasa:

 paquete com.clarck.dataStructure.matrix;/** * Almacenamiento comprimido de matriz dispersa * * clase triple de elementos distintos de cero de matriz dispersa * * @author clarck * */public class triple implementa comparable <triple> {// número de fila, columna, valor de elemento, permisos de acceso predeterminado int fila, columna, valor; public triple (int row, int columna, int value) {if (fila <0 || columna <0) {tirar nueva ilegalArgumentException ("El número de fila/columna de tripletes de elementos de matriz dispersos no es positivo"); } this.row = fila; this.colum = columna; this.Value = value; } / ** * Copie el constructor y copie un triple * * @param elem * / public triple (triple elem) {this (elem.row, elem.colum, elem.value); } @Override public string toString () {return "(" + row + "," + columna + "," + valor + ")"; } /*** ¿Son iguales los dos triples? Compare los valores de posición y elemento*/ public boolean iguales (object obj) {if (! (Obj instanciaf triple)) return false; Triple elem = (triple) obj; Devuelve this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /*** Compare los tamaños de dos trillizos de acuerdo con la posición del triplete, independientemente del valor del elemento, y acuerde el orden de la clasificación de trillizos* /@Override public int Compareto (triple elem) {// El objeto de triplete actual es pequeño if (this.row <Elrow || this.row == Elem.row && this.colum <elem.colum) // igual, diferente del método igual if (this.row == elem.row && this.colum == elem.colum) return 0; // El objeto triple actual es una gran retorno 1; } / *** además, += función de operador* @param término* / public void add (triple término) {if (this.compareto (término) == 0) this.value += term.value; De lo contrario, arroje nuevo IllegalArgumentException ("Los exponentes de los dos elementos son diferentes y no se pueden agregar"); } /** * Convención para eliminar elementos * * @return * /public boolean removable () {// elementos no almacenados como 0 return this.value == 0; } / *** Devuelve un triple de un elemento de matriz de posición simétrica* @return* / public triple tosymmetry () {return new triple (this.colum, this.row, this.value); } / ** * Operación de adición, operador de sobrecarga + * @return * / public triple plus (triple término) {triple tmp = new triple (this); tmp.add (término); return tmp; }}

Clases de matriz escasa almacenadas en orden por triplicado:

 package com.clarck.datastructure.matrix;import com.clarck.datastructure.linear.SeqList;/** * Compressed storage of sparse matrix* * Sparse matrix triple order table* * Sparse matrix class stored in triple order* * @author clarck * */public class SeqSparseMatrix { // Matrix rows and columns private int filas, columnas; // Tabla de orden triple de matriz dispersa Seqlist privado <triple> lista; / ** * Construya filas de filas, columnas columna cero matriz * * @param filas * @param columnas */ public seqsparsematrix (int rows, int columnas) {if (filas <= 0 || columnas <= 0) tirar nueva ilegalargumentException ("El número de filas o columnas de Matrix no es positiva"); this.rows = filas; this.columns = columnas; // Construye una tabla de pedido vacía y ejecute el constructor seqlist () this.list = new seqList <Pretriple> (); } public SEQSPARSEMATRIX (int filas, int columnas, triple [] elems) {this (filas, columnas); // inserta un triple de un elemento en orden principal para (int i = 0; i <elems.length; i ++) this.set (elems [i]); } / ** * Devuelve el elemento de columna J-th de la fila de matriz y la columna, el algoritmo de búsqueda de orden de la tabla de orden de clasificación, o (n) * * @param i * @param j * @return * / public int get (int i, int j) {if (i <0 || i> = rows || j <0 || j> = columnas) taller nuevo índice de indexceptualception ("" la rail de la rima de la roya de la roya de la rima de la rima de la rima de la roya de la roya de la roya de la roya de la roya de la roya de la roya de la matriz de sale de los límites "); Triple elemento = nuevo triple (i, j, 0); int k = 0; Triple elem = this.list.get (k); // Encuentra objetos de elementos en la lista de orden de clasificación mientras (k <this.list.length () && item.compareto (elem)> = 0) {// solo compara las posiciones de triple elementos, es decir, elem.row == i && elem.column == j if (item.compareto (elem) == 0) return Elem.value; // encontrar (i, j), return matrix element k ++; elem = this.list.get (k); } return 0; } / ** * Establecer elemento matriz con triple * @param elem * / public void set (triple elem) {this.set (elem.row, elem.colum, elem.value); } / ** * Establezca el valor del elemento de la columna de la columna de la matriz en valor, cambie o inserta un triple de un elemento en la lista de orden de clasificación en el orden principal de las filas de la matriz, o (n) * * @param fila * @param columna * @param valor * / public void set (int row, int columna, int value) {// no elemento almacenado como 0 if (value == 0) regreso; if (fila> = this.rows || columna> = this.columns) tirar nueva ilegalargumentException ("el número de fila o columna de triple fuera de los límites"); Triple elem = new triple (fila, columna, valor); int i = 0; // Encuentre el objeto Elem en la tabla ordenada de orden triple, o cambie o inserte mientras (i <this.list.length ()) {triple item = this.list.get (i); // Si existe elem, cambie el elemento de la matriz de posición if (elem.comppareto (item) == 0) {// Establezca el elemento i-th de la tabla de orden para elem.list.set (i, elem); devolver; } // caminar hacia atrás cuando elem es grande (elem.compareto (item)> = 0) i ++; de lo contrario rompe; } this.list.insert (i, elem); } @Override public string toString () {String str = "Tabla de orden triple:" + this.list.ToString () + "/n"; str + = "Sparse Matrix" + this.getClass (). GetSimpLename () + "(" + filas + " *" + columnas + "): /n"; int k = 0; // Devuelve el elemento k-th, si el número de secuencia especificado K no es válido, devuelve nulo triple elem = this.list.get (k ++); for (int i = 0; i <this.rows; i ++) {for (int j = 0; j <this.columns; j ++) if (elem! = null && i == elem.row && j == elem.colum) {str+= string.format ("%4d", elem.value); elem = this.list.get (k ++); } else {str += string.format ("%4d", 0); } str += "/n"; } return str; } / ** * Devuelve la matriz donde se agrega la matriz actual a smat, smatc = this+smat, no cambia la matriz actual, el algoritmo se suma a dos polinomios * * @param smat * @return * / public seqsparsematrix plus (seqsparsematrix smat) {if (this.rows smat.columns) arroje una nueva IllegalArgumentException ("Las dos matrices tienen diferentes órdenes y no se pueden agregar"); // construir filas*columnas Matriz cero SeqsParsematrix SmartC = new SEQSPARSEMATRIX (this.rows, this.columns); int i = 0, j = 0; // atraviesa la tabla de orden de las dos matrices respectivamente mientras (i <this.list.length () && j <smart.list.length ()) {triple elema = this.list.get (i); Triple elemb = smart.list.get (j); // Si dos triples representan elementos de matriz en la misma posición, los valores de elementos correspondientes se agregan si (elema.compareto (elemb) == 0) {// El resultado adicional no es cero, entonces se crea un nuevo elemento si (elema.value + elemb.value! = 0) SmartC.list.append (New Triple (elema.row, elema.colum, elema +value +. Elemb.Value)); i ++; j ++; } else if (elema.compareto (elemb) <0) {// Agregue la copia triple más pequeña a la última de la tabla de pedidos SMATC // Copie el elemento Elema para ejecutar el método del constructor Triple Copy SmartC.List.Append (New Triple (Elema)); i ++; } else {SmartC.List.Append (new Triple (Elemb)); j ++; }} // Agregue la copia triple restante de la tabla de pedido de matriz actual a la última de la tabla de pedidos SMATC mientras (i <this.list.length ()) smartc.list.append (new triple (this.list.get (i ++))); // Agregue la copia triple restante en SMART al último de la tabla de pedidos SMATC mientras (j <smartc.list.length ()) {triple elem = smat.list.get (j ++); if (elem! = null) {smatc.list.append (nuevo triple (elem)); }} return SmartC; } / ** * La matriz actual se agrega a la matriz SMAT, this+= smat, cambia la matriz actual, y el algoritmo agrega los dos polinomios * * @param smat * / public void add (seqsparsematrix smat) {if (this.Rows! = Smat.rows || IlegalargumentException ("Las dos matrices tienen órdenes diferentes y no se pueden agregar"); int i = 0, j = 0; // insertar (o agregar) cada triplete de MAT en la tabla de orden de triplete de matriz actual (i <this.list.length () && j <smat.list.length ()) {triple elema = this.list.get (i); Triple elemb = smart.list.get (j); // Si dos trillizos representan elementos de matriz en la misma posición, los valores del elemento correspondiente se agregan si (elema.compareto (elemb) == 0) {// El resultado adicional no es 0, entonces se crea un nuevo elemento if (elema.value +elemb.value! = 0) this.list.set (i ++, nuevo triple (elema.row, ello.colum, elema, elema. Elemb.Value)); de lo contrario este.list.remove (i); j ++; } else if (elema.compareto (elemb) <0) {// Continúe buscando el elemento inserto del elemento Elemble i ++; } else {// Copie el elemento Elember para insertar el elemento ésimo como this.list.insert (i ++, new triple (elemb)); j ++; }} // Copie los triples restantes en MAT en la tabla de orden de triplete de matriz actual (j <smat.list.length ()) {this.list.append (new triple (smat.list.get (j ++))); }} // Copia profunda pública seqsparsematrix (seqsparsematrix smat) {this (smat.rows, smat.columns); // crear una tabla de pedido vacía, capacidad predeterminada this.list = new seqlist <triple> (); // Copiar todos los objetos triples en smat para (int i = 0; i <smat.list.length (); i ++) this.list.append (new triple (smat.list.get (i))); } / *** Compare si dos matrices son iguales* / public boolean iguales (object obj) {if (this == obj) return true; if (! (OBJ instancia de seqsparsematrix)) return false; SeqsParSematrix smat = (seqsparsematrix) obj; devuelve this.rows == smat.rows && this.columns == smat.columns && this.list.equals (smat.list); } /*** return Transpose Matrix* @return* /public SEQSPARSEMATRIX Transpose () {// Construye una matriz cero, especifique el número de filas y columnas Seqsparsematrix trans = new SEQSParSematrix (columnas, filas); for (int i = 0; i <this.list.length (); i ++) {// inserta el triple trans.set (this.list.get (i) .Tosymmetry ()); } return trans; }}

Clase de prueba:

 paquete com.clarck.dataStructure.matrix;/** * Almacenamiento comprimido de la matriz dispersa * * Tabla de orden triple de matriz dispersa * * Matriz dispersa representada por la tabla de orden triple y sus operaciones de adición * * @author clarck * */public class seqsematrix_test {public static void main (string args []) nuevo triple (0, 2, 11), nuevo triple (0, 4, 17), nuevo triple (1, 1, 20), nuevo triple (3, 0, 19), nuevo triple (3, 5, 28), nuevo triple (4, 4, 50)}; Seqsparsematrix smata = new seqsparsematrix (5, 6, Elemsa); System.out.print ("A" + Smata.ToString ()); Triple [] elemsb = {new triple (0, 2, -11), new triple (0, 4, -17), new triple (2, 3, 51), new triple (3, 0, 10), new triple (4, 5, 99), nuevo triple (1, 1, 0)}; Seqsparsematrix smatb = new seqsparsematrix (5,6, elemsb); System.out.print ("B" + Smatb.ToString ()); Seqsparsematrix smatc = smata.plus (smatb); System.out.print ("C = A+B"+Smatc.ToString ()); System.out.println (); smata.add (smatb); System.out.print ("A + = B" + Smata.ToString ()); System.out.println ("C.Equals (a)?" + Smatc.equals (smata)); Seqsparsematrix smatd = new SeqsParsematrix (SMATB); smatb.set (0,2,1); System.out.print ("B" + Smatb.ToString ()); System.out.print ("D" + Smatd.ToString ()); System.out.println ("A Transpose" + Smata.Transpose (). ToString ()); }}

Resultados de ejecución:

 A Triple order table: ((0, 2, 11), (0, 4, 17), (1, 1, 20), (3, 0, 19), (3, 5, 28), (4, 4, 50)) Sparse matrix SeqSparseMatrix(5 * 6): 0 0 11 0 17 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 28 0 0 0 0 0 0 50 0B Triple order table: ((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))Sparse Matrix SeqSparseMatrix(5 * 6): 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 28 0 0 0 0 0 50 99A+=B triple order table: ((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99)) sparse matrix SeqSparseMatrix(5 * 6): 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 0 28 0 0 0 0 0 0 50 99C.equals(A)?trueB triple order table: ((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))Sparse Matrix SeqSparseMatrix(5 * 6): 0 0 1 0 -17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 99A transposed triple order table: ((0, 3, 29), (1, 1, 20), (3, 2, 51), (4, 4, 50), (5, 3, 28), (5, 4, 99)) Matriz dispersa SeqsParSematrix (6 * 5): 0 0 0 0 29 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 28 99 99

Para obtener más información sobre los algoritmos de Java, los lectores interesados ​​en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""

Espero que este artículo sea útil para la programación Java de todos.