تصف هذه المقالة تعريف واستخدام المصفوفة المتفرقة لهياكل بيانات Java. شاركه للرجوع إليه ، على النحو التالي:
الطبقة الثلاثية للعناصر غير الصفراء المصفوفة:
Package com.clarck.datustructure.matrix ؛/** * تخزين مضغوط من المصفوفة المتفرقة * * فئة ثلاثية من العناصر غير الصفر من المصفوفة المتفرقة * * Author Clarck * */فئة عامة ثلاثية الأدوات المماثلة <prople> {رقم صف ، رقم العمود ، قيمة الأسماء الدفالية ، العمود ، القيمة ؛ Public Triple (int row ، عمود int ، القيمة int) {if (الصف <0 || العمود <0) {رمي جديد غير alfictalargumentException ("عدد التوائم المصفوفة المفرقة من العناصر المتفرقة ليست موجبة") ؛ } this.row = row ؛ this.colum = العمود ؛ this.value = القيمة ؛ } / ** * انسخ المُنشئ ونسخ Triple * * param elem * / public Triple (Triple elem) {this (elem.row ، elem.colum ، elem.value) ؛ } Override Public String ToString () {return "(" + ROW + "،" + Column + "،" + value + ")" ؛ } /*** هل الدرز الثيران متساويان؟ قارن بين قيم الموضع والعنصر*/ public boolean يساوي (Object OBJ) {if (! (OBJ مثيل Triple)) إرجاع خطأ ؛ Triple Elem = (Triple) OBJ ؛ إرجاع this.row == elem.row && this.colum == elem.colum && this.value == elem.value ؛ } /*** قارن أحجام اثنين من ثلاثة توائم وفقًا لموضع ثلاثي ، بغض النظر عن قيمة العنصر ، والاتفاق على ترتيب فرز التوائم* /Override public int compareto (triple elem) {// الكائن الثلاثي الحالي صغير إذا كان ذلك (this.row <elem.row هذا. // على قدم المساواة ، يختلف عن طريقة متساوٍ إذا (this.row == elem.row && this.colum == elem.colum) return 0 ؛ // الكائن الثلاثي الحالي هو عائد كبير 1 ؛ } / *** إضافة ، += دالة المشغل* param term* / public void add (Triple Term) {if (this.compareto (term) == 0) this.value += term.value ؛ آخر رمي جديد غير شرعي ("أسماء العنصرين مختلفة ، ولا يمكن إضافتها") ؛ } /** * الاتفاقية لحذف العناصر * * return * /public boolean removable () {// العناصر غير المخزنة كـ 0 إرجاع this.value == 0 ؛ } / *** إرجاع ثلاثة أضعاف من عنصر مصفوفة موضع متماثل* @RETURN* / public Triple Tosymmetry () {return New Triple (this.colum ، this.row ، this.value) ؛ } / ** * عملية الإضافة ، مشغل الحمل الزائد + * return * / Public Triple Plus (Triple Term) {Triple Tmp = New Triple (this) ؛ TMP.Add (المصطلح) ؛ إرجاع TMP ؛ }}فصول المصفوفة المتفرقة المخزنة بترتيب ثلاث نسخ:
package com.clarck.datustructure.matrix ؛ استيراد com.clarck.datustructure.linear.seqlist ؛/** * تخزين مضغوط من المصفوفة المتفرقة * * المصفوفة المتفرقة Triple Order Table * * Perctix Matrix Class Endered in Triple Triple الأعمدة // Matrix Triple Order Table Private SeqList <Liple> قائمة ؛ / ** * إنشاء صفوف الصفوف ، أعمدة الأعمدة صفر مصفوفة * * param صفوف * param أعمدة */ public seqsparsematrix (صفوف int ، أعمدة int) {if (الصفوف <= 0 || أعمدة <= 0) رمي غير قانوني جديد alcalaRgumentException ("عدد الصفوف أو الأعمدة من المصفوفات غير مقصورة") ؛ this.rows = الصفوف ؛ this.columns = الأعمدة ؛ // إنشاء جدول طلب فارغ وقم بتنفيذ مُنشئ SEQLIST () this.list = new seqlist <liple> () ؛ } seqsparsematrix (int int ، أعمدة int ، triple [] elems) {هذا (الصفوف ، الأعمدة) ؛ // أدخل ثلاثية من عنصر بالترتيب الرئيسي لـ (int i = 0 ؛ i <elems.length ؛ i ++) this.set (elems [i]) ؛ } / ** * إرجاع عنصر العمود j-th من صف المصفوفة والعمود ، خوارزمية البحث عن الطلب لجدول ترتيب الفرز ، o (n) * * param i * @param j * @regiret int get (int i ، int j) {if (i 0 || i> = j <0 || j> يخرج من الحدود ") ؛ العنصر الثلاثي = جديد Triple (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 إذا (item.com pareto (elem) == 0) elem.val ؛ // Find (i ، J) ، return matrix element K ++ ؛ elem = this.list.get (k) ؛ } العودة 0 ؛ } / ** * تعيين عنصر المصفوفة مع Triple * param elem * / public void set (Triple elem) {this.set (elem.row ، elem.colum ، elem.value) ؛ } / ** * قم بتعيين قيمة عنصر عمود عمود المصفوفة لقيمة أو تغيير أو إدراج ثلاثية من عنصر في قائمة ترتيب الفرز بالترتيب الرئيسي للصفوف من المصفوفة ، o (n) * * * param row * param column * param value * / public void set (int row ، int value) {no elem if (row> = this.rows || column> = this.columns) رمي جديد alfictalargumentexception ("الصف أو العمود عدد من الحدود الثلاثي") ؛ Triple Elem = New Triple (Row ، Column ، Value) ؛ 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 (item)> = 0) i ++ ؛ استراحة أخرى } this.list.insert (i ، elem) ؛ } Override Public String ToString () {String str = "Triple Order Table:" + this.list.toString () + "/n" ؛ str + = "sparse matrix" + this.getClass (). getSimplename () + "(" + rows + " *" + columns + "): /n" ؛ int k = 0 ؛ // إرجاع العنصر K-Th ، إذا كان رقم التسلسل المحدد K غير صالح ، فإنه يعيد Null Triple Elem = this.list.get (K ++) ؛ لـ (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 ++) ؛ } آخر {str += string.format ("٪ 4D" ، 0) ؛ } str += "/n" ؛ } إرجاع str ؛ } / ** * إرجاع المصفوفة حيث تتم إضافة المصفوفة الحالية إلى SMAT ، smatc = this+smat ، لا تغير المصفوفة الحالية ، وتضيف الخوارزمية إلى اثنين من polynomials * * @param smat * @regurn * / seqsparsematrix plus (seqsparsematrix smat) {if (this.rows! smat.columns) رمي جديد غير unalfalargumentException ("المصفوفتان لهما أوامر مختلفة ، ولا يمكن إضافتها") ؛ // إنشاء صفوف*أعمدة صفر مصفوفة 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! = 0) SmartC.Append.Append elemb.value)) ؛ i ++ ؛ J ++ ؛ } آخر إذا (elema.compareto (elemb) <0) {// أضف نسخة ثلاثية أصغر إلى آخر جدول طلب SMATC // انسخ عنصر elma لتنفيذ طريقة منشئ النسخ الثلاثي SmartC.List.Append (New Triple (Elema)) ؛ i ++ ؛ } آخر {SmartC.List.Append (New Triple (ELEMB)) ؛ J ++ ؛ }} // أضف النسخة الثلاثية المتبقية من جدول ترتيب المصفوفة الحالي إلى آخر جدول ترتيب SMATC بينما (i <this.list.length ()) SmartC.List.Append (New Triple (this.list.get (i ++))) ؛ // أضف النسخة الثلاثية المتبقية في Smart إلى آخر جدول طلب SMATC بينما (j <SmartC.List.Length ()) {Triple elem = smat.list.get (j ++) ؛ if (elem! = null) {smatc.list.append (New Triple (elem)) ؛ }} return SmartC ؛ } / ** * تتم إضافة المصفوفة الحالية إلى مصفوفة SMAT ، هذا+= SMAT ، تغيير المصفوفة الحالية ، وتضيف الخوارزمية اثنين من الحدود * * param smat * / public void add (seqsparsematrix smat) {if (this.rows! = smat.rows غير unalfalArgumentException ("المصفوفتان لها أوامر مختلفة ، ولا يمكن إضافتها") ؛ int i = 0 ، j = 0 ؛ // insert (أو إضافة) كل ثلاثية من MAT في جدول ترتيب Triplet Matrix الحالي بينما (i <this.list.length () && j <smat.list.length ()) {triple elema = this.list.get (i) ؛ Triple Elemb = Smart.List.get (j) ؛ // إذا كان هناك ثلاثة توائم توثيق تمثل عناصر المصفوفة في نفس الموضع ، تتم إضافة قيم العناصر المقابلة إذا (elema.compareto (elemb) == 0) {// نتيجة الإضافة ليست 0 ، ثم يتم إنشاء عنصر جديد إذا (Elema.Value +Elemb.value! elemb.value)) ؛ آخر this.list.remove (i) ؛ J ++ ؛ } آخر إذا (elema.compareto (elemb) <0) {// تابع البحث عن عنصر إدراج لعنصر eLEMB I ++ ؛ } else {// انسخ عنصر eLEMB لإدراج عنصر ITH مثل this.list.insert (i ++ ، new Triple (elemb)) ؛ J ++ ؛ }} // انسخ الثلاثيات المتبقية في حصيرة في جدول ترتيب ثلاثي المصفوفة الحالي بينما (j <smat.list.length ()) {this.list.append (new Triple (smat.list.get (j ++))) ؛ }} // نسخة عميقة seqsparsematrix (seqsparsematrix smat) {this (smat.rows ، smat.columns) ؛ // إنشاء جدول ترتيب فارغ ، سعة افتراضية this.list = new seqlist <prowle> () ؛ // انسخ جميع الكائنات الثلاثية في SMAT لـ (int i = 0 ؛ i <smat.list.length () ؛ i ++) this.list.append (new Triple (smat.list.get (i))) ؛ } / *** قارن ما إذا كانت مصفوفين متساوية* / منطقية عامة متساوية (كائن OBJ) {if (this == obj) return true ؛ if (! (OBJ مثيل من seqsparsematrix)) إرجاع خطأ ؛ seqsparsematrix smat = (seqsparsematrix) obj ؛ إرجاع this.rows == smat.rows && this.columns == smat.columns && this.list.equals (smat.list) ؛ } /*** return transpose matrix* @REGAN* /public seqsparsematrix transposph () {// إنشاء مصفوفة صفر ، حدد عدد الصفوف والأعمدة seqsparsematrix trans = new seqsparsematrix (الأعمدة ، الصفوف) ؛ لـ (int i = 0 ؛ i <this.list.length () ؛ i ++) {// أدخل triple trans.set (this.list.get (i) .tosymmetry ()) ؛ } إرجاع trans ؛ }}فئة الاختبار:
package com.clarck.daturstructure.matrix ؛/** * تخزين مضغوط من المصفوفة المتفرقة * * جدول ترتيب ثلاثي المصفوفة * * المصفوفة المتفرقة الممثلة في جدول الطلبات الثلاثي وعمليات الإضافة * * @Author Clarck */public class seqsparsematrix_test {public static void ( Triple (0 ، 2 ، 11) ، New Triple (0 ، 4 ، 17) ، New Triple (1 ، 1 ، 20) ، New Triple (3 ، 0 ، 19) ، New Triple (3 ، 5 ، 28) ، New 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) ، New Triple (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 = 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 ()) ؛ }}نتائج التشغيل:
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 0 0 0 0 0 0 0 0 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 جدول الطلب: (((0 ، 2 ، 1) ، (0 ، 4 ، -17) ، (2 ، 3 ، 51) ، (3 ، 0 ، 10 ، 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 Order Table: (0 ، 3 ، 50) ، (5 ، 3 ، 28) ، (5 ، 4 ، 99)) المصفوفة المتفرقة seqsparsematrix (6 * 5): 0 0 0 29 0 0 0 0 0 0 0 0 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
لمزيد من المعلومات حول خوارزميات Java ، يمكن للقراء المهتمين بهذا الموقع عرض الموضوعات: "بنية بيانات Java وبرنامج تعليمي الخوارزمية" ، "ملخص" Tips Java ".
آمل أن يكون هذا المقال مفيدًا لبرمجة Java للجميع.