数据结构学习1-稀疏数组
【转载请注明出处:From李诗雨—https://blog.csdn.net/cjm2484836553/article/details/91345761】
不诗意的女程序猿不是好厨师~
1.一些基础点
1.1数据结构：包括线性结构和非线性结构。
1.2线性结构
- 特点是数据元素之间存在一对一的线性关系.
- 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。
顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。
链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。 - 线性结构常见的有：数组、队列、链表和栈。
1.3非线性结构
- 非线性结构包括：二维数组，多维数组，广义表，树结构，图结构
2.稀疏数组
2.1实际使用场景
在这里插入图片描述
举个栗子来说：
我们都玩过五子棋游戏，那么如果让我们自己撸起袖子来写一个，你会怎么做呢？用什么来表示棋盘棋子？黑棋白棋如何表示？如果下到一半累了不想玩了需要保存棋局该怎么做？打了局王者乏了又想来继续下五子棋，又该如何复局呢？
数组1
现在我们来分析一下，我们可以用一个11*11的二维数组来模拟棋局，二维数组的值来代表棋子，如果是1就表示是黑子，如果是2就表示是蓝子。
如果要实现保存棋盘的功能，就要把这个二维数组保存起来。
但是我们看现在这个二维数组有很多的0值，直接保存起来感觉很浪费。那有没有什么办法可以简化这个二维数组呢？
数组2
我们可以把它优化成如上图所示的二维数组，
第一行用来表示原有数组有几行几列吗，多少个不同的值。
从第二行开始每一行表示 行、列的位置 和对应的值。
所以数组2可以得到的信息是：
原有数组有11行11列有2个不同的值，其中在（1,2）位置的值是1，（2,3）位置的值是2。
看，其实就是对原有数组的另一种表示。而且我们把1111的规模编程了33的规模，是不是大大的做到了简化。
好的，不知不觉中我们就引入了稀疏数组，其实啊，简化后的数组就是一个稀疏数组。下面我们来看看什么是稀疏数组。
2.1稀疏数组的小结
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
记录数组一共有几行几列，有多少个不同的值。
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
3.学以致用，撸代码
在这里插入图片描述
现在让我们按下面的要求来撸一段代码，练习一下：
3.0利用稀疏数组完成棋局的保存和棋局的恢复功能。
分析：
先将如图所示的棋局，用1111的二维数组表示出来，然后把它转化为对应的稀疏数组，存储到本地文件中，这样就完成“棋局的保存”功能。
我们将文件中的内容读取出来，转化为稀疏数组，然后在转化为对应的1111的二维数组，这样就完成了“复盘”功能。
光说不练假把式，具体代码如下：
3.1用11*11的二维数组展示棋局。
/**
* 创建一个11*11的二维数组 ，来模拟五子棋棋盘
* 其中值1代表黑棋，棋2代表蓝棋
*/
int[][] gobangArray = new int[11][11];
gobangArray[1][2] = 1;
gobangArray[2][3] = 2;
System.out.println("原始棋局：");
for (int[] row : gobangArray) {
for (int element : row) {
System.out.printf("%d\t", element);
}
System.out.println();
}
打印结果如下：
在这里插入图片描述
3.2 将 原始数组 转化为 稀疏数组
具体思路：
a. 遍历 原始的二维数组，得到有效数据的个数 sum
b. 根据sum 创建 稀疏数组 sparseArray int[sum + 1] [3]
c. 将二维数组的有效数据数据存入到 稀疏数组
/**
* 遍历原始棋局，得到棋子总数
*/
int sum = 0;
for (int[] row : gobangArray) {
for (int element : row) {
if (element != 0) sum++;
}
}
/**
* 创建稀疏数组 int[sum+1][3]
* 第一行存原始棋局的行数，列数 和 棋子数
* 后面的每一行：第一列 存棋子的所在行下标，第二列 存棋子的所在列下标，第三列 存值
*/
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
int sparseRow = 1;
for (int row = 0; row < 11; row++) {
for (int column = 0; column < 11; column++) {
if (gobangArray[row][column] != 0) {
sparseArray[sparseRow][0] = row;
sparseArray[sparseRow][1] = column;
sparseArray[sparseRow][2] = gobangArray[row][column];
sparseRow++;
}
}
}
/**
* 验证一下
*/
System.out.println();
System.out.println("稀疏数组为：");
for (int[] row : sparseArray) {
for (int element : row) {
System.out.printf("%d\t", element);
}
System.out.println();
}
打印结果如下：
在这里插入图片描述
3.3 将稀疏数组保存到本地的txt文件中
//将稀疏数组存入到文件中
File file = new File("e:\\array.txt"); //存放数组数据的文件
try {
FileWriter out = new FileWriter(file); //文件写入流
//将数组中的数据写入到文件中。每行各数据之间用TAB间隔
for(int i=0;i<sparseArray.length;i++){
for(int j=0;j<3;j++){
out.write(sparseArray[i][j]+"\t");
}
out.write("\r\n");
}
out.close();
} catch (Exception e) {
e.printStackTrace();
System.out.println("存入文件时出现异常："+e.getMessage().toString());
}
此时在本地的e盘下我们会发现多了一个array.txt文件，打开这个文件，发现存储正确。
在这里插入图片描述
哈哈，到此模拟 棋局的保存 功能就完成了。
3.4 从本地txt文件中读取数据，并转化为对应的稀疏数组。
/**
* 从txt文件中读取数据
*/
File txtFile = new File("e:\\array.txt");
int[][] txtSparseArr = new int[3][3];
try {
String line;//存放每行的数据
int row = 0;//记录行数
if (txtFile.exists()) {
BufferedReader in = new BufferedReader(new FileReader(txtFile));
while ((line = in.readLine()) != null) {
String[] temp = line.split("\t");
for (int j = 0; j < temp.length; j++) {
txtSparseArr[row][j] = Integer.parseInt(temp[j]);
}
row++;
}
} else {
System.out.println("没有找到文件");
}
} catch (Exception e) {
e.printStackTrace();
}
/**
* 验证一下
*/
System.out.println();
System.out.println("txt中得到的稀疏数组：");
for (int[] lineData : txtSparseArr) {
for (int ele : lineData) {
System.out.printf("%d\t", ele);
}
System.out.println();
}
打印结果如下：
在这里插入图片描述
3.5 将稀疏数组恢复为原始数组
具体思路：
a. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 int[][] gobangArray2 = new int[11][11]。
b. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可。
/**
* 根据稀疏数组恢复棋局
* 遍历稀疏数组的每行，给新棋局进行赋值
*/
int row1 = txtSparseArr[0][0];
int column1 = txtSparseArr[0][1];
int[][] gobangArray2 = new int[row1][column1];
for (int i = 1; i < txtSparseArr.length; i++) {//需从第二行开始
int row2 = txtSparseArr[i][0];
int column2 = txtSparseArr[i][1];
int value = txtSparseArr[i][2];
gobangArray2[row2][column2] = value;
}
System.out.println();
System.out.println("复局后的新棋盘");
for (int[] row : gobangArray2) {
for (int element : row) {
System.out.printf("%d\t", element);
}
System.out.println();
}
打印结果如下：
在这里插入图片描述
这样 “恢复棋局” 功能也实现了。
思考：如果不知道txt中二维数组的行、列数呢？该如何处理？
我的想法是把txt中的每行数据都装进一个ArrayList中，这样ArrayList.size就是行数，每个行的内容进行拆分后形成的数组的长度就是列数。这样就可以创建稀疏数组了，然后遍历，把数据放入稀疏数组中。这样也可以把txt文件转换为二维数组了。
这个只是自己笨拙的思考，如果大佬有好的方法，希望可以告诉我一下哈。
File file5 = new File("e:\\array.txt");
ArrayList<String> txtData = new ArrayList<>();
try {
String line;
if (file5.exists()) {
BufferedReader in = new BufferedReader(new FileReader(file5));
while ((line = in.readLine()) != null) {
txtData.add(line);
}
} else {
System.out.println("没有找到文件");
}
} catch (Exception e) {
e.printStackTrace();
}
if (txtData != null && txtData.size() > 0) {
String[] firstLine = txtData.get(0).split("\t");
int rows = txtData.size();//得到行数
int columns = firstLine.length;//得到列数
int[][] sparseArray3 = new int[rows][columns];
for (int i = 0; i < txtData.size(); i++) {
String[] oneLine = txtData.get(i).split("\t");
//如果数组 sparseArray3 和 onLine 中的元素类型相同，则只要写此行就可以了
// sparseArray3[i] = oneLine;
for (int j = 0; j < oneLine.length; j++) {
sparseArray3[i][j] = Integer.parseInt(oneLine[j]);
}
}
System.out.println();
System.out.println("新方式得到的稀疏数组222：");
for (int[] lineData : sparseArray3) {
for (int ele : lineData) {
System.out.printf("%d\t", ele);
}
System.out.println();
}
}
打印结果如下：
在这里插入图片描述
