🎇个人主页:Ice_Sugar_7
🎇所属专栏:Java数据结构
🎇欢迎点赞收藏加关注哦!
🍉前言
之前我们在C语言阶段已经详细介绍过如何实现一个顺序表,而现在我们采用OOP实现又会有哪些区别呢?一起来看看吧!
附:之前的C语言实现顺序表的博客链接
C语言实现顺序表
🍉整体框架
- 顺序表是一个类,它的成员变量(字段)是一个数组和size
- 在字段那里,数组我们只给声明,没有分配空间。数组对象是在构造方法里面创建的,创建的同时给一个默认的大小,这里设为10,后续有需要的话再扩容
public class MyArrayList{
public int[] elem;
//有效元素个数
public int size;
//数组默认大小
private static final int DEFAULT_SIZE = 10;
public MyArrayList() {
this.elem = new int[DEFAULT_SIZE];
}
}
然后顺序表需要实现各种方法,我们可以用一个接口来封装这些方法,只需让MyArrayList类实现这个接口就ok了。接口命名为IList
在IList中,我们要实现这些方法:
public interface IList {
public void display();
// 新增元素,默认在数组最后新增
public void add(int data);
// 在 pos 位置新增元素
public void add(int pos, int data);
// 判定是否包含某个元素
public boolean contains(int toFind);
// 查找某个元素对应的位置
public int indexOf(int toFind);
// 获取 pos 位置的元素
public int get(int pos);
// 给 pos 位置的元素设为【更新为】 value
public void set(int pos, int value);
/**
* 删除第一次出现的关键字key
* @param key
*/
public void remove(int key);
//删除所有值为key的元素
public void removeAll(int key);
// 获取顺序表长度
public int size();
// 清空顺序表
public void clear();
}
🍉添加元素
🍌尾插
首先需要检查顺序表是否已经满了,如果满了就要扩容,这里我们要用copyof方法扩容
private boolean isFull() {
return this.size == elem.length;
}
private void checkCapacity() {
if(isFull()) {
elem = Arrays.copyOf(elem,elem.length*2); //容量扩大到原来的两倍
}
}
- 两个方法都用private修饰是因为我们不用把它们设计为接口(使用接口的人用不着检查容量、扩容,他们只需用你实现好的接口)
- 这两个方法可以合并为一个方法
public void add(int data) throws ListIsFullException{
//判断顺序表是否满了,如果满了,就要扩容
if(isFull()) {
elem = Arrays.copyOf(elem,elem.length*2);
}
elem[size++] = data; //注意放入元素之后size要+1
}
🍌任意位置插入
和尾插略有区别,这个需要先检查插入的下标是否合法,如果是非法下标,那我们需要抛出异常
//在指定下标插入元素时判断下标是否合法
private boolean checkPosInAdd(int pos) {
if(pos < 0 || pos > size)
return false;
return true;
}
抛出异常我们需要自定义一个异常类,命名为IllegalPosException。它属于运行时异常,所以要继承RuntimeException
public class IllegalPosException extends RuntimeException{
public IllegalPosException(String message) {
super(message);
}
}
//在获取pos处的元素或者设定pos处元素的值时,检查下标是否合法
//这个方法和尾插检查下标的那个方法的区别在于:这个是不可以取到size处的元素
public boolean checkPosInGetAndSet(int pos) {
if(pos < 0 || pos >= size)
return false;
return true;
}
//将pos下标处的值设为value
public void set(int pos, int value) {
if(!checkPosInGetAndSet(pos)) {
throw new IllegalPosException("非法下标!");
}
elem[pos] = value;
}
public void add(int pos, int data) throws IllegalPosException {
if(!checkPosInAdd(pos)) {
throw new IllegalPosException("非法下标!");
}
if(isFull()) {
elem = Arrays.copyOf(elem,elem.length*2);
}
//从pos下标开始的元素往后挪
for(int i = size -1;i>=pos;i--) {
//elem[i+1] = elem[i];
set(i+1,elem[i]);
}
set(pos,data);
++size;
}
🍉其他方法
把添加元素的方法写完后,剩下方法的实现就是洒洒水啦,在此不多赘述。源码已经放在gitee仓库了:
实现顺序表