Qz学算法-数据结构篇(稀疏数组、队列)

简介: 数据结构包括:线性结构和非线性结构。所以博主会通过这两个角度来对线性结构和非线性结构进行梳理归纳。本篇是稀疏数组和队列

数据结构包括:线性结构和非线性结构。所以博主会通过这两个角度来对线性结构和非线性结构进行梳理归纳。

1.稀疏(sparse array)数组

需求引入

  • 编写的五子棋程序中,有存盘退出续上盘的功能。
    网络异常,图片无法展示
    |

分析问题

  • 因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据->稀疏数组

1.1介绍

当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。

网络异常,图片无法展示
|

稀疏数组的处理方法是:

1)记录数组一共有几行几列,有多少个不同的值

2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模

1.2二维数组转稀疏数组的思路

  • 遍历原始的二维数组,得到有效数据的个数sum
  • 根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
  • 将二维数组的有效数据数据存入到稀疏数组

1.3稀疏数组转二维数组的思路

  • 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的chessArr2=int [11][11]
  • 在读取稀疏数组后几行的数据,并赋给原始的二维数组即可.

1.4代码实现

/**
 * @author LeeZhi
 * @version 1.0
 */
@SuppressWarnings({"all"})
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 i = 0; i < chessArr1.length; i++) {
        //    for (int j = 0; j < chessArr1[i].length; j++) {
        //        System.out.print(chessArr1[i][j]+"\t");
        //    }
        //    System.out.println();
        //}
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        //将二维数组转稀疏数组的思想
        //1.先遍历二维数组得到非0数据的个数
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //System.out.println("sum="+sum);
        //2.创建稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        //遍历二维数组,将非0的值存入 sparseArr中
        int count = 0;  //count 用于记录第几个非0数据
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        //输出稀疏数组的形式
        System.out.println();
        System.out.println("得到的稀疏数组为:");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
        }
        System.out.println();
        //将稀疏数组-->恢复成原始的二维数组
        /*
        - 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 chessArr2 = int [11][11]
        - 在读取稀疏数组后几行的数据,并赋给原始的二维数组即可.
         */
        //先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 chessArr2 = int [11][11]
        int chessArr2 [][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        //在读取稀疏数组后几行的数据(从第二行开始) ,并赋给原始的二维数组即可.
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        //输出恢复后的二维数组
        System.out.println();
        System.out.println("恢复后的二维数组");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

 

笔者的理解

我把下面的代码单独筛选出来以便于做分析

网络异常,图片无法展示
|

稀疏数组的情况(三行三列)

row col val

11   11   2

1     2   1

2     3   2

稀疏数组的第一行所包含的元素就是原数组的列 行 有效值,到第二行以后就需要存各个有效值的坐标和值了

下面的说就是有效值在原数组的坐标,如上图有效值1的坐标在原数组是(1,2)因为索引是从0开始的

//将二维数组转稀疏数组的思想
        //1.先遍历二维数组得到非0数据的个数
        int sum = 0;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //System.out.println("sum="+sum);
        //2.创建稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        //遍历二维数组,将非0的值存入 sparseArr中
        int count = 0;  //count 用于记录第几个非0数据
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }

下面的这段代码是我根据自己的理解改变了某些值,这样两端代码一比较出来就会更加直观

package Sparse_Array;
import java.util.Arrays;
/**
 * @author LeeZhi
 * @version 1.0
 */
@SuppressWarnings({"all"})
public class SpareArrayDemo {
    public static void main(String[] args) {
        int chessArr[][] = new int [8][7];
        chessArr[0][0]=1;
        chessArr[1][1]=2;
        chessArr[2][2]=3;
        chessArr[3][3]=4;
        chessArr[4][4]=5;
        chessArr[5][5]=6;
        chessArr[6][6]=7;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                System.out.print(chessArr[i][j]+"\t");
            }
            System.out.println();
        }
        int num = 0;
        for (int i = 0; i <chessArr.length ; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j]!=0) num++;
            }
        }
        System.out.println(num);
        int spareArr[][] = new int[num+1][3];
        spareArr[0][0] = 7;
        spareArr[0][1]=8;
        spareArr[0][2]=num;
        for (int row[]:spareArr){
            for (int data: row){
                System.out.print(data+"\t");
            }
            System.out.println();
        }
        System.out.println("输出稀疏矩阵");
        //插入数据
        int count=0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j]!=0){
                    count++;
                    spareArr[count][0] = i;
                    spareArr[count][1]=j;
                    spareArr[count][2]=chessArr[i][j];
                }
            }
        }
        for (int row[]:spareArr){
            for (int data: row){
                System.out.print(data+"\t");
            }
            System.out.println();
        }
        System.out.println("稀疏数组返回原始二维数组");
        int sourceArr [][] = new int [spareArr[0][1]][spareArr[0][2]];
        for (int i = 1; i < spareArr.length; i++) {
            sourceArr[spareArr[i][0]][spareArr[i][1]]=spareArr[i][2];
        }
        for (int row[] :sourceArr) {
            for (int data: row){
                System.out.print(data+"\t");
            }
            System.out.println();
        }
    }
}

2.队列(queue)

1.数组模拟队列

需求引入

银行排队的案例,一个一个叫号

1.1介绍

  • 队列是一个有序列表,可以用数组或是链表来实现。
  • 遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出
  • 示意图:(使用数组模拟队列示意图)
    网络异常,图片无法展示
    |

    这里笔者认为,front和rear取-1时刚好的,因为在数组中.第一个数据的下标是以0开始,所以这两个值都取-1是没有任何问题的,这代表了队头和队尾处于空的状态,后续只要有第一个元素加入那么这rear这个变量都会变为0,后续有数据加入就会自增1,出一个数据front就会自增1

1.2数组模拟队列

  • 队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中maxSize是该队列的最大容量。
  • 因为队列的输出、输入是分别从前后端来处理,因此需要两个变量frontrear分别记录队列前后端的下标,front会随着数据输出而改变,而rear则是随着数据输入而改变

1.3思路分析

当我们将数据存入队列时称为”addQueue”,addQueue的处理需要有两个步骤:

  1. 将尾指针往后移:rear+1,当front==rear【空】
  2. 若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指的数组元素中,否则无法存入数据。rear==maxSize-1[队列满]

1.4代码实现

* @author LeeZhi
 * @version 1.0
 */
public class ArrQueue {
    public static void main(String[] args) {
        //创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' ';//接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while(loop){
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key){
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个值");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g'://取数据
                    try{
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h'://查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e'://退出
                    scanner.close();
                    loop = false;
                    break;
            }
        }
        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[maxSize];
        front = -1;//指向队列头部,分析出front是指向队列头的前一个位置
        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;
        }
        rear++;//让rear后移
        arr[rear] = n;
    }
    //获取队列的数据,出队列
    public int getQueue(){
        //判断队列是否为空
        if (isEmpty()){
            //通过抛出异常来处理
            throw new RuntimeException("队列空,不能取数据");
        }
        front++;//front后移
        return arr[front];
    }
    //显示队列所有数据
    public void showQueue(){
        //遍历
        if (isEmpty()){
            System.out.println("队列空的,没有数据");
        }
        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];
    }
}

2.数组模拟环形队列

需求引入

目前数组使用一次就不能用,没有达到复用的效果

这里笔者认为:无法复用具体就是当我们的最大容量存满数据时,如果这时拿走一条数据,此时就不是满的了,这时maxSize和rear不能动态的改变,所以我们需要一个环形队列

对前面的数组模拟队列的优化,充分利用数组因此将数组看做是一个环形的。(通过取模的方式来实现即可)

2.1数组模拟环形队列

也就是在rear指向最后一个位置时,front前面还有没有空余的元素

  • 尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(rear+1)%maxSize=front[满],为满就是没有元素被取出去
  • rear=front[空]

2.2思路分析

  • front变量的含义做一个调整:front就指向第一个元素,也就是说arr[front]就是队列的第一个元素 front的初始值=0
  • rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间作为约定 rear的初始值=0
  • 当队列满时,条件是(rear+1)%maxSize==front【满】
  • 对队列为空的条件,rear==front 空
  • 当我们这样分析,队列中有效的数据的个数 (rear+maxSize-front)%maxSize
  • 我们就可以在原来的队列上修改得到,一个环形队列

2.3代码实现

public class CircleArrayQueue {
    public static void main(String[] args) {
        //测试
        System.out.println("测试数组模拟环形队列");
        CircleArray queue = new CircleArray(4);//这里有效数据为3
        char key = ' ';//接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while (loop) {
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个值");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g'://取数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h'://查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e'://退出
                    scanner.close();
                    loop = false;
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

使用数组模拟队列 编写一个ArrayQueue类

class CircleArray {
    private int maxSize;//表示数组最大容量
    //front就指向第一个元素,也就是说arr[front]就是队列的第一个元素
    private int front;//队列头
    //rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间作为约定
    //rear的初始值=0
    private int rear;//队列尾
    private int[] arr;//该数组用于存放数据,模拟队列
    //创建队列的构造器
    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }
    //判断队列是否满
    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 = (rear + 1) % maxSize;
    }
    //获取队列的数据,出队列
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            //通过抛出异常来处理
            throw new RuntimeException("队列空,不能取数据");
        }
        //这里需要分析出front是指向队列的第一个元素
        //1,先把front对应的值保留到一个临时变量
        //2.将front后移
        //3.将临时保存的变量返回
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }
    //显示队列所有数据
    public void showQueue() {
        //遍历
        if (isEmpty()) {
            System.out.println("队列空的,没有数据");
        }
        //思路:从front开始遍历,遍历多少个元素
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }
    //求出当前队列有效数据的个数
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
    //显示队列的头数据,注意不是取出数据
    public int headQueue() {
        //判断
        if (isEmpty()) {
            throw new RuntimeException("队列为空,没有数据");
        }
        return arr[front];
    }
}

其实对于队列的话没有特别难理解的点,看着博主的文章就好了跟着里面的注释一步步操作下来就好了

目录
相关文章
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
16天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
16天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
16天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
1天前
|
传感器 算法
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
|
2天前
|
机器学习/深度学习 算法 安全
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。

热门文章

最新文章