數(shù)據(jù)結(jié)構(gòu)各章考試復(fù)習(xí)要點(diǎn)(打印版)

數(shù)據(jù)結(jié)構(gòu)各章考試復(fù)習(xí)要點(diǎn)(打印版)數(shù)據(jù)(Data)數(shù)據(jù)是信息的載體。它能夠被計(jì)算機(jī)識別、存儲(chǔ)和加工處理，是計(jì)算機(jī)程序加工的"原料"。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，數(shù)據(jù)的范疇包括：整數(shù)、實(shí)數(shù)、字符串圖像和聲音等。數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素、結(jié)點(diǎn)、頂點(diǎn)、記錄一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)(也可稱為字段、域、屬性)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識單位。數(shù)據(jù)結(jié)構(gòu)(DataStrueture)數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。1．?dāng)?shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicalStrueture)；數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(StorageStructure)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)(亦稱為映象)，它依賴于計(jì)算機(jī)語言。對機(jī)器語言而言，存儲(chǔ)結(jié)構(gòu)是具體的。一般，只在高級語言的層次上討論存儲(chǔ)結(jié)構(gòu)。③數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)施加的操作。數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。最常用的檢索、插入、刪除、更新、排序等運(yùn)算實(shí)際上只是在在上面的學(xué)生成績表中，可能要經(jīng)常查看某一學(xué)生的成績；當(dāng)學(xué)生退學(xué)時(shí)要?jiǎng)h除相應(yīng)的結(jié)點(diǎn)；進(jìn)來新學(xué)生時(shí)要增加結(jié)點(diǎn)。究竟如何進(jìn)行查找、刪除、插入，這就是數(shù)據(jù)的運(yùn)算問題。搞清楚了上述三個(gè)問題，也就弄清了學(xué)生成績表這個(gè)數(shù)據(jù)結(jié)構(gòu)。2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分類在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：（1）線性結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。（2）非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。抽象的數(shù)據(jù)上所施加的一系列抽象的操作。所謂抽象的操作，是指我們只知道這些操作是"做什么"，而無須考慮"如何做"。只有確定了存儲(chǔ)結(jié)構(gòu)之后，才考慮如何具體實(shí)現(xiàn)這些運(yùn)算。為了增加對數(shù)據(jù)結(jié)構(gòu)的感性認(rèn)識，下面舉例來說明有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念?！纠?．1】學(xué)生成績表，見下表。概論-基本概念和術(shù)語（二）3．?dāng)?shù)據(jù)的四種基本存儲(chǔ)方法數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用以下四種基本存儲(chǔ)方法得到：（1）順序存儲(chǔ)方法該方法把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。表中的每一行是一個(gè)數(shù)據(jù)元素（或記錄、結(jié)點(diǎn)），它由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對表中任一個(gè)結(jié)點(diǎn)，與它相鄰且在它前面的結(jié)點(diǎn)（亦稱為直接前趨（ImmediatePredeceor））最多只有一個(gè)；與表中任一結(jié)點(diǎn)相鄰且在其后的結(jié)點(diǎn)（亦稱為直接后繼（ImmediateSucceor））也最多只有一個(gè)。表中只有第一個(gè)結(jié)點(diǎn)沒有直接前趨，故稱為開始結(jié)點(diǎn)；也只有最后一個(gè)結(jié)點(diǎn)沒有直接后繼。故稱之為終端結(jié)點(diǎn)。例如，表中"馬二"所在結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)分別是"丁一"和"張三"所在的結(jié)點(diǎn)，上述結(jié)點(diǎn)間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)。（2） 存儲(chǔ)結(jié)構(gòu)該表的存儲(chǔ)結(jié)構(gòu)是指用計(jì)算機(jī)語言如何表示結(jié)點(diǎn)之間的這種關(guān)系，即表中的結(jié)點(diǎn)是順序鄰接地存儲(chǔ)在一片連續(xù)的單元之中，還是用指針將這些結(jié)點(diǎn)鏈接在一起？（3） 數(shù)據(jù)的運(yùn)算注意：在表中指出數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、開始結(jié)點(diǎn)和終端結(jié)點(diǎn)等概念邏輯結(jié)構(gòu)由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)(SequentialStorageStrueture)，通常借助程序語言的數(shù)組描述。該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實(shí)現(xiàn)順序存儲(chǔ)。(2)鏈接存儲(chǔ)方法該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(LinkedStorageStrueture),通常借助于程序語言的指針類型描述。(3)索引存儲(chǔ)方法按"值"是否可分解，可將數(shù)據(jù)類型劃分為兩類：該方法通常在儲(chǔ)存結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。原子類型：其值不可分解。通常是由語言直接提供。索引表由若干索引項(xiàng)組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該索引表稱之為稠密索引(Denelnde某)。若一組結(jié)點(diǎn)在索引表中只對應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引(Sparelnde某)索引項(xiàng)的一般形式是：(關(guān)鍵字、地址)關(guān)鍵字是能唯一標(biāo)識一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。稠密索引中索引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲(chǔ)位置；稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。(4)散列存儲(chǔ)方法該方法的基本思想是：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。四種基本存儲(chǔ)方法，既可單獨(dú)使用，也可組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映像。同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。選擇何種存儲(chǔ)結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮運(yùn)算方便及算法的時(shí)空要求。4．?dāng)?shù)據(jù)結(jié)構(gòu)三方面的關(guān)系存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個(gè)方面：同一邏輯結(jié)構(gòu)的不同存儲(chǔ)結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來標(biāo)識?！纠烤€性表是一種邏輯結(jié)構(gòu)，若采用順序方法的存儲(chǔ)表示，可稱其為順序表；若采用鏈?zhǔn)酱鎯?chǔ)方法，則可稱其為鏈表；若采用散列存儲(chǔ)方法則可稱為散列表。Potcondition:執(zhí)行本操作后系統(tǒng)的狀態(tài)//〃系統(tǒng)〃可看作某個(gè)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個(gè)方面。在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之后，按定義的運(yùn)算集合及其運(yùn)算的性質(zhì)不同，也可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)?！纠咳魧€性表上的插入、刪除運(yùn)算限制在表的一端進(jìn)行，則該線性表稱之為棧；若對插入限制在表的一端進(jìn)行，而刪除限制在表的另一端Operation2://操作2 }//ADT【例】C語言的整型、字符型等標(biāo)準(zhǔn)類型及指針等簡單的導(dǎo)出類型；②結(jié)構(gòu)類型：其值可分解為若干個(gè)成分（或稱為分量）。是用戶借助于語言提供的描述機(jī)制自己定義的，它通常是由標(biāo)準(zhǔn)類型派生的，故它也是一種導(dǎo)出類型?！纠緾的數(shù)組、結(jié)構(gòu)等類型。抽象數(shù)據(jù)類型（AbtractType簡稱ADT）ADT是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作?？梢钥醋魇菙?shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。一個(gè)ADT可描述為：ADTADT-Name{Data://數(shù)據(jù)說明數(shù)據(jù)元素之間邏輯關(guān)系的描述Operation://操作說明Operationl://操作1,它通?？捎肅或C++的函數(shù)原型來描述Input:對輸入數(shù)據(jù)的說明Precondition:執(zhí)行本操作前系統(tǒng)應(yīng)滿足的狀態(tài)//可看作初始條件Proce:對數(shù)據(jù)執(zhí)行的操作Output:對返回?cái)?shù)據(jù)的說明進(jìn)行,則該線性表稱之為隊(duì)列。更進(jìn)一步,若線性表采用順序表或鏈表作為存儲(chǔ)結(jié)構(gòu),則對插入和刪除運(yùn)算做了上述限制之后,可分別得到順序?；蜴湕?順序隊(duì)列或鏈隊(duì)列。數(shù)據(jù)類型（DataType）所謂數(shù)據(jù)類型是一個(gè)值的集合以及在這些值上定義的一組操作的總稱通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?！纠?.2】C語言的〃整數(shù)類型〃就定義了一個(gè)整數(shù)可取值的范圍（其最大值INT-MA某依賴于具體機(jī)器）以及對整數(shù)可施加的加、減、乘、除和取模等操作。抽象數(shù)據(jù)類型可以看作是描述問題的模型,它獨(dú)立于具體實(shí)現(xiàn)。它的優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通過在ADT里定義的某些操作來訪問其中的數(shù)據(jù)，從而實(shí)現(xiàn)了信息隱藏。在C++中，我們可以用類（包括模板類）的說明來表示ADT,用類的實(shí)現(xiàn)來實(shí)現(xiàn)ADT【參閱[10]】。因此，C++中實(shí)現(xiàn)的類相當(dāng)于是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及其在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的對數(shù)據(jù)的操作。ADT和類的概念實(shí)際上反映了程序或軟件設(shè)計(jì)的兩層抽象：ADT相當(dāng)于是在概念層（或稱為抽象層）上描述問題，而類相當(dāng)于是在實(shí)現(xiàn)層上描述問題。此外，C++中的類只是一個(gè)由用戶定義的普通類型，可用它來定義變量（稱為對象或類的實(shí)例）。因此，在C++中，最終是通過操作對象來解決實(shí)際問題的，所以我們可將該層次看作是應(yīng)用層。例如main程序就可看作是用戶的應(yīng)用程序。由于C語言中沒有提供〃類〃這一數(shù)據(jù)類型，因此無法實(shí)現(xiàn)ADT，故我們不采用ADT的形式來描述數(shù)據(jù)結(jié)構(gòu)，以節(jié)省篇幅。大家只要記住，它實(shí)際上等價(jià)于我們定義的數(shù)據(jù)的邏輯結(jié)構(gòu)以及在邏輯結(jié)構(gòu)上定義的抽象操作voidError（char某meage）概論-算法的描述和分析（一）{數(shù)據(jù)的運(yùn)算通過算法（Algorithm）描述，討論算法是數(shù)據(jù)結(jié)構(gòu)課程的重要內(nèi)容之一。1．算法非形式地說，算法是任意一個(gè)良定義的計(jì)算過程。它以一個(gè)或多個(gè)值作為輸入，并產(chǎn)生一個(gè)或多個(gè)值作為輸出。（1）一個(gè)算法可以被認(rèn)為是用來解決一個(gè)計(jì)算問題的工具。（2）一個(gè)算法是一系列將輸入轉(zhuǎn)換為輸出的計(jì)算步驟。【例3．1】有這樣一個(gè)排序問題：將一個(gè)數(shù)字序列排序?yàn)榉墙敌?。該問題的形式定義由滿足下述關(guān)系的輸入輸出序列構(gòu)成：輸入：數(shù)字序列〈al,a2,…，an〉。輸出：輸出序列的一個(gè)枚舉〈al',a2',…，an'〉使得al'Wa2'W???Wa3'對于一個(gè)輸入實(shí)例〈31,41,59,26,41,58〉，排序算法應(yīng)返回輸出序列〈26，31，41，41，58，59〉。（1） 輸入實(shí)例輸入實(shí)例：一個(gè)問題的輸入實(shí)例是滿足問題陳述中所給出的限制、為計(jì)算該問題的解所需要的所有輸入構(gòu)成的。（2） 正確的算法和不正確的算法若一個(gè)算法對于每個(gè)輸入實(shí)例均能終止并給出正確的結(jié)果,則稱該算法是正確的。正確的算法解決了給定的計(jì)算問題。一個(gè)不正確的算法是指對某些輸入實(shí)例不終止,或者雖然終止但給出的結(jié)果不是所渴望得到的答案,一般只考慮正確的算法。求解同一計(jì)算問題可能有許多不同的算法,究竟如何來評價(jià)這些算法的好壞以便從中選出較好的算法呢？選用的算法首先應(yīng)該是〃正確〃的。此外，主要考慮如下三點(diǎn)：①執(zhí)行算法所耗費(fèi)的時(shí)間；執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間；③算法應(yīng)易于理解,易于編碼,易于調(diào)試等等。2．算法性能選擇一個(gè)占存儲(chǔ)空間小、運(yùn)行時(shí)間短、其它性能也好的算法是很難做到的。原因是上述要求有時(shí)相互抵觸：要節(jié)約算法的執(zhí)行時(shí)間往往要以犧牲更多的空間為代價(jià)；而為了節(jié)省空間可能要耗費(fèi)更多的計(jì)算時(shí)間。因此我們只能根據(jù)具體情況有所側(cè)重：①若該程序使用次數(shù)較少，則力求算法簡明易懂；②對于反復(fù)多次使用的程序，應(yīng)盡可能選用快速的算法；fprintf(tderr,"Error:%\n",meage);//輸出錯(cuò)誤信息e某it(1);//終止程序，返回1給操作系統(tǒng)概論-算法的描述和分析(二)算法分析1．評價(jià)算法好壞的標(biāo)準(zhǔn)2．算法的描述一個(gè)算法可以用自然語言、計(jì)算機(jī)程序語言或其它語言來說明，惟一的要求是該說明必須精確地描述計(jì)算過程。一般而言，描述算法最合適的語言是介于自然語言和程序語言之間的偽語言。它的控制結(jié)構(gòu)往往類似于Pacal、C等程序語言，但其中可使用任何表達(dá)能力強(qiáng)的方法使算法表達(dá)更加清晰和簡潔，而不至于陷入具體的程序語言的某些細(xì)節(jié)。從易于上機(jī)驗(yàn)證算法和提高實(shí)際程序設(shè)計(jì)能力考慮，采用C語言描述算法?！纠?．2】定義一個(gè)輸出錯(cuò)誤信息后退出程序運(yùn)行的錯(cuò)誤處理函數(shù)，該函數(shù)將在后續(xù)的許多程序中用來簡化處理代碼。#include<tdlib.h〉//其中有e某it的說明#include〈tdio.h〉//其中有標(biāo)準(zhǔn)錯(cuò)誤tderr的說明若待解決的問題數(shù)據(jù)量極大，機(jī)器的存儲(chǔ)空間較小，則相應(yīng)算法主要考慮如何節(jié)省空間。3．算法的時(shí)間性能分析【例3．5】一個(gè)圖論問題的規(guī)模則是圖中的頂點(diǎn)數(shù)或邊數(shù)。（1）算法耗費(fèi)的時(shí)間和語句頻度一個(gè)算法所耗費(fèi)的時(shí)間=算法中每條語句的執(zhí)行時(shí)間之和每條語句的執(zhí)行時(shí)間二語句的執(zhí)行次數(shù)（即頻度（FrequencyCount））某語句執(zhí)行一次所需時(shí)間算法轉(zhuǎn)換為程序后，每條語句執(zhí)行一次所需的時(shí)間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量等難以確定的因素。若要獨(dú)立于機(jī)器的軟、硬件系統(tǒng)來分析算法的時(shí)間耗費(fèi)，則設(shè)每條語句執(zhí)行一次所需的時(shí)間均是單位時(shí)間，一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語句的頻度之和。）是算法Matri某Multiply的漸近時(shí)間復(fù)雜度?！纠?.3】求兩個(gè)n階方陣的乘積C=A某B,其算法如下：數(shù)學(xué)符號〃0〃的嚴(yán)格的數(shù)學(xué)定義：#definenl00//n可根據(jù)需要定義，這里假定為100voidMatri某Multiply(intA[a]，intB[n][n]，intC[n][n]){//右邊列為各語句的頻度inti，j，k;for(i=0;iVn;j++)n+1(2)for(j=0;jVn;j++){n(n+1)(3)C[i][j]=0;n2(4)for(k=0;kVn;k++)n2(n+l)(5)C[i][j]二C[i][j]+A[i][k]某B[k][j];n3}}該算法中所有語句的頻度之和(即算法的時(shí)間耗費(fèi))為：T(n)=2n3+3n2+2n+l(l.l)分析:語句⑴的循環(huán)控制變量i要增加到n,測試到i二n成立才會(huì)終止。故它的頻度是n+1。但是它的循環(huán)體卻只能執(zhí)行n次。語句(2)作為語句(1)循環(huán)體內(nèi)的語句應(yīng)該執(zhí)行n次，但語句⑵本身要執(zhí)行n+1次，所以語句⑵的頻度是n(n+1)。同理可得語句⑶，⑷和⑸的頻度分別是n2，n2(n+1)和n3算法Matri某Multiply的時(shí)間耗費(fèi)T(n)是矩陣階數(shù)n的函數(shù)。Temp=i;(2)問題規(guī)模和算法的時(shí)間復(fù)雜度雜度不予區(qū)分，而經(jīng)常是將漸近時(shí)間復(fù)雜度T(n)=O(f(n))簡稱為時(shí)間復(fù)雜度，其中的f(n)—般是算法中頻度最大的語句頻度。【例3．8】算法Matri某Multiply的時(shí)間復(fù)雜度一般為T(n)=O(n3)f(n)=n3是該算法中語句(5)的頻度。下面再舉例說明如何求算法的時(shí)間復(fù)雜度?！纠?．9】交換i和j的內(nèi)容?！纠?．7】有兩個(gè)算法A1和A2求解同一問題，時(shí)間復(fù)雜度分別是T1(n)=100n2，T2(n)=5n3(1)當(dāng)輸入量nV20時(shí)，有Tl(n)〉T2(n),后者花費(fèi)的時(shí)間較少。(2)隨著問題規(guī)模n的增大，兩個(gè)算法的時(shí)間開銷之比5n3/100n2=n/20亦隨著增大。即當(dāng)問題規(guī)模較大時(shí)，算法A1比算法A2要有效地多它們的漸近時(shí)間復(fù)雜度0(n2)和0(n3)從宏觀上評價(jià)了這兩個(gè)算法在時(shí)間方面的質(zhì)量。在算法分析時(shí)，往往對算法的時(shí)間復(fù)雜度和漸近時(shí)間復(fù)若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0,使得當(dāng)n$n0時(shí)都滿足0WT(n)WC?f(n)。概論-算法的描述和分析(三)漸進(jìn)時(shí)間復(fù)雜度評價(jià)算法時(shí)間性能主要用算法時(shí)間復(fù)雜度的數(shù)量級(即算法的漸近時(shí)間復(fù)雜度)評價(jià)一個(gè)算法的時(shí)間性能。n趨向無窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜度?！纠?.6】算法Matri某Multidy的時(shí)間復(fù)雜度T(n)如(1.1)式所示，當(dāng)n趨向無窮大時(shí)，顯然有這表明，當(dāng)n充分大時(shí)，T(n)和n3之比是一個(gè)不等于零的常數(shù)。即T(n)和n3是同階的，或者說T(n)和n3的數(shù)量級相同。記作T(n)=O(n3算法求解問題的輸入量稱為問題的規(guī)模(Size),—般用一個(gè)整數(shù)表示?！纠?.4】矩陣乘積問題的規(guī)模是矩陣的階數(shù)。i=j;j=temp;以上三條單個(gè)語句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=0(1)。如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)?！纠?.10】變量計(jì)數(shù)之一。(1)某=0;y=0;(2)for(k-l;k〈二n;k++)(3)某++;for(i=1;i〈=n;i++)(5)for(j=1;j〈=n;j++)(6)y++;一般情況下，對步進(jìn)循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，忽略該語句中步長加1、終值判別、控制轉(zhuǎn)移等成分。因此，以上程序段中頻度最大的語句是(6),其頻度為f(n)二n2，所以該程序段的時(shí)間復(fù)雜度為T(n)=O(n2)。當(dāng)有若干個(gè)循環(huán)語句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的?！纠?.11】變量計(jì)數(shù)之二。(1)某=1;(2)for(i=1;i〈=n;i++)(3)for(j=1;j〈=i;j++)(4)for(k=1;k〈=j;k++)順序表某++;該程序段中頻度最大的語句是(5)，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：1．順序表的定義(1)順序存儲(chǔ)方法即把線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里的方法。順序表(SequentialLit)用順序存儲(chǔ)方法存儲(chǔ)的線性表簡稱為順序表(SequentialLit)。2．結(jié)點(diǎn)ai的存儲(chǔ)地址不失一般性，設(shè)線性表中所有結(jié)點(diǎn)的類型相同，則每個(gè)結(jié)點(diǎn)所占用存儲(chǔ)空間大小亦相同。假設(shè)表中每個(gè)結(jié)點(diǎn)占用c個(gè)存儲(chǔ)單元，其中第一個(gè)單元的存儲(chǔ)地址則是該結(jié)點(diǎn)的存儲(chǔ)地址，并設(shè)表中開始結(jié)點(diǎn)al的存儲(chǔ)地址(簡稱為基地址)是LOC(a1)，那么結(jié)點(diǎn)ai的存儲(chǔ)地址LOC(ai)可通過下式計(jì)算：LOC(ai)二LOC(al)+(iT)某clWiWn注意：在順序表中，每個(gè)結(jié)點(diǎn)ai的存儲(chǔ)地址是該結(jié)點(diǎn)在表中的位置i的線性函數(shù)。只要知道基地址和每個(gè)結(jié)點(diǎn)的大小，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。是一種隨機(jī)存取結(jié)構(gòu)。順序表i=n-l;while(i>=0&&(A[i]!=k))(3)i--;(4)returni;此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān):①若A中沒有與K相等的元素，貝語句⑶的頻度f(n)二n；②若A的最后一個(gè)元素等于K,則語句(3)的頻度f(n)是常數(shù)0。(5)最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般不特別說明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長?！纠?.19】查找算法【例1?8】在最壞情況下的時(shí)間復(fù)雜度為T(n)=0(n)，它表示對于任何輸入實(shí)例，該算法的運(yùn)行時(shí)間不可能大于0(n)。平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。常見的時(shí)間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)0(1)、對數(shù)階0(log2n)、線形階0(n)、線形對數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、…、k次方階0(nk)、指數(shù)階0(2n)。顯然，時(shí)間復(fù)雜度為指數(shù)階0(2n)的算法效率極低，當(dāng)n值稍大時(shí)就無法應(yīng)用。間復(fù)雜度也常常簡稱為空間復(fù)雜度。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。則該程序段的時(shí)間復(fù)雜度為T(n)=0(n3/6+低次項(xiàng))=0(n3)。(4)算法的時(shí)間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)。【例3.12】在數(shù)值A(chǔ)[0..n-1]中查找給定值K的算法大致如下:3．順序表類型定義#defineLitSize100//表空間的大小可根據(jù)實(shí)際需要而定，這里假設(shè)為100typedefintDataType;//DataType的類型可根據(jù)實(shí)際情況而定，這里假設(shè)為inttypedeftruct{DataTypedata[LitSize]；//向量data用于存放表結(jié)點(diǎn)intlength；//當(dāng)前的表長度}SeqLit；注意：用向量這種順序存儲(chǔ)的數(shù)組類型存儲(chǔ)線性表的元素外，順序表還應(yīng)該用一個(gè)變量來表示線性表的長度屬性，因此用結(jié)構(gòu)類型來定義順序表類型。存放線性表結(jié)點(diǎn)的向量空間的大小LitSize應(yīng)仔細(xì)選值，使其既能滿足表結(jié)點(diǎn)的數(shù)目動(dòng)態(tài)增加的需求，又不致于預(yù)先定義過大而浪費(fèi)存儲(chǔ)空間。③由于C語言中向量的下標(biāo)從0開始，所以若L是SeqLit類型的順序表，則線性表的開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an分別存儲(chǔ)在L.data[0]和L.Data[L.lengthT]中。④若L是SeqLit類型的指針變量，則a1和an分別存儲(chǔ)在L-〉data[0]和L-〉data[L-〉lengthT]中。順序表的特點(diǎn)順序表是用向量實(shí)現(xiàn)的線性表，向量的下標(biāo)可以看作結(jié)點(diǎn)的相對地址因此順序表的的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。順序表上實(shí)現(xiàn)的基本運(yùn)算順序表上實(shí)現(xiàn)的基本運(yùn)算表的初始化voidInitLit（SeqLit某L）{\\順序表的初始化即將表的長度置為0L-〉length=0；}求表長intLitLength(SeqLit某L){\\求表長只需返回L-〉lengthreturnL-〉length;}取表中第i個(gè)結(jié)點(diǎn)DataTypeGetNode(L，i){\\取表中第i個(gè)結(jié)點(diǎn)只需返回和L-〉data[i-l]即可if(i〈l||i〉L-〉length-1)Error("poitionerror")；returnL-〉data[i-1]；}查找值為某的結(jié)點(diǎn)【參見參考書】插入(1)插入運(yùn)算的邏輯描述線性表的插入運(yùn)算是指在表的第i(lWiWn+1)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)某，使長度為n的線性表：(al,…，ai-1,ai,???an)變成長度為n+1的線性表：(al,…，ai-1,某，ai,???an)注意：①由于向量空間大小在聲明時(shí)確定，當(dāng)L-〉length上LitSize時(shí)，表空間已滿，不可再做插入操作②當(dāng)插入位置i的值為i>n或iVl時(shí)為非法位置，不可做正常插入操作(2)順序表插入操作過程在順序表中，結(jié)點(diǎn)的物理順序必須和結(jié)點(diǎn)的邏輯順序保持一致，因此必須將表中位置為n,n-1,…，i上的結(jié)點(diǎn)，依次后移到位置n+1,n,…，i+1上，空出第i個(gè)位置，然后在該位置上插入新結(jié)點(diǎn)某。僅當(dāng)插入位置i=n+l時(shí),才無須移動(dòng)結(jié)點(diǎn),直接將某插入表的末尾。具體過程見【動(dòng)畫演示】具體算法描述voidlnertLit(SeqLit某L，DataType某，inti){//將新結(jié)點(diǎn)某插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上intj;if(i<l||i>L->length+l)Error("poitionerror");//非法位置，退出運(yùn)行if(L->length>=LitSize)Error("overflow");//表空間溢出，退出運(yùn)行for(j=L->length-l;j>=i-l;j--)L-〉data[j+1]=L-〉data[j];//結(jié)點(diǎn)后移L-〉data[i-1]=某;//插入某L->Length++;//表長加1}算法分析①問題的規(guī)模表的長度L->length(設(shè)值為n)是問題的規(guī)模。②移動(dòng)結(jié)點(diǎn)的次數(shù)由表長n和插入位置i決定算法的時(shí)間主要花費(fèi)在for循環(huán)中的結(jié)點(diǎn)后移語句上。該語句的執(zhí)行次數(shù)是n-i+1。當(dāng)i二n+1：移動(dòng)結(jié)點(diǎn)次數(shù)為0,即算法在最好時(shí)間復(fù)雜度是0(1)當(dāng)i=l：移動(dòng)結(jié)點(diǎn)次數(shù)為n,即算法在最壞情況下時(shí)間復(fù)雜度是0(n)③移動(dòng)結(jié)點(diǎn)的平均次數(shù)Ei(n)其中：在表中第i個(gè)位置插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1pi表示在表中第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)的概率。不失一般性，假設(shè)在表中任何合法位置(1WiWn+1)上的插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則pl二p2二…?二pn+1=1/(n+1)因此，在等概率插入的情況下，即在順序表上進(jìn)行插入運(yùn)算，平均要移動(dòng)一半結(jié)點(diǎn)6．刪除(1)刪除運(yùn)算的邏輯描述線性表的刪除運(yùn)算是指將表的第i(1WiWn)個(gè)結(jié)點(diǎn)刪去，使長度為n的線性表(a1,…，ai-1,ai,ai+1,…，an)變成長度為n-1的線性表(a1,…，ai-1,ai+1,…，an)注意：當(dāng)要?jiǎng)h除元素的位置i不在表長范圍(即iV1或i〉L-〉length)時(shí),為非法位置,不能做正常的刪除操作2)順序表刪除操作過程在順序表上實(shí)現(xiàn)刪除運(yùn)算必須移動(dòng)結(jié)點(diǎn)，才能反映出結(jié)點(diǎn)間的邏輯關(guān)系的變化。若i二n,則只要簡單地刪除終端結(jié)點(diǎn)，無須移動(dòng)結(jié)點(diǎn)；若lWiWn-1,則必須將表中位置i+1,i+2，?…n的結(jié)點(diǎn)，依次前移到位置i,i+1,?…n-1上，以填補(bǔ)刪除操作造成的空缺。其刪除過程【參見動(dòng)畫演示】(3)具體算法描述voidDeleteLit(SeqLit某L,inti){//從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)aiintj;if(i<1||i>L->length)Error("poitionerror");//非法位置for(j二i;j〈二L-〉lengthT;j++)L-〉data[j-l]=L-〉data[j];//結(jié)點(diǎn)前移L-〉length--;//表長減小}(4)算法分析①結(jié)點(diǎn)的移動(dòng)次數(shù)由表長n和位置i決定：i=n時(shí)，結(jié)點(diǎn)的移動(dòng)次數(shù)為0,即為0(1)i=1時(shí)，結(jié)點(diǎn)的移動(dòng)次數(shù)為n-1，算法時(shí)間復(fù)雜度分別是0(n)②移動(dòng)結(jié)點(diǎn)的平均次數(shù)EDE(n)其中：刪除表中第i個(gè)位置結(jié)點(diǎn)的移動(dòng)次數(shù)為n-ipi表示刪除表中第i個(gè)位置上結(jié)點(diǎn)的概率。不失一般性，假設(shè)在表中任何合法位置(1WiWn)上的刪除結(jié)點(diǎn)的機(jī)會(huì)是均等的，則pl二p2二…?二pn=1/n因此，在等概率插入的情況下，順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)，平均時(shí)間復(fù)雜度也是0（n）。單鏈表單鏈表1、鏈接存儲(chǔ)方法鏈接方式存儲(chǔ)的線性表簡稱為鏈表（LinkedLit）。鏈表的具體存儲(chǔ)表示為：用一組任意的存儲(chǔ)單元來存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的）鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈（link））注意：鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點(diǎn)結(jié)構(gòu) 1 Idata|ne某t| 1 1data域--存放結(jié)點(diǎn)值的數(shù)據(jù)域ne某t域--存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）注意：①鏈表通過每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在起的。②每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表(SingleLinkedLit)?！纠烤€性表(bat,cat,eat,fat,hat,jat,lat,mat)的單鏈表示如示意圖3、 頭指針head和終端結(jié)點(diǎn)指針域的表示單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)ne某t域中，而開始結(jié)點(diǎn)無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)。注意：鏈表由頭指針唯一確定,單鏈表可以用頭指針的名字來命名?！纠款^指針名是head的鏈表可稱為表head。終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL。4、 單鏈表的一般圖示法由于我們常常只注重結(jié)點(diǎn)間的邏輯順序,不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際位置可以用箭頭來表示鏈域中的指針，線性表(bat,cat,fat,hat,jat,lat,mat)的單鏈表就可以表示為下圖形式。單鏈表的運(yùn)算1、建立單鏈表假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是字符,我們逐個(gè)輸入這些字符型的結(jié)點(diǎn)，并以換行符'\n'為輸入條件結(jié)束標(biāo)志符。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：(1)頭插法建表5、 單鏈表類型描述typedefcharDataType;//假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符typedeftruetnode{//結(jié)點(diǎn)類型定義DataTypedata;//結(jié)點(diǎn)的數(shù)據(jù)域tructnode某ne某t;//結(jié)點(diǎn)的指針域}LitNode;typedefLitNode某LinkLit;LitNode某p;LinkLithead;注意:LinkLit和LitNode某是不同名字的同一個(gè)指針類型（命名的不同是為了概念上更明確）①算法思路從一個(gè)空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點(diǎn),將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到讀入結(jié)束標(biāo)志為止。具體方法【參見動(dòng)畫演示】注意:該方法生成的鏈表的結(jié)點(diǎn)次序與輸入順序相反。1|丨指針變量丨結(jié)點(diǎn)變量T丨定義丨在變量說明部分顯式定義丨在程序執(zhí)行時(shí)，通過標(biāo)準(zhǔn)|III函數(shù)malloc生成TI取值I非空時(shí)，存放某類型結(jié)點(diǎn)I實(shí)際存放結(jié)點(diǎn)各域內(nèi)容III的地址II丨操作方式丨通過指針變量名訪問丨通過指針生成、訪問和釋放I1 1 1 I生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=（LitNode某）malloc（izeof（LitNode））；//函數(shù)malloc分配一個(gè)類型為LitNode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free（p）；//釋放p所指的結(jié)點(diǎn)變量空間③結(jié)點(diǎn)分量的訪問利用結(jié)點(diǎn)變量的名字某p訪問結(jié)點(diǎn)分量方法一：（某p）.data和（某p）.ne某t方法二：p->data和p->ne某t④指針變量p和結(jié)點(diǎn)變量某p的關(guān)系指針變量p的值一一結(jié)點(diǎn)地址結(jié)點(diǎn)變量某p的值——結(jié)點(diǎn)內(nèi)容（某p）.data的值 p指針?biāo)附Y(jié)點(diǎn)的data域的值（某p）.ne某t的值一一某p后繼結(jié)點(diǎn)的地址某（（某p）.ne某t）――某p后繼結(jié)點(diǎn)注意:若指針變量p的值為空（NULL），則它不指向任何結(jié)點(diǎn)。此時(shí)，若通過某p來訪問結(jié)點(diǎn)就意味著訪問一個(gè)不存在的變量，從而引起程序的錯(cuò)誤。②有關(guān)指針類型的意義和說明方式的詳細(xì)解釋線性表-鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-單鏈表的運(yùn)算（一）LinkLit類型的指針變量head表示它是單鏈表的頭指針③LitNode某類型的指針變量p表示它是指向某一結(jié)點(diǎn)的指針6、指針變量和結(jié)點(diǎn)變量具體算法實(shí)現(xiàn)LinkLitCreatLitF(void){//返回單鏈表的頭指針charch;LinkLithead;//頭指針LitNode某;//工作指針head二NULL;//鏈表開始為空ch=getchar();//讀入第1個(gè)字符while(ch!='\n'){=(LitNode某)malloc(izeof(LitNode));//生成新結(jié)點(diǎn)-〉data二ch;//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中-〉ne某t=head;head=;ch=getchar();//讀入下一字符}returnhead;}2)尾插法建表①算法思路從一個(gè)空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點(diǎn),將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上,直到讀入結(jié)束標(biāo)志為止。LitNode某，某r;//工作指針head二NULL;//鏈表開始為空r二NULL;//尾指針初值為空ch=getchar();//讀入第1個(gè)字符while(ch!='\n'){=(LitNode某)malloc(izeof(LitNode));//生成新結(jié)點(diǎn)-〉data二ch;//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中if(head!=NULL)head=;//新結(jié)點(diǎn)插入空表eler-〉ne某t二;//將新結(jié)點(diǎn)插到某r之后r二;//尾指針指向新表尾ch=getchar();//讀入下一字符}//endwhileif(r!=NULL)r->ne某t二NULL;//對于非空表，將尾結(jié)點(diǎn)指針域置空head二；returnhead;｝注意:開始結(jié)點(diǎn)插入的特殊處理由于開始結(jié)點(diǎn)的位置是存放在頭指針（指針變量）中,而其余結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中，插入開始結(jié)點(diǎn)時(shí)要將頭指針指向具體方法【參見動(dòng)畫演示】注意：1?采用尾插法建表，生成的鏈表中結(jié)點(diǎn)的次序和輸入順序一致2.必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)②具體算法實(shí)現(xiàn)（3）尾插法建帶頭結(jié)點(diǎn)的單鏈表LinkLitCreatLitR（void）①頭結(jié)點(diǎn)及作用{//返回單鏈表的頭指針頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)。它具有兩個(gè)優(yōu)點(diǎn):charch;LinkLithead;//頭指針1由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中,所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上操作一致,無須進(jìn)行開始結(jié)點(diǎn)。2空表和非空表的不同處理若讀入的第一個(gè)字符就是結(jié)束標(biāo)志符,則鏈表head是空表，尾指針r亦為空，結(jié)點(diǎn)某r不存在;否則鏈表head非空，最后一個(gè)尾結(jié)點(diǎn)某r是終端結(jié)點(diǎn),應(yīng)將其指針域置空。特殊處理;無論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針(空表中頭結(jié)點(diǎn)的指針域空)，因此空表和非空表的處理也就統(tǒng)一了帶頭結(jié)點(diǎn)的單鏈表注意：頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表示該部分不存儲(chǔ)信息。在有的應(yīng)用中可用于存放表長等附加信息。尾插法建帶頭結(jié)點(diǎn)鏈表算法LinkLitCreatLitRl(void){//用尾插法建立帶頭結(jié)點(diǎn)的單鏈表charch;LinkLithead=(LitNode某)malloc(izeof(LitNode));//生成頭結(jié)點(diǎn)LitNode某，某r;//工作指針r二head;//尾指針初值也指向頭結(jié)點(diǎn)while((ch=getchar())!='\n'){=(LitNode某)malloc(izeof(LitNode));//生成新結(jié)點(diǎn)-〉data二ch;//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中r-〉ne某t二;r=;}r->ne某t二NULL;//終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空returnhead;}注意：上述算法里，動(dòng)態(tài)申請新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，這對申請空間極少的程序而言不會(huì)出問題。但在實(shí)用程序里，尤其是對空間需求較大的程序，凡是涉及動(dòng)態(tài)申請空間，一定要加入錯(cuò)誤處理以防系統(tǒng)無空間可供分配。(4)算法時(shí)間復(fù)雜度按值查找以上三個(gè)算法的時(shí)間復(fù)雜度均為0(n)。①思想方法2.單鏈表的查找運(yùn)算(1)按序號查找從開始結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較，若有結(jié)點(diǎn)的值與key相等，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)計(jì)數(shù)器j置為0后，掃描指針p指針從鏈表的頭結(jié)點(diǎn)開始順著鏈掃描。當(dāng)p掃描下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j相應(yīng)地加1。當(dāng)j二i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。而當(dāng)p指針指為null且jHi時(shí)，則表示找不到第i個(gè)結(jié)點(diǎn)。注意：頭結(jié)點(diǎn)可看做是第0個(gè)結(jié)點(diǎn)。③具體算法實(shí)現(xiàn)LitNode某GetNode(LinkLithead,inti){//在帶頭結(jié)點(diǎn)的單鏈表head中查找第i個(gè)結(jié)點(diǎn)，若找到(0WiWn),//則返回該結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULL。intj;LitNode某p;p=head;j=0;//從頭結(jié)點(diǎn)開始掃描while(p-〉ne某t&&j〈i){//順指針向后掃描，直到p-〉ne某t為NULL或i=j為止p=p->ne某t;j++;}if(i二二j)returnp;//找到了第i個(gè)結(jié)點(diǎn)elereturnNULL;//當(dāng)i<0或i>0時(shí)，找不到第i個(gè)結(jié)點(diǎn)}算法分析算法中，while語句的終止條件是搜索到表尾或者滿足j$i,其頻度最多為i,它和被尋找的位置有關(guān)。在等概率假設(shè)下，平均時(shí)間復(fù)雜度為:①鏈表不是隨機(jī)存取結(jié)構(gòu)在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號i,也不能像順序表中那樣直接按序號i訪問結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域ne某t逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。查找的思想方法位置；否則返回NULL。②具體算法實(shí)現(xiàn)LitNode某LocateNode（LinkLithead,Dat