Java二维数组转链式储存

时间:2022-05-23 HairLossException 人气:0

链式存储结构

链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢。

使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。

下图就是最简单最一般的单向链表：

代码思路

将二维数组压缩成链式存储大体思路与数组压缩成稀疏数组相似
这里我将链表的头节点储存二维数组的总行数、列数和有效值个
数头结点之后的每个结点存储有效值的下标和值转化思路如下图所示

代码实现

创建模拟结点的类提供构造方法和toString

/**
 * 模拟结点
 */
public class SingleNode {
    /**
     * @row 行号
     * @column 列号
     * @num 值
     */
    public int row;
    public int colunm;
    public int num;
    /**
     *next域：指向下一个结点
     */
    public SingleNode next;

    public SingleNode(int row, int colunm, int num) {
        this.row = row;
        this.colunm = colunm;
        this.num = num;
    }

    @Override
    public String toString() {
        return "SingleNode{" + "row=" + row + ", colunm=" + colunm + ", num=" + num + '}';
    }
}

创建模拟链表类提供添加结点、遍历链表和还原数组等方法

public class SingleLinkList {
    //头节点
    private SingleNode headSingleNode;
	//通过构造行数初始化头节点
    public SingleLinkList(SingleNode headSingleNode) {
        this.headSingleNode = headSingleNode;
    }

    /**
     * 添加结点(追加在链表的尾端)
     */
    public void add(SingleNode SingleNode){
        SingleNode temp = headSingleNode;
        while(true){
            if (temp.next == null) {
                //如果这个结点的next域为空就跳出while循环
                break;
            }
            //将下一个结点赋值给temp
            temp = temp.next;
        }
        temp.next= SingleNode;
    }
    /**
     * 遍历单项链表
     */
    public void show(){
        if (headSingleNode.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        SingleNode temp = headSingleNode;
        while (true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * 将链表还原成二维数组
     * @return array还原后的二维数组
     */
    public int[][] backToArray(){
        SingleNode temp = headSingleNode;
        //头结点中存储着原数组的行数和列数
        //通过这两个值创建二维数组
        int[][] array = new int[headSingleNode.row][headSingleNode.colunm];
        while (true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
            //每遍历一个结点就还原一个数据
            array[temp.row][temp.colunm] = temp.num;
        }
        return array;
    }
}

public class ArrayToLink {
    public static void main(String[] args) {
        int[][] array = new int[4][5];
        //初始化二维数组
        array[0][2] = 1;
        array[1][1] = 2;
        array[2][3] = 3;

        System.out.println("========普通数组========");
        //遍历二维数组
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j]!=0){
                    count++;
                }
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }

        //将数组转化成链式存储
        SingleLinkList list = new SingleLinkList(new SingleNode(array.length,array[0].length,count));
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] != 0){
                	//当数字不为0时视为有效值就创建一个结点并添加到链表尾部
                    list.add(new SingleNode(i,j,array[i][j]));
                }
            }
        }
        System.out.println("========转化后的链表========");
        //遍历单向链表
        list.show();

        int[][] returnArray = list.backToArray();
        //遍历还原后的二维数组
        System.out.println("========还原后的数组========");
        for (int i = 0; i < returnArray.length; i++) {
            for (int j = 0; j < returnArray[i].length; j++) {
                System.out.print(returnArray[i][j] + " ");
            }
            System.out.println();
        }
    }
}

输出结果

总结

加载全部内容