-
数据结构与算法-稀疏数组和队列
最近在小破站看尚硅谷的《数据结构与算法》，目前学了有一半了，想把之前的知识回顾一下，顺便写一下博客，记录一下之前写的代码。这里的理论知识，基本是copy的尚硅谷的讲义，代码则是自己写的。
数据（data）结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。
数据结构分为线性结构和非线性结构
线性结构：
（1） 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系；
（2）线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的；
（3）链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息；
（4）线性结构常见的有：数组、队列、链表和栈。非线性结构主要包括：二维数组，多维数组，广义表，树结构，图结构。
稀疏数组
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。稀疏数组的处理方法是:
记录数组一共有几行几列，有多少个不同的值；
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
这里看起来一目了然，但为了写代码不乱，最好明确一下思路
二维数组转稀疏数组的思路：
- 遍历原始的二维数组，得到有效数据的个数sum；
- 根据sum创建稀疏数组sparseArr int[sum+1][3]（多行三列）；
- 将二维数组的有效数据存入到稀疏数组
顺便提一下稀疏数组转二维数组的思路：
- 先读稀疏数组的第一行，根据第一行的数据，创建原始的二维数组；
- 再读稀疏数组后几行的数据，并赋给二维数组。
下面是二维转稀疏，稀疏转二维的代码
package sparseArray; //稀疏数组 public class SparseArray { public static void main(String[] args) { int [][]array=new int [8][7]; array[1][3]=1; array[5][6]=1; int[][] res = transfer(array); System.out.println("二维数组转稀疏数组"); for(int i=0;i<res.length;i++){ for(int j=0;j<res[i].length;j++){ System.out.print(res[i][j]+"\t"); } System.out.println(); } System.out.println("==================================="); System.out.println("稀疏数组转二维数组"); int[][] res2 = transfer2(res); for(int i=0;i<res2.length;i++){ for(int j=0;j<res2[i].length;j++){ System.out.print(res2[i][j]+"\t"); } System.out.println(); } } //arr.length表示行数 //arr[i].length表示列数 //二维数组转稀疏数组 public static int[][] transfer(int[][] arr){ int sum=0;//用来存储二维数组有几个非0元素 for(int i=0;i<arr.length;i++){ for(int j=0;j<arr[i].length;j++){ if(arr[i][j]!=0){ sum++; } } } int [][]sparse=new int[sum+1][3];//定义稀疏数组 sparse[0][0]=arr.length; sparse[0][1]=arr[0].length; sparse[0][2]=sum; sum=1; for(int i=0;i<arr.length;i++){ for(int j=0;j<arr[i].length;j++){ if(arr[i][j]!=0){ sparse[sum][0]=i; sparse[sum][1]=j; sparse[sum][2]=arr[i][j]; sum++; } } } return sparse; } //稀疏数组转二维数组 public static int[][] transfer2(int[][] arr){ int[][] array=new int[arr[0][0]][arr[0][1]];//定义二维数组 for(int i=1;i<arr.length;i++){ for(int j=0;j<arr[i].length;j++){ array[arr[i][0]][arr[i][1]]=arr[i][2]; } } return array; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
测试结果：
队列
队列是一个有序列表，可以用数组或链表来实现 队列遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。队列本身是有序列表，若使用数组的结构来存储队列的数据，队列数组的声明如下图，其中，maxSize是该队列的最大容量。
因为队列的输出、输入分别是从前后端来处理，因此需要两个变量front和rear分别记录队列前后端的下标，front会随着数据输入而改变，rear会随着数据输出而改变
添加数据，尾指针后移，rear+1；取出数据：头指针向后移，front+1
注：rear和front默认值为-1
队列为空和队列满的判断条件：
- front=rear：空
- rear=maxSize-1：队列满
用数组模拟一个队列，主要有以下几个方法：
- 判断队列是否满isFull()
- 判断队列是否空isEmpty()
- 添加数据addQueue()
- 取出数据getQueue()
- 显示队列数据showQueue()
- 显示队列头部数据headQueue()
具体代码如下：
class Array{ private int maxSize;//表示数组的最大容量 int arr[];//该数组用于存放数据，模拟队列 int front;//队列头 int rear;//队列尾 //创建队列 public Array(int maxSize){ this.maxSize=maxSize; // new Array(); arr=new int[maxSize]; front=-1; rear=-1; } //判断队列是否满 boolean isFull(){ return rear==maxSize-1; } //判断队列是否为空 boolean isEmpty(){ return rear==front; } //添加数据 void addQueue(int num){ if(isFull()){ System.out.println("队列已满，无法添加数据"); return; } rear++; arr[rear]=num; } //取出数据 Integer getQueue() throws Exception { if(isEmpty()){ throw new Exception("队列已空"); } front++; return arr[front]; } //显示队列数据 void showQueue(){ for (int i = front+1; i < rear+1; i++) { System.out.print(arr[i]+"\t"); } } //显示队列头部数据 void headQueue(){ System.out.println("队列的头部数据："+arr[front+1]); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
由于队列的整体思想比较简单，这里就不写测试类了。需要注意的是，我们在取出数据时让front++，这就导致了队列的存放是有限的，不能超过数组的大小。即使放入的数据已经取完了，也不能再存了，因为此时rear=maxSize-1。不能再加了。
这是一个非常不好的体验，基于此，再聊一下环形队列。
数组模拟环形队列
将数组看做是一个环形的（通过取模的方式实现）
这里front和rear的含义变了- front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值为0
- rear指向队列最后一个元素的后一个位置，因为希望空出来一个空间做约定。rear的初始值为0
注：maxSize指数组的长度
队列满的判断条件：(rear+1)%maxSize == front
队列空的判断条件：rear== front
队列中有效数据的个数：(rear+maxSize-front)%maxSize聊一下我对这三个公式的理解。在谈这几个公式前，理解里面的参数尤为重要。maxSize，指的是数组的长度，这个数组，就是我们用来模拟环形数列的数组。front，指的是队列的第一个元素，默认值是1；rear，指的是队列最后一个元素的后一个位置，默认值也为1。值得一提的是，这里空出来一个位置作为约定，这里不用深究其含义，只需知道这个空出来的位置也是动态变化的就好。
举个栗子，钟表有12个数字，1-12。但其实应该有13个数字，再多一个0。这样理解的话，13个数字最多表示12个小时，是不是有点环形队列的味了。把这13个数字想成是一个数组，数组的长度是13，也就是maxSize=13。时针转一圈表示12个小时，就是说这个“队列”满的时候里面有12个元素。那我们来验证一下-
这个队列中，我放入了12个元素，一个也没有取，此时front=0，rear=12（元素最多排到11，因为需要留一个位置作为约定）。此时（rear+1）%maxSize=0，front=0，等式成立。
-
队列空的判断条件这里就不进行展示了，比较容易。
-
第三个情况，就是求队列中的有效个数，这个更容易理解。我们可以先考虑最简单的情况，就是rear>front的情况，这种情况这个条件完全满足。或者写成（rear-front）也可以，那为什么要写成(rear+maxSize-front)%maxSize呢？因为这是一个环形队列，随着添加元素，取出元素的循环执行，最后rear可能小于front，这样直接相减就成负数了，有效个数又怎会变为负数呢？很明显，给他加一个maxSize就好了，但也没完全好。要是直接这么写，rear本来比front大的情况，结果就大于maxSize了，最终再对maxSize取余，两种情况就都能使用了。
下面的图展示一下rear
还是一样的数组，先存满，然后取六个数据，再加入六个数据。显然有效数据还是12个。用公式验证一下,此时front=6，rear=5。(rear+maxSize-front)%maxSize=（5+13-6）%13=12。和分析的结果一样。
分析到这里，就可以着手写代码了，具体的代码如下：
class Queue { int[] arr;//模拟环形队列 int maxSize; int front;//指向第一个元素 int rear;//指向最后一个元素的最后一个位置 public Queue(int maxSize) { this.maxSize = maxSize; arr = new int[maxSize]; front = 0; rear = 0; } //判断队列是否为空 public boolean isEmpty() { return front == rear; } //判断队列是否满 public boolean isFull() { return (rear + 1) % maxSize == front; } //添加元素 public void addEle(int num) { if (isFull()) { System.out.println("队列已满，不能添加元素"); return; } arr[rear] = num; rear = (rear + 1) % maxSize; } //取出元素 public int getEle() { if (isEmpty()) { System.out.println("队列已空，不能取出元素"); return -99999999; } int num = arr[front]; front = (front + 1) % maxSize; return num; } //求队列的有效个数 public int getNums() { return (rear + maxSize - front) % maxSize; } //遍历元素 public void show() { if (isEmpty()) { System.out.println("队列已空"); } for (int i = front; i < front+getNums(); i++) { System.out.print(arr[i%maxSize] + "\t"); } // 错误的代码（不知道为什么错了 // for (int i = front; i < front + getNums(); i = (i + 1) % maxSize) { // System.out.print(arr[i] + "\t"); // } } //展示顶部元素（不取出） public int showHead() { return arr[front]; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
即便是再次复习，也出现错误了。在遍历元素的时候，不知道下面那种情况为什么行不通。还望知道的朋友评论区解答一下
-
相关阅读:
基础 | 并发编程 - [多线程进度控制]
骨传导运动耳机排行榜，目前最好的几款骨传导耳机分享
在Java中使用XxlCrawler时防止被反爬的几种方式
ios的info.plist 配置
[ 环境搭建篇 ] docker 搭建部署 YAPI 框架
10.正则表达式匹配
SpringMVC的请求与响应和参数传递
【Html+JS+CSS】简易轮播图核心代码分享 + 效果展示
Android Camera性能分析 - 第17讲 拍照性能分析
SpringMVC对JSON的支持& SpringMVC的全局异常处理
- 原文地址：https://blog.csdn.net/qq_45142938/article/details/125987278
