当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
1) 记录数组一共有几行几列,有多少个不同的值
2) 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
举例说明:
3.1.1 应用实例
1) 使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等)
2) 把稀疏数组存盘,并且可以从新恢复原来的二维数组数
3) 整体思路分析
代码实现:
1 package com.hut.sparsearray; 2 3 public class SparseArray { 4 5 public static void main(String[] args) { 6 //一、将二维数组转化为稀疏数组 7 //0:表示没有棋子,1:表示黑子,2:表示蓝子 8 //1、创建原始二维数组 10*10 9 int chessArr[][] = new int [10][10]; 10 //赋值二维数组 11 chessArr[1][1] = 1; 12 chessArr[3][2] = 2; 13 chessArr[5][3] = 2; 14 chessArr[7][5] = 1; 15 //输出原始二维数组的形式 16 System.out.println("输出原始的二维数组:"); 17 for(int [] row:chessArr) { 18 for(int data:row) { 19 System.out.printf("%d ",data); 20 } 21 System.out.println(); 22 } 23 //2、遍历原始二维数组得到非0数据的个数 24 int sum = 0;//记录总非0个数 25 for(int i=0;i<10;i++) { 26 for(int j=0;j<10;j++) { 27 if(chessArr[i][j] != 0) 28 sum ++; 29 } 30 } 31 //3、创建稀疏数组 32 int sparseArr[][] = new int [sum+1][3]; 33 //给稀疏数组第一行赋值 34 sparseArr[0][0] = 10; 35 sparseArr[0][1] = 10; 36 sparseArr[0][2] = sum; 37 38 //4、将二维数组的有效值存入到稀疏数组中 39 int count = 0; //用于记录第几个非0数据 40 for(int i=0;i<10;i++) { 41 for(int j=0;j<10;j++) { 42 if(chessArr[i][j] != 0) { 43 count ++; 44 sparseArr[count][0] = i; 45 sparseArr[count][1] = j; 46 sparseArr[count][2] = chessArr[i][j]; 47 } 48 } 49 } 50 //5、输出稀疏数组 51 System.out.println(); 52 System.out.println("输出稀疏数组的形式:"); 53 for(int i =0;i<sparseArr.length;i++) { 54 System.out.printf("%d %d %d ",sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); 55 } 56 57 58 59 60 //二、将稀疏数组转化为二维数组 61 //1、读取稀疏数组的第一行,据此创建二维数组 62 int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]]; 63 //2、读取 稀疏数组后面的几行数据(从第二行开始),并赋值给二维数组 64 for(int i = 1;i < sparseArr.length;i++) { 65 chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; 66 } 67 //3、输出二维数组 68 System.out.println(); 69 System.out.println("稀疏 数组转化后的二维数组:"); 70 for(int[] row:chessArr2) { 71 for(int data:row) { 72 System.out.printf("%d ",data); 73 } 74 System.out.println(); 75 } 76 77 78 } 79 80 }
代码实现:
1 package com.hut.queue; 2 3 import java.util.Scanner; 4 5 public class ArrayQueueDemo { 6 7 public static void main(String[] args) { 8 //创建一个队列 9 ArrayQueue queue = new ArrayQueue(3); 10 char key =' '; //用于接收用户输入 11 Scanner scanner = new Scanner(System.in); 12 boolean loop = true; 13 //输出一个菜单 14 while(loop) { 15 System.out.println("s,show:显示队列"); 16 System.out.println("a,add:添加数据到队列"); 17 System.out.println("g,get:从队列获取数据"); 18 System.out.println("h,head:查看队列头的数据"); 19 System.out.println("e,exit:退出程序"); 20 key = scanner.next().charAt(0);//接收一个字符 21 switch(key) { 22 case 's': 23 queue.showQueue(); 24 break; 25 case 'a': 26 System.out.println("请输入添加的数据:"); 27 int value = scanner.nextInt(); 28 queue.addQueue(value); 29 break; 30 case 'g': 31 try { 32 int res = queue.getQueue(); 33 System.out.printf("取出的数据是:%d ",res); 34 }catch(Exception e){ 35 System.out.println(e.getMessage()); 36 } 37 break; 38 case 'h': 39 try { 40 int res = queue.headQueue(); 41 System.out.printf("取出的头部数据是:%d ",res); 42 }catch(Exception e){ 43 System.out.println(e.getMessage()); 44 } 45 break; 46 case 'e': //退出 47 scanner.close(); 48 loop = false; 49 break; 50 default: 51 break; 52 } 53 } 54 System.out.println("退出程序~~"); 55 56 } 57 58 } 59 60 //使用数组模拟队列--编写一个ArrayQueue类 61 class ArrayQueue{ 62 private int maxSize; //表示数组的最大容量 63 private int front; //队列的头 64 private int rear; //队列的尾 65 private int[] arr; //该数组用于存放数据,模拟队列 66 67 //创建队列构造器 68 public ArrayQueue(int arrMaxSize) { 69 maxSize = arrMaxSize; 70 front = -1; //指向队列头部,front是指向队列头的前一个位置 71 rear = -1; //指向队列尾部,rear指向队列尾的数据(即队列最后一个数据) 72 arr = new int[maxSize]; 73 } 74 75 //判断队列是否满 76 public boolean isFull() { 77 return rear == maxSize - 1; 78 } 79 80 //判断队列是否为空 81 public boolean isEmpty() { 82 return rear == front; 83 } 84 85 //添加数据到队列 86 public void addQueue(int n) { 87 //判断队列是否为满 88 if(isFull()) { 89 System.out.println("队列满,不能加入数据~~"); 90 return; 91 } 92 rear ++; 93 arr[rear] = n; 94 } 95 96 //获取队列的数据,出队列 97 public int getQueue() { 98 //判断队列是否为空 99 if(isEmpty()) { 100 //通过抛出异常 101 throw new RuntimeException("队列空,不能取数据"); 102 } 103 front ++; //front后移 104 return arr[front++]; 105 } 106 107 //显示队列的所有数据 108 public void showQueue() { 109 //判断队列是否为空 110 if(isEmpty()) { 111 System.out.println("队列空,无数据~~"); 112 return; 113 } 114 for(int i=0;i<arr.length;i++) { 115 System.out.printf("arr[%d]=%d ",i,arr[i]); 116 } 117 } 118 119 //显示队列头数据 120 public int headQueue() { 121 //判断是否为空 122 if(isEmpty()) { 123 //通过抛出异常 124 throw new RuntimeException("队列空,无数据"); 125 } 126 return arr[front + 1]; 127 } 128 }
但是这样的实现会出现如下问题:
1) 目前数组使用一次就不能用, 没有达到复用的效果
解决办法:将这个数组使用算法,改进成一个环形的队列 取模:%
思路如下:
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
1 package com.hut.queue; 2 3 import java.util.Scanner; 4 5 public class CircleArrayQueueDemo { 6 7 public static void main(String[] args) { 8 //测试一把 9 System.out.println("测试数组模拟环形队列的案例"); 10 11 //创建一个环形 队列 12 CircleArray queue = new CircleArray(4);//说明设置4,其队列的有效数据最大为3,空出一个空间作为约定。 13 char key = ' '; // 接收用户输入 14 Scanner scanner = new Scanner(System.in);// 15 boolean loop = true; 16 while(loop) { 17 System.out.println("s(show): 显示队列"); 18 System.out.println("a(add): 添加数据到队列"); 19 System.out.println("g(get): 从队列取出数据"); 20 System.out.println("h(head): 查看队列头的数据"); 21 System.out.println("e(exit): 退出程序"); 22 key = scanner.next().charAt(0);// 接收一个字符 23 switch(key) { 24 case 's': 25 queue.showQueue(); 26 break; 27 case 'a': 28 System.out.println(" 请输入一个数据:"); 29 int value = scanner.nextInt(); 30 queue.addQueue(value); 31 break; 32 case 'g': //取出数据 33 try { 34 int res = queue.getQueue(); 35 System.out.printf("取出的数据是:%d ",res); 36 }catch(Exception e) { 37 System.out.println(e.getMessage()); 38 } 39 break; 40 case 'h': //查看队列头数据 41 try { 42 int res = queue.headQueue(); 43 System.out.printf("取出的数据是:%d ",res); 44 }catch(Exception e){ 45 System.out.println(e.getMessage()); 46 } 47 break; 48 case 'e': 49 scanner.close(); 50 loop = false; 51 break; 52 default: 53 break; 54 } 55 } 56 57 System.out.println("程序退出~~"); 58 } 59 60 } 61 62 63 class CircleArray{ 64 private int maxSize; // 表示数组的最大容量 65 66 //front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 67 //front 的初始值 = 0 68 private int front; 69 70 //rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. 71 //rear 的初始值 = 0 72 private int rear; //队列尾 73 74 private int[] arr; //用于存放数据,模拟队列 75 76 77 //创建队列构造器 78 public CircleArray(int arrMaxSize) { 79 maxSize = arrMaxSize; 80 arr = new int[maxSize]; 81 } 82 83 //判断队列是否满 84 public boolean isFull() { 85 return (rear + 1) % maxSize == front; 86 } 87 88 //判断队列是否为空 89 public boolean isEmpty() { 90 return rear == front; 91 } 92 93 //添加数据到队列 94 public void addQueue(int n) { 95 //判断队列是否满 96 if(isFull()) { 97 System.out.println(" 队列已满~~"); 98 return; 99 } 100 //直接将数据加入 101 arr[rear] = n; 102 //将rear后移,这里必须考虑取模 103 rear = (rear + 1) % maxSize; 104 } 105 106 //获取队列的数据,出队列 107 public int getQueue() { 108 //判断队列是否为空 109 if(isEmpty()) { 110 //抛出异常 111 throw new RuntimeException("队列空,不能取数据~~"); 112 } 113 //这里需要分析出front是指向队列的第一个元素 114 // 1. 先把 front 对应的值保留到一个临时变量 115 // 2. 将 front 后移, 考虑取模 116 // 3. 将临时保存的变量返回 117 int value = arr[front]; 118 front = (front + 1)% maxSize; 119 return value; 120 } 121 122 //显示队列的所有元素 123 public void showQueue() { 124 //判断是否为空 125 if(isEmpty()) { 126 System.out.println("队列为空,没有数据~~"); 127 return; 128 } 129 //遍历 130 // 思路:从 front 开始遍历,遍历多少个元素 131 // 动脑筋 132 for(int i = front;i < front + size();i++) { 133 System.out.printf("arr[%d]=%d ", i % maxSize, arr[i % maxSize]); 134 } 135 } 136 137 //求出当前队列有效数据的个数 138 public int size() { 139 return (rear + maxSize - front) % maxSize; 140 } 141 142 143 //显示队列的头数据,注意不是取出 144 public int headQueue() { 145 //判断是否为空 146 if(isEmpty()) { 147 throw new RuntimeException("队列为空,没有数据~~"); 148 } 149 return arr[front]; 150 } 151 }