欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結構順序表用法詳解

 更新時間:2021年10月20日 09:04:50   作者:執(zhí)梗  
順序表是計算機內存中以數(shù)組的形式保存的線性表,線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中,即通過數(shù)據(jù)元素物理存儲的相鄰關系來反映數(shù)據(jù)元素之間邏輯上的相鄰關系

1.什么是順序表

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

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

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

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

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

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

解析:首先我們需要一個底層的arr數(shù)組來存儲元素,這里的T指的是泛型,因為我們還沒確定放入的元素類型,有可能放int,String等等,所以先用泛型表示,不明白泛型的可以了解了解。其次用一個N來統(tǒng)計順序表中的元素個數(shù)。在構造方法中,capacity表示我們創(chuàng)建時arr的初始長度,因為泛型是無法直接實例化的,這里我們可以new一個Object數(shù)組,因為Object是任何類的父類,所以T為任何類型我們都可以將Object強轉為我們需要的數(shù)組,N剛開始為0即可。

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

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第一次出現(xiàn)的位置
public void reSize(int newLength) 手動實現(xiàn)擴容功能

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

1.判斷線性表是否為空

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

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

2.獲取指定位置的元素

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

解析:數(shù)組可以直接索引對應位置的元素

3.向線性表表添加元素

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

解析:添加時,我們首先判斷數(shù)組arr是否已經裝滿,如果滿了會先調用我們的擴容方法增加數(shù)組長度,在后面會詳細解析。然后arr[N]這個位置加入元素即可,然后N會自增1,表示元素個數(shù)多了一個。

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;
    }

解析:插入元素我們仍然需要判斷是否需要對數(shù)組進行擴容,然后我們需要通過循環(huán)將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;
    }

解析:在這里我們也調用了擴容方法,但這里其實我們是判斷數(shù)組是否過長,當我們的存儲元素的個數(shù)小于數(shù)組長度的1/4,我們最好將數(shù)組長度縮小一半,以防止對內存的浪費。這里我們先將i處的元素用一個變量t保存。然后將i處后的元素依次向前移動一位,然后讓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;
    }

解析:這里我們直接使用暴力遍歷查找位置,當然有很多更好的查找算法可以實現(xiàn),比如二分查找等等,元素不多的情況下使用哪種都可以。如果沒查詢到我們返回一個-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;
    }

解析:擴容方法的實現(xiàn)其實非常簡單,就是判斷直接生成一個長度為原數(shù)組兩倍的數(shù)組,并把舊數(shù)組的元素遍歷進新數(shù)組,然后將新數(shù)組賦值給就數(shù)組即可。之所以要會手動擴容,因為java中的集合類ArrayList就有自動擴容的功能,它的功能與邏輯結構類似我們的順序表,懂得手動擴容使我們更容易閱讀ArrayList的源碼,更好的理解和掌握它。

總結:順序表是非常簡單且入門的一種數(shù)據(jù)結構,他與我們的數(shù)組幾乎一致,但越是簡單的東西越不能大意,我們需要做到可以熟練的手動寫成它的各種功能,達到信手拈來的地步。基礎學好才更易于我們學習后面更復雜的數(shù)據(jù)結構。

到此這篇關于Java數(shù)據(jù)結構順序表用法詳解的文章就介紹到這了,更多相關Java 順序表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • SpringBoot整合Shiro的代碼詳解

    SpringBoot整合Shiro的代碼詳解

    shiro是一個權限框架,它提供了很方便的權限認證和登錄的功能.下面通過本文給大家分享SpringBoot整合Shiro的代碼詳解,需要的的朋友參考下吧
    2017-08-08
  • 性能爆棚的實體轉換復制工具MapStruct使用詳解

    性能爆棚的實體轉換復制工具MapStruct使用詳解

    這篇文章主要為大家介紹了性能爆棚的實體轉換復制工具MapStruct使用詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-03-03
  • java實現(xiàn)簡單貪吃蛇小游戲

    java實現(xiàn)簡單貪吃蛇小游戲

    這篇文章主要為大家詳細介紹了java實現(xiàn)簡單貪吃蛇小游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-05-05
  • 基于Spring Boot使用JpaRepository刪除數(shù)據(jù)時的注意事項

    基于Spring Boot使用JpaRepository刪除數(shù)據(jù)時的注意事項

    這篇文章主要介紹了Spring Boot使用JpaRepository刪除數(shù)據(jù)時的注意事項,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • SpringBoot整合redis+Aop防止重復提交的實現(xiàn)

    SpringBoot整合redis+Aop防止重復提交的實現(xiàn)

    Spring Boot通過AOP可以實現(xiàn)防止表單重復提交,本文主要介紹了SpringBoot整合redis+Aop防止重復提交的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2023-07-07
  • 最新評論