導讀

為什麼要學習數據結構？

數據結構是關於如何組織（存儲）數據的！編程實踐中經常涉及到組織（存儲）數據，所以要學習數據結構。

那麼為啥還要學習抽象數據類型（Abstract Data Type，ADT）呢？

ADT描述了數據集、指明瞭在數據集上可能執行的操作。ADT是一種規範，它和具體的編程語言無關。儘管Java API提供多種數據結構，但是如果遇到不適用的情形，就需要針對這種情形定義ADT，然後使用Java實現它。況且如果不深入全面地掌握數據結構這方面的知識，就無法理解和合理的使用Java API提供的數據結構。

數據結構和ADT是什麼關係呢？

ADT是一個規範，用於一組值以及對這組值執行的操作。而數據結構是使用編程語言對ADT的實現。

那麼如何描述ADT呢？

我們僅描述數據和操作，不指明如何保存數據以及如何實現操作，會考慮一些實現的細節，但與具體編程語言無關。

我們藉助UML以及對他們的說明來描述ADT。還可以使用偽代碼，不過UML足以說明問題。

設計ADT的步驟是什麼呢？

確定行為，然後指定數據和操作，並且考慮特殊情況。

ADT Dictionary（字典）簡介

生活中有許多字典或詞典。從小學起我們開始學習查閱新華字典，到了高年級我們開始翻閱英漢詞典，慢慢的我們開始使用辭海，再往後，我們又或多或少的接觸了一些專業詞典，字典伴隨了我們一生。我們給字典或詞典下個通俗的定義，它是一類帶有目錄的，為字或詞給出釋義，有可能還提供例句的工具書。

數據結構中的字典與之相是，也是有“目錄”，我們稱之為鍵。

我們根據目錄在字典或詞典中查字或詞的釋義，同樣地，我們也根據鍵查找鍵對應的值。

字典（dictionary）又被稱為映射（map）、表（table）、關聯數組（asociative array） 。

ADT Dictionary（字典）的規格說明

ADT Dictionary（字典）操作細節闡述

ADT Dictionary的鍵不能為null，值可以為null，null表示什麼都沒有，如果讓一個鍵是null，將是矛盾的。其實，值為null也不是一個好的策略。鍵存在而值不存在，這種表達在現實生活種代表了一種錯誤，譬如，你在字典的目錄中找到了一個字的索引，按照索引的指示卻無法找到對應的詞條，那麼一定是字典印刷錯誤。

ADT Dictionary可以有重複的鍵和值，但是如果你在規格說明中要求字典的鍵是不可以重複的，這也是合理的，那麼針對這兩種情況就要分別加以說明。

鍵不能重複

如果要求鍵不能重複，那麼add方法的前置條件還要加一條：當插入鍵已存在於字典中，那麼插入操作無效。或者你也可以拋出異常，說明鍵已存在，不過拋出異常似乎不是一種好策略，當鍵重複時，我們只需讓插入操作不生效便可，如果此時拋出異常，客戶端還要處理這種異常，而客戶端完全不必處理這種異常。

鍵可重複

對於鍵可重複的詞典來說，getValue方法根據鍵找到的值可能不止一個，那麼上面列舉的getValue方法就不合適了，因為上面列舉的getValue方法返回一個值，而在鍵可重複的情形下應該返回一個集合。

設計模式:迭代器模式

getKeyIterator和getValueIterator都返回迭代器，這兩個方法也可以返回鍵或值數組，然後用數組下標訪問，那麼迭代器優勢在哪呢？

首先簡要闡述一下迭代器模式（以下概念來自於《設計模式：可複用面向對象軟件的基礎》）。

1 定義

提供一種方法順序訪問一個聚合對象中的各個元素，而又不需暴露該對象的內部表示。

2 適用性

1）訪問一個聚合對象的內容而無需暴露它的內部表示。

2）支持對聚合對象的多種遍歷。

3）為遍歷不同的聚合結構提供一個統一的接口（即，支持多態迭代）。

3 結構

說明：

1）Iterator：迭代器定義訪問和遍歷元素的接口。

First使迭代器指向聚合的第一個元素。

Next使迭代器指向當前元素的下一個元素

IsDone檢查當前元素的索引是否超出聚合的範圍

CurrentItem返回當前索引對應的元素

2）ConcreteIterator：具體迭代器實現迭代器接口。對該聚合遍歷時跟蹤當前位置。

3）Aggregate：聚合定義創建相應迭代器對象的接口。

4）ConcreteAggregate：具體聚合實現創建相應迭代器的接口，該操作返回ConcreteIterator的一個適當的實例。

迭代器模式的適用性也是他的效果或重要的作用。這樣看來迭代器比起Java提供的其他幾種實現迭代的語法要更有優勢。

ADT Dictionary（字典）轉換為接口

轉換的過程中使用了迭代器，我們看一下Java定義的迭代器接口，與上面迭代器模式中的接口稍有不同。先不看其定義的默認方法，hasNext相當於上面模式中的IsDone，而Iterator接口中沒有定義First方法。

interface Iterator{

boolean hasNext();

E next();

default void remove(){

throw new UnsupportedOerationException();

}

default void forEachRemaining(Consumer super E> action) {

Objects.requireNonNull(action);

while (hasNext())

action.accept(next());

}

}