Cet article décrit la définition et l'utilisation de la matrice clairsemée des structures de données Java. Partagez-le pour votre référence, comme suit:
Triple classe pour les éléments non nuls de matrice clairsemés:
Package com.clarck.datastructure.matrix; / ** * Stockage compressé de la matrice clairsemée * * Triple classe d'éléments non nuls de la matrice clairsemée * * @author Clarck * * / classe publique Triple implémente les permissions comparables <Triple> {// Row Number, Column Number, Element Value, Default Access permissions Int Row, Column, Value; Public Triple (int row, int colmn, int value) {if (row <0 || colonne <0) {lancez new illégalArgumentException ("le numéro de ligne / colonne d'élément matriciel clairsemé des triplés n'est pas positif"); } this.row = row; this.colum = colonne; this.value = valeur; } / ** * Copiez le constructeur et copiez un triple * * @param elem * / public triple (triple elem) {this (elem.row, elem.colum, elem.value); } @Override public String toString () {return "(" + row + "," + colonne + "," + value + ")"; } / ** * Les deux triplets sont-ils égaux? Comparez les valeurs de position et d'élément * / public booléen equals (objet obj) {if (! (Obj instance de triple)) return false; Triple Elem = (triple) obj; return this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } / ** * Comparez les tailles de deux triplés en fonction de la position du triplet, quelle que soit la valeur de l'élément, et acceptez l'ordre du tri des triplés * / @Override public int compareto (triple elem) {// L'objet triplet actuel est petit if (this.row <elem.row || this.row == elem.row && this.row <elem. // égal, différent de la méthode égaux if (this.row == elem.row && this.colum == elem.colum) return 0; // L'objet triple actuel est un grand retour 1; } / ** * addition, + = fonction d'opérateur * @param term * / public void add (triple terme) {if (this.compareto (term) == 0) this.value + = term.value; Sinon, jetez une nouvelle édition d'illégalArgumentException ("Les exposants des deux éléments sont différents et ne peuvent pas être ajoutés"); } / ** * Convention pour supprimer les éléments * * @return * / public boolean amovible () {// éléments non stockés comme 0 return this.value == 0; } / ** * Renvoie un triple d'un élément de matrice de position symétrique * @return * / public triple tosymetry () {return new triple (this.colum, this.row, this.value); } / ** * Opération d'addition, opérateur de surcharge + * @return * / public triple Plus (triple terme) {triple tmp = new triple (this); tmp.add (terme); retour tmp; }}Classes de matrice clairsemé stockées dans l'ordre en triple:
Package com.clarck.datastructure.matrix; import com.clarck.datastructure.linear.seqlist; / ** * Stockage compressé de la matrice clairsemée * * Matrix clairsemée Triple Order Table lignes, colonnes; // Matrix clairsemée Triple Table de commande private seqlist <priple> liste; / ** * Construire des lignes de lignes, des colonnes Colonne Matrix Zero * * @param lignes * @param colonnes * / public seqsparSematrix (intr lignes, int columns) {if (lignes <= 0 || colonnes <= 0) lancent de nouveaux ") de manière illégale"); this.Rows = lignes; this.columns = colonnes; // Construisez une table de commande vide et exécutez le constructeur SEQList () this.list = new seqlist <priple> (); } public seqsparsEmatrix (intr rows, colonnes int, triple [] elems) {this (lignes, colonnes); // insérer un triple d'un élément dans l'ordre principal pour (int i = 0; i <elems.length; i ++) this.set (elems [i]); } / ** * Renvoie l'élément de colonne J -th de la ligne et la colonne de la matrice, l'algorithme de recherche de commande de la table de commande de tri, O (n) * * @param i * @param j * @return * / public int get (int i, int j) {if (i <0 || i> = ROWS || j <0 || j> = colonnes) Throk New INDIDNOUTOFBOUNDSExExe L'élément matriciel sort des limites "); Triple item = new triple (i, j, 0); int k = 0; Triple elem = this.list.get (k); // Trouver des objets d'élément dans la liste des commandes de tri while (k <this.list.length () && item.compareto (elem)> = 0) {// Comparez uniquement les positions des éléments triples, c'est-à-dire elem.row == i && elem.column == j if (item.comPareto (elem) == 0) return elem.value; // trouver (i, j), élément de matrice de retour k ++; elem = this.list.get (k); } return 0; } / ** * Définir l'élément matriciel avec triple * @param elem * / public void set (triple elem) {this.set (elem.row, elem.colum, elem.value); } / ** * Définissez la valeur de l'élément de la colonne de la colonne de la matrice pour valeur, modifier ou insérer un triple d'un élément dans la liste d'ordre de tri dans l'ordre principal des lignes de la matrice, o (n) * * @param row * @param colonne * @param value * / public void set (int row, int colonne, int) {// no element a été stocké comme 0 if (valeur == 0); if (row> = this.Rows || colonne> = this.columns) lancez un nouveau IllégalArgumentException ("le numéro de ligne ou de colonne de triple des limites"); Triple Elem = nouveau triple (ligne, colonne, valeur); int i = 0; // Trouvez l'objet Elem dans la table triple triple triple, ou modifiez ou insérez while (i <this.list.length ()) {triple item = this.list.get (i); // si elem existe, modifiez l'élément de matrice de position if (elem.compareto (item) == 0) {// Définissez le i-tème élément de la table de commande pour elem this.list.set (i, elem); retour; } // marche en arrière lorsque Elem est grand (elem.compareto (item)> = 0) i ++; d'autre se casse; } this.list.insert (i, elem); } @Override public String toString () {String str = "Triple Order Table:" + this.list.tostring () + "/ n"; str + = "Matrix clairsemé" + this.getClass (). getImPlename () + "(" + lignes + "*" + colonnes + "): / n"; int k = 0; // Renvoie l'élément K -th, si le numéro de séquence spécifié par K n'est pas valide, il renvoie null 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; } /** * Return the matrix where the current matrix is added to smat, smatc=this+smat, does not change the current matrix, the algorithm adds to two polynomials* * @param smat * @return */ public SeqSparseMatrix plus(SeqSparseMatrix smat) { if (this.rows != smat.rows || this.columns != smat.columns) lancez un nouveau IllégalArgumentException ("les deux matrices ont des ordres différents et ne peuvent pas être ajoutés"); // Construire des lignes * colonnes zéro matrice seqsparsematrix smartc = new seqsparsematrix (this.rows, this.columns); int i = 0, j = 0; // traverse le tableau de commande des deux matrices respectivement tandis que (i <this.list.length () && j <smart.list.length ()) {triple elema = this.list.get (i); Triple elemb = smart.list.get (j); // Si deux triples représentent des éléments matriciels à la même position, les valeurs d'élément correspondantes sont ajoutées si (elema.compareto (elemb) == 0) {// Le résultat d'addition n'est pas zéro, alors un nouvel élément est créé if (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) {// Ajoutez la plus petite copie triple au dernier de la table de commande SMATC // Copiez l'élément elema pour exécuter la méthode du constructeur à triple copie smartc.list.append (New Triple (elema)); i ++; } else {smartc.List.Apend (new Triple (elemb)); j ++; }} // Ajoutez la triple copie restante de la table de commande de matrice actuelle au dernier de la table de commande SMATC While (i <this.list.length ()) smartc.List.APPEND (nouveau triple (this.list.get (i ++))); // Ajoutez la triple copie restante dans Smart au dernier de la table de commande SMATC while (j <smartc.list.length ()) {triple elem = smat.list.get (j ++); if (elem! = null) {smatc.List.append (new triple (elem)); }} return smartc; } / ** * La matrice actuelle est ajoutée à la matrice SMAT, ce + = smat, changez la matrice actuelle, et l'algorithme ajoute les deux polynômes * * @param smat * / public void add (seqsparsematrix smat) {if (this.Rows! = Smat.Rows || this.columms! = Smat.columnS) Throw IllégalArgumentException ("Les deux matrices ont des ordres différents et ne peuvent pas être ajoutés"); int i = 0, j = 0; // insérer (ou ajouter) chaque triplet de tapis dans la table de commande Triplet Matrix actuelle while (i <this.list.length () && j <smat.list.length ()) {triple elema = this.list.get (i); Triple elemb = smart.list.get (j); // Si deux triplets représentent des éléments matriciels à la même position, les valeurs d'élément correspondantes sont ajoutées si (elema.compareto (elemb) == 0) {// Le résultat d'addition n'est pas 0, alors un nouvel élément est créé if (elema.value + elemb.value! = 0) this.list.set (i ++, new ++ (elema.row, elema.colum elemb.value)); else this.list.remove (i); j ++; } else if (elema.compareto (elemb) <0) {// Continuez à rechercher l'élément d'insert de l'élément elemb i ++; } else {// Copiez l'élément elemb pour insérer le ith élément comme this.list.insert (i ++, new triple (elemb)); j ++; }} // Copiez les triples restants dans le mat dans la table de commande Triplet Matrix actuelle while (j <smat.list.length ()) {this.list.append (new Triple (smat.list.get (j ++))); }} // copie profonde public seqsparsematrix (seqsparsEmatrix smat) {this (smat.rows, smat.columns); // Créer une table de commande vide, capacité par défaut this.list = new Seqlist <Triple> (); // Copiez tous les objets triples dans smat pour (int i = 0; i <smat.list.length (); i ++) this.list.append (new triple (smat.list.get (i))); } / ** * Comparez si deux matrices sont égales * / public booléen égaux (objet obj) {if (this == obj) return true; if (! (obj instance de seqsparsematrix)) renvoie false; SeqsparsEmatrix smat = (seqsparsematrix) obj; return this.Rows == Smat.Rows && this.columns == smat.columns && this.list.equals (smat.list); } / ** * RETOUR Matrice de transposition * @return * / public seqsparsEmatrix transspose () {// Construisez une matrice zéro, spécifiez le nombre de lignes et colonnes seqsparsematrix trans = new SeqsParsEMatrix (colonnes, lignes); for (int i = 0; i <this.list.length (); i ++) {// insérer le triple trans.set (this.list.get (i) .tosymetry ()); } return trans; }}Classe de test:
Package com.clarck.datastructure.matrix; / ** * Stockage compressé de la matrice clairsemée * * Matrix clairsemée Table de commande triple * * Matrice clairsemée représentée par la table de commande triple et ses opérations d'addition * * @Autor Clarck * * / String Args []) Triple (0, 2, 11), nouveau triple (0, 4, 17), nouveau triple (1, 1, 20), nouveau triple (3, 0, 19), nouveau triple (3, 5, 28), nouveau triple (4, 4, 50)}; SeqsparsEmatrix smata = new seqsparsematrix (5, 6, elemsa); System.out.print ("a" + smata.toString ()); Triple [] elemsb = {nouveau triple (0, 2, -11), nouveau triple (0, 4, -17), nouveau triple (2, 3, 51), nouveau triple (3, 0, 10), nouveau triple (4, 5, 99), nouveau 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.Transspose (). ToString ()); }}Résultats en cours:
Une table de commande à triple: ((0, 2, 11), (0, 4, 17), (1, 1, 20), (3, 0, 19), (3, 5, 28), (4, 4, 50))) Matrice clairsemée seqsparsematrix (5 * 6): 0 0 11 0 17 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 50 0b Triple Commande Table 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99)) Matrix clairse Tableau: ((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99)) Matrice clairse 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 50), (5, 3, 28), (5, 4, 99)) Matrice clairsemée seqsparsematrix (6 * 5): 0 0 0 29 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.