В этой статье описывается определение и использование редкой матрицы структур данных Java. Поделитесь этим для вашей ссылки, следующим образом:
Тройной класс для редких матриц ненулевых элементов:
Пакет com.clarck.datastructure.matrix;/** * Сжатое хранилище редкой матрицы * * Тройной класс ненулевых элементов редкой матрицы * * @author clarck * */public Class Triple реализует сопоставимые <Triple> {// Номер строки, номер столбца, значение элемента, неверно доступа к доступу public Triple (int row, int column, int value) {if (row <0 || column <0) {throw new allogalargumentException ("ряд/столбец номер триплета элемента матрицы не является положительным"); } this.row = row; this.colum = column; this.value = значение; } / ** * Скопируйте конструктор и скопируйте тройку * * @param elem * / public triple (Triple elem) {this (elem.row, elem.colum, elem.value); } @Override public String toString () {return "(" + row + "," + column + "," + value + ")"; } /*** Равнут ли две тройки? Сравните значения позиции и элемента*/ public boolean equals (Object obj) {if (! (Obj exancef triple)) вернуть false; Triple Elem = (Triple) OBJ; вернуть this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /*** Сравните размеры двух триплетов в соответствии с триплетной позицией, независимо от значения элемента, и согласны с порядком сортировки триплетов* /@override public int compareto (тройной элемент) {// Текущий объект триплета невелик, если (this.row <elem.row || this.row = elem.row && там. // равный, отличается от метода equals if (this.row == elem.row && this.colum == elem.colum) return 0; // текущий тройной объект большой return 1; } / *** Дополнение, += Функция оператора* @param term* / public void add (тройной термин) {if (this.compareto (term) == 0) this.value += term.value; иначе бросить новое allosalargumentException («показатели двух элементов различны и не могут быть добавлены»); } /** * Конвенция о удалении элементов * * @return * /public boolean lementable () {// Элементы не хранятся как 0 возврат this.value == 0; } / *** вернуть тройной элемент матрицы симметричной позиции* @return* / public Triple Tosymmetry () {return new Triple (this.colum, this.row, this.value); } / ** * Операция добавления, оператор перегрузки + * @return * / public Triple Plus (тройной термин) {Triple TMP = new Triple (this); tmp.add (термин); вернуть TMP; }}Северные классы матрицы хранятся в трех экземплярах:
Пакет com.clarck.datastructure.matrix; import com.clarck.datastructure.lineear.seqlist;/** * * ** * ТАБЛИЦА СТИНГОВАЯ СТАРЯ столбцы; // Sparse Matrix Triple Order Table Private Seqlist <Triple> List; / ** * Конструировать строки строк, столбцы столбцы нулевой матрица * * @param Rows * @param Columns */ public seqsparsematrix (int rows, int columns) {if (rows <= 0 || столбцы <= 0) бросают в новую allodalargumentException («количество строк или столбцов матрицы непревзойден»); this.row = rows; this.columns = columns; // Построить пустую таблицу заказа и выполнить конструктор seqlist () this.list = new seqlist <triple> (); } public seqsparsematrix (int rows, int columns, triple [] elems) {this (row, columns); // вставить тройной элемент в основном порядке для (int i = 0; i <elems.length; i ++) this.set (elems [i]); } / ** * вернуть элемент столбца J-TH столбец строки и столбца матрицы, алгоритм поиска заказа таблицы заказа сортировки, O (n) * * @param i * @param j * @return * / public int get (int i, int j) {if (i <0 || i> = Rows || j <0 || j> = j) umdexoutof umbersex oumbrex Элемент выходит за пределы границ »); Triple Item = new Triple (i, J, 0); int k = 0; Triple Elem = this.List.get (k); // Найти объект объектов в списке заказов на сортировку while (k <this.list.length () && item.compareto (elem)> = 0) {// только сравнить позиции тройных элементов, то есть elem.row == i && elem.column == j if (item.compareto (lem) == 0) elem.value; // Найти (i, j), return Matrix Element K ++; elem = this.list.get (k); } return 0; } / ** * Установить элемент матрицы с Triple * @param elem * / public void set (тройной elem) {this.set (elem.row, elem.colum, elem.value); } / ** * Установите значение элемента столбца столбца матрицы на значение, изменение или вставьте тройной элемент в список заказов сортировки в основном порядке строк матрицы, O (n) * * @param row * @param столбец * @param value * / public void set (int row, int value) {// no no letled atement a a (value = value = value = value = value == 0); if (row> = this.rows || column> = = this.columns) бросить new allogalargumentException («строка или номер столбца тройного из границ»); Triple Elem = new Triple (строка, столбец, значение); int i = 0; // Найти объект ELEM в таблице отсортированного тройного заказа, или изменить или вставить while (i <this.list.length ()) {Triple Item = this.list.get (i); // Если Elem существует, измените элемент матрицы позиции if (elem.compareto (item) == 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-й, если 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 = This+SMAT, не изменяет текущую матрицу, алгоритм добавляет к двум полиномам * * @param smat * @return * / public seqsparysematrix plus (seqsparsematrix smat) {if.rows! smat.columns) бросить новое allodalargumentException («Две матрицы имеют разные приказы и не могут быть добавлены»); // Создание строк*Columns Zero Matrix SEQSPARSEMATRIX SMARTC = NEW SEQSPARSEMATRIX (this.Rows, this.columns); int i = 0, j = 0; // Переносить таблицу заказа двух матриц соответственно while (i <this.list.length () && j <smart.list.length ()) {triple elema = this.list.get (i); Тройной elemb = smart.list.get (j); // Если два тройка представляют элементы матрицы в одной и той же позиции, соответствующие значения элементов добавляются, если (elema.compareto (elemb) == 0) {// Результат добавления не нулевой, то новый элемент создается, если (elema.value + elemb.value! elemb.value)); i ++; J ++; } else if (elema.compareto (elemb) <0) {// Добавить меньшую тройную копию в последнюю из таблицы заказа SMATC // Копировать элемент Elema, чтобы выполнить метод конструкции тройной копии SmartC.List.Append (new Triple (elema)); i ++; } else {smartc.list.append (new Triple (elemb)); J ++; }} // Добавить оставшуюся тройную копию текущей таблицы заказов Matrix в последнюю из таблицы заказа SMATC while (i <this.list.length ()) smartc.list.append (new Triple (this.list.get (i ++))); // Добавить оставшуюся тройную копию в SMART в последнюю из таблицы заказа SMATC while (j <smartc.list.length ()) {Triple elem = smat.list.get (j ++); if (elem! = null) {smatc.list.append (new Triple (elem)); }} return smartc; } / ** * Текущая матрица добавляется в матрицу SMAT, This+= SMAT, изменение текущей матрицы, а алгоритм добавляет два полинома * * @param smat * / public add (seqsparsematrix smat) {if (this.rows! AllodalargumentException («две матрицы имеют разные приказы и не могут быть добавлены»); int i = 0, j = 0; // вставить (или добавить) каждую тройку MAT в текущую таблицу триплета Matrix Triplet When (i <this.list.length () && J <smat.list.length ()) {Triple Elema = this.list.get (i); Тройной elemb = smart.list.get (j); // Если два триплета представляют матричные элементы в одной и той же позиции, соответствующие значения элементов добавляются, если (elema.com.pareto (elemb) == 0) {// Результат добавления не 0, то новая элемент создается, если (elema.value +elemb.value! elemb.value)); иначе this.list.remove (i); J ++; } else if (elema.compareto (elemb) <0) {// продолжать искать элемент вставки элемента elemb i ++; } else {// Скопировать элемент elemb, чтобы вставить элемент ith как это. J ++; }} // Скопируйте оставшиеся тройки в мате в текущую таблицу триплета Matrix Triplet When (j <smat.list.length ()) {this.list.append (new Triple (smat.list.get (j ++))); }} // Deep Copy public seqsparsematrix (seqsparsematrix smat) {this (smat.rows, smat.columns); // Создать пустую таблицу заказа, емкость по умолчанию // Скопировать все тройные объекты в SMAT для (int i = 0; i <smat.list.length (); i ++) this.list.append (new Triple (smat.list.get (i))); } / *** Сравните, равны ли две матрицы* / public boolean equals (Object obj) {if (this == obj) вернуть true; if (! (obj экземпляр seqsparsematrix)) вернуть false; Seqsparsematrix smat = (seqsparsematrix) obj; вернуть this.rows == smat.rows && this.columns == smat.columns && this.list.equals (smat.list); } /*** return Transpose Matrix* @return* /public seqsparsematrix transpose () {// Создание нулевой матрицы, укажите количество строк и столбцов seqsparsematrix trans = new seqsparsematrix (столбцы, строки); for (int i = 0; i <this.list.length (); i ++) {// вставить тройной транс.set (this.list.get (i) .tosymmetry ()); } return trans; }}Тестовый класс:
Пакет com.clarck.datastructure.matrix;/** * Сжатый хранение редкой матрицы * * Таблица тройной матрицы Sparse Matrix * * * * * * * * * * * * * * * * * * * * * * * * * * * * Тройной (0, 2, 11), новый тройной (0, 4, 17), новый тройной (1, 1, 20), новый тройной (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), новый тройной (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 ("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 Тройной заказ Таблица: ((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99)). 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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). Таблица: ((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99)) Sparse Matrix Seqsparsematrix (5 * 6): 0 0 0 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, (4, (5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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)) Sparse Matrix 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 28 99
Для получения дополнительной информации об алгоритмах Java, читатели, которые заинтересованы в этом сайте, могут просмотреть темы: «Учебное пособие по структуре данных Java и алгоритм», «Сводка операции Java Dom Node», «Сводка Java File и каталог
Я надеюсь, что эта статья будет полезна для всех Java Programming.