1.什么是順序表

在程式中，經常需要將一組（通常是同為某個型別的）資料元素作為整體管理和使用，需要創建這種元素組，用變數記錄它們，傳進傳出函式等，一組資料中包含的元素個數可能發生變化（可以增加或洗掉元素），

對于這種需求，最簡單的解決方案便是將這樣一組元素看成一個序列，用元素在序列里的位置和順序，表示實際應用中的某種有意義的資訊，或者表示資料之間的某種關系，

這樣的一組序列元素的組織形式，我們可以將其抽象為線性表，一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關系，線性表是最基本的資料結構之一，在實際程式中應用非常廣泛，它還經常被用作更復雜的資料結構的實作基礎，

順序表是建立在陣列的基礎上的，我們需要在陣列的基礎上實作它的特定API功能，具體有什么功能以下

2.順序表的基本功能和結構

public class SequenceList<T> implements Iterable<T> {

    //存盤元素的資料
    private T[] arr;
    //記錄當前順序表中的元素個數
    private int N;

    //構造方法
    public SequenceList(int capacity) {
        this.arr= (T[]) new Object[capacity];
        this.N=0;
    }

決議：首先我們需要一個底層的arr陣列來存盤元素，這里的T指的是泛型，因為我們還沒確定放入的元素型別，有可能放int，String等等，所以先用泛型表示，不明白泛型的可以了解了解，其次用一個N來統計順序表中的元素個數，在構造方法中，capacity表示我們創建時arr的初始長度，因為泛型是無法直接實體化的，這里我們可以new一個Object陣列，因為Object是任何類的父類，所以T為任何型別我們都可以將Object強轉為我們需要的陣列，N剛開始為0即可，

下面是順序表需要實作的基本功能

public boolean isEmpty()	判斷線性表是否為空
public T get(int i)	獲取指定位置的元素
public void add(T t)	向線性表中添加元素t
public void insert(int i,T t)	在i元素處插入元素t
public T remove(int i)	洗掉指定位置i處的元素,并回傳該元素
public int indexOf(T t)	查找t第一次出現的位置
public void reSize(int newLength)	手動實作擴容功能

3.順序表基本功能的實作和決議

1.判斷線性表是否為空

//將一個線性表置為空表
    public void clear(){
        this.N=0;
    }
    //判斷當前線性表是否為空表
    public boolean isEmpty(){
        return N==0;
    }

決議：判斷線性表是否為空，我們只需要回傳N是否等于0即可，

2.獲取指定位置的元素

    //獲取指定位置的元素
    public  T get(int i){
        return arr[i];
    }

決議：陣列可以直接索引對應位置的元素

3.向線性表表添加元素

//向線性表中添加元素t
    public void add(T t){
        if(N== arr.length){
            reSize(2*N);
        }
        arr[N++]=t;
    }

決議：添加時，我們首先判斷陣列arr是否已經裝滿，如果滿了會先呼叫我們的擴容方法增加陣列長度，在后面會詳細決議，然后arr[N]這個位置加入元素即可，然后N會自增1，表示元素個數多了一個，

4.在位置i處插入元素

//在i元素處插入元素t
    public void insert(int i,T t){
        if(N== arr.length){
            reSize(2*N);
        }
        //把i元素開始后面的元素都向后移一位
        for(int j=N-1;j>=i;j--){
            arr[j+1]=arr[j];
        }
        N++;
        arr[i]=t;
    }

決議：插入元素我們仍然需要判斷是否需要對陣列進行擴容，然后我們需要通過回圈將i位置后的元素都向后移一個位置，最后將t放入arr【i】位置即可，別忘記N也需要加1，

4.洗掉指定位置的元素，并回傳該元素

//洗掉指定位置i處的元素,并回傳該元素
    public T remove(int i){
        if(N<arr.length/4){
            reSize(N/2);
        }
        T t=arr[i];
        for(int j=i;j<N;j++){
            arr[j]=arr[j+1];
        }
        N--;
        return t;
    }

決議：在這里我們也呼叫了擴容方法，但這里其實我們是判斷陣列是否過長，當我們的存盤元素的個數小于陣列長度的1/4，我們最好將陣列長度縮小一半，以防止對記憶體的浪費，這里我們先將i處的元素用一個變數t保存，然后將i處后的元素依次向前移動一位，然后讓N減1，最后回傳變數t即可，

5.查找t第一次出現的位置

public int indexOf(T t){
        for (int i = 0; i < N; i++) {
            if(arr[i]==t) return i;
        }
        return -1;
    }

決議：這里我們直接使用暴力遍歷查找位置，當然有很多更好的查找演算法可以實作，比如二分查找等等，元素不多的情況下使用哪種都可以，如果沒查詢到我們回傳一個-1表示該表中沒有需要查詢的t元素，

6.手動擴容方法

 //手寫擴容方法
    public void reSize(int newLength){
        T[] a=arr;
        T[] list = (T[]) new Object[N*2];
        for (int i = 0; i < arr.length; i++) {
            list[i]=a[i];
        }
        arr=list;
    }

決議：擴容方法的實作其實非常簡單，就是判斷直接生成一個長度為原陣列兩倍的陣列，并把舊陣列的元素遍歷進新陣列，然后將新陣列賦值給就陣列即可，之所以要會手動擴容，因為java中的集合類ArrayList就有自動擴容的功能，它的功能與邏輯結構類似我們的順序表，懂得手動擴容使我們更容易閱讀ArrayList的原始碼，更好的理解和掌握它，

總結：順序表是非常簡單且入門的一種資料結構，他與我們的陣列幾乎一致，但越是簡單的東西越不能大意，我們需要做到可以熟練的手動寫成它的各種功能，達到信手拈來的地步，基礎學好才更易于我們學習后面更復雜的資料結構，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/325564.html

標籤：java

上一篇：自己開發的音樂視頻網站

下一篇：每次另一個行程更新檔案時如何從檔案中讀取

Java資料結構————順序表（增刪改查詳細實作）