Java 顺序表

时间:2022-05-28 来自爪哇的bean 人气:0

一、什么是线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表*（linear list）*是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。常见的线性表有顺序表，链表，栈，队列，字符串等

注意：这里说的线性表都指的是逻辑结构，也就是他们的逻辑结构是线性的，但物理结构却不一定是线性的。

在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制

二、顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中

顺序表可以分为以下两类：

静态顺序表：通过定长数组实现
动态顺序表：数组长度可动态增长

静态顺序表比较死板，如果数组长度太小，担心后面数据存不下，太大，又会有空间浪费.

所以我们一般都用动态增长的顺序表，按需所取.

三、手撕顺序表

在学习数据结构的过程中，我们不仅要学会如何用数据结构，懂得它的理论部分，更要亲自动手去实践，将数据结构实现一遍，这样的话理解会更深刻

顺序表中我们如果只是单纯拿一个数组去用的话就会出现：顺序表中到底有多少有效数据，满了还是没满等问题，所以我们在实现顺序表的时候都还会再加一个size(有效数据个数)属性（顺序表的容量可以通过data.length获得）

属性定义

public class MyArrayList {
    public int[] data;    // 存储数据
    public int size;    // 有效数据个数
}

构造方法

public MyArrayList() {
    this.data = new int[10];   // 后面不够再增容
    this.size = 0;    // 初始无有效数据，size 为0
}

接口实现

对于顺序表我们一般都会有以下接口需要去实现：

// 打印顺序表
public void display();
// 在 pos 位置增加元素
public void add(int pos, int num);
// 判断顺序表中是否包含某个元素
public boolean contains(int num);
// 查找某个元素所在位置
public int search(int key);
// 获取 pos 位置的元素
public int getPos(int pos);
// 将 pos 位置的元素值设为 value
public void setPos(int pos, int value);
//删除第一次出现的关键字key
public void remove(int key);
// 获取顺序表长度
public int size();
// 清空顺序表
public void clear();

在实现这些接口的过程中，凡是涉及到数组下标的，我们都要进行下标合法性的检验，并且要注意用size，还是data.length

确保顺序表空间

在对顺序表增加元素的时候，我们一定要确保顺序表有足够的空间去增加元素，否则就会导致数组下标越界等情况发生

private void ensureCapacity() {
    if (this.size == this.data.length) {
        // 说明满了，该扩容了
        this.data = Arrays.copyOf(this.data, 2 * this.data.length);
    }
}

增加元素

往顺序表中增加元素的时候要注意可以在size位置去加元素（相当于尾插），同时也要确保顺序表有空间足够插入，在移动元素的时候要注意边界情况（下标越界，移动元素过多等），也别忘了size++

public void add(int pos, int num) {
    if (pos < 0 || pos > this.size) {    // 检验下表合法性
        throw new RuntimeException("ArrayIndexOutOfBoundsException : " + pos);
    }
    ensureCapacity();
    for (int i = this.size; i > pos; i--) {
        this.data[i] = this.data[i - 1];
    }
    this.data[pos] = num;
    this.size++;
}

打印顺序表

注意这里只打印有效数据

public String printMyArrayList() {
    String str = "[";
    for (int i = 0; i < this.size - 1; i++) {   // for循环中的右边界应该用size而不用data.length
        str += this.data[i] + ", ";
    }
    str += this.data[this.size - 1];
    str += "]";
    return str;
}

测试

对前面写的三个接口做测试

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        myArrayList.add(4, 2);
        myArrayList.add(0, 100);   // 头插
        myArrayList.add(2, 666);   // 中间插
        System.out.println(myArrayList.printMyArrayList());
    }
}

运行结果：

判断顺序表中是否包含某个元素

public boolean contains(int num) {
    for (int i = 0; i < this.size; i++) {
        if (this.data[i] == num) {
            return true;
        }
    }
    return false;
}

测试：

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        System.out.println(myArrayList.contains(3));
        System.out.println(myArrayList.contains(2));
        System.out.println(myArrayList.contains(0));
        System.out.println(myArrayList.contains(666));
    }
}

运行结果：

查找元素

查找顺序表中某个元素的位置（返回下标）

public int search(int key) {
    for (int i = 0; i < this.size; i++) {
        if (this.data[i] == key) {
            return i;
        }
    }
    return -1;    // 不存在这个元素，返回-1
}

测试：

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        System.out.println(myArrayList.search(0));
        System.out.println(myArrayList.search(3));
        System.out.println(myArrayList.search(666));
    }
}

获取 pos 位置的元素

注意：size位置为无效元素

public int getPos(int pos) {
    if (pos < 0 || pos >= this.size) {
        throw new RuntimeException("ArrayIndexOfBoundsException : " + pos);
    }
    return this.data[pos];
}

测试：

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        System.out.println(myArrayList.getPos(0));
        System.out.println(myArrayList.getPos(3));
        System.out.println(myArrayList.getPos(1));
        System.out.println(myArrayList.getPos(6));
    }
}

将 pos 位置的元素值设为 value

这里不涉及元素的移动

public void setPos(int pos, int value) {
    if (pos < 0 || pos >= this.size) {     // size位置为无效元素
        throw new RuntimeException("ArrayIndexOfBoundsException : " + pos);
    }
    this.data[pos] = value;
}

测试：

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        myArrayList.setPos(0, 666);
        myArrayList.setPos(3, 777);
        System.out.println(myArrayList.printMyArrayList());
    }
}

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

注意在删除的时候的数组边界以及改变size

public void remove(int key) {
    int pos = search(key);
    if (pos == -1) {
        return;        // 若是这个数字不存在，则返回
    }
    for (int i = pos; i < this.size - 1; i++) {
        this.data[i] = this.data[i + 1];      // 从后往前挪，直接将要删除的数字覆盖掉
    }
    this.size--;
}

获取顺序表长度

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

清空顺序表

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

删除所有的key

如果我们想要删除顺序表中所有的key，如何做？

法一：我们可以将第一次出现的key删除完之后再继续搜索若有，则删除，没有则删除完毕

public void removeAll(int key) {
    for (int i = 0; i < this.size; i++) {
        if (this.search(key) != -1) {
            remove(key);
        } else {
            return;
        }
    }
}

法二：我们可以转变以下思路，不直接删除key，而是重新创建一个数组，将源数组中不是key的值复制到新数组，再让原数组的引用指向新数组，间接完成删除操作

public void removeAllPlus(int key) {
    int[] newData = new int[this.data.length];    // 新数组长度应该和源数组长度相同
    int j = 0;
    for (int i = 0; i < this.size; i++) {
        if (this.data[i] != key) {
            newData[j] = this.data[i];
            j++;
        }
    }
    this.data = newData;
    this.size = j;
}

注意：在元素复制完之后要改变源数组的引用，并改变顺序表的size

法三：我们既然可以通过复制的方式实现间接删除操作，那么我们可以想着将原数组就当成目标数组，即两个指针，一个数组

public void removeAllPlusPlus(int key) {
    int dest = 0;
    for (int src = 0; src < this.size; src++) {
        if (this.data[src] != key) {
            this.data[dest] = this.data[src];
            dest++;
        }
    }
    this.size = dest;
}

加载全部内容