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