1.1 考點精講

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

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

1.1.1 算法

算法（algorithm）是對解題方案的準確而完整的描述。但它不等于程序，也不等于計算方法。通常，程序的編制不可能優于算法的設計。算法是指令的有限序列，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。當然，程序也可以作為算法的一種描述，但程序通常還需考慮很多與方法和分析無關的細節問題，這是因為在編寫程序時要受到計算機系統運行環境的限制。

1.算法的基本特征

一個算法，一般應具有以下幾個基本特征：

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

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

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

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

2.算法的基本要素

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

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

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

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

●關系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算。

●數據傳輸：主要包括賦值、輸入、輸出等操作。

2）算法的控制結構：一個算法的功能不僅取決于所選用的操作，而且還與各操作之間的執行順序有關。算法中各操作之間的執行順序稱為算法的控制結構。

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

3.算法設計的基本方法

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

（1）列舉法

列舉法的基本思想是，針對待解決的問題，列舉所有可能的情況，并用問題中給定的條件來檢驗哪些是必需的，哪些是不需要的。因此，列舉法常用于解決“是否存在”或“有多少種可能”等類型的問題。例如，我國古代的趣味數學題：“百錢買百雞”、“雞兔同籠”等求解不定方程的問題，均可采用列舉法解決。

其特點是原理比較簡單，但當列舉的可能情況較多時，執行列舉算法的工作量將會很大。因此，在用列舉法設計算法時，只要對實際問題進行詳細的分析，將與問題有關的知識條理化、完備化、系統化，從中找出規律；或對所有可能的情況進行分類，引出一些有用的信息，就可以大大減少列舉量。

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

（2）歸納法

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

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

（3）遞推法

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

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

（4）遞歸

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

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

（5）減半遞推技術

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

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

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

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

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

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

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

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

最后判斷減半后的區間長度是否已經很小：

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

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

（6）回溯法

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

回溯法在處理復雜數據結構方面有著廣泛的應用，如人工智能中的機器人下棋。

4.算法復雜度

算法的復雜度主要分為時間復雜度和空間復雜度。

（1）算法的時間復雜度

算法的時間復雜度是指執行算法所需要的計算工作量。

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

算法的工作量=f(n)

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

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

（2）算法的空間復雜度

一個算法的空間復雜度，一般是指執行這個算法所需要的內存空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數據所占的存儲空間以及算法執行中所需要的額外空間。其中額外空間包括算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間（例如，在鏈式結構中，除了需要存儲數據本身之外，還需要存儲鏈接信息）。如果額外空間量相對于問題規模來說是常數，則稱該算法是原地工作的。

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

1.1.2 數據結構

數據結構（data structure）是指反映數據元素之間關系的數據元素集合的表示，其作為計算機的一門學科，主要研究和討論以下3個方面的問題：

1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。

2）各數據元素在計算機中的存儲關系，即數據的存儲結構。

3）對各種數據結構進行的運算。

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

1.什么是數據結構

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

數據的組織方式不同，通常對它進行處理時的效率也不同。例如，在對兩個存放了相同元素的表進行查找時，如果一個表中的所有數據元素是沒有規律的，而另外一個表中的元素是經過排序的，則對前者進行查找時，只能從第一個元素開始，逐個將表中的元素與被查數進行比較，直到表中的某個元素與被查數相等（即查找成功）或者表中所有元素與被查數都進行了比較且都不相等（即查找失敗）為止。而對于后者，由于有序表中的元素是從小到大進行排列的，在查找時可以利用這個特點，使比較次數大大減少。可見數據元素在表中的排列順序對查找效率是有很大影響的。

要理解數據結構，還需要理解以下基本概念：

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

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

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

●數據結構（data structure）是指相互之間存在一種或多種特定關系的數據元素的集合。

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

前后件關系是數據元素之間的一個基本關系，但前后件關系所表示的實際意義隨具體對象的不同而不同。一般來說，數據元素之間的任何關系都可以用前后件關系來描述。

2.數據的邏輯結構

前面提到，數據結構是指反映數據元素之間關系的數據元素集合的表示。通俗地說，數據結構是指帶有結構的數據元素的集合。結構實際上是指數據元素之間的前后件關系。

一個數據結構應包含以下兩方面信息：

1）表示數據元素的信息。

2）表示各數據元素之間的前后件關系。

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

例如，一年四季的數據結構可以表示成

B={D，R}

D={春，夏，秋，冬}

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

例如，家庭成員數據結構可以表示成

B=(D，R)

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

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

例如，n維向量X=(x1，x2，…，xn)也是一種數據結構，即X={D，R}，

其中數據元素集合為

D={x1，x2，…，xn}

關系為

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

3.數據的存儲結構

在進行數據處理時，計算機所處理的數據總是存放在計算機的存儲空間中，一個數據結構中的各元素在計算機存儲空間中的位置關系與邏輯關系有可能是不同的。

數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱為數據的物理結構）。

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

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

4.數據結構的圖形表示

數據結構除了用二元關系表示外，還可以直觀地用圖形表示。

在數據結構的圖形表示中，對于數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱為數據結點，并簡稱為結點；為了進一步表示各數據元素之間的前后件關系，對于關系R中的每一個二元組，用一條有向線段從前件結點指向后件結點。

例如，一年四季的數據結構可以用如圖1-1所示的圖形來表示。

又例如，反映家庭成員間輩分關系的數據結構可以用如圖1-2所示的圖形表示。

顯然，用圖形方式表示一個數據結構是很方便的，并且也比較直觀。

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

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

5.線性結構與非線性結構

如果一個數據結構中一個數據元素都沒有，則稱該數據結構為空的數據結構。一個空的數據結構中插入一個新的元素后，該數據結構就變為非空數據結構；在只有一個數據元素的數據結構中，將該元素刪除后，該數據結構就變為空的數據結構。

根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為兩大類：線性結構與非線性結構。

如果一個非空的數據結構滿足如下兩個條件：

1）有且只有一個根結點。

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

則稱該數據結構為線性結構。線性結構又稱為線性表。

由此可以看出，在線性結構中，各數據元素之間的前后件關系是很簡單的。例如，圖1-1中一年四季這個數據結構就屬于線性結構。

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

如果一個數據結構不是線性結構，則稱為非線性結構。例如，圖1-2中的家庭成員間輩分關系的數據結構不是線性結構，而是非線性結構。顯然，在非線性結構中，各數據元素之間的前后件關系要比線性結構復雜，因此，對非線性結構的存儲與處理比線性結構要復雜得多。

線性結構與非線性結構都可以是空的數據結構。一個空的數據結構究竟是線性結構，還是非線性結構，要根據具體情況來確定。如果對該數據結構的運算是按線性結構的規則來處理的，則屬于線性結構，否則屬于非線性結構。

1.1.3 線性表

線性表的特點是數據元素之間的關系是線性的，數據元素可以看成是排列在一條線或一個環上。線性表（linear list）是最簡單、最常用的一種數據結構。

1.線性表的基本概念

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

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

表1-1 學生情況登記表

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

線性結構的基本特征如下：

1）有且僅有一個根結點，無前件。

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

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

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

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

2.線性表的順序存儲

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

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

線性表的順序存儲結構具備如下兩個基本特征：

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

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

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

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

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

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

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

在線性表的順序存儲結構下，可以對線性表做以下運算：

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

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

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

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

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

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

7）復制一個線性表（即線性表的復制）。

8）逆轉一個線性表（即線性表的逆轉）等。

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

3.線性表的插入運算

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

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

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

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

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

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

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

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

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

一般來說，設長度為n的線性表為

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

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

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

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

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

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

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

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

4.線性表的刪除運算

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

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

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

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

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

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

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

一般來說，設長度為n的線性表為

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

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

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

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

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

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

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

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

1.1.4 棧和隊列

棧和隊列是兩種特殊的線性結構。從數據結構的角度看，它們是線性表。從操作的角度看，它們是操作受限的線性表。在日常生活中經常會遇到棧或隊列的實例，另外棧和隊列還廣泛應用于各種軟件系統中。

1.棧及其基本運算

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

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

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

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

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

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

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

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

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

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

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

3.什么是隊列

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

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

1）初始時線性表為空。

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

3）當計算機系統執行完當前的用戶程序后，就從線性表的頭部取出一個用戶程序執行。

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

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

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

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

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

4.循環隊列及其運算

在實際應用中，隊列的順序存儲結構一般采用循環隊列的形式。

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

在循環隊列結構中，當存儲空間的最后一個位置已被使用而再要進行入隊運算時，只要存儲空間的第一個位置空閑，便可將元素加入第一個位置，即將存儲空間的第一個位置作為隊尾。

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

循環隊列的初始狀態為空，即rear=front=m，如圖1-11所示。

循環隊列主要有兩種基本運算：入隊運算與出隊運算。

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

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

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

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

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

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

隊列空的條件為s=0；

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

下面具體介紹循環隊列入隊與出隊的運算。

假設循環隊列的初始狀態為空，即s=0，且front=rear=m。

（1）入隊運算

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

（2）出隊運算

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

（3）求隊列長度

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

1）當隊尾指針大于隊頭指針時：

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

2）當隊尾指針小于隊頭指針時：

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

1.1.5 線性鏈表

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

1.線性表

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

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

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

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

由于線性表的順序存儲結構存在以上缺點，因此，對于大的線性表，特別是元素變動頻繁的大線性表，不宜采用順序存儲結構，而是采用下面將要介紹的鏈式存儲結構。

2.線性鏈表

線性表的鏈式存儲結構稱為線性鏈表。

假設數據結構中的每一個數據結構對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。

線性表的鏈式存儲是用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元既可以是連續的，也可以是不連續的，甚至是零散分布在內存中的任意位置上的。因此，鏈表中結點的邏輯次序和物理次序不一定相同。為了適應這種存儲結構，計算機存儲空間被劃分為一個一個小塊，每一個小塊占若干字節，通常稱這些小塊為存儲結點。

為了存儲線性表中的每一個元素并且能正確表示結點間的邏輯關系，一方面要存儲數據元素的值，另一方面要存儲各數據元素之間的前后件關系。為此，將存儲空間中的每一個結點分為兩部分：一部分用于存儲數據元素的值，稱為數據域；另一部分用于存放下一個數據元素的存儲序號（即存儲結點的地址），即指向后件元素，稱為指針域。線性表的鏈式存儲中存儲一個數據元素的結點結構如圖1-14表示，存儲線性表中所有數據元素的存儲空間結構如圖1-15所示。

由此可知，線性表的鏈式存儲結構中，存儲元素所需空間比線性表的順序存儲結構所需空間要多，多出的部分即是用來存放后件元素地址的，而線性表的順序存儲結構中只需數據元素的值，不需要存儲數據元素后件元素的地址，從而節省存儲空間。

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

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

下面舉一個例子來說明線性鏈表的存儲結構。

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

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

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

3.帶鏈的棧

棧也是線性表，也可以采用鏈式存儲結構。圖1-19是棧在鏈式存儲時的邏輯狀態示意圖。

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

4.帶鏈的隊列

與棧類似，隊列也是線性表，也可以采用鏈式存儲結構。圖1-21a是隊列在鏈式存儲時的邏輯狀態示意圖。圖1-21b是將新結點p插入隊列的示意圖。圖1-21c是將隊頭結點p退出隊列的示意圖。

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

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

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

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

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

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

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

6.線性鏈表的插入

線性鏈表的插入是指在鏈式存儲結構下的線性鏈表中插入一個新元素。

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

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

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

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

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

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

②使結點q的指針域內容改為指向結點p。

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

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

7.線性鏈表的刪除

線性鏈表的刪除是指在鏈式存儲結構下的線性鏈表中刪除包含指定元素的結點。

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

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

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

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

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

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

從線性鏈表的刪除過程可以看出，從線性鏈表中刪除一個元素后，不需要移動表中的數據元素，只要改變被刪除元素所在結點的前一個結點的指針域即可。另外，可利用棧用于收集計算機中的所有空閑結點，因此，當從線性鏈表中刪除一個元素后，該元素的存儲結點就變為空閑結點，應將空閑結點送回可利用棧。

8.循環鏈表的結構及其基本運算

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

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

循環鏈表的結構與前面所討論的線性鏈表相比，具有以下兩個特點：

1）在循環鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。

2）循環鏈表中最后一個結點的指針域不為空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。

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

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

循環鏈表的插入和刪除與線性單鏈表基本相同。但由循環鏈表的特點可以看出，在對循環鏈表進行插入和刪除的過程中，實現了空表與非空表的運算統一。

1.1.6 樹與二叉樹

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

1.樹的基本概念

樹是由n（n≥0）個結點組成的有限集合。若n=0，稱為空樹；若n>0，則：

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

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

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

在現實世界中，能用樹這種數據結構表示的例子很多。例如，圖1-26中的樹表示了學校行政關系結構；圖1-27中的樹反映了一本書的層次結構。

由于樹具有明顯的層次關系，因此，具有層次關系的數據都可以用樹這種數據結構來描述。在所有的層次關系中，人們最熟悉的是血緣關系，按血緣關系可以很直觀地理解樹結構中各數據元素結點之間的關系，因此，在描述樹結構時，也經常使用血緣關系中的一些術語。

下面介紹樹中的一些基本特征，同時介紹有關樹結構的基本術語。

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

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

樹是一種具有明顯層次關系的數據結構。在樹結構中，一般按如下原則分層：

根結點在第1層。

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

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

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

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

2.二叉樹的基本性質

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

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

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

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

在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即葉子結點。

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

根據二叉樹的特點，這個性質是顯然的。

性質2：深度為m的二叉樹至多有2m-1個結點。

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

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

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

對這個性質說明如下：

假設二叉樹中有n0個葉子結點，n1個度為1的結點，n2個度為2的結點，則二叉樹中總的結點數為

n=n0+n1+n2 （1）

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

n=m+1 （2）

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

m=n1+2n2 （3）

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

n=n1+2n2+1 （4）

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

化簡后得

n0=n2+1

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

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

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

這個性質可以由性質2直接得到。

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

滿二叉樹與完全二叉樹是兩種特殊形態的二叉樹。

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

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

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

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

完全二叉樹還具有以下兩個性質：

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

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

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

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

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

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

4.二叉樹的存儲結構

在計算機中，二叉樹通常采用鏈式存儲結構。

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

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

由于二叉樹存儲結構中的每一個存儲結點有兩個指針域，因此，二叉樹的鏈式存儲結構也稱為二叉鏈表。圖1-32a、圖1-32b、圖1-32c分別表示了一棵二叉樹、二叉鏈表的邏輯狀態、二叉鏈表的物理狀態。其中BT稱為二叉鏈表的頭指針，用于指向二叉樹根結點（即存放二叉樹根結點的存儲地址）

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

5.二叉樹的遍歷

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

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

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

（1）前序遍歷

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

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

若二叉樹為空，則結束返回。

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

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

（2）中序遍歷

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

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

若二叉樹為空，則結束返回。

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

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

（3）后序遍歷

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

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

若二叉樹為空，則結束返回。

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

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

1.1.7 查找

查找是數據處理領域中的一個重要內容，查找的效率將直接影響到數據處理的效率。

所謂查找，是指在一個給定的數據結構中查找某個指定的元素。在查找的過程中，涉及查找的方法等問題，通常根據不同的數據結構，采用不同的查找方法。

1.順序查找

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

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

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

1）如果線性表為無序線性表（即表中元素的排列是無序的），則不管是順序存儲結構，還是鏈式存儲結構，都只能用順序查找。

2）即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。

2.二分法查找

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

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

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

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

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

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

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

1.1.8 排序

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

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

1.簡單插入排序

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

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

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

2.希爾排序

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

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

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

子序列的分割方法如下：

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

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

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

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

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

3.冒泡排序法

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

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

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

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

對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時線性表已經變為有序。

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

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

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

4.快速排序法

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

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

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

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

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

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

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

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

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

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

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

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

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

5.簡單選擇排序法

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

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

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

6.堆排序法

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

設有n個元素的序列（h1，h2，…，hn），當且僅當滿足

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.各種排序方法的比較

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

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