Kaedah perwakilan dan pelaksanaan jujukan jadual linear Java

1. Apakah itu senarai jujukan?

Jadual jujukan ialah jadual linear yang disimpan dalam bentuk tatasusunan dalam ingatan komputer Storan jujukan jadual linear bermaksud menggunakan set unit storan dengan alamat berturut-turut untuk menyimpan setiap elemen secara berjujukan. dalam jadual linear, supaya elemen data bersebelahan secara logik dalam jadual linear disimpan dalam unit storan fizikal bersebelahan , iaitu, hubungan bersebelahan logik antara elemen data dicerminkan melalui hubungan bersebelahan penyimpanan fizikal elemen data, menggunakan susunan Senarai linear struktur storan selalunya dipanggil senarai berjujukan. Jadual jujukan menyimpan nod dalam jadual secara berurutan dalam set unit storan dengan alamat berturut-turut dalam memori komputer .

2. Pelaksanaan jadual jujukan

Seperti yang anda boleh lihat daripada takrif jadual jujukan, jadual jujukan ialah kumpulan unit storan dengan alamat berturut-turut , iaitu pada asasnya Tatasusunan dengan beberapa fungsi operasi asas ditambah

Fungsi yang akan dilaksanakan dalam artikel ini ialah:

• Dapatkan bilangan elemen dalam jadual jujukan

• Dapatkan kapasiti semasa jadual jujukan

• Sama ada jadual jujukan kosong

• pada kedudukan indeks yang ditentukan Tambah elemen

• Tambah elemen di penghujung jadual jujukan

• Tambah elemen di bahagian kepala jadual jujukan

• Dapatkan elemen pada kedudukan indeks yang ditentukan

• Dapatkan elemen pertama jadual jujukan

• Dapatkan elemen terakhir jadual jujukan

• Ubah suai elemen pada kedudukan indeks yang ditentukan

• Nilai sama ada elemen yang dinyatakan adalah disertakan dalam jadual jujukan

• Dapatkan elemen yang ditentukan dalam jadual jujukan Indeks

• memadamkan elemen pada kedudukan indeks yang ditentukan

• memadam dan mengembalikan elemen pertama jadual jujukan

• Padam dan kembalikan elemen terakhir jadual jujukan

• Padamkan elemen yang ditentukan dalam jadual jujukan

• Kembang dan kembangkan jadual jujukan secara dinamik

Penyediaan

实现工具	版本
IntelliJ IDEA	2021.3
JDK	1.8

Hanya buat projek Java biasa baharu dalam IntelliJ IDEA

Selepas mencipta projek Java baharu, kami mencipta sendiri Kelas jadual jujukan, di sini saya menamakan kelas semasa Array, melaksanakan generik di sini dan kelas Array perlu mempunyai dua atribut ahli:

• Array untuk menyimpan data :data, jenis ialah tatasusunan generik

• Bilangan elemen dalam jadual jujukan semasa:size, taip ialah int

Hak akses kedua-dua atribut ahli hendaklah private Pengguna tidak boleh mengubah suainya secara langsung dan hanya boleh mendapatkannya melalui kaedah getter yang sepadan. Dalam atribut ahli, bilangan elemen dalam jadual tatasusunan dan jujukan di mana kami akan menyimpan data hanya diisytiharkan, tetapi tidak dimulakan , jadi proses permulaan == perlu dilakukan dalam pembina ==

• Pembinaan dengan parameter: Apabila melakukan pembinaan dengan parameter, kami hanya perlu menentukan bahawa parameter masuk ialah data jenis intcapacity, yang mewakili Kapasiti awal jadual jujukan ialah , jadi hanya mulakan tatasusunan generik kepada data. Pada masa yang sama, tiada unsur dalam jadual jujukan semasa, yang bermaksud nilai awal bilangan elemen size dalam jadual jujukan ialah 0.

• Pembinaan tanpa parameter: Apabila pengguna tidak menyatakan kapasiti awal jadual jujukan, kami boleh menyesuaikan kapasiti awal kepada 10, dan hanya perlu lulus this(10) untuk mengkonfigurasinya Hanya panggil pembina parameter.

Nota: tidak boleh dimulakan secara langsung dalam Java Anda perlu mengisytiharkan tatasusunan jenis Object dahulu dan kemudian gunakan untuk memaksa penukaran jenis<.> Tukar tatasusunan jenis kepada tatasusunan generik Object

package net.csdn.array;
/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class Array<E> {
	/**
	 * 存放数据的数组
	 */
	private E[] data;
    /**
     * 数组中元素的数量
     */
    private int size;
	
	/**
     * 构造函数，传入数组的容量capacity构造数组
     *
     * @param capacity 初始数组大小
     */
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无参构造函数，默认数组大小为0
     */
    public Array() {
        this(10);
    }
}

Sebab menggunakan generik : Selepas menggunakan generik, anda boleh menyimpan objek dalam jadual jujukan semasa gunakan generik Jika anda menaip, anda hanya boleh menggunakan data jenis yang anda tentukan dan skalabilitinya tidak kukuh. Oleh itu, selepas menggunakan generik, anda boleh melanjutkan penggunaan jadual jujukan semasa kepada semua objek kelas , dan anda hanya perlu menentukan objek yang sepadan semasa menciptanya.

2. Dapatkan bilangan elemen dalam jadual jujukan

    /**
     * 获取数组中的元素个数
     *
     * @return 数组当前的元素个数
     */
    public int getSize() {
        return size;
    }

Untuk mendapatkan bilangan elemen dalam jadual jujukan semasa, kerana pembolehubah ahli awal yang kami takrifkan

bermaksud: 🎜> Bilangan elemen dalam jadual jujukan semasa size, tetapi intipati pembolehubah ialah penunjuk jadual jujukan semasa, menunjuk ke kedudukan seterusnya unsur terakhir dalam jadual jujukan size (indeks elemen bermula dari 0 , nilai indeks elemen terakhir ialah 1 kurang daripada nilai elemen, dan tidak boleh diubah suai secara langsung, jadi untuk mendapatkannya, anda perlu menggunakan kaedah bagi elemen sizegetter Begitu juga, untuk mendapatkan elemen senarai jujukan Nombor hanya perlu dikembalikan

size3 Dapatkan kapasiti semasa jadual jujukan

    /**
     * 获取数组当前容量
     *
     * @return 数组当前容量
     */
    public int getCapacity() {
        return data.length;
    }

Apabila mengisytiharkan jadual jujukan, pengguna melepasinya atau lalai Kapasiti awal

digunakan sebagai saiz tatasusunan untuk memulakan tatasusunan generik

, jadi atribut capacity bagi semasa data ialah data yang diluluskan, (atau apabila mengembang atau mengecilkan kapasiti secara dinamik kemudiannya) , length tidak akan pernah berubah, hanya capacity berubah) Oleh itu, mendapatkan kapasiti semasa jadual jujukan akan kembali data.lengthsizedata.length4. Sama ada jadual jujukan kosong

    /**
     * 判断数组是否为空
     *
     * @return 数组是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

Kami tahu bahawa

mewakili bilangan elemen dalam jadual jujukan, jadi untuk menentukan sama ada jadual jujukan semasa kosong, kami hanya perlu mengembalikan sama ada

bersamaan dengan 0 sizesize5 Dalam penambahan elemen yang ditentukan pada kedudukan indeks

    /**
     * 向数组中索引为index位置添加元素e
     *
     * @param index 索引位置
     * @param e 元素e
     */
    public void add(int index, E e) {
        // 判断数组空间是否已满
        if (size == data.length) {
            // 对数组进行扩容
            resize(2 * data.length);
        }
        // 越界判断
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

Isu berikut harus dipertimbangkan apabila menambah elemen pada kedudukan indeks yang ditentukan dalam jadual jujukan. :

• Adakah masih terdapat kapasiti dalam jadual jujukan semasa?

• Adakah nilai indeks unsur tambahan di luar had?

Untuk soalan pertama, apabila jadual jujukan penuh dan tidak mempunyai kapasiti, pengembangan dinamik diperlukan apabila menambah elemen Fungsi kaedah

ialah

Kembangkan dan kecilkan tatasusunan secara dinamik resize Kami akan menerangkan pelaksanaan kaedah secara terperinci kemudian di sini kami tahu bahawa jika kapasiti jadual jujukan semasa penuh, kapasiti jadual jujukan akan dikembangkan kepada Dua kali ganda kapasiti. daripada jadual jujukan semasa resize Terdapat hanya dua situasi di mana masalah kedua berlaku

Apabila indeks kurang daripada 0 atau indeks melebihi bilangan elemen dalam jadual jujukan semasa

, run akan dilemparkan. Pengecualian boleh dibuat

Selepas tiada masalah dengan indeks, proses menambah elemen adalah seperti yang ditunjukkan dalam rajah di bawah:

 要先将要添加的索引位置后的所有元素依次向后移动一位，在移动完成后将当前索引位置的元素使用要进行添加的元素对当前位置的元素进行覆盖即可，同时添加完元素后将size++，维护指针变量

6. 在顺序表末尾添加元素

    /**
     * 在数组末尾添加一个元素
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        add(size, e);
    }

在末尾添加元素可以对之前写好的向指定索引位置添加元素的代码进行复用，同时在add方法中进行了校验，因此对于扩容以及索引都问题都无需我们进行考虑，将 索引位置的参数赋值为当前最后一个元素的下一个位置size 后直接调用即可。

7. 在顺序表头部添加元素

    /**
     * 在数组的头部添加元素e
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }

在顺序表的头部添加元素也是同样的道理，对指定索引位置插入元素进行复用即可，在此不进行赘述。

8. 获取指定索引位置的元素

    /**
     * 获取索引为index位置的元素
     *
     * @param index 索引位置
     * @return 索引为index位置的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return data[index];
    }

获取指定索引位置的元素与之前在指定索引位置插入元素的思路大体一致，但是要更简单一些，无需考虑顺序表扩容以及缩容的问题，仅需要考虑传入的索引值是否合法，如果传入的索引值合法则直接将对应位置的元素进行返回即可。

9. 获取顺序表第一个元素

    /**
     * 获取数组中第一个元素
     *
     * @return 数组中第一个元素
     */
    public E getFirst() {
        return get(0);
    }

在实现了获取指定索引位置的元素后，获取顺序表的第一个元素同样是对get方法的复用，将0做为索引值进行参数传递即可。

10. 获取顺序表最后一个元素

    /**
     * 获取数组中最后一个元素
     *
     * @return 数组中最后一个元素
     */
    public E getLast() {
        return get(size - 1);
    }

获取顺序表最后一个元素也是对get方法的复用，在此不进行赘述

11. 修改指定索引位置的元素

    /**
     * 设置索引为index位置的元素值为e
     *
     * @param index 索引位置
     * @param e 要进行替换的元素值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        data[index] = e;
    }

在之前获取指定索引位置的元素时，先判断索引是否合法，如果合法将对应位置的元素进行返回。同理，先判断索引位置是否合法，如果合法就将当前位置的元素使用我们接收到的元素e进行替换。

12. 判断顺序表中是否包含指定元素

    /**
     * 判断数组中是否存在元素e
     *
     * @param e 元素e
     * @return 是否存在元素e
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

对于判断顺序表中是否存在指定元素来说，对顺序表进行线性查找，如果找到了相应的数据，就返回true，如果在对顺序表遍历结束后仍然没有找到指定元素，说明当前顺序表中不存在指定元素，返回false

注意：在这里因为是对象的比较，使用equals方法进行比较，如果是基本数据类型（如int，double等）的比较就要使用==来进行比较

13. 获取顺序表中指定元素的索引

    /**
     * 查找数组中元素e的索引，如果不存在返回 -1
     *
     * @param e 元素e
     * @return 元素e在数组中的索引
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

获取指定元素的索引同样使用线性查找法，使用equals进行比较，如果找到相同的元素则返回对应的索引值，如果遍历完顺序表后仍然没有找到指定元素则返回-1，说明当前元素不存在。

14. 删除指定索引位置的元素

    /**
     * 删除索引位置为 index 的元素并返回被删除的元素
     *
     * @param index 删除元素的索引
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 先将返回值进行存储
        E res = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;
        // 如果当前数组中的元素不足数组容量的一半
        if (size < data.length / 2) {
            // 重新分配空间
            resize(data.length / 2);
        }
        return res;
    }

在之前进行元素的添加时要考虑顺序表是否还有容量，在删除元素时不需要考虑是否还有容量，但是也要考虑相应的有关于数组缩容问题。因此要考虑以下问题：

• 删除当前元素后，顺序表中的元素个数是否不足数组容量的一半？

• 删除指定索引的元素时，传来的索引值是否合法？

对于第一个问题的解决方法为在删除元素后，对当前顺序表的元素个数与数组的容量的一半进行比较，如果发现当前元素个数小于数组容量的一半时，我们可以继续调用resize方法重新分配数组的容量（resize方法在之后会详细解释），当前的实现结果就是将数组的容量缩容至原数组都一半，对于内存的节省来说更有好处。

第二个问题解决方式与之前处理一样，查看索引值是否小于0以及是否大于等于当前顺序表都元素个数

删除元素的本质也是将当前索引值的后一个元素开始，依次向前移动，覆盖掉前一个元素，最后再将size--，维护指针，删除结束后将临时存储的被删除的元素返回即可。

删除元素过程如下图所示： 

注意：顺序表的删除本质上是用后一个元素将前一个元素依次覆盖，移动了size指针后此时指针指向的元素仍然为原本顺序表中的最后一个元素，因为在用户的实际操作中，size指向的元素无法被访问到，所以并没有什么影响。但是我们在这里使用了泛型，在Java的GC（垃圾回收机制）中因为此时顺序表的最后一个元素仍然被size指向引用，无法被回收，因此在这里手动执行data[size] = null;将当前的引用回收。

15. 删除并返回顺序表第一个元素

    /**
     * 删除并返回数组的第一个元素
     *
     * @return 数组的第一个元素
     */
    public E removeFirst() {
        return remove(0);
    }

与之前的思路一致，在有了删除指定索引位置的元素方法后，删除并返回顺序表第一个元素也是对刚才实现的remove方法进行复用，在此不做赘述。

16. 删除并返回顺序表最后一个元素

    /**
     * 删除并返回数组中的最后一个元素
     *
     * @return 数组中的最后一个元素
     */
    public E removeLast() {
        return  remove(size - 1);
    }

删除顺序表中最后一个元素同样是对remove方法的复用，在此也不多做赘述。

17. 删除顺序表中的指定元素

    /**
     * 从数组中删除元素e
     *
     * @param e 数组中被删除的元素
     * @return 是否删除成功
     */
    public boolean removeElement(E e) {
       int index = find(e);
       if (index == -1) {
           return false;
       }
       remove(index);
       return true;
    }

删除顺序表中指定的元素本质上是对之前实现的获取顺序表中指定元素的索引方法和删除指定索引位置元素方法的复用，首先通过find方法获取到要删除元素的索引，接着对索引进行判断，查看当前元素是否存在，如果当前元素存在则将获取到的索引值作为remove方法的参数传递，将当前索引位置的元素删除即可。

18. 对顺序表进行动态的扩容和缩容

    /**
     * 对数组进行扩容
     *
     * @param newCapacity 扩容后数组的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

在之前向顺序表中添加元素以及删除顺序表中的元素都涉及到了扩容以及缩容的过程，其实对于扩容以及缩容来说区别只体现在了传递来的参数与原数组容量大小的差别，扩容与缩容的思路都是声明一个新的数组，初始容量的大小为传递来的参数，接着遍历原来的数组，将每一个元素依次填充到新的数组中，之后再将data对象的引用指向新的数组newData即可。

三、运行结果

在进行结果测试前，为了方便于观察，在这里我重写了Array类的toString方法

@Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

四、总结

以上便是Java语言对线性表的顺序表示和实现，和以前使用C语言来写顺序表最大的感受就是曾经觉得很难写、很费脑的代码再次实现时感觉变得很容易了，同时对于很多的方法也有了复用的思想，对线性表的理解更加深刻。高兴于自己成长的同时也更加深刻意识到以后的路会更加的艰难，希望自己可以在未来的道路上戒骄戒躁、稳扎稳打，哪怕再困难，也不会放弃！

源码

以下是源代码

1. Array类源代码

package net.csdn.array;
/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class Array {
    private E[] data;
    /**
     * 数组中元素的数量
     */
    private int size;

    /**
     * 构造函数，传入数组的容量capacity构造数组
     *
     * @param capacity 初始数组大小
     */
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无参构造函数，默认数组大小为0
     */
    public Array() {
        this(10);
    }

    /**
     * 获取数组中的元素个数
     *
     * @return 数组当前的元素个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 获取数组当前容量
     *
     * @return 数组当前容量
     */
    public int getCapacity() {
        return data.length;
    }
    /**
     * 判断数组是否为空
     *
     * @return 数组是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在数组末尾添加一个元素
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        add(size, e);
    }
    /**
     * 在数组的头部添加元素e
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 向数组中索引为index位置添加元素e
     *
     * @param index 索引位置
     * @param e 元素e
     */
    public void add(int index, E e) {
        // 判断数组空间是否已满
        if (size == data.length) {
            // 对数组进行扩容
            resize(2 * data.length);
        }
        // 越界判断
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }
    /**
     * 获取索引为index位置的元素
     *
     * @param index 索引位置
     * @return 索引为index位置的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return data[index];
    }
    /**
     * 获取数组中第一个元素
     *
     * @return 数组中第一个元素
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 获取数组中最后一个元素
     *
     * @return 数组中最后一个元素
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 设置索引为index位置的元素值为e
     *
     * @param index 索引位置
     * @param e 要进行替换的元素值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        data[index] = e;
    }
    /**
     * 判断数组中是否存在元素e
     *
     * @param e 元素e
     * @return 是否存在元素e
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找数组中元素e的索引，如果不存在返回 -1
     *
     * @param e 元素e
     * @return 元素e在数组中的索引
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除索引位置为 index 的元素并返回被删除的元素
     *
     * @param index 删除元素的索引
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 先将返回值进行存储
        E res = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;
        // 如果当前数组中的元素不足数组容量的一半
        if (size < data.length / 2) {
            // 重新分配空间
            resize(data.length / 2);
        }
        return res;
    }

    /**
     * 删除并返回数组的第一个元素
     *
     * @return 数组的第一个元素
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 删除并返回数组中的最后一个元素
     *
     * @return 数组中的最后一个元素
     */
    public E removeLast() {
        return  remove(size - 1);
    }
    /**
     * 从数组中删除元素e
     *
     * @param e 数组中被删除的元素
     * @return 是否删除成功
     */
    public boolean removeElement(E e) {
       int index = find(e);
       if (index == -1) {
           return false;
       }
       remove(index);
       return true;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }
    /**
     * 对数组进行扩容
     *
     * @param newCapacity 扩容后数组的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }
}

2. 测试类源代码

package net.csdn.array;

/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class ArrayMain {
    public static void main(String[] args) {
        System.out.println("声明新的顺序表，初始容量为10：");
        Array<Integer> array = new Array<>(10);
        for (int i = 0; i < 10; i++) {
            array.addLast(i);
        }
        System.out.println(array + "\n");

        System.out.println("向索引为 1 的位置添加元素 100：");
        array.add(1, 100);
        System.out.println(array + "\n");

        System.out.println("在顺序表的头部添加 -1：");
        array.addFirst(-1);
        System.out.println(array + "\n");

        System.out.println("在顺序表的尾部添加 101：");
        array.addLast(101);
        System.out.println(array + "\n");

        System.out.println("移除索引位置为 2 的元素：");
        array.remove(2);
        System.out.println(array + "\n");

        System.out.println("移除顺序表中的元素 4：");
        array.removeElement(4);
        System.out.println(array + "\n");

        System.out.println("移除顺序表中的第一个元素：");
        array.removeFirst();
        System.out.println(array + "\n");

        System.out.println("移除顺序表中的最后一个元素：");
        array.removeLast();
        System.out.println(array + "\n");

        System.out.println("元素7的索引位置为：" + array.find(7));
        System.out.println("数组中是否包含元素4：" + array.contains(4));
    }

}

Atas ialah kandungan terperinci Kaedah perwakilan dan pelaksanaan jujukan jadual linear Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!