专栏首页wangweijun图解Java数据结构之稀疏数组

图解Java数据结构之稀疏数组

在编程中,算法的重要性不言而喻,没有算法的程序是没有灵魂的。可见算法的重要性。 然而,在学习算法之前我们需要掌握数据结构,数据结构是算法的基础。 我在大学的时候,学校里的数据结构是用C语言教的,因为对C语言也不是很了解,所以掌握得不是特别好,在网上找的一些学习资料里也基本都是用C语言来进行数据结构的教学。 那么,从本篇文章开始,我将用Java语言来介绍数据结构,当然,数据结构过后就是算法。

线性结构和非线性结构
  1. 线性结构 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系; 线性结构有两种不同的存储结构,即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表,顺序表中存储的元素是连续的; 链式存储的线性表称为链表,链表中存储的元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息; 线性结构常见的有:数组、队列、链表和栈
  2. 非线性结构 非线性结构包括:二维数组、多维数组、广义表、树结构、图结构
稀疏数组

对数据结构有了一个初步的认识之后,我们开始对一些具体的数据结构进行详细的分析。 我们来看一个实际的需求: 这是一个五子棋的程序,有存盘退出和续上盘的功能,如下图,如何将下图的棋局进行保存呢?

那这个问题很简单,很多人可能会想到用二维数组来进行存储。

如上图,我们用0表示无子,1表示黑子,2表示蓝子,但是这个程序问题很大,因为该二维数组的很多值都是默认值0,因此记录了很多没有意义的数据,那么这个时候我们就可以使用稀疏数组来对该二维数组进行一个压缩。 那么稀疏数组到底是什么呢? 当一个数组中大部分元素是0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。 稀疏数组的处理方法是:

  1. 记录数组一共有几行几列,有多少个不同的值
  2. 把具有不同值的元素的行列以及值记录在一个小规模的数组中,从而缩小程序的规模

那么了解了稀疏数组的概念后,我们通过稀疏数组来改进一下五子棋程序。

经过稀疏数组的压缩之后,原数组从原来的11行11列变为了三行三列。 该稀疏数组的第一行记录的是原数组的行数和列数以及元素个数。 接下来的每一行记录的是有效元素的位置和值,例如第二行记录的是原数组中位于1,2位置上的元素1;第三行记录的是原数组中位于2,3位置上的元素2。 综上所述,二维数组转稀疏数组的思路:

  1. 遍历原始的二维数组,得到要保存的有效元素个数
  2. 根据有效元素个数创建稀疏数组sparseArr
  3. 将二维数组的有效数据存入稀疏数组即可

稀疏数组转原始二维数组的思路:

  1. 先读取稀疏数组的第一行,根据第一行的数据创建原始二维数组
  2. 读取稀疏数组后几行的数据,并赋给原始的二维数组即可

关于实现思路已经分析完毕,接下来用代码实现。 将二维数组转稀疏数组用代码实现如下:

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();
		}
	}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python学习手册--第四部分(用户输入和while循环)

    现在的应用程序非常讲究和用户的交互体验,用户是上帝的真理在哪个行业都适用,只有用户认可你的东西,才能证明它的优秀。 现在假设有人要判断自己是否到了投票的年龄,...

    wangweijun
  • 程序员那些必须掌握的排序算法(上)

    现在的IT行业并不像以前那么好混了,从业人员过多,导致初级程序员过剩,这也间接导致了公司的招聘门槛越来越高,要求程序员掌握的知识也越来越多。 算法也是一个争论...

    wangweijun
  • 数据库操作中需要注意的问题

    如果你用cmd窗口向一张表插入数据的时候,插入的数据是中文,会出现错误提示,用软件操作的请忽略。。。 出现错误的原因是cmd窗口采用的是gbk编码,所以你在c...

    wangweijun
  • Java--数组

    SuperHeroes
  • 13 个 JS 数组精简技巧,一起来看看。

    数组是 JS 最常见的一种数据结构,咱们在开发中也经常用到,在这篇文章中,提供一些小技巧,帮助咱们提高开发效率。

    前端小智@大迁世界
  • 数组是如何随机访问元素?数组下标为什么从0开始,而不是1?

    数组(Array)是一种线性表数据结构,它用一组连续的内存空间,来存储相同类型的数据。

    搜云库技术团队
  • 一些 JS 数组精简技巧,要记好笔记了

    数组是 JS 最常见的一种数据结构,咱们在开发中也经常用到,在这篇文章中,提供一些小技巧,帮助咱们提高开发效率。

    前端小智@大迁世界
  • Java数组

    数组对于每一门编程语言来说都是重要的数据结构之一,当然不同语言对数组的实现及处理也不尽相同。

    用户5224393
  • 企业面试题:js编写数组去重方法

    【友情提示:舒克老湿意在为各位准备从事前端工程师岗位的小伙伴提供思路,所有代码仅供参考,切勿背题!!理解问题以及提高自己解决问题的能力最为重要!如果你有更好的解...

    舒克
  • 图解算法系列(三):数组

    "数组"结构其实就是一排紧密相邻的可数内存,并提供了一个能够直接访问单一的数据内容的计算方法.我们其实可以想象一下自家的信箱,每一个信箱都有住址,其中路名就是名...

    公众号---志学Python

扫码关注云+社区

领取腾讯云代金券