数据结构-数组和稀疏数组
数组
数组是一种数据结构，其可以在内存中连续存储多个数据元素，在内存中的分配也是连续的。
点击查看代码
class Person{}
class Student extends Person{
public static void main(String[] args){
Person[] p = new Stunent[6];
}
}
缺点：
- 数组的大小固定后就无法扩容了（如果要扩容得新建另一个数组）。
- 数组只能存储一种类型的数据。
- 添加、删除的操作慢，因为每次添加或删除都要移动其他的元素。
稀疏数组
点击查看代码
/* 原始数组............................ */
int[][] originalArray = new int[4][4];
originalArray[0][0] = 1;
originalArray[1][1] = 2;
originalArray[2][2] = 3;
/* 稀疏数组............................ */
/* 将原始数组存为稀疏数组 */
/* 1.遍历得到原始数组中不同的值的个数*/
int sum = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray.length; j++) {
if (originalArray[i][j] != 0) {
sum++;
}
}
}
/* 2.创建稀疏数组
* 思路：要存储原始数组的行数、列数、不同值 ===> 列数为3，存储不同值 ===> 根据不同的值的个数创建列数
* */
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0] = new int[]{4,4,sum};
/* 3.将原始数组中不同的值放入稀疏数组
* 思路：1、明确要存放的东西：不同值的信息（坐标和值）
* 2、存放在稀疏数组中哪个位置：以遍历到的不同值的次序依次存放
* */
int count = 0; // 记录是第几个非0数
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray.length; j++) {
if (originalArray[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = originalArray[i][j];
}
}
}