国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

Java數(shù)據(jù)結(jié)構(gòu)

2年前作者：羅小黑的橙子分類：Toy博客閱讀(17)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

java數(shù)據(jù)結(jié)構(gòu)有：

1、數(shù)組? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2、列表? (List)

3、集合（Set）???????????????????4、棧 (Stack)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

5、隊(duì)列? (Queue)? ? ? ? ? ? ? ? 6、樹 (Tree)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

7、堆 (Heap)? ? ? ? ? ? ? ? ? ? ? ?8、MAP? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Java數(shù)據(jù)結(jié)構(gòu)

一：數(shù)組

????????數(shù)組是編程語(yǔ)言中最常見的一種數(shù)據(jù)結(jié)構(gòu)，可以用它來存儲(chǔ)一個(gè)元素個(gè)數(shù)固定且元素類型相同的有序集，每個(gè)數(shù)組元素存放一個(gè)數(shù)據(jù)，通?？赏ㄟ^數(shù)組元素的索引來訪問數(shù)組元素，包括為數(shù)組元素賦值和取出數(shù)組元素的值。

數(shù)組初始化：

靜態(tài)初始化方式1：int[] number={......} (聲明數(shù)組、創(chuàng)建數(shù)組和初始化數(shù)組)

靜態(tài)初始化方式2：int[] number=new int{.......} (初始化數(shù)組和給數(shù)組賦值同時(shí)完成)

動(dòng)態(tài)初始化方式：String[] value = new String[10] (數(shù)組的聲明和初始化同時(shí)完成)

數(shù)組的特點(diǎn)：

1.數(shù)組是有序的

2.數(shù)組中的元素一定是為相同的數(shù)據(jù)類型

3.數(shù)組中的元素可以通過索引下標(biāo)訪問

4.數(shù)組的長(zhǎng)度一經(jīng)確定不可更改

5.數(shù)組一經(jīng)創(chuàng)建在內(nèi)存中開辟連續(xù)的空間

數(shù)組的操作：

1.初始化，遍歷，打印，最大值，最大值下標(biāo)

2.foreach增強(qiáng)for循環(huán)：

for(double e : list){

System.out.println(e);

}

3.復(fù)制數(shù)組有三種方法：

（1）

.int[] sourceArray = {2,5,8,10,200,-20};

int[] targetArray = new int[sourceArray.length];

for(int i = 0; i < sourceArray.length; i++)

targetArray[i] = sourceArray[i];

（2）.使用System類中的靜態(tài)方法ArrayCopy

（3）.使用clone方法復(fù)制數(shù)組

4.線性查找

5.二分查找

6.選擇排序

數(shù)組的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

  • 按照索引查詢?cè)氐乃俣群芸欤?/li>
  • 按照索引遍歷數(shù)組也很方便。

缺點(diǎn)：

  • 數(shù)組的大小在創(chuàng)建后就確定了，無(wú)法擴(kuò)容；
  • 數(shù)組只能存儲(chǔ)一種類型的數(shù)據(jù)；
  • 添加、刪除元素的操作很耗時(shí)間，因?yàn)橐苿?dòng)其他元素。

二、列表 List

Java數(shù)據(jù)結(jié)構(gòu)

概念： List集合是一個(gè)元素有序（每個(gè)元素都有對(duì)應(yīng)的順序索引，第一個(gè)元素索引為0）、且可重復(fù)的集合。

2.1? ArrayList

?????????ArrayList 是一個(gè)數(shù)組隊(duì)列，相當(dāng)于動(dòng)態(tài)數(shù)組。與Java中的數(shù)組相比，它的容量能動(dòng)態(tài)增長(zhǎng)。它繼承于AbstractList，實(shí)現(xiàn)了List,?RandomAccess（隨機(jī)訪問）,?Cloneable（克隆）,?java.io.Serializable（可序列化）這些接口。?

????????和Vector不同，ArrayList中的操作不是線程安全的！所以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList

使用：

List是Collection接口的子接口，擁有Collection所有方法外，還有一些對(duì)索引操作的方法。

  • void add(int index, E element);：將元素element插入到List集合的index處；
  • boolean addAll(int index, Collection<? extends E> c);：將集合c所有的元素都插入到List集合的index起始處；
  • E remove(int index);：移除并返回index處的元素；
  • int indexOf(Object o);：返回對(duì)象o在List集合中第一次出現(xiàn)的位置索引；
  • int lastIndexOf(Object o);：返回對(duì)象o在List集合中最后一次出現(xiàn)的位置索引；
  • E set(int index, E element);：將index索引處的元素替換為新的element對(duì)象，并返回被替換的舊元素；
  • E get(int index);：返回集合index索引處的對(duì)象；
  • List<E> subList(int fromIndex, int toIndex);：返回從索引fromIndex（包含）到索引toIndex（不包含）所有元素組成的子集合；
  • void sort(Comparator<? super E> c)：根據(jù)Comparator參數(shù)對(duì)List集合元素進(jìn)行排序；
  • void replaceAll(UnaryOperator<E> operator)：根據(jù)operator指定的計(jì)算規(guī)則重新設(shè)置集合的所有元素。
  • ListIterator<E> listIterator();：返回一個(gè)ListIterator對(duì)象，該接口繼承了Iterator接口，在Iterator接口基礎(chǔ)上增加了以下方法，具有向前迭代功能且可以增加元素:
    bookean hasPrevious()：返回迭代器關(guān)聯(lián)的集合是否還有上一個(gè)元素；
    E previous();：返回迭代器上一個(gè)元素；
    void add(E e);：在指定位置插入元素；

ArrayList的遍歷方式

3種方式

  1. 通過迭代器遍歷。即通過Iterator去遍歷。 
    Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}
  2. 隨機(jī)訪問index，通過索引值去遍歷。
    由于ArrayList實(shí)現(xiàn)了RandomAccess接口，它支持通過索引值去隨機(jī)訪問元素。 
    Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
    value = (Integer)list.get(i);        
}

    3.增強(qiáng)for循環(huán)遍歷。如下

    Integer value = null;
for (Integer integ:list) {
    value = integ;
}

ArrayList<E>使用泛型

JDK 1.5之后，引入了泛型，可指定列表內(nèi)元素的類型。類型不符合的元素不允許加入數(shù)組，這樣就能再編譯階段發(fā)現(xiàn)錯(cuò)誤，避免運(yùn)行時(shí)出錯(cuò)的尷尬。

// 開團(tuán)
		List<Girl> _泰國(guó)五日游 = new ArrayList<Girl>();
		……
		// 混入
		Boy _b = new Boy();
		//提示代碼有錯(cuò)誤:     _泰國(guó)五日游.add(_b);

Collection相關(guān)方法

這些方法屬于Collection類，可以被子類繼承，因此通用性較強(qiáng)，不僅List能用，Set也能用。

Java數(shù)據(jù)結(jié)構(gòu)

?Arrays工具類常用方法：

1 equals()：比較兩個(gè)array是否相等。array擁有相同元素個(gè)數(shù)，且所有對(duì)應(yīng)元素兩兩相等。

2 fill()：將值填入array中。

3 sort()：用來對(duì)array進(jìn)行排序。

4 binarySearch()：在排好序的array中尋找元素。

5 System.arraycopy()：array的復(fù)制。

2.2? ?Vector?

Vector是一個(gè)比較老的類，和ArrayList用法相同，在JDK 1.0即已出現(xiàn)，不推薦使用（雖然Vector是線程安全的，但是在線程安全方面也不推薦使用。推薦方案如下：

List<String> synList = Collections.synchronizedList(lst);

2.3 ?鏈表 LinkedList

LinkedList概述

??LinkedList 是一個(gè)繼承于AbstractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。LinkedList的本質(zhì)是雙向鏈表。1）LinkedList繼承于AbstractSequentialList，并且實(shí)現(xiàn)了Dequeue接口。2) LinkedList包含兩個(gè)重要的成員：header 和 size。
header：是雙向鏈表的表頭，它是雙向鏈表節(jié)點(diǎn)所對(duì)應(yīng)的類Entry的實(shí)例。Entry中包含成員變量：previous, next, element。(其中，previous是該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，next是該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，element是該節(jié)點(diǎn)所包含的值。)
size：是雙向鏈表中節(jié)點(diǎn)的個(gè)數(shù)。

單鏈表


不需要連續(xù)的存儲(chǔ)空間，所以在刪除和增加結(jié)點(diǎn)時(shí)不需要像順序表一樣需要移動(dòng)全部的元素，提高運(yùn)行效率。

Java數(shù)據(jù)結(jié)構(gòu)

class SingleList{
    Node1 head=new Node1(0,0);
    //增加鏈表到最后
    public void add(Node1 node){
        Node1 temp=head;
        while(true){
            if(temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=node;
    }
    //按序號(hào)增加鏈表
    public void addByOrder(Node1 node){
        Node1 temp=head;
        while(true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no>=node.no){
                break;
            }
            temp=temp.next;
        }
        node.next=temp.next;
        temp.next=node;
    }
    //刪除指定結(jié)點(diǎn)
    public void delNode(Node1 node){
        Node1 temp=head;
        while(true){
            if(temp.next==node){
                break;
            }
            temp=temp.next;
        }
        temp.next=temp.next.next;
    }
    //修改單鏈表的結(jié)點(diǎn)
    public void update(Node1 node,int update){
        Node1 temp=head;
        while(true){
            if(temp.no==node.no){
                break;
            }
            temp=temp.next;
        }
        temp.date=update;
    }
    //打印單鏈表
    public void list(){
        Node1 temp=head.next;
        if(head.next==null){
            System.out.println("Empty!");
        }
        while(temp!=null){
            System.out.println(temp.toString());
            temp=temp.next;
        }
    }
}
//創(chuàng)建一個(gè)類，每個(gè)類的對(duì)象就是一個(gè)結(jié)點(diǎn)。
class Node1{
    public int date;
    public int no;
    public Node1 next;

    public Node1(int date, int no) {
        this.date = date;
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node1{" +
                "date=" + date +
                ", no=" + no +
                '}';
    }
}

雙向鏈表

對(duì)于單向鏈表而言，只有一個(gè)查找方向，并且不能自我刪除。
所以引入雙向鏈表，與單向鏈表的主要不同點(diǎn)只是在于pre指針的引入和刪除操作
next：指向下一個(gè)結(jié)點(diǎn)。
pre：指向前一個(gè)結(jié)點(diǎn)。

LinkedList特點(diǎn)：使用鏈表實(shí)現(xiàn)，查詢慢，增刪快，適用于經(jīng)常插入、刪除大量數(shù)據(jù)的場(chǎng)合，適合采用迭代器Iterator遍歷。

for(Iterator iter = list.iterator(); iter.hasNext();)
    iter.next();

LinkedList使用方法：

Java數(shù)據(jù)結(jié)構(gòu)

三、集合 （set）

set：集合注重獨(dú)一無(wú)二的性質(zhì),該體系集合可以知道某物是否已近存在于集合中,不會(huì)存儲(chǔ)重復(fù)的元素用于存儲(chǔ)無(wú)序(存入和取出的順序不一定相同)元素，值不能重復(fù)。

如果想要讓兩個(gè)不同的Person對(duì)象視為相等的，就必須覆蓋Object繼下來的hashCode方法和equals方法，因?yàn)镺bject hashCode方法返回的是該對(duì)象的內(nèi)存地址，所以必須重寫hashCode方法，才能保證兩個(gè)不同的對(duì)象具有相同的hashCode，同時(shí)也需要兩個(gè)不同對(duì)象比較equals方法會(huì)返回true

兩個(gè)對(duì)象hash值相同，值不一行相等，因?yàn)榭赡躤quals（）方法不等。

迭代方法：使用迭代器

public class Demo4 {
    public static void main(String[] args) {
        //Set 集合存和取的順序不一致。
        Set hs = new HashSet();
        hs.add("世界軍事");
        hs.add("兵器知識(shí)");
        hs.add("艦船知識(shí)");
        hs.add("漢和防務(wù)");
        System.out.println(hs);
        // [艦船知識(shí), 世界軍事, 兵器知識(shí), 漢和防務(wù)]
        Iterator it = hs.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

? HashSet : 為快速查找設(shè)計(jì)的Set。存入HashSet的對(duì)象必須定義hashCode()。
??? TreeSet : 保存次序的Set, 底層為樹結(jié)構(gòu)。使用它可以從Set中提取有序的序列。
??? LinkedHashSet : 具有HashSet的查詢速度，且內(nèi)部使用鏈表維護(hù)元素的順序(插入的次序)。于是在使用迭代器遍歷Set時(shí)，結(jié)果會(huì)按元素插入的次序顯示。?

四、棧（先入后出） ?

特點(diǎn)：先入后出，變化的一端在棧頂，棧底固定，像一個(gè)桶

入棧（push）：棧頂上移

出棧（pop）：棧頂下移

Java中也提供了關(guān)于棧的類，便于直接調(diào)用。

數(shù)組模擬棧的思路分析：
定義top表示棧頂指針，初始為-1；
入棧：top++；
stack[top]=data;
出棧：拿到數(shù)據(jù)；top--；

/**
 * max 表示棧的最大容量
 * top 棧頂指針
 * stack[] 用數(shù)組模擬棧
 */
 class stack{
    private int max;
    private int top=-1;
    private int stack[];
    public stack(int max){
        this.max=max;
        stack=new int[max];
    }
    public boolean isFull(){
        return top==max-1;
    }
    public boolean isEmpty(){
        return top==-1;
    }
    //入棧
    public void push(int date){
        if(isFull()){
            System.out.println("False");
            return;
        }
        top++;
        stack[top]=date;
    }
    //出棧
     public int pop(){
        if(isEmpty()){
            throw new RuntimeException("Empty");
        }
        int value= stack[top];
        top--;
        return value;
     }
     //遍歷
     public void list(){
        for(int i=top;i>=0;i--){
            System.out.printf("stack[%d]=%d",i, stack[i]);
        }
     }
}

棧使用示例：?

//1.創(chuàng)建一個(gè)字符型的棧
Stack<Character> stack=new Stack<>();
System.out.println(stack);
//2.測(cè)試棧是否為空
System.out.println(stack.empty());
//3.入棧
stack.push('a');
stack.push('b');
stack.push('c');
System.out.println(stack);
//4.查看棧頂元素
System.out.println(stack.peek());
System.out.println(stack);
//5.出棧
stack.pop();
System.out.println(stack);
//6.返回對(duì)象在棧中的位置
System.out.println(stack.search('b'));
System.out.println(stack.search('a'));

五、隊(duì)列 （先進(jìn)先出）

?Queue：

Queue是java中實(shí)現(xiàn)隊(duì)列的接口，它總共只有6個(gè)方法，我們一般只用其中3個(gè)就可以了。Queue的實(shí)現(xiàn)類有LinkedList和PriorityQueue。最常用的實(shí)現(xiàn)類是LinkedList。?

Queue的6個(gè)方法分類：

壓入元素(添加)：add()、offer()
相同：未超出容量，從隊(duì)尾壓入元素，返回壓入的那個(gè)元素。
區(qū)別：在超出容量時(shí)，add()方法會(huì)對(duì)拋出異常，offer()返回false

彈出元素(刪除)：remove()、poll()
相同：容量大于0的時(shí)候，刪除并返回隊(duì)頭被刪除的那個(gè)元素。
區(qū)別：在容量為0的時(shí)候，remove()會(huì)拋出異常，poll()返回false

獲取隊(duì)頭元素(不刪除)：element()、peek()
相同：容量大于0的時(shí)候，都返回隊(duì)頭元素。但是不刪除。
區(qū)別：容量為0的時(shí)候，element()會(huì)拋出異常，peek()返回null。
?

public class QueueTest {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList();
        queue.offer("元素A");
        queue.offer("元素B");
        queue.offer("元素C");
        queue.offer("元素D");
        queue.offer("元素E");
        while (queue.size() > 0) {
            String element = queue.poll();
            System.out.println(element);
        }
    }
}

PriorityQueue 優(yōu)先隊(duì)列：

優(yōu)先隊(duì)列PriorityQueue是Queue接口的實(shí)現(xiàn)，可以對(duì)其中元素進(jìn)行排序，可以放基本數(shù)據(jù)類型的包裝類（如：Integer，Long等）或自定義的類對(duì)于基本數(shù)據(jù)類型的包裝器類，優(yōu)先隊(duì)列中元素默認(rèn)排列順序是升序排列但對(duì)于自己定義的類來說，需要自己定義比較器

常用方法：

peek()//返回隊(duì)首元素
poll()//返回隊(duì)首元素，隊(duì)首元素出隊(duì)列
add()//添加元素
size()//返回隊(duì)列元素個(gè)數(shù)
isEmpty()//判斷隊(duì)列是否為空，為空返回true,不空返回false

?六、樹

樹定義和基本術(shù)語(yǔ)
定義
樹(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T，并且當(dāng)n＞0時(shí)滿足下列條件：
???? （1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；
???? （2）當(dāng)n＞1時(shí)，其余結(jié)點(diǎn)可以劃分為m(m＞0)個(gè)互不相交的有限集T1、T2 、…、Tm，每個(gè)集Ti(1≤i≤m)均為樹，且稱為樹T的子樹(SubTree)。
??? 特別地，不含任何結(jié)點(diǎn)(即n＝0)的樹，稱為空樹。
如下就是一棵樹的結(jié)構(gòu)：

Java數(shù)據(jù)結(jié)構(gòu)

　　　　　　　　??????????????? 圖1
基本術(shù)語(yǔ)
結(jié)點(diǎn)：存儲(chǔ)數(shù)據(jù)元素和指向子樹的鏈接，由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的引用組成。
孩子結(jié)點(diǎn)：樹中一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，如圖1中的A的孩子結(jié)點(diǎn)有B、C、D
雙親結(jié)點(diǎn)：樹中某個(gè)結(jié)點(diǎn)有孩子結(jié)點(diǎn)(即該結(jié)點(diǎn)的度不為0)，該結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)，也叫前驅(qū)結(jié)點(diǎn)。雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)是相互的，如圖1中，A的孩子結(jié)點(diǎn)是B、C、D，B、C、D的雙親結(jié)點(diǎn)是A。
兄弟結(jié)點(diǎn)：具有相同雙親結(jié)點(diǎn)(即同一個(gè)前驅(qū))的結(jié)點(diǎn)稱為兄弟結(jié)點(diǎn)，如圖1中B、B、D為兄弟結(jié)點(diǎn)。
結(jié)點(diǎn)的度：結(jié)點(diǎn)所有子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，如圖1，A的度為3，B的度為2.
樹的度：樹中所有結(jié)點(diǎn)的度的最大值稱為樹的度，如圖1的度為3.
葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，也叫終端結(jié)點(diǎn)。如圖1的K、L、F、G、M、I、J
分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)。如圖1的A、B、C、D、E、H
結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)到樹中某結(jié)點(diǎn)所經(jīng)路徑的分支數(shù)稱為該結(jié)點(diǎn)的層次。根結(jié)點(diǎn)的層次一般為1(也可以自己定義為0)，這樣，其它結(jié)點(diǎn)的層次是其雙親結(jié)點(diǎn)的層次加1.
樹的深度：樹中所有結(jié)點(diǎn)的層次的最大值稱為該樹的深度(也就是最下面那個(gè)結(jié)點(diǎn)的層次)。
有序樹和無(wú)序樹：樹中任意一個(gè)結(jié)點(diǎn)的各子樹按從左到右是有序的，稱為有序樹，否則稱為無(wú)序樹。
樹的抽象數(shù)據(jù)類型描述
數(shù)據(jù)元素：具有相同特性的數(shù)據(jù)元素的集合。
結(jié)構(gòu)關(guān)系：樹中數(shù)據(jù)元素間的結(jié)構(gòu)關(guān)系由樹的定義確定。
基本操作：樹的主要操作有
（1）創(chuàng)建樹IntTree(&T)
???????? 創(chuàng)建1個(gè)空樹T。
（2）銷毀樹DestroyTree(&T)
（3）構(gòu)造樹CreatTree(&T，deinition)
（4）置空樹ClearTree(&T)
????????? 將樹T置為空樹。
（5）判空樹TreeEmpty(T)
（6）求樹的深度TreeDepth(T)
（7）獲得樹根Root(T)
（8）獲取結(jié)點(diǎn)Value(T，cur_e，&e)
???????? 將樹中結(jié)點(diǎn)cur_e存入e單元中。
（9）數(shù)據(jù)賦值A(chǔ)ssign(T，cur_e，value)
???????? 將結(jié)點(diǎn)value，賦值于樹T的結(jié)點(diǎn)cur_e中。
（10）獲得雙親Parent(T，cur_e)
??????? 返回樹T中結(jié)點(diǎn)cur_e的雙親結(jié)點(diǎn)。
（11）獲得最左孩子LeftChild(T，cur_e)
??????? 返回樹T中結(jié)點(diǎn)cur_e的最左孩子。
（12）獲得右兄弟RightSibling(T，cur_e)
??????? 返回樹T中結(jié)點(diǎn)cur_e的右兄弟。
（13）插入子樹InsertChild(&T，&p，i，c)
????? 將樹c插入到樹T中p指向結(jié)點(diǎn)的第i個(gè)子樹之前。
（14）刪除子樹DeleteChild(&T，&p，i)
?????? 刪除樹T中p指向結(jié)點(diǎn)的第i個(gè)子樹。
（15）遍歷樹TraverseTree(T，visit())

樹的實(shí)現(xiàn)
樹是一種遞歸結(jié)構(gòu)，表示方式一般有孩子表示法和孩子兄弟表示法兩種。樹實(shí)現(xiàn)方式有很多種、有可以由廣義表的遞歸實(shí)現(xiàn)，也可以有二叉樹實(shí)現(xiàn)，其中最常見的是將樹用孩子兄弟表示法轉(zhuǎn)化成二叉樹來實(shí)現(xiàn)。

?樹的遍歷
樹的遍歷有兩種
前根遍歷
（1）.訪問根結(jié)點(diǎn)；
（2）.按照從左到右的次序行根遍歷根結(jié)點(diǎn)的第一棵子樹；

后根遍歷
（1）.按照從左到右的次序行根遍歷根結(jié)點(diǎn)的第一棵子樹；
（2）.訪問根結(jié)點(diǎn)；

七、堆

?概念：堆就是一顆順序存儲(chǔ)的完全二叉樹，底層是一個(gè)數(shù)組。

  1. 堆邏輯上是一顆完全二叉樹

  2. 堆物理上是保存在數(shù)組中

  3. 堆滿足任意結(jié)點(diǎn)的值都大于其子樹中結(jié)點(diǎn)的值，也就是所有根節(jié)點(diǎn) > 其左右孩子結(jié)點(diǎn)，叫做大堆，或者大根堆、最大堆，反之則是小堆，或者小根堆、最小堆

  4. 堆的基本作用是快速找到集合中的最值

java的堆和數(shù)據(jù)結(jié)構(gòu)堆：java的堆是程序員用new能得到的計(jì)算機(jī)內(nèi)存的可用部分。而數(shù)據(jù)結(jié)構(gòu)的堆是一種特殊的二叉樹。?

八、MAP

常用Map：Hashtable、HashMap、LinkedHashMap、TreeMap

　　類繼承關(guān)系：

Java數(shù)據(jù)結(jié)構(gòu)

HashMap

1）無(wú)序； 2）訪問速度快； 3）key不允許重復(fù)（只允許存在一個(gè)null Key）；

LinkedHashMap

1）有序； 2）HashMap子類；

TreeMap

1）根據(jù)key排序（默認(rèn)為升序）； 2）因?yàn)橐判?，所以key需要實(shí)現(xiàn) Comparable接口，否則會(huì)報(bào)ClassCastException 異常； 3）根據(jù)key的compareTo 方法判斷key是否重復(fù)。

HashTable

一個(gè)遺留類，類似于HashMap，和HashMap的區(qū)別如下：

1）Hashtable對(duì)絕大多數(shù)方法做了同步，是線程安全的，HashMap則不是；

2） Hashtable不允許key和value為null，HashMap則允許；

3）兩者對(duì)key的hash算法和hash值到內(nèi)存索引的映射算法不同。

HashMap

HashMap底層通過數(shù)組實(shí)現(xiàn)，數(shù)組中的元素是一個(gè)鏈表，準(zhǔn)確的說HashMap是一個(gè)數(shù)組與鏈表的結(jié)合體。即使用哈希表進(jìn)行數(shù)據(jù)存儲(chǔ)，并使用鏈地址法來解決沖突。

HashMap的幾個(gè)屬性：

initialCapacity：初始容量，即數(shù)組的大小。實(shí)際采用大于等于initialCapacity且是2^N的最小的整數(shù)。

loadFactor：負(fù)載因子，元素個(gè)數(shù)/數(shù)組大小。衡量數(shù)組的填充度，默認(rèn)為0.75。

threshold：閾值。值為initialCapacity和loadFactor的乘積。當(dāng)元素個(gè)數(shù)大于閾值時(shí)，進(jìn)行擴(kuò)容。

優(yōu)化點(diǎn)：1、頻繁擴(kuò)容會(huì)影響性能。設(shè)置合理的初始大小和負(fù)載因子可有效減少擴(kuò)容次數(shù)。

　　　　2、一個(gè)好的hashCode算法，可以盡可能較少?zèng)_突，從而提高HashMap的訪問速度。

LinkedHashMap----有序的HashMap

簡(jiǎn)單來說，HashMap+雙向鏈表=LinkedHashMap。

HashMap是無(wú)序的，即添加的順序和遍歷元素的順序具有不確定性。LinkedHashMap是HashMap的子類，是一種特殊的HashMap。

LinkedHashMap通過維護(hù)一個(gè)額外的雙向鏈表（在Entry中加入 before, after屬性記錄該元素的前驅(qū)和后繼），將所有的Entry節(jié)點(diǎn)鏈入一個(gè)雙向鏈表，從而實(shí)現(xiàn)有序性。通過迭代器遍歷元素是有序的。

兩種排序方式：

　　1）元素插入順序：accessOrder=false，默認(rèn)為false；

　　2）最近訪問順序：accessOrder=true。此情況下，不能使用迭代器遍歷集合，因?yàn)間et()方法會(huì)修改Map，在迭代器模式中修改集合會(huì)報(bào)ConcurrentModificationException。可以用來實(shí)現(xiàn)LRU（最近最少使用）算法。

TreeMap

TreeMap實(shí)現(xiàn)了SortedMap，可以根據(jù)key對(duì)元素進(jìn)行排序，還提供了接口對(duì)有序的key集合進(jìn)行篩選。

內(nèi)部基于紅黑樹實(shí)現(xiàn)，紅黑樹是一種平衡查找樹，它的統(tǒng)計(jì)性能要優(yōu)于平衡二叉樹。可以在O(logN) 時(shí)間內(nèi)做查找、插入和刪除，性能較好。

如果確實(shí)需要將排序功能加入HashMap，應(yīng)該使用TreeMap，而不應(yīng)該自己去實(shí)現(xiàn)排序。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-478628.html

?

到了這里，關(guān)于Java數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包