數據結構與算法c語言描述中文(編輯修改稿)

　

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