数组是一种线性的数据结构 优点：定点查询--速度快 尾部添加容易 缺点：长度固定，操作不便 注：集合的基类见第一篇：图解数据结构之开篇+集合基类
一个数组.png
一、java数组的使用
/**
* 作者：张风捷特烈
* 时间：2018/9/19 0019:8:59
* 邮箱：1981462002@qq.com
* 说明：数组测试
*/
public class ClientOfArray {
public static void main(String[] args) {
//生成数组--方式1
int[] id = new int[5];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
//生成数组--方式2
String[] name = new String[]{"张", "风", "捷", "特", "烈"};
for (int i = 0; i < name.length; i++) {
System.out.print(name[i]);//张风捷特烈
}
//增强for循环
for (String str : name) {
System.out.print(str);//张风捷特烈
}
}
}
二、自定义数组：ArrayGroup
1.成员及构造
/**
* 成员数组
*/
private T[] datas;
/**
* 无参构造--默认容量10
*/
public ArrayGroup() {
this(10);
}
/**
* 一参构造
* @param capacity 集合容量
*/
public ArrayGroup(int capacity) {
//实例化数组
datas = (T[]) new Object[capacity];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("ArrayGroup:size =%d,capacity=%d\n",size,datas.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(datas[i].toString());
if (i != size - 1) {
sb.append(", ");
}
}
sb.append("]");
2.定点添加元素：
思路：定点后的所有元素后移一位，空出顶点位，让待添加元素入驻
数组定点添加.png
添加方法实现：
@Override
public void add(int index, T el) {
if (size == datas.length) {
throw new IllegalArgumentException("Add failed! Array is full");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed! Make sure index < 0 || index > size");
}
//从最后一个元素开始,到定点位置元素,后移一位
for (int i = size-1; i >=index ; i--) {
datas[i + 1] = datas[i];
}
datas[index] = el;
size++;
}
添加方法测试：
ArrayGroup<String> arrayGroup = new ArrayGroup<>();
arrayGroup.addLast("风");
arrayGroup.addLast("特");
arrayGroup.addLast("烈");
arrayGroup.add(1,"捷");
arrayGroup.addFirst("张");
System.out.println(arrayGroup);
//ArrayGroup:size =5,capacity=10
//[张, 风, 捷, 特, 烈]
3.查找
定点查找
@Override
public T get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed! Make sure index < 0 || index > size");
}
return datas[index];
}
定元素查找
@Override
public int[] getIndex(T el) {
//临时数组
int[] tempArray = new int[size];
//重复个数
int count = 0;
//遍历集合,获取该元素重复个数，及位置数组
for (int i = 0; i < size; i++) {
if (datas[i].equals(el)) {
tempArray[count] = i;
count++;
}
}
//将临时数组压缩
int[] indexArray = new int[count];
for (int i = 0; i < count; i++) {
indexArray[i] = tempArray[i];
}
return indexArray;
}
4.定点设置
@Override
public T set(int index, T el) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed! Make sure index < 0 || index > size");
}
T oldEl = get(index);
datas[index] = el;
return oldEl;
}
5.定点移除
思路：从删除元素索引的下一位开始到结尾，依次左移
数组定点移除.png
@Override
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed! Make sure index < 0 || index > size");
}
T temp = get(index);
//从删除元素索引的下一位开始到结尾，依次左移
for (int i = index + 1; i < size; i++) {
datas[i - 1] = datas[i];
}
size--;
//置空--游荡的对象
datas[size] = null;
return temp;
}
6.清空
这里要注意一点，从后往前删除。因为从头删，每次后面都要全部移位，消耗很大。 正向10W数据清空：正向clear:方法耗时:10.549秒 逆向100W数据清空：耗时0，可见天壤之别。所以一个好的算法作用是很大的
@Override
public void clear() {
for (int i = size-1; i <= 0; i--) {
remove(i);
}
size = 0;
}
7.定点插入集合
@Override
public Group<T> contact(int index, Group<T> group) {
//从index处遍历本数组，将待插入数据一个一个插入
for (int i = index; i < index+group.size(); i++) {
add(i+1, group.get(i-index));
}
return this;
}
三、测试
private static void otherTest(ArrayGroup<String> arrayGroup) {
arrayGroup.addLast("a");
arrayGroup.addLast("a");
arrayGroup.addLast("b");
arrayGroup.addLast("c");
arrayGroup.addLast("f");
arrayGroup.addLast("a");
arrayGroup.addLast("e");
arrayGroup.addLast("d");
System.out.println(arrayGroup);
//ArrayGroup:size =8,capacity=10
//[a, a, b, c, f, a, e, d]
//定点删除操作
String remove = arrayGroup.remove(3);
System.out.println(remove);//c
System.out.println(arrayGroup);
//ArrayGroup:size =7,capacity=10
//[a, a, b, f, a, e, d]
//定元素删除
int a = arrayGroup.removeEl("a");
System.out.println(a);//0
System.out.println(arrayGroup);
//ArrayGroup:size =6,capacity=10
//[a, b, f, a, e, d]
//定元素全删除
boolean ok = arrayGroup.removeEls("a");
System.out.println(ok);//true
System.out.println(arrayGroup);
//ArrayGroup:size =4,capacity=10
//[b, f, e, d]
//定点修改
String toly = arrayGroup.set(3, "toly");
System.out.println(toly);//d
System.out.println(arrayGroup);
//ArrayGroup:size =4,capacity=10
//[b, f, e, toly]
//是否存在元素
boolean contains = arrayGroup.contains("b");
System.out.println(contains);//true
//定点插入集合
ArrayGroup<String> arrayGroup2 = new ArrayGroup<>();
arrayGroup2.addLast("1");
arrayGroup2.addLast("2");
arrayGroup.contact(2,arrayGroup2);
System.out.println(arrayGroup);
//ArrayGroup:size =6,capacity=10
//[b, f, e, 1, 2, toly]
//末尾插入集合
arrayGroup.contact(arrayGroup2);
System.out.println(arrayGroup);
//ArrayGroup:size =8,capacity=10
//[b, f, e, 1, 2, toly, 1, 2]
//清空
arrayGroup.clear();
System.out.println(arrayGroup);
//ArrayGroup:size =0,capacity=10
//[]
}
四、动态数组：
1、扩容方法
/**
* 扩容
*
* @param newCapacity 新容量
*/
private void grow(int newCapacity) {
T[] newData = (T[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = datas[i];
}
datas = newData;
}
2、添加满了扩容
@Override
public void add(int index, T el) {
if (size == datas.length) {
grow((int) (GROW_RATE * datas.length));
}
3、移除元素后，动态修改总容量
//缩容
if (size == datas.length /4 && datas.length/2 !=0){
grow(datas.length /2);
}
五、测试ArrayGroup：
方法\数量复杂度10001000010W100W1000W
addLastO(1)0.0004秒0.0025秒0.0141秒0.0687秒1.26014秒addFirstO(n)0.0063秒0.2706秒19.5379秒--------addO(n)----------removeLastO(1)0.0005秒0.0036秒0.0091秒0.02301秒:0.1607秒removeFirstO(n)0.0063秒0.2771秒19.7902秒--------removeElO(n)----------removeElsO(n)----------removeO(n)----------clearO(1)----------setO(1)----------getO(1)----------getIndexO(n)----------
后记、
1.声明：
[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 [4]你的喜欢与支持将是我最大的动力
2.连接传送门：
更多数据结构知识欢迎访问:图解数据结构 项目源码均在我的github/DS：欢迎star 张风捷特烈个人网站，编程笔记请访问：http://www.toly1994.com
3.联系我
QQ:1981462002 邮箱：1981462002@qq.com 微信：zdl1994328
4.欢迎关注我的微信公众号，最新精彩文章，及时送达：
公众号.jpg
转载于:https://www.cnblogs.com/toly-top/p/9781870.html
