前言前言編者在寫這本書時(shí)遇到了兩個(gè)。第一個(gè)是關(guān)于數(shù)據(jù)結(jié)構(gòu)。應(yīng)該說關(guān)于數(shù)據(jù)結(jié)構(gòu)的C等語言寫的數(shù)據(jù)結(jié)構(gòu)書。所以，在編者寫本書之前，曾經(jīng)感到很為難。目前，C#語言作為微軟在新一C#語言像程序設(shè)計(jì)語言中的一件藝術(shù)品，也吸引著越來越多的開發(fā)。這也使得我院的可視化專業(yè)進(jìn)行專業(yè)C#語言作為該專業(yè)的主要開發(fā)語言。所以說，用C#語言來講授《數(shù)據(jù)結(jié)構(gòu)》課程是我院專業(yè)C#語言寫的數(shù)據(jù)結(jié)構(gòu)目前國內(nèi)基本上是空白。鑒于此，編者決定寫本書。在接下來的寫作過，編者遇到了另外一個(gè)FrameworkFramework3.0版本了。這使得編者感到了微軟技術(shù)的棄寫該書的念頭。但作為教師的責(zé)任和對(duì)新東西的執(zhí)著使得編者一直堅(jiān)持，直到該書完稿。Framework2.0前言前言編者在寫這本書時(shí)遇到了兩個(gè)。第一個(gè)是關(guān)于數(shù)據(jù)結(jié)構(gòu)。應(yīng)該說關(guān)于數(shù)據(jù)結(jié)構(gòu)的C等語言寫的數(shù)據(jù)結(jié)構(gòu)書。所以，在編者寫本書之前，曾經(jīng)感到很為難。目前，C#語言作為微軟在新一C#語言像程序設(shè)計(jì)語言中的一件藝術(shù)品，也吸引著越來越多的開發(fā)。這也使得我院的可視化專業(yè)進(jìn)行專業(yè)C#語言作為該專業(yè)的主要開發(fā)語言。所以說，用C#語言來講授《數(shù)據(jù)結(jié)構(gòu)》課程是我院專業(yè)C#語言寫的數(shù)據(jù)結(jié)構(gòu)目前國內(nèi)基本上是空白。鑒于此，編者決定寫本書。在接下來的寫作過，編者遇到了另外一個(gè)FrameworkFramework3.0版本了。這使得編者感到了微軟技術(shù)的棄寫該書的念頭。但作為教師的責(zé)任和對(duì)新東西的執(zhí)著使得編者一直堅(jiān)持，直到該書完稿。Framework2.0版本來寫的。本書的內(nèi)容81章C#的知結(jié)構(gòu)和圖結(jié)構(gòu)等常用的找常用的各種 及其應(yīng)用以及在.NET框架中相應(yīng)的算法。本書特點(diǎn)C#語言和.NET框架結(jié)合是本書的一大特點(diǎn)。.NET平臺(tái)是微軟推出的一C#了在.NET框架中常用C#在.NET平臺(tái)開發(fā)的技術(shù)技術(shù)?？梢詮谋緯蝎@得許多有益的知識(shí)和使用配套光盤本書配套光盤中包含以下內(nèi)容：1code目錄是本書所有的代碼及一個(gè)《學(xué)生信息管理系統(tǒng)》的代碼。code目錄包含9個(gè)子目錄。習(xí)《C#初級(jí)編程》課程所做的一個(gè)，是學(xué)生在沒有《數(shù)據(jù)結(jié)構(gòu)》課程時(shí)算法。（C#做過這個(gè)系統(tǒng)，所以，把代碼全部給了出來。時(shí)學(xué)生沒有8個(gè)目錄分別對(duì)C#代碼及常用算法都放在相應(yīng)章source子目錄中。（C#語言版）前言的素材使用。其中，chapter1中的project子目錄是各個(gè)例題中應(yīng)用的項(xiàng)目。chapter4由projectsourcesource子目錄。2ppt目錄下是本書的電子課件，可作為教師教學(xué)參考、學(xué)生自學(xué)之用。3pdf目錄下是本書的本，可作為電子供讀者在電腦上學(xué)習(xí)使用。4pictures目錄2003畫的，目的是5章以后章節(jié)的部分圖。30位虛擬學(xué)生的信息，可根據(jù)實(shí)際需要進(jìn)行增刪，但必須修改相應(yīng)的程序代碼。使用本書及光盤的工具安裝它）;前言的素材使用。其中，chapter1中的project子目錄是各個(gè)例題中應(yīng)用的項(xiàng)目。chapter4由projectsourcesource子目錄。2ppt目錄下是本書的電子課件，可作為教師教學(xué)參考、學(xué)生自學(xué)之用。3pdf目錄下是本書的本，可作為電子供讀者在電腦上學(xué)習(xí)使用。4pictures目錄2003畫的，目的是5章以后章節(jié)的部分圖。30位虛擬學(xué)生的信息，可根據(jù)實(shí)際需要進(jìn)行增刪，但必須修改相應(yīng)的程序代碼。使用本書及光盤的工具安裝它）;計(jì)算機(jī)中安裝它）;pictures目錄中的內(nèi)容，那么您需要在計(jì)算機(jī)中安裝它）;算機(jī)中安裝它）;致 謝沒有許多人的幫助，編者是不可能完成本書的。尤其要感謝下面這些人。張?jiān)洪L和院長一直關(guān)注和支持可視化專業(yè)的專業(yè)，并多次詢問該書的進(jìn)度并對(duì)其中的。特別是胡院長，給予指示。如果沒親自指導(dǎo)了專業(yè)有二位，該書是不可能產(chǎn)生和完成的。的和的修訂和做了大量的工作。與他們的合作非常愉快，他們盡力使本書的東西通順流暢。沒有他們的工作，本書不可能出版。最后，編者要感謝的家人。為了寫這本書，編者投入了大量的時(shí)間和精力，犧牲了許多的周末和節(jié)假日。沒有（編者的妻子）和（編者的女兒）的支持，根本不可能有這本書的問世。多少次，編者都想花些時(shí)間陪伴家人，但而放棄了。現(xiàn)到女兒的笑聲了?？偹愀嬉欢温?，編者可以有時(shí)間 地聽盡管編者在寫作過非常認(rèn)真和努力，但由于編者水平有限，書中難免錯(cuò)誤和通過下面的郵件通知編者，編者將不勝感激：:duanez@請(qǐng)?jiān)卩]件的 欄中注明：數(shù)據(jù)結(jié)構(gòu)（C#。編者12月或想法，（C#語言版）目錄I第1章1.1緒論 1數(shù)據(jù)結(jié)構(gòu) 1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性 1基本概念和術(shù)語 .21.2算法 4算法的特性 4算法的評(píng)價(jià)標(biāo)準(zhǔn) 5算法的時(shí)間復(fù)雜度 6數(shù)學(xué)預(yù)備知識(shí) .31.3.4集合 7常用的數(shù)學(xué)術(shù)語 8對(duì)數(shù) 8目錄I第1章1.1緒論 1數(shù)據(jù)結(jié)構(gòu) 1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性 1基本概念和術(shù)語 .21.2算法 4算法的特性 4算法的評(píng)價(jià)標(biāo)準(zhǔn) 5算法的時(shí)間復(fù)雜度 6數(shù)學(xué)預(yù)備知識(shí) .31.3.4集合 7常用的數(shù)學(xué)術(shù)語 8對(duì)數(shù) 8遞歸 91.4C#預(yù)備知識(shí) .2接口 10泛型編程 13本章小結(jié) 20習(xí)題一 20第2章2.1線性表 22線性表的邏輯結(jié)構(gòu) 22線性表的定義 22線性表的基本操作 22順序表 .3順序表的定義 24順序表的基本操作實(shí)現(xiàn) 29順序表應(yīng)用舉例 352.3單鏈表 38單鏈表的定義 39單鏈表的基本操作實(shí)現(xiàn) 46單鏈表應(yīng)用舉例 56其他鏈表 61雙向鏈表 61循環(huán)鏈表 64C#中的線性表 642.42.5本章小結(jié) 67習(xí)題二 67第3章棧和隊(duì)列 693.1棧 6..4棧的定義及基本運(yùn)算 69棧的和運(yùn)算實(shí)現(xiàn) 70棧的應(yīng)用舉例 82C#中的棧 873.2隊(duì)列 87隊(duì)列的定義及基本運(yùn)算 87（C#語言版）目錄II.33.2.4隊(duì)列的和運(yùn)算實(shí)現(xiàn) 89隊(duì)列的應(yīng)用舉例 103C#中的隊(duì)列 104本章小結(jié) 105習(xí)題三 105第4章4.1串和數(shù)組 106串 106串的基本概念 10..4串的及類定義 106串的基本操作的實(shí)現(xiàn) 111C#中的串 1154.2數(shù)組 117數(shù)組的邏輯結(jié)構(gòu) 117數(shù)組的內(nèi)存映象 118C#中的數(shù)組 119本章小結(jié) 121習(xí)題四 121二 123樹 123第5章目錄II.33.2.4隊(duì)列的和運(yùn)算實(shí)現(xiàn) 89隊(duì)列的應(yīng)用舉例 103C#中的隊(duì)列 104本章小結(jié) 105習(xí)題三 105第4章4.1串和數(shù)組 106串 106串的基本概念 10..4串的及類定義 106串的基本操作的實(shí)現(xiàn) 111C#中的串 1154.2數(shù)組 117數(shù)組的邏輯結(jié)構(gòu) 117數(shù)組的內(nèi)存映象 118C#中的數(shù)組 119本章小結(jié) 121習(xí)題四 121二 123樹 123第5章.35.1.4二.25.2.3樹的定義 123樹的相關(guān)術(shù)語 124樹的邏輯表示 125樹的基本操作 1261265.2二二二的定義 127的性質(zhì) 128的結(jié)構(gòu) 129結(jié)構(gòu)的類實(shí)現(xiàn) 1325.2.4二叉鏈表5.2.5二的遍歷 1375.3樹與森林 1415.3.2的轉(zhuǎn)換 1445.3.3森林的遍歷 147樹 147樹的基本概念 147樹類的實(shí)現(xiàn) 149編碼 15.35.5應(yīng)用舉例 1545.6C#中的樹 157本章小結(jié) 158習(xí)題五 1596章圖 161圖的基本概念 161圖的定義 161圖的基本術(shù)語 161（C#語言版）目錄III6.1.3圖的基本操作 1656.2圖的結(jié)構(gòu) 1666.2.1鄰接矩陣 1676.2.2鄰接表 172圖的遍歷 185深度優(yōu)先遍歷 185廣度優(yōu)先遍歷 188圖的應(yīng)用 18..3最小生189最短路徑 199拓?fù)渑判?207本章小結(jié) 210習(xí)題六 210第7章7.17.2排序 213基本概念 213簡單排序 2147.2.1直接排序 214冒泡排序 216簡單選擇排序目錄III6.1.3圖的基本操作 1656.2圖的結(jié)構(gòu) 1666.2.1鄰接矩陣 1676.2.2鄰接表 172圖的遍歷 185深度優(yōu)先遍歷 185廣度優(yōu)先遍歷 188圖的應(yīng)用 18..3最小生189最短路徑 199拓?fù)渑判?207本章小結(jié) 210習(xí)題六 210第7章7.17.2排序 213基本概念 213簡單排序 2147.2.1直接排序 214冒泡排序 216簡單選擇排序 217快速排序 219堆排序 222歸并排序 230基數(shù)排序 232多關(guān)鍵碼排序 232鏈?zhǔn)交鶖?shù)排序 23中排序的比較與討論 235235本章小結(jié) 236習(xí)題七 236第8章查找 2388.1基本概念和術(shù)語 2388.2靜態(tài)查找表 238順序查找 238有序表的折半查找 239索引查找 242動(dòng)態(tài)查找表 243表 2528.38.4表的基本概念 2528.4.1常用的函數(shù)構(gòu)造253的2548.5256本章小結(jié) 256習(xí)題八 256參考文獻(xiàn) 257（C#語言版）1.1數(shù)據(jù)結(jié)構(gòu)1第1章緒論組織數(shù)據(jù)；二是如何在計(jì)算機(jī)同一的不同操作便選擇一個(gè)適合于某個(gè)特定就是數(shù)據(jù)結(jié)構(gòu)這門課程所要研究的主要C#知識(shí)。數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性本書所要用有的人寫出來的程序效率很高，有的人卻用復(fù)雜的來解決一個(gè)簡單的。思考的過的的經(jīng)驗(yàn)，來解決更復(fù)雜更深入的，是提高程序設(shè)計(jì)水平的最有效途徑。數(shù)據(jù)結(jié)構(gòu)正是前人在思索的過所想出的解決如果只學(xué)會(huì)了程序設(shè)計(jì)的語法和語義，那么你只能解決程序設(shè)計(jì)三分之一的問序設(shè)計(jì)上，運(yùn)用最有效的來解決絕大多數(shù)的。數(shù)據(jù)結(jié)構(gòu)形成了程序員基本數(shù)據(jù)結(jié)構(gòu)工(toolkit)。對(duì)于許多常見的，工.NETFrameworkWindows應(yīng)用程序開發(fā)中的工，程序員可以直接拿來或經(jīng)過少許的修改就可以使用，非常方便。的總結(jié)，序設(shè)計(jì)水平。第三個(gè)目的是通過程序設(shè)計(jì)的技能訓(xùn)練促進(jìn)程序員綜合能力的提高。1.1.2基本概念和術(shù)語的章節(jié)中會(huì)多次出現(xiàn)。1、數(shù)據(jù)(Data)數(shù)據(jù)是外部世界信息的載體，它能夠被計(jì)算機(jī)識(shí)別、和處理，是計(jì)算機(jī)程序數(shù)、實(shí)數(shù)或復(fù)數(shù)；也可以是非數(shù)值數(shù)據(jù)，如字符、文字、圖形、圖像、聲音等。2、數(shù)據(jù)元素(Data1.1數(shù)據(jù)結(jié)構(gòu)1第1章緒論組織數(shù)據(jù)；二是如何在計(jì)算機(jī)同一的不同操作便選擇一個(gè)適合于某個(gè)特定就是數(shù)據(jù)結(jié)構(gòu)這門課程所要研究的主要C#知識(shí)。數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性本書所要用有的人寫出來的程序效率很高，有的人卻用復(fù)雜的來解決一個(gè)簡單的。思考的過的的經(jīng)驗(yàn)，來解決更復(fù)雜更深入的，是提高程序設(shè)計(jì)水平的最有效途徑。數(shù)據(jù)結(jié)構(gòu)正是前人在思索的過所想出的解決如果只學(xué)會(huì)了程序設(shè)計(jì)的語法和語義，那么你只能解決程序設(shè)計(jì)三分之一的問序設(shè)計(jì)上，運(yùn)用最有效的來解決絕大多數(shù)的。數(shù)據(jù)結(jié)構(gòu)形成了程序員基本數(shù)據(jù)結(jié)構(gòu)工(toolkit)。對(duì)于許多常見的，工.NETFrameworkWindows應(yīng)用程序開發(fā)中的工，程序員可以直接拿來或經(jīng)過少許的修改就可以使用，非常方便。的總結(jié)，序設(shè)計(jì)水平。第三個(gè)目的是通過程序設(shè)計(jì)的技能訓(xùn)練促進(jìn)程序員綜合能力的提高。1.1.2基本概念和術(shù)語的章節(jié)中會(huì)多次出現(xiàn)。1、數(shù)據(jù)(Data)數(shù)據(jù)是外部世界信息的載體，它能夠被計(jì)算機(jī)識(shí)別、和處理，是計(jì)算機(jī)程序數(shù)、實(shí)數(shù)或復(fù)數(shù)；也可以是非數(shù)值數(shù)據(jù)，如字符、文字、圖形、圖像、聲音等。2、數(shù)據(jù)元素(DataElement)和數(shù)據(jù)項(xiàng)(DataItem)（C#語言版）1.1數(shù)據(jù)結(jié)構(gòu)2數(shù)據(jù)元素是數(shù)據(jù)的基本通常被作為一個(gè)整體進(jìn)行考慮(DataItem)組成。數(shù)據(jù)項(xiàng)是不可分割的、含有意義的最小數(shù)據(jù)，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段(Field)或域(Domain)。例如，在數(shù)據(jù)庫信息處理系統(tǒng)中，數(shù)據(jù)表中的一條就是一個(gè)數(shù)據(jù)元素。這條中的學(xué)生學(xué)號(hào)、姓名、等項(xiàng)，如學(xué)生的、籍貫等，在處理時(shí)不能再進(jìn)行分割；另一種叫做組合項(xiàng)，如學(xué)生的成績，它可以再分為數(shù)學(xué)、物理、化學(xué)等更小的項(xiàng)。3、數(shù)據(jù)對(duì)象(DataObject)數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對(duì)象是{0,±1,±2,±3,…}，字符數(shù)據(jù)對(duì)象是{a,b,c,…}。4、數(shù)據(jù)類型(DataType)對(duì)象的特性。#語言中的字（String，stringtrig列集合字 等操作。數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型，如C#語言中的基本類型（整型、實(shí)型、字符型等；另一類是結(jié)構(gòu)類型，它的成分可以由多個(gè)結(jié)構(gòu)類型C#語言中數(shù)組的成分可以是整型等基本類型，也可以是數(shù)組等結(jié)構(gòu)類型。5、數(shù)據(jù)結(jié)構(gòu)(DataStructure)數(shù)據(jù)結(jié)構(gòu)是相互之間一種或多種特定著一定的稱為結(jié)構(gòu)(Structure)。根據(jù)數(shù)據(jù)元間 的不同特性，通常有4類基本數(shù)據(jù)結(jié)構(gòu)：(1)集合(Set)：如圖1.1(a)1.1數(shù)據(jù)結(jié)構(gòu)2數(shù)據(jù)元素是數(shù)據(jù)的基本通常被作為一個(gè)整體進(jìn)行考慮(DataItem)組成。數(shù)據(jù)項(xiàng)是不可分割的、含有意義的最小數(shù)據(jù)，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段(Field)或域(Domain)。例如，在數(shù)據(jù)庫信息處理系統(tǒng)中，數(shù)據(jù)表中的一條就是一個(gè)數(shù)據(jù)元素。這條中的學(xué)生學(xué)號(hào)、姓名、等項(xiàng)，如學(xué)生的、籍貫等，在處理時(shí)不能再進(jìn)行分割；另一種叫做組合項(xiàng)，如學(xué)生的成績，它可以再分為數(shù)學(xué)、物理、化學(xué)等更小的項(xiàng)。3、數(shù)據(jù)對(duì)象(DataObject)數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對(duì)象是{0,±1,±2,±3,…}，字符數(shù)據(jù)對(duì)象是{a,b,c,…}。4、數(shù)據(jù)類型(DataType)對(duì)象的特性。#語言中的字（String，stringtrig列集合字 等操作。數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型，如C#語言中的基本類型（整型、實(shí)型、字符型等；另一類是結(jié)構(gòu)類型，它的成分可以由多個(gè)結(jié)構(gòu)類型C#語言中數(shù)組的成分可以是整型等基本類型，也可以是數(shù)組等結(jié)構(gòu)類型。5、數(shù)據(jù)結(jié)構(gòu)(DataStructure)數(shù)據(jù)結(jié)構(gòu)是相互之間一種或多種特定著一定的稱為結(jié)構(gòu)(Structure)。根據(jù)數(shù)據(jù)元間 的不同特性，通常有4類基本數(shù)據(jù)結(jié)構(gòu)：(1)集合(Set)：如圖1.1(a)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”的外，不任何其它。1.1(b)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素著一對(duì)一的。多的。(4)圖狀結(jié)構(gòu)(GraphicStructure)1.1(d)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素著多對(duì)多的。(a)集合(b)線性結(jié)構(gòu)(c)樹形結(jié)構(gòu)(d)圖狀結(jié)構(gòu)圖由于集合中的元素的做專門。關(guān)于集合的概念在1.3.1小節(jié)中有。數(shù)據(jù)結(jié)構(gòu)的形式化定義為：（C#語言版）1.1數(shù)據(jù)結(jié)構(gòu)3DS，是一個(gè)二元組，DS=(D,R)其中：D是數(shù)據(jù)元素的有限集合，R是數(shù)據(jù)元間的有限集合。下面通過例題來進(jìn)一步理解后3類數(shù)據(jù)結(jié)構(gòu)?！纠?-1】學(xué)生信息表（1.1所示.）是一個(gè)線性的數(shù)據(jù)結(jié)構(gòu)，表中的每一行是一個(gè)錄。一條（在數(shù)據(jù)庫信息處理系統(tǒng)中，表中的一個(gè)數(shù)據(jù)元素稱為一個(gè)記由學(xué)號(hào)、姓名、行政班級(jí)、和出生年月等數(shù)據(jù)項(xiàng)組成。表中數(shù)據(jù)元間的是一對(duì)一的。學(xué)生信息表【例1-2】是典型的樹形結(jié)構(gòu)，圖1.2是一個(gè)三代的圖中，據(jù)元素稱為結(jié)點(diǎn)，他們之間是一對(duì)多的。其中，有兩個(gè)兒子和一個(gè)女兒，這是一對(duì)三的；一個(gè)兒子有兩個(gè)兒子（的孫子，這是一對(duì)二的關(guān)系；另一個(gè)兒子有一個(gè)兒子（的孫子）和一個(gè)女兒（的孫女，這是一對(duì)二的；女兒有三個(gè)女兒（的外孫女，這是一對(duì)三的。樹形結(jié)構(gòu)具有嚴(yán)格的層次，先有兒子或女兒再有 ，也先有孫子或?qū)O女再有兒子、先有外孫女再有女兒。女兒兒子兒子外孫女1.1數(shù)據(jù)結(jié)構(gòu)3DS，是一個(gè)二元組，DS=(D,R)其中：D是數(shù)據(jù)元素的有限集合，R是數(shù)據(jù)元間的有限集合。下面通過例題來進(jìn)一步理解后3類數(shù)據(jù)結(jié)構(gòu)?！纠?-1】學(xué)生信息表（1.1所示.）是一個(gè)線性的數(shù)據(jù)結(jié)構(gòu)，表中的每一行是一個(gè)錄。一條（在數(shù)據(jù)庫信息處理系統(tǒng)中，表中的一個(gè)數(shù)據(jù)元素稱為一個(gè)記由學(xué)號(hào)、姓名、行政班級(jí)、和出生年月等數(shù)據(jù)項(xiàng)組成。表中數(shù)據(jù)元間的是一對(duì)一的。學(xué)生信息表【例1-2】是典型的樹形結(jié)構(gòu)，圖1.2是一個(gè)三代的圖中，據(jù)元素稱為結(jié)點(diǎn)，他們之間是一對(duì)多的。其中，有兩個(gè)兒子和一個(gè)女兒，這是一對(duì)三的；一個(gè)兒子有兩個(gè)兒子（的孫子，這是一對(duì)二的關(guān)系；另一個(gè)兒子有一個(gè)兒子（的孫子）和一個(gè)女兒（的孫女，這是一對(duì)二的；女兒有三個(gè)女兒（的外孫女，這是一對(duì)三的。樹形結(jié)構(gòu)具有嚴(yán)格的層次，先有兒子或女兒再有 ，也先有孫子或?qū)O女再有兒子、先有外孫女再有女兒。女兒兒子兒子外孫女孫子孫子孫子孫女外孫女外孫女圖【例1-3】圖中，每個(gè)城市是一個(gè)頂點(diǎn)（在圖狀結(jié)構(gòu)中，數(shù)據(jù)元素稱為頂點(diǎn)，它們之間是多對(duì)多的Structure)(Network（C#語言版）學(xué)號(hào)行政班級(jí)出生年月04030300104103男1986.1204030300204103女1987.304030300304103男1986.91.2算法4成都雅安都江堰青城山1.3四城市交通圖據(jù)進(jìn)行操作的集合可以看作是數(shù)據(jù)元間的集合。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicStructure)，數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體 是為了討論沒有。構(gòu)的目的是為了在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)它的操作因此還需要研究在計(jì)算機(jī)中如何表示和 和 ，數(shù)據(jù)的（又叫映像）數(shù)據(jù)元素的表示和結(jié)構(gòu)和鏈?zhǔn)介g的表示和。結(jié)構(gòu)結(jié)構(gòu)順序結(jié)構(gòu)兩種。順序(SequenceStorageStructure)是通過數(shù)據(jù)元素在計(jì)算機(jī) 器中的相對(duì)位置來表示出數(shù)據(jù)元素的邏輯在物理位置相鄰的C#語言中用數(shù)組來實(shí)現(xiàn)順序結(jié)構(gòu)。因?yàn)閿?shù)組所分配的結(jié)構(gòu)(LinkedStorageStructure)對(duì)邏輯上相鄰的數(shù)據(jù)元素不要求其位置必須相鄰。鏈?zhǔn)紻omain)來結(jié)構(gòu)中的數(shù)據(jù)元素稱為結(jié)點(diǎn)(Node)，在結(jié)點(diǎn)中附設(shè)地址域(Address與該結(jié)點(diǎn)相鄰的結(jié)點(diǎn)的地址來實(shí)現(xiàn)結(jié)點(diǎn)間的邏輯 這個(gè)地址稱為(Reference)，這個(gè)地址域稱為域(ReferenceDomain)1.2算法4成都雅安都江堰青城山1.3四城市交通圖據(jù)進(jìn)行操作的集合可以看作是數(shù)據(jù)元間的集合。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicStructure)，數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體 是為了討論沒有。構(gòu)的目的是為了在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)它的操作因此還需要研究在計(jì)算機(jī)中如何表示和 和 ，數(shù)據(jù)的（又叫映像）數(shù)據(jù)元素的表示和結(jié)構(gòu)和鏈?zhǔn)介g的表示和。結(jié)構(gòu)結(jié)構(gòu)順序結(jié)構(gòu)兩種。順序(SequenceStorageStructure)是通過數(shù)據(jù)元素在計(jì)算機(jī) 器中的相對(duì)位置來表示出數(shù)據(jù)元素的邏輯在物理位置相鄰的C#語言中用數(shù)組來實(shí)現(xiàn)順序結(jié)構(gòu)。因?yàn)閿?shù)組所分配的結(jié)構(gòu)(LinkedStorageStructure)對(duì)邏輯上相鄰的數(shù)據(jù)元素不要求其位置必須相鄰。鏈?zhǔn)紻omain)來結(jié)構(gòu)中的數(shù)據(jù)元素稱為結(jié)點(diǎn)(Node)，在結(jié)點(diǎn)中附設(shè)地址域(Address與該結(jié)點(diǎn)相鄰的結(jié)點(diǎn)的地址來實(shí)現(xiàn)結(jié)點(diǎn)間的邏輯 這個(gè)地址稱為(Reference)，這個(gè)地址域稱為域(ReferenceDomain)。206070年代初，出現(xiàn)了大型程序，也相對(duì)，人的算法，這就是人們常說的“程序=數(shù)據(jù)結(jié)構(gòu)+1.2談?wù)勊惴ǖ?。的需要設(shè)計(jì)相應(yīng)的算法。由方面進(jìn)行。(Algorithm)是對(duì)某一特定類型的5性：1、有窮性(Fi有限的。)：一個(gè)算法總是在執(zhí)行有窮步之后結(jié)束，即算法的執(zhí)行時(shí)間是2、確定性(Unambiguousness)：算法的每一個(gè)步驟都必須有確切的含義，即無二義，并且對(duì)于相同的輸入只能有相同的輸出。3、輸入(Input)：一個(gè)算法具有零個(gè)或多個(gè)輸入。它即是在算法開始之前給出的（C#語言版）1.2算法5量。這些輸入是某數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對(duì)象。4、輸出(Output)：一個(gè)算法具有一個(gè)或多個(gè)輸出，并且這些輸出與輸入之間存在著某種特定的。5、能行性(realizability)：算法中的每一步都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次運(yùn)行來實(shí)現(xiàn)。算法的含義與程序非常相似，但二者有區(qū)別。一個(gè)程序不一定滿足有窮性。的指令必須是不一定用計(jì)算機(jī)語言來描述，自然語言、框圖、偽代碼都可以描述算法。C#語言來描述和實(shí)現(xiàn)算法，使讀者能夠閱讀或上機(jī)執(zhí)行，以便更好地理解算法。1.2.2對(duì)于一個(gè)特定的的不標(biāo)準(zhǔn)如下：1(Correctness)輸出處理的明確而無歧義的描述。2、可讀性(Readability)。算法主要是為了人閱讀和交流，其次才是對(duì)于輸入、的執(zhí)行。變成的算法也有助于對(duì)算法中隱藏錯(cuò)誤的排除和算法的移植。和異常情況做出妥善的處理，盡可能使算法沒有意外的情況發(fā)生。4、運(yùn)行時(shí)間(RunningTime)。運(yùn)行時(shí)間是指算法在計(jì)算機(jī)上運(yùn)行所花費(fèi)的時(shí)間，如果有多個(gè)算法可供選擇，應(yīng)盡可能選擇執(zhí)行時(shí)間短的算法。一般來說，執(zhí)行時(shí)間越短，性能越好。所占用的 空間，算法本身所占用的空間和算法在運(yùn)行過 臨時(shí)占用的空間是指算法執(zhí)行過所需要的最大可能選擇間來換取時(shí)間，有時(shí)需要犧牲時(shí)間來換取空間。通常把算法在運(yùn)行過臨時(shí)占用的空間的大小叫算法的空間復(fù)雜度(SpaceComplexity)1.2算法5量。這些輸入是某數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對(duì)象。4、輸出(Output)：一個(gè)算法具有一個(gè)或多個(gè)輸出，并且這些輸出與輸入之間存在著某種特定的。5、能行性(realizability)：算法中的每一步都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次運(yùn)行來實(shí)現(xiàn)。算法的含義與程序非常相似，但二者有區(qū)別。一個(gè)程序不一定滿足有窮性。的指令必須是不一定用計(jì)算機(jī)語言來描述，自然語言、框圖、偽代碼都可以描述算法。C#語言來描述和實(shí)現(xiàn)算法，使讀者能夠閱讀或上機(jī)執(zhí)行，以便更好地理解算法。1.2.2對(duì)于一個(gè)特定的的不標(biāo)準(zhǔn)如下：1(Correctness)輸出處理的明確而無歧義的描述。2、可讀性(Readability)。算法主要是為了人閱讀和交流，其次才是對(duì)于輸入、的執(zhí)行。變成的算法也有助于對(duì)算法中隱藏錯(cuò)誤的排除和算法的移植。和異常情況做出妥善的處理，盡可能使算法沒有意外的情況發(fā)生。4、運(yùn)行時(shí)間(RunningTime)。運(yùn)行時(shí)間是指算法在計(jì)算機(jī)上運(yùn)行所花費(fèi)的時(shí)間，如果有多個(gè)算法可供選擇，應(yīng)盡可能選擇執(zhí)行時(shí)間短的算法。一般來說，執(zhí)行時(shí)間越短，性能越好。所占用的 空間，算法本身所占用的空間和算法在運(yùn)行過 臨時(shí)占用的空間是指算法執(zhí)行過所需要的最大可能選擇間來換取時(shí)間，有時(shí)需要犧牲時(shí)間來換取空間。通常把算法在運(yùn)行過臨時(shí)占用的空間的大小叫算法的空間復(fù)雜度(SpaceComplexity)算法的空間復(fù)雜度比較容易計(jì)算它主要 局部變量所占用的空間和系統(tǒng)為實(shí)現(xiàn)遞歸所使用的堆棧占用的空間。5條標(biāo)準(zhǔn)評(píng)價(jià)的結(jié)果相同的情，代碼量越少越好。實(shí)際上，（C#語言版）1.2算法6性也越大，閱讀起來也越麻煩。計(jì)算。計(jì)算機(jī)的性能由以下因素決定：1、硬件條件。所使用的處理器的類型和速度（比如，使核處理器還是、可使用的內(nèi)存（RAM）以及可使用的外存等。2、實(shí)現(xiàn)算法所使用的計(jì)算機(jī)語言。實(shí)現(xiàn)算法的語言級(jí)別越高，其執(zhí)行效率相對(duì)越低。釋具有更大的靈活性。4、所使用的操作系統(tǒng)作系統(tǒng)的功能主要是管理計(jì)算機(jī)系統(tǒng)的硬件程序、解釋程序等和應(yīng)用程序都在操作系統(tǒng)的1.2.3下運(yùn)行。一個(gè)算法的時(shí)間復(fù)雜度(TimeComplexity)是指該算法的運(yùn)行時(shí)間與規(guī)模的對(duì)應(yīng)結(jié)構(gòu)和原操作最循環(huán)內(nèi)的語句，因此，算法中基本操作語句的頻度是規(guī)模n的某個(gè)函間的增長率和f(n)的增長率相同，或者說，用“O”符號(hào)表示數(shù)量級(jí)的概念。例如，如)，則1)的數(shù)量級(jí)與n2相同，所以T(n)=O（n21.2算法6性也越大，閱讀起來也越麻煩。計(jì)算。計(jì)算機(jī)的性能由以下因素決定：1、硬件條件。所使用的處理器的類型和速度（比如，使核處理器還是、可使用的內(nèi)存（RAM）以及可使用的外存等。2、實(shí)現(xiàn)算法所使用的計(jì)算機(jī)語言。實(shí)現(xiàn)算法的語言級(jí)別越高，其執(zhí)行效率相對(duì)越低。釋具有更大的靈活性。4、所使用的操作系統(tǒng)作系統(tǒng)的功能主要是管理計(jì)算機(jī)系統(tǒng)的硬件程序、解釋程序等和應(yīng)用程序都在操作系統(tǒng)的1.2.3下運(yùn)行。一個(gè)算法的時(shí)間復(fù)雜度(TimeComplexity)是指該算法的運(yùn)行時(shí)間與規(guī)模的對(duì)應(yīng)結(jié)構(gòu)和原操作最循環(huán)內(nèi)的語句，因此，算法中基本操作語句的頻度是規(guī)模n的某個(gè)函間的增長率和f(n)的增長率相同，或者說，用“O”符號(hào)表示數(shù)量級(jí)的概念。例如，如)，則1)的數(shù)量級(jí)與n2相同，所以T(n)=O（n2。22如果一個(gè)算法沒有循環(huán)語句，則算法中基本操作的執(zhí)行頻度與規(guī)模n無的執(zhí)行頻度與規(guī)模n呈線性增大（n平方階O（n2、立方階O（n3、對(duì)數(shù)階O(logn)等。2下面舉例來說明計(jì)算算法時(shí)間復(fù)雜度的。x=n;y=0;while(y<{y=y+1;}分析以下程序的時(shí)間復(fù)雜度。/*n>1*/x)①n，T(n)=O（n。【例1-5】分析以下程序的時(shí)間復(fù)雜度。for(i=1；i<n；++i){for(j=0；j<n；++j){A[i][j]=i*j;}}①（C#語言版）1.3數(shù)學(xué)預(yù)備知識(shí)7為T(n)=O（n2。x=n;y=0;分析以下程序的時(shí)間復(fù)雜度。/*n>1*/while(x>=(y+1)*(y+1)){y=y+1;}①循環(huán)的循環(huán)次數(shù)為n，所以，該程序段中語句①的頻度是n1.3數(shù)學(xué)預(yù)備知識(shí)7為T(n)=O（n2。x=n;y=0;分析以下程序的時(shí)間復(fù)雜度。/*n>1*/while(x>=(y+1)*(y+1)){y=y+1;}①循環(huán)的循環(huán)次數(shù)為n，所以，該程序段中語句①的頻度是nT(n)=O（n?！纠?-7】分析以下程序的時(shí)間復(fù)雜度。for(i=0;i<m;i++){for(j=0;j<t;j++){for(k=0;k<n;k++){c[i][j]=c[i][j]+a[i][k]＊b[k][j];}}}①fort，所以，該程序段中語m*n*t，T(n)=O（m*n*t。1.3本小節(jié)和下面的1.4小節(jié)了本書所要用到的數(shù)學(xué)和C#語言的相關(guān)知識(shí)，也可以等到在后面的章節(jié)中遇到不熟悉的數(shù)學(xué)知識(shí)和C#語言的知識(shí)，才回過頭進(jìn)入第二章的學(xué)習(xí)。雖然是把數(shù)學(xué)知識(shí)和C#語言知識(shí)，但在有關(guān)內(nèi)容時(shí)，為了講授和學(xué)習(xí)的方便，會(huì)把兩方面的內(nèi)容結(jié)合起來講。1.3.1集合1、集合的概念是由一些確定的、彼此不同的成員(Member)或者元素(Element)個(gè)數(shù)稱為集合的基數(shù)(Cardinality)。R345R3、4、5，R的基類型是整型，R3。依賴于集合的基類型，它的成員經(jīng)常有一個(gè)線性順序。（C#語言版）1.3數(shù)學(xué)預(yù)備知識(shí)8是一個(gè)集合。我們把是集合的成員叫做該集合的子集(Subset)，子集中的每個(gè)成的成員，記為：3∈R，6R的成員，記為：6?R。{3，4}1.3數(shù)學(xué)預(yù)備知識(shí)8是一個(gè)集合。我們把是集合的成員叫做該集合的子集(Subset)，子集中的每個(gè)成的成員，記為：3∈R，6R的成員，記為：6?R。{3，4}R的子集。21) 窮舉法：S＝{2，4，6，8，10}；2) 0≤x≤10}。3、集合的特性1)2)3)確定性：任何一個(gè)對(duì)象被確切地是集合中的元素或不是；1.3.2常用的數(shù)學(xué)術(shù)語計(jì)量(nit)按照“b(22字節(jié)縮寫為縮寫為“M(21字節(jié))縮寫為“Function)：n!1n之間所有整數(shù)的連n0的整數(shù)。因此，5!=1·2·3·4·5=120。特別地，0!=1。取下整和取上整(FloorandCeiling)：實(shí)數(shù)x的取下整函數(shù)(Floor)記為?x?，返回不超過x的最大整數(shù)。例如，?3.4?=3，與?3.0?的結(jié)果相同。實(shí)數(shù)x的取上整函數(shù)(Ceiling)記為?x?，返回不小于x的最小整數(shù)。例如，?3.4?=4，與?4.0?的結(jié)果相同。（s,q0≤r＜m。1.3.3對(duì)數(shù)一般地，如果a(a＞0，a≠1)的b次冪等于N，就是ab=N，那么數(shù)b叫做以a為底N的對(duì)數(shù)（Logarithm，記作logaN=b，其中a叫做對(duì)數(shù)的底數(shù)，N叫做真數(shù)。a＞0，bb，N有對(duì)數(shù)。編程行編碼，那么表示n個(gè)編碼至少需要多少位呢？ 是?log2n?。例如，如果要存1000?log21000?=10（101024的可用編碼。第二，對(duì)數(shù)普遍用于分析把分解為更小子算法。在一個(gè)（8.2.3有一個(gè)元素，一共需要進(jìn)行多少次呢？是log2n次。本書中用到的對(duì)數(shù)幾乎都以2（C#語言版）1.3數(shù)學(xué)預(yù)備知識(shí)9分為二，或者用二進(jìn)制位來1.3.4遞歸編碼。一個(gè)算法調(diào)用或間接地調(diào)用的(Recursive)。根據(jù)調(diào)用方式的不同，它分為直接遞歸(DirectRecursion)和間接遞歸(IndirectRecursion)。的是與當(dāng)前相同的直接遞歸。像，這類似于間接遞歸。一個(gè)遞歸算法必須有兩個(gè)部分：初始部分(BaseCase)和遞歸部分程度上比原始調(diào)用參數(shù)更接近初始情況。函數(shù)的遞歸調(diào)用可以理解以遞歸來定義的。如大家熟悉的階乘函數(shù)，我們可以對(duì)n!作如下定義：1.3數(shù)學(xué)預(yù)備知識(shí)9分為二，或者用二進(jìn)制位來1.3.4遞歸編碼。一個(gè)算法調(diào)用或間接地調(diào)用的(Recursive)。根據(jù)調(diào)用方式的不同，它分為直接遞歸(DirectRecursion)和間接遞歸(IndirectRecursion)。的是與當(dāng)前相同的直接遞歸。像，這類似于間接遞歸。一個(gè)遞歸算法必須有兩個(gè)部分：初始部分(BaseCase)和遞歸部分程度上比原始調(diào)用參數(shù)更接近初始情況。函數(shù)的遞歸調(diào)用可以理解以遞歸來定義的。如大家熟悉的階乘函數(shù)，我們可以對(duì)n!作如下定義：(n-1)!,而要計(jì)算(n-1)!需要先調(diào)用factorial(n-2)計(jì)算(n-2)!,以此類推，最factorial(0)0!，n!。階乘函數(shù)的C#語言實(shí)現(xiàn)如下。publicstaticlongfact(intn){if(n<=1){return1;}else{returnn*fact(n-1);}}遞歸包含函數(shù)調(diào)用，函數(shù)調(diào)用需要時(shí)空開銷。所以，遞歸比其他替代選擇諸如（C#語言版）1.4C#預(yù)備知識(shí)10決某些5有的遍歷。C#預(yù)備知識(shí)接口1接口(Interface)定義為一個(gè)約定，實(shí)現(xiàn)接口的類或結(jié)構(gòu)必須遵守該約定。進(jìn)行交互。其實(shí)接口是于類的一個(gè)定義，定義了類之間交互的標(biāo)準(zhǔn)。那么類與類之間直接交互就好了，為什么還要使用接口呢？在程序設(shè)計(jì)過SortedListSortedListSystem.ComparableSortedList，SortedList在理想情，一方面希望SortedList中對(duì)象的類型能夠繼承自現(xiàn)存的System.ObjectSortedList個(gè)類型的能力通常稱作多繼承(MultipleInheritance)。通用語言運(yùn)行時(shí)(CLR)支持單實(shí)現(xiàn)繼承和多接口繼承。單實(shí)現(xiàn)繼承(SingleImplementationInheritance)是指一個(gè)類型只能有一個(gè)基類型。所以，單實(shí)現(xiàn)繼承無法實(shí)現(xiàn)上述SortedList的功能。多接口繼承Inheritance)是指一個(gè)類型可以繼承多個(gè)接口，而接口是1.4C#預(yù)備知識(shí)10決某些5有的遍歷。C#預(yù)備知識(shí)接口1接口(Interface)定義為一個(gè)約定，實(shí)現(xiàn)接口的類或結(jié)構(gòu)必須遵守該約定。進(jìn)行交互。其實(shí)接口是于類的一個(gè)定義，定義了類之間交互的標(biāo)準(zhǔn)。那么類與類之間直接交互就好了，為什么還要使用接口呢？在程序設(shè)計(jì)過SortedListSortedListSystem.ComparableSortedList，SortedList在理想情，一方面希望SortedList中對(duì)象的類型能夠繼承自現(xiàn)存的System.ObjectSortedList個(gè)類型的能力通常稱作多繼承(MultipleInheritance)。通用語言運(yùn)行時(shí)(CLR)支持單實(shí)現(xiàn)繼承和多接口繼承。單實(shí)現(xiàn)繼承(SingleImplementationInheritance)是指一個(gè)類型只能有一個(gè)基類型。所以，單實(shí)現(xiàn)繼承無法實(shí)現(xiàn)上述SortedList的功能。多接口繼承Inheritance)是指一個(gè)類型可以繼承多個(gè)接口，而接口是到SortedList口繼承自任何的System.Object靜態(tài)造器，所以，不能實(shí)例化一個(gè)接口。布就不能再更改，對(duì)已發(fā)布的接口進(jìn)行更改會(huì)破壞現(xiàn)有的代碼。根據(jù)約定，接口類型的名稱要加一個(gè)大寫的字母I前綴。接口定義使用修飾符，例如public、protected、internal以及private等，這和類與結(jié)構(gòu)的定義一樣。當(dāng)然，大部分情public。下面簡單用到的.NET框架中的接口。(1)IComparable（C#語言版）1.4C#預(yù)備知識(shí)11須實(shí)現(xiàn)IComparable接口。由可以排序的類型，例如值類型實(shí)現(xiàn)以創(chuàng)建適合排序等目的類型特定的比較(2)IEnumerable。IEnumerable接口公開枚舉數(shù)，該枚舉數(shù)支持在集合上進(jìn)行簡單迭代。IEnumerable(3)IEnumeratorIEnumerator枚舉數(shù)只集合中的數(shù)據(jù)，枚舉數(shù)無法用于修改基礎(chǔ)集合。ICollectionSystem.CollectionsIDictionary。ICollectionICollection是鍵/Hashtable類。IList接口IDictionary實(shí)現(xiàn)接口實(shí)現(xiàn)是可被排序且可按照索引類。.NETFramework2.0提供了泛型的接口，如IComparable<T>、IEnumerable<T>IEnumerator1.4C#預(yù)備知識(shí)11須實(shí)現(xiàn)IComparable接口。由可以排序的類型，例如值類型實(shí)現(xiàn)以創(chuàng)建適合排序等目的類型特定的比較(2)IEnumerable。IEnumerable接口公開枚舉數(shù)，該枚舉數(shù)支持在集合上進(jìn)行簡單迭代。IEnumerable(3)IEnumeratorIEnumerator枚舉數(shù)只集合中的數(shù)據(jù)，枚舉數(shù)無法用于修改基礎(chǔ)集合。ICollectionSystem.CollectionsIDictionary。ICollectionICollection是鍵/Hashtable類。IList接口IDictionary實(shí)現(xiàn)接口實(shí)現(xiàn)是可被排序且可按照索引類。.NETFramework2.0提供了泛型的接口，如IComparable<T>、IEnumerable<T>IEnumerator<T>ICollection<T>IDictionary<T>和IList<T>的類。關(guān)于泛型的見下一小節(jié)。說到接口，這里要提及1.1.2小節(jié)講到的4類數(shù)據(jù)結(jié)構(gòu)中的集合。從集合的有任何其它的。.NET框架中的集合概念和數(shù)據(jù)結(jié)構(gòu)中的集合概念不盡相同。.NET框架中集合（Collection）定義如下：從.NET的角度看，所謂的集合可以定義為一種對(duì)象，這種對(duì)象提供了一種ICollectionIDictionarySystem.Collections中的“內(nèi)置”集合劃分成了三種類別：，其數(shù)據(jù)項(xiàng)的順序著從集合中取出對(duì)象的順序。System.Collections.Stack和System.Collections.QueueICollectionStackQueue。象數(shù)組一樣。System.Collections.ArrayList類是索引集合的一個(gè)例子。關(guān)于ArrayList。檢索的項(xiàng)。IDictionary集合的內(nèi)容通常按鍵值方式，可以用枚舉的方式排序檢索。System.Collections.HashtableIDictionary接口。關(guān)于將Hashtable。給定集合的功能在很大程度上受到特定接口或其實(shí)現(xiàn)接口的要的情可以被當(dāng)作同類，這就是多態(tài)性(Polymorphism)。（C#語言版）1.4C#預(yù)備知識(shí)122.0System.Collections.Generic用于的類。關(guān)于泛型的見下一小節(jié)。2、接口與抽象類中選擇使用抽象類還是接口需要比較抽象類和接口之間的具體差別。如果要設(shè)計(jì)大的功能單元或創(chuàng)建組件的多個(gè)版本，則使用抽象類。密切的對(duì)象。接口。1.4C#預(yù)備知識(shí)122.0System.Collections.Generic用于的類。關(guān)于泛型的見下一小節(jié)。2、接口與抽象類中選擇使用抽象類還是接口需要比較抽象類和接口之間的具體差別。如果要設(shè)計(jì)大的功能單元或創(chuàng)建組件的多個(gè)版本，則使用抽象類。密切的對(duì)象。接口。3、接口的實(shí)現(xiàn)接口的實(shí)現(xiàn)分為隱式實(shí)現(xiàn)(ImplicitImplementation)和顯式實(shí)現(xiàn)式實(shí)現(xiàn)，如果類或者結(jié)構(gòu)繼承了多個(gè)接口,那么接口中相同名稱成員就要顯式實(shí)現(xiàn)。顯式實(shí)現(xiàn)是通過使用接口的完全限定名來實(shí)現(xiàn)接口成員的。usingSystem;usingSystem.Collections;publicinterfaceIBook{voidShowBook();stringGetTitle();intGetPages();voidSetPages(intpages);}publicclassNewBook:IBook{publicpublicpublicstringtitle;intpages;stringauthor;public{NewBook(stringtitle,stringauthor,intpages)this.title=title;this.author=author;this.pages=pages;}publicstringGetTitle(){（C#語言版）1.4C#預(yù)備知識(shí)13returntitle;}publicintGetPages(){returnpages;}publicvoidSetPages(intpages){this.pages=pages;}publicvoidShowBook(){Console.WriteLine(“Title:{0}”,title);Console.WriteLine(“Author:{0}”,author);Console.WriteLine(“Pages:{0}”,pages);}}publicclassApp{staticvoidMain(){NewBookMyNovel=newNewBook(“Dream”,“Robert”,500);MyNovel.ShowBook();}}1.4C#預(yù)備知識(shí)13returntitle;}publicintGetPages(){returnpages;}publicvoidSetPages(intpages){this.pages=pages;}publicvoidShowBook(){Console.WriteLine(“Title:{0}”,title);Console.WriteLine(“Author:{0}”,author);Console.WriteLine(“Pages:{0}”,pages);}}publicclassApp{staticvoidMain(){NewBookMyNovel=newNewBook(“Dream”,“Robert”,500);MyNovel.ShowBook();}}1.4.2泛型編程泛型(GenericType)是.NETFramework2.0以重用數(shù)據(jù)處理算法，而沒有必要類型特定的代碼。1、泛型陳述在開發(fā)通用容器時(shí)，需要通用容器能各種類型的實(shí)例。在.NET的容器。這意味著，在該容器中使用的objectC#實(shí)現(xiàn)如下：publicclassContainer{readonlyintm_Size;object交互。//容器的容量（C#語言版）1.4C#預(yù)備知識(shí)14intm_ContainerPointer;object[]m_Items;//容器指針，指示最后一個(gè)元素的位置//容器數(shù)組，存放數(shù)據(jù)1.4C#預(yù)備知識(shí)14intm_ContainerPointer;object[]m_Items;//容器指針，指示最后一個(gè)元素的位置//容器數(shù)組，存放數(shù)據(jù)//無參構(gòu)造器publicContainer():this(100){m_ContainerPointer=-1;m_Size=100;}//有參構(gòu)造器publicContainer(intsize){m_Size=size;m_Items=newobject[m_Size];m_ContainerPointer=-1;}獲取容器元素個(gè)數(shù)屬性publicintCount{get{returnm_ContainerPointer;}}//容器是否為空publicboolIsEmpty{get{return(m_ContainerPointer}}==-1);//容器是否已滿publicboolIsFull{get{return(m_ContainerPointer==m_Size-1);}}（C#語言版）1.4C#預(yù)備知識(shí)15//在容器的尾部publicvoidInsert(objectitem){if(IsFull){Console.WriteLine("Containerisreturn;}elseif(IsEmpty){m_Items[++m_ContainerPointer]=}else{m_Items[++m_ContainerPointer]=}full!");item;item;}publicobjectDelete(){if(m_ContainerPointer>=0){returnm_Items[m_ContainerPointer--];}returnnull;}}但是，基于object的容器1.4C#預(yù)備知識(shí)15//在容器的尾部publicvoidInsert(objectitem){if(IsFull){Console.WriteLine("Containerisreturn;}elseif(IsEmpty){m_Items[++m_ContainerPointer]=}else{m_Items[++m_ContainerPointer]=}full!");item;item;}publicobjectDelete(){if(m_ContainerPointer>=0){returnm_Items[m_ContainerPointer--];}returnnull;}}但是，基于object的容器。(1)性能。在使用值類型時(shí)，必須將值類型裝箱(Boxing)以便推送和存(Unboxing)。裝箱和取消裝箱都會(huì)根據(jù)值類型的權(quán)限造成的性能損失。而且，裝箱和取消裝箱操作還會(huì)增加托管堆上的的性能損失，因?yàn)楸仨殢?qiáng)制地將object轉(zhuǎn)換為需要的實(shí)際類型進(jìn)行類型，造成強(qiáng)制類型轉(zhuǎn)換開銷，代碼如下：Containerc=newContainer();c.Insert("1");stringnumber=(strinelete();在任何類型和例如，以下代碼可以正確編譯，但是在運(yùn)行時(shí)將 無效強(qiáng)制類型轉(zhuǎn)換的異常。Containerc=newContainer();（C#語言版）1.4C#預(yù)備知識(shí)16c.Insert(1);下面這條語句能夠編譯，但不是類型安全的，將拋出一個(gè)異常。stringnumber=(string)c.Container();器來克服。publicclassIntContainer{int[]m_Items;publicvoidInsert(intitem){…}public1.4C#預(yù)備知識(shí)16c.Insert(1);下面這條語句能夠編譯，但不是類型安全的，將拋出一個(gè)異常。stringnumber=(string)c.Container();器來克服。publicclassIntContainer{int[]m_Items;publicvoidInsert(intitem){…}publicintDelete(){…}}IntContainerc=newIntContainer();c.Insert(1);intnumber=c.Delete();對(duì)于字publicclassStringContainer{string[]m_Items;publicvoidInsert(stringitem){...}publicstringDelete(){...}}StringContainerc=newStringContainer();c.Insert("1");stringnumber=c.Delete();雖然這解決了性能和類型安全，但引起了下一個(gè)同樣嚴(yán)重的。Framework1.1開發(fā)發(fā)現(xiàn)類型特定的數(shù)據(jù)結(jié)構(gòu)并不實(shí)用，還是選擇使用基于object的數(shù)據(jù)結(jié)構(gòu)，盡管它們2、泛型的概念定義如下：publicclassclassName<T>T，該參數(shù)用一對(duì)分隔符“<>”一個(gè)占位符。它在類的定義代碼中的每次出現(xiàn)都表示一個(gè)非特定的數(shù)據(jù)類型。publicclassContainer<T>{readonlyintm_Size;//容器的容量（C#語言版）1.4C#預(yù)備知識(shí)17intm_ContainerPointer;T[]m_Items;//容器指針，指示最后一個(gè)元素的位置//容器數(shù)組，存放數(shù)據(jù)//1.4C#預(yù)備知識(shí)17intm_ContainerPointer;T[]m_Items;//容器指針，指示最后一個(gè)元素的位置//容器數(shù)組，存放數(shù)據(jù)//構(gòu)造器publicContainer():this(100){m_ContainerPointer=-1;m_Size=100;}//構(gòu)造器publicContainer(intsize){m_Size=size;m_Items=newT[m_Size];m_ContainerPointer=-1;}獲取容器元素個(gè)數(shù)屬性publicintCount{get{returnm_ContainerPointer;}}//容器是否為空publicboolIsEmpty{get{return(m_ContainerPointer}}==-1);//容器是否已滿publicboolIsFull{get{return(m_ContainerPointer==m_Size-}}1);（C#語言版）1.4C#預(yù)備知識(shí)18//在容器的尾部publicvoidInsert(objectitem){if(IsFull){Console.WriteLine("Containerisreturn;}elseif(IsEmpty){m_Items[++m_ContainerPointer]=}else{m_Items[++m_ContainerPointer]=}full!");item;item;}publicobjectDelete(){if(m_ContainerPointer>=0){returnm_Items[m_ContainerPointer--];}returnnull;}}objectobject的地方在一般容器非靜態(tài)和靜態(tài)的字段1.4C#預(yù)備知識(shí)18//在容器的尾部publicvoidInsert(objectitem){if(IsFull){Console.WriteLine("Containerisreturn;}elseif(IsEmpty){m_Items[++m_ContainerPointer]=}else{m_Items[++m_ContainerPointer]=}full!");item;item;}publicobjectDelete(){if(m_ContainerPointer>=0){returnm_Items[m_ContainerPointer--];}returnnull;}}objectobject的地方在一般容器非靜態(tài)和靜態(tài)的字段、地使用類型參數(shù)來指代數(shù)據(jù)類型，用來定義字段類型和成員的參數(shù)類型，以及在類型參數(shù)在作為傳遞給成員的執(zhí)行代碼中定義局部變量的類型。為參數(shù)和輸出參數(shù)，甚至可以是數(shù)組參數(shù)。3、泛型實(shí)現(xiàn)#們的方式重要差異。與C++模板相比，C#泛型可以提供增強(qiáng)的安全性，但C++以內(nèi)聯(lián)方式代碼，并且將每個(gè)出現(xiàn)一般類型參數(shù)的地方替換為指定的類型。（C#語言版）1.4C#預(yù)備知識(shí)19已經(jīng)在應(yīng)用器負(fù)責(zé)解決該足跡。2.0IL（中間語言）CLR本身中具有本機(jī)IL，就像其他任何類型IL只包含實(shí)際特定類型的參數(shù)或占位符，并有泛型操作。泛型代碼的元數(shù)據(jù)中包含泛型信息。IL指令支持真正的泛型實(shí)例化工作以“on-demand”JIT當(dāng)進(jìn)ILT，JITIL元數(shù)據(jù)好像從未涉及到泛型一樣。這樣，JIT編譯器就可以確保IntelliSense。參數(shù)的正確性，實(shí)IL代碼編譯類型。如果本機(jī)指定的是值類型，則JIT1.4C#預(yù)備知識(shí)19已經(jīng)在應(yīng)用器負(fù)責(zé)解決該足跡。2.0IL（中間語言）CLR本身中具有本機(jī)IL，就像其他任何類型IL只包含實(shí)際特定類型的參數(shù)或占位符，并有泛型操作。泛型代碼的元數(shù)據(jù)中包含泛型信息。IL指令支持真正的泛型實(shí)例化工作以“on-demand”JIT當(dāng)進(jìn)ILT，JITIL元數(shù)據(jù)好像從未涉及到泛型一樣。這樣，JIT編譯器就可以確保IntelliSense。參數(shù)的正確性，實(shí)IL代碼編譯類型。如果本機(jī)指定的是值類型，則JIT編譯器將泛型類型參數(shù)替換為特定的值JIT編譯器跟蹤已經(jīng)生成的類型特定的IL代碼。如果JIT編譯器用已經(jīng)編譯機(jī)代碼的值類型編譯泛型IL代碼，則只是返回代碼的。因?yàn)镴IT編譯器在以后的所有場(chǎng)合中都將使用相同的值類如果本機(jī)指定的是代碼膨脹。IL代碼中的泛型參數(shù)替型參數(shù)的請(qǐng)求中，都將使用該代碼。JIT編譯器只會(huì)重新使用實(shí)際代碼。實(shí)例仍然按照它們離開托管堆的大小分配空間，并且沒有強(qiáng)制類型轉(zhuǎn)換。4、泛型的好處泛型使代碼可以重用，類型和內(nèi)部數(shù)據(jù)可以在不導(dǎo)致代碼膨脹的情更任何類型（ 將來的類型）來重用它，并且全部具有編譯器支持和類型安全。因?yàn)榉盒痛a類型進(jìn)行向下強(qiáng)制類型轉(zhuǎn)換，所以性能得到顯著提高。對(duì)于值類型，性能通常會(huì)提高200%；類型，在 該類型時(shí)，可以預(yù)期性能最多提高100%（當(dāng)然，整個(gè)應(yīng)對(duì)于用程序的性能可能會(huì)提高，也可能5、泛型類與泛型接口提高。泛型類封裝了不表、 表、棧、隊(duì)列、。這些類中的操作，如對(duì)容器添加、刪除元素，不論所的數(shù)據(jù)是何種類型，都執(zhí)行幾乎同樣的操作。.NETFramework2.0類庫System.Collections.Generic中所提供的容器類。有關(guān)使用這些類的詳細(xì)信息，請(qǐng)參見基礎(chǔ)類庫中的泛型。直至達(dá)到一般性和可用性的最佳平衡。IComparable，以避免值類型上的裝箱和拆箱操作。.NETFramework2.0類庫定義了幾個(gè)新的泛型接口，以配合System.Collections.Generic中新容器類的使用。本書后面章節(jié)有許多有型接口的例子，這里不再舉例說明。（C#語言版）本章小結(jié)、習(xí)題一20本章小結(jié)本章首先了數(shù)據(jù)結(jié)構(gòu)及其相關(guān)的概念，數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、一種或多種特定數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)般有4類：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。集合中的數(shù)據(jù)元素除了屬于“同一集合這一。線性結(jié)構(gòu)中的數(shù)據(jù)元間存在一對(duì)一的間一對(duì)多的據(jù)元間多對(duì)多的性結(jié)構(gòu)。樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)屬于非線性結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)又叫結(jié)構(gòu)，是數(shù)據(jù)元素在計(jì)算機(jī)中的方式。結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)是在計(jì)算機(jī)中把邏輯上相鄰的數(shù)據(jù)元素的 單元中鏈?zhǔn)浇Y(jié)構(gòu)是邏輯上相鄰的數(shù)據(jù)元素不一定鄰的單元中，數(shù)據(jù)元間的邏輯用表示。求解的運(yùn)行時(shí)間與規(guī)模的對(duì)應(yīng)度）作為算法的時(shí)間復(fù)雜度。最后，本章簡單了本書要用到的數(shù)學(xué)知識(shí)和C#語言知識(shí)。數(shù)學(xué)知識(shí)主要了接口和泛型編程。習(xí)題一1.1簡述下列術(shù)語。數(shù)據(jù)元素算法。數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1.51.6數(shù)據(jù)結(jié)構(gòu)課程的主要目的是什么？算法的特性是什么？評(píng)價(jià)算法的標(biāo)準(zhǔn)是什么？分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。for(inti=0;i<n;++i){++p;}for本章小結(jié)、習(xí)題一20本章小結(jié)本章首先了數(shù)據(jù)結(jié)構(gòu)及其相關(guān)的概念，數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、一種或多種特定數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)般有4類：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。集合中的數(shù)據(jù)元素除了屬于“同一集合這一。線性結(jié)構(gòu)中的數(shù)據(jù)元間存在一對(duì)一的間一對(duì)多的據(jù)元間多對(duì)多的性結(jié)構(gòu)。樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)屬于非線性結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)又叫結(jié)構(gòu)，是數(shù)據(jù)元素在計(jì)算機(jī)中的方式。結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)是在計(jì)算機(jī)中把邏輯上相鄰的數(shù)據(jù)元素的 單元中鏈?zhǔn)浇Y(jié)構(gòu)是邏輯上相鄰的數(shù)據(jù)元素不一定鄰的單元中，數(shù)據(jù)元間的邏輯用表示。求解的運(yùn)行時(shí)間與規(guī)模的對(duì)應(yīng)度）作為算法的時(shí)間復(fù)雜度。最后，本章簡單了本書要用到的數(shù)學(xué)知識(shí)和C#語言知識(shí)。數(shù)學(xué)知識(shí)主要了接口和泛型編程。習(xí)題一1.1簡述下列術(shù)語。數(shù)據(jù)元素算法。數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)1.51.6數(shù)據(jù)結(jié)構(gòu)課程的主要目的是什么？算法的特性是什么？評(píng)價(jià)算法的標(biāo)準(zhǔn)是什么？分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。for(inti=0;i<n;++i){++p;}for(inti<0;i<n;++i){for(intj=0;j<m;++j){++p;}}(4)i=1;（C#語言版）本章小結(jié)、習(xí)題一21while(i<=本章小結(jié)、習(xí)題一21while(i<=n){i*=3;}(5)inti=1;intk=0;do{k=k+10*i;++i;}（C#語言版）2.1線性表的邏輯結(jié)構(gòu)22第2章線性表線性表是最簡單、最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表是線性結(jié)構(gòu)的抽象間一對(duì)一的線性種一對(duì)一的指的是數(shù)據(jù)元間的位置（1除第一個(gè)位置的數(shù)據(jù)（2除最后一個(gè)位置的構(gòu)。數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的順序鏈?zhǔn)浇Y(jié)線性表的邏輯結(jié)構(gòu)線性表的定義線性表(List)n(n≥0)個(gè)相同類型的數(shù)據(jù)元素的有限序列。對(duì)于這據(jù)元素個(gè)性表中的數(shù)據(jù)元素都屬于同一類型。線性表通常記為：L=(a1,a2,…,ai-1,ai,ai+1,…,an)，L是英文單詞list的第12.1線性表的邏輯結(jié)構(gòu)22第2章線性表線性表是最簡單、最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表是線性結(jié)構(gòu)的抽象間一對(duì)一的線性種一對(duì)一的指的是數(shù)據(jù)元間的位置（1除第一個(gè)位置的數(shù)據(jù)（2除最后一個(gè)位置的構(gòu)。數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的順序鏈?zhǔn)浇Y(jié)線性表的邏輯結(jié)構(gòu)線性表的定義線性表(List)n(n≥0)個(gè)相同類型的數(shù)據(jù)元素的有限序列。對(duì)于這據(jù)元素個(gè)性表中的數(shù)據(jù)元素都屬于同一類型。線性表通常記為：L=(a1,a2,…,ai-1,ai,ai+1,…,an)，L是英文單詞list的第1的數(shù)據(jù)元素，我們稱作最后一個(gè)元素。n為線性表的表長，n=0時(shí)的線性表被稱為空表（EmptyList。線性表中的數(shù)據(jù)元間著前后次序的位置ai-1稱為ai的直接前驅(qū)，將ai稱為ai+1的直接后繼。除a1外，其余元素只有一個(gè)直接前驅(qū)，因?yàn)閍1是第一個(gè)元素，所以它沒有前驅(qū)。除an外，其余元素只有一個(gè)直接后繼，因?yàn)閍n是最后一個(gè)元素，所以它沒有后繼。線性表的形式化定義為：線性表(List)簡記為L，是一個(gè)二元組，L(D,R)其中：D是數(shù)據(jù)元素的有限集合。R是數(shù)據(jù)元間的有限集合。100(2,4,6,…,100)名都不一樣）也可以用一個(gè)線性表來表示：(“zhangsan”,”lisi”,”wangwu”,”zhaoliu”,”sunqi”,”huangba”)表中數(shù)據(jù)元素的類型為字。的線性表又稱文件(File)。例如，例子1.1中的學(xué)生信息表就是一和出生年月等數(shù)據(jù)項(xiàng)組成。2.1.2線性表的基本操作（C#語言版）2.1線性表的邏輯結(jié)構(gòu)23首先應(yīng)該考慮這種表示法要支持的基本操作。從線性表的定義可知，一個(gè)線性表在長度上應(yīng)該能夠增長和縮短，也就是說，線性表最重要的操作應(yīng)該能夠性表的任何位置和刪除元素。可以生成和清除（或者重新初始化）線性表。理的具體實(shí)現(xiàn)只有在確定了線性表的以根據(jù)不同的結(jié)構(gòu)派生出一系列相關(guān)的運(yùn)算來。C#接口的形式表示線性表，接口中的用應(yīng)用更復(fù)雜的類型來代替。線性表的接口如下所示。publicinterfaceIListDS<T>intGetLength();{//求長度//清空操作voidboolvoidvoidClear();IsEmpty();Append(Titem);//線性表是否為空//附加操作Insert(Titem,inti);//操作TDelete(inti);TGetElem(inti);intLocate(Tvalue);//刪除操作//取//按值查找}為了和.NETIListIList表示數(shù)據(jù)結(jié)構(gòu)。下面對(duì)線性表的基本操作進(jìn)行說明。1、求長度：GetLength()初始條件：線性表；操作結(jié)果：返回線性表中所有數(shù)據(jù)元素的個(gè)數(shù)。2、清空操作：Clear()初始條件：線性表且有數(shù)據(jù)元素；操作結(jié)果：從線性表中清除所有數(shù)據(jù)元素，線性表為空。3、線性表是否為空：IsEmpty()初始條件：線性表；2.1線性表的邏輯結(jié)構(gòu)23首先應(yīng)該考慮這種表示法要支持的基本操作。從線性表的定義可知，一個(gè)線性表在長度上應(yīng)該能夠增長和縮短，也就是說，線性表最重要的操作應(yīng)該能夠性表的任何位置和刪除元素?？梢陨珊颓宄ɑ蛘咧匦鲁跏蓟┚€性表。理的具體實(shí)現(xiàn)只有在確定了線性表的以根據(jù)不同的結(jié)構(gòu)派生出一系列相關(guān)的運(yùn)算來。C#接口的形式表示線性表，接口中的用應(yīng)用更復(fù)雜的類型來代替。線性表的接口如下所示。publicinterfaceIListDS<T>intGetLength();{//求長度//清空操作voidboolvoidvoidClear();IsEmpty();Append(Titem);//線性表是否為空//附加操作Insert(Titem,inti);//操作TDelete(inti);TGetElem(inti);intLocate(Tvalue);//刪除操作//取//按值查找}為了和.NETIListIList表示數(shù)據(jù)結(jié)構(gòu)。下面對(duì)線性表的基本操作進(jìn)行說明。1、求長度：GetLength()初始條件：線性表；操作結(jié)果：返回線性表中所有數(shù)據(jù)元素的個(gè)數(shù)。2、清空操作：Clear()初始條件：線性表且有數(shù)據(jù)元素；操作結(jié)果：從線性表中清除所有數(shù)據(jù)元素，線性表為空。3、線性表是否為空：IsEmpty()初始條件：線性表；操作結(jié)果：如果線性表為空返回true，否則返回false。4、附加操作：Append(Titem)初始條件：線性表且未滿；操作結(jié)果：將值為item的新元素添加到表的末尾。5、操作：Insert(Titem,inti)初始條件：線性表，位置正確()(1≤i≤n+1,n為前的表長)。操作結(jié)果：i一個(gè)值為item的新元素，這樣使得原序號(hào)為i,i+1,…,n的數(shù)據(jù)元素的序號(hào)變?yōu)閕+1,i+2,…,n+1，后表長=原（C#語言版）2.2順序表24表長+1。6、刪除操作：Delete(inti)初始條件：線性表長)。且不為空，刪除位置正確(1≤i≤n,n為刪除前的表操作結(jié)果：性表中刪除序號(hào)為i的數(shù)據(jù)元素，返回刪除后的數(shù)據(jù)元素。表長=7、取長-1。：GetElem(inti)長；操作結(jié)果：返回線性表中第i個(gè)數(shù)據(jù)元素。8、按值查找：Locate(Tvalue)初始條件：線性表。操作結(jié)果：性表中查找值為value的數(shù)據(jù)元素，其結(jié)果返回 性表中首次出現(xiàn)的值為value的數(shù)據(jù)元素的序號(hào)，稱為查找性表中未實(shí)際上，在.NET框架中，許多類的求長度、空等操作都用屬性來表示，這里在接口中定義為是為了說明數(shù)據(jù)結(jié)構(gòu)的操作運(yùn)算。實(shí)際上，屬性也是 說明了。順序表順序表的定義單元，這就是線性表的順序 。線性一個(gè)地放進(jìn)順序的表的順序 中用一塊地址連續(xù)的空間依次存放線性表的數(shù)據(jù)元素，用這種方式 是表中相鄰的數(shù)據(jù)元素在內(nèi)存中位置也相鄰。01…i-1i… n-1…maxsize-12.2順序表24表長+1。6、刪除操作：Delete(inti)初始條件：線性表長)。且不為空，刪除位置正確(1≤i≤n,n為刪除前的表操作結(jié)果：性表中刪除序號(hào)為i的數(shù)據(jù)元素，返回刪除后的數(shù)據(jù)元素。表長=7、取長-1。：GetElem(inti)長；操作結(jié)果：返回線性表中第i個(gè)數(shù)據(jù)元素。8、按值查找：Locate(Tvalue)初始條件：線性表。操作結(jié)果：性表中查找值為value的數(shù)據(jù)元素，其結(jié)果返回 性表中首次出現(xiàn)的值為value的數(shù)據(jù)元素的序號(hào)，稱為查找性表中未實(shí)際上，在.NET框架中，許多類的求長度、空等操作都用屬性來表示，這里在接口中定義為是為了說明數(shù)據(jù)結(jié)構(gòu)的操作運(yùn)算。實(shí)際上，屬性也是 說明了。順序表順序表的定義單元，這就是線性表的順序 。線性一個(gè)地放進(jìn)順序的表的順序 中用一塊地址連續(xù)的空間依次存放線性表的數(shù)據(jù)元素，用這種方式 是表中相鄰的數(shù)據(jù)元素在內(nèi)存中位置也相鄰。01…i-1i… n-1…maxsize-1↑last結(jié)構(gòu)示意圖假設(shè)順序表中的每個(gè)數(shù)據(jù)元素占w個(gè)為Loc(ai)，則有：1≤i≤nLoc(ai)=Loc(a1)+(i-1)*w式中的Loc(a1)表示第一個(gè)數(shù)據(jù)元素a1的地址，也是順序表的起始地址，(BaseAddress)數(shù)據(jù)元素所占的單元的個(gè)數(shù)就可以求出順序表中任何一個(gè)數(shù)據(jù)元素的具有隨機(jī)存取的特點(diǎn)。C#語言中的數(shù)組在內(nèi)存中占用的空間就是一組連續(xù)的 性。區(qū)域的特（C#語言版）a1a2…ai-1aiai+1…an…2.2順序表25把順序表看作是一個(gè)泛型類，類名叫SeqList<T?！盨eq是英文單IListDS<T>。用數(shù)組來存SeqList<T>data來表示。由于經(jīng)常需要在順序表中System.Array2.2順序表25把順序表看作是一個(gè)泛型類，類名叫SeqList<T?！盨eq是英文單IListDS<T>。用數(shù)組來存SeqList<T>data來表示。由于經(jīng)常需要在順序表中System.ArrayLength屬性來表示。但為了說明SeqList<T>類中構(gòu)造器的參數(shù)sizedata[0]maxsizeSeqList<T>last表示順序表中最后一個(gè)數(shù)據(jù)元素在數(shù)組中的位置。如果順序表中有數(shù)據(jù)元素時(shí)，last的變數(shù)據(jù)元素需要序表已滿不能法外，還需要實(shí)現(xiàn)順序表是否已滿等成員 。publicclassSeqList<T>IListDS<T>privateintmaxsize;privateT[]data;privateintlast;//順序表的容量//數(shù)組，用于//指示順序表最后一個(gè)元素的位置//索引器publicTthis[intindex]{get{returndata[index];}set{data[index]=value;}}publicintLast{get{returnlast;}}//容量屬性publicintMaxsize（C#語言版）2.2順序表26{get{returnmaxsize;}set{maxsize=value;}}2.2順序表26{get{returnmaxsize;}set{maxsize=value;}}//構(gòu)造器publicSeqList(intsize){data=newT[size];maxsize=size;last=-1;}//求順序表的長度publicintGetLength(){returnlast+1;}//清空順序表publicvoidClear(){last=-1;}/順序表是否為空publicboolIsEmpty(){if(last==-1){returntrue;}else{returnfalse;}}（C#語言版）2.2順序表27/順序表是否為滿publicboolIsFull(){if(last==maxsize-1)2.2順序表27/順序表是否為滿publicboolIsFull(){if(last==maxsize-1){returntrue;}else{returnfalse;}}publicvoidAppend(Titem){if(IsFull()){Console.WriteLine("Listisfull");return;}data[++last]=item;}i個(gè)數(shù)據(jù)元素的位置publicvoidInsert(Titeminti){if(IsFull()){一個(gè)數(shù)據(jù)元素Console.WriteLine("Listisfull");return;}if(i<1||i>last+2){Console.WriteLine("Positioniserror!");return;}if(i==last+2){data[last+1]=item;（C#語言版）2.2順序表28}else{for(intj=2.2順序表28}else{for(intj=last;j>=i-1;--j){data[j+1]=data[j];}data[i-1]=item;}++last;}i個(gè)數(shù)據(jù)元素publicTDelete(i