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

【数据结构与算法】顺序表的原理及实现

news 来源：原创 2024/11/17 5:35:57

1.什么是顺序表

顺序表是用一段物理地址连续的存储单元进行存储元素的线性结构，通常是以数组进行存储。
通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

在这里插入图片描述

2.顺序表的实现

判断顺序表是否为空表	public boolean isEmpty()
判断顺序表是否满	public boolean ifFull()
向顺序表中添加元素	public void add(T ele)
删除指定位置的元素	public void delete(int index)
删除指定的元素	public void remove(T ele)
在指定的位置添加元素	public void add(int index,T ele)
修改数据	public void update(int index,T ele)
获取顺序表的长度	public int size()
获取对应位置的元素	public T getIndex(int index)
遍历输出顺序表	public void show()

在这里插入图片描述

（1）定义构造方法

public class SequenceList<T> {

    /**
     * 定义默认的数组长度
     */
    private final static int DEFAULT_SIZE = 10;

    /**
     * 定义存储数组
     */
    private T[] list;

    /**
     * 定义顺序表的有效元素个数
     */
    private int num;

    /**
     * 定义数组的长度
     */
    private int size;

    /**
     * 无参构造方法，默认长度10
     */
    public SequenceList(){
        list = (T[]) new Object[DEFAULT_SIZE];
        this.size = DEFAULT_SIZE;
        this.num=0;
    }

    /**
     * 有参构造，长度为size
     * @param size
     */
    public SequenceList(int size){
        list = (T[]) new Object[size];
        this.size = size;
        this.num=0;
    }
}

（2）判断队列是否为空

    /**
     * 顺序表的判空实现
     * @return
     */
    public boolean isEmpty(){
        //如果num == 0的时候
        return num==0;
    }

（3）判断队列是否为满

    /**
     * 顺序表的判满实现
     * @return
     */
    public boolean isFull(){
        //如果num（当前顺序表元素个数 == 顺序表的长度时）
        return num==list.length;
    }

（4）遍历顺序表元素

    /**
     * 顺序表的遍历
     */
    public void show(){
        for(int i=0;i<num;i++){
            System.out.println(list[i]);
        }
    }

（5）向顺序表中添加元素

    /**
     * 顺序表添加元素，添加到指定的下标下
     * @param index
     * @param ele
     */
    public void add(int index,T ele){
        if(isFull()){
            //这块后续会加上扩容的方法
            System.out.println("当前集合元素已满");
        }
        //如果index 为 -1 表示直接插入末尾
        if(index == -1){
            list[num++]=ele;
            return;
        }
        //不为-1的话，则插入到指定的下标
        if(index<0 || index>num){
            System.out.println("参数不合法");
        }
        //把i的位置腾出来 i位置的元素全部向后移动一位
        if (num - index >= 0) System.arraycopy(list, index, list, index + 1, num - index);
        //直接插入元素
        list[i]=ele;
        num++;
    }

    /**
     * 顺序表添加元素，添加到末尾
     * @param ele
     */
    public void add(T ele){
        this.add(-1,ele);
    }

（6）获取元素的下标索引

    /**
     * 获取元素的下标索引
     * @param ele
     * @return
     */
    public int indexOf(T ele){
        for (int i = 0; i < list.length; i++) {
            if(list[i].equals(ele)){
                return i;
            }
        }
        return -1;
    }

（7）向顺序表中删除指定元素

    /**
     * 删除指定位置的元素
     * @param ele
     */
    public void delete(int index){
        if(index <0 || index>num){
            System.out.println("参数不合法");
        }
        //把每个元素向前移动一位
        if (num - (index + 1) >= 0) System.arraycopy(list, index + 1, list, index + 1 - 1, num - (index + 1));
        num--;
    }

    /**
     * 删除指定元素
     * @param ele
     */
    public void remove(T ele){
        //获取元素下标索引
        int index = this.indexOf(ele);
        if(index == -1){
            System.out.println("当前元素不存在:"+ele);
        }
        //删除元素
        this.delete(index);
    }

（8）修改指定下标元素

    /**
     * 修改指定下标元素
     * @param index
     * @param ele
     */
    public void update(int index,T ele){
        list[index]=ele;
    }

（9）获取有效元素个数

    /**
     * 获取元素个数
     * @return
     */
    public int getNum(){
        return num;
    }

（10）顺序表扩容

    /**
     * 扩充顺序表容量
     * 私有方法，不对外提供，在插入元素时，判断是否已经满的情况下调用
     * 如果顺序表的元素已经满了，则调用扩容方法
     * @param size
     */
    private void reList(int size){
        //保存之前的顺序表
        T []temp=list;
        //创建新的顺序表
        list = (T[]) new Object[size];
        //拷贝元素
        System.arraycopy(temp, 0, list, 0, temp.length);
    }

# 修改add方法中判断元素是否已经满了的逻辑
# 如果元素已经满了，则进行扩容原长度的2倍
# 同时修改容量的大小
if(isFull()){
    this.size = list.length*2;
    reList(this.size);
}

（11）获取顺序表的最大容量

    /**
     * 返回顺序表容量大小
     * @return
     */
    public int size(){
        return size;
    }

（12）整体顺序表实现代码

/**
 * @description 顺序表数据结构实现
 * @author lixiang
 * @param <T>
 */
public class SequenceList<T> {

    /**
     * 定义默认的数组长度
     */
    private final static int DEFAULT_SIZE = 10;

    /**
     * 定义存储数组
     */
    private T[] list;

    /**
     * 定义顺序表的有效元素个数
     */
    private int num;

    /**
     * 定义数组的长度
     */
    private int size;

    /**
     * 无参构造方法，默认长度10
     */
    public SequenceList(){
        list = (T[]) new Object[DEFAULT_SIZE];
        this.size = DEFAULT_SIZE;
        this.num=0;
    }

    /**
     * 有参构造，长度为size
     * @param size
     */
    public SequenceList(int size){
        list = (T[]) new Object[size];
        this.size = size;
        this.num=0;
    }

    /**
     * 顺序表的判空实现
     * @return
     */
    public boolean isEmpty(){
        return num==0;
    }

    /**
     * 顺序表的判满实现
     * @return
     */
    public boolean isFull(){
        return num==list.length;
    }

    /**
     * 顺序表的遍历
     */
    public void showNum(){
        for(int i=0;i<num;i++){
            System.out.println(list[i]);
        }
    }

    /**
     * 顺序表添加元素，添加到指定的下标下
     * @param index
     * @param ele
     */
    public void add(int index,T ele){
        if(isFull()){
            //这块后续会加上扩容的方法
            this.size = list.length*2;
            reList(this.size);
        }
        //如果index 为 -1 表示直接插入末尾
        if(index == -1){
            list[num++]=ele;
            return;
        }
        //不为-1的话，则插入到指定的下标
        if(index<0 || index>num){
            System.out.println("参数不合法");
        }
        //把i的位置腾出来 i位置的元素全部向后移动一位
        if (num - index >= 0) System.arraycopy(list, index, list, index + 1, num - index);
        //直接插入元素
        list[index]=ele;
        num++;
    }

    /**
     * 顺序表添加元素，添加到末尾
     * @param ele
     */
    public void add(T ele){
        this.add(-1,ele);
    }

    /**
     * 删除指定位置的元素
     * @param ele
     */
    public void delete(int index){
        if(index <0 || index>num){
            System.out.println("参数不合法");
        }
        //把每个元素向前移动一位
        if (num - (index + 1) >= 0) System.arraycopy(list, index + 1, list, index + 1 - 1, num - (index + 1));
        num--;
    }

    /**
     * 删除指定元素
     * @param ele
     */
    public void remove(T ele){
        //获取元素下标索引
        int index = this.indexOf(ele);
        if(index == -1){
            System.out.println("当前元素不存在:"+ele);
        }
        //删除元素
        this.delete(index);
    }

    /**
     * 获取元素的下标索引
     * @param ele
     * @return
     */
    public int indexOf(T ele){
        for (int i = 0; i < list.length; i++) {
            if(list[i].equals(ele)){
                return i;
            }
        }
        return -1;
    }

    /**
     * 修改指定下标元素
     * @param index
     * @param ele
     */
    public void update(int index,T ele){
        list[index]=ele;
    }

    /**
     * 获取元素个数
     * @return
     */
    public int getNum(){
        return num;
    }

    /**
     * 扩充顺序表容量
     * 私有方法，不对外提供，在插入元素时，判断是否已经满的情况下调用
     * 如果顺序表的元素已经满了，则调用扩容方法
     * @param size
     */
    private void reList(int size){
        //保存之前的顺序表
        T []temp=list;
        //创建新的顺序表
        list = (T[]) new Object[size];
        //拷贝元素
        System.arraycopy(temp, 0, list, 0, temp.length);
    }

    /**
     * 返回顺序表容量大小
     * @return
     */
    public int size(){
        return size;
    }

}

3.顺序表功能验证

（1）验证顺序表初始化

public class Main {
    public static void main(String[] args) {
        SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();
        SequenceList<Integer> sequenceCustomSizeList = new SequenceList<>(5);
        System.out.println("默认定义顺序表容量大小:"+sequenceDefaultSizeList.size());
        System.out.println("自定义顺序表容量大小:"+sequenceCustomSizeList.size());
    }
}

在这里插入图片描述

（2）验证添加元素

public class Main {
    public static void main(String[] args) {
        SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();
        //添加1 2 3 元素
        sequenceDefaultSizeList.add(1);
        sequenceDefaultSizeList.add(2);
        sequenceDefaultSizeList.add(3);
        //输出
        sequenceDefaultSizeList.show();
    }
}

在这里插入图片描述

（3）验证修改元素

public class Main {
    public static void main(String[] args) {
        SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();
        //添加1 2 3 元素
        sequenceDefaultSizeList.add(1);
        sequenceDefaultSizeList.add(2);
        sequenceDefaultSizeList.add(3);
        //输出
        sequenceDefaultSizeList.show();

        sequenceDefaultSizeList.update(0,9);
        sequenceDefaultSizeList.show();
    }
}

在这里插入图片描述

（4）验证删除元素

public class Main {
    public static void main(String[] args) {
        SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>();
        //添加1 2 3 元素
        sequenceDefaultSizeList.add(1);
        sequenceDefaultSizeList.add(2);
        sequenceDefaultSizeList.add(3);
        //输出
        sequenceDefaultSizeList.show();

        sequenceDefaultSizeList.delete(0);
        sequenceDefaultSizeList.show();
    }
}

在这里插入图片描述

（5）验证集合扩容

public class Main {
    public static void main(String[] args) {
        SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>(2);
        System.out.println("扩容前："+sequenceDefaultSizeList.size());
        //添加1 2 3 元素
        sequenceDefaultSizeList.add(1);
        sequenceDefaultSizeList.add(2);
        sequenceDefaultSizeList.add(3);
        //输出
        System.out.println("扩容后："+sequenceDefaultSizeList.size());
    }
}

在这里插入图片描述

（6）验证获取元素的下标索引

public class Main {
    public static void main(String[] args) {
        SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>(2);//添加1 2 3 元素
        sequenceDefaultSizeList.add(1);
        sequenceDefaultSizeList.add(2);
        //输出
        System.out.println("元素index："+sequenceDefaultSizeList.indexOf(2));
    }
}

在这里插入图片描述

（7）获取当前集合有效元素个数

public class Main {
    public static void main(String[] args) {
        SequenceList<Integer> sequenceDefaultSizeList = new SequenceList<>(4);//添加1 2 3 元素
        sequenceDefaultSizeList.add(1);
        sequenceDefaultSizeList.add(2);
        //输出
        System.out.println("当前集合有效元素个数为："+sequenceDefaultSizeList.getNum());
    }
}