数据结构提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
- 前言
- 一、线性结构
- 二、非线性结构
- 三、稀疏数组
前言
JAVA----数据结构与算法的学习
一、线性结构
- 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
- 线性结构有两种不同的存储方式：顺序存储和链式存储
2.1.顺序存储的线性表称为顺序表，存储元素是连续的。
2.2.链式存储的顺序表称为链表，链表的存储元素不一定是连续的，元素节点存放数据元素以及相邻元素的地址信息 - 线性结构常见有：数组，队列，链表和栈；
二维数组，多维数组，广义表，树结构，图结构
三、稀疏数组- 什么是稀疏数组？
当一个数组当中大部分元素都为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
如果二维数组中有很多默认值为0，可以将原始的二维数组压缩成稀疏数组。
2.稀疏数组的处理方法（JAVA）
- 记录数组有多少行多少列，有多少个不同的值.
- 把n个不同值的数据元素的行列以及值记录到一个小规模的数组当中，压缩成稀疏数组.
假设一个4*5的二维数组:
|0|0|0|0|5|----------------------------------->行 列 值
|0|1|0|0|0| ------>转化为稀疏数组----->|4 | 5 | 4 |
|0|0|2|0|0| ---------------------------------->|0 | 4 | 5 |
|0|7|0|0|0| ---------------------------------->|1 | 1 | 1 |
————————————————>|2 | 2 | 2 |
————————————————>|3 | 1 | 7 |
- 如上所示一个4行5列（20个）的二维数组压缩成一个小规模的5行3列（15）的稀疏数组
- 稀疏数组中的第一行：存放的是原始数组当中一共多少行、多少列、多少个值
- 数组第一行从0开始
--------利用JAVA代码实现---------
假设一个五子棋盘的实现
代码实现如下:
第一步创建一个二维数组:
//创建一个原始的11*11的二维数组:
int chessArr1[][] = new int[11][11];
//假设 0为没有子，1为黑子，2为白子
chessArr1[1][2] = 1;//黑子;
chessArr1[2][3] = 2; //白子;
//外层循环遍历行
System.out.println("原始的11*11的二维数组");
for (int[] row : chessArr1){
for (int data: row){
System.out.printf("%dt",data);
}
System.out.println();
}
第二:将原始的二维数组转化为稀疏数组
//将原始的二维数组转换为稀疏数组
int count=0;//记录多少个值
int row1=0;//记录一共多少行
int col=0;//记录一共多少列
for (int[] row:chessArr1){
col=0;
row1++;
for (int data:row){
if (data!=0){
count++;
}
col++;
}
}
int sparseArr[][] = new int[count+1][3];//创建稀疏数组
sparseArr[0][0] = row1;//行
sparseArr[0][1] = col;//列
sparseArr[0][2] = count;//非0个数，即值的个数
第三、将存在的非0值存放到稀疏数组sparseArr
//遍历二维数组将非0的数据存入
for (int i =0;i
for (int j = 0;j
if (chessArr1[i][j]!=0){
sparseArr[x][0]=i;
sparseArr[x][1]=j;
sparseArr[x][2]=chessArr1[i][j];
x++;
}
}
}
System.out.println("**********稀疏数组遍历******");
for (int[] row : sparseArr){
for (int data: row){
System.out.printf("%dt",data);
}
System.out.println();
}
第四、将稀疏数组转化为原始二维数组：
//将稀疏数组转化为原始二位数组:
//读取稀疏数组的第一行，创建原始数组的行列
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
for(int i =1;i
chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
System.out.println("******稀疏数组转换为原始二位数组*****");
for (int row[]:chessArr2){
for (int data:row){
System.out.printf("%dt",data);
}
System.out.println();
}
运行结果：
