Java數據結構順序表用法詳解
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。
5.刪除指定位置的元素,並返回該元素
//刪除指定位置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即可。
6.查找t第一次出現的位置
public int indexOf(T t){ for (int i = 0; i < N; i++) { if(arr[i]==t) return i; } return -1; }
解析:這裡我們直接使用暴力遍歷查找位置,當然有很多更好的查找算法可以實現,比如二分查找等等,元素不多的情況下使用哪種都可以。如果沒查詢到我們返回一個-1表示該表中沒有需要查詢的t元素。
7.手動擴容方法
//手寫擴容方法 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的源碼,更好的理解和掌握它。
總結:順序表是非常簡單且入門的一種數據結構,他與我們的數組幾乎一致,但越是簡單的東西越不能大意,我們需要做到可以熟練的手動寫成它的各種功能,達到信手拈來的地步。基礎學好才更易於我們學習後面更復雜的數據結構。
到此這篇關於Java數據結構順序表用法詳解的文章就介紹到這瞭,更多相關Java 順序表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java 順序表專題解讀
- Java List接口的集合使用詳解
- Java 自定義動態數組方式
- Java ArrayList與LinkedList使用方法詳解
- Java中ArrayList與順序表的概念與使用實例