Java線性表的順序表示及實現

2022-07-03 14:00:11

前言

在之前對順序表使用C語言進行了簡單的實現：C語言線性表順序表示及實現

當時使用C語言進行實現是因為學校的教材使用的是C語言來進行實現，在後來的學習中，Java成為了我的主語言，使用不同的語言對順序表來進行實現也可以加深我對語言的理解和應用。

一、什麼是順序表？

順序表是在計算機記憶體中以陣列的形式儲存的線性表，線性表的順序儲存是指用一組地址連續的儲存單元依次儲存線性表中的各個元素、使得線性表中在邏輯結構上相鄰的資料元素儲存在相鄰的物理儲存單元中，即通過資料元素物理儲存的相鄰關係來反映資料元素之間邏輯上的相鄰關係，採用順序儲存結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機記憶體中一組地址連續的儲存單元中。

二、順序表的實現

在順序表的定義中可以看到，順序表是一組地址連續的儲存單元，本質上是一種增加了一些基本操作功能的陣列

在本文中要實現的功能有：

獲取順序表中的元素個數
獲取順序表當前的容量
順序表是否為空
在指定索引位置新增元素
在順序表末尾新增元素
在順序表頭部新增元素
獲取指定索引位置的元素
獲取順序表第一個元素
獲取順序表最後一個元素
修改指定索引位置的元素
判斷順序表中是否包含指定元素
獲取順序表中指定元素的索引
刪除指定索引位置的元素
刪除並返回順序表第一個元素
刪除並返回順序表最後一個元素
刪除順序表中的指定元素
對順序表進行動態的擴容和縮容

1. 準備工作

實現工具	版本
IntelliJ IDEA	2021.3
JDK	1.8

在 IntelliJ IDEA 中新建普通的Java專案即可

在新建好Java工程後，我們建立自己的順序表類，在這裡我對當前類命名為Array，在這裡實現泛型，同時Array類中需要有兩個成員屬性：

存放資料的陣列：data，型別為泛型陣列
當前順序表中元素的數量：size，型別為int

兩個成員屬性的存取許可權都應該為private，使用者不能夠直接進行修改，只能通過對應的getter方法進行獲取。在成員屬性中我們將存放資料的陣列和順序表中的元素數量只是進行了宣告，但是並未進行初始化，因此==初始化的過程就需要在構造方法中進行==

有參構造：在進行有參構造時，我們只需要指定傳入的引數為一個int型別的資料capacity，代表順序表的初始容量，因此對data進行初始化泛型陣列即可。同時當前順序表中是沒有元素的，代表順序表中的元素個數size的初始值為0。
無參構造：在使用者沒有指定了順序表的初始容量時我們可以自定義初始容量為10，僅需要通過this(10)進行有參構造的呼叫即可。

注意： 在Java中不能直接初始化泛型陣列，需要先宣告Object型別的陣列後通過強制型別轉換的方式將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);
    }
}

使用泛型的原因：使用泛型後可以將當前順序表中儲存物件，如果不使用泛型的話只能使用自己指定型別的資料，擴充套件性不強。因此使用泛型後可以將當前順序表的使用擴充套件到所有類物件，只需要在建立時指定相應的物件即可。

2. 獲取順序表的元素個數

    /**
     * 獲取陣列中的元素個數
     *
     * @return 陣列當前的元素個數
     */
    public int getSize() {
        return size;
    }

對於獲取當前順序表中的元素個數來說，因為我們定義的初始成員變數size代表的含義就是當前順序表的元素個數，但是size變數的本質為當前順序表的指標，指向順序表最後一個元素的下一個位置 （元素的索引從0開始，最後一個元素的索引值比元素個數值小 1），不能直接進行修改，因此要想獲取需要通過size元素的getter方法

同樣地，對於獲取順序表的元素個數只需要將size返回即可

3. 獲取順序表當前的容量

    /**
     * 獲取陣列當前容量
     *
     * @return 陣列當前容量
     */
    public int getCapacity() {
        return data.length;
    }

在對順序表進行宣告的時候，就已經將使用者傳來的或者預設的初始容量capacity作為陣列的大小對data泛型陣列進行了初始化，因此當前data的length屬性就是傳來的capacity，（或者在後面進行動態擴容或縮容時，data.length是一直不會改變的，改變的只有size）因此獲取順序表當前的容量將data.length返回即可

4. 順序表是否為空

    /**
     * 判斷陣列是否為空
     *
     * @return 陣列是否為空
     */
    public boolean isEmpty() {
        return size == 0;
    }

我們知道size代表的是順序表中的元素個數，因此要判斷當前順序表是否為空僅需要將size是否等於0進行返回即可

5. 在指定索引位置新增元素

    /**
     * 向陣列中索引為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++;
    }

當向順序表中指定索引位置新增元素時要考慮以下幾個問題：

當前順序表中是否還有容量？
新增的元素索引值是否越界？

對於第一個問題來說，當順序表已滿沒有容量時，再進行新增元素時需要進行動態的擴容，resize方法的作用就是對陣列進行動態的擴容以及縮容，對於resize方法的實現我們放到後面進行具體的講解，在這裡我們知道如果當前順序表容量已滿，將順序表容量擴大為當前順序表容量的二倍

第二個問題的出現情況只有兩種，索引小於0或索引超過了當前順序表中的元素個數時，丟擲執行時異常即可

在索引沒有問題後，新增元素的過程如下圖所示：

要先將要新增的索引位置後的所有元素依次向後移動一位，在移動完成後將當前索引位置的元素使用要進行新增的元素對當前位置的元素進行覆蓋即可，同時新增完元素後將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 = %dn", 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<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);
    }

    /**
     * 獲取陣列中的元素個數
     *
     * @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 = %dn", 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));
    }

}

到此這篇關於Java線性表的順序表示及實現的文章就介紹到這了,更多相關Java線性表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！