博客

顺序表：

概念以及结构：


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

顺序表一般可以分为：

静态顺序表：使用定长数组存储。

动态顺序表：使用动态开辟的数组存储。

顺序表的各种操作：


顺序表的各种操作—-尾插、头插、插入指定位置、尾删、头删、删除指定位置、查找元素、下标与修改元素

package 顺序表;

/**
 * Create with Darcula IDEA
 * Description:
 *
 * @Author CJP
 */
public class MyArrayList {
    private int[] array;
    private int size;

    public MyArrayList() {
        array = new int[2];
        int aize = 0;
    }

    //顺序表 增
    //尾插
    public void pushBack(int element) {
        ensureCapacity();
        array[size] = element;
        size++;
    }

    //头插
    public void pushFront(int element) {
        ensureCapacity();
        for (int i = size - 1; i >= 0; i--) {
            array[i + 1] = array[i];
        }
        array[0] = element;
        size++;
    }

    //插入指定位置
    public void insert(int index, int element) {
        if (index < 0 | index > size) {
            System.out.println("下标错误");
            return;
        }
        ensureCapacity();

        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = element;
        size++;
    }
    //顺序表 删
    //尾删
    public void popBack() {
        if (size <= 0) {
            System.out.println("顺序表为空");
            return;
        }
        array[--size] = 0;
    }

    //头删
    public void popFront() {
        if (size <= 0) {
            System.out.println("顺序表为空");
            return;
        }
        for (int i = 1; i <= size - 1; i++) {
            array[i - 1] = array[i];
        }
        array[size - 1] = 0;
        size--;
    }

    //删除指定位置的元素
    public void earse(int index) {
        if (size <= 0) {
            System.out.println("顺序表为空");
            return;
        }
        if(index < 0 | index > size){
            System.out.println("下标不合理");
            return;
        }
        for (int i = index + 1; i < size; i++) {
            array[i - 1] = array[i];
        }
        array[--size] = 0;
    }

    //顺序表  查
    //返回 element 在顺序表中的下标，如果出现多次，返回第一次出现的下标
    public int indexOf(int element){
        for(int i = 0; i < size; i++){
            if(array[i] == element){
                return i;
            }
        }
        return -1;
    }
    //给一个下标，找出下标位置的数
    public int get(int index){
       if(index < 0 | index > size){
           System.out.println("下标不合理");
           return -1;
       }
       return array[index];
    }
    //顺序表  改
    // 修改指定位置的数
    public void set(int index, int element){
        if(index < 0 | index > size){
            System.out.println("下标不合理");
            return ;
        }
       array[index] = element;
    }

    //确保容量是否够用，否则进行扩容
    private void ensureCapacity() {
        if (size < array.length) {
            return;
        }
        int newCapacity = array.length * 2;
        int[] newArray = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = array[i];
        }
        array = newArray;
    }
    //打印
    public void print(){
        System.out.println("长度为："+ array.length);
        for(int i = 0; i < size; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }

    //测试代码
    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.print();
        list.pushBack(1);
        list.pushBack(2);
        list.pushBack(3);
        list.print();
        list.pushFront(9);
        list.print();
        list.insert(2,8);
        list.print();
        list.popBack();
        list.print();
        list.popFront();
        list.print();
        list.earse(1);
        list.print();
    }
}