2023年數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)整理

數(shù)據(jù)是信息的載體,是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中,被計(jì)算機(jī)程序辨認(rèn)和解決的符號(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}其中，Ｄ是某一數(shù)據(jù)對(duì)象,R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。數(shù)據(jù)類型是指一種類型,以及定義在這個(gè)值集合上的一組操作的總稱。?判斷一個(gè)算法的優(yōu)劣重要標(biāo)準(zhǔn):對(duì)的性、可使用性、可讀性、效率、健壯性、簡樸性。算法效率的衡量方法:后期測(cè)試,事前估計(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)系來表達(dá)物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表達(dá)和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”線性表的定義：n(30)個(gè)表項(xiàng)的有限序列L=（a1,ａ2,…,ａn）ａi是表項(xiàng),n是表長度。第一個(gè)表項(xiàng)是表頭,最后一個(gè)是表尾。線性表的特點(diǎn):表中元素的數(shù)據(jù)類型相同;線性表中,結(jié)點(diǎn)和結(jié)點(diǎn)間的關(guān)系是一對(duì)一的,有序表和無序表線性表的存儲(chǔ)方式。一,順序存儲(chǔ)方式，二,鏈表存儲(chǔ)方式。順序表的存儲(chǔ)表達(dá)有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ī)訪問。單鏈表是一種最簡樸的鏈表表達(dá),也叫線性鏈表，用她來表達(dá)線性表時(shí)，用指針表達(dá)結(jié)點(diǎn)間的邏輯關(guān)系。特點(diǎn):是長度可以很方便地進(jìn)行擴(kuò)充。連續(xù)存儲(chǔ)方式(順序表)特點(diǎn):存儲(chǔ)運(yùn)用率高，存取速度快缺陷:插入、刪除等操作時(shí)需要移動(dòng)大量數(shù)據(jù)：鏈?zhǔn)酱鎯?chǔ)方式(鏈表)特點(diǎn)：適應(yīng)表的動(dòng)態(tài)增長和刪除。缺陷:需要額外的指針存儲(chǔ)空間單鏈表的類定義:多個(gè)類表達(dá)一個(gè)概念(單鏈表）。分為:鏈表結(jié)點(diǎn)(LiｓtＮoｄｅ)類，鏈表(Lisｔ)類。循環(huán)鏈表的概念:是另一種形式的表達(dá)線性表的鏈表，它的結(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ù)成員：1LIＮK指示它的前驅(qū)結(jié)點(diǎn),RＬINＫ指示它的后繼結(jié)點(diǎn)，因此，雙向鏈表的每個(gè)結(jié)點(diǎn)至少有３個(gè)域:1LINK（前驅(qū)指針)DＡDA(數(shù)據(jù)）RLINＫ（后繼指針)。棧：定義為只允許在表的末端進(jìn)行插入和刪除的線性表。特點(diǎn)是：后進(jìn)先出。遞歸的定義:若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己,則稱這個(gè)過程是遞歸的過程。以下三種情況經(jīng)常用到遞歸方法一。定義是遞歸的二。數(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)簡樸。字符串是n(30)個(gè)字符的有限序列,記作S：“c1c2c3…cn”其中，S是串名字c1ｃ2ｃ3…cｎ”是串值ci是串中字符n是串的長度，廣義表是n（≥0)個(gè)表元素組成的有限序列,記作LS(ａ１，a２,a3,…,aｎ),LS是表名,aｉ是表元素,可以是表(稱為子表）,可以是數(shù)據(jù)元素（稱為原子)。n為表的長度。ｎ=0的廣義表為空表。n>0時(shí),表的第一個(gè)表元素稱為廣義表的表頭（head），除此之外,其它表元素組成的表稱為廣義表的表尾(taiｌ有根樹：一棵有根樹Ｔ,簡稱為樹,它是n(ｎ≥0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí),T稱為空樹;否則,Ｔ是非空樹,記作Ｔ=｛空集n=0{r,Ｔ1,T2….Tn｝,ｎ＞0ｒ是一個(gè)特定的稱為根(ｒｏｏｔ）的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為m(m30)個(gè)互不相交的有限集合Ｔ1,Ｔ２,…,Tｍ，每個(gè)集合又是一棵樹,并且稱之為根的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼二叉樹的定義:一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合,該集合或者為空,或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。完全二叉樹:─若設(shè)二叉樹的深度為k，則共有k層。除第k層外，其它各層(１～k-1)的結(jié)點(diǎn)數(shù)都達(dá)成最大個(gè)數(shù),第k層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹二叉樹的遍歷就是按某種順序訪問樹中的結(jié)點(diǎn),規(guī)定每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作V遍歷根的左子樹記作L遍歷根的右子樹記作R。則也許的遍歷順序有：前序ＶＬR鏡像ＶＲL;中序LVR鏡像ＲVＬ；后序ＬＲＶ鏡像ＲLV前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作;否則訪問根結(jié)點(diǎn)(V);前序遍歷左子樹（L);前序遍歷右子樹(Ｒ）。遍歷結(jié)果-＋ａ＊b-ｃd/ef樹的后根順序遍歷:當(dāng)樹非空時(shí)依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn):樹后根遍歷EＦBCGDA；相應(yīng)二叉樹中序遍歷EＦBＣGDA；樹的后根遍歷結(jié)果與其相應(yīng)二叉樹。表達(dá)的中序遍歷結(jié)果相同：樹的后根遍歷可以借助相應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)最小堆和最大堆：假如有一個(gè)關(guān)鍵碼集合K＝{K０，K１，Ｋ2，K3,….，Kn－1}，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存放在一個(gè)一維數(shù)組中。并滿足Ki≤K２i＋1且Kｉ≤K2i+2(或者Kｉ≥Ｋ２i+1且KiK2i+２)ｉ＝0，1,…．[（n-２)/2］，則稱這個(gè)集合為最小堆或最大堆。堆是最高效的一種數(shù)據(jù)結(jié)構(gòu)，每次出隊(duì)列的是優(yōu)先權(quán)最高的元素。用堆實(shí)現(xiàn)其存儲(chǔ)表達(dá),可以高效運(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)有且僅有一條途徑。Ｈuffｍan樹:帶權(quán)途徑長度最小的二叉樹應(yīng)是權(quán)值大的外結(jié)點(diǎn)離根結(jié)點(diǎn)最近的擴(kuò)充二叉樹。帶途徑長度最小的擴(kuò)充二叉樹不一定是完全二叉樹。集合是成員（元素)的一個(gè)群集。集合中的成員可以是原子(單元素），也可以是集合。字典是一些元素的集合,每個(gè)元素有一個(gè)稱作關(guān)鍵碼(keｙ）的域，不同元素的關(guān)鍵碼互不相同。散列方法：抱負(fù)的搜索方法是可以不通過比較，一次直接從字典中得到要搜索的元素。假如在元素存儲(chǔ)位置與其關(guān)鍵碼之間建立一個(gè)擬定的相應(yīng)函數(shù)關(guān)系Hasｈ(),使得每個(gè)關(guān)鍵碼與結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相相應(yīng):Ａｄdress=Hａｓh（key)。在插入時(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)鍵碼集合比散列表地址集合大得多。因此有也許通過散列函數(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)記這個(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è)若表中有ＣuｒrｅntSize個(gè)元素，則順序搜索從表的先端開始,順序用各元素的關(guān)鍵碼與給定值x進(jìn)行比較若找到與其值相等的元素,則搜索成功,給出該元素在表中的位置。若整個(gè)表都已檢測(cè)完仍未找到關(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)鍵碼。４左子樹和右子樹也是二叉搜索樹。二叉搜索樹為二叉排序樹假如對(duì)一棵二叉搜索樹進(jìn)行中序遍歷,可以按從小到大的順序,將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為ｘ的元素,搜索過程從根結(jié)點(diǎn)開始。假如根指針為NＵLL，則搜索不成功；否則用給定值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)存在。在插入之前,先使用搜索算法在樹中檢查要插入元素有還是沒有。假如搜索成功，說明樹中已有這個(gè)元素,不再插入;假如搜索不成功,說明樹中本來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。圖定義：圖是由頂點(diǎn)集合（ｖerｔex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Ｇraph=（V,E)其中V={x|ｘ?某個(gè)數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；E＝｛(x,y)|ｘ，ｙ?V}或E={＜x,y>｜x，ｙ?V&&Path（x，y）},是頂點(diǎn)之間關(guān)系的有窮集合,也叫做邊(ｅdge)集合。Path(x,y)表達(dá)從x到y(tǒng)的一條單向通路,它是有方向的。有向圖與無向圖：在有向圖中,頂點(diǎn)對(duì)＜x,y>是有序的。在無向圖中，頂點(diǎn)對(duì)（ｘ,y)是無序的。完全圖:若有n個(gè)頂點(diǎn)的無向圖有n(n-１)/2條邊，則此圖為完全無向圖。有n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,則此圖為完全有向圖在圖的鄰接矩陣表達(dá)中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表,尚有一個(gè)表達(dá)各個(gè)頂點(diǎn)之間關(guā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)值cｏst。頂點(diǎn)表的第i個(gè)頂點(diǎn)中保存該頂點(diǎn)的數(shù)據(jù)，以及它相應(yīng)邊鏈表的頭指針adｊ最短途徑問題：假如從圖中某一頂點(diǎn)（稱為源點(diǎn))另一頂點(diǎn)(稱為終點(diǎn))的途徑也許不止一條,如何找到一條途徑使得沿此途徑上各邊上的權(quán)值總和達(dá)成最小。排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。數(shù)據(jù)表（ｄatalist):它是待排序數(shù)據(jù)元素的有限集合。排序碼(ｋey):通常數(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)前插入ｎewnodｅ→lｉｎk=ｆirst；first=neｗｎoｄe;第二種情況：在鏈表中間插入newnｏde→link=p→link; p→linｋ=newnｏde;第三種情況：在鏈表末尾插入nｅwnoｄe→link＝p→link; ?p→liｎk=lasｔ＝neｗnｏdｅ；２、鏈表插入算法實(shí)現(xiàn)３、鏈表結(jié)點(diǎn)刪除算法intLisｔ：：Iｎsｅrｔ(coｎstintx,ｃonｓｔinti){／／在鏈表第i個(gè)結(jié)點(diǎn)處插入新元素xListNoｄe*p=fiｒst;iｎtｋ=0；wｈile(p!=NULL&&k<i－１）{p＝p→ｌink;k++;}//找第i-1個(gè)結(jié)點(diǎn)if（ｐ==ＮＵLL&＆fｉｒsｔ!=NＵLL){?cｏuｔ<<“無效的插入位置!\n”;retｕrn０;}?ＬｉｓｔNｏde＊ｎewｎｏｄe=newListNｏｄe(ｘ,NULL);/／創(chuàng)建新結(jié)點(diǎn),其數(shù)據(jù)為x,指針為0if（fiｒｓt＝=ＮＵLL|｜i==0)｛/／插在表前ｎｅwnｏde→link＝ｆｉrst;???if（fｉｒst==NULＬ)lａsｔ＝neｗnode;?firsｔ=ｎewnｏde;｝else{／/插在表中或末尾neｗnｏde→lｉnk=p→lｉnk； if（p→link=＝NUＬL）last=neｗｎｏde;p→lｉnk=ｎeｗｎode;}return1; ??? ?}intList::Removｅ(ｉnti)｛／/在鏈表中刪除第i個(gè)結(jié)點(diǎn)Nodｅ*p=fiｒst,＊q;intｋ=0;while(ｐ!=ＮＵＬL&&k<ｉ-1)｛ｐ=p→link；ｋ+＋;｝//找第i-1個(gè)結(jié)點(diǎn)iｆ（p＝=NULＬ||p→link=＝NＵLL){cout<<“無效的刪除位置!＼n”；reｔuｒn0;}if(i==０)｛／／刪除表中第1個(gè)結(jié)點(diǎn)q＝fiｒsｔ;//ｑ保存被刪結(jié)點(diǎn)地址p=firsｔ=first→link;／/修改fiｒst｝ ?eｌｓe{??//刪除表中或表尾元素ｑ=p→link；p→liｎk=q→link;／/重新鏈接｝? ?if（q=＝last)lａst＝ｐ; ／/也許修改ｌａsｔｋ＝q→dａt(yī)ａ;deleteq;/／刪除qｒｅｔurnk; ??}在帶表頭結(jié)點(diǎn)的單鏈表,第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)newnoｄｅ→lｉnｋ＝p→ｌiｎk;?if(ｐ→link=＝NULL)last=ｎewnｏdｅ；p→ｌiｎk=newｎode;從帶表頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)結(jié)點(diǎn)q=p→ｌink；p→link=q→liｎk;delｅteq;if(p→lｉnｋ==NＵLＬ)lasｔ=ｐ;排序直接插入排序的算法折半插入排序的算法#inclｕde"ｄａt(yī)aＬｉst.ｈ"teｍpｌate<cｌassT>vｏidInsertＳort（daｔａＬist＜Ｔ>&Ｌ,intleft，intrｉght）{/／依次將元素Ｌ.Vectoｒ［i]按其排序碼插入到有序表/／L.Ｖｅｃtor[ｌeft]，…,L.Vector[i-1]中,使得//L.Vecｔor[lｅft]到L．Vｅctoｒ[ｉ］有序。Elｅmｅｎt<T>temp;inti,j;ｆｏr（i=lｅｆt＋1;ｉ＜=ｒighｔ；ｉ+＋)if(Ｌ[ｉ]＜L[i-1]){ｔemp＝L[ｉ］;ｊ=i-1;do｛L[j+1]=L［j]；j--；}whiｌｅ（j＞＝leｆt&&ｔemp<L[ｊ]);Ｌ[j+1]=temp;｝｝; #ｉncluｄe"dataList.ｈ"template＜claｓsT＞voidBinaryInseｒtSoｒｔ(ｄatａList＜Ｔ>&L,coｎsｔintlｅft,ｃonstiｎｔright)｛//運(yùn)用折半搜索,在Ｌ.Vectoｒ[leｆt］到L.Veｃtor[i-1]中//查找L.Veｃtｏr[ｉ]應(yīng)插入的位置,再進(jìn)行插入。Ｅleｍeｎｔ＜Ｔ>ｔｅmp;inti,lｏw，high,ｍiddlｅ,k；foｒ(i=lefｔ＋1;i<=right；ｉ++){temp=Ｌ[i]；low=left;high＝ｉ－1;ｗhilｅ(ｌoｗ＜＝high){ //折半搜索插入位置mｉddle=(ｌow＋ｈｉgｈ)/2；?/／取中點(diǎn)iｆ(temp<L[ｍiddlｅ］)?//插入值小于中點(diǎn)值high=midｄle-1;?／/向左縮社區(qū)間eｌseｌｏｗ=midｄle+1;?//否則,向右縮社區(qū)間}foｒ(ｋ=i-1;k>=ｌow;k--)Ｌ[k+1]=L[k］；?/／成塊移動(dòng),空出插入位置 L［low］=ｔｅｍp; //插入}}；堆排序的算法直接選擇排序的算法tｅｍpｌaｔe＜ｃlａsｓT>vｏiｄHeaｐSorｔ(datａLisｔ<T>&L){//對(duì)表L.Ｖｅｃtoｒ［0]到L.Vector[n-1]進(jìn)行排序,使得表／/中各個(gè)元素按其排序碼非遞減有序inｔｉ,n=L.ｌength()；foｒ（ｉ=(n-２)/２;i>=０;i-－) /／將表轉(zhuǎn)換為堆ｓiftDown(L,i，n-1）; for（ｉ=ｎ-１;i>=0;i-－){ ?／/對(duì)表排序L.Swaｐ(0，ｉ);siｆｔDown(L,0,i-１);}｝;#iｎclude"datａLiｓｔ.h"tempｌaｔe<cｌaｓsT>ｖoidSelectSort(dａt(yī)aＬisｔ＜Ｔ>＆L，ｃｏｎstintleｆt，coｎstｉnｔｒigｈt)｛fｏr(ｉnｔi=left;ｉ<rigｈt;i＋+){intk=i;/在L[ｉ]到L[n-1]找最小排序碼元素ｆoｒ(intj=ｉ+1；ｊ<=ｒiｇhｔ;ｊ++）ｉf（L[ｊ］<Ｌ[k]）k=j;if（ｋ!=i）Ｓwap(L［ｉ］,L[k］)； //互換}};希爾排序的算法起泡排序的算法#ｉｎcｌuｄe"dａt(yī)ａLｉsｔ.h＂teｍplaｔe＜ｃｌassT＞voidShellsorｔ（dataLiｓt<T＞&Ｌ,cｏnsｔiｎtleft，constｉntrｉght）｛inti,j,ｇap=rｉｇhｔ-lｅft＋１;??//增量的初始值 Elemenｔ<T>tｅｍp;dｏ{gaｐ=gａp/3+1；? ／/求下一增量值foｒ(ｉ＝lｅｆｔ+gap；i<=righｔ;i+＋)if（L[ｉ]＜L［ｉ－gaｐ]){??／/逆序teｍp=Ｌ［i］;j＝i-gap;dｏ{L[j+gap]=L[j];ｊ=j－gaｐ；｝while（j>＝ｌefｔ&&temp＜L［j］);Ｌ［j+gap]=tｅmｐ； ／/將ｖeｃtor[i］回送}}whiｌe(gap>1);};ｔｅmｐｌatｅ＜classT>voiｄBｕbbleSort(daｔaLiｓt＜T＞＆L,coｎｓtiｎtleft,ｃonsｔiｎｔｒｉｇht){intpａss＝left+1,exｃhaｎgｅ=1;whｉｌｅ（pasｓ<=right&&exchangｅ){ｅｘcｈanｇe=0;? //標(biāo)志為0假定未互換ｆor（intj=ｒiｇht；j>＝pａss;j--)iｆ(L[j-1]>L[j］)｛?/／逆序Swap(Ｌ[j-１］,L[j]）; //互換 exchange＝１;//標(biāo)志置為1，有互換}pａss＋＋；}｝;兩路歸并算法最大堆的向下調(diào)整算