博客

一、顺序表的理解

顺序表是用一段

物理地址连续

的存储单元词义存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

顺序表可以分为静态顺序表和动态顺序表：

1. 静态顺序表使用一块已经确定开辟的定长空间来存储数组元素。

2. 动态顺序表可以根据数组元素个数来动态的开辟内存。

注意数组下标是从0开始

二、顺序表的代码实现

首先我们要先构建一个顺序表并初始化顺序表。

public class MyArrayList {
    public int[] elem;
    public int usedSize;
    public void MyArrayList(){
        this.elem= new int[10];
    }
}

我在其中定义了一个构造方法，用来以后存放数组元素。

1. 打印顺序表

我们通过已知的数组元素，使用for循环即可打印数组元素。

public void display(){
    for (int i = 0; i < usedSize; i++) {
        System.out.println(this.elem[i]+" ");
            }
    System.out.println();
        }

2. 在顺序表中添加元素

在顺序表中添加元素分为两种情况：

1. 在数组的末尾插入元素
   

这种情况比较简单，我们只需要在数组的最后一个元素后面插入新元素就可以了

2. 在数组的中间或者开头插入元素
   

无论是在数组元素的中间插入元素还是在数组元素的开头插入元素，我们都需要将插入元素之后的元素整体向后移动，空出来的空间来存放新的数据元素。

public void add(int pos, int data) {
            if(pos < 0 || pos > usedSize){ //判断插入下标位置是否合法
                System.out.println("位置不合法");
                return;
            }
            if(isFull()){ //判断数组元素是否已满，如果已满则需要进行数组扩容
                this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
            }
            for (int i = this.usedSize - 1; i >= pos; i--) {
                elem[i+1] = elem[i]; //将所有插入元素之后的数组元素向后移动
            }
            this.elem[pos] = data;
            this.usedSize++;
        }

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

判定是否包含特定元素的时候我们只需遍历数组，寻找对应值相等的数组元素并返回是否寻找成功即可。

public boolean isFull(){
     return this.usedSize == this.elem.length;//判断数组的长度
        }
        // 判定是否包含某个元素
public boolean contains(int toFind) {
            for (int i = 0; i < usedSize; i++) { //遍历数组
                if(elem[i] == toFind);
                return true;
            }
            return false;
        }

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

在上一步的基础上，返回数组下标即可。

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

5. 获取 pos 位置的元素

判断pos位置我们需要注意一个关键点：pos下标位置是否合法

public int getPos(int pos) {
    if(pos < 0 || pos > usedSize){
        System.out.println("位置不合法");
        return -1;
    }
    return this.elem[pos];
}

6. 给 pos 位置的元素设为 value

依然要判断位置是否合法

public void setPos(int pos, int value) {
    if(pos < 0 || pos > usedSize){
        System.out.println("位置不合法");
       }
    this.elem[pos] = value;
}

7. 删除第一次出现的关键字key

在删除顺序表中的元素也分为两种情况：

1. 在顺序表的表尾删除元素

这种情况比较简单，我们直接删除表尾元素即可

2. 在顺序表中间删除元素

在顺序表的中间或者头部删除元素时，要注意将删除元素后面的元素全部向前移动一格。

public void remove(int toRemove) {
    int index = this.search(toRemove);
    if(index < 0 || index > usedSize){
        System.out.println("没找到要删除的元素");
     }
        for (int i = index; i < this.usedSize; i++) {
            this.elem[i] = this.elem[i+1];
        }
     this.usedSize--;
 }

8. 获取顺序表长度

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

9. 清空顺序表

清空顺序表只要将长度置空即可。

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

三、顺序表的优点和缺点

顺序表的优点是可以对给定的数据元素进行随机存取，时间复杂度为O(1)。

缺点是1. 顺序表中间/头部的插入删除，时间复杂度为O(N) 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。