【大厂必会的数据结构和算法】01-稀疏数组和队列
文章目录
开篇
数据结构包括:线性结构和非线性结构
线性结构
- 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对有的线性关系
- 线性结构有两种不同的存储结构,及顺序存储结构(数组)和链式存储结构(链表)。顺序存储结构的线性表称为顺序表,顺序表中的元素是连续的;如数组;
- 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放元素以及相邻元素的地址信息;
- 线性结构常见的有:数组,队列,表,链表和栈
非线性结构:
非线性结构包括:二维数组,多为数组,广义表,树结构,图结构
一、稀疏数组
当一个数组中大部分元素为0,或者同一个值的数组时,可以使用稀疏数组来保存该数组。
(1)稀疏数组的处理方法是:
- 记录数组有几行几列,有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模;
(2)思路分析
二维数组转稀疏数组的思路:
- 遍历原始的二维数组,得到有效的个数sum
- 根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
- 将二维数组的有效数据存入到稀疏数组中
稀疏数组转原始的二维数组思路:
- 先读取稀疏数组的第一行,根据第一行的数据创建原始的二维数组
- 读取稀疏数组后几行的数据,并赋值给原始的二维数组
(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();
将原始的二维数组转换为稀疏数组;
// 将二维数组转为为稀疏数组 //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();
运行结果:
将稀疏数组转换为原来的二维数组:
//将原始的稀疏数组-》恢复成原来的二维数组 //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(); } }
二、队列
- 队列是一个有序列表,可以使用数组或者链表来实现
- 遵循先入先出的原则,即:先存入队列的数据,要先取出,后存入的要后取出
- 示意图:front随着数据输出而改变,rear随着数据输入而改变
当我们将数据存入队列时称为“addQueue”,addQuene的处理需要有两个步骤:
- 将尾指针往后移。rear+1,当front=rear则表明队列为空
- 若尾指针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]; }
三、数组模拟环型队列
(1)问题分析及优化
- 目前数组使用一次就不能用,没有达到复用效果
- 将这个数组使用算法,改进成一个环型队列
数组模拟环型队列思路分析:
- front变量的含义做一个调整:front指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素,front初始值=0
- rear变量的含义做一个调整:rear指向队列最后一个元素的后一个位置,因为希望空出一个空间作为约定;rear初始值=0
- 当队列满时:(rear+1)%maxSize=front【满】
- 当队列为空的条件: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; }}
运行结果展示:
如果感觉内容写的还不错的话,一键三连不迷路!!!!
后面将会更新更多学习内容,一起学习吧!!!!!!