鞠婧祎早期视频,中国泳装美女视频

相信大家對迭代器模式還是比較熟悉的，在Java的集合中有比較多的應(yīng)用。比如你想使用迭代器遍歷一個集合，代碼可能是這樣：

Java代碼

1. for (Iterator it = collection.iterator(); it.hasNext();)
2. {
3. doSomething(it.next());
4. }

   1. for (Iterator it = collection.iterator(); it.hasNext();)2. {3.     doSomething(it.next());4. }

迭代器的作用在于對數(shù)據(jù)的遍歷與數(shù)據(jù)的內(nèi)部表示進(jìn)行了分離。通過迭代器，你知道調(diào)用hasNext()來確認(rèn)是否還有下一個元素。如果有，那么就可以調(diào)用next()取得下一個元素。至于數(shù)據(jù)內(nèi)部如何表示，我們并不關(guān)心。我們關(guān)心的只是能以一種預(yù)先定義的順序來訪問每個元素。

組合模式用來表示一個節(jié)點(diǎn)內(nèi)部包含若干個其它的節(jié)點(diǎn)，而被包含的節(jié)點(diǎn)同樣也可以再包含另外的節(jié)點(diǎn)。因此是一種遞歸的結(jié)構(gòu)。不包含其他節(jié)點(diǎn)的節(jié)點(diǎn)叫做葉子節(jié)點(diǎn)，這通常是遞歸的終結(jié)點(diǎn)。樹形結(jié)構(gòu)比較適合用來說明組合模式。

假設(shè)我們用Node接口表示一個節(jié)點(diǎn)?？梢酝@個節(jié)點(diǎn)上添加節(jié)點(diǎn)，也可以獲得這個節(jié)點(diǎn)的迭代器，用來遍歷節(jié)點(diǎn)中的其他節(jié)點(diǎn)。

Java代碼

1. public interface Node {
2. void addNode(Node node);
3. Iterator<Node> iterator();
4. }

   1. public interface Node {2.     void addNode(Node node);3.     Iterator<Node> iterator();4. }

抽象類AbstractNode實(shí)現(xiàn)這個接口，并不做多余的事情。只是讓這個節(jié)點(diǎn)有個名字，以區(qū)分于其他節(jié)點(diǎn)。

Java代碼

1. public abstract class AbstractNode implements Node {
2. protected String name;
3.
4. protected AbstractNode(String name)
5. {
6. this.name = name;
7. }
8.
9. public String toString()
10. {
11. return name;
12. }
13. }

   1. public abstract class AbstractNode implements Node {2.     protected String name;3.4.     protected AbstractNode(String name)5.     {6.         this.name = name;7.     }8.9.     public String toString()10.     {11.         return name;12.     }13. }

接下來，是表示兩種不同類型的節(jié)點(diǎn)，樹枝節(jié)點(diǎn)和葉子節(jié)點(diǎn)。它們都繼承自AbstractNode，不同的是葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)。

Java代碼

1. public class LeafNode extends AbstractNode {
2.
3. public LeafNode(String name) {
4. super(name);
5. }
6.
7. public void addNode(Node node) {
8. throw new UnsupportedOperationException("Can't add a node to leaf.");
9. }
10.
11. public Iterator<Node> iterator() {
12. return new NullIterator<Node>();
13. }
14. }

   1. public class LeafNode extends AbstractNode {2.3.     public LeafNode(String name) {4.         super(name);5.     }6.7.     public void addNode(Node node) {8.         throw new UnsupportedOperationException("Can't add a node to leaf.");9.     }10.11.     public Iterator<Node> iterator() {12.         return new NullIterator<Node>();13.     }14. }

可以看到，試圖往葉子節(jié)點(diǎn)添加節(jié)點(diǎn)會導(dǎo)致異常拋出。而獲取葉子節(jié)點(diǎn)的迭代器，則返回……NullIterator。這個是什么？因?yàn)槿~子節(jié)點(diǎn)沒有子節(jié)點(diǎn)，所以葉子節(jié)點(diǎn)的迭代器沒有什么意義。我們可以簡單地返回null，但是那樣處理節(jié)點(diǎn)的代碼就需要區(qū)分是葉子節(jié)點(diǎn)還是其他節(jié)點(diǎn)。如果我們返回的是一個NullIterator，一個看起來和其他的迭代器差不多，但是hasNext()永遠(yuǎn)返回false，而next()永遠(yuǎn)返回null的迭代器，那么葉子節(jié)點(diǎn)的遍歷也就和其他節(jié)點(diǎn)沒有什么兩樣了。

接下來是樹枝節(jié)點(diǎn)：

Java代碼

1. public class BranchNode extends AbstractNode {
2. public BranchNode(String name) {
3. super(name);
4. }
5.
6. private Collection<Node> childs = new ArrayList<Node>();
7.
8. public void addNode(Node node) {
9. childs.add(node);
10. }
11.
12. public Iterator<Node> iterator() {
13. return childs.iterator();
14. }
15. }

   1. public class BranchNode extends AbstractNode {2.     public BranchNode(String name) {3.         super(name);4.     }5.6.     private Collection<Node> childs = new ArrayList<Node>();7.8.     public void addNode(Node node) {9.         childs.add(node);10.     }11.12.     public Iterator<Node> iterator() {13.         return childs.iterator();14.     }15. }

樹枝節(jié)點(diǎn)可以添加子節(jié)點(diǎn)，葉子節(jié)點(diǎn)或者另外一個樹枝節(jié)點(diǎn)。但是我們注意到，這里的迭代器只是簡單地返回了該節(jié)點(diǎn)直屬子節(jié)點(diǎn)集合的迭代器。什么意思呢？這意味著如果你通過這個迭代器去遍歷這個節(jié)點(diǎn)，你能獲得是只是所有直接添加到這個節(jié)點(diǎn)上的子節(jié)點(diǎn)。要想遞歸地遍歷子節(jié)點(diǎn)的子節(jié)點(diǎn)，以及子節(jié)點(diǎn)的子節(jié)點(diǎn)的子節(jié)點(diǎn)……我們就需要一個特殊的迭代器。

用一個深度優(yōu)先遍歷的迭代器怎么樣？所謂深度優(yōu)先，通俗的講就是沿著一條路走下去，直到走不通為止，再回過頭來看看有沒有別的路可走。

Java代碼

1. public class DepthFirstIterator implements Iterator<Node> {
2.
3. private Stack<Iterator<Node>> stack = new Stack<Iterator<Node>>();
4.
5. public DepthFirstIterator(Iterator<Node> it) {
6. stack.push(it);
7. }
8.
9. public boolean hasNext() {
10. if (stack.isEmpty()) {
11. return false;
12. } else {
13. Iterator<Node> it = stack.peek();
14. if (it.hasNext()) {
15. return true;
16. } else {
17. stack.pop();
18. return hasNext();
19. }
20. }
21. }
22.
23. public Node next() {
24. if (hasNext()) {
25. Iterator<Node> it = stack.peek();
26. Node next = it.next();
27. if (next instanceof BranchNode) {
28. stack.push(next.iterator());
29. }
30. return next;
31. } else {
32. return null;
33. }
34. }
35.
36. public void remove() {
37. throw new UnsupportedOperationException("Can't remove node, yet");
38. }
39. }

   1. public class DepthFirstIterator implements Iterator<Node> {2.3.     private Stack<Iterator<Node>> stack = new Stack<Iterator<Node>>();4.5.     public DepthFirstIterator(Iterator<Node> it) {6.         stack.push(it);7.     }8.9.     public boolean hasNext() {10.         if (stack.isEmpty()) {11.             return false;12.         } else {13.             Iterator<Node> it = stack.peek();14.             if (it.hasNext()) {15.                 return true;16.             } else {17.                 stack.pop();18.                 return hasNext();19.             }20.         }21.     }22.23.     public Node next() {24.         if (hasNext()) {25.             Iterator<Node> it = stack.peek();26.             Node next = it.next();27.             if (next instanceof BranchNode) {28.                 stack.push(next.iterator());29.             }30.             return next;31.         } else {32.             return null;33.         }34.     }35.36.     public void remove() {37.         throw new UnsupportedOperationException("Can't remove node, yet");38.     }39. }

代碼不是很長，理解起來可比較費(fèi)勁。這不僅是因?yàn)槲液軕袥]有寫注釋，更是因?yàn)橛锌蓯旱倪f歸在。先從構(gòu)造函數(shù)看起，一個包含了迭代器的構(gòu)造函數(shù)，也就是說，這是個迭代器的迭代器……這該怎么理解呢？可以把它理解成樹枝節(jié)點(diǎn)迭代器的一個改良的迭代器。樹枝節(jié)點(diǎn)的迭代器只知道如何找到第一級子節(jié)點(diǎn)，而這個迭代器則可以沿著子節(jié)點(diǎn)一直尋找下去，直到找到葉子節(jié)點(diǎn)，然后再返回來繼續(xù)尋找。好吧，說起來簡單，怎么做呢？

先看如何找到“下一個”節(jié)點(diǎn)吧，看next()方法：

如果存在下一個節(jié)點(diǎn)，那么開始下一個節(jié)點(diǎn)的尋找之旅。否則返回null結(jié)束。

首先，通過樹枝節(jié)點(diǎn)自帶的迭代器，找到樹枝節(jié)點(diǎn)的第一個子節(jié)點(diǎn)，這個子節(jié)點(diǎn)就是我們要找的“第一個” 節(jié)點(diǎn)。這很簡單，對吧？那么下一個節(jié)點(diǎn)是哪一個？這取決于我們找到的第一個節(jié)點(diǎn)是什么類型，如果是葉子節(jié)點(diǎn)，那么很簡單，下一個節(jié)點(diǎn)跟樹枝節(jié)點(diǎn)迭代器定義的下一個節(jié)點(diǎn)一樣，也就是樹枝節(jié)點(diǎn)的第二個直屬子節(jié)點(diǎn)。如果是樹枝節(jié)點(diǎn)呢？這個時候它將被當(dāng)成一個新的起點(diǎn)，被壓入堆棧，下一次遍歷將從這個節(jié)點(diǎn)開始重復(fù)上面的邏輯，也就是遞歸。聽起來并不復(fù)雜，不是嗎？

讓我們來一個例子，如果我們要遍歷這樣一棵樹

Java代碼

# /**
# * Create a tree like this
# * Root
# * / | \
# * A B C
# * / \
# * D F
# * /
# * E
# *
# * @return The tree
# */
# static Node createTree() {
# Node root = new BranchNode("Root");
# Node a = new BranchNode("A");
# Node b = new LeafNode("B");
# Node c = new BranchNode("C");
# Node d = new BranchNode("D");
# Node e = new LeafNode("E");
# Node f = new LeafNode("F");
#
# a.addNode(d);
# d.addNode(e);
#
# c.addNode(f);
#
# root.addNode(a);
# root.addNode(b);
# root.addNode(c);
# return root;
# }

# /**#      * Create a tree like this#      *          Root#      *          /  |   #      *         A  B    C#      *        /            #      *       D             F#      *      /#      *     E#      *#      * @return The tree#      */#     static Node createTree() {#         Node root = new BranchNode("Root");#         Node a = new BranchNode("A");#         Node b = new LeafNode("B");#         Node c = new BranchNode("C");#         Node d = new BranchNode("D");#         Node e = new LeafNode("E");#         Node f = new LeafNode("F");##         a.addNode(d);#         d.addNode(e);##         c.addNode(f);##         root.addNode(a);#         root.addNode(b);#         root.addNode(c);#         return root;#     }

從根節(jié)點(diǎn)Root開始遍歷，第一個子節(jié)點(diǎn)，也就是Root自己的第一個直屬子節(jié)點(diǎn)，是A。下一個呢？因?yàn)锳是一個樹枝節(jié)點(diǎn)，所以我們把它先壓入堆棧。下一次從A開始，我們可以把從A開始的子節(jié)點(diǎn)遍歷看成一次全新的遍歷，所以A的第一個子節(jié)點(diǎn)是什么呢？D！很簡單不是？然后是E。因?yàn)镋沒有子節(jié)點(diǎn)，所以我們返回找D的下一個子節(jié)點(diǎn)，但是D除了E是它的子節(jié)點(diǎn)之外，沒有另外的子節(jié)點(diǎn)了。所以D也沒有子節(jié)點(diǎn)了，又返回到A。A也沒有多余的子節(jié)點(diǎn)了，所以這個時候輪到B……

所以，最終的順序是Root -> A -> D -> E -> B -> C -> F。

回過頭來看看hasNext()做了什么。還記得嗎？我們把每一個遇到的樹枝節(jié)點(diǎn)壓入堆棧，當(dāng)堆棧中不存在任何的樹枝節(jié)點(diǎn)時，遍歷就完成了。如果有，我們就取出一個，看它是不是還有子節(jié)點(diǎn)，如果有，那么我們就說還有下一個節(jié)點(diǎn)。如果沒有了，那我們就取出堆棧中的下一個樹枝節(jié)點(diǎn)，并以這個樹枝節(jié)點(diǎn)為起點(diǎn)，看是否存在下一個節(jié)點(diǎn)。

試試這個迭代器威力如何：

Java代碼

1. static void depthFirstIterate(Node tree) {
2. doSomething(tree);
3. for (Iterator<Node> it = new DepthFirstIterator(tree.iterator()); it.hasNext();) {
4. doSomething(it.next());
5. }
6. }

   1. static void depthFirstIterate(Node tree) {2.         doSomething(tree);3.         for (Iterator<Node> it = new DepthFirstIterator(tree.iterator()); it.hasNext();) {4.             doSomething(it.next());5.         }6.     }

如果doSomething(Node node)只是簡單地打印這個節(jié)點(diǎn)，像這樣：

Java代碼

1. static void doSomething(Node node) {
2. System.out.println(node);
3. }

   1. static void doSomething(Node node) {2.         System.out.println(node);3.     }

那么你可以看到前面所述的順序被打印出來 Root -> A -> D -> E -> B -> C -> F。當(dāng)然，沒有箭頭，而且是分行顯示的。

好的，這看起來確實(shí)不錯，那么廣度優(yōu)先遍歷呢？所謂廣度優(yōu)先，通俗來講就是層層推進(jìn)。首先遍歷所有的第一級子節(jié)點(diǎn)，然后是第二層，第三層……結(jié)果就像是這樣：Root -> A -> B -> C -> D -> F -> E

聽起來更加簡單，是不是？事實(shí)上做起來并不簡單，除非你已經(jīng)正確理解了上面深度優(yōu)先遍歷。

如果你理解了深度優(yōu)先遍歷，那么廣度優(yōu)先遍歷和深度優(yōu)先唯一不同的地方就是樹枝節(jié)點(diǎn)的存取順序。在深度優(yōu)先遍歷中，樹枝節(jié)點(diǎn)使用堆棧，存取順序是后進(jìn)先出。先就是說，最后遇到（也就是后進(jìn)）的樹枝節(jié)點(diǎn)先拿出來用（就像插隊(duì)一樣，不得不承認(rèn)這有點(diǎn)不公平）。那么，我們最先遇到的樹枝節(jié)點(diǎn)是Root自己，然后是A，最后是D（不是E，因?yàn)镋不是樹枝節(jié)點(diǎn)）。根據(jù)后進(jìn)先出的原則，我們先把D拿出來遍歷，最終得到D的子節(jié)點(diǎn)是E。然后是A，最后才是Root，所以Root的第二個子節(jié)點(diǎn)B會在Root的第一個子節(jié)點(diǎn)遍歷完成之后才能遍歷到。

所以，只要我們將堆棧換成公平的強(qiáng)力支持者，先進(jìn)先出的隊(duì)列（Queue），問題就解決了：

因?yàn)镽oot最先進(jìn)入隊(duì)列，所以它的所有直屬子節(jié)點(diǎn)會被先遍歷，然后才輪到A，然后是C，然后是D。所以最終順序會是這樣：

Root -> A -> B -> C -> D -> F -> E

廣度優(yōu)先代碼：

Java代碼

1. public class BreadthFirstIterator implements Iterator<Node> {
2.
3. private Queue<Iterator<Node>> queue = new LinkedList<Iterator<Node>>();
4.
5. public BreadthFirstIterator(Iterator<Node> it) {
6. queue.offer(it);
7. }
8.
9. public boolean hasNext() {
10. if (queue.isEmpty()) {
11. return false;
12. } else {
13. Iterator<Node> it = queue.peek();
14. if (it.hasNext()) {
15. return true;
16. } else {
17. queue.poll();
18. return hasNext();
19. }
20. }
21. }
22.
23. public Node next() {
24. if (hasNext()) {
25. Iterator<Node> it = queue.peek();
26. Node next = it.next();
27. if (next instanceof BranchNode) {
28. queue.offer(next.iterator());
29. }
30. return next;
31. } else {
32. return null;
33. }
34. }
35.
36. public void remove() {
37. throw new UnsupportedOperationException("Can't remove node, yet");
38. }
39. }

   1. public class BreadthFirstIterator implements Iterator<Node> {2.3.     private Queue<Iterator<Node>> queue = new LinkedList<Iterator<Node>>();4.5.     public BreadthFirstIterator(Iterator<Node> it) {6.         queue.offer(it);7.     }8.9.     public boolean hasNext() {10.         if (queue.isEmpty()) {11.             return false;12.         } else {13.             Iterator<Node> it = queue.peek();14.             if (it.hasNext()) {15.                 return true;16.             } else {17.                 queue.poll();18.                 return hasNext();19.             }20.         }21.     }22.23.     public Node next() {24.         if (hasNext()) {25.             Iterator<Node> it = queue.peek();26.             Node next = it.next();27.             if (next instanceof BranchNode) {28.                 queue.offer(next.iterator());29.             }30.             return next;31.         } else {32.             return null;33.         }34.     }35.36.     public void remove() {37.         throw new UnsupportedOperationException("Can't remove node, yet");38.     }39. }

可以看到代碼和深度優(yōu)先遍歷幾乎完全一樣，除了把堆棧（Stack）換成了隊(duì)列（Queue）

參考了《HeadFirst設(shè)計(jì)模式》

本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊舉報。

国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看