稀疏矩阵
表示稀疏矩阵的三元组：
稀疏矩阵常用的压缩存储共有3种：
顺序存储单链表存储十字链表存储
顺序存储
稀疏矩阵三元组顺序表：
表示稀疏矩阵非零元素的三元组：
public class Triple implements Comparable<Triple>{//行号，列号，元素值int row, column, value;public Triple(int row, int column, int value){if (row<0 || column<0)throw new IllegalArgumentException("稀疏矩阵元素三元组的行/列序号非正数。");this.row = row;this.column = column;this.value = value;}//拷贝构造方法，复制一个三元组public Triple(Triple elem){this(elem.row, elem.column, elem.value);}//返回三元组描述字符串public String toString(){return "(" + row + "," + column + "," + value + ")";}//两个三元组比较是否相等，比较位置和元素值public boolean equals(Object obj){if (!(obj instanceof Triple))return false;Triple elem = (Triple)obj;return this.row == elem.row && this.column == elem.column && this.value == elem.value;}//根据三元组位置比较两个三元组的大小，与元素值无关，约定三元组排序次序@Overridepublic int compareTo(Triple elem){if (this.row < elem.row || this.row == elem.row && this.column < elem.column)return -1; //当前三元组对象小if (this.row == elem.row && this.column == elem.column)return 0; //相等，与equals()方法含义不同return 1; //当前三元组对象大}//行的单链表用public void add(Triple term){//加法，＋=运算符作用if (pareTo(term)==0)this.value += term.value;elsethrow new IllegalArgumentException("两项的指数不同，不能相加。");}//约定删除元素条件public boolean removable(){return this.value == 0;//不存储值为0的元素}//转置矩阵用public Triple toSymmetry(){//返回对称位置矩阵元素的三元组return new Triple(this.column, this.row, this.value);}}
实现：
package pers.zhang.array;import pers.zhang.linearList.SeqList;/*** @author zhang* @date /1/19 - 14:34** 稀疏矩阵的顺序存储*/public class SeqSparseMatrix {//矩阵行数、列数private int rows, columns;//稀疏矩阵三元组顺序表private SeqList<Triple> list;//构造rows行columns列零矩阵public SeqSparseMatrix(int rows, int columns){if (rows <= 0 || columns <= 0)throw new IllegalArgumentException("矩阵行数或列数非正数。"); //抛出无效参数异常this.rows = rows;this.columns = columns;this.list = new SeqList<Triple>(); //构造空顺序表，执行SeqList()构造方法}//构造rows行columns列矩阵，由三元组数组elems提供矩阵初值public SeqSparseMatrix(int rows, int columns, Triple[] elems){this(rows, columns);for (int i = 0; i < elems.length; i++)this.set(elems[i]); //按行主序插入一个元素的三元组}//返回矩阵第i行第j列元素，排序顺序表的顺序查找算法，O(n)public int get(int i, int j){if (i < 0 || i >= rows || j < 0 || j >= columns)throw new IndexOutOfBoundsException("矩阵元素的行或列序号越界");Triple item = new Triple(i,j,0);int k = 0;Triple elem = this.list.get(k);while (k < this.list.length() && pareTo(elem) >= 0){//在排序顺序表list中顺序查找item对象if (pareTo(elem) == 0) //只比较三元组元素位置，即elem.row==i && elem.column==jreturn elem.value;//查找到(i,j)，返回矩阵元素k++; //item“大”时向后走elem = this.list.get(k);}return 0; //没有找到时返回0}//以三元组设置矩阵元素public void set(Triple elem){this.set(elem.row, elem.column, elem.value);}//设置矩阵第row行第column列的元素值为value，按行主序在排序顺序表list中更改或插入一个元素的三元组，O(n)public void set(int row, int column, int value){if (value == 0)return;//不存储值为0元素if (row >= this.rows || column >= this.columns)throw new IllegalArgumentException("三元组的行或列序号越界");Triple elem = new Triple(row,column,value);int i = 0;while (i < this.list.length()){//在排序的三元组顺序表中查找elem对象，或更改或插入Triple item = this.list.get(i);if (pareTo(item)==0){//若elem存在，则更改该位置矩阵元素this.list.set(i, elem);//设置顺序表第i个元素为elemreturn;}if (pareTo(item)>=0)i++; //elem较“大”时向后走else break;}this.list.insert(i, elem);//插入elem对象作为顺序表第i个元素}//返回稀疏矩阵三元组顺序表和稀疏矩阵描述字符串public String toString(){String str="三元组顺序表："+ this.list.toString()+"\n";str += "稀疏矩阵" + this.getClass().getName() + "（" + rows + "×" + columns + "）：\n";int k = 0;Triple elem = this.list.get(k++); //返回第k个元素，若k指定序号无效则返回nullfor (int i = 0; i < this.rows; i++){for (int j = 0; j < this.columns; j++)if (elem != null && i == elem.row && j == elem.column){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，不改变当前矩阵，算法同两个多项式相加public SeqSparseMatrix plus(SeqSparseMatrix smat){if (this.rows != smat.rows || this.columns != smat.columns)throw new IllegalArgumentException("两个矩阵阶数不同，不能相加");SeqSparseMatrix smatc = new SeqSparseMatrix(this.rows, this.columns); //构造rows×columns零矩阵int i = 0, j = 0;while (i < this.list.length() && j < smat.list.length())//分别遍历两个矩阵的顺序表{Triple elema = this.list.get(i);Triple elemb = smat.list.get(j);if (pareTo(elemb) == 0){//若两个三元组表示相同位置的矩阵元素，则对应元素值相加if (elema.value+elemb.value != 0) //相加结果不为0，则新建元素smatc.list.append(new Triple(elema.row, elema.column, elema.value+elemb.value));i++;j++;}else if (pareTo(elemb) < 0){//将较小三元组复制添加到smatc顺序表最后smatc.list.append(new Triple(elema));//复制elema元素执行Triple拷贝构造方法i++;}else{smatc.list.append(new Triple(elemb));j++;}}while (i<this.list.length()) //将当前矩阵顺序表的剩余三元组复制添加到smatc顺序表最后smatc.list.append(new Triple(this.list.get(i++)));while (j<smat.list.length()) //将smat中剩余三元组复制添加到smatc顺序表最后smatc.list.append(new Triple(smat.list.get(j++)));return smatc; //返回对象引用}/* 可行，效率低，用于测试get(i,j)方法是否正确public String toString() //返回稀疏矩阵三元组顺序表和稀疏矩阵描述字符串{String str="三元组顺序表："+ this.list.toString()+"\n";str+="稀疏矩阵"+this.getClass().getName()+"（"+rows+"×"+columns+"）：\n";for (int i=0; i<this.rows; i++){for (int j=0; j<this.columns; j++)str += String.format("%4d", this.get(i,j));str += "\n";}return str;}*///当前矩阵与smat矩阵相加，this+=smat，改变当前矩阵，算法同两个多项式相加public void add(SeqSparseMatrix smat){if (this.rows != smat.rows || this.columns != smat.columns)throw new IllegalArgumentException("两个矩阵阶数不同，不能相加");int i = 0, j = 0;while (i < this.list.length() && j < smat.list.length()){//将mat的各三元组依次插入（或相加）到当前矩阵三元组顺序表中Triple elema = this.list.get(i);Triple elemb = smat.list.get(j);if (pareTo(elemb)==0){//若两个三元组表示相同位置的矩阵元素，则对应元素值相加if (elema.value+elemb.value!=0) //相加结果不为0，则新建元素this.list.set(i++, new Triple(elema.row, elema.column, elema.value+elemb.value));elsethis.list.remove(i);j++;}else if (pareTo(elemb)<0) //继续向后寻找elemb元素的插入位置i++;else{this.list.insert(i++, new Triple(elemb));//复制elemb元素插入作为this.list的第i个元素j++;}}while (j<smat.list.length()) //将mat中剩余三元组依次复制插入当前矩阵三元组顺序表中this.list.append(new Triple(smat.list.get(j++)));}//深拷贝public SeqSparseMatrix(SeqSparseMatrix smat){this(smat.rows, smat.columns);this.list = new SeqList<Triple>(); //创建空顺序表，默认容量for (int i=0; i<smat.list.length(); i++) //复制smat中所有三元组对象this.list.append(new Triple(smat.list.get(i)));}/*也可public SeqSparseMatrix(SeqSparseMatrix smat) //深拷贝{this(smat.rows, smat.columns);this.add(smat);}*///也可，算法效率低//返回当前矩阵与smat相加后的矩阵，smatc=this+smat，不改变当前矩阵，算法同两个多项式相加/*public SeqSparseMatrix plus(SeqSparseMatrix smat){SeqSparseMatrix smatc=new SeqSparseMatrix(this); //深拷贝smatc.add(smat);return smatc; //返回对象引用}*/public boolean equals(Object obj) //比较两个矩阵是否相等{if (this==obj)return true;if (!(obj instanceof SeqSparseMatrix))return false;SeqSparseMatrix smat=(SeqSparseMatrix)obj;return this.rows==smat.rows && this.columns==smat.columns && this.list.equals(smat.list);//比较两个三元组顺序表是否相等}public SeqSparseMatrix transpose() //返回转置矩阵{SeqSparseMatrix trans = new SeqSparseMatrix(columns, rows); //构造零矩阵，指定行数和列数for (int i=0; i<this.list.length(); i++)trans.set(this.list.get(i).toSymmetry());//插入矩阵对称位置元素的三元组return trans;}}
测试：
package pers.zhang.array;/*** @author zhang* @date /1/19 - 14:42*/public class SeqSparseMatrix_ex {public static void main(String args[]){//数组没有要求元素 排序Triple[] elemsa={new 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)};//不存储值为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("\n//习题5");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转置"+smata.transpose().toString()); //习题5}}/*A 三元组顺序表：((0,2,11), (0,4,17), (1,1,20), (3,0,19), (3,5,28), (4,4,50))稀疏矩阵pers.zhang.array.SeqSparseMatrix（5×6）：0 0 11 0 17 00 20 0 0 0 00 0 0 0 0 019 0 0 0 0 280 0 0 0 50 0B 三元组顺序表：((0,2,-11), (0,4,-17), (2,3,51), (3,0,10), (4,5,99))稀疏矩阵pers.zhang.array.SeqSparseMatrix（5×6）：0 0 -11 0 -17 00 0 0 0 0 00 0 0 51 0 010 0 0 0 0 00 0 0 0 0 99C=A+B 三元组顺序表：((1,1,20), (2,3,51), (3,0,29), (3,5,28), (4,4,50), (4,5,99))稀疏矩阵pers.zhang.array.SeqSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 0 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99//习题5A+=B 三元组顺序表：((1,1,20), (2,3,51), (3,0,29), (3,5,28), (4,4,50), (4,5,99))稀疏矩阵pers.zhang.array.SeqSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 0 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99C.equals(A)？trueB 三元组顺序表：((0,2,1), (0,4,-17), (2,3,51), (3,0,10), (4,5,99))稀疏矩阵pers.zhang.array.SeqSparseMatrix（5×6）：0 0 1 0 -17 00 0 0 0 0 00 0 0 51 0 010 0 0 0 0 00 0 0 0 0 99D 三元组顺序表：((0,2,-11), (0,4,-17), (2,3,51), (3,0,10), (4,5,99))稀疏矩阵pers.zhang.array.SeqSparseMatrix（5×6）：0 0 -11 0 -17 00 0 0 0 0 00 0 0 51 0 010 0 0 0 0 00 0 0 0 0 99A转置三元组顺序表：((0,3,29), (1,1,20), (3,2,51), (4,4,50), (5,3,28), (5,4,99))稀疏矩阵pers.zhang.array.SeqSparseMatrix（6×5）：0 0 0 29 00 20 0 0 00 0 0 0 00 0 51 0 00 0 0 0 500 0 0 28 99*/
三元组单链表压缩存储
三元组单链表：
行单链表：
public class LinkedSparseMatrix {private int rows, columns; //矩阵行数、列数private SeqList<PolySLinkedList<Triple>> list; //行指针顺序表，元素是多项式排序单链表对象 public LinkedSparseMatrix(int rows, int columns) //构造rows行columns列零矩阵{if (rows<=0 || columns<=0)throw new IllegalArgumentException("矩阵行数或列数非正数。");this.rows = rows;this.columns = columns;this.list = new SeqList<PolySLinkedList<Triple>>();//构造空顺序表，元素是nullfor (int i=0; i<rows; i++)//顺序表增加rows个空单链表元素this.list.append(new PolySLinkedList<Triple>());}//构造rows行columns列矩阵，由三元组数组elems提供矩阵初值public LinkedSparseMatrix(int rows, int columns, Triple[] elems){this(rows, columns);for (int i=0; i<elems.length; i++)this.set(elems[i]); //按行主序插入一个元素的三元组}public int get(int i, int j) //返回矩阵第i行第j列的元素{if (i<0 || i>=rows || j<0 || j>=columns)throw new IndexOutOfBoundsException("矩阵元素的行或列序号越界");PolySLinkedList<Triple> link = this.list.get(i); //获得第i行多项式排序单链表Triple find=link.search(new Triple(i,j,0)); //在排序单链表中顺序查找，返回找到结点，算法实现见8.2.1节return (find==null) ? 0 : find.value; //没有找到时返回0，否则返回结点元素}public void set(Triple elem) //以三元组设置矩阵元素{this.set(elem.row, elem.column, elem.value);}public void set(int row, int column, int value) //设置矩阵第row行第column列元素值为value{if (value==0)return;//不存储值为0元素if (row>=this.rows || column>=this.columns)throw new IllegalArgumentException("三元组的行或列序号越界");//以下在第row条单链表中查找指定三元组对象，或更改，或按行主序插入一个三元组PolySLinkedList<Triple> link=this.list.get(row); //获得第row行多项式排序单链表Node<Triple> front=link.head, p=front.next; //front是p的前驱结点while (p!=null && p.data.column<=column) //在排序单链表中进行顺序查找{if (p.data.column==column) //查找到，更改矩阵元素值{p.data.value = value;return;}front = p;p = p.next;}front.next = new Node<Triple>(new Triple(row,column,value), p); //在front之后插入三元组元素}//思考题：set(elem)方法中能否调用link.insert(elem)？为什么？//答：不能，因为值相同时要替换，不插入。public String toString() //返回稀疏矩阵三元组顺序表和稀疏矩阵描述字符串{String str="三元组行的单链表：";for (int i=0; i<this.list.length(); i++) //调用SeqList的length()方法str += this.list.get(i).toString(); //调用SinglyLinkedList的toString()方法str += "\n稀疏矩阵"+this.getClass().getName()+"（"+rows+"×"+columns+"）：\n";for (int i=0; i<this.list.length(); i++){PolySLinkedList<Triple> link = this.list.get(i);Node<Triple> p=link.head.next;for (int j=0; j<this.columns; j++)if (p!=null && j==p.data.column) //有i==p.data.row {str += String.format("%4d",p.data.value);p = p.next;}elsestr +=String.format("%4d",0);str += "\n";}return str;}//当前矩阵与smat矩阵相加，this+=smat，改变当前矩阵，每两条单链表的合并算法同两个多项式相加public void add(LinkedSparseMatrix smat){if (this.rows!=smat.rows || this.columns!=smat.columns)throw new IllegalArgumentException("两个矩阵阶数不同，不能相加");for (int i=0; i<this.rows; i++)this.list.get(i).add(smat.list.get(i)); //调用多项式单链表相加(+=)算法}//深度拷贝，复制顺序表，复制顺序表中所有单链表及其中所有结点和元素对象public LinkedSparseMatrix(LinkedSparseMatrix smat){this(smat.rows, smat.columns); //构造rows行columns列零矩阵，顺序表有rows个空单链表对象for (int i=0; i<this.rows; i++){PolySLinkedList<Triple> link=new PolySLinkedList<Triple>(smat.list.get(i));//多项式单链表深拷贝，已复制所有结点，没有复制元素对象for (Node<Triple> p=link.head.next; p!=null; p=p.next)p.data = new Triple(p.data);//复制一条单链表中各结点引用的元素对象this.list.set(i, link); //将复制后的单链表设置为顺序表第i个元素}}//返回当前矩阵与smat相加后的矩阵，不改变当前矩阵，smatc=this+smatpublic LinkedSparseMatrix plus(LinkedSparseMatrix smat){LinkedSparseMatrix smatc=new LinkedSparseMatrix(this); //深拷贝smatc.add(smat);return smatc; //返回对象引用}public boolean equals(Object obj) //比较两个矩阵是否相等，算法同SeqSparseMatrix类{if (this==obj)return true;if (!(obj instanceof LinkedSparseMatrix))return false;LinkedSparseMatrix smat=(LinkedSparseMatrix)obj;return this.rows==smat.rows && this.columns==smat.columns && this.list.equals(smat.list);//比较两个三元组顺序表是否相等}//习题5/* //可行，效率低，用于测试get(i,j)方法是否正确public String toString() //返回稀疏矩阵三元组顺序表和稀疏矩阵描述字符串{String str="三元组行的单链表："+ this.list.toString()+"\n";str+="稀疏矩阵"+this.getClass().getName()+"（"+rows+"×"+columns+"）：\n";for (int i=0; i<this.rows; i++){for (int j=0; j<this.columns; j++)str += String.format("%4d", this.get(i,j));str += "\n";}return str;} */public LinkedSparseMatrix transpose() //返回转置矩阵{LinkedSparseMatrix trans = new LinkedSparseMatrix(columns, rows); //构造零矩阵，指定行数和列数for (int i=0; i<this.rows; i++){//归并（相加）两条排序的单链表Node<Triple> p=this.list.get(i).head.next;while (p!=null) //对称元素的三元组item插入排序的单链表{trans.set(p.data.toSymmetry()); //复制q结点并插入到front结点之后p = p.next;}}return trans;}}
测试：
public class LinkedSparseMatrix_ex {public static void main(String args[]){Triple[] elemsa={new 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)};LinkedSparseMatrix smata = new LinkedSparseMatrix(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)};//不存储值为0元素LinkedSparseMatrix smatb = new LinkedSparseMatrix(5,6,elemsb);System.out.print("B "+smatb.toString());LinkedSparseMatrix smatc=smata.plus(smatb);System.out.print("C=A+B "+smatc.toString());smata.add(smatb);System.out.print("A+=B "+smata.toString());System.out.println("C.equals(A)？"+smatc.equals(smata));//深拷贝，引用测试smata.set(new Triple(1,4,19));System.out.print("A "+smata.toString());System.out.println("C.equals(A)？"+smatc.equals(smata));System.out.println("\n//习题5");System.out.println("A转置"+smata.transpose().toString()); //习题5}}/*程序运行结果如下：A 三元组行的单链表：((0,2,11), (0,4,17))((1,1,20))()((3,0,19), (3,5,28))((4,4,50))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 11 0 17 00 20 0 0 0 00 0 0 0 0 019 0 0 0 0 280 0 0 0 50 0B 三元组行的单链表：((0,2,-11), (0,4,-17))()((2,3,51))((3,0,10))((4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 -11 0 -17 00 0 0 0 0 00 0 0 51 0 010 0 0 0 0 00 0 0 0 0 99C=A+B 三元组行的单链表：()((1,1,20))((2,3,51))((3,0,29), (3,5,28))((4,4,50), (4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 0 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99A+=B 三元组行的单链表：()((1,1,20))((2,3,51))((3,0,29), (3,5,28))((4,4,50), (4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 0 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99C.equals(A)？trueA 三元组行的单链表：()((1,1,20), (1,4,19))((2,3,51))((3,0,29), (3,5,28))((4,4,50), (4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 19 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99C.equals(A)？false//习题5A转置三元组行的单链表：((0,3,29))((1,1,20))()((3,2,51))((4,1,19), (4,4,50))((5,3,28), (5,4,99))稀疏矩阵LinkedSparseMatrix（6×5）：0 0 0 29 00 20 0 0 00 0 0 0 00 0 51 0 00 19 0 0 500 0 0 28 99*/
十字链表
十字链表节点类：
public class CrossNode {//数据域表示三元组Triple data;//right指向行的下一个节点，down指向列的下一个节点CrossNode right, down;//构造结点，data指定元素，right指向行的下一个结点，down指向列的下一个结点public CrossNode(Triple data, CrossNode right, CrossNode down){this.data = data;this.right = right;this.down = down;}}
实现：
package pers.zhang.array;/*** @author zhang* @date /1/19 - 15:00** 十字链表存储稀疏矩阵*/public class CrossLinkedSparseMatrix {//矩阵行数、列数private int rows, columns;//行指针数组和列指针数组，元素类型是十字链表结点 private CrossNode rowheads[],columnheads[];//构造rows行columns列零矩阵public CrossLinkedSparseMatrix(int rows, int columns){if (rows <= 0 || columns <= 0)throw new IllegalArgumentException("矩阵行数或列数非正数。");this.rows = rows;this.columns = columns;this.rowheads = new CrossNode[this.rows];//构造行指针数组的空顺序表，元素是nullthis.columnheads = new CrossNode[this.columns]; //构造列指针数组的空顺序表，元素是null}//构造rows行columns列矩阵，由三元组数组elems提供矩阵初值public CrossLinkedSparseMatrix(int rows, int columns, Triple[] elems){this(rows, columns);for (int i = 0; i < elems.length; i++)this.set(elems[i]); //插入一个元素的三元组}//返回矩阵第i行第j列的元素public int get(int i, int j){if (i < 0 || i >= rows || j < 0 || j >= columns)throw new IndexOutOfBoundsException("矩阵元素的行或列序号越界");for (CrossNode p = this.rowheads[i]; p != null; p = p.right) //在第i行排序单链表中顺序查找(i,j,?)结点if (p.data.column == j)//查找依据是列，忽略三元组元素值return p.data.value; //查找到(i,j,value)结点，返回矩阵元素return 0; //没有找到时返回0}//以三元组设置矩阵元素public void set(Triple elem){this.set(elem.row, elem.column, elem.value);}//设置矩阵第i行第j列元素值为valuepublic void set(int i, int j, int value){if (value == 0)return;//不存储值为0元素if (i >= this.rows || j >= this.columns)throw new IllegalArgumentException("三元组的行或列序号越界");//以下在第i条单链表中查找指定三元组，或更改，或在行、列单链表中插入三元组结点Triple elem = new Triple(i,j,value);CrossNode rhead = this.rowheads[i]; //rhead指向第i行单链表的第一个结点if (rhead == null || rhead.data.column > j){//空表插入或头插入this.rowheads[i] = new CrossNode(elem, rhead, null);insertColumnHeads(this.rowheads[i]); //将该结点插入到列的单链表return;}CrossNode front = null, p = rhead;while (p != null && p.data.column <= j)//在排序单链表中顺序查找(i,j,?)结点{if (p.data.column == j)//查找依据是列，忽略三元组元素值{p.data.value = value; //查找到，更改矩阵元素值return;}front = p; //front是p的前驱结点p = p.right;}front.right = new CrossNode(elem, p, null); //未找到，在front之后插入三元组结点，中间或尾插入insertColumnHeads(front.right);//将该结点插入到列的单链表}//插入node结点到相应列的单链表中private void insertColumnHeads(CrossNode node){Triple elem = node.data;CrossNode chead = this.columnheads[elem.column];//获得第column列单链表if (chead == null || chead.data.row > elem.row){//空表插入或头插入this.columnheads[elem.column] = node;if (chead != null)node.down = chead.down;}else{//中间插入或尾插入CrossNode front = chead, p = front.down; //front是p的前驱结点while (p != null && p.data.row <= elem.row) //在排序单链表中顺序查找，寻找插入位置{front = p;p = p.down;}front.down = node; //将node结点插入在front之后，中间或尾插入node.down = p;}}public String toString() //返回稀疏矩阵三元组十字链表和稀疏矩阵字符串{String str="三元组十字链表\n";str+="三元组行的单链表：";for (int i=0; i<this.rowheads.length; i++){str+="(";for (CrossNode p=this.rowheads[i]; p!=null; p=p.right){str += p.data.toString();if (p.right!=null)str+=",";}str += ")";if (i<this.rowheads.length-1)str += ", ";}str+="\n三元组列的单链表：";for (int i=0; i<this.columnheads.length; i++){str+="(";for (CrossNode p=this.columnheads[i]; p!=null; p=p.down){str += p.data.toString();if (p.down!=null)str+=",";}str += ")";if (i<this.columnheads.length-1)str += ", ";}str+="\n稀疏矩阵"+this.getClass().getName()+"（"+rows+"×"+columns+"）：\n";for (int i=0; i<this.rows; i++){CrossNode p=this.rowheads[i];for (int j=0; j<this.columns; j++)if (p!=null && j==p.data.column) //有i==p.data.row {str += String.format("%4d",p.data.value);p = p.right;}elsestr +=String.format("%4d",0);str += "\n";}return str;}//当前矩阵与smat矩阵相加，this+=smat，改变当前矩阵public void add(CrossLinkedSparseMatrix smat){if (this.rows != smat.rows || this.columns != smat.columns)throw new IllegalArgumentException("两个矩阵阶数不同，不能相加");for (int i = 0; i < this.rows; i++){//相加合并两条排序单链表CrossNode rhead = this.rowheads[i]; //获得当前矩阵第i行单链表CrossNode q = smat.rowheads[i]; //获得参数矩阵第i行单链表if (q == null)continue;if (rhead == null || rhead.data.column > q.data.column)//空表插入或头插入{rhead = new CrossNode(new Triple(q.data), rhead, null); //创建结点，复制元素this.rowheads[i] = rhead;insertColumnHeads(rhead);q = q.right;}CrossNode front = null, p = rhead; //中间或尾插入while (p != null && q != null){if (p.data.column == q.data.column){//两个结点表示相同位置矩阵元素p.data.value += q.data.value; //更改结点元素值，矩阵元素值相加if (p.data.value==0) {//相加元素值为0if (front == null) {this.rowheads[i] = p.right;removeColumnHeads(p); //在相应列的单链表中删除node结点p = p.right;} else {front.right = p.right; //相加后元素不需要存储，删除p结点removeColumnHeads(p); //在相应列的单链表中删除node结点p = front.right;}}else{front = p;//front是p的前驱结点p = p.right;}q = q.right;}else if (p.data.column < q.data.column){front = p;p = p.right; //当前矩阵元素值小，p向后移动，q不动}else{//复制q结点并插入到front结点之后，复制元素front.right = new CrossNode(new Triple(q.data), p, null);q = q.right;insertColumnHeads(front.right);}}while (q != null) //将smat矩阵单链表中剩余结点复制并插入到当前链表尾{front.right = new CrossNode(new Triple(q.data), null, null);insertColumnHeads(front.right);front = front.right;q = q.right;}}}//在相应列的单链表中删除node结点private void removeColumnHeads(CrossNode node){Triple elem = node.data;CrossNode chead = this.columnheads[elem.column];//获得第column列单链表if (chead.data.row == elem.row) //头删除，有chead!=nullthis.columnheads[elem.column] = node.down;//删除node结点else //中间或尾删除{CrossNode front=chead, p=front.down; //front是p的前驱结点while (p!=null && p.data.row<elem.row) //在排序单链表中顺序查找{front = p;p = p.down;}if (p!=null && p.data.row==elem.row) //p为查找到结点，待删除front.down = node.down;//删除front之后的node结点，中间或尾删除}}//深拷贝public CrossLinkedSparseMatrix(CrossLinkedSparseMatrix smat){this(smat.rows, smat.columns);this.add(smat);}//返回当前矩阵与smat相加后的矩阵，不改变当前矩阵，=this+smat，同SeqSparseMatrix类public CrossLinkedSparseMatrix plus(CrossLinkedSparseMatrix smat){CrossLinkedSparseMatrix smatc=new CrossLinkedSparseMatrix(this); //深拷贝smatc.add(smat);return smatc; //返回对象引用}//比较两个矩阵是否相等public boolean equals(Object obj){if (this == obj)return true;if (!(obj instanceof CrossLinkedSparseMatrix))return false;CrossLinkedSparseMatrix smat = (CrossLinkedSparseMatrix)obj;if (this.rows != smat.rows || this.columns != smat.columns)return false;for (int i = 0; i < this.rows; i++) //分别比较this矩阵的第i行单链表与smat矩阵的第i行单链表是否相等{CrossNode p = this.rowheads[i], q = smat.rowheads[i];while (p != null && q != null){if (!(p.data.equals(q.data)))return false;p = p.right;q = q.right;}if (p != null || q != null)return false;}return true;}// public CrossLinkedSparseMatrix transpose() //返回转置矩阵// {// CrossLinkedSparseMatrix trans = new CrossLinkedSparseMatrix(columns, rows);//构造零矩阵// for (int i=0; i<this.rows; i++)// { //归并（相加）两条排序的单链表// CrossNode p=this.rowheads[i];//在第i条单链表中查找// while (p!=null) //对称元素的三元组item插入排序的单链表// {//trans.set(p.data.toSymmetry()); //复制q结点并插入到front结点之后//p = p.right;// }// }// return trans;// }}
测试:
package pers.zhang.array;/*** @author zhang* @date /1/19 - 14:52*/public class LinkedSparseMatrix_ex {public static void main(String args[]){Triple[] elemsa={new 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)};CrossLinkedSparseMatrix smata = new CrossLinkedSparseMatrix(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)};//不存储值为0元素CrossLinkedSparseMatrix smatb = new CrossLinkedSparseMatrix(5,6,elemsb);System.out.print("B "+smatb.toString());CrossLinkedSparseMatrix smatc=smata.plus(smatb);System.out.print("C=A+B "+smatc.toString());smata.add(smatb);System.out.print("A+=B "+smata.toString());System.out.println("C.equals(A)？"+smatc.equals(smata));//深拷贝，引用测试smata.set(new Triple(1,4,19));System.out.print("A "+smata.toString());System.out.println("C.equals(A)？"+smatc.equals(smata));}}/*程序运行结果如下：A 三元组行的单链表：((0,2,11), (0,4,17))((1,1,20))()((3,0,19), (3,5,28))((4,4,50))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 11 0 17 00 20 0 0 0 00 0 0 0 0 019 0 0 0 0 280 0 0 0 50 0B 三元组行的单链表：((0,2,-11), (0,4,-17))()((2,3,51))((3,0,10))((4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 -11 0 -17 00 0 0 0 0 00 0 0 51 0 010 0 0 0 0 00 0 0 0 0 99C=A+B 三元组行的单链表：()((1,1,20))((2,3,51))((3,0,29), (3,5,28))((4,4,50), (4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 0 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99A+=B 三元组行的单链表：()((1,1,20))((2,3,51))((3,0,29), (3,5,28))((4,4,50), (4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 0 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99C.equals(A)？trueA 三元组行的单链表：()((1,1,20), (1,4,19))((2,3,51))((3,0,29), (3,5,28))((4,4,50), (4,5,99))稀疏矩阵LinkedSparseMatrix（5×6）：0 0 0 0 0 00 20 0 0 19 00 0 0 51 0 029 0 0 0 0 280 0 0 0 50 99C.equals(A)？false*/
