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

Posted on by

前言

在之前對順序表使用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 = %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<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 = %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));
    }

}

到此這篇關於Java線性表的順序表示及實現的文章就介紹到這瞭,更多相關Java線性表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：