admin | 女足世界杯预测
java手撸数据结构–数组(无序、有序、稀疏)
数组是java语言内置的数据类型，他是一个线性的序列，所以可以快速访问其他的元素，数组和其他语言不同，当你创建了一个数组时，他的容量是不变的，而且生命周期也是不能改变的，还有JAVA数组会做边界检查，如果发现有越界现象，会报RuntimeException异常错误，当然检查边界会以效率为代价。
数组的局限性分析
插入快:对于无序数组，即元素没有按照一定顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但有序数组却不一定了，它需要在指定的位置插入。查找慢:当然通过下标查找是很快的。但是通常我们都是根据元素值来查找的，给定一个元素值，对于无序数组，我们需要从数组的第一个元素还是遍历，直到找到那个元素。有序数组通过特定算法查找的速度会比无需数组快。删除慢：根据元素值删除，我们要先找到该元素所在位置，然后将元素后端的值整体向前移动一个位置。也需要比较多的时间。数组一旦创建，大小固定:如果初始化一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面的数据个数增加了又添加不进去了。
很显然，数组虽然插入快，但是查找和删除比较慢，而且扩展性差，所以我们一般不会用数组来存储数据。
无序数组
无序数组，顾名思义，就是没有顺序的数组，即元素没有按照一定顺序排列，只是按照插入的顺序排列。
创建一个类来实现无序数组
class MyArray{
//存储具体数据的数组
int[] array;
//当前数组存放数据数量
int size;
//构造函数，初始化无序数组
public MyArray(int maxPage) {
array = new int[maxPage];
size = 0;
}
}
1. 插入
/**
* 插入
*/
public void insert(int value) {
if (size < array.length) {
//数组未满，则插入
array[size++] = value;
}
}
2. 查找
/**
* 查找返回下标
*/
public int find(int value) {
int i;
for (i = 0; i < array.length; i++) {
if (array[i] == value) {
break;
}
}
if (i == size) {
System.out.println("数组中不存在当前数据");
return -1;
} else {
return i;
}
}
3. 删除
/**
* 删除
*/
public void delete(int value) {
int j;
if((j=this.find(value))>-1){
for (int i = j; i < size-1; i++) {
array[i]=array[i+1];
}
//删除完把记录-1
size--;
}
}
4. 遍历
/**
* 遍历
*/
public void forEach(){
for (int i = 0; i < size; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
5.测试
public static void main(String[] args) {
MyArray myArray = new MyArray(10);
myArray.insert(12);
myArray.insert(5);
myArray.insert(1);
myArray.forEach();
myArray.delete(5);
myArray.forEach();
}
值：
12 5 1
12 1
有序数组
有序数组优缺点分析
优点：
采用二分查找效率高，比无序数组效率高。缺点：
插入的时候，要移动元素，比无序数组效率低。
创建一个类来实现有序数组
/**
* 有序数组
*/
class MySequenceArray {
//存储有序数组的集合
private int[] array;
//元素数量
private int size;
public MySequenceArray(int size) {
array = new int[size];
size = 0;
}
｝
查找
/**
* 查找返回下标(二分查找)
*/
public int find(int value) {
if (size == 0) {
return -1;
}
int index;
//当前比对的最大下标
int maxIndex = size - 1;
// 当前比对的最小下标
int minIndex = 0;
//当前下标
int currentIndex;
while (true) {
if (minIndex > maxIndex) {
return -1;
}
currentIndex = (maxIndex + maxIndex) / 2;
if (value == array[currentIndex]) {
return currentIndex;
} else if (value > array[currentIndex]) {
minIndex = currentIndex + 1;
} else {
maxIndex = currentIndex - 1;
}
}
}
插入
/**
* 插入
*/
public void insert(int value) {
if (array.length > size) {
int index;
for (index = 0; index < size; index++) {
if (value < array[index]) {
//找到了
break;
}
}
if (index < size) {
//数组中存在比value大的数，则index以后的数向后移动一位
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
//将value插入index处
array[index] = value;
} else {
//最后找不到比value大的数
array[index] = value;
}
size++;
}
}
删除
/**
* 删除
*/
public void delete(int value) {
int index;
if ((index = find(value)) > -1) {
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
size--;
}
}
遍历
/**
* 遍历
*/
public void forEach() {
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
测试
public static void main(String[] args) {
MySequenceArray mySequenceArray = new MySequenceArray(10);
mySequenceArray.insert(10);
mySequenceArray.insert(1);
mySequenceArray.insert(55);
mySequenceArray.insert(3);
mySequenceArray.forEach();
mySequenceArray.delete(3);
mySequenceArray.delete(2);
mySequenceArray.forEach();
}
1 3 10 55
1 10 55
稀疏数组
所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。
因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。
稀疏数组实现方式
如下：
方式一：二维数组存储，用空间换取时间，占用空间大，查询效率高
int[][] array = new int[7][9]; //占用63
array[1][1] = 3;
array[3][0] = 1;
array[3][1] = 4;
array[4][2] = 7;
array[5][5] = 5;
遍历
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
遍历值如下：
0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 4 0 0 0 0 0 0 0
0 0 7 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0 0
方式二：使用压缩方式，执行效率较低，占用空间小
创建一个类来实现稀疏数组
/**
* 稀疏数组实现
*/
class MySparseArray{
//稀疏数组的行数
private int row;
//稀疏数组的列数
private int col;
//稀疏数组当前行当前列的值
private int val;
//通过构造函数实例化
public MySparseArray(int row, int col, int val) {
this.row = row;
this.col = col;
this.val = val;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getVal() {
return val;
}
}
稀疏数组的使用
//定义五个节点的稀疏数组，这里的6不包含第一行记录
MySparseArray[] mySparseArrays = new MySparseArray[6];
//第一行为记录行数、列数、节点数，下标为0
//7行、9列
mySparseArrays[0] = new MySparseArray(7, 9, 6);
mySparseArrays[1] = new MySparseArray(1, 1, 3);
mySparseArrays[2] = new MySparseArray(3, 0, 1);
mySparseArrays[3] = new MySparseArray(3, 1, 4);
mySparseArrays[4] = new MySparseArray(4, 2, 7);
mySparseArrays[5] = new MySparseArray(5, 5, 5);
// 遍历
for (int i = 0; i < mySparseArrays[0].getRow(); i++) {
for (int j = 0; j < mySparseArrays[0].getCol(); j++) {
int k;//这个字段用来记录有值的下标
//第一行记录为0，要跳过第一行
for (k = 1; k < mySparseArrays.length; k++) {
if (mySparseArrays[k].getRow() == i && mySparseArrays[k].getCol() == j) {
break;
}
}
if (k < mySparseArrays.length) {
System.out.print(mySparseArrays[k].getVal() + " ");
} else {
System.out.print(0 + " ");
}
}
//换行
System.out.println();
}
值为：
0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 4 0 0 0 0 0 0 0
0 0 7 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0 0