数据结构--稀疏矩阵常用的三种压缩存储（顺序、行单链表、十字链表）

不念不忘少年蓝@ 2021-08-13 22:56 1063阅读 0赞

### 稀疏矩阵 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]  
表示稀疏矩阵的三元组：  
![在这里插入图片描述][20200119142144183.png]  
![在这里插入图片描述][20200119142152178.png]  
稀疏矩阵常用的压缩存储共有3种：

*  顺序存储
 *  单链表存储
 *  十字链表存储

### 顺序存储 ###

稀疏矩阵三元组顺序表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]  
表示稀疏矩阵非零元素的三元组：

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;
        }
    
        //根据三元组位置比较两个三元组的大小，与元素值无关，约定三元组排序次序
        @Override
        public 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 (this.compareTo(term)==0)
                this.value += term.value;
            else
                throw 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 2020/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() && item.compareTo(elem) >= 0){  //在排序顺序表list中顺序查找item对象
                if (item.compareTo(elem) == 0)                   //只比较三元组元素位置，即elem.row==i && elem.column==j
                    return 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 (elem.compareTo(item)==0){                    //若elem存在，则更改该位置矩阵元素
                    this.list.set(i, elem);                    //设置顺序表第i个元素为elem
                    return;
                }
                if (elem.compareTo(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指定序号无效则返回null
            for (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 (elema.compareTo(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 (elema.compareTo(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 (elema.compareTo(elemb)==0){ //若两个三元组表示相同位置的矩阵元素，则对应元素值相加
                    if (elema.value+elemb.value!=0)            //相加结果不为0，则新建元素
                        this.list.set(i++, new Triple(elema.row, elema.column, elema.value+elemb.value));
                    else
                        this.list.remove(i);
                    j++;
                }else if (elema.compareTo(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 2020/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 0 0 20 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 28 0 0 0 0 50 0 B 三元组顺序表：((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 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99 C=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 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 //习题5 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 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 C.equals(A)？true B 三元组顺序表：((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 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99 D 三元组顺序表：((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 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99 A转置三元组顺序表：((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 0 0 20 0 0 0 0 0 0 0 0 0 0 51 0 0 0 0 0 0 50 0 0 0 28 99 */

### 三元组单链表压缩存储 ###

三元组单链表：  
![在这里插入图片描述][20200119144425596.png]行单链表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]

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>>();//构造空顺序表，元素是null
            for (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;
                    }
                    else
                        str +=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+smat
        public 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 0 0 20 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 28 0 0 0 0 50 0 B 三元组行的单链表：((0,2,-11), (0,4,-17))()((2,3,51))((3,0,10))((4,5,99)) 稀疏矩阵LinkedSparseMatrix（5×6）： 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99 C=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 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 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 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 C.equals(A)？true A 三元组行的单链表：()((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 0 0 20 0 0 19 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 C.equals(A)？false //习题5 A转置三元组行的单链表：((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 0 0 20 0 0 0 0 0 0 0 0 0 0 51 0 0 0 19 0 0 50 0 0 0 28 99 */

### 十字链表 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]  
十字链表节点类：

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 2020/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];          //构造行指针数组的空顺序表，元素是null
            this.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列元素值为value
        public 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;
                    }
                    else
                        str +=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) {                  //相加元素值为0
                            if (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!=null
                this.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 2020/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 0 0 20 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 28 0 0 0 0 50 0 B 三元组行的单链表：((0,2,-11), (0,4,-17))()((2,3,51))((3,0,10))((4,5,99)) 稀疏矩阵LinkedSparseMatrix（5×6）： 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99 C=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 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 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 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 C.equals(A)？true A 三元组行的单链表：()((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 0 0 20 0 0 19 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99 C.equals(A)？false */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/ce1ff3eb3b8141acad2f0e3dda03423a.png
[20200119142144183.png]: /images/20210813/5bcf6a9072014eab86e96bfd9edab467.png
[20200119142152178.png]: /images/20210813/65111f15ec0a4726be7ab8cef20340d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]: /images/20210813/a528a787b63343019b04ae3115b26544.png
[20200119144425596.png]: /images/20210813/ca3ff72d02dd4461ae9a8c04dc469136.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]: /images/20210813/debfa48357364158bdc8986ac421e072.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]: /images/20210813/e549140be75848a7a0aa19f5e6f2a99e.png