寫(xiě)在前面

關(guān)于數(shù)據(jù)結(jié)構(gòu)，Java官方其實(shí)已經(jīng)幫我們寫(xiě)好并封裝起來(lái)了，在真正需要使用的時(shí)候直接調(diào)用即可，但為了更好的理解數(shù)據(jù)結(jié)構(gòu)，我會(huì)按照源碼的思路寫(xiě)一個(gè)簡(jiǎn)化后的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)接收的數(shù)據(jù)為int

1.線(xiàn)性表

線(xiàn)性表是多個(gè)具有相同特性的數(shù)據(jù)元素的序列，線(xiàn)性表在邏輯上是一條連續(xù)的直線(xiàn)，但在實(shí)際存儲(chǔ)上卻不一定

順序表則是線(xiàn)性表的一種，是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性結(jié)構(gòu)，通常是使用數(shù)組來(lái)實(shí)現(xiàn)

2.順序表的實(shí)現(xiàn)

新建一個(gè)類(lèi)叫做ArrList，順序表的底層是數(shù)組，所以類(lèi)里面也要有數(shù)組，其次還需要一個(gè)計(jì)數(shù)器來(lái)判斷數(shù)組目前使用的空間是多少，那么順序表的框架就完成了

public class ArrList {
    public int[] arr;
    public int count;
    public ArrList() {
        this.arr = new int[5];  //初始給5個(gè)大小空間
    }
}

接下來(lái)就是順序表的增刪改查等操作了

2.1增加數(shù)據(jù)

增加數(shù)據(jù)有兩個(gè)方法：末尾增加數(shù)據(jù)和任意位置增加數(shù)據(jù)

2.1.1尾部增加數(shù)據(jù)

在這之前需要進(jìn)行的一項(xiàng)工作是判斷順序表的空間是否已滿(mǎn)，如果空間已滿(mǎn)的話(huà)需要進(jìn)行擴(kuò)容，判斷順序表空間是否已滿(mǎn)的依據(jù)是計(jì)數(shù)器的值和數(shù)組的長(zhǎng)度是否相等

public boolean isFull() {
        return this.count==this.arr.length;
    }
public void tailAdd(int data) {
        //首先判斷順序表是否已滿(mǎn)
        if(isFull()) {
            //順序表已滿(mǎn)，需要擴(kuò)容，這里是擴(kuò)大為原來(lái)的兩倍
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        //程序走到這，不管有沒(méi)有擴(kuò)容，此時(shí)順序表都是未滿(mǎn)，直接添加數(shù)據(jù)
        this.arr[this.count]=data;
        this.count++;
    }

2.1.2任意位置增加數(shù)據(jù)

任意位置添加數(shù)據(jù)的話(huà)首先要判斷輸入的值是否是合法的，有一點(diǎn)要注意：如果輸入的值和計(jì)數(shù)器的值是相等的，那么此時(shí)就是在順序表末尾添加數(shù)據(jù)，這個(gè)數(shù)是合法的

public void add(int index,int data) {
        //首先需要判斷index的值是否合法，不合法直接拋出異常
        if(index<0||index>this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        if(isFull()) {
            //順序表已滿(mǎn)，需要擴(kuò)容
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        if(index==this.count) {
            this.arr[this.count]=data;
            this.count++;
        } else {
            //中間位置添加數(shù)據(jù)需要先把從此處開(kāi)始到末尾的數(shù)據(jù)都往后移動(dòng)一位，從后往前移
            for (int i = this.count-1; i >=index ; i--) {  
                this.arr[i+1]=this.arr[i];
            }
            this.arr[index]=data;
            this.count++;
        }
    }

2.2查找數(shù)據(jù)

輸入一個(gè)值，遍歷順序表進(jìn)行查找，有則返回下標(biāo)，沒(méi)有返回-1

public int find (int data) {
       for (int i = 0; i < this.count; i++) {
            if(this.arr[i]==data) {
                return i;
            }
        }
        return -1;
    }

之所以返回值是int而不是boolean是因?yàn)楹竺娴膭h除和修改數(shù)據(jù)的方法會(huì)使用到此方法

2.3刪除數(shù)據(jù)

找到要?jiǎng)h除的值的下標(biāo)，從此處開(kāi)始用后面的值對(duì)前面的值進(jìn)行覆蓋，最后將尾部的值改為0

public void delData(int data) {
        int i=find(data);
        if(i!=-1) {
            for (int j = i; j <this.count-1 ; j++) {
                this.arr[j]=this.arr[j+1];
            }
            this.count--;
            this.arr[this.count]=0;
        }
    }

2.4修改數(shù)據(jù)

修改指定位置的值，依舊首先要判斷位置是否合法

public void setIndex (int index,int data) {
        if(index<0||index>=this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        this.arr[index]=data;
    }

最后是銷(xiāo)毀順序表，不需要吧數(shù)組進(jìn)行銷(xiāo)毀，否則下次使用的時(shí)候還需要再實(shí)例化一個(gè)對(duì)象，只需要讓計(jì)數(shù)器為0即可

public void clear () {
        this.count=0; 
    }

3.ArrayList

Java中的順序表叫做ArrayList，這是一個(gè)泛型類(lèi)，這個(gè)類(lèi)繼承了多個(gè)其它類(lèi)以及接口，其中包括List接口，List提供了很多抽象方法，ArrayList實(shí)現(xiàn)此接口對(duì)這些方法進(jìn)行重寫(xiě)

3.1ArrayList的實(shí)例化

ArrayList有三種構(gòu)造方法

要說(shuō)明的是：調(diào)用無(wú)參數(shù)構(gòu)造方法，默認(rèn)數(shù)組的大小為0，之后在調(diào)用里面的方法（比如add方法）的時(shí)候會(huì)有專(zhuān)門(mén)的擴(kuò)容的方法將其擴(kuò)容為10，之后如果數(shù)組滿(mǎn)了的話(huà)擴(kuò)容為之前的1.5倍（源碼里面套的方法太多就不展示了）

3.2ArrayList常用的方法

最后的截取方法是在原數(shù)組上進(jìn)行截取

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

最新評(píng)論