原文鏈接：Part 1: An Introduction to Data Structures

介紹:
本文是介紹在.Net平臺下使用數(shù)據(jù)結(jié)構(gòu)的系列文章,共分為六部分,這是本文的第一部分.本文試圖考察幾種數(shù)據(jù)結(jié)構(gòu),其中有的包含在.Net Framework的基類庫中,有的是我們自己創(chuàng)建的.如果你對這些名詞不太熟悉,那么我們可以把數(shù)據(jù)結(jié)構(gòu)看作是一種抽象結(jié)構(gòu)或是類,它通常用來組織數(shù)據(jù),并提供對數(shù)據(jù)的操作.最常見并為我們所熟知的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組array,它包含了一組連續(xù)的數(shù)據(jù),并通過索引進(jìn)行訪問.

在閱讀本文內(nèi)容之前,讓我們先看看這六部分的主要內(nèi)容.如果你有什么想法,或覺得本文有什么遺漏之處,希望你通過e-mail(mitchell@4guysfromrolla.com)和我聯(lián)系,共同分享你的思想.假如有時間的話,我很高興將你的建議放到合適的部分,如有必要,可以在這篇系列文章中加上第七部分.

第一部分:首先介紹數(shù)據(jù)結(jié)構(gòu)在算法設(shè)計中的重要性.決定數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣在于其性能.我們將經(jīng)過嚴(yán)格分析數(shù)據(jù)結(jié)構(gòu)的各種性能.此部分還將介紹.Net Frameword下兩種常用的數(shù)據(jù)機(jī)構(gòu):Array 和ArrayList.我們將考察其結(jié)構(gòu)的操作方式及其效率.

第二部分:我們將繼續(xù)從更多細(xì)節(jié)上分析ArrayList結(jié)構(gòu),同時還將介紹Queue類和Stack類.和ArrayList一樣,Queue和Stack存放的都是一組連續(xù)的數(shù)據(jù)集合,都屬于.Net Framework基類庫.與ArrayList不同的是,Stack和Queue只能以預(yù)先規(guī)定的序列順序讀取其數(shù)據(jù)(先進(jìn)先出和先進(jìn)后出),而ArrayList可以任意獲取數(shù)據(jù)項.我們將通過示例程序來考察Queue,Stack,并通過擴(kuò)展ArrayList類來實現(xiàn)它們.之后,我們還要分析哈希表HashTable,它象ArrayList一樣可以直接訪問數(shù)據(jù),不同的是它以key(字符串)為索引.

ArrayList對數(shù)據(jù)直接讀取和存儲是一種理想的數(shù)據(jù)結(jié)構(gòu),同時,它也是支持?jǐn)?shù)據(jù)搜索的候選方案.在第三部分,我們將考察二叉樹結(jié)構(gòu),對于數(shù)據(jù)搜索而言,它比ArrayList更加有效. .Net Framework并不包含此種內(nèi)置數(shù)據(jù)結(jié)構(gòu),因此需要我們自己創(chuàng)建.

二叉樹搜索的效率受制于插入到樹中的數(shù)據(jù)的順序.如果我們插入的是有序或近似有序的數(shù)據(jù),實際上,它的效率不如ArrayList.為了將這兩種的優(yōu)勢結(jié)合起來,在第四部分,我門將考察一種有趣的隨機(jī)數(shù)據(jù)結(jié)構(gòu)——SkipList. SkipList既保留了二叉樹搜索的高效率,同時輸入數(shù)據(jù)的順序?qū)ζ湫视绊懮跷?

第五部分我們將注意力轉(zhuǎn)向通常用來表現(xiàn)圖形的數(shù)據(jù)結(jié)構(gòu).圖(graph)是眾多節(jié)點以及節(jié)點之間邊的集合.舉例來說,地圖就可以圖的形式來表現(xiàn).城市是節(jié)點,公路則是連接節(jié)點之間的邊.許多現(xiàn)實問題都可以抽象成圖的形式,因此,圖也是我們經(jīng)常要用到的數(shù)據(jù)結(jié)構(gòu).

最后,第六部分我們將談到reprisent sets(表示集?)和disjoint sets(非關(guān)聯(lián)集,即交集為空?)集合是一種無序數(shù)據(jù)的集中.非關(guān)聯(lián)集是指它和另外一個集合沒有共同的元素.我們在程序編寫時會經(jīng)常用到集合和非關(guān)聯(lián)集.我們將在這一部分中詳細(xì)描述它.

在這篇系列文章中，我們將計算每一種新的數(shù)據(jù)結(jié)構(gòu)和它們的漸進(jìn)操作運行時間，并通過相似的操作比較其他數(shù)據(jù)結(jié)構(gòu)在運行時間上的區(qū)別。

數(shù)組：一種線形的，可以直接訪問的，單一數(shù)據(jù)結(jié)構(gòu)

在程序編寫中，數(shù)組是最簡單也是最廣泛使用的數(shù)據(jù)結(jié)構(gòu)。在所有的程序語言中數(shù)組都具備以下共同的屬性：
1．?dāng)?shù)組的數(shù)據(jù)存儲在一段連續(xù)的內(nèi)存之中；
2．?dāng)?shù)組的所有元素都必須是同一種數(shù)據(jù)類型，因此數(shù)組又被認(rèn)為是單一數(shù)據(jù)結(jié)構(gòu)(homogeneous data structures)；
3．?dāng)?shù)組元素可以直接訪問。（在很多數(shù)據(jù)結(jié)構(gòu)中，這一特點是不必要的。例如，文章第四部分介紹的數(shù)據(jù)結(jié)構(gòu)SkipList。要訪問SkipList中的特定元素，你必須根據(jù)搜索其他元素直到找到搜索對象為止。然而對于數(shù)組而言，如果你知道你要查找第i個元素，就可以通過arrayName[i]來訪問它。）（譯注：很多語言都規(guī)定數(shù)組的下標(biāo)從0開始，因此訪問第i個元素，應(yīng)為arrayName[i-1]）

以下是數(shù)組常用的操作：
1．分配空間
2．?dāng)?shù)據(jù)訪問
3．?dāng)?shù)組空間重分配（Redimensioning）

在C#里聲明數(shù)組時，數(shù)組為空值（null）。下面的代碼創(chuàng)建了一個名為booleanArray的數(shù)組變量，其值為空（null）：

Bool [] boolleanArray;

在使用該數(shù)組時，必須用一個特定數(shù)字給它分配空間，如下所示：

booleanArray = new bool[10];

通用的表述為：

arrayName = new arrayType[allocationSize];

它將在CLR托管堆里分配一塊連續(xù)的內(nèi)存空間，足以容納數(shù)據(jù)類型為arrayTypes、個數(shù)為allocationSize的數(shù)組元素。如果arrayType為值類型（譯注：如int類型），則有allocationSize個未封箱（unboxed）的arrayType值被創(chuàng)建。如果arrayType為引用類型(譯注：如string類型)，則有allocationSize個arrayType引用類型值被創(chuàng)建。（如果你對值類型和引用類型、托管堆和棧之間的區(qū)別不熟悉，請查閱“理解.Net公共類型系統(tǒng)Common Type System”）

為幫助理解.Net Framework中數(shù)組的內(nèi)部存儲機(jī)制，請看下面的例子：

arrayName = new arrayType[allocationSize];

This allocates a contiguous block of memory in the CLR-managed heap large enough to hold the allocationSize number of arrayTypes. If arrayType is a value type, then allocationSize number of unboxed arrayType values are created. If arrayType is a reference type, then allocationSize number of arrayType references are created. (If you are unfamiliar with the difference between reference and value types and the managed heap versus the stack, check out Understanding .NET‘s Common Type System.)

To help hammer home how the .NET Framework stores the internals of an array, consider the following example:

bool [] booleanArray;
FileInfo [] files;

booleanArray = new bool[10];
files = new FileInfo[10];

這里，booleanArray是值類型System.Boolean數(shù)組，而files數(shù)組則是引用類型System.IO.FileInfo數(shù)組。圖一顯示了執(zhí)行這四行代碼后CLR托管堆的情況。

 
 
圖一：在托管堆中順序存放數(shù)組元素

請記住在files數(shù)組中存放的十個元素指向的是FileInfo實例。圖二強(qiáng)調(diào)了這一點（hammers home this point，有些俚語的感覺，不知道怎么翻譯），顯示了如果我們?yōu)閒iles數(shù)組中的FileInfo實例分配一些值后內(nèi)存的分布情況。
 

圖二：在托管堆中順序存放數(shù)組元素

.Net中所有數(shù)組都支持對元素的讀寫操作。訪問數(shù)組元素的語法格式如下：

// 讀一個數(shù)組元素
bool b = booleanArray[7];

// 寫一個數(shù)組元素，即賦值
booleanArray[0] = false;

訪問一個數(shù)組元素的運行時間表示為O(1)，因為對它的訪問時間是不變的。那就是說，不管數(shù)組存儲了多少元素，查找一個元素所花的時間都是相同的。運行時間之所以不變，是因為數(shù)組元素是連續(xù)存放的，查找定位的時候只需要知道數(shù)組在內(nèi)存中的起始位置，每個元素的大小，以及元素的索引值。

在托管代碼中，數(shù)組的查找比實際的實現(xiàn)稍微復(fù)雜一些，因為在CLR中訪問每個數(shù)組，都要確保索引值在其邊界之內(nèi)。如果數(shù)組索引超出邊界，會拋出IndexOutOfRangeException異常。這種邊界檢查有助于確保我們在訪問數(shù)組不至于意外地超出數(shù)組邊界而進(jìn)入另外一塊內(nèi)存區(qū)。而且它不會影響數(shù)組訪問的時間，因為執(zhí)行邊界檢查所需時間并不隨數(shù)組元素的增加而增加。

注：如果數(shù)組元素特別多，索引邊界檢查會對應(yīng)用程序的執(zhí)行性能有稍許影響。而對于非托管代碼，這種邊界檢查就被忽略了。要了解更多信息，請參考Jeffrey Richter所著的Applied Microsoft .NET Framework Programming第14章。

使用數(shù)組時，你也許需要改變數(shù)組大小?？梢酝ㄟ^根據(jù)特定的長度大小創(chuàng)建一個新數(shù)組實例，并將舊數(shù)組的內(nèi)容拷貝到新數(shù)組，來實現(xiàn)該操作。我們稱這一過程為數(shù)組空間重分配(redimensioning)，如下代碼：

using System;
using System.Collections;

public class MyClass
{
   public static void Main()
   {
      // 創(chuàng)建包含3個元素的int類型數(shù)組
      int [] fib = new int[3];
      fib[0] = 1;
      fib[1] = 1;
      fib[2] = 2;
     
      // 重新分配數(shù)組，長度為10
      int [] temp = new int[10];

// 將fib數(shù)組內(nèi)容拷貝到臨時數(shù)組
      fib.CopyTo(temp, 0);
     
      // 將臨時數(shù)組賦給fib
      fib = temp;  
   }
}

在代碼的最后一行，fib指向包含10個元素的Int32類型數(shù)組。Fib數(shù)組中3到9（譯注：注意下標(biāo)從0開始）的元素值默認(rèn)為0（Int32類型）。

當(dāng)我們要存儲同種類型的數(shù)據(jù)（原文為heterogeneous types——異類數(shù)據(jù)類型，我懷疑有誤）并僅需要直接訪問數(shù)據(jù)時，數(shù)組是較好的數(shù)據(jù)結(jié)構(gòu)。搜索未排序的數(shù)組時間復(fù)雜度是線形的。當(dāng)我們對小型數(shù)組進(jìn)行操作，或很少對它進(jìn)行查詢操作時，數(shù)組這種結(jié)構(gòu)是可以接受的。但當(dāng)你的應(yīng)用程序需要存儲大量數(shù)據(jù)，且頻繁進(jìn)行查詢操作時，有很多其他數(shù)據(jù)結(jié)構(gòu)更能適應(yīng)你的工作。我們來看看本文接下來將要介紹的一些數(shù)據(jù)結(jié)構(gòu)。（如果你要根據(jù)某個屬性查找數(shù)組，且數(shù)組是根據(jù)該屬性進(jìn)行排序的，你可以使用二叉法（binary search）對其搜索，它的時間復(fù)雜度為O(log n)，與在二叉樹中搜索的時間復(fù)雜度相同。事實上，數(shù)組類中包含了一個靜態(tài)方法BinarySearch()。如要了解該方法的更多信息，請參考我早期的一篇文章“有效地搜索有序數(shù)組”。

注：.Net Framework同樣支持多維數(shù)組。與一維數(shù)組一樣，多維數(shù)組對數(shù)據(jù)元素的訪問運行時間仍然是不變的?；叵胍幌挛覀兦懊娼榻B的在n個元素的一維數(shù)組中查詢操作的時間復(fù)雜度為O(n)。對于一個nxn的二維數(shù)組，時間復(fù)雜度為O(n2)，因為每次搜索都要檢查n2個元素。以此類推，k維數(shù)組搜索的時間復(fù)雜度為O（nk）。

ArrayList：可存儲不同類型數(shù)據(jù)、自增長的數(shù)組

明確地，數(shù)組在設(shè)計時受到一些限制，因為一維數(shù)組只能存儲相同類型的數(shù)據(jù)，而且在使用數(shù)組時，必須為數(shù)組定義特定的長度。很多時候，開發(fā)人員要求數(shù)組更加靈活，它可以存儲不同類型的數(shù)據(jù)，也不用去關(guān)心數(shù)組空間的分配。在.Net Framework基類庫中提供了滿足這樣條件的數(shù)據(jù)結(jié)構(gòu)——System.Collections.ArrayList。

如下的一小段代碼是ArrayList的示例。注意到使用ArrayList時可以添加任意類型的數(shù)據(jù)，且不需要分配空間。所有的這些都由系統(tǒng)控制。

ArrayList countDown = new ArrayList();
countDown.Add(5);
countDown.Add(4);
countDown.Add(3);
countDown.Add(2);
countDown.Add(1);
countDown.Add("blast off!");
countDown.Add(new ArrayList());

從深層次的含義來講，ArrayList使用的存放類型為object的System.Array對象。既然所有類型都是直接或間接從object派生，自然一個object類型的數(shù)組也可以存放任何類型的元素。ArrayList默認(rèn)創(chuàng)建16個object類型元素的數(shù)組，當(dāng)然我們也可以通過構(gòu)造函數(shù)中的參數(shù)或設(shè)置Capacity屬性來定制ArrayList大小。通過Add()方法添加新元素，數(shù)組內(nèi)部自動檢查其容量。如果添加新元素導(dǎo)致越界，則容量則自動成倍增加，我們稱為自增長。

ArrayList和Array一樣，也可以通過索引直接訪問：

// Read access
int x = (int) countDown[0];
string y = (string) countDown[5];

// Write access
countDown[1] = 5;

// 會產(chǎn)生ArgumentOutOfRange 異常
countDown[7] = 5;

既然ArrayList存儲的是object類型的元素，因此從ArrayList中讀元素時應(yīng)該顯示的指定類型轉(zhuǎn)換。同時要注意的是，如果你訪問的數(shù)組元素超過ArrayList的長度，系統(tǒng)會拋出System.ArgumentOutOfRange異常。

ArrayList提供了標(biāo)準(zhǔn)數(shù)組所不具備的自增長靈活性，但這種靈活性是以犧牲性能為代價的，尤其是當(dāng)我們存儲的是值類型——例如System.Int32，System.Double，System.Boolean等。它們在托管堆中是以未封箱形式(unboxed form)連續(xù)存放的。然而，ArrayList的內(nèi)部機(jī)制是一個引用的object對象數(shù)組；因此，即使ArrayList中只存放了值類型，這些元素仍然會通過封箱（boxing）轉(zhuǎn)換為引用類型。如圖三所示：
 

圖三：存儲連續(xù)塊的object引用的ArrayList

在ArrayList中使用值類型，將額外進(jìn)行封箱(boxing)和撤箱(unboxing)操作，當(dāng)你的應(yīng)用程序是一個很大的ArrayList，并頻繁進(jìn)行讀寫操作時，會很大程度上影響程序性能。如圖3所示，對于引用類型而言，ArrayList和數(shù)組的內(nèi)存分配是相同的。

比較數(shù)組而言，ArrayList的自增長并不會導(dǎo)致任何性能的下降。如果你知道存儲到ArrayList的元素的準(zhǔn)確數(shù)量，可以通過ArrayList構(gòu)造函數(shù)初始化容量以關(guān)閉其自增長功能。而對于數(shù)組，當(dāng)你不知道具體容量時，不得不在插入的數(shù)據(jù)元素超過數(shù)組長度的時候，手動改變數(shù)組的大小。

一個經(jīng)典的計算機(jī)科學(xué)問題是：當(dāng)程序運行時超出了緩存空間，應(yīng)該分配多少新的空間為最佳。一種方案是是原來分配空間的基礎(chǔ)上每次加1。例如數(shù)組最初分配了5個元素，那么在插入第6個元素之前，將其長度增加為6。顯然，這種方案最大程度上節(jié)約了內(nèi)存空間，但代價太大，因為每插入一個新元素都要進(jìn)行一次再分配操作。

另一種方案剛好相反，也就是每次分配都在原來大小的基礎(chǔ)上增加100倍。如果數(shù)組最初分配了5個元素，那么在插入第6個元素之前，數(shù)組空間增長為500。顯然，該方案大大地減少了再分配操作的次數(shù)，但僅當(dāng)插入極少的數(shù)據(jù)元素時，就會有上百的元素空間未使用，實在太浪費空間了！

ArrayList的漸近運行時間和標(biāo)準(zhǔn)數(shù)組一樣。即使對ArrayList的操作是高開銷的，尤其是存儲值類型，其元素個數(shù)和每次操作的代價之間的關(guān)系與標(biāo)準(zhǔn)數(shù)組相同。