当前位置：首页 > news >正文

「数据结构」实现顺序表

news 来源：原创 2024/5/13 5:59:48

🎇个人主页：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 位置的元素设为【更新为】 valuepublic 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下标处的值设为valuepublic 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;}