1.1 考點精講

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

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

1.1.1 算法

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

1.算法的基本特征

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

1）可行性：算法的可行性，是指算法中指定的操作都可以通過基本運算執(zhí)行有限的次數(shù)后實現(xiàn)。針對實際問題設(shè)計算法時必須考慮它的可行性，因為人們總是希望能夠達到滿意的結(jié)果。

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

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

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

2.算法的基本要素

1）算法中對數(shù)據(jù)的運算和操作：每個算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。

計算機可以執(zhí)行的基本操作是以指令的形式描述的。一個計算機系統(tǒng)能執(zhí)行的所有指令的集合，稱為該計算機系統(tǒng)的指令系統(tǒng)。計算機程序就是按解題要求從計算機指令系統(tǒng)中選擇合適的指令所組成的指令序列。在一般的計算機系統(tǒng)中，基本的運算和操作有以下4類：

●算術(shù)運算：主要包括加、減、乘、除等運算。

●邏輯運算：主要包括“與”、“或”、“非”等運算。

●關(guān)系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算。

●數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。

2）算法的控制結(jié)構(gòu)：一個算法的功能不僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。

算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。

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

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

（1）列舉法

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

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

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

（2）歸納法

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

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

（3）遞推法

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

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

（4）遞歸

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

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

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

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

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

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

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

首先取給定區(qū)間的中點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ì)上是對實際問題進行歸納的結(jié)果，而減半遞推技術(shù)也是歸納法的一個分支。在工程上，有些實際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能無限地列舉。對于這類問題，只能采用“試探”的方法，通過對問題的分析，找出解決問題的線索，然后沿著這個線索進行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換其他路線進行試探。這種方法即稱為回溯法。

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

4.算法復(fù)雜度

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

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

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

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

算法的工作量=f(n)

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

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

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

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

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

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

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

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

2）各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。

3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。

討論以上問題的主要目的是提高數(shù)據(jù)處理的效率。提高數(shù)據(jù)處理的效率主要包括兩個方面：一是提高數(shù)據(jù)速度，二是盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間。

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

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

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

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

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

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

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

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

一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(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)系）來描述。例如，在考慮一年四個季節(jié)的順序關(guān)系時，“春”是“夏”的前件（即直接前驅(qū)，下同），而“夏”是“春”的后件（即直接后繼，下同）。同樣，“夏”是“秋”的前件，“秋”是“夏”的后件；“秋”是“冬”的前件，“冬”是“秋”的后件。在考慮家庭成員間的輩分關(guān)系時，“父親”是“兒子”和“女兒”的前件，而“兒子”與“女兒”都是“父親”的后件。

前后件關(guān)系是數(shù)據(jù)元素之間的一個基本關(guān)系，但前后件關(guān)系所表示的實際意義隨具體對象的不同而不同。一般來說，數(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ù)據(jù)元素之間的前后件關(guān)系。

一個數(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)有兩個要素：一是用D表示數(shù)據(jù)元素的集合，二是用R表示數(shù)據(jù)元素之間的前后件關(guān)系。即一個數(shù)據(jù)結(jié)構(gòu)可以表示為B=(D，R)，其中B表示數(shù)據(jù)結(jié)構(gòu)。這就是一個二元關(guān)系的表示方式。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。例如，假設(shè)a與b是D中的兩個數(shù)據(jù)，則二元組(a，b)表示a是b的前件，b是a的后件。這樣，在D中的每兩個元素之間的關(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ù)的存儲結(jié)構(gòu)

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

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

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

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

4.數(shù)據(jù)結(jié)構(gòu)的圖形表示

數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。

在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱為數(shù)據(jù)結(jié)點，并簡稱為結(jié)點；為了進一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點。

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

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

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

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

通常，一個數(shù)據(jù)結(jié)構(gòu)中的結(jié)點可能是動態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新結(jié)點（稱為插入運算），也可以刪除數(shù)據(jù)結(jié)構(gòu)中的某個結(jié)點（稱為刪除運算）。插入與刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運算。除此之外，對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復(fù)制和修改等。在對數(shù)據(jù)結(jié)構(gòu)的處理過程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)點（即數(shù)據(jù)元素）的個數(shù)在動態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動態(tài)變化。例如，一個無序表可以通過排序處理而變成有序表；一個數(shù)據(jù)結(jié)構(gòu)中的根結(jié)點被刪除后，它的某一個后件可能變成了根結(jié)點；在一個數(shù)據(jù)結(jié)構(gòu)中的終端結(jié)點后插入一個新的結(jié)點后，則原來的那個終端結(jié)點就不再是終端結(jié)點而成為內(nèi)部結(jié)點了。有關(guān)數(shù)據(jù)的基本運算將在后面講到具體數(shù)據(jù)結(jié)構(gòu)時再介紹。

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

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

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

1）有且只有一個根結(jié)點。

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

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

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

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

如果一個數(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ù)雜，因此，對非線性結(jié)構(gòu)的存儲與處理比線性結(jié)構(gòu)要復(fù)雜得多。

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

1.1.3 線性表

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

1.線性表的基本概念

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

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

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

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

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

1）有且僅有一個根結(jié)點，無前件。

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

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

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

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

2.線性表的順序存儲

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

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

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

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

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

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

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

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

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

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

在線性表的順序存儲結(jié)構(gòu)下，可以對線性表做以下運算：

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

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

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

4）對線性表中的元素進行排序（即線性表的排序）。

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

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

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

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

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

3.線性表的插入運算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.線性表的刪除運算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1.4 棧和隊列

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

1.棧及其基本運算

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

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

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

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

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

2.棧的順序存儲及其運算

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

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

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

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

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

3.什么是隊列

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

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

1）初始時線性表為空。

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

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

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

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

向隊列的隊尾插入一個元素稱為入隊運算，從隊列的隊頭刪除一個元素稱為出隊運算。

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

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

4.循環(huán)隊列及其運算

在實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。

所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用，如圖1-11所示。

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

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

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

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

每進行一次入隊運算，隊尾指針就進1。當(dāng)隊尾指針rear=m+1時，則置rear=1。

每進行一次出隊運算，隊頭指針就進1。當(dāng)隊頭指針front=m+1時，則置front=1。

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

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

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

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

隊列空的條件為s=0；

隊列滿的條件為s=1且front=rear。

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

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

（1）入隊運算

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

（2）出隊運算

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

（3）求隊列長度

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

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

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

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

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

1.1.5 線性鏈表

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

1.線性表

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

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

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

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

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

2.線性鏈表

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

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

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

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

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

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

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

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

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

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

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

3.帶鏈的棧

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

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

4.帶鏈的隊列

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

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

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

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

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

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

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

2）當(dāng)線性鏈表中不存在包含元素x的結(jié)點時，找到的p為線性鏈表中的最后一個結(jié)點序號。

6.線性鏈表的插入

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

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

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

1）從可利用棧取得一個結(jié)點，設(shè)該結(jié)點號為p（即取得結(jié)點的存儲序號存放在變量p中），并置結(jié)點p的數(shù)據(jù)域為插入的元素值b。經(jīng)過這一步后，可利用棧的狀態(tài)1-22b所示。

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

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

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

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

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

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

7.線性鏈表的刪除

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

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

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

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

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

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

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

從線性鏈表的刪除過程可以看出，從線性鏈表中刪除一個元素后，不需要移動表中的數(shù)據(jù)元素，只要改變被刪除元素所在結(jié)點的前一個結(jié)點的指針域即可。另外，可利用棧用于收集計算機中的所有空閑結(jié)點，因此，當(dāng)從線性鏈表中刪除一個元素后，該元素的存儲結(jié)點就變?yōu)榭臻e結(jié)點，應(yīng)將空閑結(jié)點送回可利用棧。

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

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

因此，可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存儲空間，僅對表的鏈接方式稍做改變，使得對表的處理更加方便靈活。從單鏈表可知，最后一個結(jié)點的指針域為NULL，表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個結(jié)點的指針域改為存放鏈表中頭結(jié)點（或第一個結(jié)點）的地址，就使得整個鏈表構(gòu)成一個環(huán)，而且沒有增加額外的存儲空間，滿足這樣條件的鏈表叫做循環(huán)鏈表（circular linked list）。

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

1）在循環(huán)鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點。循環(huán)鏈表的頭指針指向表頭結(jié)點。

2）循環(huán)鏈表中最后一個結(jié)點的指針域不為空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。

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

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

循環(huán)鏈表的插入和刪除與線性單鏈表基本相同。但由循環(huán)鏈表的特點可以看出，在對循環(huán)鏈表進行插入和刪除的過程中，實現(xià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）個結(jié)點組成的有限集合。若n=0，稱為空樹；若n>0，則：

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

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

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

在現(xiàn)實世界中，能用樹這種數(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é)點之間的關(guān)系，因此，在描述樹結(jié)構(gòu)時，也經(jīng)常使用血緣關(guān)系中的一些術(shù)語。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n=n0+n1+n2 （1）

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

n=m+1 （2）

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

m=n1+2n2 （3）

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

n=n1+2n2+1 （4）

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

化簡后得

n0=n2+1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.二叉樹的遍歷

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

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

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

（1）前序遍歷

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

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

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

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

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

（2）中序遍歷

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

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

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

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

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

（3）后序遍歷

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

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

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

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

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

1.1.7 查找

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

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

1.順序查找

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

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

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

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

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

2.二分法查找

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

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

將x與線性表的中間項進行比較：

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

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

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

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

1.1.8 排序

排序也是數(shù)據(jù)處理的重要內(nèi)容。它為數(shù)據(jù)查找操作提供方便，因為排序后的數(shù)據(jù)在進行查找操作時效率較高。

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

1.簡單插入排序

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

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

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

2.希爾排序

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

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

將整個無序序列分割成若干小的子序列分別進行插入排序。

子序列的分割方法如下：

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

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

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

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

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

3.冒泡排序法

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

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

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

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

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

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

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

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

4.快速排序法

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

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

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

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

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

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

在對線性表或子表進行實際分割時，可以按如下步驟進行：

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

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

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

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

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

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

5.簡單選擇排序法

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

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

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

6.堆排序法

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

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

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

由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項。

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

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

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

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

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

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

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

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

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

1）首先將一個無序序列建成堆。

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

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

7.各種排序方法的比較

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

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