1.1 考點(diǎn)精講

計(jì)算機(jī)已經(jīng)被廣泛用于數(shù)據(jù)處理。所謂數(shù)據(jù)處理，是指對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行操作，包括插入、刪除、查找、更改等，也包括對(duì)數(shù)據(jù)元素進(jìn)行分析。在進(jìn)行數(shù)據(jù)處理時(shí)，實(shí)際需要處理的數(shù)據(jù)元素一般很多，而這些大量的數(shù)據(jù)元素都需要存放在計(jì)算機(jī)中，因此，大量的數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，這是進(jìn)行數(shù)據(jù)處理的關(guān)鍵問題。

算法是一個(gè)十分古老的研究課題，然而計(jì)算機(jī)的出現(xiàn)為這個(gè)課題注入了青春和活力，使算法的設(shè)計(jì)和分析成為計(jì)算機(jī)學(xué)科中最為活躍的研究熱點(diǎn)之一。針對(duì)實(shí)際問題，例如要編制一個(gè)高效率的處理程序，那就需要解決如何合理地組織數(shù)據(jù)，建立合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)好的算法來提高程序執(zhí)行的效率這樣的問題。

1.1.1 算法

算法（algorithm）是對(duì)解題方案的準(zhǔn)確而完整的描述。但它不等于程序，也不等于計(jì)算方法。通常，程序的編制不可能優(yōu)于算法的設(shè)計(jì)。算法是指令的有限序列，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。當(dāng)然，程序也可以作為算法的一種描述，但程序通常還需考慮很多與方法和分析無關(guān)的細(xì)節(jié)問題，這是因?yàn)樵诰帉懗绦驎r(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制。

1.算法的基本特征

一個(gè)算法，一般應(yīng)具有以下幾個(gè)基本特征：

1）可行性：算法的可行性，是指算法中指定的操作都可以通過基本運(yùn)算執(zhí)行有限的次數(shù)后實(shí)現(xiàn)。針對(duì)實(shí)際問題設(shè)計(jì)算法時(shí)必須考慮它的可行性，因?yàn)槿藗兛偸窍Ｍ軌蜻_(dá)到滿意的結(jié)果。

2）確定性：算法的確定性，是指算法中的每一個(gè)步驟都必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。

3）有窮性：算法的有窮性，是指一個(gè)算法必須在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。另外，算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間，如果一個(gè)算法需要執(zhí)行很長時(shí)間甚至上千年才能終止，就失去了實(shí)用價(jià)值。

4）擁有足夠的情報(bào)：一個(gè)算法是否有效，還取決于為算法所提供的情報(bào)是否足夠，一般來說，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的，否則，可能無效。

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)化流程圖、算法描述語言等。一個(gè)算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。

3.算法設(shè)計(jì)的基本方法

計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。計(jì)算機(jī)算法不同于人工處理的方法，下面是工程上常用的幾種算法設(shè)計(jì)方法，在實(shí)際應(yīng)用時(shí)，各種方法之間往往存在著一定的聯(lián)系。

（1）列舉法

列舉法的基本思想是，針對(duì)待解決的問題，列舉所有可能的情況，并用問題中給定的條件來檢驗(yàn)?zāi)男┦潜匦璧模男┦遣恍枰摹Ｒ虼耍信e法常用于解決“是否存在”或“有多少種可能”等類型的問題。例如，我國古代的趣味數(shù)學(xué)題：“百錢買百雞”、“雞兔同籠”等求解不定方程的問題，均可采用列舉法解決。

其特點(diǎn)是原理比較簡單，但當(dāng)列舉的可能情況較多時(shí)，執(zhí)行列舉算法的工作量將會(huì)很大。因此，在用列舉法設(shè)計(jì)算法時(shí)，只要對(duì)實(shí)際問題進(jìn)行詳細(xì)的分析，將與問題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，從中找出規(guī)律；或?qū)λ锌赡艿那闆r進(jìn)行分類，引出一些有用的信息，就可以大大減少列舉量。

列舉算法雖然是一種比較笨拙而原始的方法，其運(yùn)算量比較大，但在有些實(shí)際問題中（如尋找路徑、查找、搜索等問題），局部使用列舉法卻是很有效的。因此，列舉算法是計(jì)算機(jī)算法中的一個(gè)基礎(chǔ)算法。

（2）歸納法

歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后歸納出一般的關(guān)系。顯然，歸納法比列舉法更能反映問題的本質(zhì)，并且可以解決列舉量為無限的問題。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出一般性的結(jié)論。

歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對(duì)所有的情況進(jìn)行列舉，因此，該方法得到的結(jié)論只是一種猜測(cè)，還需要進(jìn)行證明。

（3）遞推法

遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個(gè)中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問題本身已經(jīng)給定，或是通過對(duì)問題的分析與化簡而確定。遞推的本質(zhì)也是一種歸納，工程上許多遞推關(guān)系式實(shí)際上是通過對(duì)實(shí)際問題的分析與歸納得到的。因此，遞推關(guān)系式通常是歸納的結(jié)果。

遞推算法在數(shù)值計(jì)算中是極為常見的。例如，裴波那契數(shù)列是采用遞推的方法解決問題的。但是，對(duì)于數(shù)值型的遞推算法必須注意數(shù)值計(jì)算的穩(wěn)定性問題。

（4）遞歸

在解決一些復(fù)雜問題或問題的規(guī)模比較大時(shí)，為了降低問題的復(fù)雜程序，通常將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，并沒有對(duì)問題進(jìn)行求解，而只是在解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進(jìn)行綜合，這就是遞歸的基本思想。

遞歸分為直接遞歸和間接遞歸兩種方法。如果一個(gè)算法直接調(diào)用自己，稱為直接遞歸調(diào)用；如果一個(gè)算法A調(diào)用另一個(gè)算法B，而算法B又調(diào)用算法A，則此種遞歸稱為間接遞歸調(diào)用。遞歸過程能將一個(gè)復(fù)雜的問題歸納為若干較簡單的問題，然后將這些較簡單的問題再歸結(jié)為更簡單的問題，這個(gè)過程可以一直做下去，直到歸結(jié)出最簡單的問題為止。由此可以看出，遞歸的基礎(chǔ)也是歸納。在實(shí)際工程中，許多問題就是用遞歸來定義的，數(shù)學(xué)中的許多函數(shù)也是用遞歸來定義的。遞歸在可計(jì)算性理論和算法設(shè)計(jì)中占很重要的地位。

（5）減半遞推技術(shù)

實(shí)際問題的復(fù)雜程序往往與問題的規(guī)模有著密切的聯(lián)系。因此，利用分治法解決這類實(shí)際問題是有效的。所謂分治法，就是對(duì)問題分而治之。工程上常用的分治法是減半遞推技術(shù)。

所謂“減半”，即將問題的規(guī)模減半，而問題的性質(zhì)不變；所謂“遞推”，是指重復(fù)“減半”的過程。例如，一元二次方程的求解，求解過程見下例。

例如，設(shè)方程f(x)=0在區(qū)間[a，b]上有實(shí)根，且f(a)與f(b)異號(hào)。利用二分法求該方程在區(qū)間[a，b]上的一個(gè)實(shí)根。

用二分法求方程實(shí)根的減半遞推過程如下：

首先取給定區(qū)間的中點(diǎn)c=(a+b)/2。

然后判斷f(c)是否為0.若f(c)=0，則說明c即為所求的根，求解過程結(jié)束；如果f(c)≠0，則根據(jù)以下原則將原區(qū)間減半：

若f(a)f(c)＜0，則取原區(qū)間的前半部分；

若f(b)f(c)＜0，則取原區(qū)間的后半部分。

最后判斷減半后的區(qū)間長度是否已經(jīng)很小：

若|a-b|＜ε，則過程結(jié)束，取(a+b)/2為根的近似值；

若|a-b|≥ε，同重復(fù)上述的減半過程。

（6）回溯法

前面討論的遞推和遞歸算法本質(zhì)上是對(duì)實(shí)際問題進(jìn)行歸納的結(jié)果，而減半遞推技術(shù)也是歸納法的一個(gè)分支。在工程上，有些實(shí)際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能無限地列舉。對(duì)于這類問題，只能采用“試探”的方法，通過對(duì)問題的分析，找出解決問題的線索，然后沿著這個(gè)線索進(jìn)行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換其他路線進(jìn)行試探。這種方法即稱為回溯法。

回溯法在處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)方面有著廣泛的應(yīng)用，如人工智能中的機(jī)器人下棋。

4.算法復(fù)雜度

算法的復(fù)雜度主要分為時(shí)間復(fù)雜度和空間復(fù)雜度。

（1）算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

為了能夠比較客觀地反映出一個(gè)算法的效率，一個(gè)算法的工作量不僅與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。為此，可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即

算法的工作量=f(n)

其中n是問題規(guī)模。例如，兩個(gè)n階矩陣相乘所需要的基本運(yùn)算次數(shù)為n3，即計(jì)算量為n3，也就是時(shí)間復(fù)雜度為n3。

另外，在同一問題規(guī)模下，若算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定的輸入數(shù)據(jù)，則可以用平均性態(tài)分析和最壞情況分析兩種方法來分析算法的工作量。顧名思義，平均性態(tài)分析即輸入所有可能的平均值，相應(yīng)的時(shí)間復(fù)雜度為算法的平均時(shí)間復(fù)雜度；最壞情況分析則是以最壞的情況估算算法執(zhí)行時(shí)間的一個(gè)上界。一般情況下，后者更為常用。

（2）算法的空間復(fù)雜度

一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間（例如，在鏈?zhǔn)浇Y(jié)構(gòu)中，除了需要存儲(chǔ)數(shù)據(jù)本身之外，還需要存儲(chǔ)鏈接信息）。如果額外空間量相對(duì)于問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。

在許多實(shí)際問題中，為了減少算法的內(nèi)存空間，一般采用壓縮存儲(chǔ)技術(shù)，以便盡量減少不必要的額外空間。

1.1.2 數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)（data structure）是指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示，其作為計(jì)算機(jī)的一門學(xué)科，主要研究和討論以下3個(gè)方面的問題：

1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。

2）各數(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ù)處理的效率。提高數(shù)據(jù)處理的效率主要包括兩個(gè)方面：一是提高數(shù)據(jù)速度，二是盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存儲(chǔ)空間。

1.什么是數(shù)據(jù)結(jié)構(gòu)

在數(shù)據(jù)處理領(lǐng)域中，建立數(shù)學(xué)模型有時(shí)并不十分重要，事實(shí)上，許多實(shí)際問題是無法表示成數(shù)學(xué)模型的。人們最感興趣的是知道數(shù)據(jù)集合中各數(shù)據(jù)元素之間存在什么關(guān)系，應(yīng)如何組織它們，即如何表示所需要處理的數(shù)據(jù)元素。

數(shù)據(jù)的組織方式不同，通常對(duì)它進(jìn)行處理時(shí)的效率也不同。例如，在對(duì)兩個(gè)存放了相同元素的表進(jìn)行查找時(shí)，如果一個(gè)表中的所有數(shù)據(jù)元素是沒有規(guī)律的，而另外一個(gè)表中的元素是經(jīng)過排序的，則對(duì)前者進(jìn)行查找時(shí)，只能從第一個(gè)元素開始，逐個(gè)將表中的元素與被查數(shù)進(jìn)行比較，直到表中的某個(gè)元素與被查數(shù)相等（即查找成功）或者表中所有元素與被查數(shù)都進(jìn)行了比較且都不相等（即查找失敗）為止。而對(duì)于后者，由于有序表中的元素是從小到大進(jìn)行排列的，在查找時(shí)可以利用這個(gè)特點(diǎn)，使比較次數(shù)大大減少。可見數(shù)據(jù)元素在表中的排列順序?qū)Σ檎倚适怯泻艽笥绊懙摹?/p>

要理解數(shù)據(jù)結(jié)構(gòu)，還需要理解以下基本概念：

●數(shù)據(jù)（data）是對(duì)客觀事物的符號(hào)表示，是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。在計(jì)算機(jī)學(xué)科中，數(shù)據(jù)就是計(jì)算機(jī)加工處理的對(duì)象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。

●數(shù)據(jù)元素（data element）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。例如，描述一年四季的季節(jié)名：春、夏、秋、冬可以作為季節(jié)的數(shù)據(jù)元素。

●數(shù)據(jù)對(duì)象（data object）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個(gè)具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對(duì)象，數(shù)據(jù)元素是數(shù)據(jù)元素類的一個(gè)實(shí)例。

●數(shù)據(jù)結(jié)構(gòu)（data structure）是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系（即連續(xù)），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（或直接前驅(qū)與直接后繼關(guān)系）來描述。例如，在考慮一年四個(gè)季節(jié)的順序關(guān)系時(shí)，“春”是“夏”的前件（即直接前驅(qū)，下同），而“夏”是“春”的后件（即直接后繼，下同）。同樣，“夏”是“秋”的前件，“秋”是“夏”的后件；“秋”是“冬”的前件，“冬”是“秋”的后件。在考慮家庭成員間的輩分關(guān)系時(shí)，“父親”是“兒子”和“女兒”的前件，而“兒子”與“女兒”都是“父親”的后件。

前后件關(guān)系是數(shù)據(jù)元素之間的一個(gè)基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義隨具體對(duì)象的不同而不同。一般來說，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述。

2.數(shù)據(jù)的邏輯結(jié)構(gòu)

前面提到，數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。通俗地說，數(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)系。

所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。由前面的敘述可以知道，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是用D表示數(shù)據(jù)元素的集合，二是用R表示數(shù)據(jù)元素之間的前后件關(guān)系。即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為B=(D，R)，其中B表示數(shù)據(jù)結(jié)構(gòu)。這就是一個(gè)二元關(guān)系的表示方式。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。例如，假設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組(a，b)表示a是b的前件，b是a的后件。這樣，在D中的每兩個(gè)元素之間的關(guān)系都可以用這種二元組來表示。

例如，一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成

B={D，R}

D={春，夏，秋，冬}

R={(春，夏)，(夏，秋)，(秋，冬)}

例如，家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示成

B=(D，R)

D=｛父親，兒子，女兒｝

R=｛(父親，兒子)，(父親，女兒)｝

例如，n維向量X=(x1，x2，…，xn)也是一種數(shù)據(jù)結(jié)構(gòu)，即X={D，R}，

其中數(shù)據(jù)元素集合為

D={x1，x2，…，xn}

關(guān)系為

R={(x1，x2)，(x2，x3)，…，(xn-1，xn)}

3.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

在進(jìn)行數(shù)據(jù)處理時(shí)，計(jì)算機(jī)所處理的數(shù)據(jù)總是存放在計(jì)算機(jī)的存儲(chǔ)空間中，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的各元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系有可能是不同的。

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱為數(shù)據(jù)的物理結(jié)構(gòu)）。

由于數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計(jì)算機(jī)存儲(chǔ)空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。

一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等，采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)是很重要的。

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é)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。

例如，一年四季的數(shù)據(jù)結(jié)構(gòu)可以用如圖1-1所示的圖形來表示。

又例如，反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)可以用如圖1-2所示的圖形表示。

顯然，用圖形方式表示一個(gè)數(shù)據(jù)結(jié)構(gòu)是很方便的，并且也比較直觀。

在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（也稱為葉子結(jié)點(diǎn)）。例如，在圖1-1所示的數(shù)據(jù)結(jié)構(gòu)中，元素“春”所在的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)“春”，下同）為根結(jié)點(diǎn)，結(jié)點(diǎn)“冬”為終端結(jié)點(diǎn)；在圖1-2所示的數(shù)據(jù)結(jié)構(gòu)中，結(jié)點(diǎn)“父親”為根結(jié)點(diǎn)，結(jié)點(diǎn)“兒子”與結(jié)點(diǎn)“女兒”均為終端結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)中除了根結(jié)點(diǎn)與終端結(jié)點(diǎn)外的其他結(jié)點(diǎn)一般稱為內(nèi)部結(jié)點(diǎn)。

通常，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)可能是動(dòng)態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個(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ù)制和修改等。在對(duì)數(shù)據(jù)結(jié)構(gòu)的處理過程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)（即數(shù)據(jù)元素）的個(gè)數(shù)在動(dòng)態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動(dòng)態(tài)變化。例如，一個(gè)無序表可以通過排序處理而變成有序表；一個(gè)數(shù)據(jù)結(jié)構(gòu)中的根結(jié)點(diǎn)被刪除后，它的某一個(gè)后件可能變成了根結(jié)點(diǎn)；在一個(gè)數(shù)據(jù)結(jié)構(gòu)中的終端結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)后，則原來的那個(gè)終端結(jié)點(diǎn)就不再是終端結(jié)點(diǎn)而成為內(nèi)部結(jié)點(diǎn)了。有關(guān)數(shù)據(jù)的基本運(yùn)算將在后面講到具體數(shù)據(jù)結(jié)構(gòu)時(shí)再介紹。

5.線性結(jié)構(gòu)與非線性結(jié)構(gòu)

如果一個(gè)數(shù)據(jù)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。一個(gè)空的數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新的元素后，該數(shù)據(jù)結(jié)構(gòu)就變?yōu)榉强諗?shù)據(jù)結(jié)構(gòu)；在只有一個(gè)數(shù)據(jù)元素的數(shù)據(jù)結(jié)構(gòu)中，將該元素刪除后，該數(shù)據(jù)結(jié)構(gòu)就變?yō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)。

如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足如下兩個(gè)條件：

1）有且只有一個(gè)根結(jié)點(diǎn)。

2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱為線性表。

由此可以看出，在線性結(jié)構(gòu)中，各數(shù)據(jù)元素之間的前后件關(guān)系是很簡單的。例如，圖1-1中一年四季這個(gè)數(shù)據(jù)結(jié)構(gòu)就屬于線性結(jié)構(gòu)。

特別需要說明的是，在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。根據(jù)這一點(diǎn)，如果一個(gè)數(shù)據(jù)結(jié)構(gòu)滿足上述兩個(gè)條件，但在此數(shù)據(jù)結(jié)構(gòu)中插入或刪除任何一個(gè)就不滿足這兩個(gè)條件時(shí)，則該數(shù)據(jù)結(jié)構(gòu)不能稱為線性結(jié)構(gòu)。例如，圖1-3的數(shù)據(jù)結(jié)構(gòu)顯然是滿足上述兩個(gè)條件的，但它不屬于線性結(jié)構(gòu)，因?yàn)樵谶@個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除結(jié)點(diǎn)A后，就不滿足上述的條件1）了。

如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱為非線性結(jié)構(gòu)。例如，圖1-2中的家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，而是非線性結(jié)構(gòu)。顯然，在非線性結(jié)構(gòu)中，各數(shù)據(jù)元素之間的前后件關(guān)系要比線性結(jié)構(gòu)復(fù)雜，因此，對(duì)非線性結(jié)構(gòu)的存儲(chǔ)與處理比線性結(jié)構(gòu)要復(fù)雜得多。

線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。一個(gè)空的數(shù)據(jù)結(jié)構(gòu)究竟是線性結(jié)構(gòu)，還是非線性結(jié)構(gòu)，要根據(jù)具體情況來確定。如果對(duì)該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)。

1.1.3 線性表

線性表的特點(diǎn)是數(shù)據(jù)元素之間的關(guān)系是線性的，數(shù)據(jù)元素可以看成是排列在一條線或一個(gè)環(huán)上。線性表（linear list）是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。

1.線性表的基本概念

線性表由一組數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元素的含義很廣泛，在不同的情況下，它可以有不同的含義。例如，一個(gè)n維向量（x1，x2，…，xn）是一個(gè)長度為n的線性表，其中的每一個(gè)分量就是一個(gè)數(shù)據(jù)元素。又例如，英文小寫字母表（a，b，c，…，z）是一個(gè)長度為26的線性表，其中的每一個(gè)小寫字母就是一個(gè)數(shù)據(jù)元素。再如，一年中的4個(gè)季節(jié)（春、夏、秋、冬）是一個(gè)長度為4的線性表，其中的每一個(gè)季節(jié)名就是一個(gè)數(shù)據(jù)元素。

數(shù)據(jù)元素可以是簡單項(xiàng)（如上述例子中的數(shù)字、字母、季節(jié)名等）。在稍微復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素還可以由若干數(shù)據(jù)項(xiàng)組成。例如，某班的學(xué)生情況登記表是一個(gè)復(fù)雜的線性表，表中每一個(gè)學(xué)生的情況就組成了線性表中的每一個(gè)元素，每一個(gè)數(shù)據(jù)元素包括學(xué)號(hào)、姓名、性別、年齡、班級(jí)5個(gè)數(shù)據(jù)項(xiàng)，如表1-1所示。在這種復(fù)雜的線性表中，由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄，而由多個(gè)記錄構(gòu)成的線性表又稱為文件。因此，上述學(xué)生情況登記表就是一個(gè)文件，其中每一個(gè)學(xué)生的情況就是一個(gè)記錄。

表1-1 學(xué)生情況登記表

綜上所述，線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n（n≥0）個(gè)結(jié)點(diǎn)的有限序列。對(duì)于其中的結(jié)點(diǎn)，有且僅有一個(gè)根結(jié)點(diǎn)，沒有前件但有一個(gè)后件；有且僅有一個(gè)終端結(jié)點(diǎn)，沒有后件但有一個(gè)前件。其他的結(jié)點(diǎn)都有且僅有一個(gè)前件和一個(gè)后件。一般地，一個(gè)線性表可以表示成一個(gè)線性序列：a1，a2，…，an，其中a1是根結(jié)點(diǎn)，an是終端結(jié)點(diǎn)。

線性結(jié)構(gòu)的基本特征如下：

1）有且僅有一個(gè)根結(jié)點(diǎn)，無前件。

2）有且僅有一個(gè)終端結(jié)點(diǎn)，無后件。

3）除終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)均有且僅有一個(gè)后件。

4）除根結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)均有且僅有一個(gè)前件。

由n（n≥0）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a1，a2，…，an組成的有限序列稱為線性表，其中數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長度。當(dāng)n=0時(shí)稱為空表，常常將非空的線性表（n>0）記作：（a1，a2，…，an）。

2.線性表的順序存儲(chǔ)

在計(jì)算機(jī)中存放線性表，一種最簡單的方法是順序存儲(chǔ)，也稱為順序分配。

線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。

線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征：

1）線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的。

2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面。如果線性表中各數(shù)據(jù)元素所占的存儲(chǔ)空間（字節(jié)數(shù)）相等，則要在線性表中查找某一個(gè)元素是很方便的。

假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址（指第一字節(jié)的地址，即首地址）為ADR（a1），每個(gè)元素需要占用k個(gè)存儲(chǔ)單元，則線性表中第i個(gè)元素ai在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為

ADR(ai)=ADR(a1)+(i-1)×k

即在順序存儲(chǔ)結(jié)構(gòu)中，線性表中每一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該元素在線性表中的位置序號(hào)唯一確定。一般來說，長度為n的線性表（a1，a2，…，an），設(shè)每個(gè)數(shù)據(jù)元素在內(nèi)存中占4字節(jié)，起始元素的存儲(chǔ)地址為1010，則該線性表在計(jì)算機(jī)中的順序存儲(chǔ)結(jié)構(gòu)如圖1-4所示。

在程序設(shè)計(jì)語言中，通常定義一個(gè)一維數(shù)組來表示線性表的順序存儲(chǔ)空間。在用一維數(shù)組存放線性表時(shí)，該一維數(shù)組的長度通常要定義得比線性表的實(shí)際長度大一些，以便對(duì)線性表進(jìn)行各種運(yùn)算，特別是插入運(yùn)算。在一般情況下，如果線性表的長度在處理過程中是動(dòng)態(tài)變化的，則在開辟線性表的存儲(chǔ)空間時(shí)，要考慮到線性表在動(dòng)態(tài)變化過程中可能達(dá)到的最大長度。

在線性表的順序存儲(chǔ)結(jié)構(gòu)下，可以對(duì)線性表做以下運(yùn)算：

1）在線性表的指定位置處加入一個(gè)新的元素（即線性表的插入）。

2）在線性表中刪除指定的元素（即線性表的刪除）。

3）在線性表中查找某個(gè)（或某些）特定的元素（即線性表的查找）。

4）對(duì)線性表中的元素進(jìn)行排序（即線性表的排序）。

5）將一個(gè)線性表分解成多個(gè)線性表（即線性表的分解）。

6）將多個(gè)線性表合并成一個(gè)線性表（即線性表的合并）。

7）復(fù)制一個(gè)線性表（即線性表的復(fù)制）。

8）逆轉(zhuǎn)一個(gè)線性表（即線性表的逆轉(zhuǎn)）等。

線性表的基本運(yùn)算是插入運(yùn)算和刪除運(yùn)算，下面兩小節(jié)主要討論這兩種運(yùn)算。

3.線性表的插入運(yùn)算

線性表的插入運(yùn)算是指在表的第i（1≤i≤n+l）個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長度為n的線性表：

（a1,…,ai－1,ai,…,an）

變成長度為n+1的線性表：（a1…,ai-1,x,a,…,an）

首先舉一個(gè)例子來說明如何在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入一個(gè)新元素。

例如，圖1-5a是一個(gè)長度為8的線性表，順序存儲(chǔ)在長度為10的存儲(chǔ)空間中。現(xiàn)在要求在第2個(gè)元素（即18）之前插入一個(gè)新元素35。其插入過程如下：

首先從最后一個(gè)元素開始直到第2個(gè)元素，將其中的每一個(gè)元素均依次往后移動(dòng)一個(gè)位置，然后將新元素35插入第2個(gè)位置。

插入一個(gè)新元素后，線性表的長度變成了9，如圖1-5b所示。

如果要再在線性表的第9個(gè)元素之前插入一個(gè)新元素22，則采用類似的方法：將第9個(gè)元素往后移動(dòng)一個(gè)位置，然后將新元素插入第9個(gè)位置。插入后，線性表的長度變成了10，如圖1-5c所示。

現(xiàn)在，為線性表開辟的存儲(chǔ)空間已經(jīng)滿了，不能再插入新的元素了。如果再要插入，則會(huì)造成稱為“上溢”的錯(cuò)誤。

一般來說，設(shè)長度為n的線性表為

（a1，…，ai-1，ai，…，an）

現(xiàn)要在線性表的第i個(gè)元素ai之前插入一個(gè)新元素b，插入后得到長度為n+1的線性表為

（a1′，a2′，…，aj′，aj+1′，…，an′，an+1′）

則插入前后的兩線性表中的元素滿足如下關(guān)系：

在一般情況下，要在第i（1≤i≤n）個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開始，直到第i個(gè)元素，共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入第i項(xiàng)。插入結(jié)束后，線性表的長度就增加了1。

下面分析插入算法的時(shí)間復(fù)雜度。順序表的插入運(yùn)算，其時(shí)間主要花費(fèi)在了數(shù)據(jù)的移動(dòng)上，在第i個(gè)位置插入b，從ai到an都要向后移動(dòng)一個(gè)位置，共需要移動(dòng)n-i+1個(gè)元素，而i的取值范圍為1≤i≤n，即有n+1個(gè)位置可以插入。假設(shè)在第i個(gè)位置上做插入操作的概率為pi，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)為：

設(shè)pi=1/(n+1)，即為等概率情況，則

這說明，在順序表上進(jìn)行插入操作大約需要移動(dòng)表中一半的數(shù)據(jù)元素，顯然該算法的時(shí)間復(fù)雜度為O(n)。

4.線性表的刪除運(yùn)算

線性表的刪除運(yùn)算是指將表的第i（1≤i≤n）個(gè)元素從線性表中去掉，刪除后使原來長度為n的線性表：

（a1，…，ai－1，ai，…，an）

變成長度為n-1的線性表：（a1，…，ai－1，ai＋1，…，an）

首先舉一個(gè)例子來說明如何在順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除一個(gè)元素。

例如，圖1-6a為一個(gè)長度為8的線性表順序存儲(chǔ)在長度為10的存儲(chǔ)空間中。現(xiàn)在要求刪除線性表中的第1個(gè)元素（即刪除元素26）。其刪除過程如下：

從第2個(gè)元素開始直到最后一個(gè)元素，將其中的每一個(gè)元素均依次往前移動(dòng)一個(gè)位置。此時(shí)，線性表的長度變成了7，如圖1-6b所示。

如果要再刪除線性表的第6個(gè)元素，則采用類似的方法：將第7個(gè)元素往前移動(dòng)一個(gè)位置。此時(shí)，線性表的長度變成了6，如圖1-6c所示

一般來說，設(shè)長度為n的線性表為

（a1，…，ai－1，ai，…，an）

現(xiàn)要?jiǎng)h除表中的第i個(gè)元素，刪除后得到長度為n-1的線性表為

（a1′，a2′，…，aj′，…，an-1′）

則刪除前后的兩線性表中的元素滿足如下關(guān)系：

在一般情況下，在刪除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開始，直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)束后，線性表的長度就減小了1。

下面分析刪除算法的時(shí)間復(fù)雜度。與插入運(yùn)算相同，其時(shí)間主要花費(fèi)在了數(shù)據(jù)的移動(dòng)上，當(dāng)刪除第i個(gè)位置時(shí)，從ai+1到an都要向前移動(dòng)一個(gè)位置，共需要移動(dòng)n-i個(gè)元素，而i的取值范圍為1≤i≤n，即有n個(gè)位置可以刪除。假設(shè)在第i個(gè)位置上做刪除操作的概率為pi，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)為：

在等概率情況下，pi=1/n，則：

這說明，在順序表上進(jìn)行刪除操作時(shí)大約需要移動(dòng)表中一半的元素，顯然該算法的時(shí)間復(fù)雜度也是O(n)。

1.1.4 棧和隊(duì)列

棧和隊(duì)列是兩種特殊的線性結(jié)構(gòu)。從數(shù)據(jù)結(jié)構(gòu)的角度看，它們是線性表。從操作的角度看，它們是操作受限的線性表。在日常生活中經(jīng)常會(huì)遇到棧或隊(duì)列的實(shí)例，另外棧和隊(duì)列還廣泛應(yīng)用于各種軟件系統(tǒng)中。

1.棧及其基本運(yùn)算

棧實(shí)際上也是線性表，是一種特殊的線性表。這種特殊的線性表的插入與刪除運(yùn)算都只能在表的一端進(jìn)行。即在這種線性表的結(jié)構(gòu)中，一端是封閉的，不允許進(jìn)行插入與刪除元素；另一端是開口的，允許插入與刪除元素。在順序存儲(chǔ)結(jié)構(gòu)下，對(duì)這種類型線性表的插入與刪除運(yùn)算是不需要移動(dòng)表中其他數(shù)據(jù)元素的。這種線性表稱為棧。

棧（stack）是限定在一端進(jìn)行插入與刪除的線性表。在棧中，允許插入與刪除的一端稱為棧頂（top），而不允許插入與刪除的另一端稱為棧底（bottom），如圖1-7所示。當(dāng)表中沒有元素時(shí)稱為空棧。

假設(shè)棧S=（al，a2，a3，…，an），則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…，an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。棧頂總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才被刪除的元素。即棧是按照“先進(jìn)后出”（First In Last Out，F(xiàn)ILO）或“后進(jìn)先出”（Last In First Out，LIFO）的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。由此可以看出，棧具有記憶作用。

向棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素（即刪除棧頂元素）稱為退棧運(yùn)算。棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。

棧這種數(shù)據(jù)結(jié)構(gòu)在日常生活中也是常見的。例如，子彈夾是一種棧結(jié)構(gòu)，最后壓入的子彈總是最先被彈出，而最先被壓入的子彈最后才能被彈出。又如，在用羽毛球筒（一端為封閉另一端為開口的容器）裝羽毛球時(shí)，也是遵循“先進(jìn)后出”或“后進(jìn)先出”原則的。

2.棧的順序存儲(chǔ)及其運(yùn)算

與一般線性表一樣，在程序設(shè)計(jì)語言中，用一維數(shù)組作為棧的順序存儲(chǔ)空間。通常，棧底指針指向棧空間的低地址一端（即數(shù)組的起始地址這一端）。圖1-8a是容量為10的棧順序存儲(chǔ)空間，棧中已有6個(gè)元素；圖1-8b與圖1-8c分別為入棧與退棧后的狀態(tài)。在棧的順序存儲(chǔ)空間中，bottom通常為棧底元素，top通常為棧頂元素。top=0表示棧空。

棧的操作主要有入棧運(yùn)算、退棧運(yùn)算（出棧）和讀棧頂元素。

1）入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂指針加1（即top加1），然后將新元素插入棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說明棧空間已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧“上溢”錯(cuò)誤。

2）退棧運(yùn)算：退棧是指取出棧頂元素并賦給一個(gè)指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂元素（棧頂指針指向的元素）賦給一個(gè)指定的變量，然后將棧頂指針減1（即top減1）。當(dāng)棧頂指針為0時(shí)，說明棧空，不可進(jìn)行退棧操作。這種情況稱為棧的“下溢”錯(cuò)誤。

3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。必須注意，這個(gè)運(yùn)算不刪除棧頂元素，只是將它賦給一個(gè)變量，因此棧頂指針不會(huì)改變。當(dāng)棧頂指針為0時(shí)，說明棧空，讀不到棧頂元素。

3.什么是隊(duì)列

在計(jì)算機(jī)系統(tǒng)中，如果一次只能執(zhí)行一個(gè)程序，則在多個(gè)用戶程序需要執(zhí)行時(shí)，這些用戶程序必須按照到來的順序進(jìn)行排隊(duì)等待。這通常是由計(jì)算機(jī)操作系統(tǒng)來管理的。

在操作系統(tǒng)中，用一個(gè)線性表來組織管理用戶程序的排隊(duì)執(zhí)行，原則是：

1）初始時(shí)線性表為空。

2）當(dāng)有用戶程序來到時(shí)，將該用戶程序加入線性表的末尾進(jìn)行等待。

3）當(dāng)計(jì)算機(jī)系統(tǒng)執(zhí)行完當(dāng)前的用戶程序后，就從線性表的頭部取出一個(gè)用戶程序執(zhí)行。

由這個(gè)例子可以看出，在這種線性表中，需要加入的元素總是插入線性表的末尾，并且又總是從線性表的頭部取出（刪除）元素。這種線性表稱為隊(duì)列。

隊(duì)列（queue）是指允許在一端插入，而在另一端刪除的線性表。允許插入的一端叫做隊(duì)尾，通常用一個(gè)稱為尾指針（rear）的指針指向隊(duì)尾元素，即尾指針總是指向最后被插入的元素；允許刪除的一端叫做隊(duì)頭（也稱為排頭），通常也用一個(gè)隊(duì)頭指針（front）指向隊(duì)頭元素的前一個(gè)位置。顯然，在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先被刪除，反之，最后插入的元素最后才被刪除。因此隊(duì)列又稱為“先進(jìn)先出”（First In First Out，F(xiàn)IFO）或后進(jìn)后出（Last In Last Out，LILO）的線性表。它體現(xiàn)了“先來先服務(wù)”的原則。在隊(duì)列中，隊(duì)尾指針rear與隊(duì)頭指針front共同反映了隊(duì)列中元素動(dòng)態(tài)變化的情況。當(dāng)隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。圖1-9是具有4個(gè)元素的隊(duì)列示意圖。

向隊(duì)列的隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算，從隊(duì)列的隊(duì)頭刪除一個(gè)元素稱為出隊(duì)運(yùn)算。

圖1-10是在隊(duì)列中進(jìn)行插入與刪除的示意圖。由圖1-10可以看出，在隊(duì)列的末尾插入一個(gè)元素（入隊(duì)運(yùn)算）只涉及隊(duì)尾指針rear的變化，刪除隊(duì)列中的隊(duì)頭元素（出隊(duì)運(yùn)算）只涉及隊(duì)頭指針front的變化。

與棧類似，在程序設(shè)計(jì)語言中，用一維數(shù)組作為隊(duì)列的順序存儲(chǔ)空間。

4.循環(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)狀空間，供隊(duì)列循環(huán)使用，如圖1-11所示。

在循環(huán)隊(duì)列結(jié)構(gòu)中，當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用而再要進(jìn)行入隊(duì)運(yùn)算時(shí)，只要存儲(chǔ)空間的第一個(gè)位置空閑，便可將元素加入第一個(gè)位置，即將存儲(chǔ)空間的第一個(gè)位置作為隊(duì)尾。

在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置。因此，從隊(duì)頭指針front指向的后一個(gè)位置到隊(duì)尾指針rear指向的位置之間的所有元素均為隊(duì)列中的元素。

循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m，如圖1-11所示。

循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與出隊(duì)運(yùn)算。

每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就進(jìn)1。當(dāng)隊(duì)尾指針rear=m+1時(shí)，則置rear=1。

每進(jìn)行一次出隊(duì)運(yùn)算，隊(duì)頭指針就進(jìn)1。當(dāng)隊(duì)頭指針front=m+1時(shí)，則置front=1。

圖1-12a是一個(gè)容量為8的循環(huán)隊(duì)列存儲(chǔ)空間，且其中已有6個(gè)元素。圖1-12b是在圖1-12a的循環(huán)隊(duì)列中又加入了2個(gè)元素后的狀態(tài)。圖1-12c是在圖1-12b的循環(huán)隊(duì)列中退出了1個(gè)元素后的狀態(tài)。

由圖1-12中循環(huán)隊(duì)列動(dòng)態(tài)變化的過程可以看出，在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1，向前移動(dòng)。只不過當(dāng)頭尾指針指向向量上界（m）時(shí)，其加1操作的結(jié)果是指向向量的下界0。

由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，無法通過front=rear來判斷隊(duì)列是“空”還是“滿”。在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)列是滿還是空，通常還需增加一個(gè)標(biāo)志s，定義如下：當(dāng)s=0時(shí)，表示隊(duì)列空；當(dāng)s=1時(shí)，表示隊(duì)列非空。

由此可以得出隊(duì)列空與隊(duì)列滿的條件如下：

隊(duì)列空的條件為s=0；

隊(duì)列滿的條件為s=1且front=rear。

下面具體介紹循環(huán)隊(duì)列入隊(duì)與出隊(duì)的運(yùn)算。

假設(shè)循環(huán)隊(duì)列的初始狀態(tài)為空，即s=0，且front=rear=m。

（1）入隊(duì)運(yùn)算

入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。首先將隊(duì)尾指針進(jìn)1（即rear=rear+1），且當(dāng)rear=m+l時(shí)，置rear=1；然后將新元素插入隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空（s=l），且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”。

（2）出隊(duì)運(yùn)算

出隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)頭位置退出一個(gè)元素并賦給指定的變量。首先將隊(duì)頭指針進(jìn)1（即front=front+1），且當(dāng)front=m+1時(shí)，置front=1；然后將隊(duì)頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行出隊(duì)運(yùn)算，這種情況稱為“下溢”。

（3）求隊(duì)列長度

求隊(duì)列長度是指求出當(dāng)前循環(huán)隊(duì)列中存儲(chǔ)元素的個(gè)數(shù)。在循環(huán)隊(duì)列中，存儲(chǔ)空間可以重復(fù)利用，隨著入隊(duì)和出隊(duì)運(yùn)算的操作，隊(duì)頭指針和隊(duì)尾指針的位置不斷變化，可能會(huì)出現(xiàn)隊(duì)尾指針小于隊(duì)頭指針的情況，所以在循環(huán)隊(duì)列中，計(jì)算所存儲(chǔ)的元素個(gè)數(shù)分兩種情況：

1）當(dāng)隊(duì)尾指針大于隊(duì)頭指針時(shí)：

隊(duì)列中的元素個(gè)數(shù)為（rear-front），如圖1-13a所示。

2）當(dāng)隊(duì)尾指針小于隊(duì)頭指針時(shí)：

隊(duì)列中的元素個(gè)數(shù)為（rear-front+m）%m，其中，m為循環(huán)隊(duì)列的容量，如圖1-13b所示。

1.1.5 線性鏈表

前面主要討論了線性表的順序存儲(chǔ)結(jié)構(gòu)以及在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算。本節(jié)主要介紹線性鏈表的存儲(chǔ)方式和基本操作。

1.線性表

線性表的順序存儲(chǔ)結(jié)構(gòu)具有簡單、運(yùn)算方便的優(yōu)點(diǎn)，特別是對(duì)于小線性表或長度固定的線性表，采用順序存儲(chǔ)結(jié)構(gòu)的優(yōu)越性更為突出。但是，線性表的順序存儲(chǔ)結(jié)構(gòu)在某些情況下就不那么方便，運(yùn)算效率不那么高了。實(shí)際上，線性表的順序存儲(chǔ)結(jié)構(gòu)存在以下幾方面的缺點(diǎn)：

1）在一般情況下，要在順序存儲(chǔ)的線性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)，為了保證插入或刪除后的線性表仍然為順序存儲(chǔ)，則在插入和刪除過程中需要移動(dòng)大量的數(shù)據(jù)元素。對(duì)于大的線性表，特別是在元素插入或刪除很頻繁的情況下，采用順序存儲(chǔ)結(jié)構(gòu)是很不方便的，插入與刪除運(yùn)算的效率都很低。

2）當(dāng)為一個(gè)線性表分配順序存儲(chǔ)空間后，在線性表的存儲(chǔ)空間已滿，但還需要插入新的元素時(shí)，就會(huì)發(fā)生“上溢”錯(cuò)誤。在這種情況下，如果在原線性表的存儲(chǔ)空間后找不到與之連續(xù)的可用空間，則會(huì)導(dǎo)致運(yùn)算的失敗或中斷。顯然這種情況的出現(xiàn)對(duì)運(yùn)算是很不利的。也就是說，在順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充。

3）在實(shí)際應(yīng)用中，往往是同時(shí)有多個(gè)線性表共享計(jì)算機(jī)的存儲(chǔ)空間。例如，在一個(gè)處理中，可能要用到若干線性表（包括棧與隊(duì)列）。在這種情況下，存儲(chǔ)空間的分配將是一個(gè)難題。如果將存儲(chǔ)空間平均分配給各線性表，則有可能造成有的線性表的空間不夠用，而有的線性表的空間根本用不著或用不滿，這就使得在有的線性表空間無用而處于空閑的情況下，另外一些線性表的操作由于“上溢”而無法進(jìn)行。這種情況實(shí)際上是計(jì)算機(jī)的存儲(chǔ)空間得不到充分利用。如果多個(gè)線性表共享存儲(chǔ)空間，對(duì)每一個(gè)線性表的存儲(chǔ)空間進(jìn)行動(dòng)態(tài)分配，則為了保證每一個(gè)線性表的存儲(chǔ)空間連續(xù)且順序分配，會(huì)導(dǎo)致在對(duì)某個(gè)線性表進(jìn)行動(dòng)態(tài)分配存儲(chǔ)空間時(shí)，必須移動(dòng)其他線性表中的數(shù)據(jù)元素。這就是說，線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間進(jìn)行動(dòng)態(tài)分配。

由于線性表的順序存儲(chǔ)結(jié)構(gòu)存在以上缺點(diǎn)，因此，對(duì)于大的線性表，特別是元素變動(dòng)頻繁的大線性表，不宜采用順序存儲(chǔ)結(jié)構(gòu)，而是采用下面將要介紹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

2.線性鏈表

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。

假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。

線性表的鏈?zhǔn)酱鎯?chǔ)是用一組任意的存儲(chǔ)單元來依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了適應(yīng)這種存儲(chǔ)結(jié)構(gòu)，計(jì)算機(jī)存儲(chǔ)空間被劃分為一個(gè)一個(gè)小塊，每一個(gè)小塊占若干字節(jié)，通常稱這些小塊為存儲(chǔ)結(jié)點(diǎn)。

為了存儲(chǔ)線性表中的每一個(gè)元素并且能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，一方面要存儲(chǔ)數(shù)據(jù)元素的值，另一方面要存儲(chǔ)各數(shù)據(jù)元素之間的前后件關(guān)系。為此，將存儲(chǔ)空間中的每一個(gè)結(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)（即存儲(chǔ)結(jié)點(diǎn)的地址），即指向后件元素，稱為指針域。線性表的鏈?zhǔn)酱鎯?chǔ)中存儲(chǔ)一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)結(jié)構(gòu)如圖1-14表示，存儲(chǔ)線性表中所有數(shù)據(jù)元素的存儲(chǔ)空間結(jié)構(gòu)如圖1-15所示。

由此可知，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)元素所需空間比線性表的順序存儲(chǔ)結(jié)構(gòu)所需空間要多，多出的部分即是用來存放后件元素地址的，而線性表的順序存儲(chǔ)結(jié)構(gòu)中只需數(shù)據(jù)元素的值，不需要存儲(chǔ)數(shù)據(jù)元素后件元素的地址，從而節(jié)省存儲(chǔ)空間。

在線性鏈表中，用一個(gè)專門的指針HEAD指向線性鏈表的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)（即存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)點(diǎn)的序號(hào)）。線性表中最后一個(gè)元素沒有后件，因此，線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨ㄓ肗ULL或0表示），表示鏈表終止。鏈表通過每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起，其邏輯結(jié)構(gòu)如圖1-16所示。

由于上述鏈表的每一個(gè)結(jié)點(diǎn)只有一個(gè)鏈域，所以將這種鏈表稱為單鏈表（single linked）或線性鏈表。

下面舉一個(gè)例子來說明線性鏈表的存儲(chǔ)結(jié)構(gòu)。

設(shè)線性表為（a1，a2，a3，a4），其存儲(chǔ)空間具有10個(gè)存儲(chǔ)結(jié)點(diǎn)，該線性表在存儲(chǔ)空間中的存儲(chǔ)情況如圖1-17a所示。為了直觀地表示該線性鏈表中各元素之間的前后件關(guān)系，還可以用如圖1-17b所示的邏輯狀態(tài)來表示，其中每一個(gè)結(jié)點(diǎn)上面的數(shù)字表示該結(jié)點(diǎn)的存儲(chǔ)序號(hào)（簡稱結(jié)點(diǎn)號(hào)）。

一般來說，在線性鏈表中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來指示的，指向線性中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為頭指針，當(dāng)HEAD=NULL（或0）時(shí)稱為空表。對(duì)于線性鏈表可以從頭指針開始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。但是由這個(gè)指針只能找到后件結(jié)點(diǎn)，不能找到前件結(jié)點(diǎn)。因此，在這種線性鏈表中，只能順指針向鏈尾方向掃描，這會(huì)給某些問題的處理帶來不便，因?yàn)樵谶@種鏈接方式下，由某一個(gè)結(jié)點(diǎn)出發(fā)，只能找到它的后件，而為了找出它的前件，必須從頭指針開始重新尋找。

為了彌補(bǔ)線性單鏈表的這個(gè)缺點(diǎn)，在某些應(yīng)用中，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，用以指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針，用以指向其后件結(jié)點(diǎn)。這樣的線性鏈表稱為雙向鏈表，其邏輯狀態(tài)如圖1-18所示。

3.帶鏈的棧

棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。圖1-19是棧在鏈?zhǔn)酱鎯?chǔ)時(shí)的邏輯狀態(tài)示意圖。

在實(shí)際應(yīng)用中，帶鏈的棧可以用來收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。由于可利用棧鏈接了計(jì)算機(jī)存儲(chǔ)空間中的所有空閑結(jié)點(diǎn)，因此，當(dāng)計(jì)算機(jī)系統(tǒng)或用戶程序需要存儲(chǔ)結(jié)點(diǎn)時(shí)，就可以從中取出棧頂結(jié)點(diǎn)，如圖1-20a所示，當(dāng)計(jì)算機(jī)系統(tǒng)或用戶釋放一個(gè)存儲(chǔ)結(jié)點(diǎn)（該元素從表中刪除）時(shí)，則要將該結(jié)點(diǎn)放回到可利用棧的棧頂，如圖1-20b所示。由此可知，計(jì)算機(jī)中的所有可利用空間都可以以結(jié)點(diǎn)為單位鏈接在可利用棧中。隨著其他線性鏈表中結(jié)點(diǎn)的插入與刪除，可利用棧處于動(dòng)態(tài)變化之中，即可利用棧經(jīng)常要進(jìn)行退棧與入棧操作。

4.帶鏈的隊(duì)列

與棧類似，隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。圖1-21a是隊(duì)列在鏈?zhǔn)酱鎯?chǔ)時(shí)的邏輯狀態(tài)示意圖。圖1-21b是將新結(jié)點(diǎn)p插入隊(duì)列的示意圖。圖1-21c是將隊(duì)頭結(jié)點(diǎn)p退出隊(duì)列的示意圖。

5.在線性鏈表中查找指定元素

線性鏈表的運(yùn)算包括在線性鏈表中指定元素結(jié)點(diǎn)之前插入元素、在線性鏈表中刪除指定元素、將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表、將一個(gè)線性鏈表按要求進(jìn)行分解、逆轉(zhuǎn)線性鏈表、復(fù)制線性鏈表、線性鏈表的排序與查找。

在對(duì)線性鏈表進(jìn)行插入或刪除的運(yùn)算中，首先需要找到插入或刪除的位置，這就需要對(duì)線性鏈表進(jìn)行掃描查找，在線性鏈表中尋找包含指定元素的前一個(gè)結(jié)點(diǎn)。當(dāng)找到包含指定元素的前一個(gè)結(jié)點(diǎn)后，就可以在該結(jié)點(diǎn)后插入新結(jié)點(diǎn)或刪除該結(jié)點(diǎn)后的一個(gè)結(jié)點(diǎn)。

在非空線性鏈表中，尋找包含指定元素x的前一個(gè)結(jié)點(diǎn)p的基本方法是：從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止。

因此，使用這種方法找到的結(jié)點(diǎn)p有兩種可能：

1）當(dāng)線性鏈表中存在包含元素x的結(jié)點(diǎn)時(shí)，找到的p為第一次遇到的包含元素x的前一個(gè)結(jié)點(diǎn)序號(hào)。

2）當(dāng)線性鏈表中不存在包含元素x的結(jié)點(diǎn)時(shí)，找到的p為線性鏈表中的最后一個(gè)結(jié)點(diǎn)序號(hào)。

6.線性鏈表的插入

線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中插入一個(gè)新元素。

為了要在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè)新結(jié)點(diǎn)，以便于存儲(chǔ)該元素的值。新結(jié)點(diǎn)可以從可利用棧中取得，然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。

假設(shè)可利用棧與線性鏈表如圖1-22a所示。現(xiàn)在要在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入一個(gè)新元素b。其插入過程如下：

1）從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p（即取得結(jié)點(diǎn)的存儲(chǔ)序號(hào)存放在變量p中），并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲。經(jīng)過這一步后，可利用棧的狀態(tài)1-22b所示。

2）在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為q。線性鏈表如圖1-22b所示。

3）最后將結(jié)點(diǎn)p插入結(jié)點(diǎn)q之后。為了實(shí)現(xiàn)這一步，只要改變以下兩個(gè)結(jié)點(diǎn)的指針域內(nèi)容：

①使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)（即結(jié)點(diǎn)q的后件結(jié)點(diǎn)）。

②使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p。

這一步的結(jié)果如圖1-22c所示。此時(shí)插入完成。

由線性鏈表的插入過程可以看出，由于插入的新結(jié)點(diǎn)取自可利用棧，因此，只要可利用棧不空，在線性鏈表插入時(shí)總能取到存儲(chǔ)插入元素的新結(jié)點(diǎn)，不會(huì)發(fā)生“上溢”的情況。而且，由于可利用棧是公用的，多個(gè)線性鏈表可以共享它，從而很方便地實(shí)現(xiàn)了存儲(chǔ)空間的動(dòng)態(tài)分配。另外，線性鏈表在插入過程中不發(fā)生數(shù)據(jù)元素移動(dòng)的現(xiàn)象，只要改變有關(guān)結(jié)點(diǎn)的指針即可，從而提高了插入的效率。

7.線性鏈表的刪除

線性鏈表的刪除是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。

為了要在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，然后將要?jiǎng)h除結(jié)點(diǎn)放回可利用棧。

假設(shè)可利用棧與線性鏈表如圖1-23a所示。現(xiàn)在要在線性鏈表中刪除包含元素x的結(jié)點(diǎn)，其刪除過程如下：

1）在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為q。

2）將結(jié)點(diǎn)q后的結(jié)點(diǎn)p從線性鏈表中刪除，即讓結(jié)點(diǎn)q的指針指向包含元素x的結(jié)點(diǎn)p的指針指向的結(jié)點(diǎn)。

經(jīng)過上述兩步后，線性鏈表如1-23b所示。

3）將包含元素x的結(jié)點(diǎn)p送回可利用棧。經(jīng)過這一步后，可利用棧的狀態(tài)如圖1-23c所示。此時(shí)線性鏈表的刪除完成。

從線性鏈表的刪除過程可以看出，從線性鏈表中刪除一個(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結(jié)點(diǎn)，應(yīng)將空閑結(jié)點(diǎn)送回可利用棧。

8.循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算

在前面所討論的線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問題，在運(yùn)算過程中，對(duì)空表和第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，這使得空表與非空表的運(yùn)算不統(tǒng)一。

因此，可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存儲(chǔ)空間，僅對(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)，而且沒有增加額外的存儲(chǔ)空間，滿足這樣條件的鏈表叫做循環(huán)鏈表（circular linked list）。

循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個(gè)特點(diǎn)：

1）在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(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)狀鏈。

圖1-24是循環(huán)鏈表的示意圖。其中圖1-24a是一個(gè)非空的循環(huán)鏈表，圖1-24b是一個(gè)空的循環(huán)鏈表。在此，空表與非空表是針對(duì)線性表中的元素而言的。

在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)。由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表的運(yùn)算統(tǒng)一。

循環(huán)鏈表的插入和刪除與線性單鏈表基本相同。但由循環(huán)鏈表的特點(diǎn)可以看出，在對(duì)循環(huán)鏈表進(jìn)行插入和刪除的過程中，實(shí)現(xiàn)了空表與非空表的運(yùn)算統(tǒng)一。

1.1.6 樹與二叉樹

樹（tree）是一種簡單的非線性結(jié)構(gòu)。在樹中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。圖1-25為一棵樹的示例。由圖1-25可以看出，用圖形表示的這種數(shù)據(jù)結(jié)構(gòu)，很像自然界中的樹，只不過是一棵倒長的樹，因此，這種數(shù)據(jù)結(jié)構(gòu)就用“樹”來命名。

1.樹的基本概念

樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。若n=0，稱為空樹；若n>0，則：

1）有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)。它只有直接后件，但沒有直接前件。

2）除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn)可以劃分為m（m≥0）個(gè)互不相交的有限集合T0，T1，…，Tm－1，每個(gè)集合Ti（i=0，1，…，m-l）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前件，但可以有0個(gè)或多個(gè)直接后件。

在樹的圖形表示中，總是認(rèn)為在用直線連起來的兩端結(jié)點(diǎn)中，上端結(jié)點(diǎn)是前件，下端結(jié)點(diǎn)是后件，這樣，表示前后件關(guān)系的箭頭就可以省略。

在現(xiàn)實(shí)世界中，能用樹這種數(shù)據(jù)結(jié)構(gòu)表示的例子很多。例如，圖1-26中的樹表示了學(xué)校行政關(guān)系結(jié)構(gòu)；圖1-27中的樹反映了一本書的層次結(jié)構(gòu)。

由于樹具有明顯的層次關(guān)系，因此，具有層次關(guān)系的數(shù)據(jù)都可以用樹這種數(shù)據(jù)結(jié)構(gòu)來描述。在所有的層次關(guān)系中，人們最熟悉的是血緣關(guān)系，按血緣關(guān)系可以很直觀地理解樹結(jié)構(gòu)中各數(shù)據(jù)元素結(jié)點(diǎn)之間的關(guān)系，因此，在描述樹結(jié)構(gòu)時(shí)，也經(jīng)常使用血緣關(guān)系中的一些術(shù)語。

下面介紹樹中的一些基本特征，同時(shí)介紹有關(guān)樹結(jié)構(gòu)的基本術(shù)語。

在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱為樹的根。例如，在圖1-25中，結(jié)點(diǎn)A是樹的根結(jié)點(diǎn)。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。例如，在圖1-25中，結(jié)點(diǎn)C、D、E、F、H、I均為葉子結(jié)點(diǎn)。

在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。在樹中，所有結(jié)點(diǎn)中最大的度稱為樹的度。例如，在圖1-25中，根結(jié)點(diǎn)A和結(jié)點(diǎn)G的度為2，結(jié)點(diǎn)B的度為3，葉子結(jié)點(diǎn)C、D、E、F、H、I的度為0，在此樹中，結(jié)點(diǎn)B的度最大為3，所以此樹的度為3。

樹是一種具有明顯層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)。在樹結(jié)構(gòu)中，一般按如下原則分層：

根結(jié)點(diǎn)在第1層。

同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)都在下一層。例如，在圖1-25中，根結(jié)點(diǎn)A在第1層；結(jié)點(diǎn)B、F、G在第2層；結(jié)點(diǎn)C、D、E、H、I在第3層。

樹的最大層次稱為樹的深度。例如，圖1-25的樹的深度為3。

在樹中，以某一結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹稱為該結(jié)點(diǎn)的一棵子樹。例如，在圖1-25中，結(jié)點(diǎn)A有3棵子樹，它們分別以結(jié)點(diǎn)B、F、G為根結(jié)點(diǎn)；結(jié)點(diǎn)B有3棵子樹，它們分別以結(jié)點(diǎn)C、D、E為根結(jié)點(diǎn)；結(jié)點(diǎn)G有2棵子樹，它們分別以結(jié)點(diǎn)H、I為根結(jié)點(diǎn)。在樹中，葉子結(jié)點(diǎn)沒有子樹，如結(jié)點(diǎn)C、D、E、F、H、I。

若將樹中任意結(jié)點(diǎn)的子樹均看成是從左到右有次序的，不能隨意交換，則稱該樹是有序樹；否則稱為無序樹。

2.二叉樹的基本性質(zhì)

二叉樹（binary tree）是一種很有用的非線性結(jié)構(gòu)。二叉樹不同于前面介紹的樹結(jié)構(gòu)，但它與樹結(jié)構(gòu)相似，并且，樹結(jié)構(gòu)的所有術(shù)語都可以用到二叉樹上。

二叉樹由n（≥0）個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹，如圖1-28b所示。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹具有如下兩個(gè)特點(diǎn)：

1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)，如圖1-28a所示。

2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。

在二叉樹中，一個(gè)結(jié)點(diǎn)可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當(dāng)一個(gè)結(jié)點(diǎn)既沒有左子樹也沒有右子樹時(shí)，該結(jié)點(diǎn)即葉子結(jié)點(diǎn)。

性質(zhì)1：在二叉樹的第k層上至多有2k-1（k≥1）個(gè)結(jié)點(diǎn)。

根據(jù)二叉樹的特點(diǎn)，這個(gè)性質(zhì)是顯然的。

性質(zhì)2：深度為m的二叉樹至多有2m-1個(gè)結(jié)點(diǎn)。

深度為m的二叉樹是指二叉樹共有m層。根據(jù)性質(zhì)1，只要將第1層到第m層上的最大的結(jié)點(diǎn)數(shù)相加，就可以得到整個(gè)二叉樹中結(jié)點(diǎn)數(shù)的最大值，即

21-1+22-1+…+2m-1=2m-1

性質(zhì)3：對(duì)于任何一棵二叉樹，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。

對(duì)這個(gè)性質(zhì)說明如下：

假設(shè)二叉樹中有n0個(gè)葉子結(jié)點(diǎn)，n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，則二叉樹中總的結(jié)點(diǎn)數(shù)為

n=n0+n1+n2 （1）

由于在二叉樹中除了根結(jié)點(diǎn)外，其余每一個(gè)結(jié)點(diǎn)都有唯一的一個(gè)分支進(jìn)入。設(shè)二叉樹中所有進(jìn)入分支的總數(shù)為m，則二叉樹中總的結(jié)點(diǎn)數(shù)為

n=m+1 （2）

又由于二叉樹中這m個(gè)進(jìn)入分支是分別由非葉子結(jié)點(diǎn)發(fā)出的。其中度為1的每個(gè)結(jié)點(diǎn)發(fā)出1個(gè)分支，度為2的每個(gè)結(jié)點(diǎn)發(fā)出2個(gè)分支。因此，二叉樹中所有度為1與度為2的結(jié)點(diǎn)發(fā)出的分支總數(shù)為n1+2n2。而在二叉樹中，總的發(fā)出分支數(shù)應(yīng)與總的進(jìn)入分支數(shù)相等，即

m=n1+2n2 （3）

將（3）第代入（2）式有

n=n1+2n2+1 （4）

最后比較（1）式和（4）式有

化簡后得

n0=n2+1

即在二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。

例如，在圖1-28所示的二叉樹中，有3個(gè)葉子結(jié)點(diǎn)，有2個(gè)度為2的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè)。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度至少為[log2n]+1，其中[log2n]表示log2n的整數(shù)部分。

這個(gè)性質(zhì)可以由性質(zhì)2直接得到。

3.滿二叉樹與完全二叉樹

滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。

1）滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。例如，圖1-29a、圖1-29b、圖1-29c分別是深度為2、3、4的滿二叉樹。這就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。

2）完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；最后一層只缺少右邊的若干結(jié)點(diǎn)，如圖1-30a、b所示。更確切地說，如果從根結(jié)點(diǎn)起，對(duì)二叉樹的結(jié)點(diǎn)自上而下、自左至右由自然數(shù)進(jìn)行連續(xù)編號(hào)，則深度為m，且有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹中編號(hào)從1～n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。也就是說，一棵具有n個(gè)結(jié)點(diǎn)的深度為k的完全二叉樹，它的每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)為1～n的結(jié)點(diǎn)一一對(duì)應(yīng)。

對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)：對(duì)于任何一個(gè)結(jié)點(diǎn)，若其左右分支下的子孫結(jié)點(diǎn)的最大層次為p，則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜，或?yàn)閜+1。

由滿二叉樹與完全二叉樹的特點(diǎn)可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。

完全二叉樹還具有以下兩個(gè)性質(zhì)：

性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為[log2n]+1或[log2(n+1)]。

性質(zhì)6：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（從第1層到第[log2n]+1層，每層從左到右），則對(duì)于任意結(jié)點(diǎn)i（1≤i≤n），有：

1）如果i=1，則結(jié)點(diǎn)i無雙親，是二叉樹的根；如果i>1，則其雙親是結(jié)點(diǎn)[i/2]。

2）如果2i>n，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；否則，其左孩子是結(jié)點(diǎn)2i。

3）如果2i+1>n，則結(jié)點(diǎn)i無右孩子；否則，其右孩子是結(jié)點(diǎn)2i+1。

根據(jù)完全二叉樹的這個(gè)性質(zhì)，如果按從上到下，從左到右順序存儲(chǔ)完全二叉樹的各結(jié)點(diǎn)，則很容易確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的位置。

4.二叉樹的存儲(chǔ)結(jié)構(gòu)

在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域。但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件（兩個(gè)子結(jié)點(diǎn)），因此，用于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域；另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。圖1-31為二叉樹存儲(chǔ)結(jié)點(diǎn)示意圖

在圖1-31中，L(i)為結(jié)點(diǎn)i的左指針域，即L(i)為結(jié)點(diǎn)i的左子結(jié)點(diǎn)的存儲(chǔ)地址；R(i)為結(jié)點(diǎn)i的右指針域，即R(i)為結(jié)點(diǎn)i的右子結(jié)點(diǎn)的存儲(chǔ)地址；V(i)為數(shù)據(jù)域。

由于二叉樹存儲(chǔ)結(jié)構(gòu)中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域，因此，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表。圖1-32a、圖1-32b、圖1-32c分別表示了一棵二叉樹、二叉鏈表的邏輯狀態(tài)、二叉鏈表的物理狀態(tài)。其中BT稱為二叉鏈表的頭指針，用于指向二叉樹根結(jié)點(diǎn)（即存放二叉樹根結(jié)點(diǎn)的存儲(chǔ)地址）

對(duì)于滿二叉樹與完全二叉樹來說，根據(jù)完全二叉樹的性質(zhì)6，可以按層次進(jìn)行順序存儲(chǔ)，這樣，不僅節(jié)省了存儲(chǔ)空間，又能方便地確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)與左右子結(jié)點(diǎn)的位置，但順序存儲(chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹不適用。

5.二叉樹的遍歷

所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪問一次。

由于二叉樹是一種非線性結(jié)構(gòu)，因此，對(duì)二叉樹的遍歷要比遍歷線性表復(fù)雜得多。在遍歷二叉樹的過程中，當(dāng)訪問到某個(gè)結(jié)點(diǎn)時(shí)，再往下訪問可能有兩個(gè)分支，那么先訪問哪一個(gè)分支呢？對(duì)于二叉樹來說，需要訪問根結(jié)點(diǎn)、左子樹上的所有結(jié)點(diǎn)、右子樹上的所有結(jié)點(diǎn)，在這三者中，究竟先訪問哪一個(gè)？也就是說，遍歷二叉樹的方法實(shí)際上是要確定訪問各結(jié)點(diǎn)的順序，以便不重不漏地訪問到二叉樹中的所有結(jié)點(diǎn)。

在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為3種：前序遍歷、中序遍歷、后序遍歷。下面分別介紹這3種遍歷的方法。

（1）前序遍歷

前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。因此，前序遍歷二叉樹的過程是一個(gè)遞歸的過程。

下面是二叉樹前序遍歷的簡單描述。

若二叉樹為空，則結(jié)束返回。

否則，1）訪問根結(jié)點(diǎn)；2）前序遍歷左子樹；3）前序遍歷右子樹。

在此特別要注意的是，在遍歷左右子樹時(shí)仍然采用前序遍歷的方法。例如，對(duì)圖1-32a中的二叉樹進(jìn)行前序遍歷，則遍歷的結(jié)果（即前序序列）為A、B、D、E、G、C、F、H、I。

（2）中序遍歷

中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。因此，中序遍歷二叉樹的過程也是一個(gè)遞歸的過程。

下面是二叉樹中序遍歷的簡單描述。

若二叉樹為空，則結(jié)束返回。

否則，1）中序遍歷左子樹；2）訪問根結(jié)點(diǎn)；3）中序遍歷右子樹。

在此也要特別注意的是，在遍歷左右子樹時(shí)，仍然采用中序遍歷的方法。例如，對(duì)圖1-32a中的二叉樹進(jìn)行中序遍歷，則遍歷的結(jié)果（即中序序列）為D、B、G、E、A、H、F、I、C。

（3）后序遍歷

后序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。因此，后序遍歷二叉樹的過程也是一個(gè)遞歸的過程。

下面是二叉樹后序遍歷的簡單描述。

若二叉樹為空，則結(jié)束返回。

否則，1）后序遍歷左子樹；2）后序遍歷右子樹；3）訪問根結(jié)點(diǎn)。

在此也要特別注意的是，在遍歷左右子樹時(shí)仍然采用后序遍歷的方法。例如，對(duì)圖1-32a中的二叉樹進(jìn)行后序遍歷，則遍歷的結(jié)果（即后序序列）為D、G、E、B、H、I、F、C、A。

1.1.7 查找

查找是數(shù)據(jù)處理領(lǐng)域中的一個(gè)重要內(nèi)容，查找的效率將直接影響到數(shù)據(jù)處理的效率。

所謂查找，是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。在查找的過程中，涉及查找的方法等問題，通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法。

1.順序查找

順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法為從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中的所有元素與被查找元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失敗）。

在進(jìn)行順序查找過程中，如果線性表中的第一個(gè)元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找元素是線性表中的最后一個(gè)元素，或者被查找元素根本不在線性表中，則為了查找這個(gè)元素需要與線性表中所有的元素進(jìn)行比較，這是順序查找的最壞情況。在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較。

由此可以看出，對(duì)于大的線性表來說，順序查找的效率是很低的。雖然順序查找的效率不高，但在下列兩種情況下也只能采用順序查找。

1）如果線性表為無序線性表（即表中元素的排列是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)，還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。

2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。

2.二分法查找

二分法查找只適用于順序存儲(chǔ)的有序表。在此所說的有序表是指線性表中的元素按值非遞減（即從小到大，但允許相鄰元素值相等）排列。

設(shè)有序線性表的長度為n，被查元素為x，則對(duì)分查找的方法如下。

將x與線性表的中間項(xiàng)進(jìn)行比較：

●若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束。

●若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找。

●若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。

這個(gè)過程一直進(jìn)行到查找成功或子表長度為0（說明線性表中沒有這個(gè)元素）時(shí)為止。顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多。可以證明，對(duì)于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。

1.1.8 排序

排序也是數(shù)據(jù)處理的重要內(nèi)容。它為數(shù)據(jù)查找操作提供方便，因?yàn)榕判蚝蟮臄?shù)據(jù)在進(jìn)行查找操作時(shí)效率較高。

所謂排序，是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。排序的方法有很多，根據(jù)待排序序列的規(guī)模及對(duì)數(shù)據(jù)處理的要求，可以采用不同的排序方法。在排序技術(shù)方面，主要考查插入排序、選擇排序、冒泡排序、快速排序和堆排序等方法。

1.簡單插入排序

簡單插入排序（straight insertion sort）算法的思路是：初始可認(rèn)為線性表中的第1個(gè)元素已排好序，然后將第2個(gè)元素到第n個(gè)元素依次插入由已排序的元素組成的線性表中。在對(duì)第i個(gè)元素ai進(jìn)行插入時(shí)，a1、a2、…、ai-1已排序，將元素ai與已經(jīng)排好序的元素從右向左依次比較，找到ai應(yīng)插入的位置，將該位置以后直到ai-1各元素順序后移，空出該位置讓ai插入。

例如，使用簡單插入排序?qū)?12、126、272、226、28、165、123共7個(gè)元素按照從小到大排序。簡單插入排序的執(zhí)行過程示意圖如圖1-33所示。圖中畫有方框的元素表示剛被插入有序子表中。

在簡單插入排序中，每一次比較后最多移掉一個(gè)逆序，最壞情況下，需要進(jìn)行n(n-1)/2次比較。

2.希爾排序

希爾排序法（shell sort）屬于插入類排序，但它對(duì)簡單插入排序做了較大的改進(jìn)。

希爾排序法的基本思想如下：

將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序。

子序列的分割方法如下：

將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序過程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn)行一次插入排序，排序就完成。

增量序列一般取ht=n/2k（k=1，2，…，[log2n]），其中n為待排序序列的長度。

例如，使用希爾排序?qū)?、19、24、13、31、8、82、18、44、63、5、29共12個(gè)元素按照從小到大排序。希爾排序的執(zhí)行過程示意圖如圖1-34所示。

在希爾排序過程中，雖然對(duì)于每一個(gè)子表采用的仍是插入排序，但是，在子表中每進(jìn)行一趟比較，就有可能移去整個(gè)線性表中的多個(gè)逆序，從而改善了整個(gè)排序過程的性能。

希爾排序的效率與所選取的增量序列有關(guān)。如果選取上述增量序列，則在最壞的情況下，希爾排序所需要的比較次數(shù)為O(n1.5)。

3.冒泡排序法

冒泡排序法是一種最簡單的交換類排序方法，它通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。

冒泡排序法的基本過程如下：

首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，這樣就消去了一個(gè)逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的大者往后移動(dòng)，最后將線性表中的最大者換到了最后，這也是線性表中最大元素應(yīng)有的位置。

然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的小者往前移動(dòng)，最后就將線性表中的最小者換到了最后，這也是線性表中最小元素應(yīng)有的位置。

對(duì)剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)線性表已經(jīng)變?yōu)橛行颉?/p>

在上述排序過程中，對(duì)線性表的每一次來回掃描后，都將其中的最大者沉到了表的底部，最小者像氣泡一樣冒到表的前頭。冒泡排序由此而得名，且冒泡排序又稱下沉排序。

假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)/2。但這個(gè)工作量不是必需的，一般情況下要小于這個(gè)工作量。

圖1-35是冒泡排序的示意圖。圖中有方框的元素位置表示掃描過程中最后一次發(fā)生交換的位置。由圖1-35可以看出，整個(gè)排序?qū)嶋H上只用了2遍從前往后的掃描和2遍從后往前的掃描就完成。

4.快速排序法

在前面所討論的冒泡排序法中，由于在掃描過程中只對(duì)相鄰兩個(gè)元素進(jìn)行比較，因此，在互換兩個(gè)相鄰元素時(shí)，只能消除一個(gè)逆序。如果通過兩個(gè)（不是相鄰的）元素的交換，能夠消除線性表中的多個(gè)逆序，就會(huì)大大加快排序的速度。顯然，為了通過一次交換消除多個(gè)逆序，就不能像冒泡排序法那樣對(duì)相鄰兩個(gè)元素進(jìn)行比較，因?yàn)檫@只能使相鄰兩個(gè)元素交換，從而只能消除一個(gè)逆序。下面介紹的快速排序法可以實(shí)現(xiàn)通過一次交換而消除多個(gè)逆序。

快速排序法也是一種互換類的排序方法，但由于它比冒泡排序法的速度快，因此稱為快速排序法。

快速排序法的基本思想如下：

從線性表中選取一個(gè)元素，設(shè)為T，將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成了兩部分（稱為兩個(gè)子表），T插入其分界線的位置處，這個(gè)過程稱為線性表的分割。通過對(duì)線性表的一次分割，就以T為分界線，將線性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于T，而后面子表中所有元素均不小于T。

如果對(duì)分割后的子表再按上述原則進(jìn)行分割，并且，這種分割過程可以一直做下去，直到所有子表為空為止，則此時(shí)的線性表就變成了有序表。

由此可知，快速排序法的關(guān)鍵是對(duì)線性表進(jìn)行分割，以及對(duì)各分割出的子表進(jìn)行再分割，這個(gè)過程如圖1-36所示。

在對(duì)線性表或子表進(jìn)行實(shí)際分割時(shí)，可以按如下步驟進(jìn)行：

首先，在表的第一個(gè)、中間一個(gè)與最后一個(gè)元素中選取中間項(xiàng)，設(shè)為P(k)，并將P(k)賦給T，再將表中的第一個(gè)元素移到P(k)的位置上。

然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最后的位置。反復(fù)操作以下兩步：

1）將j逐漸減小，并逐次比較P(j)與T，直到發(fā)現(xiàn)一個(gè)P(j)<T為止，將P(j)移到P(i)的位置上。

2）將i逐漸減小，并逐次比較P(i)與T，直到發(fā)現(xiàn)一個(gè)P(i)>T為止，將其移到P(j)的位置上。

上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一個(gè)位置(即i=j)為止，此時(shí)將T移到P(i)的位置上。

在快速排序過程中，隨著對(duì)各子表不斷地進(jìn)行分割，劃分出的子表會(huì)越來越多，但一次又只能對(duì)一個(gè)子表進(jìn)行再分割處理，需要將暫時(shí)不分割的子表記憶起來，這就要用一個(gè)棧來實(shí)現(xiàn)。在對(duì)某個(gè)子表進(jìn)行分割后，可以將分割出的后一個(gè)子表的第一個(gè)元素與最后一個(gè)元素的位置壓入棧中，而繼續(xù)對(duì)前一個(gè)子表進(jìn)行再分割；當(dāng)分割出的子表為空時(shí)，可以從棧中退出一個(gè)子表（實(shí)際上只是該子表的第一個(gè)元素與最后一個(gè)元素的位置）進(jìn)行分割。這個(gè)過程直到棧空為止，此時(shí)說明所有子表為空，沒有子表再需要分割，排序就完成了。

5.簡單選擇排序法

選擇排序法的基本思想如下：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面（這是它應(yīng)有的位置）；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。

對(duì)于長度為n的序列，選擇排序需要掃描n-1遍，每一遍掃描均從剩下的子表中選出最小的元素，然后將該最小的元素與子表中的第一個(gè)元素進(jìn)行交換。這種排序法的示意圖如圖1-37所示，圖中有方框的元素是剛被選出來的最小元素。

簡單選擇排序法在最壞情況下需要比較n(n-1)/2次。

6.堆排序法

堆排序是一種樹形選擇排序。堆的定義如下：

設(shè)有n個(gè)元素的序列（h1，h2，…，hn），當(dāng)且僅當(dāng)滿足

（i=1，2，…，n/2）時(shí)稱為堆。本節(jié)只討論滿足前者條件的堆。

由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)。

在實(shí)際處理中，可以用一維數(shù)組來存儲(chǔ)堆序列中的元素，也可以用完全二叉樹來直觀地表示堆的結(jié)構(gòu)。堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。

例如，序列（87，75，60，39，46，35，26，18）是一個(gè)堆，它所對(duì)應(yīng)的完全二叉樹如圖1-38所示。

由圖1-38可以看出，在用完全二叉樹表示堆時(shí)，樹中所有非葉子結(jié)點(diǎn)值均不小于其左、右子樹的根結(jié)點(diǎn)值，因此，堆頂（完全二叉樹的根結(jié)點(diǎn)）元素必為序列的n個(gè)元素中的最大項(xiàng)。

在具體討論堆排序法之前，先討論這樣一個(gè)問題：在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹（用一維數(shù)組H(1：n)表示）中，假設(shè)結(jié)點(diǎn)H(m)左右子樹均為堆，現(xiàn)在將以H(m)為根結(jié)點(diǎn)的子樹也調(diào)整為堆。這是調(diào)整建堆的問題。

例如，假設(shè)圖1-39a是某完全二叉樹的一棵子樹，顯然，在這棵子樹中，根結(jié)點(diǎn)49的左、右子樹均為堆。現(xiàn)在為了將整個(gè)子樹調(diào)整為堆，首先將根結(jié)點(diǎn)49與其左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，此時(shí)由于左子樹根結(jié)點(diǎn)95大于右子樹根結(jié)點(diǎn)63，且它又大于根結(jié)點(diǎn)49，因此，根據(jù)堆的條件，應(yīng)將元素49與95交換，如圖1-39b所示。經(jīng)過這一次交換后，破壞了原來左子樹的堆結(jié)構(gòu)，需要對(duì)左子樹再進(jìn)行調(diào)整，將元素81與49進(jìn)行交換，調(diào)整后的結(jié)果如圖1-39c所示。

由這個(gè)例子可以看出，在調(diào)整建堆的過程中，總是將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，若不滿足堆的條件，則將左、右子樹根結(jié)點(diǎn)值中的大者與根結(jié)點(diǎn)值進(jìn)行交換。這個(gè)調(diào)整過程一直做到所有子樹均為堆為止。

有了調(diào)整建堆的算法后，就可以將一個(gè)無序序列建成為堆。

假設(shè)無序序列H(1:n)以完全二叉樹表示。從完全二叉樹的最后一個(gè)非葉子結(jié)點(diǎn)（即第n/2個(gè)元素）開始，直到根結(jié)點(diǎn)（即第一個(gè)元素）為止，對(duì)每一個(gè)結(jié)點(diǎn)進(jìn)行調(diào)整建堆，最后就可以得到與該序列對(duì)應(yīng)的堆。

根據(jù)堆的定義，可以得到堆排序的方法如下：

1）首先將一個(gè)無序序列建成堆。

2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前n-1個(gè)元素構(gòu)成的子序列，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調(diào)整為堆。反復(fù)做第2）步，直到剩下的子序列為空為止。

堆排序的方法對(duì)于規(guī)模較小的線性表并不合適，但對(duì)于較大規(guī)模的線性表來說是很有效的。在最壞情況下，堆排序需要比較的次數(shù)為O(nlog2n)。

7.各種排序方法的比較

各種排序方法的時(shí)間復(fù)雜度和空間復(fù)雜度比較如表1-2所示。

表1-2 各種排序算法的比較