【大厂算法系列】编码手写顺序表相关功能，线性结构核心知识点详细剖析

什么是线性表

• 在第二章里我们说到的两个元素有**“一对一”** 逻辑关系的数据，其储存方式就是线性表

• 线性表也叫线性储存结构，是基本最常用的一种数据结构。由n个具有相同特性的数据元素组成的序列

• 这样理解成 线性表储存数据就是把所有的数据用一根线穿起来，放到物理空间中。如下，这种几种存放的结构，数据依次储存到物理空间， 就称为顺序表 ，数据分散存放的结构也称为链表

• 线性表相关术语

  • 线性表中的每个个体被称为数据元素 图中1,2,3都是一个元素
  • 具有一对一逻辑关系的数据

• 某个元素左边的相邻元素称为前驱元素 ，右边的相邻元素称为后继元素 如图4的前驱元素与后继元素

• 总结线性表的特征：

  • 数据元素之间具有一对一的逻辑关系
  • 第一个元素没有前驱元素，如图中的1，这个1也被称为头元素
  • 最后一个元素没有后继元素，如图中的6，比称为尾元素
  • 除了头元素跟尾元素，其他的元素只存在一个前驱或者后继节点

什么是顺序表

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

• Java中的ArrayList类
  • 增加元素
  • 删除元素
  • 修改元素值
  • 查找缘故

顺序表简介初始化和判空判满功能实现

• 顺序表的实现

  • 顺序表的实现一般包含了如下几个方法：

    判断顺序表是否为空表	public boolean isEmpty()
    判断顺序表是否满	public boolean ifFull()
    向顺序表中添加元素	public void addNum(int ele)
    删除指定位置的元素	public void delNum(int ele)
    在指定的位置添加元素	public void insertNum(int i,int number)
    修改数据	public void changeData(int index,int number)
    获取顺序表的长度	public int getLength()
    获取对应位置的元素	public int getNum(int flag)
    遍历输出顺序表	public void showNum()

• 判断队列是否为空

• 判断队列是否为满

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

顺序表实现之指定位置数据的增加与遍历操作

• 添加元素

 //顺序表添加元素
    public void addNum(int ele){
        if(isFull()){
            reList(list.length*2);
        }
        list[num++]=ele;
    }

• 遍历元素

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

• 在指定位置插入元素

    //顺序表指定位置插入元素
    public void insertNum(int i,int number){
        if(i<0 || i>num-1){
            throw new RuntimeException("参数不合法");
        }
        if(isFull()){
            reList(list.length*2);
        }
        //把i的位置腾出来 i位置的元素全部向后移动一位
        for(int index=num;index>i;index--){
            list[index]=list[index-1];
        }
        //直接插入元素
        list[i]=number;
        num++;
    }

顺序表实现删除指定位置的元素与修改操作

• 删除指定元素

public void delNum(int ele) {
        if (ele < 0 || ele > num-1) {
            throw new RuntimeException("参数不合法");
        }
        //把每个元素向前移动一位
        for(int index=ele+1;index<num;index++){
            list[index-1]=list[index];
        }
        num--;
    }

• 修改元素

//修改元素
    public void changeData(int index,int number){
        list[index]=number;
    }

• 获取有效元素个数

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

• 获取对应位置元素

//获取元素
    public int getNum(int index){
        return list[index];
    }

顺序表实现扩容操作

• 在之前的操作中，我们实现了isFull()判满的操作，当有效元素个数等于数组长度的时候，就无法插入了。这样设计一个顺序表的话明显是不合理的，需要增加扩容功能。

• 当你的顺序表满的时候，就自动将顺序表进行扩容，让其可以继续增加数据。

实现思路：

• 顺序表满的时候

• 我们就实现一个方法，检查当前数组的大小是否可以加入新的元素。如果不行，就创建容量是之前两倍的数组，把之前的元素复制进去，之后继续完成添加元素的操作。

代码实现：

public void reList(int size){
        //保存之前的顺序表
        int []temp=list;
        //创建新的顺序表
        list=new int[size];
        //拷贝
        for(int i=0;i<temp.length;i++){
            list[i]=temp[i];
        }
    }

顺序表使用泛型适应多种类型数据

public class SequenceDemoT {
    public static void main(String[] args) {
        SequenceList1 sequenceList = new SequenceList1(4);
        sequenceList.addNum("xx");
        sequenceList.showNum();
    }
}

class SequenceList1<T>{
    //顺序表元素存放的数组
    private T[] list;
    //顺序表的有效元素个数
    private int num;
    public SequenceList1(int size){
        list=(T[])new Object[size];
        num=0;
    }
    //顺序表的判空实现
    public boolean isEmpty(){
        return num==0;
    }
    //顺序表的判满实现
    public boolean isFull(){
        return num==list.length;
    }
    //顺序表添加元素
    public void addNum(T ele){
        if(isFull()){
            //扩容
            reList(list.length*2);
        }
        list[num++]=ele;
    }
    //顺序表指定位置插入元素
    public void insertNum(int i,T number){
        if(i<0 || i>num){
            throw new RuntimeException("参数不合法");
        }
        if(isFull()){
            //扩容
            reList(list.length*2);
        }
        //把i的位置腾出来 i位置的元素全部向后移动一位
        for(int index=num;index>i;index--){
            list[index]=list[index-1];
        }
        //直接插入元素
        list[i]=number;
        num++;
    }
    //顺序表的遍历
    public void showNum(){
        for(int i=0;i<num;i++){
            System.out.println(list[i]);
        }
    }
    //删除指定位置的元素
    public void delNum(int ele) {
        if (ele < 0 || ele > num) {
            throw new RuntimeException("参数不合法");
        }
        //把每个元素向前移动一位
        for(int index=ele+1;index<num;index++){
            list[index-1]=list[index];
        }
        num--;
    }
    //修改元素
    public void changeData(int index,T number){
        list[index]=number;
    }
    //获取元素个数
    public int getLength(){
        return num;
    }
    //获取元素
    public T getNum(int index){
        return list[index];
    }
    //顺序表扩容
    public void reList(int size){
        //保存之前的顺序表
        T []temp=list;
        //创建新的顺序表
        list=(T[])new Object[size];
        //拷贝
        for(int i=0;i<temp.length;i++){
            list[i]=temp[i];
        }
    }

}

专栏地址：【大厂算法系列】
专栏内容： 数组，列表，栈，队列，树，哈希表，字符串，堆，查找，排序，DFS,BFS，回溯，贪心，动态规划等+力扣大厂真题
算法交流： V 【yopa66】