二級(jí)-數(shù)據(jù)結(jié)構(gòu)與算法.doc

計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法 1 算法 算法：是指解題方案的準(zhǔn)確而完整的描述。算法不等于程序，也不等計(jì)算機(jī)方法，程序的編制不可能優(yōu)于算法的設(shè)計(jì)。算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，每一個(gè)規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括：（1）可行性；（2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；（3）有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟后終止，包括合理的執(zhí)行時(shí)間的含義；（4）擁有足夠的情報(bào)。算法的基本要素：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。指令系統(tǒng)：一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合?；具\(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。線性結(jié)構(gòu)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。3 線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。在復(fù)雜線性表中，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個(gè)記錄構(gòu)成的線性表又稱為文件。非空線性表的結(jié)構(gòu)特征：（1）且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。ai的存儲(chǔ)地址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第一個(gè)元素的地址，k代表每個(gè)元素占的字節(jié)數(shù)。順序表的運(yùn)算：插入、刪除。 （詳見(jiàn)14-16頁(yè)）4 棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進(jìn)后出”（filo）或“后進(jìn)先出”（lifo）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。棧的基本運(yùn)算：（1）插入元素稱為入棧運(yùn)算；（2）刪除元素稱為退棧運(yùn)算；（3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。rear指針指向隊(duì)尾，front指針指向隊(duì)頭。隊(duì)列是“先進(jìn)行出”（fifo）或“后進(jìn)后出”（lilo）的線性表。隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；（2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。循環(huán)隊(duì)列：s=0表示隊(duì)列空，s=1且front=rear表示隊(duì)列滿5 線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。結(jié)點(diǎn)由兩部分組成：（1）用于存儲(chǔ)數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性鏈表，head稱為頭指針，head=null（或0）稱為空表，如果是兩指針：左指針（llink）指向前件結(jié)點(diǎn)，右指針（rlink）指向后件結(jié)點(diǎn)。線性鏈表的基本運(yùn)算：查找、插入、刪除。6 樹(shù)與二叉樹(shù)樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱樹(shù)的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度。樹(shù)的最大層次稱為樹(shù)的深度。二叉樹(shù)的特點(diǎn)：（1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。二叉樹(shù)的基本性質(zhì)：（1）在二叉樹(shù)的第k層上，最多有2k-1(k1)個(gè)結(jié)點(diǎn)；（2）深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)；（3）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)；（4）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2n+1,其中l(wèi)og2n表示取log2n的整數(shù)部分；（5）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1；（6）設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1，2，.n給結(jié)點(diǎn)進(jìn)行編號(hào)（k=1,2.n），有以下結(jié)論：若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為int(k/2)；若2kn，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（也無(wú)右子結(jié)點(diǎn)）；若2k+1n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。滿二叉樹(shù)是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k-1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹(shù)是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。二叉樹(shù)存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹(shù)與完全二叉樹(shù)可以按層序進(jìn)行順序存儲(chǔ)。二叉樹(shù)的遍歷：（1）前序遍歷（dlr），首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；（2）中序遍歷（ldr），首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；（3）后序遍歷（lrd）首先遍歷左子樹(shù)，然后訪問(wèn)遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。7 查找技術(shù)順序查找的使用情況：（1）線性表為無(wú)序表；（2）表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表，對(duì)于長(zhǎng)度為n的有序線性表，最壞情況只需比較log2n次。8 排序技術(shù)排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。交換類排序法：（1）冒泡排序法，需要比較的次數(shù)為n(n-1)/2； （2）快速排序法。插入類排序法：（1）簡(jiǎn)單插入排序法，最壞情況需要n(n-1)/2次比較；（2）希爾排序法，最壞情況需要o(n1.5)次比較。選擇類排序法：（1）簡(jiǎn)單選擇排序法, 最壞情況需要n(n-1)/2次比較；（2）堆排序法，最壞情況需要o(nlog2n)次比較。等級(jí)考試公共基礎(chǔ)考點(diǎn)分析之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(1)1.1 算法 考點(diǎn)1 算法的基本概念 計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。 算法(algorithm)是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，同時(shí)是明確的；此順序?qū)⒃谟邢薜拇螖?shù)后終止。算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 1算法的基本特征 (1)可行性(effectiveness)：針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。 (2)確定性(definiteness)：算法中的每一個(gè)步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性。 (3)有窮性(finiteness)：算法必需在有限時(shí)間內(nèi)做完，即算法必需能在執(zhí)行有限個(gè)步驟之后終止。 (4)擁有足夠的情報(bào)：要使算法有效必需為算法提供足夠的情報(bào)當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才最有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無(wú)效。 2算法的基本要素 (1)算法中對(duì)數(shù)據(jù)的運(yùn)算和操作：每個(gè)算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指令序列。 計(jì)算機(jī)可以執(zhí)行的基本操作是以指令的形式描述的。一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合，稱為該計(jì)算機(jī)系統(tǒng)的指令系統(tǒng)。計(jì)算機(jī)程序就是按解題要求從計(jì)算機(jī)指令系統(tǒng)中選擇合適的指令所組成的指令序列在一般的計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下4類： 算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算； 邏輯運(yùn)算：主要包括“與”、“或”、“非”等運(yùn)算； 關(guān)系運(yùn)算：主要包括“大于”、“小于”、“等于”、“不等于”等運(yùn)算； 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。 (2)算法的控制結(jié)構(gòu)：一個(gè)算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。 算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等。一個(gè)算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。 (3)算法設(shè)計(jì)的基本方法 計(jì)算機(jī)算法不同于人工處理的方法，下面是工程上常用的幾種算法設(shè)計(jì)，在實(shí)際應(yīng)用時(shí)，各種方法之間往往存在著一定的聯(lián)系。 (1)列舉法 列舉法是計(jì)算機(jī)算法中的一個(gè)基礎(chǔ)算法。列舉法的基本思想是，根據(jù)提出的問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的?列舉法的特點(diǎn)是算法比較簡(jiǎn)單。但當(dāng)列舉的可能情況較多時(shí)，執(zhí)行列舉算法的工作量將會(huì)很大。因此，在用列舉法設(shè)計(jì)算法時(shí)，使方案優(yōu)化，盡量減少運(yùn)算工作量，是應(yīng)該重點(diǎn)注意的。 (2)歸納法 歸納法的基本思想是，通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。從本質(zhì)上講，歸納就是通過(guò)觀察一些簡(jiǎn)單而特殊的情況，最后總結(jié)出一般性的結(jié)論。 (3)遞推 遞推是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)而確定。遞推本質(zhì)上也屬于歸納法，工程上許多遞推關(guān)系式實(shí)際上是通過(guò)對(duì)實(shí)際問(wèn)題的分析與歸納而得到的，因此，遞推關(guān)系式往往是歸納的結(jié)果。對(duì)于數(shù)值型的遞推算法必須要注意數(shù)值計(jì)算的穩(wěn)定性問(wèn)題。 (4)遞歸 人們?cè)诮鉀Q一些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程度(如問(wèn)題的規(guī)模等)，一般總是將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。這種將問(wèn)題逐層分解的過(guò)程，實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解決了最后那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的基本思想。 遞歸分為直接遞歸與間接遞歸兩種。 (5)減半遞推技術(shù) 實(shí)際問(wèn)題的復(fù)雜程度往往與問(wèn)題的規(guī)模有著密切的聯(lián)系。因此，利用分治法解決這類實(shí)際問(wèn)題是有效的。工程上常用的分治法是減半遞推技術(shù)。 所謂“減半”，是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變；所謂“遞推”，是指重復(fù)“減半”的過(guò)程。 (6)回溯法 在工程上，有些實(shí)際問(wèn)題很難歸納出一組簡(jiǎn)單的遞推公式或直觀的求解步驟，并且也不能進(jìn)行無(wú)限的列舉。對(duì)于這類問(wèn)題，一種有效的方法是“試”。通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，若試探成功，就得到問(wèn)題的解，若試探失敗，就逐步回退，換別的路線再逐步試探。 4算法設(shè)計(jì)的要求 通常一個(gè)好的算法應(yīng)達(dá)到如下目標(biāo)：(l)正確性(correctness) 正確性大體可以分為以下4個(gè)層次： 程序不含語(yǔ)法錯(cuò)誤； 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果； 程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果； 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說(shuō)明要求的結(jié)果。 (2)可讀性(readability) 算法主要是為了方便入的閱讀與交流，其次才是其執(zhí)行?？勺x性好有助于用戶對(duì)算法的理解；晦澀難懂的程序易于隱藏較多錯(cuò)誤，難以調(diào)試和修改。 (3)健壯性(robustness) 當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。 (4)效率與低存儲(chǔ)量需求 效率指的是程序執(zhí)行時(shí)，對(duì)于同一個(gè)問(wèn)題如果有多個(gè)算法可以解決，執(zhí)行時(shí)間短的算法效率高；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。考點(diǎn)2 算法的復(fù)雜度 1算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。同一個(gè)算法用不同的語(yǔ)言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行，效率均不同。這表明使用絕對(duì)的時(shí)間單位衡量算法的效率是不合適的。撇開(kāi)這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模(通常用整數(shù)n表示)，它是問(wèn)題的規(guī)模函數(shù)。即 算法的工作量=f(n) 例如，在NN矩陣相乘的算法中，整個(gè)算法的執(zhí)行時(shí)間與該基本操作(乘法)重復(fù)執(zhí)行的次數(shù)n3成正比，也就是時(shí)間復(fù)雜度為n3，即 f(n)=O(n3) 在有的情況下，算法中的基本操作重復(fù)執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。例如在起泡排序的算法中，當(dāng)要排序的數(shù)組a初始序列為自小至大有序時(shí)，基本操作的執(zhí)行次數(shù)為氏當(dāng)初始序列為自大至小有序時(shí)，基本操作的執(zhí)行次數(shù)為n(n-1)/2。對(duì)這類算法的分析，可以采用以下兩種方法來(lái)分析。 (1)平均性態(tài)(Average Behavior) 所謂平均性態(tài)是指各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。 設(shè)x是所有可能輸入中的某個(gè)特定輸入，p(x)是x出現(xiàn)的概率(即輸入為x的概率)，t(x)是算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為 其中Dn表示當(dāng)規(guī)模為n時(shí)，算法執(zhí)行的所有可能輸入的集合。 (2)最壞情況復(fù)雜性(Worst-case Complexity) 所謂最壞情況分析，是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。 2算法的空間復(fù)雜度 算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過(guò)程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間。如果額外空間量相對(duì)于問(wèn)題規(guī)模來(lái)說(shuō)是常數(shù)，則稱該算法是原地(in place)工作的。在許多實(shí)際問(wèn)題中，為了減少算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)，以便盡量減少不必要的額外空間。考點(diǎn)3 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)結(jié)構(gòu)(data structure)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。 數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究和討論以下三個(gè)方面： (l)數(shù)據(jù)集合中個(gè)數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； (2)在對(duì)數(shù)據(jù)元素進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)； (3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 討論以上問(wèn)題的日的是為了提高數(shù)據(jù)處理的效率，所謂提高數(shù)據(jù)處理的效率有兩個(gè)方面： (l)提高數(shù)據(jù)處理的速度； (2)盡量節(jié)省在數(shù)據(jù)處理過(guò)程中所占用的計(jì)算機(jī)存儲(chǔ)空間。 數(shù)據(jù)(data)：是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元素(data element)：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù)對(duì)象(data object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 在一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系(即連續(xù))，這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系(或直接前驅(qū)與直接后繼關(guān)系)來(lái)描述。 前后件關(guān)系是數(shù)據(jù)元素之間的一個(gè)基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義隨具體對(duì)象的不同而不同。一般來(lái)說(shuō)，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。 1數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。更通俗地說(shuō)，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。所謂結(jié)構(gòu)實(shí)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。 一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面信息： (1)表示數(shù)據(jù)元素的信息； (2)表示各數(shù)據(jù)元素之間的前后件關(guān)系。 考點(diǎn)4 數(shù)據(jù)結(jié)構(gòu)的圖形表示 數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。 在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。 在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)(也稱為葉子結(jié)點(diǎn))。 一個(gè)數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)可能是在動(dòng)態(tài)變化的。根據(jù)需要或在處理過(guò)程中，可以在一個(gè)數(shù)據(jù)結(jié)構(gòu)中增加一個(gè)新結(jié)點(diǎn)(稱為插入運(yùn)算)，也可以刪除數(shù)據(jù)結(jié)構(gòu)中的某個(gè)結(jié)點(diǎn)(稱為刪除運(yùn)算)。插入與刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。除此之外，對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改等。 考點(diǎn)5 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 如果在一個(gè)數(shù)據(jù)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素都沒(méi)有，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。 非空數(shù)據(jù)結(jié)構(gòu)滿足： (l)有且只有一個(gè)根結(jié)點(diǎn)； (2)每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱為線性表。一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。至于每個(gè)元素的具體含義，在不同的情況下各不相同，它可以是一個(gè)數(shù)或一個(gè)符號(hào)，也可以是一頁(yè)書(shū)，甚至其他更復(fù)雜的信息。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。對(duì)于空的數(shù)據(jù)結(jié)構(gòu)，如果對(duì)該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來(lái)處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。1.3 線性表及順序存儲(chǔ)結(jié)構(gòu) 考點(diǎn)6 線性表的定義 線性表是n(n0)個(gè)元素構(gòu)成的有限序列(a1，a2，an)。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。即線性表是一個(gè)空表，或可以表示為 (a1，a2，an) 其中ai(i=1，2，n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。 其中，每個(gè)元素可以簡(jiǎn)單到是一個(gè)字母或是一個(gè)數(shù)據(jù)，也可能是比較復(fù)雜的由多個(gè)數(shù)據(jù)項(xiàng)組成的。在復(fù)雜的線性表中，由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄(record)，而由多個(gè)記錄構(gòu)成的線性表又稱為文件(file)。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。非空線性表有如下一些結(jié)構(gòu)特征： (1)有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件； (2)有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件； (3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。 考點(diǎn)7 線性表的順序存儲(chǔ)結(jié)構(gòu) 線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。 線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征： (l)線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的； (2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 假設(shè)線性表的每個(gè)元素需要占用k個(gè)存儲(chǔ)單元，并以所占的存儲(chǔ)位置ADR(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置ADR(ai)之間滿足下列關(guān)系： ADR(ai+1)=ADR(ai)+k 線性表第i個(gè)元素ai的存儲(chǔ)位置為 ADR(ai)=ADR(a1)+(i-1)k 式中ADR(ai)是線性表的第一個(gè)數(shù)據(jù)元素a，的存儲(chǔ)位置，通常稱做線性表的起始位置或基址。 線性表的這種表示稱做線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像，這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。表中每一個(gè)元素的存儲(chǔ)位置都和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比例的常數(shù)。如圖1-4所示。由此只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。在程序設(shè)計(jì)語(yǔ)言中，通常定義一個(gè)一維數(shù)組來(lái)表示線性表的順序存儲(chǔ)空間。在用一維數(shù)組存放線性表時(shí)，該一維數(shù)組的長(zhǎng)度通常要定義得比線性表的實(shí)際長(zhǎng)度大一些，以便對(duì)線性表進(jìn)行各種運(yùn)算，特別是插入運(yùn)算。在線性表的順序存儲(chǔ)結(jié)構(gòu)下，可以對(duì)線性表做以下運(yùn)算： (l)在線性表的指定位置處加入一個(gè)新的元素(即線性表的插入)； (2)在線性表中刪除指定的元素(即線性表的刪除)； (3)在線性表中查找某個(gè)(或某些)特定的元素(即線性表的查找)； (4)對(duì)線性表中的元素進(jìn)行整序(即線性表的排序)； (5)按要求將一個(gè)線性表分解成多個(gè)線性表(即線性表的分解)； (6)按要求將多個(gè)線性表合并成一個(gè)線性表(即線性表的合并)； (7)復(fù)制一個(gè)線性表(即線性表的復(fù)制)； (8)逆轉(zhuǎn)一個(gè)線性表(即線性表的逆轉(zhuǎn))等。 考點(diǎn)8 順序表的插入運(yùn)算 線性表的插入運(yùn)算是指在表的第i(1in+l)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表 (a1，ai-1，ai，an) 變成長(zhǎng)度為n+1的線性表 (a1，ai-1，x，ai，an) 現(xiàn)在分析算法的復(fù)雜度。這里的問(wèn)題規(guī)模是表的長(zhǎng)度，設(shè)它的值為n。該算法的時(shí)間主要花費(fèi)在循環(huán)結(jié)點(diǎn)后移語(yǔ)句上，該語(yǔ)句的執(zhí)行次數(shù)(即移動(dòng)結(jié)點(diǎn)的次數(shù))是n-i+1。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。 當(dāng)i=n+1時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語(yǔ)句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜度O(1)； 當(dāng)i=1時(shí)，結(jié)點(diǎn)后移語(yǔ)句，將循環(huán)執(zhí)行n次，需移動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，其時(shí)間復(fù)雜度為O(n)。 由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平均復(fù)雜度。 在長(zhǎng)度為n的線性表中第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令Eis ( n )表示移動(dòng)結(jié)點(diǎn)的期望值(即移動(dòng)的平均次數(shù))，則在第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1。故 不失一般性，假設(shè)在表中任何位置(1in+1)上插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則 p1=p2=p3=pn+1=1/(n+1) 因此，在等概率插入的情況下， 也就是說(shuō)，在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半的結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。雖然Eis ( n )中n的的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線性級(jí)的。因此算法的平均時(shí)間復(fù)雜度為O(n)?？键c(diǎn)9 順序表的刪除運(yùn)算 線性表的刪除運(yùn)算是指將表的第i(1in)個(gè)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線性表： (a1，ai-1，ai，ai+1，an) 變成長(zhǎng)度為n-l的線性表 (a1，ai-1，ai+1，an) 該算法的時(shí)間分析與插入算法相似，結(jié)點(diǎn)的移動(dòng)次數(shù)也是由表長(zhǎng)n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語(yǔ)句將不執(zhí)行，無(wú)需移動(dòng)結(jié)點(diǎn)；若i=1，則前移語(yǔ)句將循環(huán)執(zhí)行n一1次，需移動(dòng)表中除開(kāi)始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時(shí)間復(fù)雜度分別為O(1)和O(n)。 刪除算法的平均性能分析與插入算法相似。在長(zhǎng)度為n的線性表中刪除一個(gè)結(jié)點(diǎn)，令Ede(n)表示所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)，刪除表中第i個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i，故 式子中，pi表示刪除表中第i個(gè)結(jié)點(diǎn)的概率。在等概率的假設(shè)下， p1=p2=p3=pn=1/n 由此可得： 即在順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)，平均時(shí)間復(fù)雜度也是O(n)。 1.4 棧和隊(duì)列 考點(diǎn)10 棧及其基本運(yùn)算 1什么是棧 棧實(shí)際也是線性表，只不過(guò)是一種特殊的線性表。棧(Stack)是只能在表的一端進(jìn)行插入和刪除運(yùn)算配線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒(méi)有元素時(shí)稱為空棧(棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。 假設(shè)棧S=(al，a2，a3，an)，則a1，稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說(shuō)，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為先進(jìn)后出表(FILO，F(xiàn)irst In Last Out)，或“后進(jìn)先出”表(LIFO，Last In First Out)，如圖1-7所示。 2棧的順序存儲(chǔ)及其運(yùn)算 (l)入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。首先將棧頂指針加一(即top加1)，然后將元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說(shuō)明棧空間已滿，不可能再進(jìn)行入棧操作。這種情況稱為?！吧弦纭卞e(cuò)誤。如圖1-8所示。 (2)退棧運(yùn)算：退棧是指取出棧頂元素并賦給一個(gè)指定的變量。首先將棧頂元素(棧頂指針指向的元素)賦給一個(gè)指定的變量，然后將棧頂指針減一(即t叩減1)。當(dāng)棧頂指針為。時(shí)，說(shuō)明?？?，不可進(jìn)行退棧操作。這種情況稱為棧的“下溢”錯(cuò)誤。 (3)讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。這個(gè)運(yùn)算不刪除棧頂元素，只是將它賦給一個(gè)變量，因此棧頂指針不會(huì)改變。當(dāng)棧頂指針為0時(shí)，說(shuō)明?？?，讀不到棧頂元素。 考點(diǎn)11 隊(duì)列及其基本運(yùn)算 1什么是隊(duì)列 隊(duì)列(queue)是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)， 當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次加入元素a1，a2，an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是a1，a2，an也就是說(shuō)隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。因此隊(duì)列亦稱作先進(jìn)先出(FIFO，F(xiàn)irst In First Out)的線性表，或后進(jìn)后出(LILO，Last In Last Out)的線性表。往隊(duì)列隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算，如圖1-10所示。 一個(gè)隊(duì)列幣。刪除個(gè)兒素后的隊(duì)列間插入元素E后的隊(duì)列 2循環(huán)隊(duì)列及其運(yùn)算 在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間 在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置。因此，從排頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。 可以將向量空間想象為一個(gè)首尾相接的圓環(huán)，如圖1-12所示，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列( Cireular Queue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1，朝前移動(dòng)。只不過(guò)當(dāng)頭尾指針指向向量上界(Queuesize-l)時(shí)，其加1操作的結(jié)果是指向向量的下界0。 由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，我們無(wú)法通過(guò)front=rear來(lái)判斷隊(duì)列“空”還是“滿”。 在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一個(gè)標(biāo)志、，、值的定義如下：當(dāng)s=0時(shí)表示隊(duì)列空；當(dāng)s=1時(shí)表示隊(duì)列非空。 (l)入隊(duì)運(yùn)算 入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。首先將隊(duì)尾指針進(jìn)一(即rear=rear+1)，并當(dāng)rear=m+l時(shí)置rear=1；然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空(s=l)且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說(shuō)明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”。(2)退隊(duì)運(yùn)算 退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)頭位置退出一個(gè)元素并賦給指定的變量。首先將隊(duì)頭指針一進(jìn)一(即from=front +1)，并當(dāng)front = m+1時(shí)，置front=1然后將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空(s =0)時(shí)，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為“下溢”1.5 線性鏈表 考點(diǎn)12 線性單鏈表的結(jié)構(gòu)及其基本運(yùn)算 1什么是線性鏈表 (l)線性表順序存儲(chǔ)的缺點(diǎn) 在一般情況下，要在順序存儲(chǔ)的線性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)，為了保證插入或刪除后的線性表仍然為順序存儲(chǔ)，則在插入或刪除過(guò)程中需要移動(dòng)大量的數(shù)據(jù)元素。因此采用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行插入或刪除的運(yùn)算效率很低； 當(dāng)為一個(gè)線性表分配順序存儲(chǔ)空間后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿，但還需要插入新的元素時(shí)棧會(huì)發(fā)生“上溢”錯(cuò)誤； 計(jì)算機(jī)空間得不到充分利用，并且不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。 (2)線性表鏈?zhǔn)降幕靖拍?在定義的鏈表中，若只含有一個(gè)指針域來(lái)存放下一個(gè)元素地址，稱這樣的鏈表為單鏈表或線性鏈表。 在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)。如圖1-13所示。 2線性單鏈表的存儲(chǔ)結(jié)構(gòu) 用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后件結(jié)點(diǎn)的地址(或位置)信息，這個(gè)信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)， 鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起。由于上述鏈表的每一個(gè)結(jié)點(diǎn)只有一個(gè)鏈域，故將這種鏈表稱為單鏈表(Single Linked)。 顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前驅(qū)結(jié)點(diǎn)Next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前驅(qū)，故應(yīng)設(shè)頭指針HEAD指向開(kāi)始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后件，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL。 3帶鏈的棧與隊(duì)列 (1)棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在實(shí)際應(yīng)用中，帶鏈的?？梢杂脕?lái)收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧 (2)隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，考點(diǎn)13 線性鏈表的基本運(yùn)算 線性鏈表的運(yùn)算主要有以下幾個(gè)： (l)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素； (2)在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)； (3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性表； (4)將一個(gè)線性鏈表按要求進(jìn)行分解； (5)逆轉(zhuǎn)線性鏈表； (6)復(fù)制線性鏈表； (7)線性鏈表的排序； (8)線性鏈表的查找。 1在線性鑊表中查找指定元素 在對(duì)線性鏈表進(jìn)行插入或刪除的運(yùn)算中，總是首先需要找到插入或刪除的位置，這就需要對(duì)線性鏈表進(jìn)行掃描查找，在線性鏈表中尋找包含指定元素的前一個(gè)結(jié)點(diǎn)。 在線性鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)a，也不能像順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域Next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。 在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值x的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為x的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值x作比較。 2線性鏈表的插入 線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中插入一個(gè)新元素。 插入運(yùn)算是將值為X的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1，與ai之間。因此，我們必須首先找到ai-1的存儲(chǔ)位置p，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*p，并令結(jié)點(diǎn)，p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai 由線性鏈表的插入過(guò)程可以看出，由于插入的新結(jié)點(diǎn)取自于可利用棧，因此，只要可利用棧不空，在線性鏈表插入時(shí)總能取到存儲(chǔ)插入元素的新結(jié)點(diǎn)，不會(huì)發(fā)生“上溢”的情況。而且，由于可利用棧是公用的，多個(gè)線性鏈表可以共享它，從而很方便地實(shí)現(xiàn)了存儲(chǔ)空間的動(dòng)態(tài)分配。另外，線性鏈表在插入過(guò)程中不發(fā)生數(shù)據(jù)元素移動(dòng)的現(xiàn)象，只要改變有關(guān)結(jié)點(diǎn)的指針即可，從而提高了插入的效率。 3多線性鏈表的刪除 線性鏈表的刪除是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。 刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)a的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1，的指針域Next中，所以我們必須首先找到ai-1的存儲(chǔ)位置p。然后令p-Next指向ai的直接后件結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)a的空間。 從線性鏈表的刪除過(guò)程可以看出，從線性鏈表中刪除一個(gè)元素后，不需要移動(dòng)表中的數(shù)據(jù)元素，只要改變被刪除元素所在結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針域即可。另外，由于可利用棧是用于收集計(jì)算機(jī)中所有的空閑結(jié)點(diǎn)，因此，當(dāng)從線性鏈表中刪除一個(gè)元素后，該元素的存儲(chǔ)結(jié)點(diǎn)就變?yōu)榭臻e，應(yīng)將空閑結(jié)點(diǎn)送回到可利用棧。 考點(diǎn)14 線性雙向鏈表的結(jié)構(gòu)及其基本運(yùn)算 1什么是雙向鏈表 在單鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時(shí)間復(fù)雜度為O(1)，但無(wú)法直接找到它的互接前件；在單循環(huán)鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時(shí)間復(fù)雜度仍為O(1)，直接找到它的直接前件，時(shí)間復(fù)雜度為O(n)。有時(shí)，希望能快速找到一個(gè)結(jié)點(diǎn)的直接前件，這時(shí)，可以在單鏈表中的結(jié)點(diǎn)中增加一個(gè)指針域指向它的直接前件，這樣的鏈表，就稱為雙向鏈表(一個(gè)結(jié)點(diǎn)中含有兩個(gè)指針)。如果每條鏈構(gòu)成一個(gè)循環(huán)鏈表，則會(huì)得到雙向循環(huán)鏈表 2雙向鏈表的基本運(yùn)算 (l)插入：在HEAD為頭指針的雙向鏈表中，在值為Y的結(jié)點(diǎn)之后插入值為X的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針變化。如圖1-20所示(若改為在值為Y的結(jié)點(diǎn)之前插入值為X的結(jié)點(diǎn)，可以做類似分析)。 (2)刪除：在以HEAD為頭指針的雙向鏈表中刪除值為X的結(jié)點(diǎn)，刪除算法的指針變化，如圖1-21所示。 考點(diǎn)15 循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算 單鏈表上的訪問(wèn)是一種順序訪問(wèn)，從其中的某一個(gè)結(jié)點(diǎn)出發(fā)，可以找到它的直接后件，但無(wú)法找到它的直接前件。 在前面所討論的線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問(wèn)題，在運(yùn)算過(guò)程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。 因此，我們可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存貯空間，僅對(duì)表的鏈接方式稍做改變，使得對(duì)表的處理更加方便靈活。從單鏈表可知，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)镹ULL，表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)(或第一個(gè)結(jié)點(diǎn))的地址，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，又沒(méi)有增加額外的存儲(chǔ)空間 循環(huán)鏈表具有以下兩個(gè)特點(diǎn)： (1)在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)； (2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。 在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)。 由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表的運(yùn)算統(tǒng)一。1.6 樹(shù)與二叉樹(shù) 考點(diǎn)16 樹(shù)的定義 樹(shù)是由n( n0)個(gè)結(jié)點(diǎn)組成的有限集合。若n =0，稱為空樹(shù)；若n0，則： (1)有一個(gè)特定的稱為根(root)的結(jié)點(diǎn)。它只有直接后件，但沒(méi)有直接前件； (2)除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn)可以劃分為m(m0)個(gè)互不相交的有限集合T0，T1，Tm-1，每個(gè)集合Ti(i=0，1，m-l)又是一棵樹(shù)，稱為根的子樹(shù)，每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前件，但可以有0個(gè)或多個(gè)直接后件。樹(shù)型結(jié)構(gòu)具有如下特點(diǎn)： (1)助每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱為樹(shù)的根； (2)每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)； (3)一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為樹(shù)的結(jié)點(diǎn)度； (4)樹(shù)的最大層次稱為樹(shù)的深度。 在計(jì)算機(jī)中，可以用樹(shù)結(jié)構(gòu)來(lái)表示算術(shù)表達(dá)式，用樹(shù)來(lái)表示算術(shù)表達(dá)式的原則是： (1)表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)； (2)運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)(在樹(shù)中的順序?yàn)閺淖蟮接?； (3)運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。 樹(shù)在計(jì)算機(jī)中通常用多重鏈表表示。 考點(diǎn)17 二叉樹(shù)的定義及其基本性質(zhì) 1什么是二叉樹(shù) 二叉樹(shù)(binary tree)是由n(0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹(shù)組成，并且左右子樹(shù)都是二叉樹(shù)。二叉樹(shù)可以是空集合，根可以有空的左子樹(shù)或空的右子樹(shù)。二叉樹(shù)不是樹(shù)的特殊情況，它們是兩個(gè)概念。 二叉樹(shù)具有如下兩個(gè)特點(diǎn)： (1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； (2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。 二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，或者說(shuō)，在二叉樹(shù)中，不存在度大于2的結(jié)點(diǎn)，并且二叉樹(shù)是有序樹(shù)(樹(shù)為無(wú)序樹(shù))，其子樹(shù)的順序不能顛倒，因此，二叉樹(shù)有5種不同的形態(tài) 在二叉樹(shù)中，一個(gè)結(jié)點(diǎn)可以只有左子樹(shù)而沒(méi)有右子樹(shù)，也可以只有右子樹(shù)而沒(méi)有左子樹(shù)。當(dāng)一個(gè)結(jié)點(diǎn)既沒(méi)有左子樹(shù)也沒(méi)有右子樹(shù)時(shí)，該結(jié)點(diǎn)即是葉子結(jié)點(diǎn)) 2二叉樹(shù)的基本性質(zhì) 性質(zhì)1：在二叉樹(shù)的第入層上至多有2k-1個(gè)結(jié)點(diǎn)(k1)。 性質(zhì)2：深度為m的二叉樹(shù)至多有2m-1個(gè)結(jié)點(diǎn)。 深度為m的二叉樹(shù)的最大的結(jié)點(diǎn)數(shù)是為二叉樹(shù)中每層上的最大結(jié)點(diǎn)數(shù)之和，由性質(zhì)1得到最大結(jié)點(diǎn)數(shù)。 性質(zhì)3：對(duì)任何一棵二叉樹(shù)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。 如果葉子結(jié)點(diǎn)