【Java 数据结构】顺序表

- 日理万妓 2024-04-03 09:54 17阅读 0赞

![b4e6ca8983a34017be11d504193bfa0e.png][] 篮球哥温馨提示：编程的同时不要忘记锻炼哦！

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

--------------------

**目录**

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，方法已经实现的差不多了，感兴趣的下来结合代码画图写一写吧！

--------------------

## **3、ArrayList 的学习** ##

### 3.1 ArrayList的成员属性 ###

![624dc106a5744cad90baad09f4a61222.png][]

>  *  ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
>  *  ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
>  *  ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

这就是类定义的前部分，这里还是比较复杂的，会随着我们学习的深入，逐步学习到。

**接下来我们来看ArrayList的几个成员变量：**

![2e1a46bd907d4420a0d0af054977957e.png][]

### 3.2 ArrayList的构造方法 ###

### 3.2.1 构造方法1 ###

![065b7e9f4a434b449452ed54d4171563.png][]

当前是一个带参数的构造方法，很好理解，根据传递的参数开辟大小，如果参数是等于0，就直接把 EMPTY\_ELEMENTDATA 共享空数组赋值给存放数据的数组中， 如果是给定一个负数，显然是错误的，也即直接抛出异常！

### 3.2.2 构造方法2 ###

![8bcfd841beb84a348b21f94154a6da34.png][]

奇怪，这个无参构造方法居然也是给了一个空数组，也就是没有分配数组内存，那到底是怎么把数据放进去的呢？别急，随着后面的讲解，你会解开这个谜题。

### 3.2.3 构造方法3 ###

![37883e588cfb4fc38c77661e73f7bfae.png][]

按照集合迭代器返回元素的顺序，构造一个包含指定集合元素的列表，如果是属于同类型，就直接放入到存放数据的数组中，如果不是同类型，则利用 copyOf 拷贝指定的集合，如果指定集合长度为0，则把 EMPTY\_ELEMENTDATA 共享空数组赋值给存放数据的数组中。

这个地方如果你不是很理解，没关系，因为现在还没接触迭代器，随着学习的深入就会接触到。

### 3.3 ArrayList 的 add 方法 ###

![51d79bed334146aa9bdfcc93255b9646.png][]

别小看这几行代码，跟我们自己模拟实现的还是有区别的，真正有内涵的代码其实在 ensureCapacityInternal 这个方法中，那么现在，我们就一步步去解开他的面纱：

![d5a85cd022f54c17b5117e5a1dfa46e2.png][]有了上面的图解我们不难看出，真正的扩容是在 add 方法中实现的，所以在实例化 ArrayList 的时候，是不会默认给你开辟空间的。所以 ArrayList 默认容量是在 add 方法调用后，才会分配空间。而且在真正扩容之前会检测是否能扩容成功，防止太大导致扩容失败。

### 3.4 ArrayList的常用方法 ###

<table style="width:663px;"> 
 <thead> 
  <tr> 
   <th style="width:305px;">方法</th> 
   <th style="width:357px;">作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="width:305px;">boolean add(E e)</td> 
   <td style="width:357px;">尾插 e</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">void add(int index, E element)</td> 
   <td style="width:357px;">将 e 插入到 index 位置</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">boolean addAll(Collection c)</td> 
   <td style="width:357px;">尾插 c 中的元素</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">E remove(int index)</td> 
   <td style="width:357px;">删除 index 位置元素</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">boolean remove(Object o)</td> 
   <td style="width:357px;">删除遇到的第一个 o</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">E get(int index)</td> 
   <td style="width:357px;">获取下标 index 位置元素</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">E set(int index, E element)</td> 
   <td style="width:357px;">将下标 index 位置元素设置为 element</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">void clear()</td> 
   <td style="width:357px;">清空顺序表</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">boolean contains(Object o)</td> 
   <td style="width:357px;">判断 o 是否在线性表中</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">int indexOf(Object o)</td> 
   <td style="width:357px;">返回第一个 o 所在下标</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">int lastIndexOf(Object o)</td> 
   <td style="width:357px;">返回最后一个 o 的下标</td> 
  </tr> 
  <tr> 
   <td style="width:305px;">List subList(int fromIndex, int toIndex)</td> 
   <td style="width:357px;">截取部分 list</td> 
  </tr> 
 </tbody> 
</table>

还有其他方法需要使用的话，就可以去查阅Java的帮助文档，到了数据结构阶段，就要尝试着自己看源码，看文档了，培养自主学习的能力！

--------------------

## **4、ArrayList的使用** ##

### 4.1 ArrayList的遍历 ###

对于顺序表的遍历，我们可以通过 for 循环，for-each，以及迭代器的方法遍历：

public class TestArrayList {
        public static void main(String[] args) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(1);
            arrayList.add(2);
            arrayList.add(3);
            // 通过for循环遍历ArrayList
            for (int i = 0; i < arrayList.size(); i++) {
                System.out.print(arrayList.get(i) + " ");
            }
            // 通过for-each循环遍历ArrayList
            for (Integer integer : arrayList) {
                System.out.print(integer + " ");
            }
            // 通过迭代器遍历ArrayList(了解即可)
            Iterator<Integer> it = arrayList.iterator();
            while (it.hasNext()) {
                System.out.print(it.next() + " ");
            }
        }
    }

### 4.2 扑克牌例子 ###

这里我们要运用我们上面学的知识写一个扑克牌的例子：

#### 4.2.1 准备工作 ####

首先我们肯定有一个类把我们的一张扑克抽象出来，扑克有花色和点数，那么我们就可以这样写：

public class Poker {
        private String decor;
        private int number;
    
        public Poker(String decor, int number) {
            this.decor = decor;
            this.number = number;
        }
    
        @Override
        public String toString() {
            return this.decor + this.number;
        }
    }

那么我们还得需要表示多张扑克牌，同时也需要一个存放扑克牌的容器，这里我们选用 ArrayList，同时还需要一个数组来存储对应花色。

public class Pokers {
        private final String[] decor = { "♥", "♠", "♣", "♦" };
        private List<Poker> pokerList = new ArrayList<>();
    
        // 获取花色
        public String get(int index) {
            return decor[index];
        }
    }

这里为什么可以使用 List 接收 ArrayList 的对象呢？因为 List 是一个接口，ArrayList 实现了这个接口，所以这里就实现了**向上转型**。

#### 4.2.2 买一副牌逻辑 ####

准备工作都做好了，我们要实现买一副牌的逻辑，除了大小王一共有52张牌，我们这里用11 12 13 代替 J Q K，每张牌一共有四种花色，也就是定义一个双层循环遍历放入到我们的容器中即可，最后在放入我们的大小王，这里不涉及太复杂，就定大小王的点数为0！

![e4622ddd4eca471782f420993f507aac.png][]

#### 4.2.3 洗牌逻辑 ####

买一副扑克牌的逻辑写好了，那么现在就应该洗牌了，那么洗牌应该怎么去实现他呢？

我们可以运用 Random 类中产生随机数方法，但是产生了随机数，如何打乱牌呢？

如果从最后一个开始洗，即 last 位置开始，产生 last 的随机数是 \[0~last) ，不包含last，所以我们可以从后往前洗牌，每次把最后一张牌与产生的随机数位置的牌交换即可。(不考虑业务性)

![a6130daad2cf435482a307d6077c52c2.png][]

#### 4.2.3 发牌逻辑(重点) ####

如何去模拟实现发牌呢？一共有三个人打牌，每个人轮流摸牌，如果是54张牌要摸18轮，摸到的牌是不是也应该放到对应的人手上，站在编程的角度，应该摸到的牌应该放在对应那个人的容器中。

如何表示我们上述的设想呢？假设我们有一个顺序表，一共三个元素，分别代表三个人，而每个元素里面又放着一个顺序表，而这个顺序表对应着这个人摸到的牌！我们就能画出这样的图：

![c06ddeb037514f1a92dbb0052514e2b7.png][]

通过图我们想一想，这个结构不就是有一个ArrayList吗？然后ArrayList里面放的元素类型还是ArrayList，我们要传什么实参类型进去呢？当然是Poker了啊，因为里面的ArrayList最后是要放扑克牌的！于是我们就能写出这样的代码：

![df33b712a2b7442b8149d7012ea3e829.png][]

这里我们要说一点，发牌的时候，每次都是删除第一张牌，并且把删除的第一张牌增加到对应用户的手牌中，这样也就形成了摸牌逻辑，最后把牌打印出来就好了！

#### 4.2.4 测试整体逻辑 ####

![7284b1a00de647e4b2da917be933dd19.png][]

最终我们在main方法中调用如上的 testGame方法实现的是这样一个效果：

![db7c7184803b4c208b0c813d02b9f3d7.png][]

到这就实现的差不多啦！买牌，洗牌，发牌逻辑都没问题，这个小练习，不涉及业务，我们主要是把学习的顺序表知识运用起来，听博主一句话，学数据结构，多敲代码多画图！

--------------------

![f5475aba903540b38e26323717bc5139.jpeg][]

下期预告：【Java 数据结构】单链表与OJ题

[b4e6ca8983a34017be11d504193bfa0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7c2f8344938f4924886ea36f2f960cdd.png
[624dc106a5744cad90baad09f4a61222.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a13aa89be44549e3b8358167000c20e3.png
[2e1a46bd907d4420a0d0af054977957e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b6396bc64d5b450b8e2d7caa78edb6b3.png
[065b7e9f4a434b449452ed54d4171563.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/fc105bd18c1a4f2faa5be5adefed5d32.png
[8bcfd841beb84a348b21f94154a6da34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b9b5e921dcd94fdc876fca740ba5d1a3.png
[37883e588cfb4fc38c77661e73f7bfae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b139ea61c8114a0587b50bc49b0cc775.png
[51d79bed334146aa9bdfcc93255b9646.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7e029dd358dc422fa46c1caf53d5de3d.png
[d5a85cd022f54c17b5117e5a1dfa46e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e38da4a4f60d46c9b206e652d2bfbbb6.png
[e4622ddd4eca471782f420993f507aac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9fb3febdda6a4061a766a2fbe3e54b1c.png
[a6130daad2cf435482a307d6077c52c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/dfbcf6744bdd49e888f30bab093c0d97.png
[c06ddeb037514f1a92dbb0052514e2b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/aa3153a90d58468db5a416c58feb8032.png
[df33b712a2b7442b8149d7012ea3e829.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d296d0e76ff04b09bbc57f7c3a690e80.png
[7284b1a00de647e4b2da917be933dd19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/dc0ee9f3597f49098d22adbe388c83d5.png
[db7c7184803b4c208b0c813d02b9f3d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0d42450c5e4a4e3a84e0b677714826f3.png
[f5475aba903540b38e26323717bc5139.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f94d80607f0146fe907d2344cfe762e6.jpeg