【数据结构】稀疏矩阵和队列

一、稀疏数组sparsearray

1、应用场景

需求：五子棋”存盘退出“ --> 二维数组保存

问题：这个二维数组大部分都是默认值0，记录了很多没有意义的数据 --> 稀疏数组

2、稀疏数组

稀疏数组：数组大部分为同一个值

处理方法：记录数组几行几列，有多少个的值。把不同值的行和列记录在小规模数组中。

[0]：共几行几列，存在几个值

[1] - [n]：记录x行x列的值是多少

3、思路分析

1）二维转稀疏

1. 遍历原始二维数组，得到有效数据个数 -> sum
2. 创建稀疏数组sparseArr int[sum][3]
3. 将有效数据存到sparseArr中

2）稀疏转二维

1. 读取sparseArr的第一行的数据创建原始二维数组
2. 读取sparseArr后面的数值，赋值给二维数组

4、代码实现

1）基础代码

package work.rexhao.sparsearray;

public class sparsearray {
   

    public static void main(String[] args) {
   
        // 创建一个原始的二维数组11*11
        // 0：没有旗子，1：黑子，2：蓝子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        // 输出
        System.out.println("原始二维数组");
        for(int[] row : chessArr1) {
   
            for(int i : row) {
   
                System.out.printf("%d ",i);
            }
            System.out.println();
        }

        // 将二维数组转换成稀疏数组
        // 1.遍历二维数组，得到非0个数、行和列
        int r = 0, l = 0, v = 0;
        for(int[] row : chessArr1) {
   
            r++;
            for(int i : row) {
   
                l++;
                if(i != 0) {
   
                    v++;
                }
            }
        }
        l /= r;

        // 2.创建稀疏数组
        int sparseArr[][] = new int[v+1][3];

        // 3.给稀疏数组赋值
        sparseArr[0][0] = r;
        sparseArr[0][1] = l;
        sparseArr[0][2] = v;
        int ii = 0;
        for(int i = 0; i < r; i++) {
   
            for(int j = 0; j < l; j++) {
   
                if(chessArr1[i][j] != 0) {
   
                    sparseArr[++ii][0] = i;
                    sparseArr[ii][1] = j;
                    sparseArr[ii][2] = chessArr1[i][j];
                }
            }
        }

        // 稀疏数组的输出
        System.out.println("得到的稀疏数组是：");
        for(int[] row : sparseArr) {
   
            for(int i : row) {
   
                System.out.print(i + " ");
            }
            System.out.println();
        }

        // 将稀疏数组恢复二维数组
        // 1.读取第一行，创建二维数组
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

        // 2.读取并赋值
        for(int i = 1; i <= sparseArr[0][2]; i++) {
   
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        // 输出
        System.out.println("转换的二维数组是：");
        for(int[] row : chessArr2) {
   
            for(int i : row) {
   
                System.out.printf("%d ",i);
            }
            System.out.println();
        }
    }

}

2）IO代码

package work.rexhao.sparsearray;

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;

public class sparsearray_out {
   
    public static void main(String[] args) throws FileNotFoundException, IOException {
   
        ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("./chess.data"));
        // 创建一个原始的二维数组11*11
        // 0：没有旗子，1：黑子，2：蓝子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[1][3] = 2;
        // 将二维数组转换成稀疏数组
        // 1.遍历二维数组，得到非0个数、行和列
        int r = 0, l = 0, v = 0;
        for (int[] row : chessArr1) {
   
            r++;
            for (int i : row) {
   
                l++;
                if (i != 0) {
   
                    v++;
                }
            }
        }
        l /= r;

        // 2.创建稀疏数组
        int sparseArr[][] = new int[v + 1][3];

        // 3.给稀疏数组赋值
        sparseArr[0][0] = r;
        sparseArr[0][1] = l;
        sparseArr[0][2] = v;
        int ii = 0;
        for (int i = 0; i < r; i++) {
   
            for (int j = 0; j < l; j++) {
   
                if (chessArr1[i][j] != 0) {
   
                    sparseArr[++ii][0] = i;
                    sparseArr[ii][1] = j;
                    sparseArr[ii][2] = chessArr1[i][j];
                }
            }
        }


        // 4.序列化
        oos.writeObject(sparseArr);
        oos.close();
        System.out.println("存档成功！");
    }
}

package work.rexhao.sparsearray;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;

public class sparsearray_in {
   

    public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException {
   
        ObjectInputStream ois = new ObjectInputStream(new FileInputStream("./chess.data"));
        int sparseArr[][] = (int[][])ois.readObject();
        System.out.println("读档成功!");
        // 将稀疏数组恢复二维数组
        // 1.读取第一行，创建二维数组
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

        // 2.读取并赋值
        for (int i = 1; i <= sparseArr[0][2]; i++) {
   
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        // 输出
         for (int[] row : chessArr2) {
   
            for (int i : row) {
   
                System.out.printf("%d ", i);
            }
            System.out.println();
        }

    }

}

二、队列

1、队列概述

队列是一个有序列表，可以用数组或链表实现

遵循先入先出原则

2、数组模拟队列

1）数组结构介绍

数组的结构存储队列元素，maxSize是队列最大容量

两个变量front和rear记录队列前后端

2）思路分析

1. 尾指针后移：rear+1
2. rear < maxSize - 1：可以存

当front == rear，队列空

当rear == maxSize - 1，队列满

3）代码实现

package work.rexhao.queue;

import java.util.Scanner;

public class arrayQueueDemo {
   

    public static void main(String[] args) {
   
        ArrayQueue aq = new ArrayQueue(3);
        boolean loop = true;
        while (loop) {
   
            Scanner sc = new Scanner(System.in);
            System.out.println("1. 添加数据");
            System.out.println("2. 弹出数据");
            System.out.println("3. 显示首数据");
            System.out.println("4. 遍历");
            System.out.println("0. 退出");
            int key = sc.nextInt();
            if (key == 1) {
   
                System.out.println("请输入需要添加的数据");
                int value = sc.nextInt();
                aq.addQueue(value);
            } else if (key == 2) {
   
                try {
   
                    int value = aq.getQueue();
                    System.out.printf("弹出元素：%d\n",value);
                } catch (Exception e) {
   
                    System.out.println(e.getMessage());
                }

            } else if (key == 3) {
   
                try {
   
                    int value = aq.headQueue();
                    System.out.printf("首元素：%d\n", value);
                } catch (Exception e) {
   
                    System.out.println(e.getMessage());
                }
            } else if (key == 4) {
   
                aq.showQueue();
            } else if (key == 0) {
   
                loop = false;
            } else {
   
                System.out.println("请检查输入");
            }
        }
    }

}

/**
 * 使用数组模拟队列----编写一个ArrayQueue类
 */
class ArrayQueue {
   
    private int maxSize; // 数组最大容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int[] arr; // 队列的数据

    /**
     * 创建队列的构造器
     */
    public ArrayQueue(int arrMaxSize) {
   
        maxSize = arrMaxSize;
        arr = new int[arrMaxSize];
        front = -1;// 指向队列头的前一个位置
        rear = -1;// 指向队列尾
    }

    /**
     * 判断队列是否满
     */
    public boolean isFull() {
   
        return rear == maxSize - 1;
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
   
        return rear == front;
    }

    /**
     * 添加队列数据
     */
    public void addQueue(int n) {
   
        if (isFull()) {
   
            System.out.println("队列满，添加失败！");
            return;
        }
        arr[++rear] = n;
    }

    /**
     * 出队列
     */
    public int getQueue() {
   
        if (isEmpty()) {
   
            // 抛出异常 -- 不需要写return
            throw new RuntimeException("队列空");
        }
        return arr[++front];
    }

    /**
     * 遍历
     */
    public void showQueue() {
   
        if (isEmpty()) {
   
            System.out.println("队列空！");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
   
            System.out.printf("arr[%d] = %d\n", i, arr[i]);
        }
    }

    /**
     * 显示头数据（不取出）
     */
    public int headQueue() {
   
        if (isEmpty()) {
   
            throw new RuntimeException("队列空");
        }
        return arr[front + 1];
    }
}

4）问题与优化

1. 对于普通队列，数组使用一次就不能用，没有达到复用的效果
2. 将这个数组使用算法，改进成一个环形的队列 （取模：%）

3、数组模拟环形队列

1）思路分析

1. front变量的含叉做一个调整：front就指向队列的第一个元素，也就是说ari[front] 就是队列的第一个元素。front 的初始值=0
2. rear 变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，空出一个空间做为约定。rear 的初始值=0
3. 当队列满时，条件是 (rear +1) % maxsize == front
4. 对队列为空的条件，rear == front
5. 队列中有效的数据的个数 (rear+ maxsize - front) % maxsize

2）代码实现

package work.rexhao.queue;

import java.util.Scanner;

public class circleQueueDemo {
   

    public static void main(String[] args) {
   
        CircleQueue cq = new CircleQueue(3);
        boolean loop = true;
        while (loop) {
   
            Scanner sc = new Scanner(System.in);
            System.out.println("1. 添加数据");
            System.out.println("2. 弹出数据");
            System.out.println("3. 显示首数据");
            System.out.println("4. 遍历");
            System.out.println("0. 退出");
            int key = sc.nextInt();
            if (key == 1) {
   
                System.out.println("请输入需要添加的数据");
                int value = sc.nextInt();
                cq.addQueue(value);
            } else if (key == 2) {
   
                try {
   
                    int value = cq.getQueue();
                    System.out.printf("弹出元素：%d\n", value);
                } catch (Exception e) {
   
                    System.out.println(e.getMessage());
                }

            } else if (key == 3) {
   
                try {
   
                    int value = cq.headQueue();
                    System.out.printf("首元素：%d\n", value);
                } catch (Exception e) {
   
                    System.out.println(e.getMessage());
                }
            } else if (key == 4) {
   
                cq.showQueue();
            } else if (key == 0) {
   
                loop = false;
            } else {
   
                System.out.println("请检查输入");
            }
        }

    }

}

/**
 * 使用数组模拟环形队列----编写一个CircleQueue类
 */
class CircleQueue {
   
    private int maxSize; // 数组最大容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int[] arr; // 队列的数据

    /**
     * 创建队列的构造器
     */
    public CircleQueue(int arrMaxSize) {
   
        maxSize = arrMaxSize;
        arr = new int[arrMaxSize];
        front = 0;// 指向队列头
        rear = 0;// 指向队列尾的后一个位置（空出一个空间做为约定）

    }

    /**
     * 判断队列是否满
     */
    public boolean isFull() {
   
        return (rear + 1) % maxSize == front;
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
   
        return rear == front;
    }

    /**
     * 添加队列数据
     */
    public void addQueue(int n) {
   
        if (isFull()) {
   
            System.out.println("队列满，添加失败！");
            return;
        }
        arr[rear] = n;
        rear = (rear + 1) % maxSize;
    }

    /**
     * 出队列
     */
    public int getQueue() {
   
        if (isEmpty()) {
   
            // 抛出异常 -- 不需要写return
            throw new RuntimeException("队列空");
        }
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    /**
     * 遍历？？？
     */
    public void showQueue() {
   
        if (isEmpty()) {
   
            System.out.println("队列空！");
            return;
        }
        for (int i = front; i < front + size(); i++) {
   
            System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    /**
     * 显示头数据（不取出）
     */
    public int headQueue() {
   
        if (isEmpty()) {
   
            throw new RuntimeException("队列空");
        }
        return arr[front];
    }

    /**
     * 有效数据
     */
    public int size() {
   
        return (rear - front + maxSize) % maxSize;
    }
}