Java-数据结构基础1

Java数据结构实现 1. 稀疏数组（Sparse Array）的实现

在实际编程中，我们经常会遇到这样的场景：一个二维数组中大部分元素都是0（或者是同一个值），只有少部分元素有不同值。这种情况下，如果我们直接存储整个二维数组，会造成极大的空间浪费。这时候，我们就可以使用稀疏数组来解决这个问题。

1.1 稀疏数组的基本概念

稀疏数组的处理方法是：

记录数组一共有几行几列，有多少个不同的值把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模 1.2 代码实现 public class SparseArray { public static void main(String[] args) { // 创建原始二维数组 11*11 int arrays[][] = new int[11][11]; // 初始化几个值 arrays[1][2] = 1; arrays[2][3] = 2; arrays[5][6] = 2; // 输出原始二维数组 System.out.println("原始二维数组："); for(int row[] : arrays) { for(int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 统计非0值的个数 int sum = 0; for(int i = 0; i < 11; i++) { for(int j = 0; j < 11; j++) { if(arrays[i][j] != 0) { sum++; } } } // 创建稀疏数组 int sparse[][] = new int[sum + 1][3]; // 记录原始数组的行列和有效数据个数 sparse[0][0] = 11; sparse[0][1] = 11; sparse[0][2] = sum; // 将非0的值存入稀疏数组 int count = 0; for(int i = 0; i < 11; i++) { for(int j = 0; j < 11; j++) { if(arrays[i][j] != 0) { count++; sparse[count][0] = i; sparse[count][1] = j; sparse[count][2] = arrays[i][j]; } } } // 输出稀疏数组 System.out.println("\n转换后的稀疏数组："); for(int row[] : sparse) { for(int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 还原二维数组 int newarrays[][] = new int[sparse[0][0]][sparse[0][1]]; for(int i = 1; i < sparse.length; i++) { newarrays[sparse[i][0]][sparse[i][1]] = sparse[i][2]; } // 输出还原后的二维数组 System.out.println("\n还原后的二维数组："); for(int row[] : newarrays) { for(int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } } 1.3 稀疏数组实现要点 稀疏数组的第一行保存原始二维数组的行数、列数和有效数据个数之后的每一行保存一个有效数据的行、列和值还原时只需要读取稀疏数组的第一行创建原始大小的数组，然后逐个还原有效数据 2. 循环数组队列的实现

循环队列是一种线性数据结构，它的特点是把队列的首尾相连，形成一个环。这样可以更有效地利用数组空间，避免假溢出的问题。

2.1 循环队列的基本概念 front：队列头指针，指向队列的第一个元素rear：队列尾指针，指向队列最后一个元素的下一个位置maxSize：队列的最大容量 2.2 代码实现 class CircleArray { private int maxSize; private int front; private int rear; private int[] arr; public CircleArray(int maxsize) { maxSize = maxsize; arr = new int[maxSize]; // front和rear初始值为0 } // 判断队列是否已满 public boolean IsFulled() { return (rear + 1) % maxSize == front; } // 判断队列是否为空 public boolean IsEmpty() { return rear == front; } // 添加数据到队列 public void AddQueue(int n) { if(IsFulled()) { System.out.println("队列已满"); return; } arr[rear] = n; rear = (rear + 1) % maxSize; } // 从队列取出数据 public int GetQueue() { if(IsEmpty()) { throw new RuntimeException("队列空"); } int value = arr[front]; front = (front + 1) % maxSize; return value; } // 查看队列头部数据 public int HeadQueue() { if(IsEmpty()) { throw new RuntimeException("队列空"); } return arr[front]; } // 显示队列所有数据 public void ListQueue() { 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; } } 2.3 循环队列实现要点 队列满的条件是：(rear + 1) % maxSize == front队列空的条件是：rear == front队列中有效数据的个数：(rear + maxSize - front) % maxSize入队和出队操作都需要使用取模运算来实现循环 2.4 队列状态图解 2.4.1 初始状态 [ ][ ][ ][ ][ ] maxSize = 5 ↑ f,r 说明： - front = 0, rear = 0 - 队列为空 2.4.2 添加元素 添加元素 1, 2, 3： [1][2][3][ ][ ] ↑ ↑ f r 说明： - front = 0 - rear = 3 - 有效元素个数 = 3 2.4.3 队列满状态 [1][2][3][4][ ] ↑ ↑ f r 说明： - 最后一个位置必须空出来 - 满队列条件：(rear + 1) % maxSize == front 2.4.4 出队操作 初始： [1][2][3][4][ ] ↑ ↑ f r 出队一个元素后： [ ][2][3][4][ ] ↑ ↑ f r 说明： - front = (front + 1) % maxSize 2.4.5 循环利用空间 初始： [1][2][3][4][ ] ↑ ↑ f r 出队两个元素后： [ ][ ][3][4][ ] ↑ f ↑ r 再添加元素5： [5][ ][3][4][ ] ↑ f ↑ r 说明： - 通过取模运算实现空间复用 2.5 核心操作解析 2.5.1 判断队列是否已满 public boolean IsFulled() { return (rear + 1) % maxSize == front; } 示意图： [1][2][3][4][ ] ↑ ↑ f r - rear的下一个位置是front时，队列满 2.5.2 判断队列是否为空 public boolean IsEmpty() { return rear == front; } 示意图： [ ][ ][ ][ ][ ] ↑ f,r - front和rear指向同一位置时，队列空 2.5.3 计算队列有效数据个数 public int Size() { return (rear + maxSize - front) % maxSize; } 示意图： [5][ ][3][4][ ] ↑ f ↑ r 计算过程： 1. rear = 1 2. front = 2 3. maxSize = 5 4. (1 + 5 - 2) % 5 = 4 % 5 = 4 2.6 实际应用示例 2.6.1 数据入队过程 1. 初始状态： [ ][ ][ ][ ][ ] ↑ f,r 2. 添加1： [1][ ][ ][ ][ ] ↑ ↑ f r 3. 添加2： [1][2][ ][ ][ ] ↑ ↑ f r 4. 添加3： [1][2][3][ ][ ] ↑ ↑ f r 2.6.2 数据出队过程 1. 初始状态： [1][2][3][ ][ ] ↑ ↑ f r 2. 出队一个元素： [ ][2][3][ ][ ] ↑ ↑ f r 3. 添加新元素4： [4][2][3][ ][ ] ↑ ↑ f r 总结

稀疏数组的优点：

节省存储空间适合处理大规模稀疏数据压缩和还原过程简单高效

循环队列的优点：

避免了普通队列的"假溢出"问题能够充分利用数组空间实现了队列的先进先出特性

实际应用场景：

稀疏数组：棋盘游戏存储、地图数据压缩等循环队列：消息队列、打印机任务队列、实时数据处理等