国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Java 數據結構實現(DataStructure)2

simpleapples / 807人閱讀

摘要:堆??梢钥闯墒怯刑囟ㄒ巹t為的線性表,特定規則就是先進后出,后進先出,可以看成是我們的先的要后,所以利用這一點可以通過繼承或組合的方式來構建堆棧。鑒于上面這張物理結構和邏輯結構,我們采用提供的來構建主存儲結構,即節點的線性表以達到索引的目的。

堆棧

可以看成是有特定規則為的線性表,特定規則就是先進后出,后進先出,可以看成是我們List的先insertFromHead的要后deleteFromHead,所以利用這一點可以通過繼承或組合的方式來構建堆棧。

繼承構建堆棧:

public class StackInheritance extends List {
   public StackInheritance() { super( "stack" ); }
   public void push( Object o )
      { insertFromHead( o ); }
   public Object pop() throws EmptyListException
      { return deleteFromHead(); }
   public boolean isEmpty() { return super.isEmpty(); }
   public void print() { super.print(); }
}

組合構建堆棧:

public class StackComposition {
   private List s;

   public StackComposition() { s = new List( "stack" ); }
   public void push( Object o )
      { s.insertFromHead( o ); }
   public Object pop() throws EmptyListException
      { return s.deleteFromHead(); }
   public boolean isEmpty() { return s.isEmpty(); }
   public void print() { s.print(); }
}

隊列

可以看成是有特定規則為的線性表,特定規則就是先進先出(FIFO),后進后出,可以看成是我們List的先insertFromBack的要后deleteFromHead,所以利用這一點可以通過繼承或組合的方式來構建堆棧。

繼承構建隊列

public class QueueInheritance extends List {
   public QueueInheritance() { super( "queue" ); }
   public void enqueue( Object o )
      { insertFromBack( o ); }
   public Object dequeue()
      throws EmptyListException { returnDeleteFromHead(); }
   public boolean isEmpty() { return super.isEmpty(); }
   public void print() { super.print(); }
}

二叉樹

可以看成是一堆散節點通過特殊的連接構成的散點集,這些散點集構成了特殊的結構,看起來成了樹一樣的結果。

如下圖所示,上面的為二叉樹的邏輯結構,這樣的邏輯結構利于分析二叉樹的性質,卻不能說明二叉樹存儲的實際情形,因此需要使用下圖所示的二叉樹的物理結構來描述其存儲特性,二叉樹的節點存儲為線性表,線性表中的節點有自己的特殊的包含(連接關系),因此使得這種物理結構和它的邏輯結構有了能夠轉換的基礎。

鑒于上面這張物理結構和邏輯結構,我們采用Java提供的List(LinkedList)來構建主存儲結構,即Node節點的線性表以達到索引的目的。然后建立節點之間的連接關系。

import java.util.LinkedList;
import java.util.List;

public class BinTreeTraverse {

    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    private static List nodeList = null;

    /**
     * 內部類:節點
     */
    private static class Node {
        Node leftChild;
        Node rightChild;
        int data;

        Node(int newData) {
            leftChild = null;
            rightChild = null;
            data = newData;
        }
    }

    public void createBinTree() {
        nodeList = new LinkedList();
        // 將一個數組的值依次轉換為Node節點
        for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
            nodeList.add(new Node(array[nodeIndex]));
        }
        // 對前lastParentIndex-1個父節點按照父節點與孩子節點的數字關系建立二叉樹
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
            // 左孩子
            nodeList.get(parentIndex).leftChild = nodeList
                    .get(parentIndex * 2 + 1);
            // 右孩子
            nodeList.get(parentIndex).rightChild = nodeList
                    .get(parentIndex * 2 + 2);
        }
        // 最后一個父節點:因為最后一個父節點可能沒有右孩子,所以多帶帶拿出來處理
        int lastParentIndex = array.length / 2 - 1;
        // 左孩子
        nodeList.get(lastParentIndex).leftChild = nodeList
                .get(lastParentIndex * 2 + 1);
        // 右孩子,如果數組的長度為奇數才建立右孩子
        if (array.length % 2 == 1) {
            nodeList.get(lastParentIndex).rightChild = nodeList
                    .get(lastParentIndex * 2 + 2);
        }
    }

    /**
     * 先序遍歷
     * 
     * 這三種不同的遍歷結構都是一樣的,只是先后順序不一樣而已
     * 
     * @param node
     *            遍歷的節點
     */
    public static void preOrderTraverse(Node node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }

    /**
     * 中序遍歷
     * 
     * 這三種不同的遍歷結構都是一樣的,只是先后順序不一樣而已
     * 
     * @param node
     *            遍歷的節點
     */
    public static void inOrderTraverse(Node node) {
        if (node == null)
            return;
        inOrderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        inOrderTraverse(node.rightChild);
    }

    /**
     * 后序遍歷
     * 
     * 這三種不同的遍歷結構都是一樣的,只是先后順序不一樣而已
     * 
     * @param node
     *            遍歷的節點
     */
    public static void postOrderTraverse(Node node) {
        if (node == null)
            return;
        postOrderTraverse(node.leftChild);
        postOrderTraverse(node.rightChild);
        System.out.print(node.data + " ");
    }

    public static void main(String[] args) {
        BinTreeTraverse binTree = new BinTreeTraverse();
        binTree.createBinTree();
        // nodeList中第0個索引處的值即為根節點
        Node root = nodeList.get(0);

        System.out.println("先序遍歷:");
        preOrderTraverse(root);
        System.out.println();

        System.out.println("中序遍歷:");
        inOrderTraverse(root);
        System.out.println();

        System.out.println("后序遍歷:");
        postOrderTraverse(root);
    }

}
  

這里我們為什么不使用自己定義的NodeList呢?因為如果一旦使用這個NodeList來作為主存儲部分,就會使得在子節點的指向過程中導致整個結構指向混亂,造成對結構的破壞。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64205.html

相關文章

  • Java? 教程(嵌套類)

    嵌套類 Java編程語言允許你在另一個類中定義類,這樣的類稱為嵌套類,如下所示: class OuterClass { ... class NestedClass { ... } } 術語:嵌套類分為兩類:靜態和非靜態,聲明為static的嵌套類稱為靜態嵌套類,非靜態嵌套類稱為內部類。 class OuterClass { ... stati...

    Cheng_Gang 評論0 收藏0
  • Java 數據結構實現DataStructure)1

    摘要:雙向鏈表的實現,必須注意雙向鏈表的和兩個指針的正確指向,以及插入和刪除過程中指向操作增減的有序性。定義節點,節點數據類型為,可以通過多態方式具象化為其他類型定義從頭尾節點增加節點定義從頭尾節點刪除節點 線性表和鏈表 單向鏈表利用了類的自引用,實現了類似指針的效果。 雙向鏈表的實現,必須注意雙向鏈表的head和back兩個指針的正確指向,以及插入和刪除過程中指向操作增減的有序性。 下...

    宋華 評論0 收藏0
  • 數據結構-棧

    摘要:棧也稱為后進先出表棧的應用場景操作撤銷例如將操作的每組數據存入棧中,如果想要撤銷,只需要彈出棧頂元素,就可以恢復上一步操作了。最后執行完成,根據棧的結構開始彈出數據,一步一步再走回方法。 數據結構-棧 定義 棧(英語:stack)又稱為堆?;蚨询B,棧作為一種數據結構,它按照先進后出的原則存儲數據,先進入的數據被壓入棧底,最后的數據在棧頂,需要讀數據的時候從棧頂開始彈出數據(最后一個數據...

    TalkingData 評論0 收藏0
  • 數據結構-數組

    摘要:數據結構數組數組數據結構中最基本的一個結構就是線性結構,而線性結構又分為連續存儲結構和離散存儲結構。比如容量,擴容個,沒有意義,很快就滿了容量,擴充個,太多了,容易早證浪費。 數據結構-數組 數組 數據結構中最基本的一個結構就是線性結構,而線性結構又分為連續存儲結構和離散存儲結構。所謂的連續存儲結構其實就是數組。 優點:插入塊如果知道坐標可以快速去地存取 缺點:查找慢,刪除慢,大...

    894974231 評論0 收藏0
  • HashedWheelTimer算法詳解

    摘要:算法序和年的論文提出了一種定時輪的方式來管理和維護大量的調度算法內核中的定時器采用的就是這個方案。使用實例每一次的時間間隔每一次就會到達下一個槽位輪中的數源碼解讀之時間輪算法實現定時輪算法細說延時任務的處理定時器的實現 HashedWheelTimer算法 序 George Varghese 和 Tony Lauck 1996 年的論文:Hashed and Hierarchical ...

    aervon 評論0 收藏0

發表評論

0條評論

simpleapples

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<