スパースマトリックスの定義とJavaデータ構造の使用の例

この記事では、Javaデータ構造のスパースマトリックスの定義と使用について説明します。次のように、参照のために共有してください。

スパースマトリックス非ゼロ要素のトリプルクラス：

パッケージcom.clarck.dataStructure.matrix;/** *スパースマトリックスの圧縮ストレージ * *スパースマトリックスの非ゼロ要素のトリプルクラス * * @author clarck * */public classトリプル<トリプル> {//行番号、列番号、列番号、デフォルトアクセス許容順、列、列の値。 public Triple（int row、int column、int value）{if（row <0 || column <0）{show new IllegalargumentException（ "スパースマトリックス要素トリプレットの行/列番号は肯定的ではありません"）; } this.row = row; this.colum = column; this.value = value; } / ** *コンストラクターをコピーしてトリプル * * @param elem * / public Triple（triple elem）{this（elem.row、elem.colum、elem.value）; } @Override public String toString（）{return "（" + row + "、" + column + "、" + value + "）"; } /*** 2つのトリプルは等しいですか？位置と要素の値を比較*/ public boolean Equals（Object obj）{if（！（obj instanceof））return false;トリプルエレム=（トリプル）obj; return this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /***要素値に関係なく、トリプレットの位置に応じて2つのトリプレットのサイズを比較し、トリプレットのソートの順序に同意します* /@Override public int compareto（triple elem）{//現在のトリプレットオブジェクトは小さいif（this.row <elem.row || this.row = = elem.ROW && this.colum <1; //等しく、等しい方法とは異なります（this.row == elem.row && this.colum == elem.colum）return 0; //現在のトリプルオブジェクトは大きな返品です1; } / ***追加、 += operator function* @param Term* / public void add（triple Term）{if（this.comPareto（Term）== 0）this.value += value;それ以外の場合は、新しいIllegalargumentExceptionを投げます（「2つの項目の指数は異なり、追加できません」）; } /** *要素を削除するための慣習 * * @return * /public boolean removable（）{// 0として保存されていない要素は0を返します。 } / ***対称位置マトリックス要素のトリプルを返します* @return* / public Triple tosymmetry（）{return new Triple（this.colum、this.row、this.value）; } / ** *追加操作、オーバーロードオペレーター + * @return * / public Triple Plus（トリプル用語）{トリプルTMP = new Triple（this）; tmp.add（用語）; TMPを返します。 }}

3回順序で保存されているスパースマトリックスクラス：

パッケージcom.clarck.datastructure.matrix; Import com.clarck.dataStructure.linear.seqlist;/** *スパースマトリックスの圧縮ストレージ * *スパースマトリックストリプルオーダーテーブル * *トリップオーダーに保存されているスパースマトリックスクラス * * @author clarck */public classプライベートインクロウ、列; //スパースマトリックストリプルオーダーテーブルプライベートseqlist <トリプル>リスト; / ** *列の列を構築する列ゼロマトリックス * * @param rows * @param列 */ public seqsparsematrix（int rows、int columns）{if（rows <= 0 ||列<= 0）新しい違法な列の列（ "列の数または列の数は非陽性です"）; this.rows = rows; this.columns =列; //空の注文テーブルを作成し、seqlist（）constructor this.list = new seqlist <triple>（）を実行します。 } public seqsparsematrix（int rows、int columns、triple [] elems）{this（rows、columns）; //（int i = 0; i <elems.length; i ++）this.set（elems [i]）のトリプルをメイン順序で挿入します。 } /** * Return the j-th column element of the matrix row and column, the order search algorithm of the sorting order table, O(n) * * @param i * @param j * @return */ public int get(int i, int j) { if (i < 0 || i >= rows || j < 0 || j >= columns) throw new IndexOutOfBoundsException("The row or column number of the matrix element範囲外に出ます "）;トリプルアイテム= new Triple（i、j、0）; int k = 0; Triple Elem = this.list.get（k）; //ソートオーダーリストでアイテムオブジェクトを見つけるwhile（k <this.list.length（）&& item.compareto（elem）> = 0）{//トリプル要素の位置のみを比較します。 // find（i、j）、Matrix Element K ++を返します。 Elem = this.list.get（k）; } return 0; } / ** *トリプルで行列要素を設定 * @param elem * / public void set（triple elem）{this.set（elem.row、elem.colum、elem.value）; } / ** *マトリックスの列の列の要素値を設定して、マトリックスの行の主な順序でソートオーダーリストの要素のトリプルを値、変更、または挿入します。 if（row> = this.rows || column> = this.columns）新しいIllegalargumentException（ "boundsのトリプルアウトの行または列番号"）; Triple Elem = new Triple（row、column、value）; int i = 0; //ソートされたトリプルオーダーテーブルでエレムオブジェクトを見つけます。または挿入または挿入while（i <this.list.length（））{triple item = this.list.get（i）; // elemが存在する場合、位置マトリックス要素を変更する場合（elem.compareto（item）== 0）{//注文テーブルのi番目の要素をelem this.list.set（i、elem）;戻る; } // Elemが大きいときに後方に歩く（elem.comPareto（item）> = 0）i ++;それ以外の場合は休憩します。 } this.list.insert（i、elem）; } @Override public String toString（）{string str = "トリプルオーダーテーブル：" + this.list.toString（） + "/n"; str + = "SPARSE MATRIX" + this.getClass（）。getSimplename（） + "（" + rows + " *" + columns + "）： /n"; int k = 0; // k番目の要素を返します。K指定シーケンス番号が無効である場合、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; } / ** *現在のマトリックスがSMATに追加されるマトリックスを返し、SMATC =この+SMATは現在のマトリックスを変更しません。アルゴリズムは2つの多項式 * @param Smat * @return * / public seqsparsematrix plus（seqsparsematrix smat）| | smat！ smat.columns）新しいIllegalargumentException（「2つのマトリックスには異なる順序があり、追加できない」）を投げます）。 // rowsの構築*列ゼロマトリックスseqsparsematrix smartc = new seqsparsematrix（this.rows、this.columns）; int i = 0、j = 0; // 2つのマトリックスの順序表をそれぞれトラバースします（i <this.list.length（）&& j <smart.list.length（））{triple elema = this.list.get（i）; Triple Elemb = smart.list.get（j）; // 2つのトリプルが同じ位置のマトリックス要素を表す場合、対応する要素値が追加されます（elema.compareto（elemb）== 0）{//追加の結果はゼロではありません、その後、新しい要素は（elema.value + elemb.value！= 0）smartc.list.append（elema.row、elema.row、elema.colum、elema.colum、elema.colum、elema.colum、elema.lema.colum、elema.lema.colum.colum.colum、elema.lema.colum.colum、 Elemb.Value））; i ++; J ++; } else if（elema.compareto（elemb）<0）{//小さいトリプルコピーをsmatcオーダーテーブルの最後に追加する// elema要素をコピーして、トリプルコピーコンストラクターメソッドSmartc.list.append（elema）（elema））を実行します。 i ++; } else {smartc.list.append（new Triple（Elemb））; J ++; }} //現在のMatrix Orderテーブルの残りのトリプルコピーをSMATCオーダーテーブルの最後に追加します（i <this.list.length（））smartc.list.append（new Triple（this.list.get（i ++）））; // Smartの残りのトリプルコピーをSMATCオーダーテーブルの最後に追加します。 if（elem！= null）{smatc.list.append（new Triple（Elem））; }} smartcを返します。 } / ** *現在のマトリックスがSMATマトリックスに追加されます。これは+= SMAT、現在のマトリックスを変更し、アルゴリズムは2つの多項式 *を追加します * * @param smat * / public void add（seqsparsematrix smat）{if（this.rows！= smat.rows | | this.columns！= smat.columns！= smat.columns！ IllegalArgumentException（「2つのマトリックスには異なる順序があり、追加できません」）; int i = 0、j = 0; //マットの各トリプレットを現在のマトリックストリプレットオーダーテーブルに挿入（または追加）します（i <this.list.length（）&& j <smat.list.length（））{triple elema = this.list.get（i）; Triple Elemb = smart.list.get（j）; // 2つのトリプレットが同じ位置のマトリックス要素を表す場合、対応する要素値が追加されます（elema.compareto（elemb）== 0）{//追加の結果は0ではありません、次に新しい要素が作成されます（elema.value +elemb.value！= 0）this.list.set（i ++、elema.rema.rema. rema.colum.colum、elema、elema、elema、elema、elema、elema.lema、elema.lema、elema.lema.lema.columa.columa. Elemb.Value））; else this.list.remove（i）; J ++; } else if（elema.compareto（elemb）<0）{// Elemb要素I ++の挿入要素を探し続けます。 } else {// Elemb要素をコピーして、this.list.insert（i ++、new Triple（elemb））としてith要素を挿入します。 J ++; }} //残りのトリプルをマット内のトリプルを現在のマトリックストリプレットオーダーテーブルにコピーしますが、（j <smat.list.length（））{this.list.append（new Triple（smat.list.get（j ++）））; }} //ディープコピーpublic seqsparsematrix（seqsparsematrix smat）{this（smat.rows、smat.columns）; //空の注文テーブル、デフォルト容量this.list = new seqlist <triple>（）; // smatのすべてのトリプルオブジェクトを（int i = 0; i <smat.list.length（）; i ++）this.list.append（new Triple（smat.list.get（i）））; } / *** 2つの行列が等しいかどうかを比較* / public boolean等しい（オブジェクトobj）{if（this == obj）trueを返します。 if（！（obj instanceof seqsparsematrix））falseを返します。 seqsparsematrix smat =（seqsparsematrix）obj; this.rows == smat.rows && this.columns == smat.columns && this.list.equals（smat.list）; } /*** transoppes Matrix* @return* /public seqsparsematrix transpose（）{//ゼロマトリックスの構築、列の数を指定し、seqsparsematrix trans = new seqsparsematrix（列、rows）を指定します。 for（int i = 0; i <this.list.length（）; i ++）{// triple trans.set（this.list.get（i）.tosymmetry（））; } transを返します。 }}

テストクラス：

パッケージcom.clarck.datastructure.matrix;/** *スパースマトリックスの圧縮ストレージ * *スパースマトリックストリプルオーダーテーブル * *トリプルオーダーテーブルとその追加操作 * * @author clarck * */public class seqsparsematrix_test {] {新しいトリプル（0、2、11）、新しいトリプル（0、4、17）、新しいトリプル（1、1、20）、新しいトリプル（3、0、19）、新しいトリプル（3、5、28）、新しいトリプル（4、4、50）}; seqsparsematrix smata = new seqsparsematrix（5、6、elemsa）; System.out.print（ " + smata.toString（））; TRIPLE [] ELEMSB = {新しいトリプル（0、2、-11）、新しいトリプル（0、4、-17）、新しいトリプル（2、3、51）、新しいトリプル（3、0、10）、新しいトリプル（4、5、99）、新しいトリプル（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（ "transpose" + smata.transpose（）。toString（））; }}

実行結果：

トリプルオーダーテーブル：（（0、2、11）、（0、4、17）、（1、1、20）、（3、0、19）、（3、5、28）、（4、4、50））スパースマトリックス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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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トリプルオーダーテーブル：（（0、2、-11）、（0、4、-17）、（2、3、51）、（3、0、10）、（4、5、99））スパースマトリックスSeqsparsematrix（5 * 6）：0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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、1、20）、（2、3、51）、（3、0、29）、（3、5、28）、（4、4、50）、（4、5、99））まばらなマトリックスseqsparsematrix（5 * 6）：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 99c.equals（a）？trueBトリプルオーダーテーブル：（（0、2、1）、（0、4、-17）、（2、3、51）、（3、0、10）、（4、5、99））スパースマトリックスSeqsparsematrix（5 * 6）：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20）、（3、2、51）、（4、4、50）、（5、3、28）、（5、4、99））まばらなマトリックスseqsparsematrix（6 * 5）：0 0 0 29 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。

この記事がみんなのJavaプログラミングに役立つことを願っています。