【正文】 ，最先進(jìn)遂道的是火車頭， 最后是火車尾，而火車出遂道的時候也是火車頭先出，最后出的是火車尾。若 有隊列： Q =(q1,q2,? ,qn) 那么， q1為隊頭元素（排頭元素）， qn為隊尾元素。隊列中的元素是按照 q1， q2，?， qn的順序進(jìn)入的，退出隊列也只能按照這個次序依次退出，即只有在 q1， q2，?， qn1都退隊之后， qn才能退出隊列。因最先進(jìn)入隊列的元素將最先出隊， 所以隊列具有先進(jìn)先出的特性，體現(xiàn)“先來先服務(wù)”的原則。 隊頭元素 q1是最先被插入的元素，也是最先被刪除的元素。隊尾元素 qn是 最后被插入的元素，也是最后被刪除的元素。因此，與棧相反，隊列又稱為“先 進(jìn)先出”（ First In First Out，簡稱 FIFO） 或“后進(jìn)后出”（ Last In Last Out，簡 稱 LILO）的線性表。 2. 隊列運(yùn)算 入隊運(yùn)算是往隊列隊尾插入一個數(shù)據(jù)元素；退隊運(yùn)算是從隊列的隊頭刪除一 個數(shù)據(jù)元素。 隊列的順序存儲結(jié)構(gòu)一般采用隊列循環(huán)的形式。循環(huán)隊列 s=0表示隊列空； s=1且 front=rear表示隊列滿。計算循環(huán)隊列的元素個數(shù)：“尾指針減頭指針”， 若為負(fù)數(shù)，再加其容量即可。 鏈表 在鏈?zhǔn)酱鎯Ψ绞街校竺總€結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素 值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為 指針域。其中指針用于指向該結(jié) 點的前一個或后一個結(jié)點（即前件或后件）。 鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 （ 1）線性鏈表 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 在某些應(yīng)用中，對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針， 用以指向其前件結(jié)點；另一個稱為右指針，用以指向其后件結(jié)點。這樣的表稱為 雙向鏈表。 在線性鏈表中，各數(shù)據(jù)元素結(jié)點的存儲空間可以是不連續(xù)的，且各數(shù)據(jù)元素 的存儲順序與邏輯順序可以不一致。在線性鏈表中進(jìn)行插入與刪除，不需要移動 鏈表中的元素。 線性單鏈表中， HEAD稱為頭指針， HEAD=NULL（或 0）稱為空表。 如果是雙項鏈表的兩指針：左指針（ Llink）指向前件結(jié)點，右指針（ Rlink） 指向后件結(jié)點。 線性鏈表的基本運(yùn)算：查找、插入、刪除。 （ 2）帶鏈的棧 棧也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。帶鏈的棧可以用來收集計算機(jī)存 儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用棧。 二叉樹 二叉樹概念及其基本性質(zhì) 1. 二叉樹及其基本概念 二叉樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個特點： ① 非空二叉樹只有一個根結(jié)點； ② 每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹。 在二叉樹中，每一個結(jié)點的度最大為 2，即所有子樹（左子樹或右子樹）也 均為二叉樹。另外，二叉樹中的每個結(jié)點的子樹被明顯地分為左子樹和右子樹。 在二叉樹中，一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有右子樹而 沒有左子樹。當(dāng)一個結(jié)點既沒有左子樹也沒有右子樹時，該結(jié)點即為葉子結(jié)點。 例如，一個家族中的族譜關(guān)系如圖 11所示： A有后代 B， C； B有后代 D， E； C有后代 F。 典型的二叉 樹如圖 11所示： 詳細(xì)講解二叉樹的基本概念，見表 12。 圖 11 二叉樹圖 表 12 二叉樹的基本概念 父結(jié)點（根） 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只 有一個，稱為樹的根結(jié)點，簡稱樹的根。例如，在圖 11中，結(jié)點 A是樹的根 結(jié)點。 子結(jié)點和 葉子結(jié)點 在樹結(jié)構(gòu)中，每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后 件的結(jié)點稱為葉子結(jié)點。例如，在圖 11中，結(jié)點 D， E， F均為葉子結(jié)點。 度 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個 數(shù)稱為該結(jié)點的度，所有結(jié)點中 最大的度稱為樹的度。例如，在圖 11中，根結(jié)點 A和結(jié)點 B的度為 2，結(jié)點 C的度為 1，葉子結(jié)點 D， E， F的度為 0。所以，該樹的度為 2。 深度 定義一棵樹的根結(jié)點所在的層次為 1，其他結(jié)點所在的層次等于它的父結(jié) 點所在的層次加 1。樹的最大層次稱為樹的深度。例如，在圖 11中，根結(jié)點 A在第 1層，結(jié)點 B， C在第 2層，結(jié)點 D， E， F在第 3層。該樹的深度為 3。 子樹 在樹中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹。 2. 二叉樹基本性質(zhì) 二叉樹具 有以下幾個性質(zhì)： 性質(zhì) 1：在二叉樹的第 k層上，最多有 2k1（ k≥ 1）個結(jié)點。 性質(zhì) 2：深度為 m的二叉樹最多有 2m1個結(jié)點。 性質(zhì) 3：在任意一棵二叉樹中，度為 0的結(jié)點（即葉子結(jié)點）總是比度為 2 的結(jié)點多一個。 性質(zhì) 4：具有 n個結(jié)點的二叉樹，其深度至少為 [log2n]+1，其中 [log2n]表示 取 log2n的整數(shù)部分。 3. 滿二叉樹與完全二叉樹 滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點都有 兩個子結(jié)點。在滿二叉樹中，每一層上的結(jié)點數(shù)都達(dá)到最大值，即在滿二叉樹 的 第 k層上有 2k1個結(jié)點，且深度為 m的滿二叉樹有 2m1個結(jié)點。 完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到最 大值；在最后一層上只缺少右邊的若干結(jié)點。 對于完全二叉樹來說，葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)：對于任何 一個結(jié)點，若其右分支下的子孫結(jié)點的最大層次為 p，則其左分支下的子孫結(jié)點 的最大層次或為 p，或為 p+1。 完全二叉樹具有以下兩個性質(zhì)： 性質(zhì) 1：具有 n個結(jié)點的完全二叉樹的深度為 [log2n]+1。 性質(zhì) 2：設(shè)完全二叉樹共有 n個結(jié)點。如果從根結(jié)點開 始，按層次（每一層 從左到右）用自然數(shù) 1， 2，??， n給結(jié)點進(jìn)行編號，則對于編號為 k（ k=1， 2，??， n）的結(jié)點有以下結(jié)論： ① 若 k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若 k1，則該結(jié)點的父結(jié)點 編號為 INT（ k/2）； ② 若 2k≤ n，則編號為 k的結(jié)點的左子結(jié)點編號為 2k；否則該結(jié)點無左子 結(jié)點（顯然也沒有右子結(jié)點）； ③ 若 2k+1≤ n，則編號為 k的結(jié)點的右子結(jié)點編號為 2k+1；否則該結(jié)點無 右子結(jié)點。 二叉樹的遍歷 在遍歷二叉樹的過程中，一般先遍歷左子樹，再 遍歷右子樹。在先左后右的 原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷 和后序遍歷。 （ 1）前序遍歷 先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且在遍歷左、右子樹 時，仍需先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。例如，對圖 11中 的二叉樹進(jìn)行前序遍歷的結(jié)果（或稱為該二叉樹的前序序列）為： A， B， D， E， C， F。 （ 2）中序遍歷 先遍歷左子樹、然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子 樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。 例如，對圖 11 中的二叉樹進(jìn)行中序遍歷的結(jié)果（或稱為該二叉樹的中序序列）為： D， B， E， A， C， F。 （ 3）后序遍歷 先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)點；并且，在遍歷左、右子 樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。例如，對圖 11 中的二叉樹進(jìn)行后序遍歷的結(jié)果（或稱為該二叉樹的后序序列）為： D， E， B， F， C， A。 查找 順序查找 查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。從線性表的第一個 元素開始，依次將線性表中的 元素與被查找的元素相比較，若相等則表示查找成 功；若線性表中所有的元素都與被查找元素進(jìn)行了比較但都不相等，則表示查找 失敗。 例如，在一維數(shù)組 [21， 46， 24， 99， 57， 77， 86]中，查找數(shù)據(jù)元素 99，首 先從第 1個元素 21開始進(jìn)行比較，比較結(jié)果與要查找的數(shù)據(jù)不相等，接著與第 2個元素 46進(jìn)行比較，以此類推，當(dāng)進(jìn)行到與第 4個元素比較時，它們相等， 所以查找成功。如果查找數(shù)據(jù)元素 100，則整個線性表掃描完畢，仍未找到與 100 相等的元素，表示線性表中沒有要查找的元素。 在下列兩種情況下也只 能采用順序查找： ①如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，只能 用順序查找； ②即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。 二分法查找 二分法查找，也稱拆半查找，是一種高效的查找方法。能使用二分法查找的 線性表必須滿足用順序存儲結(jié)構(gòu)和線性表是有序表兩個條件。 “有序”是特指元素按非遞減排列，即從小到大排列，但允許相鄰元素相等。 下一節(jié)排序中，有序的含義也是如此。 對于長度為 n的有序線性表，利用二分法查找元素 X的過程如下： 步驟 1：將 X與線性表的中間項比較； 步驟 2：如果 X的值與中間項的值相等，則查找成功，結(jié)束查找； 步驟 3：如果 X小于中間項的值，則在線性表的前半部分以二分法繼續(xù) 查找； 步驟 4：如果 X大于中間項的值，則在線性表的后半部分以二分法繼續(xù) 查找。 例如，長度為 8的線性表關(guān)鍵碼序列為： [6， 13， 27， 30， 38， 46， 47， 70]， 被