【文章內(nèi)容簡(jiǎn)介】 、A集合交叉B集合、A集合聯(lián)合B集和圖17集合操作圖是由節(jié)點(diǎn)集合以及與節(jié)點(diǎn)相連的邊集合組成的。圖用來(lái)對(duì)必須訪問(wèn)圖中每個(gè)節(jié)點(diǎn)的情況進(jìn)行建模，而且有些時(shí)候還要按照特定順序進(jìn)行訪問(wèn)。這樣做的目的是為了找到“遍歷”圖的最有效的方法。圖可用于，也可用于計(jì)算機(jī)科學(xué)和數(shù)學(xué)研究領(lǐng)域。大家可能聽(tīng)說(shuō)過(guò)“旅行商”問(wèn)題。這就是圖問(wèn)題的一種特殊類(lèi)型。此問(wèn)題要求在旅行預(yù)算允許的條件下為需要拜訪路線中所有城市的商人確定最有效的完整旅行路線。此問(wèn)題的實(shí)例圖表示在圖18中。（原書(shū)P10頁(yè)圖）Tokyo:東京、Seattle:西雅圖、LA:洛杉磯、Boston:波士頓、New York:紐約、Washington:華盛頓、London:倫敦、Paris:巴黎、Rome:羅馬、Moscow:莫斯科圖18旅行商問(wèn)題此問(wèn)題是被稱(chēng)為NP完全問(wèn)題的其中一部分內(nèi)容。這就意味著針對(duì)此類(lèi)型的大量問(wèn)題是無(wú)法知道確切解決方案的。例如，為了找到圖18所示問(wèn)題的解決方案，需要檢查10的階乘這么多條線路，這等于是3628800條線路。如果把問(wèn)題擴(kuò)展為100座城市，就需要檢查100的階乘條線路。就目前方法而言是無(wú)法用現(xiàn)在方法實(shí)現(xiàn)的。因此需要找到一種近似的解決方案。網(wǎng)絡(luò)是圖的一種特殊類(lèi)型。網(wǎng)絡(luò)的每一條邊都被賦予了權(quán)。權(quán)同使用某邊從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)所花費(fèi)的代價(jià)相關(guān)。圖19描述了帶權(quán)的城市網(wǎng)絡(luò)，其中這里的權(quán)是兩座城市（節(jié)點(diǎn)）之間的英里數(shù)。（原書(shū)P11頁(yè)圖）圖19網(wǎng)絡(luò)群集至此已經(jīng)對(duì)將要在本書(shū)中討論的不同群集類(lèi)型做了總體的概述。下面就準(zhǔn)備實(shí)際看一看這些群集是如何用C語(yǔ)言實(shí)現(xiàn)的了。 CollectionBase類(lèi).NET框架庫(kù)不包括用于存儲(chǔ)數(shù)據(jù)的通用Collection類(lèi)，但是大家可以使用一種抽象的類(lèi)CollectionBase類(lèi)來(lái)構(gòu)造屬于自己的Collection類(lèi)。CollectionBase類(lèi)為程序員提供了實(shí)現(xiàn)定制Collection類(lèi)的能力。CollectionBase類(lèi)隱含實(shí)現(xiàn)了兩個(gè)為構(gòu)造Collection類(lèi)所必需的接口，即ICollection和IEnumerable，而留給程序員要做的工作就只是對(duì)這些作為Collection類(lèi)特殊內(nèi)容的方法的實(shí)現(xiàn)。本節(jié)將要說(shuō)明如何用C語(yǔ)言來(lái)實(shí)現(xiàn)自身的Collection類(lèi)。這是出于幾種目的考慮。首先，如果大家不是很熟悉面向?qū)ο缶幊蹋∣OP），那么這個(gè)實(shí)現(xiàn)將會(huì)展示一些簡(jiǎn)單的用C語(yǔ)言進(jìn)行面向?qū)ο缶幊痰募记?。其次，就如同討論各種C數(shù)據(jù)結(jié)構(gòu)一樣，此節(jié)內(nèi)容還可用于討論一些將要出現(xiàn)的性能問(wèn)題。最后，就像本書(shū)中其他實(shí)現(xiàn)章節(jié)一樣，本節(jié)內(nèi)容也會(huì)使人獲益良多，因?yàn)閮H僅用語(yǔ)言自身的元素就能重新實(shí)現(xiàn)已存在的數(shù)據(jù)結(jié)構(gòu)實(shí)在是充滿樂(lè)趣的事。正如Don Kunth（計(jì)算機(jī)科學(xué)的先驅(qū)之一）所說(shuō)的那樣，也許只有當(dāng)學(xué)成計(jì)算機(jī)時(shí)才會(huì)真正學(xué)到一些知識(shí)。所以，與從日常編程庫(kù)中選取類(lèi)來(lái)使用相比，通過(guò)講解C語(yǔ)言如何實(shí)現(xiàn)不同數(shù)據(jù)結(jié)構(gòu)的方法將會(huì)使大家學(xué)會(huì)更多關(guān)于這些結(jié)構(gòu)的知識(shí)。在C。此類(lèi)提供了一套可以實(shí)現(xiàn)構(gòu)造自身群集的抽象方法集合。CollectionBase類(lèi)還提供了一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)——InnerList（一個(gè)ArrayList）。此結(jié)構(gòu)可以用作自身類(lèi)的基礎(chǔ)。本章節(jié)會(huì)看到如何使用CollectionBase來(lái)構(gòu)造Collection類(lèi)。彌補(bǔ)Collection類(lèi)的全部方法包括一些與類(lèi)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)InnerList相交互的類(lèi)型。本節(jié)第一部分要實(shí)現(xiàn)的方法是Add方法、Remove方法、Count方法和Clear方法。盡管定義的其他方法可以使類(lèi)更有用，但是上述這些方法是類(lèi)的絕對(duì)基本要素。首先從Add方法開(kāi)始。這種方法有一個(gè)參數(shù)，即Object變量。此變量用來(lái)保存群集要添加的數(shù)據(jù)項(xiàng)。代碼如下所示：public void Add(Object item){ (item)。}ArrayList把數(shù)據(jù)作為對(duì)象（即Object數(shù)據(jù)類(lèi)型）來(lái)存儲(chǔ)。這就是把數(shù)據(jù)項(xiàng)聲明為Object的原因。第2章將會(huì)學(xué)到更多有關(guān)ArrayLists的內(nèi)容。 Remove方法的執(zhí)行與上述類(lèi)似：public void Remove(Object item) { (item)。}接下來(lái)是Count方法。Count最常作為屬性來(lái)實(shí)現(xiàn)，但是這里更喜歡把它用作方法。而且，由于是在基礎(chǔ)類(lèi)CollectionBase中實(shí)現(xiàn)Count，所以必須用新的關(guān)鍵詞來(lái)隱藏在CollectionBase中找到的Count的定義：public new int Count() { return 。}Clear方法把全部數(shù)據(jù)項(xiàng)從InnerList中移除掉。這里也需要在方法定義中使用新的關(guān)鍵詞：public new void Clear() { ()。}了解這些內(nèi)容足夠開(kāi)始了。下面來(lái)看一個(gè)用Collection類(lèi)且?guī)в型暾?lèi)定義的程序：using System。using 。public class Collection : CollectionBase{ public void Add(Object item) { (item)。 } public void Remove(Object item) { (item)。 } public new void Clear() { ()。 } public new int Count() { return 。 }}class chapter1{ static void Main() { Collection names = new Collection()。 (David)。 (Bernica)。 (Raymond)。 (Clayton)。 foreach (Object name in names) { (name)。 } (Number of names: + ())。 (Raymond)。 (Number of names: + ())。 ()。 (Number of names: + ())。 }}為了創(chuàng)建一個(gè)更加有用的Collection類(lèi)，還可以實(shí)現(xiàn)幾種其他的方法。大家可以在練習(xí)中實(shí)現(xiàn)一些這樣的方法。 面向?qū)ο缶幊痰膯?wèn)題之一就是所謂“代碼膨脹”的特征。為了說(shuō)明方法參數(shù)所有可能的數(shù)據(jù)類(lèi)型而需要重載某種方法或重載一套方法集合的時(shí)候，就會(huì)發(fā)生某種類(lèi)型的代碼膨脹。代碼膨脹的解決方案之一就是使某個(gè)值呈現(xiàn)多種數(shù)據(jù)類(lèi)型的能力，同時(shí)僅提供此值的一種定義。這種方法被稱(chēng)為是范型編程。范型編程提供數(shù)據(jù)類(lèi)型“占位符”。它在編譯時(shí)由特定的數(shù)據(jù)類(lèi)型填充。這個(gè)占位符用一對(duì)尖括號(hào)（ ）和放在括號(hào)間的標(biāo)識(shí)符來(lái)表示。下面來(lái)看一個(gè)實(shí)例。范型編程第一個(gè)規(guī)范實(shí)例就是Swap函數(shù)。下面是C語(yǔ)言中范型Swap函數(shù)的定義：static void SwapT(ref T val1, ref T val2){ T temp。 temp = val1。 val1 = val2。 val2 = temp。}立刻把數(shù)據(jù)類(lèi)型占位符放置在函數(shù)名后邊。現(xiàn)在無(wú)論何時(shí)需要范型數(shù)據(jù)類(lèi)型都可以使用放置在尖括號(hào)中的標(biāo)識(shí)符了。就像用于交換的臨時(shí)變量一樣，每個(gè)參數(shù)都會(huì)獲得一個(gè)范型數(shù)據(jù)類(lèi)型。下面就是一個(gè)測(cè)試此代碼的程序：using System。class chapter1{ static void Main() { int num1 = 100。 int num2 = 200。 (num1: + num1)。 (num2: + num2)。 Swapint(ref num1, ref num2)。 (num1: + num1)。 (num2: + num2)。 string str1 = Sam。 string str2 = Tom。 (String 1: + str1)。 (String 2: + str2)。 Swapstring(ref str1, ref str2)。 (String 1: + str1)。 (String 2: + str2)。 } static void SwapT(ref T val1, ref T val2) { T temp。 temp = val1。 val1 = val2。 val2 = temp。 }}程序的輸出如下所示： （原書(shū)P16頁(yè)截圖） 范型對(duì)函數(shù)定義沒(méi)有限制。所以也可以創(chuàng)建范型類(lèi)。范型類(lèi)的定義包括一個(gè)跟在類(lèi)名后邊的范型類(lèi)型占位符。任何定義中引用類(lèi)名的時(shí)候都必須提供類(lèi)型占位符。下面的類(lèi)定義說(shuō)明了創(chuàng)建范型類(lèi)的方法：public class NodeT{ T data。 NodeT link。 public Node(T data, NodeT link) { = data。 = link。 }}可以按照如下形式使用此類(lèi)：Nodestring node1 = new Nodestring(Mike, null)。Nodestring node2 = new Nodestring(Raymond, node1)。本書(shū)討論到的幾種數(shù)據(jù)結(jié)構(gòu)都將采用Node類(lèi)。雖然范型編程的這種用法可能是十分有用的，但是C語(yǔ)言提供了備用的范型數(shù)據(jù)結(jié)構(gòu)庫(kù)。，而且在討論作為此命名空間內(nèi)容的數(shù)據(jù)結(jié)構(gòu)的時(shí)候，還將對(duì)它的使用做分析。雖然通常情況下這些類(lèi)具有和非范型數(shù)據(jù)結(jié)構(gòu)類(lèi)相同的功能性，但是由于其他方法及其用途沒(méi)有什么不同，所以通常會(huì)為了如何實(shí)例化類(lèi)的對(duì)象而限制范型類(lèi)的討論。 由于本書(shū)采用了一種實(shí)用的方法來(lái)分析數(shù)據(jù)結(jié)構(gòu)與算法檢測(cè)，所以這里避開(kāi)使用大O分析法，而采用運(yùn)行簡(jiǎn)單基準(zhǔn)測(cè)試的方式來(lái)代替。這種測(cè)試將會(huì)說(shuō)明運(yùn)行一段代碼需要多少秒數(shù)（或者無(wú)論什么時(shí)間單位）?；鶞?zhǔn)法測(cè)試是用時(shí)間測(cè)試的方式來(lái)衡量運(yùn)行完整算法所花費(fèi)的時(shí)間長(zhǎng)度。如同科學(xué)一樣，基準(zhǔn)測(cè)試也像是一門(mén)藝術(shù)，而且為了獲得精確分析需要很小心測(cè)試代碼的方法。下面就來(lái)進(jìn)行詳細(xì)討論。 首先時(shí)間測(cè)試需要一些代碼。出于簡(jiǎn)單的考慮，這里將測(cè)試一個(gè)有關(guān)控制臺(tái)數(shù)組內(nèi)容的子程序。代碼如下所示：static void DisplayNums(int[] arr){for (int i = 0。 i = (0)。 i++) (arr[i] + )。}數(shù)組的初始化放在了程序的另外一部分，這部分稍后再進(jìn)行研究。為了測(cè)試這個(gè)子程序，需要?jiǎng)?chuàng)建一個(gè)變量，并且把子程序調(diào)用時(shí)的系統(tǒng)時(shí)間賦值給此變量。此外，還需要一個(gè)變量用來(lái)存儲(chǔ)子程序返回時(shí)的時(shí)間。根據(jù)這些內(nèi)容寫(xiě)出了下述這段代碼：DateTime startTime。TimeSpan endTime。startTime = 。endTime = (startTime)。在作者筆記本（運(yùn)行環(huán)境：，操作系統(tǒng)Windows XP專(zhuān)業(yè)版）上運(yùn)行此代碼時(shí)，子程序的運(yùn)行時(shí)間大約為5秒左右（）。雖然這段代碼對(duì)執(zhí)行時(shí)間測(cè)試好像很有道理。為什么呢？首先，代碼測(cè)量的是從子程序調(diào)用開(kāi)始到子程序返回主程序之間流失的時(shí)間。但是測(cè)試所測(cè)量的時(shí)間也包含了與C程序同時(shí)運(yùn)行的其他進(jìn)程所用的時(shí)間。其次。，系統(tǒng)可能在執(zhí)行無(wú)用單元收集的任何一個(gè)時(shí)間暫停。時(shí)間代碼實(shí)例沒(méi)有考慮無(wú)用單元收集時(shí)間，以及很容易受無(wú)用單元收集影響的結(jié)果時(shí)間。那么到底應(yīng)該怎么做呢？。所以在編寫(xiě)時(shí)間測(cè)試代碼時(shí)需要考慮這些情況。先來(lái)看一下如何處理無(wú)用單元收集。首先討論一下無(wú)用單元收集的用途。C語(yǔ)言用有時(shí)被稱(chēng)為堆的內(nèi)存來(lái)給參考類(lèi)型（例如字符串、數(shù)組以及類(lèi)事例對(duì)象）分配存儲(chǔ)空間。堆是用來(lái)保存數(shù)據(jù)項(xiàng)（前面提到的類(lèi)型）的內(nèi)存區(qū)域。諸如普通變量這樣的值類(lèi)型則存儲(chǔ)在堆棧中。引用的參考數(shù)據(jù)也存儲(chǔ)在堆棧中，但是實(shí)際的數(shù)據(jù)則是以參考類(lèi)型的形式存儲(chǔ)在堆中。當(dāng)聲明變量的子程序完全執(zhí)行結(jié)束時(shí)就可以釋放掉存儲(chǔ)在堆棧中的變量。而另一方面，存儲(chǔ)在堆中的變量則會(huì)一直保留到調(diào)用無(wú)用單元收集進(jìn)程的時(shí)候。當(dāng)沒(méi)有引用堆數(shù)據(jù)的行為時(shí)，只有通過(guò)無(wú)用單元收集才可以移除這些數(shù)據(jù)。在程序執(zhí)行過(guò)程中無(wú)用單元收集可能會(huì)發(fā)生在任何時(shí)候。然而需要確保在實(shí)現(xiàn)時(shí)間測(cè)試代碼時(shí)沒(méi)有運(yùn)行無(wú)用單元收集器。但是也許大家聽(tīng)說(shuō)過(guò)通過(guò)強(qiáng)制調(diào)用無(wú)用單元收集器來(lái)進(jìn)