1.什么是順序表

在程序中，經(jīng)常需要將一組（通常是同為某個(gè)類(lèi)型的）數(shù)據(jù)元素作為整體管理和使用，需要?jiǎng)?chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化（可以增加或刪除元素）。

對(duì)于這種需求，最簡(jiǎn)單的解決方案便是將這樣一組元素看成一個(gè)序列，用元素在序列里的位置和順序，表示實(shí)際應(yīng)用中的某種有意義的信息，或者表示數(shù)據(jù)之間的某種關(guān)系。

這樣的一組序列元素的組織形式，我們可以將其抽象為線性表。一個(gè)線性表是某類(lèi)元素的一個(gè)集合，還記錄著元素之間的一種順序關(guān)系。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實(shí)際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)。

順序表是建立在數(shù)組的基礎(chǔ)上的，我們需要在數(shù)組的基礎(chǔ)上實(shí)現(xiàn)它的特定API功能，具體有什么功能以下

2.順序表的基本功能和結(jié)構(gòu)

public class SequenceList<T> implements Iterable<T> {
 
    //存儲(chǔ)元素的數(shù)據(jù)
    private T[] arr;
    //記錄當(dāng)前順序表中的元素個(gè)數(shù)
    private int N;
 
    //構(gòu)造方法
    public SequenceList(int capacity) {
        this.arr= (T[]) new Object[capacity];
        this.N=0;
    }

解析：首先我們需要一個(gè)底層的arr數(shù)組來(lái)存儲(chǔ)元素，這里的T指的是泛型，因?yàn)槲覀冞€沒(méi)確定放入的元素類(lèi)型，有可能放int，String等等，所以先用泛型表示，不明白泛型的可以了解了解。其次用一個(gè)N來(lái)統(tǒng)計(jì)順序表中的元素個(gè)數(shù)。在構(gòu)造方法中，capacity表示我們創(chuàng)建時(shí)arr的初始長(zhǎng)度，因?yàn)榉盒褪菬o(wú)法直接實(shí)例化的，這里我們可以new一個(gè)Object數(shù)組，因?yàn)镺bject是任何類(lèi)的父類(lèi)，所以T為任何類(lèi)型我們都可以將Object強(qiáng)轉(zhuǎn)為我們需要的數(shù)組，N剛開(kāi)始為0即可。

下面是順序表需要實(shí)現(xiàn)的基本功能

3.順序表基本功能的實(shí)現(xiàn)和解析

1.判斷線性表是否為空

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

解析：判斷線性表是否為空，我們只需要返回N是否等于0即可。

2.獲取指定位置的元素

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

解析：數(shù)組可以直接索引對(duì)應(yīng)位置的元素

3.向線性表表添加元素

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

解析：添加時(shí)，我們首先判斷數(shù)組arr是否已經(jīng)裝滿，如果滿了會(huì)先調(diào)用我們的擴(kuò)容方法增加數(shù)組長(zhǎng)度，在后面會(huì)詳細(xì)解析。然后arr[N]這個(gè)位置加入元素即可，然后N會(huì)自增1，表示元素個(gè)數(shù)多了一個(gè)。

4.在位置i處插入元素

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

解析：插入元素我們?nèi)匀恍枰袛嗍欠裥枰獙?duì)數(shù)組進(jìn)行擴(kuò)容，然后我們需要通過(guò)循環(huán)將i位置后的元素都向后移一個(gè)位置，最后將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;
    }

解析：在這里我們也調(diào)用了擴(kuò)容方法，但這里其實(shí)我們是判斷數(shù)組是否過(guò)長(zhǎng)，當(dāng)我們的存儲(chǔ)元素的個(gè)數(shù)小于數(shù)組長(zhǎng)度的1/4，我們最好將數(shù)組長(zhǎng)度縮小一半，以防止對(duì)內(nèi)存的浪費(fèi)。這里我們先將i處的元素用一個(gè)變量t保存。然后將i處后的元素依次向前移動(dòng)一位，然后讓N減1，最后返回變量t即可。

6.查找t第一次出現(xiàn)的位置

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

解析：這里我們直接使用暴力遍歷查找位置，當(dāng)然有很多更好的查找算法可以實(shí)現(xiàn)，比如二分查找等等，元素不多的情況下使用哪種都可以。如果沒(méi)查詢(xún)到我們返回一個(gè)-1表示該表中沒(méi)有需要查詢(xún)的t元素。

7.手動(dòng)擴(kuò)容方法

 //手寫(xiě)擴(kuò)容方法
    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;
    }

解析：擴(kuò)容方法的實(shí)現(xiàn)其實(shí)非常簡(jiǎn)單，就是判斷直接生成一個(gè)長(zhǎng)度為原數(shù)組兩倍的數(shù)組，并把舊數(shù)組的元素遍歷進(jìn)新數(shù)組，然后將新數(shù)組賦值給就數(shù)組即可。之所以要會(huì)手動(dòng)擴(kuò)容，因?yàn)閖ava中的集合類(lèi)ArrayList就有自動(dòng)擴(kuò)容的功能，它的功能與邏輯結(jié)構(gòu)類(lèi)似我們的順序表，懂得手動(dòng)擴(kuò)容使我們更容易閱讀ArrayList的源碼，更好的理解和掌握它。

總結(jié)：順序表是非常簡(jiǎn)單且入門(mén)的一種數(shù)據(jù)結(jié)構(gòu)，他與我們的數(shù)組幾乎一致，但越是簡(jiǎn)單的東西越不能大意，我們需要做到可以熟練的手動(dòng)寫(xiě)成它的各種功能，達(dá)到信手拈來(lái)的地步?；A(chǔ)學(xué)好才更易于我們學(xué)習(xí)后面更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)順序表用法詳解的文章就介紹到這了,更多相關(guān)Java 順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論