数据结构-顺序表

一.思维导图

二.什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

三.顺序表的实现

（1）.在实现顺序表的之前，我们要创建一个数组，这里我就用int类型的数据进行创建。

（2）.同时我们还需要创建一个usedSize变量，用来记录顺序表中元素的个数。

（3）.提供两个构造方法（分别是带参数的构造方法和不带参数的构造方法）

这些基本的代码完成之后我们就要开始实现顺序表中的方法。

1.添加元素（add）

(1).在末尾位置新增元素。

但是我们会想到，如果数组正好满了不能再添加新的元素我们会怎么办？
这里我们就要想到要先对数组进来扩容然后再存放数据。

 private boolean isFull(){
        return usedSize==elem.length;
}
    //扩容方法的实现
    private void checkExpansion(){
        if (isFull()){
            elem=Arrays.copyOf(elem,elem.length*2);
        }
 }
    @Override
    public void add(int data) {
        //如果数组满了怎么办？扩容
        checkExpansion();
        this.elem[usedSize]=data;
        usedSize++;
 }
//我们先判断数组是否已经满了，如果满了的情况下就要对数组进行扩容。

（2）.在任意位置添加元素。
在任意位置添加元素首先要看pos的合法性，如果pos小于0，或者pos大于usedSize都是不可取的。

private void isLegal(int pos) throws PosLegitimate{
        if(pos<0||pos>usedSize){
            System.out.println("不合法");
            throw new PosLegitimate("pos下标异常"+pos);
        }
    }

public void add(int pos, int data) {
        //1，先判断pos的合法性
        try{
            isLegal(pos);
        }catch (PosLegitimate e){
            e.printStackTrace();
        }
        checkExpansion();

        for (int i = usedSize-1; i < pos; i--) {
            elem[i+1]=elem[i];
        }
        elem[pos]=data;
        usedSize++;
    }

2.判定是否包含某个元素

先判断数组是否为空，如果为空返回false。

@Override
    public boolean contains(int toFind) {
        if (isEmpty()){
            return false;
        }
        for (int i = 0; i < usedSize; i++) {
            if(elem[i]==toFind){
                return true;
            }
        }
        return false;
    }

3.查找某个元素对应的位置

 @Override
    public int indexOf(int toFind) {
        if (isEmpty()){
            return -1;
        }
        for (int i = 0; i < usedSize; i++) {
            if(elem[i]==toFind){
                return i;
            }
        }
        return -1;
    }

4.获取某一下标的元素

也要考虑到pos的合法性

 private void isLegalGetAndSet(int pos) throws MyArrayEmpty{
        if(pos<0||pos>=usedSize){
            System.out.println("不合法");
            throw new MyArrayEmpty("获取指定元素下标异常");
        }
    }


  @Override
    public int get(int pos) {
        isLegalGetAndSet(pos);
        return elem[pos];
    }

5.更新某一下标的元素

 private void isLegalGetAndSet(int pos) throws MyArrayEmpty{
        if(pos<0||pos>=usedSize){
            System.out.println("不合法");
            throw new MyArrayEmpty("获取指定元素下标异常");
        }
    }

public void set(int pos, int value) {
        isLegalGetAndSet(pos);
        elem[pos]=value;
    }

6.删除某一位置元素

删除一个元素，我们首先要找到该元素所在的位置，然后我们将后面的元素一个一个向前挪动给他覆盖掉即可。

@Override
    public void remove(int toRemove) {
        int index=indexOf(toRemove);
        if(index==-1){
            System.out.println("找不到");
            return;
        }
        for (int i = index; i < usedSize-1; i++) {
            elem[i]=elem[i+1];
        }
        usedSize--;
    }

当然循环中为什么是usedSize-1，是因为循环体中elem[i+1]，如果是要删除数组的最后一个数据，那么elem[i+1]就会报错。因为此时数组已经越界。

6.获取顺序表长度

 @Override
    public int size() {
        return this.usedSize;
    }

7.清空顺序表

 public void clear() {
        this.usedSize=0;
    }