【Java 数据结构】顺序表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Java 数据结构】顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构java顺序表基本算法测试,Java数据结构,数据结构,顺序表,算法,java — 篮球哥温馨提示：编程的同时不要忘记锻炼哦！

我们不过是普通人，只不过在彼此眼中闪闪发光

1、什么是顺序表？

2、模拟实现ArrayList

2.1 模拟实现前的约定

2.2 构造方法

2.3 add方法

2.4 contains 方法

2.5 indexOf 方法

2.6 get 方法

2.7 set 方法

2.8 remove 方法

2.9 getSize 和 clear 方法

3、ArrayList 的学习

3.1 ArrayList的成员属性

3.2 ArrayList的构造方法

3.2.1 构造方法1

3.2.2 构造方法2

3.2.3 构造方法3

3.3 ArrayList 的 add 方法

3.4 ArrayList的常用方法

4、ArrayList的使用

4.1 ArrayList的遍历

4.2 扑克牌例子

4.2.1 准备工作

4.2.2 买一副牌逻辑

4.2.3 洗牌逻辑

4.2.3 发牌逻辑(重点)

4.2.4 测试整体逻辑

1、什么是顺序表？

这里运用博主之前写C语言实现顺序表中引用的一句话：

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

顺序表又可以分为动态存储的顺序表和静态存储的顺序表，基本上现在不会使用静态的，这里就不介绍静态的了，所谓动态，就是当顺序表满的时候会自动扩容！我们接着往下看：

在Java中官方提供了ArrayList类，底层也是用数组实现的顺序表。

那么今天我们不急着去解读ArrayList类，而是先凭借我们之前的学习面向对象的知识，以及C语言数据结构阶段顺序表的实现，尝试着模拟实现 ArrayList类，当然，Java提供的是一个泛型类，可以存放任意指定类型数据(基本数据类型除外) ，我们就不模拟的那么复杂，能基本实现一些常见方法就行，等模拟实现之后，我们再去阅读源码。

2、模拟实现ArrayList

2.1 模拟实现前的约定

我们约定 elem 是存放整型数据的数组，size 表示数组当前有效元素个数，DEFAULT_CAPACITY 容量值，那么就可以写出这样的代码：

public class MyArrayList {
    private int elem[]; //存放数据
    private int size; //数组有效元素个数
    private static final int DEFAULT_CAPACITY = 10; //约定容量
}

同时我们还要实现以下几个常用的方法：

public void add(int data);// 新增元素,默认在数组最后新增

public void add(int pos, int data);// 在 pos 位置新增元素

public boolean contains(int toFind);// 判定是否包含某个元素

public int indexOf(int toFind);// 查找某个元素对应的位置

public int get(int pos);// 获取 pos 位置的元素

public void set(int pos, int value);// 给 pos 位置的元素设为 value

public void remove(int toRemove);//删除第一次出现的关键字key

public int getSize()// 获取顺序表长度

public void clear();// 清空顺序表

其实还有很多方法，比如头插，尾删，但这些你实现了上面的，相信你自己也能解决的，现在我们就撸起袖子写代码吧：

2.2 构造方法

这里我们想一想，如何设置我们的构造方法呢？如果用户想一开始的时候就自定义大小呢？如果不想自定义我们是不是要设置一个默认的大小？那么就可以写出下面两个构造方法：

// 无参构造方法，默认将数组容量设置成DEFAULT_CAPACITY
public MyArrayList() {
    this.elem = new int[DEFAULT_CAPACITY];
}
// 带参数构造方法，将数组容量设置成用户指定的容量
public MyArrayList(int capacity) throws IllegalCapacityException {
    // 检查指定容量是否非法
    if (capacity <= 0) {
        throw new IllegalCapacityException("设置非法容量");
    }
    this.elem = new int[capacity];
}

代码中的异常是我自定义的一个运行时异常，如果对异常还不了解的，可以看博主之前写的JavaSE系列文章，这里我就不再谈异常了。

2.3 add方法

private void capacity() {
    //将原数组扩大到2倍，利用Arrays.copyOf
    int len = getSize();
    this.elem = Arrays.copyOf(this.elem, len * 2);
}

// 新增元素,默认在数组最后新增
public void add(int data) {
    // 1.空间是否满了，满了则需要扩容
    if (getSize() == this.elem.length) {
        capacity(); //扩容
    }
    // 2.往数组最后位置新增元素
    // 3.有效数据自增1
    this.elem[this.size++] = data;
}

在写这个方法的时候，我们要注意数组如果满了就要增容，而增容这里我们用到 copyOf 方法，每次扩容2倍。

add方法重载，在pos位置新增：

// 在 pos 位置新增元素
public void add(int pos, int data) throws IllegalPosException {
    //1.检查pos下标的合法性(顺序表指定插入前面必须有元素，不能隔着插入)
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("指定插入pos位置不合法");
    }
    //2.判断数组是否需要增容
    if (getSize() == this.elem.length) {
        capacity(); //扩容
    }
    //3.从pos位置的元素都往后移
    for (int i = this.size - 1; i >= pos; i--) {
        this.elem[i + 1] = this.elem[i];
    }
    //4.pos位置放入数据，size自增
    this.elem[pos] = data;
    this.size++;
}

这里图就不给大家画了，在博主数据结构C语言版本的时候已经有很详细了图解了，感兴趣的可以去看一看，大同小异。

这里我们直接来说第一个要注意的点，因为是顺序表，插入元素不能隔着元素插入，也就是你插入的位置前面必须要有元素！也就得出 pos 必须小于等于我们的有效元素个数！

而且 pos 的位置不能小于0！

接着就是判断扩容和中间插入需要挪动后面的元素了，过程很简单，这里就不多谈了。

2.4 contains 方法

// 判定是否包含某个元素
public boolean contains(int toFind) {
    //1.遍历数组
    for (int i = 0; i < getSize(); i++) {
        if (this.elem[i] == toFind) {
            return true; //2.找到返回true
        }
    }
    //3.找不到返回false
    return false;
}

这个方法就太简单了，看我写的注释就能看懂！

2.5 indexOf 方法

// 查找某个元素对应的位置
public int indexOf(int toFind) {
    //1.遍历数组
    for (int i = 0; i < getSize(); i++) {
        if (this.elem[i] == toFind) {
            return i; //2.找到返回下标
        }
    }
    //3.找不到返回-1
    return -1;
}

这个方法跟上面contains方法大同小异，无需多言！

2.6 get 方法

// 获取 pos 位置的元素
public int get(int pos) {
    //1.判断pos位置是否合法
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("获取pos位置不合法");
    }
    //2.返回pos位置值
    return this.elem[pos];
}

这个方法需要注意的点就是判断pos下标位置的合法性，注意这一点就ok了！

2.7 set 方法

// 给 pos 位置的元素设为 value
public void set(int pos, int value) {
    //1.判断pos位置是否合法
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("pos位置不合法");
    }
    //2.设置值
    this.elem[pos] = value;
}

好像跟上面的 get 方法没什么区别唉，多简单就不用我多说了吧！

2.8 remove 方法

//删除第一次出现的关键字key
public void remove(int toRemove) {
    //1.获取第一次key出现的位置
    int pos = indexOf(toRemove);
    if (pos == -1) {
        return;
    }
    //2.从pos位置的元素都往前覆盖
    for (int i = pos + 1; i < getSize(); i++) {
        this.elem[i - 1] = this.elem[i];
    }
    //3.有效数据减一(如果是引用类型需要置null)
    this.size--;
}

这个方法我们就可以复用我们之前写的 indexOf 方法了，不用重新写查找逻辑了，接着把后面的元素覆盖掉 pos 下标的元素就可以了！记得别忘记有效数据减一哦！

2.9 getSize 和 clear 方法

// 获取顺序表长度
public int getSize() {
    return this.size;
}

// 清空顺序表
public void clear() {
    this.size = 0;
}

这两个就简单了吧，但是要注意一点，如果你的顺序表放的是引用类型，需要置null，方法已经实现的差不多了，感兴趣的下来结合代码画图写一写吧！