數(shù)據(jù)結(jié)構(gòu)與算法C語(yǔ)言描述中文

1、 .440/440前言數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)對(duì)于進(jìn)行軟件開(kāi)發(fā)的專(zhuān)業(yè)程序員而言是非常關(guān)鍵的。雖然有許許多多關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法的書(shū)籍，但是這些書(shū)籍通常都是大學(xué)教材，而且是用在大學(xué)里經(jīng)典講授的Java語(yǔ)言或C+語(yǔ)言編寫(xiě)的。C#語(yǔ)言正在成為一種廣受歡迎的編程語(yǔ)言。這本書(shū)為C#語(yǔ)言程序員提供了學(xué)習(xí)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法的機(jī)會(huì)。C#語(yǔ)言根植在一個(gè)功能非常豐富的.NET框架開(kāi)發(fā)環(huán)境中。在.NET框架庫(kù)中包含有一套數(shù)據(jù)結(jié)構(gòu)類(lèi)（也稱(chēng)為集合類(lèi)）。這套類(lèi)的圍從Array類(lèi)、ArrayList類(lèi)和Collection類(lèi)到Stack類(lèi)和Queue類(lèi)，再到Hashtable類(lèi)和SortedList類(lèi)。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)生在

2、學(xué)習(xí)如何實(shí)現(xiàn)它們之前可以先明白如何使用數(shù)據(jù)結(jié)構(gòu)。以前老師在構(gòu)建完整的堆棧數(shù)據(jù)結(jié)構(gòu)之前只能抽象地講解堆棧的概念。而現(xiàn)在老師可以立刻通過(guò)示數(shù)據(jù)結(jié)構(gòu)工具來(lái)向?qū)W生們展示如何用堆棧執(zhí)行一些計(jì)算，比如數(shù)制之間的轉(zhuǎn)換。有了這些知識(shí)后，學(xué)生可以課后學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)（或算法）的基本原理，甚至可以構(gòu)造屬于他們自己的實(shí)現(xiàn)。本書(shū)把所有認(rèn)真的計(jì)算機(jī)程序員們需要知道和了解的數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)踐概述作為主要的寫(xiě)作容。由于這種情況，本書(shū)沒(méi)有涵蓋數(shù)據(jù)結(jié)構(gòu)與算法的正規(guī)的分析。因此，本書(shū)沒(méi)有一個(gè)數(shù)學(xué)公式，也一次沒(méi)有提與大O分析（如果你不知道大O分析的含義，查看參考文獻(xiàn)中提到的任何一本書(shū)都可以）。取而代之的，本書(shū)把各種各樣的數(shù)據(jù)結(jié)構(gòu)與算

3、法表示成求解問(wèn)題的工具。書(shū)中討論的數(shù)據(jù)結(jié)構(gòu)與算法用簡(jiǎn)單的時(shí)間測(cè)試來(lái)進(jìn)行性能比較。前提條件閱讀本書(shū)的唯一前提條件就是需要讀者對(duì)C#語(yǔ)言有大概的了解 。如果會(huì)用C#進(jìn)行面向?qū)ο缶幊谈?。章?jié)組織第1章向讀者介紹數(shù)據(jù)結(jié)構(gòu)作為數(shù)據(jù)集合的概念。介紹線性和非線性集合的概念。示說(shuō)明了Collection類(lèi)。本章還介紹泛型編程的概念。泛型編程允許程序員編寫(xiě)一個(gè)類(lèi)或一種方法，并且把它用于眾多數(shù)據(jù)類(lèi)型。泛型編程是C#語(yǔ)言一種重要的新特性（在C#2.0以與更高版本中可用）。這種特性是如此重要以至于在System.Collections.Generic命名空間中存在一個(gè)專(zhuān)門(mén)的泛型數(shù)據(jù)結(jié)構(gòu)庫(kù)。當(dāng)數(shù)據(jù)結(jié)構(gòu)具有在此庫(kù)中能找

4、到的泛型實(shí)現(xiàn)時(shí)，就會(huì)討論它的用途。本章結(jié)尾處介紹了衡量書(shū)中討論的數(shù)據(jù)結(jié)構(gòu)與算法性能的方法。第2章提供了數(shù)組構(gòu)造方法的回顧，并連同示例說(shuō)明了Array類(lèi)的特征。Array類(lèi)把許多與數(shù)組相關(guān)的函數(shù)（UBound函數(shù)、LBound函數(shù)等等）封裝到單獨(dú)一個(gè)包中。ArrayLists是數(shù)組的一種特殊類(lèi)型，它支持動(dòng)態(tài)地調(diào)整容量。第3章是對(duì)基礎(chǔ)排序算法的介紹，例如冒泡排序和插入排序。而第4章則研究了用于存查找的最基本算法，順序查找和二叉查找。第5章探討了兩種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)：堆棧和隊(duì)列。本章節(jié)強(qiáng)調(diào)的重點(diǎn)是這些數(shù)據(jù)結(jié)構(gòu)在解決日常數(shù)據(jù)處理問(wèn)題中的實(shí)際應(yīng)用。第6章講述了BitArray類(lèi)。這種類(lèi)可以用于有效地表示大

5、量整數(shù)值，比如測(cè)試成績(jī)。數(shù)據(jù)結(jié)構(gòu)的書(shū)常不包含字符串，但是第7章介紹了字符串、String類(lèi)和StringBuilder類(lèi)。這是因?yàn)樵贑#語(yǔ)言中許多的數(shù)據(jù)處理是在字符串上執(zhí)行的，讀者應(yīng)該接觸基于這兩種類(lèi)的特殊方法。第8章分析了用于文本處理和模式匹配的正則表達(dá)式的使用。與較傳統(tǒng)的字符串函數(shù)和方法相比，正則表達(dá)式常常會(huì)提供更強(qiáng)大更有效的處理。第9章向讀者介紹作為數(shù)據(jù)結(jié)構(gòu)的字典的使用。字典和基于字典的不同數(shù)據(jù)結(jié)構(gòu)把數(shù)據(jù)作為鍵/值對(duì)來(lái)存儲(chǔ)。本章向讀者說(shuō)明了如何創(chuàng)建基于DictionaryBase類(lèi)的他或她自己的類(lèi)。DictionaryBase類(lèi)是一個(gè)抽象類(lèi)。第10章包括散列表和HashTable類(lèi)。Ha

6、shTable類(lèi)是字典的一種特殊類(lèi)型，它用散列算法對(duì)部數(shù)據(jù)進(jìn)行存儲(chǔ)。鏈表作為另外一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)是在第11章介紹。鏈表在C#語(yǔ)言中不像在C+這樣基于指針的語(yǔ)言中那樣重要，但是它始終在C#編程中發(fā)揮作用。第12章為讀者介紹另一種經(jīng)典數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)。二叉查找樹(shù)作為二叉樹(shù)的特殊類(lèi)型將是本章的主要容。其他二叉樹(shù)類(lèi)型在第15章進(jìn)行介紹。第13章向讀者說(shuō)明在集合中存儲(chǔ)數(shù)據(jù)的方法。這種方法在數(shù)據(jù)結(jié)構(gòu)只存儲(chǔ)唯一數(shù)據(jù)值的情況下是很實(shí)用的。第14章涵蓋了高級(jí)排序算法，包括流行且高效的快速排序算法。此算法是大多數(shù)在.NET框架庫(kù)中實(shí)現(xiàn)的排序程序的基礎(chǔ)。第15章會(huì)看到三種數(shù)據(jù)結(jié)構(gòu)。在無(wú)法使用二叉查找樹(shù)的時(shí)候，這三種

7、數(shù)據(jù)結(jié)構(gòu)證明對(duì)查找是很有用的。他們是：AVL樹(shù)、紅黑樹(shù)和跳躍表。第16章討論了圖以與圖的算法。圖在表示許多不同的數(shù)據(jù)類(lèi)型時(shí)非常有用，特別是網(wǎng)絡(luò)的情況。最后，第17章向讀者介紹真正的算法設(shè)計(jì)技巧是什么：動(dòng)態(tài)算法和貪心算法。 致 在這里我要感來(lái)自各界幫助我完成此書(shū)的人們。首先，我要感首批聆聽(tīng)我講授數(shù)據(jù)結(jié)構(gòu)與算法開(kāi)發(fā)課程的學(xué)生們。這些學(xué)生包括有（排名不分先后）：Matt Hoffman、Ken Chen、 Ken Cates、Jeff Richmond以與Gordon Caffey。此外，要感我在普拉斯基科技學(xué)院的同事Clayton Ruff。他多次旁聽(tīng)我的課程并且提出了建議和批評(píng)。我還要感系主管D

8、avid Durr和系主席Bernica Tackett支持我的寫(xiě)作努力。而且，我要感我的家人在我全身心投入研究和寫(xiě)作時(shí)對(duì)我的容忍。最后，我要感劍橋的編輯Lauren Cowles和Heather Bergman，感他們?nèi)萑涛业脑S多問(wèn)題，更改容和經(jīng)常的延遲。目 錄前言 1前提條件 1章節(jié)組織 1第1章 Collections類(lèi)、泛型類(lèi)和Timing類(lèi)概述 181.1群集的定義 181.2群集的描述 181.2.1直接存取群集 181.2.2順序存取群集 201.2.3層次群集 211.2.4組群集 221.3 CollectionBase類(lèi) 221.3.1用ArrayLists實(shí)現(xiàn)Collec

9、tion類(lèi) 221.3.2定義Collection類(lèi) 231.3.3實(shí)現(xiàn)Collection類(lèi) 231.4型編程 241.5時(shí)間測(cè)試 251.5.1一個(gè)簡(jiǎn)單化的時(shí)間測(cè)試 251.5.2用于.NET環(huán)境的時(shí)間測(cè)試 261.5.3Timing Test類(lèi) 27小結(jié) 28練習(xí) 28第2章數(shù)組和ArrayLists 302.1數(shù)組基本概念 302.1.1數(shù)組的聲明和初始化 302.1.2數(shù)組元素的設(shè)置和存取訪問(wèn) 302.1.3取回?cái)?shù)組元數(shù)據(jù)的方法和屬性 312.1.4多維數(shù)組 312.1.5參數(shù)數(shù)組 322.1.6鋸齒狀數(shù)組 322.2ArrayList類(lèi) 332.2.1ArrayList類(lèi)的成員 3

10、42.2.2應(yīng)用ArrayList類(lèi) 34ArrayList grades = new ArrayList(); 34小結(jié) 36練習(xí) 36第3章基礎(chǔ)排序算法 383.1 排序算法 383.1.1數(shù)組類(lèi)測(cè)試環(huán)境 383.1.2 冒泡排序 393.1.3 檢驗(yàn)排序過(guò)程 403.1.4 選擇排序 403.1.5 插入排序 413.2 基礎(chǔ)排序算法的時(shí)間比較 42小結(jié) 43練習(xí) 43第4章基礎(chǔ)查找算法 444.1 順序查找算法 444.1.1 查找最小值和最大值 454.1.2 自組織數(shù)據(jù)加快順序查找速度 464.2 二叉查找算法 474.3 遞歸二叉查找算法 48小結(jié) 49練習(xí) 49第5章堆棧和隊(duì)列

11、 505.1堆棧、堆棧的實(shí)現(xiàn)以與STACK類(lèi) 505.1.1堆棧的操作 505.1.2Stack類(lèi)的實(shí)現(xiàn) 505.2STACK類(lèi) 525.2.1Stack構(gòu)造器方法 525.2.2主要的堆棧操作 525.2.3Peek方法 545.2.4Clear方法 545.2.5Contains方法 545.2.6CopyTo方法和ToArray方法 545.2.7Stack類(lèi)的實(shí)例：十進(jìn)制向多種進(jìn)制的轉(zhuǎn)換 545.3隊(duì)列、QUEUE類(lèi)以與QUEUE類(lèi)的實(shí)現(xiàn) 555.3.1隊(duì)列的操作 555.3.2Queue的實(shí)現(xiàn) 565.3.3 Queue類(lèi)：實(shí)例應(yīng)用 565.3.4用隊(duì)列存儲(chǔ)數(shù)據(jù) 585.3.5源自Q

12、ueue類(lèi)的優(yōu)先隊(duì)列 60小結(jié) 61練習(xí) 61第6章 BitArray類(lèi) 636.1激發(fā)的問(wèn)題 636.2位和位操作 636.2.1二進(jìn)制數(shù)制系統(tǒng) 646.2.2處理二進(jìn)制數(shù)：按位運(yùn)算符和位移運(yùn)算符 646.3按位運(yùn)算符的應(yīng)用 656.3.1位移運(yùn)算符 666.4整數(shù)轉(zhuǎn)換成二進(jìn)制形式的應(yīng)用程序 666.5位移的示例應(yīng)用程序 686.6BITARRAY類(lèi) 696.6.1使用BitArray類(lèi) 696.6.2更多BitArray類(lèi)的方法和屬性 706.7用BITARRAY來(lái)編寫(xiě)埃拉托斯特尼篩法 716.8BITARRAY與數(shù)組在埃拉托斯特尼篩法上的比較 72小結(jié) 72練習(xí) 72第7章 字符串、St

13、ring類(lèi)和StringBuilder類(lèi) 737.1STRING類(lèi)的應(yīng)用 737.1.1創(chuàng)建String對(duì)象 737.1.2常用String類(lèi)的方法們 737.1.3Split方法和Join方法 757.1.4比較字符串的方法 767.1.5處理字符串的方法 787.2STRINGBUILDER類(lèi) 817.2.1構(gòu)造StringBuilder對(duì)象 817.2.2獲取并且設(shè)置關(guān)于StringBuilder對(duì)象的信息 817.2.3修改StringBuilder對(duì)象 827.3STRING類(lèi)與STRINGBUILDER的性能比較 83小結(jié) 84練習(xí) 85第8章 模式匹配和文本處理 868.1正則表

14、達(dá)式概述 868.1.1概述：使用正則表達(dá)式 868.2數(shù)量詞 878.3使用字符類(lèi) 888.4用斷言修改正則表達(dá)式 908.5使用分組構(gòu)造 908.5.1匿名組 908.5.2命名組 918.5.3零寬度正向預(yù)搜索斷言和零寬度反向預(yù)搜索斷言 918.6CAPTURESCOLLECTION類(lèi) 928.7正則表達(dá)式的選項(xiàng) 92小結(jié) 93練習(xí) 93第9章 構(gòu)建字典：DictionaryBase類(lèi)和SortedList類(lèi) 949.1DICTIONARYBASE類(lèi) 949.1.1DictionaryBase類(lèi)的基礎(chǔ)方法和屬性 949.1.2其他的DictionaryBase方法 959.2通用的KEY

15、VALUEPAIR類(lèi) 969.3SORTEDLIST類(lèi) 979.3.1使用SortedList類(lèi) 97小結(jié) 97練習(xí) 98第10章 散列和Hashtable類(lèi) 9910.1 散列概述 9910.2 選擇散列函數(shù) 9910.3 查找散列表中數(shù)據(jù) 10010.4 解決沖突 10110.4.1 桶式散列法 10110.4.2 開(kāi)放定址法 10210.4.3 雙重散列法 10210.5 HASHTABLE類(lèi) 10210.5.1實(shí)例化Hashtable對(duì)象并且給其添加數(shù)據(jù) 10210.5.2從散列表中分別取回關(guān)鍵字和數(shù)值 10310.5.3取回基于關(guān)鍵字的數(shù)值 10310.5.4 Hashtable類(lèi)的

16、實(shí)用方法 10410.6 HASHTABLE的應(yīng)用程序：計(jì)算機(jī)術(shù)語(yǔ)表 104小結(jié) 106練習(xí) 106第11章 鏈表 10711.1數(shù)組存在的問(wèn)題 10711.2鏈表的定義 10711.3面向?qū)ο箧湵淼脑O(shè)計(jì) 10811.3.1 Node類(lèi) 10811.3.2 LinkedList類(lèi) 10811.4 鏈表設(shè)計(jì)的改進(jìn)方案 10911.4.1 雙向鏈表 11011.4.2 循環(huán)鏈表 11111.5 使用ITERATOR類(lèi) 11311.5.1 新的LinkedList類(lèi) 11411.5.2 實(shí)例化Iterator類(lèi) 11411.6 通用的LINKED LIST類(lèi)和通用的NODE類(lèi) 11711.6.1 通

17、用鏈表實(shí)例 117小結(jié) 118練習(xí) 118第12章 二叉樹(shù)和二叉查找樹(shù) 11912.1 樹(shù)的定義 11912.2 二叉樹(shù) 12012.2.1 構(gòu)造二叉查找樹(shù) 12012.2.2 遍歷二叉查找樹(shù) 12112.2.3 在二叉查找樹(shù)中查找節(jié)點(diǎn)和最大/最小值 12312.2.4 從BST中移除葉子節(jié)點(diǎn) 12312.2.5 刪除帶有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn) 12412.2.6 刪除帶有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn) 124小結(jié) 126練習(xí) 127第13章 集合 12813.1集合的基礎(chǔ)定義、操作與屬性 12813.1.1集合的定義 12813.1.2集合的操作 12813.1.3集合的屬性 12813.2第一個(gè)用散列表的SE

18、T類(lèi)的實(shí)現(xiàn) 12913.2.1類(lèi)數(shù)據(jù)成員和構(gòu)造器方法 12913.2.2Add方法 12913.2.3Remove方法和Size方法 12913.2.4Union方法 12913.2.5Intersection方法 13013.2.6Subset方法 13013.2.7Difference方法 13013.2.8測(cè)試CSet實(shí)現(xiàn)的程序 13013.3CSET類(lèi)的BITARRAY實(shí)現(xiàn) 13113.3.1使用BitArray實(shí)現(xiàn)的概述 13113.3.2BitArray集合的實(shí)現(xiàn) 132小結(jié) 133練習(xí) 133第14章 高級(jí)排序算法 13414.1希爾排序算法 13414.2歸并排序算法 1351

19、4.3堆排序算法 13614.3.1構(gòu)造堆 13614.4快速排序算法 13814.4.1快速排序算法的描述 13914.4.2快速排序算法的代碼 13914.4.3快速排序算法的改進(jìn) 140小結(jié) 140練習(xí) 140第15章 查找的高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法 14115.1 AVL樹(shù) 14115.1.1 AVL樹(shù)的基本原理 14115.1.2 AVL樹(shù)的實(shí)現(xiàn) 14115.2 紅黑樹(shù) 14315.2.1 紅黑樹(shù)規(guī)則 14315.2.2 紅黑樹(shù)的插入 14315.2.3 紅黑樹(shù)實(shí)現(xiàn)代碼 14415.3 跳躍表 14615.3.1 跳躍表的基本原理 14615.3.2 跳躍表的實(shí)現(xiàn) 147小結(jié) 149練習(xí)

20、150第16章 圖和圖的算法 15116.1 圖的定義 15116.2 由圖模擬真實(shí)世界系統(tǒng) 15116.3 圖類(lèi) 15116.3.1 頂點(diǎn)的表示 15216.3.2 邊的表示 15216.3.3 圖的構(gòu)造 15216.3.4 圖的第一個(gè)應(yīng)用：拓?fù)渑判?15316.3.5 拓?fù)渑判蛩惴?15416.3.6 拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn) 15416.4 圖的搜索 15616.4.1 深度優(yōu)先搜索 15616.4.2 廣度優(yōu)先搜索 15716.5 最小生成樹(shù) 15816.5.1 最小生成樹(shù)算法 15816.6 查找最短路徑 15916.6.1 加權(quán)圖 15916.6.2 確定最短路徑的Dijkstra算法

21、16016.6.3 Dijkstra算法的代碼 160小結(jié) 164練習(xí) 164第17章 高級(jí)算法 16517.1 動(dòng)態(tài)規(guī)劃 16517.1.1動(dòng)態(tài)規(guī)劃實(shí)例：計(jì)算斐波納契數(shù)列 16517.1.2 尋找最長(zhǎng)公共子串 16717.1.3 背包問(wèn)題 16817.2 貪心算法 16917.2.1貪心算法實(shí)例：找零錢(qián)問(wèn)題 16917.2.2 采用哈夫曼編碼的數(shù)據(jù)壓縮 17017.2.3用貪心算法解決背包問(wèn)題 174小結(jié) 176練習(xí) 176索引 177第1章 Collections類(lèi)、泛型類(lèi)和Timing類(lèi)概述這本書(shū)采用C#語(yǔ)言來(lái)討論數(shù)據(jù)結(jié)構(gòu)與算法的開(kāi)發(fā)和實(shí)現(xiàn)。書(shū)中用到的數(shù)據(jù)結(jié)構(gòu)都可以在.NET框架類(lèi)庫(kù)Sy

22、stem.Collections中找到。本章會(huì)逐步展開(kāi)群集的概念，首先是討論自身特有的Collection類(lèi)（采用數(shù)組作為我們實(shí)現(xiàn)的基礎(chǔ)）的實(shí)現(xiàn)，接著會(huì)介紹.NET框架中Collection類(lèi)的容。泛型是C#語(yǔ)言2.0版新增加的一個(gè)重要補(bǔ)充。泛型允許C#語(yǔ)言程序員可以獨(dú)立地或者在一個(gè)類(lèi)中編寫(xiě)函數(shù)的某一個(gè)版本，而且不需要為了不同的數(shù)據(jù)類(lèi)型而多次負(fù)載此函數(shù)。C#語(yǔ)言2.0版還為個(gè)別幾種System.Collections數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)型提供了一個(gè)專(zhuān)門(mén)的庫(kù)System.Collections.Generic。本章將向讀者介紹泛型編程。本章最后會(huì)介紹一種用戶(hù)定制的類(lèi)Timing類(lèi)。后續(xù)的幾個(gè)章節(jié)將會(huì)用此

23、類(lèi)來(lái)衡量數(shù)據(jù)結(jié)構(gòu)與/或算法的性能。此類(lèi)將代替大O分析法的位置。這不是因?yàn)榇驩分析法不重要，而是因?yàn)楸緯?shū)采取了一種更為實(shí)用的方法來(lái)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法。1.1群集的定義群集是一種結(jié)構(gòu)化的數(shù)據(jù)類(lèi)型。它存儲(chǔ)數(shù)據(jù)，并且提供數(shù)據(jù)的添加、刪除、更新操作，以與對(duì)群集的不同屬性值的設(shè)置與返回操作。群集可以分為兩類(lèi)：線性的和非線性的。線性群集是一元素列表，表中的元素順次相連。線性群集中的元素通常由位置來(lái)決定次序（例如，第一個(gè)元素、第二個(gè)元素、第三個(gè)元素，依次類(lèi)推）。在現(xiàn)實(shí)世界中，購(gòu)物清單就是很好的線性群集實(shí)例。而在計(jì)算機(jī)世界中（當(dāng)然這也是真實(shí)世界）則把數(shù)組設(shè)計(jì)成線性群集。非線性群集所包含的元素在群集沒(méi)有位置次序之

24、分。組織結(jié)構(gòu)圖就像用架子壘好的臺(tái)球一樣是一個(gè)非線性群集的實(shí)例。而在計(jì)算機(jī)世界中樹(shù)、堆、圖和集都是非線性群集。無(wú)論是線性的還是非線性的群集都擁有一套定義好的屬性和操作的集合。其中，屬性用來(lái)描述群集，而操作就是群集能執(zhí)行的容。群集Count就是群集屬性的一個(gè)實(shí)例。它保存著群集中數(shù)據(jù)項(xiàng)的數(shù)量。這里把群集的操作稱(chēng)為方法，它包括Add（即向群集添加新元素），Insert（即在群集指定的索引位置添加新元素）、Remove（即從群集中移除指定元素）、Clear（即從群集中移除所有元素）、Contains（即確定指定元素是否是群集的成員）、以與IndexOf（即確定指定元素在群集中的索引位置）。1.2群集的描

25、述在兩種主要的群集類(lèi)中有幾個(gè)子類(lèi)別。線性的群集可能是直接存取群集，也可能是順序存取群集。而非線性的群集既可以是層次群集，也可以是組群集。本小節(jié)就來(lái)討論這些群集的類(lèi)型。1.2.1直接存取群集直接存取群集最常見(jiàn)的實(shí)例就是數(shù)組。這里把數(shù)組定義為具有一樣數(shù)據(jù)類(lèi)型的元素的群集，而且所有數(shù)組元素如同圖1-1說(shuō)明的那樣可以通過(guò)整數(shù)型索引直接進(jìn)行存取訪問(wèn)。（原書(shū)P3頁(yè)圖）第0項(xiàng)、第1項(xiàng)、第2項(xiàng)、第3項(xiàng)、第j項(xiàng)、第n-1項(xiàng)圖1-1數(shù)組數(shù)組可以是靜態(tài)的，這樣當(dāng)聲明數(shù)組的時(shí)候便于針對(duì)程序的長(zhǎng)度來(lái)固定指定元素的數(shù)量。數(shù)組也可以是動(dòng)態(tài)的，通過(guò)ReDim或者ReDim Preserve語(yǔ)句就可以增加數(shù)組元素的數(shù)量。在C#

26、語(yǔ)言中，數(shù)組不只是置的數(shù)據(jù)類(lèi)型，它還是一種類(lèi)。在本章的后續(xù)部分，當(dāng)詳細(xì)分析數(shù)組使用的時(shí)候?qū)?huì)討論如何把數(shù)組作為類(lèi)對(duì)象來(lái)使用。我們可以用數(shù)組來(lái)存儲(chǔ)一個(gè)線性的群集。向數(shù)組添加新元素是很容易的，只要簡(jiǎn)單地把新元素放置在數(shù)組尾部第一個(gè)空位上就可以了。但是，在數(shù)組中插入一個(gè)元素就不是這么容易的（或高效）了。因?yàn)橐o插入的元素空出位置，所以需要按順序向后移動(dòng)數(shù)組元素。從數(shù)組的尾部刪除一個(gè)元素也是很有效率的操作，只要簡(jiǎn)單地移除掉最后一個(gè)元素的值就可以了。但是，刪除數(shù)組中任何其他位置上的元素就沒(méi)有這么有效率了，就像處理插入操作一樣，為了保持?jǐn)?shù)組中元素的連續(xù)性，可能需要先前調(diào)整許多數(shù)組元素的位置。這些情況將在本

27、章后續(xù)容中進(jìn)行討論。.NET框架為簡(jiǎn)化線性群集的編程提供了一種專(zhuān)門(mén)的數(shù)組類(lèi)ArrayList。第3章將會(huì)對(duì)此類(lèi)進(jìn)行分析研究。字符串是直接存取群集的另外一種類(lèi)型。字符串是字符的群集。和存取數(shù)組元素的方式一樣，也可以基于字符的索引對(duì)其進(jìn)行存取。在C#語(yǔ)言中，字符串也是作為類(lèi)對(duì)象來(lái)實(shí)現(xiàn)的。這個(gè)類(lèi)包含一個(gè)在字符串上執(zhí)行標(biāo)準(zhǔn)操作的龐大的方法集合，其中操作有串連接、返回子串、插入字符、移除字符等等。第8章會(huì)討論String類(lèi)。C#字符串是不可變的。這意味著一旦對(duì)字符串進(jìn)行了初始化，就不能再改變它了。當(dāng)要修改字符串的時(shí)候，不是改變?cè)嫉淖址?，而是?chuàng)建一個(gè)字符串的副本。在某些情況下這種行為可能會(huì)導(dǎo)致性能下降

28、，所以.NET框架提供了StringBuilder類(lèi)來(lái)讓用戶(hù)能處理可變的字符串。第8章也會(huì)對(duì)StringBuilder進(jìn)行介紹。結(jié)構(gòu)（在其他編程語(yǔ)言中也被稱(chēng)為記錄）是最后一種直接存取的群集類(lèi)型。結(jié)構(gòu)是一種復(fù)合數(shù)據(jù)類(lèi)型。它所包含的數(shù)據(jù)可能擁有許多不同的數(shù)據(jù)類(lèi)型。例如，一名雇員記錄就是由雇員的（字符串）、薪水（整數(shù)）、工號(hào)（字符串或整數(shù)），以與其他屬性組成的。由于把這些數(shù)據(jù)的值分別存儲(chǔ)在分散的變量是很容易變混淆的，所以編程語(yǔ)言采用結(jié)構(gòu)來(lái)存儲(chǔ)此類(lèi)數(shù)據(jù)。C#語(yǔ)言的結(jié)構(gòu)所增加的強(qiáng)大能力就是為執(zhí)行存儲(chǔ)在數(shù)據(jù)上的操作定義了方法。盡管不能從結(jié)構(gòu)繼承或推導(dǎo)出一種新的類(lèi)型，但是這種做法使得結(jié)構(gòu)在某些地方很像一個(gè)類(lèi)

29、。下面的代碼舉例明了C#語(yǔ)言中結(jié)構(gòu)的一個(gè)簡(jiǎn)單應(yīng)用。using System;public struct Name private string fname, mname, lname; public Name(string first, string middle, string last) fname = first; mname = middle; lname = last; public string firstName get return fname; set fname = firstName; public string middleName get return mname;

30、set mname = middleName; public string lastName get return lname; set lname = lastName; public override string ToString() return (String.Format(0 1 2, fname, mname,lname); public string Initials() return (String.Format(012, fname.Substring(0, 1),mname.Substring(0, 1), lname.Substring(0, 1); public cl

31、ass NameTest static void Main() Name myName = new Name(Michael, Mason, McMillan); string fullName, inits; fullName = myName.ToString(); inits = myName.Initials(); Console.WriteLine(My name is 0., fullName); Console.WriteLine(My initials are 0., inits); 雖然.NET環(huán)境中許多元素都是作為類(lèi)來(lái)實(shí)現(xiàn)的（比如數(shù)組和字符串），但是語(yǔ)言的幾個(gè)主要元素還是作

32、為結(jié)構(gòu)來(lái)實(shí)現(xiàn)的，比如數(shù)字?jǐn)?shù)據(jù)類(lèi)型。例如，整數(shù)類(lèi)型就是作為Int32結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。采用Int32的方法之一就是把用字符串表示的數(shù)轉(zhuǎn)換成為整數(shù)的Parse方法。實(shí)例如下所示：using System;public class IntStruct static void Main() int num; string snum; Console.Write(Enter a number: ); snum = Console.ReadLine(); num = Int32.Parse(snum); Console.WriteLine(num); 1.2.2順序存取群集順序存取群集是把群集元素按順序存儲(chǔ)的

33、表。這里也把此類(lèi)群集稱(chēng)為線性表。線性表在創(chuàng)建時(shí)沒(méi)有大小限制，這就意味著它們可以動(dòng)態(tài)地?cái)U(kuò)展和收縮。不能對(duì)線性表中數(shù)據(jù)項(xiàng)進(jìn)行直接存取訪問(wèn)，而要像圖1-2表示的那樣通過(guò)數(shù)據(jù)項(xiàng)的位置對(duì)其進(jìn)行存取。線性表的第一個(gè)元素在表頭的位置，而最后一個(gè)元素在表尾的位置。（原書(shū)P6頁(yè)圖）第1項(xiàng)、第2項(xiàng)、第3項(xiàng)、第4項(xiàng)、第n項(xiàng)表頭 表尾圖1-2線性表由于不能直接存取線性表的元素，為了訪問(wèn)某個(gè)元素就需要遍歷線性表直到到達(dá)要找元素的位置為止。線性表的實(shí)現(xiàn)通常允許兩種遍歷表的方法：一種是單向從前往后遍歷，而另一種則是雙向遍歷，即從前向后和從后先前遍歷。線性表的一個(gè)簡(jiǎn)單實(shí)例就是購(gòu)物清單。順次寫(xiě)下要購(gòu)買(mǎi)的全部商品就會(huì)形成一購(gòu)物清

34、單。在購(gòu)物時(shí)一旦找到某種商品就把它從清單中劃掉。線性表既可以是有序的，也可以是無(wú)序的。有序線性表具有順次對(duì)應(yīng)的有序值。如下列人名所表示的情況：Beata、Bernica、David 、Frank、Jennifer、Mike、Raymond、Terrill。而無(wú)序線性表則是由無(wú)序元素組成的。在第2章對(duì)二叉查找算法與簡(jiǎn)單線性查找算法進(jìn)行討論時(shí)就會(huì)發(fā)現(xiàn)線性表的順序會(huì)在查找表中數(shù)據(jù)時(shí)產(chǎn)生很大的差異。線性表的某些類(lèi)型限制訪問(wèn)數(shù)據(jù)元素。這類(lèi)線性表有堆棧和隊(duì)列。堆棧是一種只允許在表頭（或頂端）存取數(shù)據(jù)的表。在表的頂端放置數(shù)據(jù)項(xiàng)，而且也只能從表的頂端移出數(shù)據(jù)項(xiàng)。正是基于這種原因，堆棧也被稱(chēng)為后進(jìn)先出結(jié)構(gòu)。這里

35、把向堆棧添加數(shù)據(jù)項(xiàng)的操作稱(chēng)為入棧，而把從堆棧移出數(shù)據(jù)項(xiàng)的操作稱(chēng)為出棧。圖1-3展示了堆棧的這兩種操作。（原書(shū)P7頁(yè)圖）入棧、出棧圖1-3堆棧操作堆棧是非常常見(jiàn)的一種數(shù)據(jù)結(jié)構(gòu)，特別是在計(jì)算機(jī)系統(tǒng)編程中尤為普遍。在堆棧的眾多應(yīng)用中，它常用于算術(shù)表達(dá)式的計(jì)算和平衡符號(hào)。隊(duì)列是一種只允許在表尾進(jìn)行數(shù)據(jù)項(xiàng)添加和移出操作的表。它也被稱(chēng)為是先進(jìn)先出結(jié)構(gòu)。這里把向隊(duì)列添加數(shù)據(jù)項(xiàng)稱(chēng)為EnQueue，而把從隊(duì)列移出數(shù)據(jù)項(xiàng)稱(chēng)為DeQueue。圖1-4展示了隊(duì)列的這兩種操作。（原書(shū)P7頁(yè)圖）圖1-4隊(duì)列操作隊(duì)列既可用于調(diào)度操作系統(tǒng)任務(wù)的系統(tǒng)編程，也可用于模擬研究的編程。在每一種能想象到的少量情況下，隊(duì)列都可以為模擬等

36、待隊(duì)列產(chǎn)生極好的結(jié)構(gòu)。優(yōu)先隊(duì)列是隊(duì)列的一種特殊類(lèi)型。它允許最先移出隊(duì)列的數(shù)據(jù)項(xiàng)具有最高的優(yōu)先級(jí)。例如，優(yōu)先隊(duì)列可以用來(lái)研究醫(yī)院急診室的操作，這里應(yīng)該對(duì)心臟病突發(fā)患者先進(jìn)行救護(hù)，然后再處理手臂骨折患者。最后要討論的一類(lèi)線性群集被稱(chēng)為通用的索引群集。這類(lèi)群集的第一種就是散列表。它存儲(chǔ)了一組與關(guān)鍵字相關(guān)聯(lián)的數(shù)據(jù)值。在散列表中有一個(gè)被稱(chēng)為散列函數(shù)的特殊函數(shù)。此函數(shù)會(huì)取走一個(gè)數(shù)據(jù)值，并且把此數(shù)據(jù)值（稱(chēng)為關(guān)鍵字）轉(zhuǎn)換成用來(lái)取回?cái)?shù)據(jù)的整數(shù)索引。然后此索引會(huì)用來(lái)存取訪問(wèn)與關(guān)鍵字相關(guān)聯(lián)的數(shù)據(jù)記錄。例如，一條雇員記錄可能由雇員、薪水、工作年限以與所工作的部門(mén)組成。此結(jié)構(gòu)如圖1-5所示。此數(shù)據(jù)記錄的關(guān)鍵字就是雇員的

37、。C#語(yǔ)言有一個(gè)稱(chēng)為HashTable的類(lèi)用來(lái)存儲(chǔ)散列表的數(shù)據(jù)。第10章會(huì)討論此結(jié)構(gòu)。（原書(shū)P8頁(yè)圖）“信息系統(tǒng)”部門(mén)圖1-5散列的記錄另外一種通用的索引群集就是字典。字典也被稱(chēng)為聯(lián)合，它是由一系列鍵值對(duì)構(gòu)成的。此結(jié)構(gòu)與詞典類(lèi)似，詞典中的詞是關(guān)鍵字，而詞的定義則是與關(guān)鍵字相關(guān)聯(lián)的值。關(guān)鍵字就是與其相關(guān)聯(lián)的值的索引。雖然索引不需要就是整數(shù)，但是由于上述這種索引方案，所以還是常把字典稱(chēng)為聯(lián)合數(shù)組。第11章會(huì)對(duì).NET框架容的幾種Dictionary類(lèi)進(jìn)行討論。1.2.3層次群集非線性群集分為兩大主要類(lèi)型：層次群集和組群集。層次群集是一組劃分了層次的數(shù)據(jù)項(xiàng)集合。位于某一層的數(shù)據(jù)項(xiàng)可能會(huì)有位于下一較低

38、層上的后繼數(shù)據(jù)項(xiàng)。樹(shù)是一種常見(jiàn)的層次群集。樹(shù)群集看上去像是一棵倒立的樹(shù)，其中一個(gè)數(shù)據(jù)項(xiàng)作為根，而其他數(shù)據(jù)值則作為葉子掛在根的下面。樹(shù)的元素被稱(chēng)為節(jié)點(diǎn)，而且在特定節(jié)點(diǎn)下面的元素被稱(chēng)為是此節(jié)點(diǎn)的孩子。圖1-6展示了一棵實(shí)例樹(shù)。（原書(shū)P9頁(yè)圖）根圖1-6樹(shù)群集樹(shù)在幾種不同的領(lǐng)域都有應(yīng)用。大多數(shù)現(xiàn)代操作系統(tǒng)的文件系統(tǒng)都是采用樹(shù)群集設(shè)計(jì)而成的，其中一個(gè)目錄作為根，而其他子目錄則作為根的孩子們。二叉樹(shù)是樹(shù)群集的一種特殊類(lèi)型，樹(shù)中每個(gè)節(jié)點(diǎn)最多只有兩個(gè)孩子。二叉樹(shù)可以變成二叉查找樹(shù)，這樣做可以極提高查找大量數(shù)據(jù)的效率。實(shí)現(xiàn)的方法是依據(jù)從根到要存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)的路徑為最短路徑的方式來(lái)放置節(jié)點(diǎn)。還有一種樹(shù)類(lèi)型就是堆

39、。堆這樣組織就是為了便于把最小數(shù)據(jù)值始終放置在根節(jié)點(diǎn)上。在刪除時(shí)會(huì)移除根節(jié)點(diǎn)。此外，堆的插入和刪除操作總是會(huì)導(dǎo)致堆的重組，因?yàn)橹挥羞@樣才能把最小值放在根節(jié)點(diǎn)上。我們經(jīng)常會(huì)用堆來(lái)排序，這被稱(chēng)為是堆排序。通過(guò)反復(fù)刪除根節(jié)點(diǎn)以與重組堆的方式就可以對(duì)存儲(chǔ)在堆的數(shù)據(jù)元素進(jìn)行排序。第12章將對(duì)幾種不同類(lèi)型的樹(shù)進(jìn)行討論。1.2.4組群集數(shù)據(jù)項(xiàng)為無(wú)序的非線性群集被稱(chēng)為組。集合、圖和網(wǎng)絡(luò)是組群集的三種主要類(lèi)型。集合是一種無(wú)序數(shù)據(jù)值的群集，并且集合中每一個(gè)數(shù)據(jù)值都是唯一的。當(dāng)然，就像整數(shù)一樣，班級(jí)中學(xué)生的列表就是一個(gè)集合的實(shí)例。在集合上執(zhí)行的操作包括聯(lián)合和交叉。圖1-7顯示了集合操作的實(shí)例。（原書(shū)P10頁(yè)圖）A集

40、合、B集合、A集合交叉B集合、A集合聯(lián)合B集和圖1-7集合操作圖是由節(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í)例圖表示在圖1-8中。（原書(shū)P10頁(yè)圖）Tokyo:東京、Seattle:西雅圖、LA:洛杉磯、Boston:波士頓、New York:紐約、Washington:

41、華盛頓、London:倫敦、Paris:巴黎、Rome:羅馬、Moscow:莫斯科圖1-8旅行商問(wèn)題此問(wèn)題是被稱(chēng)為NP-完全問(wèn)題的其中一部分容。這就意味著針對(duì)此類(lèi)型的大量問(wèn)題是無(wú)法知道確切解決方案的。例如，為了找到圖1-8所示問(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)。圖1-9描述了帶權(quán)的城市網(wǎng)絡(luò)，其中這里的權(quán)是兩座城市（節(jié)點(diǎn)

42、）之間的英里數(shù)。（原書(shū)P11頁(yè)圖）圖1-9網(wǎng)絡(luò)群集至此已經(jīng)對(duì)將要在本書(shū)中討論的不同群集類(lèi)型做了總體的概述。下面就準(zhǔn)備實(shí)際看一看這些群集是如何用C#語(yǔ)言實(shí)現(xiàn)的了。首先會(huì)看到如何用來(lái)自.NET框架的抽象類(lèi)CollectionBase類(lèi)來(lái)構(gòu)建一個(gè)Collection類(lèi)。1.3 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)造Col

43、lection類(lèi)所必需的接口，即ICollection和IEnumerable，而留給程序員要做的工作就只是對(duì)這些作為Collection類(lèi)特殊容的方法的實(shí)現(xiàn)。1.3.1用ArrayLists實(shí)現(xiàn)Collection類(lèi)本節(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é)容還可用于討論一些將要出現(xiàn)的性能問(wèn)題。最后，就像本書(shū)中其他實(shí)現(xiàn)章節(jié)一樣，本節(jié)容也會(huì)使人獲益良多，因?yàn)閮H僅用語(yǔ)言自身的元素就能重新實(shí)現(xiàn)已存在的數(shù)據(jù)

44、結(jié)構(gòu)實(shí)在是充滿(mǎn)樂(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í)。1.3.2定義Collection類(lèi)在C#語(yǔ)言中定義一個(gè)Collection類(lèi)最簡(jiǎn)單的方法就是把在System.Collections庫(kù)中已找到的抽象類(lèi)CollectionBase類(lèi)作為基礎(chǔ)類(lèi)。此類(lèi)提供了一套可以實(shí)現(xiàn)構(gòu)造自身群集的抽象方法集合。CollectionBase類(lèi)還提供了一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)InnerList（一個(gè)ArrayList）。此結(jié)構(gòu)可

45、以用作自身類(lèi)的基礎(chǔ)。本章節(jié)會(huì)看到如何使用CollectionBase來(lái)構(gòu)造Collection類(lèi)。1.3.3實(shí)現(xiàn)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) InnerList.Add(item);Arr

46、ayList把數(shù)據(jù)作為對(duì)象（即Object數(shù)據(jù)類(lèi)型）來(lái)存儲(chǔ)。這就是把數(shù)據(jù)項(xiàng)聲明為Object的原因。第2章將會(huì)學(xué)到更多有關(guān)ArrayLists的容。 Remove方法的執(zhí)行與上述類(lèi)似：public void Remove(Object item) InnerList.Remove(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 InnerLis

47、t.Count;Clear方法把全部數(shù)據(jù)項(xiàng)從InnerList中移除掉。這里也需要在方法定義中使用新的關(guān)鍵詞：public new void Clear() InnerList.Clear();了解這些容足夠開(kāi)始了。下面來(lái)看一個(gè)用Collection類(lèi)且?guī)в型暾?lèi)定義的程序：using System;using System.Collections;public class Collection : CollectionBase public void Add(Object item) InnerList.Add(item); public void Remove(Object item) I

48、nnerList.Remove(item); public new void Clear() InnerList.Clear(); public new int Count() return InnerList.Count; class chapter1 static void Main() Collection names = new Collection(); names.Add(David); names.Add(Bernica); names.Add(Raymond); names.Add(Clayton); foreach (Object name in names) Console

49、.WriteLine(name); Console.WriteLine(Number of names: + names.Count(); names.Remove(Raymond); Console.WriteLine(Number of names: + names.Count(); names.Clear(); Console.WriteLine(Number of names: + names.Count(); 為了創(chuàng)建一個(gè)更加有用的Collection類(lèi)，還可以實(shí)現(xiàn)幾種其他的方法。大家可以在練習(xí)中實(shí)現(xiàn)一些這樣的方法。1.4型編程面向?qū)ο缶幊痰膯?wèn)題之一就是所謂“代碼膨脹”的特征。為了說(shuō)

50、明方法參數(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 Swap(ref T val1, ref T val2) T temp; temp = val1; val1 = val2; val2 = temp;立刻把數(shù)據(jù)

51、類(lèi)型占位符放置在函數(shù)名后邊?，F(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; Console.WriteLine(num1: + num1); Console.WriteLine(num2: + num2); Swap(ref num1, ref num2); Console.WriteLine(num1: + num1); Consol

52、e.WriteLine(num2: + num2); string str1 = Sam; string str2 = Tom; Console.WriteLine(String 1: + str1); Console.WriteLine(String 2: + str2); Swap(ref str1, ref str2); Console.WriteLine(String 1: + str1); Console.WriteLine(String 2: + str2); static void Swap(ref T val1, ref T val2) T temp; temp = val1;

53、 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 Node T data; Node link; public Node(T data, Node link) this.data = data; this.link = link; 可以按照如下形式使用此類(lèi)：Node node1 = new Node(Mike, null);Node node2 = new N

54、ode(Raymond, node1);本書(shū)討論到的幾種數(shù)據(jù)結(jié)構(gòu)都將采用Node類(lèi)。雖然型編程的這種用法可能是十分有用的，但是C#語(yǔ)言提供了備用的型數(shù)據(jù)結(jié)構(gòu)庫(kù)。在System.Collection.Generics命名空間中都可以找到這些數(shù)據(jù)結(jié)構(gòu)，而且在討論作為此命名空間容的數(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)的討論。1.5時(shí)間測(cè)試由于本書(shū)采用了一種實(shí)用的方法來(lái)分析數(shù)據(jù)結(jié)構(gòu)與算法檢測(cè)，所以這里避開(kāi)使用大O分析法，而采用運(yùn)行簡(jiǎn)單基準(zhǔn)測(cè)試的方式來(lái)代替。這種測(cè)試將會(huì)

55、說(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ì)討論。1.5.1一個(gè)簡(jiǎn)單化的時(shí)間測(cè)試首先時(shí)間測(cè)試需要一些代碼。出于簡(jiǎn)單的考慮，這里將測(cè)試一個(gè)有關(guān)控制臺(tái)數(shù)組容的子程序。代碼如下所示：static void DisplayNums(int arr)for (int i = 0; i = arr.GetUpperBound(0); i+) Console.Write(arri + );數(shù)組的初始化放在了程序的另外一部分，這部分稍后再

56、進(jìn)行研究。為了測(cè)試這個(gè)子程序，需要?jiǎng)?chuàng)建一個(gè)變量，并且把子程序調(diào)用時(shí)的系統(tǒng)時(shí)間賦值給此變量。此外，還需要一個(gè)變量用來(lái)存儲(chǔ)子程序返回時(shí)的時(shí)間。根據(jù)這些容寫(xiě)出了下述這段代碼：DateTime startTime;TimeSpan endTime;startTime = DateTime.Now;endTime = DateTime.Now.Subtract(startTime);在作者筆記本（運(yùn)行環(huán)境：機(jī)器主頻1.4mHz，操作系統(tǒng)Windows XP專(zhuān)業(yè)版）上運(yùn)行此代碼時(shí)，子程序的運(yùn)行時(shí)間大約為5秒左右（4.9917秒）。雖然這段代碼對(duì)執(zhí)行時(shí)間測(cè)試好像很有道理，但是在.NET環(huán)境下運(yùn)行時(shí)間代碼是完

57、全不合適的。為什么呢？首先，代碼測(cè)量的是從子程序調(diào)用開(kāi)始到子程序返回主程序之間流失的時(shí)間。但是測(cè)試所測(cè)量的時(shí)間也包含了與C#程序同時(shí)運(yùn)行的其他進(jìn)程所用的時(shí)間。其次，時(shí)間代碼不考慮.NET環(huán)境下執(zhí)行的無(wú)用單元收集。在類(lèi)似.NET這樣的運(yùn)行時(shí)間環(huán)境中，系統(tǒng)可能在執(zhí)行無(wú)用單元收集的任何一個(gè)時(shí)間暫停。時(shí)間代碼實(shí)例沒(méi)有考慮無(wú)用單元收集時(shí)間，以與很容易受無(wú)用單元收集影響的結(jié)果時(shí)間。那么到底應(yīng)該怎么做呢？1.5.2用于.NET環(huán)境的時(shí)間測(cè)試在.NET環(huán)境中需要考慮程序運(yùn)行中的線程以與無(wú)用單元收集可能在任何時(shí)候發(fā)生的事實(shí)。所以在編寫(xiě)時(shí)間測(cè)試代碼時(shí)需要考慮這些情況。先來(lái)看一下如何處理無(wú)用單元收集。首先討論一下無(wú)

58、用單元收集的用途。C#語(yǔ)言用有時(shí)被稱(chēng)為堆的存來(lái)給參考類(lèi)型（例如字符串、數(shù)組以與類(lèi)事例對(duì)象）分配存儲(chǔ)空間。堆是用來(lái)保存數(shù)據(jù)項(xiàng)（前面提到的類(lè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)

59、用無(wú)用單元收集器來(lái)進(jìn)行專(zhuān)門(mén)的無(wú)用單元收集。.NET環(huán)境為執(zhí)行無(wú)用單元收集調(diào)用提供了專(zhuān)門(mén)的對(duì)象GC。為了使系統(tǒng)執(zhí)行無(wú)用單元收集，可以有如下簡(jiǎn)單書(shū)寫(xiě)：GC.Collect();但是不是所有都要這樣做的。存儲(chǔ)在堆中的每一個(gè)對(duì)象都有一個(gè)稱(chēng)為finalizer的專(zhuān)門(mén)方法。finalizer方法是在刪除對(duì)象之前執(zhí)行的最后一步。有關(guān)finalizer方法的問(wèn)題是，這些方法不是按照系統(tǒng)方式運(yùn)行的。事實(shí)上，甚至無(wú)法確信對(duì)象的finalizer方法是否真的執(zhí)行了，但是知道在確定刪除對(duì)象之前需要執(zhí)行此對(duì)象的finalizer方法。為了確信這一點(diǎn)，我們添加了一行代碼來(lái)告訴程序等待堆上對(duì)象的所有finalizer方法都

60、運(yùn)行后再繼續(xù)。此代碼行如下：GC.WaitForPendingFinalizers( );已經(jīng)清除了一個(gè)障礙，現(xiàn)在就剩下一個(gè)問(wèn)題了采用正確的線程。在.NET環(huán)境中，程序運(yùn)行在被稱(chēng)為應(yīng)用程序域的進(jìn)程中。這就允許操作系統(tǒng)在同一時(shí)間分開(kāi)運(yùn)行每個(gè)不同的程序。在進(jìn)程，程序或程序的一部分是在線程運(yùn)行的。操作系統(tǒng)通過(guò)線程來(lái)分配程序的執(zhí)行時(shí)間。在用時(shí)間測(cè)試程序代碼時(shí)，需要確信正在進(jìn)行時(shí)間測(cè)試的代碼就在為自身程序分配的進(jìn)程中，而不在操作系統(tǒng)執(zhí)行的其他任務(wù)里。在.NET框架下通過(guò)使用Process類(lèi)可以做到這一點(diǎn)。Process類(lèi)擁有的方法允許選取當(dāng)前的進(jìn)程、選取程序運(yùn)行其的線程，以與選取存儲(chǔ)線程開(kāi)始執(zhí)行時(shí)間的計(jì)