Java數(shù)據(jù)結(jié)構(gòu)順序表用法詳解
1.什么是順序表
在程序中,經(jīng)常需要將一組(通常是同為某個(gè)類型的)數(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è)線性表是某類元素的一個(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ù)組來存儲(chǔ)元素,這里的T指的是泛型,因?yàn)槲覀冞€沒確定放入的元素類型,有可能放int,String等等,所以先用泛型表示,不明白泛型的可以了解了解。其次用一個(gè)N來統(tǒng)計(jì)順序表中的元素個(gè)數(shù)。在構(gòu)造方法中,capacity表示我們創(chuàng)建時(shí)arr的初始長(zhǎng)度,因?yàn)榉盒褪菬o法直接實(shí)例化的,這里我們可以new一個(gè)Object數(shù)組,因?yàn)镺bject是任何類的父類,所以T為任何類型我們都可以將Object強(qiáng)轉(zhuǎn)為我們需要的數(shù)組,N剛開始為0即可。
下面是順序表需要實(shí)現(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) | 手動(dòng)實(shí)現(xiàn)擴(kuò)容功能 |
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元素開始后面的元素都向后移一位 for(int j=N-1;j>=i;j--){ arr[j+1]=arr[j]; } N++; arr[i]=t; }
解析:插入元素我們?nèi)匀恍枰袛嗍欠裥枰獙?duì)數(shù)組進(jìn)行擴(kuò)容,然后我們需要通過循環(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ù)組是否過長(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),比如二分查找等等,元素不多的情況下使用哪種都可以。如果沒查詢到我們返回一個(gè)-1表示該表中沒有需要查詢的t元素。
7.手動(dòng)擴(kuò)容方法
//手寫擴(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中的集合類ArrayList就有自動(dòng)擴(kuò)容的功能,它的功能與邏輯結(jié)構(gòu)類似我們的順序表,懂得手動(dòng)擴(kuò)容使我們更容易閱讀ArrayList的源碼,更好的理解和掌握它。
總結(jié):順序表是非常簡(jiǎn)單且入門的一種數(shù)據(jù)結(jié)構(gòu),他與我們的數(shù)組幾乎一致,但越是簡(jiǎn)單的東西越不能大意,我們需要做到可以熟練的手動(dòng)寫成它的各種功能,達(dá)到信手拈來的地步。基礎(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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java工具之ja-netfilter?2022.1?配置教程
這篇文章主要介紹了Java工具之ja-netfilter?2022.1?配置教程,本防火墻基于javaagent,所以目前只有基于java的程序能夠使用,需要的朋友可以參考下2022-04-04SpringBoot整合Shiro實(shí)現(xiàn)登錄認(rèn)證的方法
這篇文章主要介紹了SpringBoot整合Shiro實(shí)現(xiàn)登錄認(rèn)證的方法,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-02-02java中對(duì)list分頁并顯示數(shù)據(jù)到頁面實(shí)例代碼
這篇文章主要介紹了java中對(duì)list分頁并顯示數(shù)據(jù)到頁面實(shí)例代碼,分享了相關(guān)代碼示例,小編覺得還是挺不錯(cuò)的,具有一定借鑒價(jià)值,需要的朋友可以參考下2018-02-02

性能爆棚的實(shí)體轉(zhuǎn)換復(fù)制工具M(jìn)apStruct使用詳解

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

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

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