บทความนี้อธิบายถึงคำจำกัดความและการใช้เมทริกซ์เบาบางของโครงสร้างข้อมูล Java แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
คลาสสามชั้นสำหรับองค์ประกอบที่ไม่เป็นศูนย์เมทริกซ์:
แพ็คเกจ com.clarck.datastructure.matrix;/** * การจัดเก็บข้อมูลบีบอัดของเมทริกซ์เบาบาง * * คลาสสามชั้นขององค์ประกอบที่ไม่ใช่ศูนย์ของเมทริกซ์เบาบาง * * @author clarck * */คลาสสาธารณะคลาสที่เปรียบเทียบได้ Public Triple (Int แถว, คอลัมน์ int, ค่า int) {if (แถว <0 || คอลัมน์ <0) {โยน unlegalargumentException ใหม่ ("หมายเลขแถว/คอลัมน์ของ Triplets Matrix Element Triplets ไม่เป็นบวก"); } this.row = row; this.colum = คอลัมน์; this.value = ค่า; } / ** * คัดลอกคอนสตรัคเตอร์และคัดลอกสาม * * @param elem * / สาธารณะสาม (Triple Elem) {this (elem.row, elem.colum, elem.value); } @Override สตริงสาธารณะ toString () {return "(" + row + "," + คอลัมน์ + "," + value + ")"; } /*** ทั้งสองเท่ากันเท่ากันหรือไม่? เปรียบเทียบค่าตำแหน่งและค่าองค์ประกอบ*/ บูลีนสาธารณะเท่ากับ (Object OBJ) {ถ้า (! (OBJ Instance Triple)) ส่งคืน FALSE; Triple Elem = (สาม) OBJ; ส่งคืน this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /*** เปรียบเทียบขนาดของสอง triplets ตามตำแหน่ง triplet โดยไม่คำนึงถึงค่าองค์ประกอบและเห็นด้วยกับลำดับของการเรียงลำดับ triplets* /@Override public int compareto (Triple Elem) {// วัตถุทริปเล็ตในปัจจุบันมีขนาดเล็กถ้า // เท่ากันแตกต่างจากวิธี Equals ถ้า (this.row == elem.row && this.colum == elem.colum) ส่งคืน 0; // วัตถุทริปเปิ้ลปัจจุบันเป็นผลตอบแทนขนาดใหญ่ 1; } / *** เพิ่มเติม, += ฟังก์ชั่นตัวดำเนินการ* @param term* / โมฆะสาธารณะเพิ่ม (คำศัพท์สามคำ) {ถ้า (this.compareto (เทอม) == 0) this.value += term.value; อื่น ๆ โยน unlegalargumentException ใหม่ ("เลขชี้กำลังของทั้งสองรายการแตกต่างกันและไม่สามารถเพิ่มได้"); } /** * อนุสัญญาลบองค์ประกอบ * * @return * /บูลีนสาธารณะที่ถอดออกได้ () {// องค์ประกอบที่ไม่เก็บเป็น 0 ส่งคืนสิ่งนี้ value == 0; } / *** ส่งคืนสามขององค์ประกอบเมทริกซ์ตำแหน่งสมมาตร* @return* / public tosymmetry () {กลับมาใหม่ Triple ใหม่ (this.colum, this.row, this.value); } / ** * การดำเนินการเพิ่มเติมตัวดำเนินการโอเวอร์โหลด + * @return * / Public Triple Plus (เทอมสาม) {triple tmp = ใหม่สาม (นี่); tmp.add (เทอม); กลับ TMP; -คลาสเมทริกซ์เบาบางที่เก็บไว้ในลำดับสามเท่า:
แพ็คเกจ com.clarck.datastructure.matrix; นำเข้า com.clarck.datastructure.linear.seqlist;/** * การจัดเก็บบีบอัดของเมทริกซ์เบาบาง * * เมทริกซ์สปอร์ทริกซ์ * * * * * * * * * * * * * * * * * * * * * * * * * * * แถวคอลัมน์; // Sparse Matrix Triple Order Table Private Seqlist <Triple> รายการ; / ** * สร้างแถวแถวคอลัมน์คอลัมน์ศูนย์เมทริกซ์ * * @param rows * @param คอลัมน์ */ สาธารณะ seqsparsematrix (แถว int, คอลัมน์ int) {ถ้า (แถว <= 0 || คอลัมน์ <= 0) this.rows = แถว; this.columns = คอลัมน์; // สร้างตารางคำสั่งที่ว่างเปล่าและเรียกใช้ Seqlist () Constructor this.list = seqlist ใหม่ <Triple> (); } สาธารณะ seqsparsematrix (แถว int, คอลัมน์ int, สาม [] elems) {นี่ (แถว, คอลัมน์); // แทรกสามองค์ประกอบในลำดับหลักสำหรับ (int i = 0; i <elems.length; i ++) this.set (elems [i]); } / ** * ส่งคืนองค์ประกอบคอลัมน์ j-th ของแถวเมทริกซ์และคอลัมน์อัลกอริทึมการค้นหาคำสั่งซื้อของตารางลำดับการเรียงลำดับ o (n) * * @param i * @param j * @return * / public int รับ (int i, int j) {if (i <0 || i> = rows || องค์ประกอบออกไปจากขอบเขต "); triple item = ใหม่สาม (i, j, 0); int k = 0; triple elem = this.list.get (k); // ค้นหาวัตถุรายการในรายการลำดับการเรียงลำดับในขณะที่ (k <this.list.length () && item.compareto (elem)> = 0) {// เปรียบเทียบตำแหน่งขององค์ประกอบสามอย่างเท่านั้นนั่นคือ elem.row == i && elem.column == j if (item.compareto (elem) // find (i, j), ส่งคืนองค์ประกอบเมทริกซ์ k ++; elem = this.list.get (k); } return 0; } / ** * ตั้งค่าองค์ประกอบเมทริกซ์ด้วย triple * @param elem * / ชุดโมฆะสาธารณะ (Triple Elem) {this.set (elem.row, elem.colum, elem.value); } / ** * ตั้งค่าองค์ประกอบของคอลัมน์คอลัมน์ของเมทริกซ์เป็นค่าเปลี่ยนหรือแทรกสามขององค์ประกอบในรายการลำดับการเรียงลำดับในลำดับหลักของแถวของเมทริกซ์, o (n) * * @param แถว * @param คอลัมน์ * @param ค่า @param if (row> = this.rows || คอลัมน์> = this.columns) โยน unlegalargumentException ใหม่ ("หมายเลขแถวหรือคอลัมน์ของสามเท่าของขอบเขต"); Triple Elem = ใหม่ Triple (แถว, คอลัมน์, ค่า); int i = 0; // ค้นหาวัตถุ elem ในตารางลำดับสามเรียงหรือเปลี่ยนหรือแทรกในขณะที่ (i <this.list.length ()) {triple item = this.list.get (i); // ถ้ามี elem ให้เปลี่ยนองค์ประกอบเมทริกซ์ตำแหน่งถ้า (elem.compareto (รายการ) == 0) {// ตั้งค่าองค์ประกอบ i-th ของตารางคำสั่งเป็น elem this.list.set (i, elem); กลับ; } // เดินย้อนกลับเมื่อ Elem มีขนาดใหญ่ (elem.compareto (รายการ)> = 0) i ++; แตกอื่น; } this.list.insert (i, elem); } @Override สตริงสาธารณะ toString () {string str = "ตารางลำดับสาม:" + this.list.toString () + "/n"; str + = "matrix sparse" + this.getClass (). getSimplename () + "(" + rows + " *" + คอลัมน์ + "): /n"; int k = 0; // ส่งคืนองค์ประกอบ k-th หากหมายเลขลำดับ K-specified ไม่ถูกต้องจะส่งคืน null triple elem = this.list.get (k ++); สำหรับ (int i = 0; i <this.rows; i ++) {สำหรับ (int j = 0; j <this.columns; j ++) ถ้า (elem! = null && i == elem.row && j == elem.colum) {str+= string.format ("%4d" elem = this.list.get (k ++); } else {str += string.format ("%4d", 0); } str += "/n"; } return str; } / ** * ส่งคืนเมทริกซ์โดยที่เมทริกซ์ปัจจุบันถูกเพิ่มลงใน smat, smatc = this+smat ไม่เปลี่ยนเมทริกซ์ปัจจุบันอัลกอริทึมจะเพิ่มลงในสองพหุนาม * * @param smat * @return * / seqsparsematrix plus smat.columns) โยน unlegalargumentException ใหม่ ("เมทริกซ์ทั้งสองมีคำสั่งซื้อที่แตกต่างกันและไม่สามารถเพิ่มได้"); // สร้างแถว*คอลัมน์ศูนย์เมทริกซ์ seqsparsematrix smartc = ใหม่ seqsparsematrix (this.rows, this.columns); int i = 0, j = 0; // สำรวจตารางลำดับของเมทริกซ์ทั้งสองตามลำดับในขณะที่ (i <this.list.length () && j <smart.list.length ()) {triple elema = this.list.get (i); triple elemb = smart.list.get (j); // ถ้าสองอเนกประสงค์แสดงองค์ประกอบเมทริกซ์ที่ตำแหน่งเดียวกันค่าองค์ประกอบที่สอดคล้องกันจะถูกเพิ่มถ้า (elema.compareto (elemb) == 0) {// ผลการเพิ่มไม่ใช่ศูนย์ดังนั้นองค์ประกอบใหม่จะถูกสร้างขึ้นหาก (elema.value + elemb.value! elemb.value)); i ++; J ++; } อื่นถ้า (elema.compareto (elemb) <0) {// เพิ่มสำเนาสามสามขนาดเล็กลงในตารางคำสั่งซื้อ SMATC ครั้งสุดท้าย // คัดลอกองค์ประกอบ elema เพื่อเรียกใช้วิธีการสร้างตัวสร้างการคัดลอกสามครั้ง smartc.list.append (ใหม่ Triple (Elema)); i ++; } else {smartc.list.append (ใหม่ Triple (Elemb)); J ++; }} // เพิ่มสำเนาสามที่เหลือของตารางคำสั่งซื้อเมทริกซ์ปัจจุบันไปยังตารางคำสั่งซื้อ SMATC สุดท้ายในขณะที่ (i <this.list.length ()) smartc.list.append (ใหม่ Triple (this.list.get (i ++))); // เพิ่มสำเนาสามที่เหลืออยู่ใน SMART ไปยังตารางคำสั่งซื้อ SMATC สุดท้ายในขณะที่ (j <smartc.list.length ()) {triple elem = smat.list.get (j ++); if (elem! = null) {smatc.list.append (ใหม่สาม (elem)); }} return smartc; } / ** * เมทริกซ์ปัจจุบันถูกเพิ่มเข้าไปในเมทริกซ์ SMAT,+= smat, เปลี่ยนเมทริกซ์ปัจจุบันและอัลกอริทึมเพิ่มสองพหุนาม * * @param smat * / โมฆะสาธารณะเพิ่ม (seqsparsematrix smat) {ถ้า การรับรู้ผิดกฎหมาย ("เมทริกซ์ทั้งสองมีคำสั่งซื้อที่แตกต่างกันและไม่สามารถเพิ่มได้"); int i = 0, j = 0; // แทรก (หรือเพิ่ม) Triplet ของ MAT แต่ละตัวลงในตารางคำสั่ง Matrix Triplet ปัจจุบันในขณะที่ (i <this.list.length () && j <smat.list.length ()) {triple elema = this.list.get (i); triple elemb = smart.list.get (j); // ถ้า triplets สองตัวแสดงองค์ประกอบเมทริกซ์ที่ตำแหน่งเดียวกันค่าองค์ประกอบที่สอดคล้องกันจะถูกเพิ่มถ้า (elema.compareto (elemb) == 0) {// ผลลัพธ์การเพิ่มไม่ใช่ 0 ดังนั้นองค์ประกอบใหม่จะถูกสร้างขึ้นหาก (elema.value +elemb.value! = 0) elemb.value)); อย่างอื่น this.list.remove (i); J ++; } อื่นถ้า (elema.compareto (elemb) <0) {// ดำเนินการต่อเพื่อค้นหาองค์ประกอบแทรกขององค์ประกอบ elemb i ++; } else {// คัดลอกองค์ประกอบ elemb เพื่อแทรกองค์ประกอบ ith เป็น this.list.insert (i ++, ใหม่สาม (elemb)); J ++; }} // คัดลอก Triples ที่เหลืออยู่ใน MAT ลงในตารางคำสั่งซื้อของเมทริกซ์ปัจจุบันในขณะที่ (j <smat.list.length ()) {this.list.append (ใหม่ Triple (smat.list.get (j ++))); }} // การคัดลอกสาธารณะ seqsparsematrix (seqsparsematrix smat) {this (smat.rows, smat.columns); // สร้างตารางคำสั่งที่ว่างเปล่าความจุเริ่มต้น this.list = seqlist ใหม่ <Rriple> (); // คัดลอกวัตถุสามอย่างทั้งหมดใน smat สำหรับ (int i = 0; i <smat.list.length (); i ++) this.list.append (ใหม่ Triple (smat.list.get (i))); } / *** เปรียบเทียบว่าเมทริกซ์สองตัวมีค่าเท่ากัน* / บูลีนสาธารณะเท่ากับ (Object OBJ) {ถ้า (นี้ == OBJ) คืนค่าจริงหรือไม่ if (! (OBJ instanceof seqsparsematrix)) ส่งคืน false; seqsparsematrix smat = (seqsparsematrix) obj; ส่งคืนสิ่งนี้ rows == smat.rows && this.columns == smat.columns && this.list.equals (smat.list); } /*** ส่งคืนเมทริกซ์ transpose* @return* /สาธารณะ seqsparsematrix transpose () {// สร้างเมทริกซ์ศูนย์ระบุจำนวนแถวและคอลัมน์ seqsparsematrix trans = seqsparsematrix ใหม่ (คอลัมน์, แถว); สำหรับ (int i = 0; i <this.list.length (); i ++) {// แทรก trans.set สาม (this.list.get (i) .tosymmetry ()); } return trans; -คลาสทดสอบ:
แพ็คเกจ com.clarck.datastructure.matrix;/** * การจัดเก็บบีบอัดของเมทริกซ์เบาบาง * * เมทริกซ์เบาบางตารางลำดับสามคำสั่ง * * เมทริกซ์เบาบางที่แสดงโดยตารางลำดับสามครั้งและการดำเนินการเพิ่มเติม * * @author clarck * * ใหม่สาม (0, 2, 11), ใหม่สาม (0, 4, 17), ใหม่สาม (1, 1, 20), ใหม่สาม (3, 0, 19), ใหม่สาม (3, 5, 28), ใหม่สาม (4, 4, 50)}; seqsparsematrix smata = ใหม่ seqsparsematrix (5, 6, elemsa); System.out.print ("a" + smata.tostring ()); Triple [] Elemsb = {New Triple (0, 2, -11), ใหม่ Triple (0, 4, -17), ใหม่สาม (2, 3, 51), ใหม่สาม (3, 0, 10), ใหม่สาม (4, 5, 99), ใหม่สาม (1, 1, 0)}; seqsparsematrix smatb = ใหม่ 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 = ใหม่ 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 (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 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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)) เมทริกซ์ seqsparsematrix (5 * 6): 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ตารางคำสั่งซื้อ: ((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99)) Matrix Seqsparsematrix Sparse (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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)) Matrix Seqsparsematrix Sparse Sparse (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 0 0 0 0
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน