Artikel ini menjelaskan definisi dan penggunaan matriks jarang struktur data Java. Bagikan untuk referensi Anda, sebagai berikut:
Triple Class untuk elemen matriks nol yang jarang:
Paket com.clarck.dataStructure.matrix;/** * Penyimpanan terkompresi dari matriks jarang * * Kelas triple dari elemen non-nol dari matriks jarang * * @author clarck * */kelas publik mengimplementasikan row yang dapat dibandingkan <triple> {// nomor baris, nomor kolom, nilai elemen nilai, nilai akses default <triple> {// nomor kolom, nilai kolom, nilai elemen, nilai akses default Intclement <triple> {// nomor kolom, nilai kolom, nilai elemen nilai permisuhan default interclement <tripel triple publik (baris int, kolom int, nilai int) {if (baris <0 || kolom <0) {lempar baru illegalArgumentException ("Jumlah baris/kolom triplet elemen matriks jarang tidak positif"); } this.row = row; this.colum = kolom; this.value = nilai; } / ** * Salin konstruktor dan salin triple * * @param elem * / public triple (triple elem) {this (elem.row, elem.colum, elem.value); } @Override public string toString () {return "(" + row + "," + column + "," + value + ")"; } /*** Apakah kedua tiga kali lipat sama? Bandingkan Nilai Posisi dan Elemen*/ Public Boolean Equals (Object Obj) {if (! (Obj instance dari Triple)) Return False; Triple elem = (triple) obj; kembalikan this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /*** Bandingkan ukuran dua kembar tiga sesuai dengan posisi triplet, terlepas dari nilai elemen, dan setujui urutan triplet penyortiran* /@override int compareto (triple elem) {// objek triplet saat ini kecil (elem.row || this.row == elem.row & & this. // sama, berbeda dari metode Equals if (this.row == elem.row && this.colum == elem.colum) return 0; // objek triple saat ini adalah pengembalian besar 1; } / *** penambahan, += fungsi operator* @param istilah* / public void add (triple istilah) {if (this.Compareto (term) == 0) this.value += term.value; Lain melempar IllegalArgumentException baru ("eksponen dari dua item berbeda, dan tidak dapat ditambahkan"); } /** * Konvensi untuk menghapus elemen * * @return * /public boolean removable () {// elemen tidak disimpan sebagai 0 kembalikan this.value == 0; } / *** Mengembalikan triple dari elemen matriks posisi simetris* @return* / triple tosimmetry () {return triple baru (this.colum, this.row, this.value); } / ** * Operasi tambahan, operator kelebihan muatan + * @return * / public triple plus (triple istilah) {triple tmp = triple baru (ini); tmp.add (istilah); mengembalikan tmp; }}Kelas matriks jarang disimpan dalam urutan rangkap tiga:
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 baris, kolom; // jarang matriks triple order tabel private seqlist <fliple> daftar; /** * Construct rows rows, columns column zero matrix* * @param rows * @param columns */ public SeqSparseMatrix(int rows, int columns) { if (rows <= 0 || columns <= 0) throw new IllegalArgumentException("The number of rows or columns of matrix is non-positive"); this.rows = baris; this.columns = kolom; // Bangun tabel pesanan kosong dan jalankan konstruktor seqlist () this.list = SEQList baru <Priple> (); } public seqsparseMatrix (int baris, kolom int, triple [] elem) {this (baris, kolom); // Masukkan triple suatu elemen dalam urutan utama untuk (int i = 0; i <elems.length; i ++) this.set (elems [i]); } / ** * Mengembalikan elemen kolom j-th dari baris dan kolom matriks, algoritma pencarian pesanan dari tabel pesanan penyortiran, o (n) * * @param i * @param j * @return * / public int get (int i, int j) {if (i <0 || i> = rowsn || j <0 || j> columns (i <0 || i> = baris || j <0 || j> columns (i if (0 || i> = rows || j <0 || j> columns (i if (0 || i> = rows || j <0 || j> = columns) louck (i <0 || i> = rows || j <0 || j> columns (i if (0 || i> = row || j <0 || j> columns) to MOX (i <0 || i> = rows || j <0 || j> columns) to MOX) elemen keluar dari batas "); Triple item = triple baru (i, j, 0); int k = 0; Triple elem = this.list.get (k); // Temukan objek item dalam daftar pesanan penyortiran while (k <this.list.length () && item.Compareto (elem)> = 0) {// Hanya membandingkan posisi elemen triple, yaitu, elem.row == i && elem.column == J if (item.Compareto (elem) == 0) return elem. // temukan (i, j), kembalikan elemen matriks k ++; elem = this.list.get (k); } return 0; } / ** * Atur elemen matriks dengan triple * @param elem * / public void set (triple elem) {this.set (elem.row, elem.colum, elem.value); } / ** * Atur nilai elemen kolom kolom dari matriks ke nilai, ubah atau masukkan triple elemen dalam daftar urutan penyortiran dalam urutan utama baris matriks, o (n) * * @param baris * @param colom * @param value * / public void set (baris int, int kolom, nilai int) { / / tidak ada elemen yang distasikan sebagai 0) public void set (baris int, int kolom, nilai int) { / / tidak ada elemen yang distasikan sebagai 0) set public 0) if nilai 0) no Nilai) { / No Element as stored as stored * / public void (int row, int column, nilai int value) {// No Element as stored as stored * / public void (row row, int colom, value nilai) { / / No Element stored Nilai 0) 0) return; if (row> = this.rows || column> = this.columns) melempar baru ilegalargumentException ("baris atau kolom jumlah triple di luar batas"); Triple elem = triple baru (baris, kolom, nilai); int i = 0; // Temukan objek Elem dalam tabel pesanan tiga yang diurutkan, atau ubah atau masukkan sementara (i <this.list.length ()) {item triple = this.list.get (i); // jika ada elem, ubah elemen matriks posisi if (elem.compareto (item) == 0) {// Atur elemen i-th dari tabel pesanan ke elem this.list.set (i, elem); kembali; } // Berjalan mundur saat elem besar (elem.comppareto (item)> = 0) i ++; Lainnya istirahat; } this.list.insert (i, elem); } @Override Public String ToString () {String str = "Tabel Triple Order:" + this.list.toString () + "/n"; str + = "matriks jarang" + this.getClass (). getsImplename () + "(" + baris + " *" + kolom + "): /n"; int k = 0; // Mengembalikan elemen K-th, jika nomor urutan yang ditentukan K tidak valid, mengembalikan null triple elem = this.list.get (k ++); untuk (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; } / ** * Mengembalikan matriks di mana matriks saat ini ditambahkan ke SMAT, smatc = this+smat, tidak mengubah matriks saat ini, algoritma menambah dua polinomial * * @param smat * @return * / public seqsparsematrix plus (seqsparsematrix smat) {ife. i oUf. smat.columns) melempar IllegalArgumentException baru ("Dua matriks memiliki perintah yang berbeda, dan tidak dapat ditambahkan"); // Bangun baris*kolom nol matriks seqsparsematrix smartc = seqsparsematrix baru (this.rows, this.columns); int i = 0, j = 0; // lintasi tabel pesanan dari dua matriks masing -masing sementara (i <this.list.length () && j <smart.list.length ()) {triple elema = this.list.get (i); Triple elemb = smart.list.get (j); // Jika dua tiga kali lipat mewakili elemen matriks pada posisi yang sama, nilai elemen yang sesuai ditambahkan if (elema.compareto (elemb) == 0) {// Hasil penambahan tidak nol, maka elemen baru dibuat jika (elema.value + elemb.value! = 0) smartc.list.lpertebal (eLema. elemb.value)); i ++; j ++; } else if (elema.compareto (elemb) <0) {// Tambahkan salinan triple yang lebih kecil ke tabel pesanan SMATC terakhir // salin elemen elema untuk menjalankan metode konstruktor copy triple copy smartc.list.append (triple baru (elema)); i ++; } else {smartc.list.append (triple baru (elemb)); j ++; }} // Tambahkan salinan triple yang tersisa dari tabel pesanan matriks saat ini ke tabel pesanan SMATC terakhir sementara (i <this.list.length ()) smartc.list.append (triple baru (this.list.get (i ++)))); // Tambahkan salinan triple yang tersisa di Smart ke yang terakhir dari tabel pesanan SMATC sementara (j <smartc.list.length ()) {triple elem = smat.list.get (j ++); if (elem! = null) {smatc.list.append (triple baru (elem)); }} return smartc; } / ** * Matriks saat ini ditambahkan ke matriks SMAT, this+= smat, ubah matriks saat ini, dan algoritma menambahkan dua polinomial * * @param smat * / public void add (seqsparseMatrix smat) {if (this.rows! = Smat.rows || this.colums) {if (this.rows! = Smat.rows | | colume.colums) {if (this.rows! = Smat.rows | itike.coT.colums) {if (this.rows! = Smat.rows | itike.colums! IllegalargumentException ("Dua matriks memiliki perintah yang berbeda, dan tidak dapat ditambahkan"); int i = 0, j = 0; // masukkan (atau tambahkan) setiap triplet mat ke tabel pesanan triplet matriks saat ini sementara (i <this.list.length () && j <smat.list.length ()) {triple elema = this.list.get (i); Triple elemb = smart.list.get (j); // Jika dua triplet mewakili elemen matriks pada posisi yang sama, nilai elemen yang sesuai ditambahkan if (elema.comppareto (elemb) == 0) {// Hasil penambahan bukan 0, maka elemen baru dibuat jika (elema.value +elemb.value! = 0) this.list.set (i ++, elema. elemb.value)); lain this.list.remove (i); j ++; } else if (elema.compareto (elemb) <0) {// terus mencari elemen insert dari elemen elemb i ++; } else {// Salin elemen elemb untuk memasukkan elemen ith sebagai this.list.insert (i ++, triple baru (elemb)); j ++; }} // Salin tripel yang tersisa di matras ke tabel pesanan triplet matriks saat ini sementara (j <smat.list.length ()) {this.list.append (triple baru (smat.list.get (j ++))); }} // deep copy publik seqsparsematrix (seqsparsematrix smat) {this (smat.rows, smat.columns); // Buat tabel pesanan kosong, kapasitas default this.list = new seqlist <driple> (); // Salin semua objek tiga di SMAT untuk (int i = 0; i <smat.list.length (); i ++) this.list.append (triple baru (smat.list.get (i)))); } / *** Bandingkan apakah dua matriks sama* / public boolean sama (objek obj) {if (this == obj) return true; if (! (obj instance dari seqsparsematrix)) mengembalikan false; Seqsparsematrix smat = (seqsparsematrix) obj; kembalikan this.rows == smat.rows && this.columns == smat.columns && this.list.equals (smat.list); } /*** Mengembalikan transpose matriks* @return* /public seqsparsematrix transpose () {// Bangun matriks nol, tentukan jumlah baris dan kolom seqsparsematrix trans = seqsparsematrix baru (kolom, baris); untuk (int i = 0; i <this.list.length (); i ++) {// Masukkan triple trans.set (this.list.get (i) .tosimmetry ()); } return trans; }}Kelas Tes:
package com.clarck.datastructure.matrix;/** * Compressed storage of sparse matrix* * Sparse matrix triple order table* * Sparse matrix represented by triple order table and its addition operations* * @author clarck * */public class SeqSparseMatrix_test { public static void main(String args[]) { Triple[] elemsa = { new Triple (0, 2, 11), triple baru (0, 4, 17), triple baru (1, 1, 20), triple baru (3, 0, 19), triple baru (3, 5, 28), triple baru (4, 4, 50)}; SEQSPARSEMATRIX SMATA = SEQSPARSEMATRIX BARU (5, 6, ELEMSA); System.out.print ("a" + smata.tostring ()); Triple [] elemsb = {triple baru (0, 2, -11), triple baru (0, 4, -17), triple baru (2, 3, 51), triple baru (3, 0, 10), triple baru (4, 5, 99), triple baru (1, 1, 0)}; SEQSPARSEMATRIX SMATB = SEQSPARSEMATRIX baru (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 = SEQSPARSEMATRIX baru (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 ()); }}Hasil Menjalankan:
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 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 99A transposed triple order table: ((0, 3, 29), (1, 1, 20), (3, 2, 51), (4, 4, 50), (5, 3, 28), (5, 4, 99)) matriks jarang 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 0 0 0 0 0 0 0 0 0 0 0 28 99
Untuk informasi lebih lanjut tentang algoritma java, pembaca yang tertarik dengan situs ini dapat melihat topik: "struktur data java dan tutorial algoritma", "ringkasan tips node dom java", "ringkasan file operasi java dan direktori" dan "ringkasan tip operasi java cache" tips java "tips java" Tips "Java Cache Tips"
Saya harap artikel ini akan membantu pemrograman Java semua orang.