数据结构与算法的关系
几个实际编程中遇到的问题
要想写出优秀的算法，首先应该能读懂别人写好的算法。
将生活中遇到的实际问题，使用程序来解决
线性结构和非线性结构
线性结构和非线性结构的关系：
数据结构：线性结构 + 非线性结构
线性结构：数据元素之间是 一对一 的关系
非线性结构：数据元素之间是 一对多 或 多对多 的关系
线性结构的存储方式：顺序存储 + 链式存储
顺序存储：数据存储在一片连续的地址空间中
链式存储：数据的存储空间可能并不连续。元素节点中存储的是「数据元素」和「相邻元素的地址信息」
常见的线性结构：数组、链表（两种不同的存储方式）、栈、队列
非线性结构：树、图、（集合）、二维数组、多维数组、广义表
1. 线性结构
2. 非线性结构
一、稀疏数组
1. 应用场景
普通的二维数组记录数据时，可能存放大量的无效数据，导致存储空间的浪费
2. 基本介绍
稀疏数组的应用背景：二维数组中存放大量的无效数据时，可使用稀疏数组
稀疏数组的处理方法：
记录数组一共有几行几列、有多少个有效数据（第一行）将有效数据的行、列、值存储到数组中（其余行）
二维数组和稀疏数组的对应关系图：
第一行：数组信息
其余行：有效数据信息
3. 案例
有大量的无效数据0
4. 分析
二维数组如何转换为稀疏数组：
需要知道
稀疏数组的行：有效数据的个数+1
稀疏数组的列：3
有效数据的个数：设置一个计数器，通过遍历来获取
有效数据的信息：通过遍历数组来获取
稀疏数组如何转换为二维数组：
根据稀疏数组的第一行：创建二维数组
遍历稀疏数组：然后为二维数组赋值
最终保存到磁盘即可（IO）
整体思路：
5. 代码实现：
6. 课后题：
7. 完整代码
package com.SparseArray_01;import java.io.*;import java.nio.charset.StandardCharsets;import java.nio.file.Files;import java.nio.file.Paths;import java.util.List;public class SparseArray {public static void main(String[] args) {/*** 1. 创建一个二维数组，并存储数据* 2. 输出二维数组中的数组* 3. 将二维数组转换为稀疏数组* 4. 输出稀疏数组中的数据* 5. 将稀疏数组的数据转为二维数组* 6. 输出二维数组中的数据* 7. 将稀疏数组写入到 map.txt 文件中* 8. 将稀疏数组从 map.txt 文件中读取出来* 9. 从文件中读出稀疏数组的结果，打印在控制台*/// 1. 创建一个二维数组，并存储数据int chessArr1[][] = new int[11][11];chessArr1[1][2] = 1;chessArr1[2][3] = 2;chessArr1[3][4] = 1;chessArr1[3][3] = 2;// 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();}// 3. 将二维数组转换为稀疏数组int sum = 0; // 记录有效数据的个数for(int i = 0; i < chessArr1.length; i++) {for (int j = 0; j < chessArr1[i].length; j++) {if (chessArr1[i][j] != 0) {sum++;}}}//稀疏数组int sparseArray[][] = new int[sum+1][3];sparseArray[0][0] = 11;sparseArray[0][1] = 11;sparseArray[0][2] = sum;//填充有效数据int count = 0;for (int i = 0; i < chessArr1.length; i++) {for (int j = 0; j < chessArr1[i].length; j++) {if (chessArr1[i][j] != 0) {count++;sparseArray[count][0] = i;sparseArray[count][1] = j;sparseArray[count][2] = chessArr1[i][j];}}}// 4. 输出稀疏数组中的数据System.out.println("稀疏数组如下图所示：");for (int i = 0; i < sparseArray.length; i++) {System.out.print(sparseArray[i][0] + "\t" + sparseArray[i][1] + "\t" + sparseArray[i][2] + "\n");}// 5. 将稀疏数组的数据转为二维数组int[][] chessArr2 = new int[sparseArray[0][0]][sparseArray[0][1]];for (int i = 1; i < sparseArray.length; i++) {chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];}// 6. 输出二维数组中的数据System.out.println("稀疏数据转为二维数组后，如下图所示：");for (int i = 0; i < chessArr2.length; i++) {for (int j = 0; j < chessArr2[i].length; j++) {System.out.print(chessArr2[i][j] + "\t");}System.out.println();}// 7. 将稀疏数组写入到 map.txt 文件中PrintWriter pw = null;try {pw = new PrintWriter("D:/map.txt");StringBuffer stringBuffer = new StringBuffer();for (int i = 0; i < sparseArray.length; i++) {for (int j = 0; j < sparseArray[i].length; j++) {stringBuffer.append(sparseArray[i][j] + "\t");}stringBuffer.append("\n");}pw.println(stringBuffer);} catch (FileNotFoundException e) {e.printStackTrace();}finally {pw.close();}// 8. 将稀疏数组从 map.txt 文件中读取出来try {List<String> lines = Files.readAllLines(Paths.get("D:/map.txt"), StandardCharsets.UTF_8);// 这里lines集合，最后一行是空行，需要省去for (int i = 0; i < lines.size()-1; i++) {// 这里在分割时要注意，如果使用" "来分割的话，会将\t也存入到数组中，这里我们只想将字符串存入到数组中String[] s = lines.get(i).split("\t");for (int j = 0; j < s.length; j++) {sparseArray[i][j] = Integer.parseInt(s[j]);}}} catch (IOException ioException) {ioException.printStackTrace();}// 9. 从文件中读出稀疏数组的结果，打印在控制台System.out.println("从文件中读出稀疏数组的结果：");for (int i = 0; i < sparseArray.length; i++) {for (int j = 0; j < sparseArray[i].length; j++) {System.out.print(sparseArray[i][j] + "\t");}System.out.println();}}}
如果觉得《尚硅谷01 数据结构与算法_数据结构与算法介绍+稀疏数组》对你有帮助，请点赞、收藏，并留下你的观点哦！
