數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)（數(shù)

值、字符等）的集合。

數(shù)據(jù)元素（數(shù)據(jù)成員）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等

數(shù)據(jù)對(duì)象具有相同性質(zhì)的數(shù)據(jù)元素（數(shù)據(jù)成員）的集合

數(shù)據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為Data_Structure={D,R}其中，D是某一數(shù)據(jù)

對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。

數(shù)據(jù)類型是指一種類型，以及定義在這個(gè)值集合上的一組操作的總稱。

判斷一個(gè)算法的優(yōu)劣主要標(biāo)準(zhǔn)：正確性、可使用性、可讀性、效率、健壯性、簡單性。

算法效率的衡量方法：后期測試，事前估計(jì)

算法分析是算法的漸進(jìn)分析簡稱

數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個(gè)方面（層次）：

邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)成員之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)成員的集合和定義在此集合上的若干關(guān)系來表示物

理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”

線性表的定義：n（>0）個(gè)表項(xiàng)的有限序列L=...,an）由是表項(xiàng)，”是表長度。第一個(gè)表項(xiàng)是表頭，最后一

個(gè)是表尾。

線性表的特點(diǎn)：表中元素的數(shù)據(jù)類型相同；線性表中，結(jié)點(diǎn)和結(jié)點(diǎn)間的關(guān)系是一對(duì)一的，有序表和無序表線性表的存

儲(chǔ)方式。一，順序存儲(chǔ)方式，二，鏈表存儲(chǔ)方式。

順序表的存儲(chǔ)表示有2種方式：靜態(tài)方式和動(dòng)態(tài)方式。

順序表的定義是：把線性表中的所有表項(xiàng)按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)中指定存儲(chǔ)位置開始的一塊連續(xù)的

存儲(chǔ)空間中。

順序表的特點(diǎn)：用地址連續(xù)的一塊存儲(chǔ)空間順序存放各表項(xiàng)，各表項(xiàng)的邏輯順序與物理順序一致，對(duì)各個(gè)表項(xiàng)可以順

序訪問，也可以隨機(jī)訪問。

單鏈表是一種最簡單的鏈表表示，也叫線性鏈表，用她來表示線性表時(shí)，用指針表示結(jié)點(diǎn)間的邏輯關(guān)系。特點(diǎn)：是長

度可以很方便地進(jìn)行擴(kuò)充。

連續(xù)存儲(chǔ)方式（順序表）特點(diǎn)：存儲(chǔ)利用率高，存取速度快缺點(diǎn)：插入、刪除等操作時(shí)需要移動(dòng)大量數(shù)據(jù)：

鏈?zhǔn)酱鎯?chǔ)方式（鏈表）特點(diǎn)：適應(yīng)表的動(dòng)態(tài)增長和刪除。缺點(diǎn)：需要額外的指針存儲(chǔ)空間

單鏈表的類定義：多個(gè)類表達(dá)一個(gè)概念（單鏈表）。分為：鏈表結(jié)點(diǎn)（UsWode）類，鏈表（乙汨）類。

循環(huán)鏈表的概念：是另一種形式的表示線性表的鏈表，它的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表相同，與單璉表不同的是鏈表中表尾結(jié)

點(diǎn)的LINK域中不是NULL,而是存放了一個(gè)指向鏈表開始結(jié)點(diǎn)的指針，這樣，只要知道表中任何一個(gè)結(jié)點(diǎn)的地址，

就能遍歷表中其他任何一結(jié)點(diǎn)。

雙向鏈表的概念：在雙向鏈表的沒餓結(jié)點(diǎn)中應(yīng)有兩個(gè)鏈接指針作為它的數(shù)據(jù)成員：1L1NK指示它的前驅(qū)結(jié)點(diǎn)，RLINK指

示它的后繼結(jié)點(diǎn)，因此，雙向鏈表的每個(gè)結(jié)點(diǎn)至少有3個(gè)域：1LINK（前驅(qū)指針）DADA（數(shù)據(jù)）RLINK（后繼指針）。棧：

定義為只允許在表的末端進(jìn)行插入和刪除的線性表。特點(diǎn)是：后進(jìn)先出。

遞歸的定義：若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義，則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過程直接地或間

接地調(diào)用自己，則稱這個(gè)過程是遞歸的過程。以下三種情況常常用到遞歸方法一。定義是遞歸的二。數(shù)據(jù)結(jié)構(gòu)是遞歸的

三問題的解法是遞歸的。

隊(duì)列：隊(duì)列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊(duì)頭，允許插入的一端叫做隊(duì)尾。特性：

先進(jìn)先出。

優(yōu)先級(jí)隊(duì)列：是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。多維數(shù)組是一維

數(shù)組的推廣。

多維數(shù)組是一維數(shù)組的推廣。多維數(shù)組的特點(diǎn)是每一個(gè)數(shù)據(jù)元素可以有多個(gè)直接前驅(qū)和多個(gè)直接后繼。數(shù)組元素的下

標(biāo)一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡單。

字符串是?（>0）個(gè)字符的有限序列,記作S:“clc2c3…cn”其中，S是串名字clc2c3…cn”是串值ci是串中字符”是

串的長度，n=0稱為空串。

廣義表是n（20）個(gè)表元素組成的有限序列，記作LS（al,a2,a3，…，an）,LS是表名，山是表元素，可以是表（稱為子

表），可以是數(shù)據(jù)元素（稱為原子）。〃為表的長度。〃=0的廣義表為空表。時(shí)，表的第一個(gè)表元素稱為廣義表的

表頭（head）,除此之外，其它表元素組成的表稱為廣義表的表尾（tail

有根樹：一棵有根樹T,簡稱為樹，它是“（G0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)〃=0時(shí)，7稱為空樹；否則，T是非空樹，

記作T={空集n=0

{r,Tl,T2....Tn},n>0

r是一個(gè)特定的稱為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為m(m>0)個(gè)互不

相交的有限集合Tl,T2,....Tm,每個(gè)集合又是一棵樹，并且稱之為根的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前

驅(qū)，但可以有0個(gè)或多個(gè)直接后繼

二叉樹的定義:一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和

右子樹的、互不相交的二叉樹組成。

完全二叉樹：一若設(shè)二叉樹的深度為k,則共有k層。除第k層外，其它各層(l~k-l)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，

第k層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹

二叉樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作V遍歷根的左

子樹記作L遍歷根的右子樹記作R。則可能的遍歷次序有：前序VLR鏡像VRL；中序LVR鏡像RVL；后序LRV鏡

像RLV

前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子

樹(R)o遍歷結(jié)果-+a*b-cd/e/

樹的后根次序遍歷:當(dāng)樹非空時(shí)依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn)：樹后根遍歷EFBCGDA：對(duì)應(yīng)二叉樹中序遍歷

EFBCGDA；樹的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹。

表示的中序遍歷結(jié)果相同：樹的后根遍歷可以借助對(duì)應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)

最小堆和最大堆：如果有一個(gè)關(guān)鍵碼集合K={KO,K1,K2,K3,.…,Kn-1},把它的所有元素按完全二叉樹的順序存儲(chǔ)

方式存放在一個(gè)一維數(shù)組中。并滿足KiWK2i+l且KiWK2i+2(或者Ki>K2i+l且KiK2i+2)i=0,(n-2)/2],則稱

這個(gè)集合為最小堆或最大堆。

堆是最高效的一種數(shù)據(jù)結(jié)構(gòu)，每次出隊(duì)列的是優(yōu)先權(quán)最高的元素。用堆實(shí)現(xiàn)其存儲(chǔ)表示，能夠高效運(yùn)作。

堆的建立：有2種方式建立最小的堆，一種方式是通過第一個(gè)構(gòu)造函數(shù)建立一個(gè)空堆，其大小通過動(dòng)態(tài)存儲(chǔ)分配得到，

另一中建立最小堆的方式是通過第二個(gè)構(gòu)造函數(shù)復(fù)制一個(gè)記錄數(shù)組并對(duì)其加以調(diào)整形成一個(gè)堆。

路徑：從樹中一個(gè)結(jié)點(diǎn)到達(dá)另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成該兩結(jié)點(diǎn)之間的路徑。

路徑長度：是指路徑上的分支條數(shù)，樹的路徑長度是從樹的根結(jié)點(diǎn)到每一個(gè)結(jié)點(diǎn)的路徑長度之和。由樹的定義，從根

結(jié)點(diǎn)到達(dá)書中每一結(jié)點(diǎn)有且僅有一條路徑。

Huffman樹：帶權(quán)路徑長度最小的二叉樹應(yīng)是權(quán)值大的外結(jié)點(diǎn)離根結(jié)點(diǎn)最近的擴(kuò)充二叉樹。帶路徑長度最小的擴(kuò)充二叉

樹不一定是完全二叉樹。

集合是成員(元素)的一個(gè)群集。集合中的成員可以是原子(單元素)，也可以是集合。

字典是一些元素的集合，每個(gè)元素有一個(gè)稱作關(guān)鍵碼(key)的域，不同元素的關(guān)鍵碼互不相同。

散列方法：理想的搜索方法是可以不經(jīng)過比較，一次直接從字典中得到要搜索的元素。如果在元素存儲(chǔ)位置與其關(guān)鍵

碼之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash(),使得每個(gè)關(guān)鍵碼與結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)：Address=

Hash(key)o在插入時(shí)依此函數(shù)計(jì)算存儲(chǔ)位置并按此位置存放。在搜索時(shí)對(duì)元素的關(guān)鍵碼進(jìn)行同樣的計(jì)算，把求得的函

數(shù)值當(dāng)做元素存儲(chǔ)位置，在結(jié)構(gòu)中按此位置搜索。這就是散列方法。在散列方法中所用轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此

方法構(gòu)造出來的表叫做散列表。使用散列方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵碼的比較，搜索速度比較快，可以直接到達(dá)或逼

近具有此關(guān)鍵碼的表項(xiàng)的實(shí)際存放地址。

散列函數(shù)是一個(gè)壓縮映象函數(shù)。關(guān)鍵碼集合比散列表地址集合大得多。因此有可能經(jīng)過散列函數(shù)的計(jì)算，把不同的關(guān)

鍵碼映射到同一個(gè)散列地址上，這就產(chǎn)生了沖突

搜索就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。搜索的結(jié)果通常有兩種可能：搜索成功，即找到滿足條件的數(shù)

據(jù)對(duì)象。這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中的位置，還可給出該對(duì)象中的具體信息。搜索不成功，或搜索失

敗。作為結(jié)果，應(yīng)報(bào)告一些信息，如失敗標(biāo)志、位置等

搜索結(jié)構(gòu)通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象(或記錄)組成。在每個(gè)對(duì)象中有若干屬性，其

中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際

應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實(shí)施搜索時(shí)有兩種不同的環(huán)

境。靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。—靜態(tài)搜索表動(dòng)態(tài)環(huán)境，為保持較高的搜索效率，

搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。一動(dòng)態(tài)搜索表

順序搜索主要用于在線性表中搜索。設(shè)若表中有Currentsize個(gè)元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵

碼與給定值x進(jìn)行比較若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。若整個(gè)表都已檢測完仍未找

到關(guān)鍵碼與x相等的元素，則搜索失敗。給出失敗信息

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：1每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(key),所有結(jié)

點(diǎn)的關(guān)鍵碼互不相同。2左子樹(如果非空)上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。3右子樹(如果非空)上所

有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。4左子樹和右子樹也是二叉搜索樹。

二叉搜索樹為二叉排序樹如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，

所以也稱二叉搜索樹為二叉排序樹

在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的

過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為X的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL,則搜索不成

功；否則用給定值x與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：若給定值等于根結(jié)點(diǎn)關(guān)鍵碼，則搜索成功，返回搜索成功信息并報(bào)

告搜索到結(jié)點(diǎn)地址。若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子

二叉搜索樹的插入算法：為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之

前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；如果

搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。

圖定義：圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph=(V,E)其中V={x|xe某個(gè)

數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；E={(x,功|x,yeV}或七={<x,y>|x,yeU&&Path(x,切},是頂點(diǎn)之間關(guān)系

的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y(tǒng)的一條單向通路，它是有方向的。

有向圖與無向圖：在有向圖中，頂點(diǎn)對(duì)<x,y>是有序的。在無向圖中，頂點(diǎn)對(duì)(x,y)是無序的。

完全圖：若有n個(gè)頂點(diǎn)的無向圖有n(n-l)/2條邊，則此圖為完全無向圖。有n個(gè)頂點(diǎn)的有向圖有n(n-l)條邊，則此

圖為完全有向圖

在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。

鄰接表是鄰接矩陣的改進(jìn)形式。為此需要把鄰接矩陣的各行分別組織為一個(gè)單鏈表。在鄰接表中，同一個(gè)頂點(diǎn)發(fā)出的邊

鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn))，結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)dest和指針link。對(duì)于帶權(quán)

圖，邊結(jié)點(diǎn)中還要保存該邊的權(quán)值cost。頂點(diǎn)表的第i個(gè)頂點(diǎn)中保存該頂點(diǎn)的數(shù)據(jù)，以及它對(duì)應(yīng)邊鏈表的頭指針adj最

短路徑問題：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得

沿此路徑上各邊上的權(quán)值總和達(dá)到最小。

排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

數(shù)據(jù)表(dafa/isf):它是待排序數(shù)據(jù)元素的有限集合。

排序碼(Aey):通常數(shù)據(jù)元素有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來區(qū)分元素，作為排序依據(jù)。

該域即為排序碼。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為排序碼，要視具體的應(yīng)用需要而定。

插入排序基本方法是：每步將一個(gè)待排序的元素，按其排序碼大小，插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上，直到元

素全部插入為止。

鏈表

1、單鏈表中的插入與刪除

第一種情況：在第一個(gè)結(jié)點(diǎn)前插入第二種情況：在鏈表中間插入第三種情況：在鏈表末尾插入

newnode-^link=first;newnode-^link=pflink;newnode^link=pflink;

first=newnode；pflink=newnode；pflink=last=newnode；

2、鏈表插入算法實(shí)現(xiàn)3、鏈表結(jié)點(diǎn)刪除算法

intList:Insert(constintx,constinti){intList:Remove(inti){〃在鏈表中刪除第i個(gè)結(jié)點(diǎn)

〃在鏈表第i個(gè)結(jié)點(diǎn)處插入新元素xNode*p=first,*q;intk=0;

ListNode*p=first;intk=0;while(p!=NULL&&fc<i-l)

while(p!=NULL){p=pflink;fc++;}加煤M個(gè)結(jié)點(diǎn)

{P=p-link;k++;}的涕M個(gè)結(jié)點(diǎn)if(p==NULL11pflink==NULL)

if(p==NULL&&first!=NULL){cout<v“無效的刪除位置!\n”

{cout?“無效的插入位置!\n”；return0;

return0;]

}if(i==0){〃刪除表中第1個(gè)結(jié)點(diǎn)

ListNode*newnode=newListNode(x,NULL];q=first;〃q保存被刪結(jié)點(diǎn)地址

〃創(chuàng)建新結(jié)點(diǎn)，其數(shù)據(jù)為x,指針為0p=first=firstflink;〃修改first

if(first==NULL\\i==0){腐在表前]

newnode^link=first;else{〃刪除表中或表尾元素

if(first==NULL)last=newnode;q=p-*link;

first=newnode;p—link=qflink;〃重新鏈接

}}

else{體1在表中或末尾if(q==last)last=p;T能修改last

newnode-^link=p->link;k=q-data;

if(p-*link==NULL)last=newnode;deleteq;〃刪除q

p-*link=newnode;returnk;

}]

return1;

1

在帶表頭結(jié)點(diǎn)的單鏈表，第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)從帶表頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)結(jié)點(diǎn)

newnode-^link=p—link;q=p-link;p—link=q-*link;

if(p-link==NULL)last=newnode;deleteq;

pflink=newnode:if(p->link==NULL}last=v\

排序

直接插入排序的算法折半插入排序的算法

#include"dataList.h',#include"dataList.h"

template<classT>template<classT>

voidInsertSort(dataList<T>&L,intleft,intright){voidBinarylnsertSort(dataList<T>&Lz

〃依次將元素L.Vector國按其排序碼插入到有序表constintleft,constintright)|

〃L?Vector[加ft],…,L.Vector[i-l]中，使得〃利用折半搜索，在L.Vector[left]$lJLVectoiji-l]中

〃L.Vector[left]到L.Vector[i]有序?！ú檎襆.Vector。]應(yīng)插入的位置，再進(jìn)行插入。

Element<T>temp;inti,j;Element<T>temp;

for(i=left+l;i<=right;i++)inti,low,high,middle,k;

if(L[i]<L[i-l]){for(i=left+1;i<=right;i++){

temp=L[i];j=i-l;temp=L[i];low=left;high=i-l;

do{while(low<=high){〃折半搜索插入位置

L[j+l]=L[j];j-;middle=Qow+high)/2;〃取中點(diǎn)

}while(j>=left&&temp<L[j]);if(temp<L[middle])〃插入值小于中點(diǎn)值

L[j+1]=temp;high=middle-1;〃向左縮小區(qū)間

}elselow=middle+1;〃否則，向右縮小區(qū)間

};}

for(k=i-1;k>=low;k—)L[k+1]=L[k];

〃成塊移動(dòng),空出插入位置

L[low]=temp;〃插入

}

1；

堆排序的算法直接選擇排序的算法

template<classT>#include"dataList.h"

voidHeapSort(dataList<T>&L){template<classT>

〃對(duì)表L.Vector[O]JlJL.Vector[n?l]進(jìn)行排序，使得表voidSelectSort(dataList<T>&L,

〃中各個(gè)元素按其排序碼非遞減有序constintleft,constintright)

intizn=L.length();{for(inti=left;i<right;i++){

for(i=(n-2)/2;i>=0;i-)〃將表轉(zhuǎn)換為堆intk=i;/在L[i]到L[n-1]找最小排序碼元素

siftDown(L,i,n-1);for(intj=i+l;j<=right;j++)

for(i=n-l;i>=0;i-)(分寸表排序if(LU]<L[k])k=j;

L.Swap(0,i);siftDown(L,0,i-1);if(k!=i)Swap(L[i],L[k]);〃交換

}1

)；}；

希爾排序的算法起泡排序的算法

#include"dataList.h"template<classT>

template<classT>voidBubbleSort(dataList<T>&L,constintleft,

voidShellsort(dataList<T>&L,constintright)

constintleft,constintright){{intpass=left+1,exchange=1;

inti,j,gap=right-left+1;〃增量的初始值while(pass<=right&&exchange){

Element<T>temp;exchange=0;〃標(biāo)志為0假定未交換

do{for(intj=right;j>=pass;j-)

gap=gap/3+l;〃求下一增量值if(L[j-l]>LLj]){〃逆序

for(i=left+gap;i<=right;i++)Swap(L[j-1],LU])；管換

if(L[i]<L[i-gap]){〃逆序exchange=1;〃標(biāo)志置為1,有交換

temp=L[i];j=i-gap;}

do{pass++;

L[j+gap]=L[j];j=j-gap;}

}while(j>=left&&temp<L[j]);}；

L[j+gap]=temp;〃將vector/]回送

}

}while(gap>1