🍎1、线性结构

在提及顺序表之前我们首先要讲的概念是线性结构简而言之线性结构就是一对一的逻辑关系结构。下面的糖葫芦就深刻的体现了线性结构一个个的山楂相当于线性结构中的数据也就是所有数据用线串起来然后存储在物理空间中。

• 线性表在逻辑上是线性结构也就说是连续的一条直线。
• 线性表在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。

🍎2、顺序表

将数据依次存储在连续的整块物理空间中这种存储结构称为顺序存储结构简称顺序表。顺序表的底层原理为数组在数组上完成数据的增删查改。下面就是顺序表看起来其实和数组一样。

那么有人可能会说了既然顺序表底层原理是数据那么为什么要用顺序表呢直接使用数组不就行了嘛

• 顺序表可以对数据进行整合和管理顺序表也是一种简单的数据结构。
• 顺序表记录元素的个数比如我想要在顺序表中存放七个元素然而数组中有9个空间如果是数组打印元素会把后面的0也打印出来而在顺序表中会记录它的有效个数就不会打印出0。顺序表有很多基本操作我们慢慢往下看。

代码实现顺序表各个操作

public class MyArrayList {
    public int[] elem;
    public int usedSize;//有效数据个数
    public MyArrayList() {
        this.elem = new int[5];
    }
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] +" ");
        }
        System.out.println();
    }

    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;//找不到返回-1
    }

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if(this.isFull()) {
            resize();
        }

        this.elem[this.usedSize] = data;
        this.usedSize++;
    }
    /**
     * 扩容
     */
    private void resize() {
        this.elem = Arrays.copyOf(this.elem,
                2*this.elem.length);
    }

    /**
     * 判断是否为满
     * @return
     */
    public boolean isFull() {
        /*if(this.usedSize == this.elem.length) {
            return true;
        }
        return false;*/
        return this.usedSize == this.elem.length;
    }

    // 在 pos 位置新增元素 O(N)
    public void add(int pos, int data) {
        checkIndex(pos);
        if(isFull()) {
            resize();
        }
        for (int i = usedSize-1; i >= pos ; i--) {
            elem[i+1] = elem[i];
        }
        elem[pos] = data;
        usedSize++;
    }

    /**
     * 检查add数据的时候pos是否是合法的
     * @param pos
     */
    private void checkIndex(int pos) {
        if(pos < 0 || pos > usedSize) {
            throw new IndexOutOfException
                    ("位置不合法请检查位置的合法性");
        }
    }

    // 获取 pos 位置的元素
    public int get(int pos) {
        checkGetIndex(pos);
        return elem[pos];
    }

    private void checkGetIndex(int pos) {
        if(pos < 0 || pos >= usedSize) {
            throw new IndexOutOfException
                    ("get获取元素的时候位置不合法请检查位置的合法性");
        }
    }
    // 给 pos 位置的元素设为 value  1
    public void set(int pos, int value) {
        checkIndex(pos);
        elem[pos] = value;
    }

    //删除第一次出现的关键字key O(n)
    public boolean remove(int toRemove) {
        int index = indexOf(toRemove);
        if(index == -1) {
            System.out.println("没有这个数据");
            return false;
        }

        for (int i = index;i < usedSize-1;i++) {
            elem[i] = elem[i+1];
        }
        usedSize --;
        //elem[usedSize] = null;
        // 如果里面是引用类型 那么此时就需要手动置空
        elem[usedSize] = 0;
        return true;
    }

    // 清空顺序表
    public void clear() {
       /*
       for (int i = 0; i < usedSize; i++) {
            elem[i] = null;
        }
        usedSize = 0;
        */
        usedSize = 0;
    }
}

后序
顺序表的内容我们就讲到这里🍠🍠🍠由于顺序表的增删查改不怎么难好多图我就省略了后面将链表的时候我会具体画图带领大家一起学习。💕💕💕