看得见的数据结构Android版之表的数组实现(数据结构篇)

零、前言:

一讲到装东西的容器,你可能习惯于使用ArrayList和数组,你有想过ArrayList和数组的区别吗? Java的类起名字都不是随便乱起的,一般前面是辅助,后面是实质:ArrayList = Array + List Array就是数组,List便是表结构,ArrayList即数组实现的表结构,问题来了,什么是表结构 注:不要问我效果图用什么软件画的...因为本来就没用什么软件画。下一节带你一起自己画!!! 希望你可以和我在Github一同见证:DS4Android的诞生与成长,欢迎star

0.不管别的,先留图镇楼:

表结构的常规操作

表结构的常规操作.gif

数组的扩容与缩容

数组的扩容与缩容


1.在我们生活中都有什么表?
课程表,成绩表,作息时间表、列车行程表、手表(这个算了吧...)
2.表有什么用?

成绩表.jpg

可以把同类的对象统一管理,比如成绩表:
高三12班的54为同学的成绩是对象,对象又包括数学、语文、英语...等属性  
把混乱的54个对象放在一起,这么一排,哪个是学霸,哪个是学渣一目了然,非常方便  
如果其中某个对象的成绩改错了,可以get到对象重新set一下,也非常方便  
如果中间一个人作弊了,分数取消,直接remove掉,后面的人名词往前排,也非常方便  
如果高三12班和高三11班要比较成绩,两张表contact一下,就成一张表,合并也很方便
3.表和数组有什么不同?

打个最恰当的比方就是:数组相当于打印出来的纸质版表结构像是Excel中可操作版

1.数组定长:添加新元素,定位添加都很困难
2.拿删除来说:数组remove掉了,后面的人名次都不变----(我还没个空白名次高,你说气人不气人...)
3.表是一种抽象数据类型(Abstract Data Type),既然是抽象就是规范或功能,表会有不同的实现形式 

[番外]:小和尚问老和尚:"什么是圣人?"    老和尚说:"好好学习,天天向上,乐于助人,诚信友善"
这里"圣人"便是一种抽象,"好好学习,天天向上,乐于助人,诚信友善"便是"圣人"的"条件(功能)",
小和尚按照这么做了,他就是老和尚眼中的"圣人",即小和尚实现了圣人。

4.同样,表是一种抽象,也可以定义你眼中的表,并为它附上add(),get(),set(),remove()等功能  
5.其实Java的ArrayList实现了List这个抽象接口
4.数组表结构:本文要务

数组表结构.png


一、定义自己的表结构

由于Java用List,为了不混淆,取了个新名字叫Chart

1.定义表的接口

也就是说说你的表能干嘛用(接口方法最好注释非常清晰)

/**
 * 作者:张风捷特烈
 * 时间:2018/9/25 0025:8:25
 * 邮箱:1981462002@qq.com
 * 说明:线性表结构接口
 */
public interface IChart<T> {
//region -------------添加操作------------

    /**
     * 定点添加
     *
     * @param index 索引
     * @param el    数据元素
     */
    void add(int index, T el);

    /**
     * 添加尾
     *
     * @param el 数据元素
     */
    void add(T el);

//endregion

//region -------------删除操作------------

    /**
     * 定位删除
     *
     * @param index 索引
     * @return 删除的元素
     */
    T remove(int index);

    /**
     * 删除尾位
     *
     * @return 删除的元素
     */
    T remove();

    /**
     * 删除指定元素的第一次出现时
     *
     * @param el 数据元素
     * @return 元素位置
     */
    int removeEl(T el);

    /**
     * 删除所有指定元素
     *
     * @param el 数据元素
     */
    boolean removeEls(T el);

    /**
     * 清空集合
     */
    void clear();

//endregion

//region -------------改查操作------------

    /**
     * 设置某位置的元素新值
     *
     * @param index 索引
     * @param el    新值
     * @return 旧值
     */
    T set(int index, T el);

    /**
     * 根据指定位置获取元素
     *
     * @param index 索引
     * @return 数据元素
     */
    T get(int index);

    /**
     * 根据指定元素获取匹配索引
     *
     * @param el 数据元素
     * @return 索引集
     */
    int[] getIndex(T el);
//endregion

//region ------------其他操作-------------

    /**
     * 集合是否包含某元素
     *
     * @param el 数据元素
     * @return 是否包含
     */
    public boolean contains(T el);

    /**
     * 连接两个集合
     *
     * @param iChart 插入集合
     * @return 合并后的集合
     */
    public IChart<T> contact(IChart<T> iChart);

    /**
     * 定点连接两个集合
     *
     * @param index  索引
     * @param iChart 插入集合
     * @return 合并后的集合
     */
    IChart<T> contact(int index, IChart<T> iChart);

    /**
     * 是否为空
     *
     * @return 是否为空
     */
    boolean isEmpty();

    /**
     * 返回集合大小
     *
     * @return 大小
     */
    int size();
    
    /**
     * 获取数组容量
     * @return 数组容量
     */
    int capacity();

//endregion
}
2.使用数组实现表结构:ArrayChart

实现接口,并实现接口里的所有方法

/**
 * 作者:张风捷特烈<br/>
 * 时间:2018/11/21 0021:8:18<br/>
 * 邮箱:1981462002@qq.com<br/>
 * 说明:数组实现线性表结构
 */
public class ArrayChart<T> implements IChart<T> {
 //空实现---略
}
3.成员变量和构造初始化
private int size;//表中数据的个数
private T[] data;//数据核心承载体
private static final int DEFAULT_CAPACITY = 10;//默认数组容量
private static final float GROW_RATE = 1.5f;//扩容增长率

public ArrayChart() {
    this(DEFAULT_CAPACITY);//无参构造默认创建10个容量的数组
}
public ArrayChart(int capacity) {
    data = (T[]) new Object[capacity];//新创建[数组表]时初始化数组
}
4.简单接口的实现:
@Override
public boolean isEmpty() {
    return size == 0;
}

@Override
public int size() {
    return size;
}

@Override
public int capacity() {
    return data.length;
}

二、主要方法的实现(CRUD)

1.定点添加元素:

看一下操作图(将在下一篇:视图篇完成):默认添加到尾部 思路:定点后的所有元素后移一位,空出顶点位,让待添加元素入驻 紫色框代表空的数组位,中间填充的是表中的实际元素 可见定点添加是在选中索引的前一位添加,所以添加到尾部是add(size,data)来添加

尾添加和定点添加.gif

@Override
public void add(T el) {
    add(size , el);//这里size---是因为在size之前一位添加
}

@Override
public void add(int index, T el) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Add failed! Make sure index < 0 || index > size");
    }
    //从最后一个元素开始,到定点位置元素,元素都后移一位
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = el;
    size++;
}

addByIndex.png


2.查找与设置值:get(),set():

set和定索引查询.gif

 @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);
     data[index] = el;//设置一下,很简单
     return oldEl;
 }

 @Override
 public T get(int index) {
     if (index < 0 || index >= size) {
         throw new IllegalArgumentException("Get failed! Make sure index < 0 || index > size");
     }
     return data[index];//查询数组的对应索引处
 }

定值查询获取索引

定值查询获取索引.gif

@Override
public int[] getIndex(T el) {
    int[] tempArray = new int[size];//临时数组
    int count = 0;//重复个数
    for (int i = 0; i < size; i++) {//遍历集合,获取该元素重复个数,及位置数组
        if (data[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;//返回查找元素的索引数组(相当于成绩表看数学80分的都有哪些人)
}

3.删除元素:

删除和定点删除.gif

@Override
public T remove() {
    return remove(size - 1);
}

@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);
    //从删除元素索引的下一位开始到结尾,依次左移
    // 可简写: System.arraycopy(data, index + 1, data, index + 1 - 1, size - index + 1);
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }
    size--;
    //置空--游荡的对象
    data[size] = null;
    return temp;
}

其他删除: 定元素删除单个和定元素删除所有相当于前面的组合操作,就不做操作演示了

@Override
public int removeEl(T el) {
    int[] indexes = getIndex(el);//查找元素的索引集合,删除首个
    int index = -1;
    if (indexes.length > 0) {
        index = indexes[0];
        remove(indexes[0]);
    }
    return index;
}
@Override
public boolean removeEls(T el) { //查找元素的索引集合,删除所有
    int[] indexArray = getIndex(el);
    if (indexArray.length != 0) {
        for (int i = 0; i < indexArray.length; i++) {
            remove(indexArray[i] - i); // 注意-i
        }
        return true;
    }
    return false;
}

三、动态扩容与缩容的实现

也没有什么高大上的,就是一个篮子装不下了,装个更大的篮子装而已

数组的扩容与缩容

1.扩容与缩容方法的实现
/**
 * 扩容/缩容
 *
 * @param newCapacity 新容量
 */
private void grow(int newCapacity) {
    T[] newData = (T[]) new Object[newCapacity];//创建个大篮子
    for (int i = 0; i < size; i++) {//把原来的元素放到大篮子里
        newData[i] = data[i];
    }
    data = newData;
}
2.扩容和缩容的调用契机

什么时候扩容----篮子不够装了呗---add 什么时候需要缩容----1000个容量的篮子装1个鸡蛋想想也浪费---remove

1) add检测扩容时机:满了
@Override
public void add(int index, T el) {
    if (size == data.length) {//篮子装不下了---
        grow((int) (GROW_RATE * data.length));//换个1.5倍的篮子
    }
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Add failed! Make sure index < 0 || index > size");
    }
    //从最后一个元素开始,到定点位置元素,元素都后移一位
    //可简写:System.arraycopy(data, index, data, index + 1, size - index);
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = el;
    size++;
}
2)remove检测缩容时机

这里的判断标志是留多点备用,不然有可能插入移除频繁而导致重复扩容或缩容, 篮子可能会说:"你到底缩还是放,你是不是在玩老子....,老子给你多留点空行了吧!"

@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);
    //从删除元素索引的下一位开始到结尾,依次左移
    // 可简写: System.arraycopy(data, index + 1, data, index + 1 - 1, size - index + 1);
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }
    size--;
    //置空--游荡的对象
    data[size] = null;
    //缩容----此处限定是为了避免反复出现扩容缩容---可自定义
    if (size == data.length / 4 && data.length / 2 != 0 && data.length > 5) {
        grow(data.length / 2);
    }
    return temp;
}
3.清空时,数组缩放到初始值
@Override
public void clear() {
    size = 0;
    grow(DEFAULT_CAPACITY);
}

四、其他操作

1.是否包含某元素
 @Override
 public boolean contains(T el) {
     return getIndex(el).length != 0;//按值查询有数据
 }

2.contact连接数组

表的联合.png

@Override
public IChart<T> contact(IChart<T> iChart) {
    return contact(size - 1, iChart);
}


@Override
public IChart<T> contact(int index, IChart<T> iChart) {
    if (!(iChart instanceof ArrayChart)) {//必须是数组才能联合
        return null;
    }
    //从index处遍历本数组,将待插入数据一个一个插入
    for (int i = index; i < index + iChart.size(); i++) {
        add(i + 1, iChart.get(i - index));
    }
    return this;
}

作为一个表结构,基本上就演示这么多,还有其他操作可以自定义接口,自己实现, 不过不管多么复杂的操作都是以上操作的组合而已。


五、小结:

关于复杂度的分析,等到所有表结构讲完再整体比较一下,这里先粗略感觉一下

耗时测试

方法\操作次数

1000

10000

10W

100W

1000W

add首

0.0063秒

0.2706秒

19.5379秒

----

----

add尾

0.0004秒

0.0025秒

0.0141秒

0.0687秒

1.26014秒

remove首

0.0063秒

0.2771秒

19.7902秒

----

----

remove尾

0.0005秒

0.0036秒

0.0091秒

0.02301秒

:0.1607秒

可以看出往开始添加/删除会很困难,从代码中可以感觉到,毕竟要让后面所有人挪一挪 想一下如果30000人排一起,第一个人走了,后面所有人往前挪一下,是不是工程量挺大的 要是你决定插到第一个,让后面的人都往后移一下.....(大哥,活着难道不好吗....) 所以频繁对第一个元素进行操作的,还是不要作死,数组表结构(ArrayList)不适合你

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Go语言中反射的正确使用

介绍 反射是元数据编程的一种形式,指的是程序获得本身结构的一种能力。不同语言的反射模型实现不一样,本文中的反射,仅仅指的是Go语言中的反射模型。 反射有两个问题...

377160
来自专栏xingoo, 一个梦想做发明家的程序员

Elasticsearch——Date Math在索引中的用法详解

在elasticsearch中,有时会想要通过索引日期来筛选查询的数据,此时就需要用到日期数学表达式。 更多内容参考Elasticsearch翻译汇总 ...

25370
来自专栏喵了个咪的博客空间

zephir-(6)运算符

#zephir-运算符# ? ##前言## 先在这里感谢各位zephir开源技术提供者 了解的动态变量和静态变量之后我们今天来了解一下在编码工作中至关重要的运算...

37490
来自专栏技术/开源

30分钟?不需要,轻松读懂IL

先说说学IL有什么用,有人可能觉得这玩意平常写代码又用不上,学了有个卵用。到底有没有卵用呢,暂且也不说什么学了可以看看一些语法糖的实现,或对.net理解更深一点...

20970
来自专栏MyBlog

Effective.Java 读书笔记(5)复用对象

通常来说我们每次重复使用一个对象是比重新创建一个功能上相等的对象更为合适的,复用可以更快并且更加优雅,当一个对象是不变的(Immutable)时候可以被经常重用

11820
来自专栏Play & Scala 技术分享

挑逗 Java 程序员的那些 Scala 绝技

有个问题一直困扰着 Scala 社区,为什么一些 Java 开发者将 Scala 捧到了天上,认为它是来自上帝之吻的完美语言;而另外一些 Java 开发者却对它...

19560
来自专栏Golang语言社区

Go语言中反射的正确使用

介绍 反射是元数据编程的一种形式,指的是程序获得本身结构的一种能力。不同语言的反射模型实现不一样,本文中的反射,仅仅指的是Go语言中的反射模型。 反射有两个问题...

37080
来自专栏Java爬坑系列

【Java入门提高篇】Day1 抽象类

  基础部分内容差不多讲解完了,今天开始进入Java提高篇部分,这部分内容会比之前的内容复杂很多,希望大家做好心理准备,看不懂的部分可以多看两遍,仍不理解的部分...

23960
来自专栏码洞

《快学 Go 语言》第 3 课 —— 分支与循环

上面这个等式每一个初学编程的同学都从老师那里听说过。它并不是什么严格的数据公式,它只是对一般程序的简单认知。数据结构是内存数据关系的静态表示,算法是数据结构从一...

12430
来自专栏Kotlin源码阅读

kotlin源码阅读——函数式编程

我主要写Kotlin源码阅读,函数式编程的基本概念,概念大家可以在网上做一些了解,这里推荐一下百度百科的定义,函数式编程概念,蛮清晰的。

35950

扫码关注云+社区

领取腾讯云代金券