> 文档中心 > 【大厂必会的数据结构和算法】01-稀疏数组和队列

【大厂必会的数据结构和算法】01-稀疏数组和队列

文章目录

  • 开篇
  • 一、稀疏数组
      • (1)稀疏数组的处理方法是:
      • (2)思路分析
      • (3)代码实现
  • 二、队列
      • (2)代码实现
  • 三、数组模拟环型队列
      • (1)问题分析及优化
      • (2)代码实现

开篇

数据结构包括:线性结构和非线性结构

线性结构

  1. 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对有的线性关系
  2. 线性结构有两种不同的存储结构,及顺序存储结构(数组)和链式存储结构(链表)。顺序存储结构的线性表称为顺序表,顺序表中的元素是连续的;如数组;
  3. 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放元素以及相邻元素的地址信息;
  4. 线性结构常见的有:数组,队列,表,链表和栈

非线性结构:
非线性结构包括:二维数组,多为数组,广义表,树结构,图结构

一、稀疏数组

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

(1)稀疏数组的处理方法是:

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

(2)思路分析

【大厂必会的数据结构和算法】01-稀疏数组和队列

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

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

稀疏数组转原始的二维数组思路:

  1. 先读取稀疏数组的第一行,根据第一行的数据创建原始的二维数组
  2. 读取稀疏数组后几行的数据,并赋值给原始的二维数组

(3)代码实现

首先创建原始的二维数组

 //创建一个原始的二维数组,11*11 //0:表示没有妻棋子,1:表示黑子,2:表示蓝子 int chessArr[][]=new int[11][11]; chessArr[1][2]=1; chessArr[2][3]=2; System.out.println("输出原始的二维数组"); //输出原始的二维数组 for (int[] row : chessArr) {     for (int data : row) {  System.out.printf("%d\t",data);     }     System.out.println();

【大厂必会的数据结构和算法】01-稀疏数组和队列

将原始的二维数组转换为稀疏数组;

// 将二维数组转为为稀疏数组 //1.先遍历二维数组,得到非0的个数; int sum=0; for (int i=0;i<11;i++){     for (int j = 0; j < 11; j++) {  if (chessArr[i][j]!=0){      sum++;  }     } } //2.创建对应的稀疏数组 int sparseArr[][]=new int[sum+1][3]; //给稀疏数组赋值 //第一行 sparseArr[0][0]=11; sparseArr[0][1]=11; sparseArr[0][2]=sum; //第二行// 遍历二维数组,将非零的值放到sparseArr中 int count=0;//用于给sparseArr计数: for (int i = 0; i < 11; i++) {     for (int j = 0; j < 11; j++) {  if (chessArr[i][j]!=0){      count++;      sparseArr[count][0]=i;      sparseArr[count][1]=j;      sparseArr[count][2]=chessArr[i][j];  }     } } //输出稀疏数组的形式 System.out.println(); System.out.println("得到的稀疏数组为------"); for (int i = 0; i <sparseArr.length; i++) {     System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);//输出所在行的第一个数据,第二个数据,第三个数据 } System.out.println();

运行结果:
【大厂必会的数据结构和算法】01-稀疏数组和队列
将稀疏数组转换为原来的二维数组:

//将原始的稀疏数组-》恢复成原来的二维数组 //1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组 int chessArry2[][]=new int[sparseArr[0][0]][sparseArr[0][1]]; //2.读取稀疏数组后几行的数据—(从第二行开始),并赋值给原始的二维数组 for (int i = 1; i < sparseArr.length; i++) {     chessArry2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2]; } //输出恢复后的二维数组 for (int[] row : chessArry2) {     for (int data : row) {  System.out.printf("%d\t",data);     }     System.out.println(); }      } 

【大厂必会的数据结构和算法】01-稀疏数组和队列


二、队列

  • 队列是一个有序列表,可以使用数组或者链表来实现
  • 遵循先入先出的原则,即:先存入队列的数据,要先取出,后存入的要后取出
  • 示意图:front随着数据输出而改变,rear随着数据输入而改变
    【大厂必会的数据结构和算法】01-稀疏数组和队列

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

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

(2)代码实现

//编写一个叫做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;//指向队列头部,指向队列头的前一个位置 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("队列时空的,没有数据");     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];    }

【大厂必会的数据结构和算法】01-稀疏数组和队列


三、数组模拟环型队列

(1)问题分析及优化

  1. 目前数组使用一次就不能用,没有达到复用效果
  2. 将这个数组使用算法,改进成一个环型队列

数组模拟环型队列思路分析:

  1. front变量的含义做一个调整:front指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素,front初始值=0
  2. rear变量的含义做一个调整:rear指向队列最后一个元素的后一个位置,因为希望空出一个空间作为约定;rear初始值=0
  3. 当队列满时:(rear+1)%maxSize=front【满】
  4. 当队列为空的条件:rear=front【空】
    5.队列中有效的数据的个数:(rear+maxSize-front)%maxSize

(2)代码实现

public class CircleArrayQueueDemo {    public static void main(String[] args) { //数组模拟环型队列 System.out.println("测试数组模拟环型队列的案例~~~~~"); //创建一个环型队列 CircleArrray queue = new CircleArrray(4);//设置为4,其实有效使用空间为3 char key=' ';//接受用户输入 Scanner scanner = new Scanner(System.in); boolean loop=true; while (loop) {     System.out.println("s(show):显示队列");     System.out.println("e(excit):退出程序");     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;  default:      break;     } } System.out.println("程序退出~~~~~~~~");    }}class CircleArrray{    private int maxSize;//表示最大容量    private int front;//队列头    private int rear;//队列尾    private int[] arr;//该数组用于存放数据,模拟队列    //构造器    public CircleArrray(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是指向队列的第一个元素 //先将front对应的值保存到一个临时变量 int value=arr[front]; //将front后移front= (front+1)%maxSize;//将临时保存的变量返回return  value;    }    //显示所有队列数据    public  void showQueue(){ //遍历 if (isEmpty()){     System.out.println("队列时空的,没有数据");     return; } //从front开始遍历,遍历多少个元素 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+maxSize-front) % maxSize;    }}

运行结果展示:
【大厂必会的数据结构和算法】01-稀疏数组和队列


如果感觉内容写的还不错的话,一键三连不迷路!!!!
后面将会更新更多学习内容,一起学习吧!!!!!!
在这里插入图片描述