【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 位置的元素设为 valuepublic void remove(int toRemove);//删除第一次出现的关键字keypublic int getSize()// 获取顺序表长度public void clear();// 清空顺序表
其实还有很多方法,比如头插,尾删,但这些你实现了上面的,相信你自己也能解决的,现在我们就撸起袖子写代码吧:
2.2 构造方法
这里我们想一想, 如何设置我们的构造方法呢?如果用户想一开始的时候就自定义大小呢?如果不想自定义我们是不是要设置一个默认的大小?那么就可以写出下面两个构造方法:
// 无参构造方法,默认将数组容量设置成DEFAULT_CAPACITYpublic 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 = 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 位置的元素设为 valuepublic 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 方法
//删除第一次出现的关键字keypublic 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的成员属性
- ArrayList实现了RandomAccess接口,表明ArrayList支持随机访问
- ArrayList实现了Cloneable接口,表明ArrayList是可以clone的
- ArrayList实现了Serializable接口,表明ArrayList是支持序列化的
这就是类定义的前部分,这里还是比较复杂的,会随着我们学习的深入,逐步学习到。
接下来我们来看ArrayList的几个成员变量:
3.2 ArrayList的构造方法
3.2.1 构造方法1
当前是一个带参数的构造方法,很好理解,根据传递的参数开辟大小,如果参数是等于0,就直接把 EMPTY_ELEMENTDATA 共享空数组赋值给存放数据的数组中, 如果是给定一个负数,显然是错误的,也即直接抛出异常!
3.2.2 构造方法2
奇怪,这个无参构造方法居然也是给了一个空数组,也就是没有分配数组内存,那到底是怎么把数据放进去的呢?别急,随着后面的讲解,你会解开这个谜题。
3.2.3 构造方法3
按照集合迭代器返回元素的顺序,构造一个包含指定集合元素的列表,如果是属于同类型,就直接放入到存放数据的数组中,如果不是同类型,则利用 copyOf 拷贝指定的集合,如果指定集合长度为0,则把 EMPTY_ELEMENTDATA 共享空数组赋值给存放数据的数组中。
这个地方如果你不是很理解,没关系,因为现在还没接触迭代器,随着学习的深入就会接触到。
3.3 ArrayList 的 add 方法
别小看这几行代码,跟我们自己模拟实现的还是有区别的,真正有内涵的代码其实在 ensureCapacityInternal 这个方法中,那么现在,我们就一步步去解开他的面纱:
有了上面的图解我们不难看出,真正的扩容是在 add 方法中实现的,所以在实例化 ArrayList 的时候,是不会默认给你开辟空间的。所以 ArrayList 默认容量是在 add 方法调用后,才会分配空间。而且在真正扩容之前会检测是否能扩容成功,防止太大导致扩容失败。
3.4 ArrayList的常用方法
方法 | 作用 |
---|---|
boolean add(E e) | 尾插 e |
void add(int index, E element) | 将 e 插入到 index 位置 |
boolean addAll(Collection c) | 尾插 c 中的元素 |
E remove(int index) | 删除 index 位置元素 |
boolean remove(Object o) | 删除遇到的第一个 o |
E get(int index) | 获取下标 index 位置元素 |
E set(int index, E element) | 将下标 index 位置元素设置为 element |
void clear() | 清空顺序表 |
boolean contains(Object o) | 判断 o 是否在线性表中 |
int indexOf(Object o) | 返回第一个 o 所在下标 |
int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
List subList(int fromIndex, int toIndex) | 截取部分 list |
还有其他方法需要使用的话,就可以去查阅Java的帮助文档,到了数据结构阶段,就要尝试着自己看源码,看文档了,培养自主学习的能力!
4、ArrayList的使用
4.1 ArrayList的遍历
对于顺序表的遍历,我们可以通过 for 循环,for-each,以及迭代器的方法遍历:
public class TestArrayList { public static void main(String[] args) { ArrayList 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 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 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!
4.2.3 洗牌逻辑
买一副扑克牌的逻辑写好了,那么现在就应该洗牌了,那么洗牌应该怎么去实现他呢?
我们可以运用 Random 类中产生随机数方法,但是产生了随机数,如何打乱牌呢?
如果从最后一个开始洗,即 last 位置开始,产生 last 的随机数是 [0~last) ,不包含last,所以我们可以从后往前洗牌,每次把最后一张牌与产生的随机数位置的牌交换即可。(不考虑业务性)
4.2.3 发牌逻辑(重点)
如何去模拟实现发牌呢?一共有三个人打牌,每个人轮流摸牌,如果是54张牌要摸18轮,摸到的牌是不是也应该放到对应的人手上,站在编程的角度,应该摸到的牌应该放在对应那个人的容器中。
如何表示我们上述的设想呢?假设我们有一个顺序表,一共三个元素,分别代表三个人,而每个元素里面又放着一个顺序表,而这个顺序表对应着这个人摸到的牌!我们就能画出这样的图:
通过图我们想一想,这个结构不就是有一个ArrayList吗?然后ArrayList里面放的元素类型还是ArrayList,我们要传什么实参类型进去呢?当然是Poker了啊,因为里面的ArrayList最后是要放扑克牌的!于是我们就能写出这样的代码:
这里我们要说一点,发牌的时候,每次都是删除第一张牌,并且把删除的第一张牌增加到对应用户的手牌中,这样也就形成了摸牌逻辑,最后把牌打印出来就好了!
4.2.4 测试整体逻辑
最终我们在main方法中调用如上的 testGame方法实现的是这样一个效果:
到这就实现的差不多啦!买牌,洗牌,发牌逻辑都没问题,这个小练习,不涉及业务,我们主要是把学习的顺序表知识运用起来,听博主一句话,学数据结构,多敲代码多画图!
下期预告:【Java 数据结构】单链表与OJ题