102      阿裏雲  技術社區[雲棲]

《數據結構與抽象：Java語言描述（原書第4版）》一 引　言-組 織 數 據

本節書摘來華章計算機《數據結構與抽象：Java語言描述（原書第4版）》一書中的第1章 ，［美］弗蘭克M.卡拉諾（Frank M. Carrano）　蒂莫西M.亨利（Timothy M. Henry） 著 羅得島大學　 新英格蘭理工學院 辛運幃　饒一梅　譯 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。

引　言

Data Structures and Abstractions with Java, Fourth Edition

組 織 數 據

環顧四周，你就會發現人們安排事情的方式。早晨去商店時，你會站在線後等待付賬。這條線會讓人們按先來後到的次序排隊。線後的第一個人是最先得到服務的人，也是最先離開隊列的人。最終，你到達線前，結賬後拿著你購買的一包物品離開商店。包裏的東西沒有特別的次序，且有些還是一樣的。
你看到桌子上的一摞書或一疊紙了嗎？很容易看到或拿走一摞東西最上麵的一件，或者在一摞東西上麵放一件新的東西。一摞東西也是按時間順序組織的，最後放的在最上麵，最先放的在最下麵。
在桌子上，可以看到做事清單。清單中的每一項對你或重要或不重要。寫這些項時，可能是按照它們的重要性排列的，也可能是按照字母序排列的。這個次序是你定的，清單隻是寫這些項的地方。
字典是單詞及其定義的字母序列表。你在裏麵查找一個單詞從而得到它的定義。如果你的字典是紙製印刷的，則字母序的組織方式能幫助你快速找到這個單詞。如果你的字典是電子版的，則字母序的組織方式是隱式的，但它仍然能加快查找過程。
再來看計算機，文件是放到文件夾（或稱目錄）中的。每個文件夾又包含若幹其他的文件夾或文件。這種組織類型是層次的。如果將它畫成圖，會得到一個類似家族樹或公司內部部門圖的東西。數據的這些組織方式是類似的，稱為樹。
最後來看看道路地圖，你正用它來規劃周末遊。道路和城市的地圖向你展示如何從一個地方到達另一個地方。通常會有幾條不同的路。一條路可能路程更短些，另一條路可能所需時間更短。地圖的組織方式稱為圖。

計算機程序也需要組織它們的數據，其組織方式類似於我們剛剛引用的例子，即程序可以使用棧、線性表、字典等。這些數據組織的方式表示為抽象數據類型。抽象數據類型（Abstract Data Type，ADT）是描述數據集（set）及數據上操作的規格說明。每個ADT說明存儲什麼數據及對數據進行什麼操作。因為ADT不明示如何保存數據，也不說明如何實現操作，所以我們可以脫離程序設計語言來談論ADT。相比之下，數據結構（data structure）是某種程序設計語言中ADT的一種實現。
集合（collection）是一個一般術語，是指包含一組對象的ADT。有些集合允許有重複項，而有些則不允許有重複項。
我們可以創建一個ADT包（bag），它由一個無序集合構成，其中允許有重複值。它好像是一個雜貨店的袋子、一個午餐袋，或一個薯片袋。假定從薯片袋中拿出一片。你不知道薯片何時放入袋中。你不知道袋子中是否有另一片薯片，它的形狀與剛拿走的那片一模一樣。但你真的不在意這個。如果在意，就不會將薯片放入袋子中！
袋子中的物品沒有次序，但有時你想讓它們有次序。ADT可以以多種方式排列項的次序。例如，ADT線性表（list）對項進行編號。這樣，線性表有第一項、第二項等。雖然可以將項添加到線性表的表尾，但也可以將項添加到線性表的表頭，或者在兩項的中間。這樣操作後新加項後麵的項需要重新編號。另外，可以刪除線性表指定位置的項。所以線性表中項的位置並不能表明這個項是何時添加進來的。注意，線性表不決定項的放置位置。這件事由你來決定。
相反，ADT棧（stack）和隊列（queue）按時間確定項的次序。當從棧中刪除項時，刪除的是最後添加的項。當從隊列中刪除項時，刪除的是最早添加的項。所以，棧像是一摞書。你可以拿走最上麵的書，或者將另一本書放在這摞書的上麵。隊列像是一隊人。人從隊列前頭離開，站隊時站到最後。
如果項可以進行比較，有些ADT按排列的次序管理項。例如，字符串可以按字母序組織。例如，當在ADT有序表（sorted list）中添加項時，由ADT來確定這個項在有序表中的位置。你不用指明這個項的位置，而在ADT線性表中需要指明。
ADT字典（dictionary）含有項對，很像是字典中含有的單詞及其定義。在這個例子中，單詞充當關鍵字（key），用它來查找項。有些字典對項進行排序，有些字典沒有排序。
ADT樹（tree）根據層次組織項。例如，在家族樹中，人與其孩子和父母相關聯。ADT二叉查找樹（binary search tree）按照層次和排序來組織項，這使得項的查找更容易。
ADT圖（graph）是ADT樹的推廣，它按照項之間的關係而不是層次來組織。例如，道路圖是一個圖，展示的是城鎮之間已有的道路和距離。
本書介紹如何使用並實現這些數據組織方式。本書假定你已經了解了Java，如果需要複習這方麵的知識，附錄對你很有用。附錄A概述了編寫適用於javadoc注釋的方法。附錄B複習了Java的基本語句。附錄C討論了類和方法的基礎結構。附錄D介紹了組成與繼承的要點。最後，附錄E介紹讀和寫外部文件的方法。附錄B、C和E在本書的網站上（pearsonhighered.com/carrano）也能找到。可以根據需要下載並參考這些資料。本書中稱為“Java插曲”的章節，集中討論了與Java相關的內容，這些內容對你可能是全新的，包括如何處理異常。後麵的序言中討論了如何設計類、說明方法，以及寫Java接口。使用接口和編寫注釋來說明方法，都是介紹ADT不可缺少的部分。

最後更新：2017-06-26 14:02:08

  上一篇：  《數據結構與抽象：Java語言描述（原書第4版）》一序　言-設　計　類

  下一篇：  《偉大的計算原理》一導讀