图解Java数据结构之稀疏数组
2019-08-26 06:51:53来源：博客园 阅读 ()
图解Java数据结构之稀疏数组
在编程中，算法的重要性不言而喻，没有算法的程序是没有灵魂的。可见算法的重要性。
然而，在学习算法之前我们需要掌握数据结构，数据结构是算法的基础。
我在大学的时候，学校里的数据结构是用C语言教的，因为对C语言也不是很了解，所以掌握得不是特别好，在网上找的一些学习资料里也基本都是用C语言来进行数据结构的教学。
那么，从本篇文章开始，我将用Java语言来介绍数据结构，当然，数据结构过后就是算法。
线性结构和非线性结构
- 线性结构
线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系；
线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中存储的元素是连续的；
链式存储的线性表称为链表，链表中存储的元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息；
线性结构常见的有：数组、队列、链表和栈 - 非线性结构
非线性结构包括：二维数组、多维数组、广义表、树结构、图结构
稀疏数组
对数据结构有了一个初步的认识之后，我们开始对一些具体的数据结构进行详细的分析。
我们来看一个实际的需求：
这是一个五子棋的程序，有存盘退出和续上盘的功能，如下图，如何将下图的棋局进行保存呢？
那这个问题很简单，很多人可能会想到用二维数组来进行存储。
如上图，我们用0表示无子，1表示黑子，2表示蓝子，但是这个程序问题很大，因为该二维数组的很多值都是默认值0，因此记录了很多没有意义的数据，那么这个时候我们就可以使用稀疏数组来对该二维数组进行一个压缩。
那么稀疏数组到底是什么呢？
当一个数组中大部分元素是0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是：
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同值的元素的行列以及值记录在一个小规模的数组中，从而缩小程序的规模
那么了解了稀疏数组的概念后，我们通过稀疏数组来改进一下五子棋程序。
经过稀疏数组的压缩之后，原数组从原来的11行11列变为了三行三列。
该稀疏数组的第一行记录的是原数组的行数和列数以及元素个数。
接下来的每一行记录的是有效元素的位置和值，例如第二行记录的是原数组中位于1，2位置上的元素1；第三行记录的是原数组中位于2,3位置上的元素2。
综上所述，二维数组转稀疏数组的思路：
- 遍历原始的二维数组，得到要保存的有效元素个数
- 根据有效元素个数创建稀疏数组sparseArr
- 将二维数组的有效数据存入稀疏数组即可
稀疏数组转原始二维数组的思路：
- 先读取稀疏数组的第一行，根据第一行的数据创建原始二维数组
- 读取稀疏数组后几行的数据，并赋给原始的二维数组即可
关于实现思路已经分析完毕，接下来用代码实现。
将二维数组转稀疏数组用代码实现如下：
public static void main(String[] args) {
// 创建一个原始的二维数组(11行11列)
// 0:表示没有棋子
// 1:表示黑子
// 2:表示蓝子
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
System.out.println("原始的二维数组:");
for (int[] row : chessArr1) {
for (Integer value : row) {
System.out.printf("%d\t", value);
}
System.out.println();
}
// 将二维数组转稀疏数组
// 先遍历二维数组,得到非0的元素个数
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 sparseArr[][] = new int[sum + 1][3];
// 给稀疏数组赋值
// 稀疏数组第一行存的是原始数组的行数、列数和有效元素个数
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
// 遍历二维数组,将非0的值存入到稀疏数组中
int count = 0; // 用于记录是第几个非0数据
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j] != 0) {
count++;
sparseArr[count][0] = i; // 存放元素位置
sparseArr[count][1] = j; // 存放元素位置
sparseArr[count][2] = chessArr1[i][j];// 存放元素值
}
}
}
//遍历稀疏数组
System.out.println();
System.out.println("稀疏数组:");
for (int[] row : sparseArr) {
for (Integer value : row) {
System.out.printf("%d\t", value);
}
System.out.println();
}
}运行结果如下：
原始的二维数组:
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
稀疏数组:
11 11 2
1 2 1
2 3 2 这样，我们就成功地将二维数组转为了稀疏数组。
那么用代码如何将稀疏数组转为二维数组呢？
// 将稀疏数组转为二维数组
// 先读取稀疏数组的第一行，根据第一行的数据创建原始数组
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
// 读取稀疏数组后几行数据(从第二行开始读取)，并赋给原始数组
for (int i = 1; i < sparseArr.length; i++) {
// 第一列和第二列组成元素位置，第三列为元素值
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
// 遍历恢复后的二维数组
System.out.println();
System.out.println("恢复后的二维数组:");
for (int[] row : chessArr2) {
for (Integer value : row) {
System.out.printf("%d\t", value);
}
System.out.println();
}思路缕清除之后，代码非常简单，看运行效果：
原始的二维数组:
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
稀疏数组:
11 11 2
1 2 1
2 3 2
恢复后的二维数组:
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 整体代码如下：
public static void main(String[] args) {
// 创建一个原始的二维数组(11行11列)
// 0:表示没有棋子
// 1:表示黑子
// 2:表示蓝子
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
System.out.println("原始的二维数组:");
for (int[] row : chessArr1) {
for (Integer value : row) {
System.out.printf("%d\t", value);
}
System.out.println();
}
// 将二维数组转稀疏数组
// 先遍历二维数组,得到非0的元素个数
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 sparseArr[][] = new int[sum + 1][3];
// 给稀疏数组赋值
// 稀疏数组第一行存的是原始数组的行数、列数和有效元素个数
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
// 遍历二维数组,将非0的值存入到稀疏数组中
int count = 0; // 用于记录是第几个非0数据
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j] != 0) {
count++;
sparseArr[count][0] = i; // 存放元素位置
sparseArr[count][1] = j; // 存放元素位置
sparseArr[count][2] = chessArr1[i][j];// 存放元素值
}
}
}
// 遍历稀疏数组
System.out.println();
System.out.println("稀疏数组:");
for (int[] row : sparseArr) {
for (Integer value : row) {
System.out.printf("%d\t", value);
}
System.out.println();
}
// 将稀疏数组转为二维数组
// 先读取稀疏数组的第一行，根据第一行的数据创建原始数组
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
// 读取稀疏数组后几行数据(从第二行开始读取)，并赋给原始数组
for (int i = 1; i < sparseArr.length; i++) {
// 第一列和第二列组成元素位置，第三列为元素值
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
// 遍历恢复后的二维数组
System.out.println();
System.out.println("恢复后的二维数组:");
for (int[] row : chessArr2) {
for (Integer value : row) {
System.out.printf("%d\t", value);
}
System.out.println();
}
}原文链接:https://www.cnblogs.com/blizzawang/p/11411602.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：Spring框架完全掌握(下)
下一篇：Spring框架完全掌握(上)
- 国外程序员整理的Java资源大全（全部是干货） 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集（附答案） 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
