1. 稀疏数组
package com.summer.sparsearray;
/**
* 稀疏数组
* 2020/7/11
* io流处理
*/
public class Sparsearrary {
public static void main(String[] args) {
//1. 创建初始数组
int chess1[][] = new int[11][11];
chess1[1][2] = 1;
chess1[2][4] = 2;
//2. 查看初始数组
for (int[] row : chess1) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
//3. 计算sum
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chess1[i][j]!=0){
sum++;
}
}
}
System.out.println("sum" + sum);
//4. 创建稀疏数组 第一行存储 原数组的 行 列 不同数据个数
int sparse[][] = new int[sum+1][3];
//5. 往稀疏数组中存值
//先存第一行的值
sparse[0][0] = 11;
sparse[0][1] = 11;
sparse[0][2] = sum;
//创建一个计数器count 来记录第几行
int count = 1;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chess1[i][j]!=0){
sparse[count][0] = i;
sparse[count][1] = j;
sparse[count][2] = chess1[i][j];
count++;
}
}
}
//查看稀疏数组
for (int[] row : sparse) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
//6. 将稀疏数组还原为初始数组
int chess2[][] = new int[sparse[0][0]][sparse[0][1]];
for (int i = 1; i <= sparse[0][2]; i++) {
chess2[sparse[i][0]][sparse[i][1]] = sparse[i][2];
}
//查看chess2
System.out.println("chess2:");
for (int[] row : chess2) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
}
}
2.队列
特点：先入先出
- rear 头
- front 尾
- maxsize 队列容量的最大值
数据加在尾部，在头部取数据
ArrayQueue 对象
属性：
- maxSize 队列容量的最大值
- rear 头部
- front 尾部
- arr 数组
实现方法：
- isFull () 判断队列是否已满
- isEmpty() 判断数组是否为空
- addQueue() 入队
- getQueue() 出队
- showQueue() 展示所有的数据
- headQueue() 获取头部的数据
public class ArrayQueue {
private Integer maxSize;
private Integer rear;
private Integer front;
private int[] arr;
//初始化数组
public ArrayQueue(Integer maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
rear = -1; //指向队列的头部，front指向队列的头部前面一个位置
front = -1; // 指向尾部，就是队列的最后一个数据
}
//判断队列是否已满
public Boolean isFull(){
return front == maxSize-1;
}
//判断数组是否为空
public Boolean isEmpty(){
return rear==front;
}
//添加数据
public void addQueue(int data){
//判断数组是否已经满了
if (isFull()) {
System.out.println("队列已经满了");
}
front++;
arr[front] = data;
}
//取数据
public int getQueue(){
//判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列为空—");
}
rear++;
return arr[rear];
}
//显示队列中所有的数据
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[rear+1];
}
}
问题：
- 数组只能使用一次就不能再使用，没有达到复用的效果。
解决方法：
- 改造成为环形的队列 使用 ==%==
- 取模复用！！！！
环形队列
- front指向队列的第一个元素，即arr[front]就是队列的第一个元素。front的初值为0
- rear指向队列的最后一个元素的后一个位置。空出一个空间来进行判断。rear的初值为0
- 队列满的条件：（rear+1）%maxSize =front
- 队列为空的条件：rear = front
- 队列中有效的数据个数为（rear+maxSize-front）%maxSize
- 有一个空间我们用来判断队列是否为满，不能存值，
实现环形队列
public class CircleArrayQueue {
private Integer maxSize;
private Integer rear;
private Integer front;
private int[] arr;
//初始化数组
public CircleArrayQueue(Integer maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
front = 0; //指向队列的头部
rear = 0; // 指向尾部，就是队列的最后一个数据的后一个位置
}
//判断队列是否已满
public Boolean isFull(){ return (rear + 1) % maxSize == front; }
//判断数组是否为空
public Boolean isEmpty(){
return rear==front;
}
//添加数据
public void addQueue(int data){
//判断数组是否已经满了
if (isFull()) {
System.out.println("队列已经满了");
return;
}
arr[rear] = data;
rear = (rear+1) % maxSize;
}
//取数据
public int getQueue(){
//判断队列是否为空
if (isEmpty()) { throw new RuntimeException("队列为空—"); }
int value = arr[front];
front = (front+1)%maxSize;
return value;
}
//显示队列中所有的数据
public void showQueue(){
// 判断数组是否为空
if (isEmpty()) {
System.out.println("队列为空，没有数据");
return;
}
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];
}
}
网友评论