数据结构包括：线性结构和非线性结构。所以博主会通过这两个角度来对线性结构和非线性结构进行梳理归纳。
1.稀疏(sparse array)数组
需求引入
分析问题
1.1 介绍
当一个数组中大部分元素为 0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是：
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
1.2 二维数组转稀疏数组的思路
1.3 稀疏数组转二维数组的思路
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 数组模拟队列
1.3 思路分析
当我们将数据存入队列时称为”addQueue”,addQueue 的处理需要有两个步骤：
将尾指针往后移：rear+1,当 front==rear【空】
若尾指针 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 前面还有没有空余的元素
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]; }}
复制代码
其实对于队列的话没有特别难理解的点,看着博主的文章就好了跟着里面的注释一步步操作下来就好了
评论