本文主要是介绍线性表——顺序表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数据结构第一课

• 线性表
• • 顺序表
  • • 增删改查
    • 遍历
    • 用数组实现顺序表

线性表

线性表是什么？线性表就是n个具有相同特性的数据元素的有限序列，注意其概念，是具有相同特性，也就是说线性表中的数据元素需要是相同类型的数据；
线性表是一种在实际中广泛应用的数据结构，常见的线性表有顺序表，链表，栈，队列等等。其中相对重要也相对基础的是顺序表和链表。
线性表的一个元素便占据这一个内存，我们称之为节点，线性表要求每一个节点只能够拥有一个前驱节点和一个后继节点，到底是怎样的呢？我们看下图便能明白：

顺序表

顺序表是线性表的一种，它和数组有一些类似，顺序表是数据结构中更加广义的概念，而数组是java语法中的，是更加具体的概念，我们可以这么说：数组是顺序表实现的一种典型方法。数组有的功能顺序表有，而顺序表所能实现的功能，数组不一定能实现（数组想要实现顺序表的功能需要自己动手敲代码，而顺序表的功能则是标准库中有的，可以直接拿来使用），但是有一点需要注意，数组所特有的“[ ]”取下标是顺序表所不具备的。
顺序表是一个泛型表，即它可以实现多种类型的顺序表，在下面的文章中统一以整型顺序表举例。
创建顺序表
两种创建方法，但是建议使用第一种，因为 ArrayList 是一个类，它实现了List这个接口，可以与链表区分开来。

        List<Integer> A = new ArrayList<>();
        ArrayList<Integer> B = new ArrayList<>();

增删改查

线性表的核心功能是增删改查，顺序表作为线性表中的一员，必然也是具备的。
插入元素——add
add()方法传入的参数不同也有不同插入方法，传过去的是元素的值，则表示进行尾插；而如果在传元素的值以外还有下标位置，则表示根据下标位置插入；

		//public boolean add(int e){}
        A.add(1);
        //public void add(int index, int e){}
        A.add(1,1);

删除元素——remove
remove()与add()一样也有重载方法，有按下标删除，和按内容删除；在 Integer 类型的顺序表中，删除的时候如果不加上 Integer.valueOf(1) 的话系统会默认为下标删除。

		//public int remove(int index){}
        int i = A.remove(0);//按下标删除
        //public boolean remove(int e){} 
        boolean a = A.remove(Integer.valueOf(1));//按内容删除

修改元素——set
set()没有重载方法只有一种使用方法——set(int index, 元素类型 e)，index 表示下标，后面的参数表示要插入的值

		//public int set(int index, int e){}
		A.set(0, 2);

查找元素
查找元素的方法很多——get()、contains()、indexOf()、lastindexOf()，这里不一一介绍了，只演示一种特别常见的方法——get()，get()是获取对应下标的值

		//public int get(int index){}
		A.get(0);

打印顺序表
打印顺序表的方法很多，讲其中最简单的就是直接打印顺序表，这是 ArrayList类 中重写了 toString() 的功劳。

		System.out.println(A);

		[0, 1, 2, 3]

遍历

顺序表的遍历其实和数组的遍历差不多

        for(int i  = 0; i < A.size(); i++){
            System.out.println(A.get(i));
        }
        for(int x : A){
            System.out.println(x);
        }

在打印的时候是使用方法get()，这就是顺序表遍历和数组遍历一个比较明显的差别。

用数组实现顺序表

要想了解顺序表，自己写一个顺序表是最能够清楚的，实现顺序表使用到的是数组。在写代码的时候有一个实现数组的时候明显区别的方法——expansion()，其是被private的修饰的方法，是一个扩容方法，虽然实现简单但却是一个不可获缺的方法，因为顺序表和数组有一个本质上的区别——数组的容量在一开始便是确定，后期不可再更改；而顺序表的容量是可以更改的。
具体实现如下：

public class ArrayList<E> {
    //创建一个数组
    private E[] data;
    private int size = 0;
    private int capacity = 100;

    //由于E的类型不清楚，所以不能够实例化，所以先创建一个Object类型的通用的数组，
    //然后再将其强转为 E 类型
    public ArrayList(){
        data = (E[]) new Object[capacity];
    }

    @Override
    public String toString() {
        E[] arr = (E[]) new Object[size];
        for(int i = 0; i < size; i++){
            arr[i] = data[i];
        }
        return  "[" + Arrays.toString(arr) + "]";

    }

    //数组和顺序表的区别，当容量不够的时候增加容量
    private int expansion(int capacity){
        capacity = capacity * 2;
        return capacity;
    }
    //增
    //从尾部直接增加
    public void add(E record){
        //如果已存储的数据大于或等于容量，那么扩充容量
        if(size >= capacity ){
            expansion(capacity);
        }
        //先将size + 1，再将要添加的数据放到数组中去
        this.data[size++] = record;
    }

    //中间插入
    public void add(int index, E record){
        //如果已存储的数据大于或等于容量，那么扩充容量
        if(size >= capacity ){
            expansion(capacity);
        }
        size++;
        //将index的数值都往后移将其中的空出来
        for(int i = size - 1; i > index; i--){
            data[i] = data[i - 1];
        }
        this.data[index] = record;
    }
    //删
    //删除即为遍历数组找出相同的，然后将其移到最后一个元素的位置，再将size减一;
    public void remove(E record){
        int i = 0;
        for(; i < size; i++){
            if(data[i].equals(record)){
                break;
            }
        }
        if(i >= size){
            System.out.println("查无次数据，无法删除!");
            return;
        }
        for(int j = i; j < size - 1; j++){
            E tmp = data[j];
            data[j] = data[j + 1];
            data[j + 1] = tmp;
        }
        size--;
    }

    //改
    //修改值需要知道修改的坐标位置，第二个修改成什么内容
    public void set(int index, E record){
        data[index] = record;
    }
    //查
    //查询是否存在这个数据
    public boolean contains(E record){
        int i = 0;
        for(; i < size; i++){
            if(data[i].equals(record)){
                break;
            }
        }
        if(i >= size){
            return false;
        }
        return true;
    }

    //查询对应内容得下标
    public int IndexOf(E record){
        int i = 0;
        for(; i < size; i++){
            if(data[i].equals(record)){
                break;
            }
        }
        if(i >= size){
            return -1;
        }
        return i;
    }

    //从后面开始查找，找出与所找元素相同的第一个元素
    public int lastIndexOf(E record){
        int i = size - 1;
        for(; i >= 0; i--){
            if(data[i].equals(record)){
                break;
            }
        }
        if(i < 0){
            return -1;
        }
        return i;
    }

    //查询对应下标的内容
    public E get(int index){
        return data[index];
    }

    //查询链表长度
    public int Size(){
        return size;
    }

    //清空顺序表
    public void clear(){
        size = 0;
    }

    //判断顺序表是否为空,为空输出 true ,反之输出false
    public boolean isEmpty(){
        if(size == 0){
            return true;
        }else{
            return false;
        }
    }
}

这篇关于线性表——顺序表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！